Computer Design A computer aided design and VLSI approach Paul J. Drongowski Chapter 8 - Datapath synthesis. This chapter presents a collection of heuristic rules for translating an ISA to datapath composed of coarse grain building blocks. These rules address the declaration of storage objects, the translation of assignment statements to operators and interconnections, and the practical considerations of power and control signals. Section 1 - Declarations. Of course, the ISA storage elements must be implemented using registers, register files and memory circuits. ISA storage elements were declared as C language variables and are translated to building blocks according to the rules given below. * For each simple register, draw a register block. The number of bits in the register block depends upon the ISA specification for that register. Be prepared to add intrinsic operations (increment, clear, etc.) to the block later. * For each "small" array, find a register file of sufficient size to represent the array. Replicate blocks to achieve the specified word size and stack blocks to increase the capacity (indexed length) of the register file. * For each "large" array, replicate and stack memory blocks. The notions of "small" and "large" are based upon engineering judgment and will vary with technology. For example, the 74LS89 register circuit (16 words of 4 bits) is an inappropriate choice for constructing a one million byte memory. It would take 2^17 74LS89 circuits to build the 1 Mbyte memory with large amounts of board area, current and heat dissipation. Eight one million bit dynamic memory chips would be more economical. The high speed of the 74LS89 makes it a good choice for the implementation of a general register set, however, where the number of parts required is low and high power is acceptable. External input and ports are translated to external input and output interface circuits. Again, the circuits to be used are technology sensitive and must accommodate the packaging and electrical standards in use. VLSI circuits, for example, have the following requirements. * An input circuit requires a bonding pad for external connection, a hysteresis circuit for TTL compatibility and static protection circuitry. * An output has a bonding pad and large transistors to drive a signal off-chip at high speed. * Bi-directional interfaces need a bonding pad, hysteresis, static protection and a drive circuit that can be disabled when the interface is off the shared bus. In all three cases, the interface circuits must be drawn at the edges of the chip floor plan to support manual or automatic wire bonding. ISA name C type Building block Words Bits -------- ------ -------------- ----- ---- AC char Simple register 1 8 MD char Simple register 1 8 CR char Simple register 1 8 SR char Simple register 1 8 IP char Simple register 1 8 Z char Simple register 1 1 M char Read only memory 256 8 Table 1 - Preliminary storage blocks. A preliminary assignment of variables to storage blocks is summarized in Table 1. Temporary storage elements and intrinsic operations will be added later. Section 2 - Assignment statements. The simple assignment statement, "R = S," implies that a transfer path must exist from register S to register R (Figure 1.) Initially, we will assume that a direct transfer path is required. For a complex datapath with temporary registers, it may be possible to program an indirect path that requires a sequence of intermediate transfers. The penalty, of course, is an increase in execution time. --- --- | R |<----| S | --- --- Figure 1 - Simple assignment path. If we write the assignment, "R = S + T," the datapath must provide a data operator which performs addition, a path from S to the left input of the operator, a path from T to the right input of the operator and a path from the output of the operator to the register R (Figure 2.) This requirement holds for any assignment involving a data operator. Like a simple transfer, temporary registers may be introduced into the transfer paths and may be used to hold the intermediate results produced during the evaluation of a complex expression. The penalty, again, is execution time as more than one control step will be required for evaluation. ___ --- --- | |<----| S | | R |<----| + | --- --- | |<----| T | --- --- Figure 2 - Datapath for the expression "R = S + T" The naive translation of an assignment statement, therefore, has three steps. First, the designer must instantiate a combinational block for each data operator appearing in the expression on the right hand side of the assignment. Next, the designer must draw a path from the expression operands to the inputs of the data operators. Finally, a path is drawn from the output of the operator producing the result of the expression to the destination register. The naive translation of assignments will yield a complex maze of registers, data operators and interconnections. Complexity can be reduced by introducing temporary registers and more general data operators such as an arithmetic logic unit. Thus, a single adder or ALU can be used to handle the arithmetic needs of the ISA behavior. The designer must still ultimately guarantee that the datapath will "cover" every assignment in the ISA. The ideas of need and covering are familiar to computer scientists. Producer and consumer relationships are called "data dependencies." A data item must be produced by a register operand, data operator or subexpression before it can be consumed by the destination register. By building a table of data dependencies, the datapath can be checked against the data dependencies as it evolves to be sure that all behavior specified by the ISA is covered, i.e., that all expressions can be evaluated and stored by the datapath design. Data dependencies have the advantage of accommodating a wide range of design styles (zero, two or three main busses, etc.) and multiple control steps through the use of transitive closure on the producer-consumer relationships. Left Right Operand Operand Operation Destination ------- ------- --------- ----------- Input AC AC Output AC MD + AC AC M & AC 2 / AC AC 2 * AC M CR M AC M MD CR 1 - CR AC MD MD AC M<3:0> Exception M IP IP 2 + SR SR IP IP 1 + IP IP 2 + IP 0 Z 1 Z Table 2 - SP.1 data dependencies. Section 3 - Special cases. Some special cases and opportunities naturally arise when translating from the ISA to its implementation. Register file indices, for example, must be produced. A likely source for an index is a bit-field selected from the register holding the current instruction. In the assignment statement, "R[IR<3:0>] = T," the four low order bits of the register IR are used to select a word from the register file R. The transfer paths required are shown in Figure 3. It may also be necessary to connect the index of the register file to a group of control signals emanating from the controller. --- | T | --- | V ---- --- | IR |----->| R | ---- --- Figure 3 - Register file indexing. As described in Chapter 8 on building blocks, intrinsic operations are the primitive operations which a building block can perform. The intrinsic operations which can be performed by counters and shift registers, for example, are especially useful, since increment, decrement, shift right and shift left operations can be performed in place without bringing a data value out of the register, modifying it and writing it back. Such intrinsic operations save external circuitry and wiring. Situation Intrinsic operation --------- ------------------- R = 0 Clear R = 1 Preset (Set to all ones) R = R + 1 Increment R = R - 1 Decrement R = R / 2 Right shift R = R * 2 Left shift Table 3 - Intrinsic operations. Table 4 shows the possible assignment of intrinsic operations to the SP.1 storage blocks. The SP.1 ISA shifts the register AC both left and right, suggesting that a shift register be used to represent AC. The instruction pointer IP is incremented by one or two after every instruction. The Decrement instruction decreases the value of CR by one. Both IP and CR are good candidates for implementation using 8-bit counting registers. Finally, the Z flag must occasionally be cleared and requires the intrinsic function "Clear." ISA name C type Building block Words Bits Operations -------- ------ -------------- ----- ---- ---------- AC char Shift register 1 8 Right, Left MD char Simple register 1 8 CR char Counter 1 8 Decrement SR char Simple register 1 8 IP char Counter 1 8 Increment Z char Simple register 1 1 Clear, Preset M char Read only memory 256 8 Table 4 - SP.1 storage blocks with intrinsic operations. Any constant values (with perhaps the exception of zero and one) must be generated from a read only memory. A single special constant can be created by selectively tying bits to either the positive voltage or ground rail (Figure 3.) Current limiting resistors are usually required. If more than one constant is needed, a ROM block is preferable. A memory index must be provided during operation to select a particular value from the ROM. Since microinstructions are already stored in ROM for microprogrammed machines, one natural solution is to store and retrieve the needed constant value from an "emit" field within the current microinstruction. This solution may be uneconomical if the emit field is frequently unused or very long. +5V Gnd +5V +5V Gnd Gnd +5V +5V | | | | | | | | R | R R | | R R | | | | | | | | V V V V V V V V 1 0 1 1 0 0 1 1 Figure 3 - Constant value. ROM index --- | | R |<--- V --- | --- ---| K | (a) ROM implementation --- | --- | S |<--- --- ---------------------------- | | K | | microinstruction ---------------------------- | ------- (b) Emit field implementation | | V V --- --- | R | | S | --- --- Figure 4 - Multiple constants. Often a single register will be the destination of two or more assignments. Since only one data value can be transferred into the register at any time, a selector must be inserted between the source registers (data operators or ports) and the input of the destination register. The selection signal(s) must be generated and routed to the selector. --- --- | S | | T | --- --- | | ------------ | Selector |<---- Select ------------ | V --- | R | --- Figure 5 - Multiple source - single destination. The naive translation scheme proposed earlier produces a separate data operator (combinational block) for every operator that appears in an expression. The resulting systems will have a large number of specialized combinational blocks with a high cost in space, power and wiring complexity. Since all expressions are performed in one control step, the implementation will be very fast. To reduce the component count, the many specialized operators may be replaced by a more general building block such as an ALU (Figure 6.) The ALU must be shared between several different computations and as a centralized resource, operations must be serialized, thereby reducing the number of computations that can be performed in parallel. --- --- | S | | T | --- --- | | ----------- | ALU |<---- Operation ----------- | V --- | R | --- Figure 6 - Operator folding. Section 4 - Power and control signals. The preceding figures are simplified and do not show power connections (Figure 7.) In addition to power, control signals and the clock must be routed between building blocks. This will increase the overall complexity of the wire routing problem. For printed circuit cards with three or more layers, one can usually find a good path for all of these signals by jumping between layers when a collision is imminent. The standard silicon gate nMOS process, however, only provides one layer of metalization. This single layer must distribute power and due to the lower capacitance of metal, must carry long distance signals such as the clock and shared busses. --------------- +5V | | --- --- | R |<----| S | --- --- | | --------------- Ground Figure 7 - Power busing. Once all of the building blocks have been selected and drawn for the ISA implementation, the designer should make a list of the control signals used by the blocks. This list will assist the design of the microinstruction or random logic, finite state machine controller. Control values and their meanings should also be provided. An example format is given in Table 5. AC - Shift register Right 0: No effect 1: Shift right Left 0: No effect 1: Shift left ALU - Arithmetic logic unit Op 0: Addition 1: Subtraction 2: Bit-wise AND 3: Bit-wise OR Table 5 - Partial list of SP.1 control signals. Copyright (c) 1987-2013 Paul J. Drongowski