6.004 Computation Structures: Lab#3

MASSACHUSETTS INSTITUTE OF TECHNOLOGY DEPARTMENT OF ELECTRICAL ENGINEERING AND COMPUTER SCIENCE 6.004 Computation Structures Lab #3 In this laboratory exercise, we’ll build the arithmetic and logic unit (ALU) for the Beta processor. The ALU has two 32-bit inputs (which we’ll call “A” and “B”) and produces one 32-bit output. We’ll start by designing each piece of the ALU as a separate circuit, each producing its own 32 bit output. Then we’ll combine these outputs into a single ALU result. When designing circuitry there are three separate factors that can be optimized: (1) design for maximum performance (minimum latency) (2) design for minimum cost (minimum area) (3) design for the best cost/performance ratio (minimize area*latency) Happily it’s often possible to do all three at once but in some portions of the circuit some sort of design tradeoff will need to be made. When designing your circuitry you should choose which of these three factors is most important to you and optimize your design accordingly. A functional ALU design will earn six points. Four additional points can be earned if you implement the optional multiplier unit – see the section labeled “Optional Design Problem: Implementing Multiply” for details. Standard Cell Library The building blocks for our design will be a family of logic gates that are part of a standard cell library. The available combinational gates are listed in the table below along with information about their timing, loading and size. You can access the library by starting your netlist with the following include statements: .include "/mit/6.004/jsim/nominal.jsim" .include "/mit/6.004/jsim/stdcell.jsim" Everyone should use the provided cells in creating their design. The timings have been taken from a 0.18 micron CMOS process measured at room temperature. 6.004 Computation Structures -1- Lab #3 Netlist Xid Xid Xid Xid Xid Xid Xid Xid Xid Xid Xid Xid Xid Xid Xid Xid Xid Xid z z a a a a a a a a e e e e a a a a constant0 constant1 z inverter z inverter_2 z inverter_4 z inverter_8 z buffer z buffer_2 z buffer_4 z buffer-8 a z tristate a z tristate_2 a z tristate_4 a z tristate_8 b z and2 b c z and3 b c d z and4 b z nand2 Xid a b c z nand3 Xid a b c d z nand4 Xid Xid Xid Xid a a a a b b b b z c c z or2 z or3 d z or4 nor2 Function Z =0 Z =1 Z = A Z = A Z = A when e=1 else Z not driven Z = A⋅ B Z = A⋅ B⋅C Z = A⋅ B⋅C ⋅ D Z = A⋅ B Z = A⋅ B⋅C Z Z Z Z = = = = A⋅ B⋅C ⋅ D A+ B A+ B+C A+ B+C + D tCD tPD tR tF load (ns) (ns) (ns/pf) (ns/pf) (pf) — — — — — — .005 .02 2.3 .009 .02 1.1 .009 .02 .56 .02 .11 .28 .02 .08 2.2 .02 .07 1.1 .02 .07 .56 .02 .07 .28 .03 .15 2.3 .03 .13 1.1 .02 .12 .6 .02 .11 .3 .03 .12 4.5 .03 .15 4.5 .03 .16 4.5 .01 .03 4.5 — — 1.2 .6 .3 .15 1.2 .6 .3 .15 1.3 .6 .3 .17 2.3 2.6 2.5 2.8 — — .007 .013 .027 .009 .003 .005 .01 .02 .004 .006 .011 .02 .002 .002 .002 .004 size (μ2) 0 0 10 13 20 56 13 17 30 43 23 30 40 56 13 17 20 10 .01 .05 4.2 3.0 .005 13 .01 .07 4.4 3.5 .005 17 .15 .21 .29 .05 4.5 4.5 4.5 6.7 2.5 2.5 2.6 2.4 .002 .003 .003 .004 Z = A+ B .03 .04 .06 .01 Xid a b c z nor3 Z = A+ B+C .02 .08 8.5 2.4 .005 13 Xid a b c d z nor4 Z = A+ B+C + D Z = A⊕ B .02 .12 9.5 2.4 .005 20 Z = A⊕ B .03 .03 .14 .14 4.5 4.5 2.5 2.5 .006 27 .006 27 Xid a1 a2 b z aoi21 Z = ( A1 ⋅ A2) + B .02 .07 6.8 2.7 .005 13 Xid a1 a2 b z oai21 Z = ( A1 + A2) ⋅ B Z = D0 when S = 0 Z = D1 when S = 1 .02 .07 6.7 2.7 .005 17 .02 .12 4.5 2.5 .005 27 Z=D0 when S0=0, S1=0 Z=D1 when S0=1, S1=0 Z=D2 when S0=0, S1=1 Z=D3 when S0=1, S1=1 .04 .19 4.5 2.5 .006 66 D→Q on CLK↑ .03 .19 4.3 2.5 .002 56 Xid a b z xor2 Xid a b z xnor2 Xid s d0 d1 z mux2 Xid s0 s1 d0 d1 d2 d3 z mux4 (Note order of s0 and s1!) Xid d clk q dreg tsetup = .15, thold = 0 6.004 Computation Structures -2- Lab #3 13 17 20 10 Gate-level Simulation Since we’re designing at the gate level we can use a faster simulator that only knows about gates and logic values (instead of transistors and voltages). You can run JSim’s gate-level simulator by in the toolbar. Note that your design can’t contain any mosfets, resistors, capacitors, clicking etc.; this simulator only supports the gate primitives in the standard cell library. Inputs are still specified in terms of voltages (to maintain netlist compatability with the other simulators) but the gate-level simulator converts voltages into one of three possible logic values using the VIL and VIH thresholds specified in nominal.jsim: 0 1 X logic low (voltages less than or equal to VIL threshold) logic high (voltages greater than or equal to VIH threshold) unknown or undefined (voltages between the thresholds, or unknown voltages) A fourth value “Z” is used to represent the value of nodes that aren’t being driven by any gate output (e.g., the outputs of tristate drivers that aren’t enabled). The following diagram shows how these values appear on the waveform display: 0 1 X Z Connecting electrical nodes together using .connect JSim has a control statement that lets you connect two or more nodes together so that they behave as a single electrical node: .connect node1 node2 node3... The .connect statement is useful for connecting two terminals of a subcircuit or for connecting nodes directly to ground. For example, the following statement ties nodes cmp1, cmp2, ..., cmp31 directly to the ground node (node "0"): .connect 0 cmp[31:1] Note that the .connect control statement in JSim works differently than many people expect. For example, .connect A[5:0] B[5:0] will connect all twelve nodes (A5, A4, ..., A0, B5, B4, ..., B0) together -- usually not what was intended. To connect two busses together, one could have entered .connect A5 B5 .connect A4 B4 ... which is tedious to type. Or one can define a two-terminal device that uses .connect internally, and then use the usual iteration rules (see next section) to make many instances of the device with one "X" statement: 6.004 Computation Structures -3- Lab #3 .subckt knex a b .connect a b .ends X1 A[5:0] B[5:0] knex Using iterators to create multiple gates with a single “X” statement JSim makes it easy to specify multiple gates with a single "X" statement. You can create multiple instances of a device by supplying some multiple of the number of nodes it expects, e.g., if a device has 3 terminals, supplying 9 nodes will create 3 instances of the device. To understand how nodes are matched up with terminals specified in the .subckt definition, imagine a device with P terminals. The sequence of nodes supplied as part of the "X" statement that instantiates the device are divided into P equal-size contiguous subsequences. The first node of each subsequence is used to wire up the first device, the second node of each subsequence is used for the second device, and so on until all the nodes have been used. For example: Xtest a[2:0] b[2:0] z[2:0] xor2 is equivalent to Xtest#0 a2 b2 z2 xor2 Xtest#1 a1 b1 z1 xor2 Xtest#2 a0 b0 z0 xor2 since xor2 has 3 terminals. There is also a handy way of duplicating a signal: specifying "foo#3" is equivalent to specifying "foo foo foo". For example, xor'ing a 4-bit bus with a control signal could be written as Xbusctl in[3:0] ctl#4 out[3:0] xor2 which is equivalent to Xbusctl#0 Xbusctl#1 Xbusctl#2 Xbusctl#3 in3 in2 in1 in0 ctl ctl ctl ctl out3 out2 out1 out0 xor2 xor2 xor2 xor2 Using iterators and the “constant0” device from the standard cell library, here’s a better way of connecting cmp[31:1] to ground: Xgnd cmp[31:1] constant0 Since the “constant0” has one terminal and we supply 31 nodes, 31 copies of the device will be made. ALU Design NOTE: the ALUFN signals used to control the operation of the ALU circuitry use an encoding chosen to make the design of the ALU circuitry as simple as possible. This encoding is not the same as the one used to encode the 6-bit opcode field of Beta instructions. In Lab 6, you’ll build some logic (actually a ROM) that will translate the opcode field of an instruction into the appropriate ALUFN control bits. 6.004 Computation Structures -4- Lab #3 (A) Design an adder/subtractor unit that operates on 32-bit two’s complement inputs and generates a 32-bit output. It will be useful to generate three other output signals to be used by the comparison logic in part (B): “Z” which is true when the S outputs are all zero, “V” which is true when the addition operation overflows (i.e., the result is too large to be represented in 32 bits), and “N” which is true when the S is negative (i.e., S31 = 1). Overflow can never occur when the two operands to the addition have different signs; if the two operands have the same sign, then overflow can be detected if the sign of the result differs from the sign of the operands: V = XA31 ⋅ XB31 ⋅ S 31 + XA31 ⋅ XB31 ⋅ S 31 Note that this equation uses XB31, which is the high-order bit of the B operand to the adder itself (i.e., after the XOR gate – see the schematic below). ALUFN0 will be set to 0 for an ADD (S = A + B) and 1 for a SUBTRACT (S = A – B); A[31:0] and B[31:0] are the 32-bit two’s complement input operands; S[31:0] is the 32 bit result; z/v/n are the three condition code bits described above. We’ll be using the “little-endian” bit numbering convention where bit 31 is the most-significant bit and bit 0 is the least-significant bit. The following schematic is one suggestion for how to go about the design: Z V N 32 A31…A0 XA 32 B31…B0 32 x32 S31…S0 32-bit add S XB carry in 32 ALUFN0 The ALUFN0 input signal selects whether the operation is an ADD or SUBTRACT. To do a SUBTRACT, the circuit first computes the two’s complement negation of the “B” operand by inverting “B” and then adding one (which can be done by forcing the carry-in of the 32-bit add to be 1). Start by implementing the 32-bit add using a ripple-carry architecture (you’ll get to improve on this later on the lab). You’ll have to construct the 32-input NOR gate required to compute Z using a tree of smaller fan-in gates (the parts library only has gates with up to 4 inputs). We’ve created a test jig to test your adder. Your netlist should incorporate the following three .include statements .include "/mit/6.004/jsim/nominal.jsim" .include "/mit/6.004/jsim/stdcell.jsim" .include "/mit/6.004/jsim/lab3adder.jsim" 6.004 Computation Structures -5- Lab #3 and the following subcircuit definition (you can of course define other subcircuits as well) .subckt adder32 ALUFN[0] A[31:0] B[31:0] s[31:0] z v n … your adder/subtractor circuit here … .ends To use the test jig, make sure your design file contains a definition for an “adder32” subcircuit as shown above. Then do a gate-level simulation; a waveform window showing the adder32 inputs and outputs should appear. Next click the checkoff button (the green checkmark) in the toolbar. JSim will check your circuit’s results against a list of expected values and report any discrepancies it finds. Using this test jig file, nothing will be sent to the on-line server – it’s provided to help test your design as you go. The Beta instruction set includes three compare instructions (CMPEQ, CMPLT, CMPLE) that compare the “A” and “B” operands. We can use the adder unit designed above to compute “A−B” and then look at the result (actually just the Z, V and N condition codes) to determine if A=B, A B or A≤B. The compare instructions generate a 32-bit Boolean result, using “0” to represent false and “1” to represent true. (B) Design a 32-bit compare unit that generates one of two constants (“0” or “1”) depending on the ALUFN control signals (used to select the comparison to be performed) and the Z, V, and N outputs of the adder/subtractor unit. Clearly the high order 31 bits of the output are always zero. The least significant bit of the output is determined by the comparison being performed and the results of the subtraction carried out by the adder/subtractor: Comparison Equation for LSB LSB = Z LSB = N ⊕ V LSB = Z + (N ⊕ V) ALUFN2 0 1 1 ALUFN1 1 0 1 ALUFN[2:1] are used to control the compare unit since we also need to control the adder/subtractor unit (i.e., ALUFN0 = 1 to force a subtract). Performance note: the Z, V and N inputs to this circuit can only be calculated by the adder/subtractor unit after the 32-bit add is complete. This means they arrive quite late and then require further processing in this module, which in turn makes cmp0 show up very late in the game. You can speed things up considerably by thinking about the relative timing of Z, V and N and then designing your logic to minimize delay paths involving late-arriving signals. We’ve created a test jig to test your compare unit. Your netlist should incorporate the following three .include statements .include "/mit/6.004/jsim/nominal.jsim" .include "/mit/6.004/jsim/stdcell.jsim" .include "/mit/6.004/jsim/lab3compare.jsim" and the following subcircuit definition 6.004 Computation Structures -6- Lab #3 .subckt compare32 ALUFN[2:1] z v n cmp[31:0] … your compare circuit here … .ends (C) Design a 32-bit Boolean unit for the Beta’s logic operations. One implementation of a 32-bit boolean unit uses a 32 copies of a 4-to-1 multiplexer where ALUFN0, ALUFN1, ALUFN2, and ALUFN3 encode the operation to be performed, and Ai and Bi are hooked to the select inputs. This implementation can produce any of the 16 2-input Boolean functions; we’ll only be using 4 of the possibilities. The following table shows the encodings for the ALUFN[3:0] control signals used by the test jig. If you choose a different implementation you should also include logic to convert the supplied control signals into signals appropriate for your design. Operation AND 1000 OR 1110 XOR 0110 “A” 1010 ALUFN[3:0] We’ve created a test jig to test your boolean unit. Your netlist should incorporate the following three .include statements .include "/mit/6.004/jsim/nominal.jsim" .include "/mit/6.004/jsim/stdcell.jsim" .include "/mit/6.004/jsim/lab3boolean.jsim" and the following subcircuit definition .subckt boole32 ALUFN[3:0] A[31:0] B[31:0] boole[31:0] … your boolean unit circuit here … .ends (D) Design a 32-bit shifter that implements SRA, SHR and SHL instructions. The “A” operand supplies the data to be shifted and the low-order 5 bits of the “B” operand are used as the shift count (i.e., from 0 to 31 bits of shift). The desired operation will be encoded on ALUFN[1:0] as follows: Operation SHL (shift left) 6.004 Computation Structures ALUFN[1:0] 00 -7- Lab #3 SHR (shift right) SRA (shift right with sign extension) 01 11 With this encoding, ALUFN0 is 0 for a left shift and 1 for a right shift and ALUFN1 controls the sign extension logic on right shift. For SHL and SHR, 0’s are shifted into the vacated bit positions. For SRA (“shift right arithmetic”), the vacated bit positions are all filled with A31, the sign bit of the original data so that the result will be the same as dividing the original data by the appropriate power of 2. The simplest implementation is to build two shifters—one for shifting left and one for shifting right—and then use a 2-way 32-bit multiplexer to select the appropriate answer as the unit’s output. It’s easy to build a shifter after noticing that a multi-bit shift can be accomplished by cascading shifts by various powers of 2. For example, a 13-bit shift can be implemented by a shift of 8, followed by a shift of 4, followed by a shift of 1. So the shifter is just a cascade of multiplexers each controlled by one bit of the shift count. The schematic below shows a possible implementation of the left shift logic; the right shift logic is similar with the slight added complication of having to shift in either “0” or “A31.” Another approach that adds latency but saves gates is to use the left shift logic for both left and right shifts, but for right shifts, reverse the bits of the “A” operand on the way in and reverse the bits of the output on the way out. A[31:0] 0 x32 A[15:0],GND#16 W[31:0] 0 W[23:0],GND#8 1 x32 W[31:0] 1 B4 X[31:0] X[27:0],GND#4 B3 0 x32 Y[31:0] Y[29:0],GND#2 B2 0 Z[30:0],GND 1 x32 0 x32 Y[31:0] 1 Z[31:0] X[31:0] Z[31:0] 1 B1 SL[31:0] B0 We’ve created a test jig to test your shift unit. Your netlist should incorporate the following three .include statements .include "/mit/6.004/jsim/nominal.jsim" .include "/mit/6.004/jsim/stdcell.jsim" .include "/mit/6.004/jsim/lab3shifter.jsim" and the following subcircuit definition .subckt shift32 ALUFN[1:0] A[31:0] B[4:0] shift[31:0] … your shifter circuit here … .ends 6.004 Computation Structures -8- Lab #3 (E) Combine the outputs of the adder, compare, boolean and shift units to produce a single ALU output. The simplest approach is to use a 4-way 32-bit multiplexer as shown in the schematic below: A[31:0] B[31:0] ALUFN0 A[31:0] B[31:0] ALUFN[3:0] add Z V N 00 boole 01 ALU[31:0] A[31:0] B[4:0] ALUFN[1:0] shift 10 Z V N ALUFN[2:1] cmp 11 ALUFN[5:4] Two additional control signals (ALUFN[5:4]) have been introduced to select which unit will supply the value for the ALU output. The encodings for ALUFN[5:0] used by the test jig are shown in the following table: Operation ADD SUB AND OR XOR “A” (LDR) SHL SHR SRA CMPEQ CMPLT CMPLE 6.004 Computation Structures ALUFN[5:0] 000000 000001 011000 011110 010110 011010 100000 100001 100011 110011 110101 110111 -9- hex 0x00 0x01 0x18 0x1E 0x16 0x1A 0x20 0x21 0x23 0x33 0x35 0x37 Lab #3 (F) When you’ve completed your design, you can use lab3checkoff_6.jsim to test your circuit. Your netlist should incorporate the following three .include statements .include "/mit/6.004/jsim/nominal.jsim" .include "/mit/6.004/jsim/stdcell.jsim" .include "/mit/6.004/jsim/lab3checkoff_6.jsim" and the following subcircuit definition (you can of course define other subcircuits as well) .subckt alu ALUFN[5:0] A[31:0] B[31:0] alu[31:0] z v n … your ALU circuit here … .ends Note that the z, v, and n signals from the adder/subtractor unit are included in the terminal list for the alu subcircuit. While these signals are not needed when using the ALU as part of the Beta, they are included here to make it easier for the test jig to pinpoint problems with your circuit. Before using lab3checkoff_6.jsim remember to comment out any test circuitry and .tran statements you may have added to your netlist while debugging your circuit. Also remember to use JSim’s gate-level simulator ( in the toolbar) to simulate your circuit. If this test jig runs okay, it will offer to check-in your lab with the on-line server. Optional Design Problem: Implementing Multiply The goal of this design project is build a combinational multiplier that accepts 32-bit operands and produces a 32-bit result. Multiplying two 32-bit numbers produces a 64-bit product; the result we’re looking for is the low-order 32-bits of the 64-bit product. Your multiplier circuitry should be integrated into the ALU design you completed in the first part of this lab. We’ll use the following encoding for ALUFN[5:0] when requesting a multiply operation by the ALU. Operation MUL ALUFN[5:0] 000010 hex 0x02 Here’s a detailed bit-level description of how a 4-bit by 4-bit unsigned multiplication works. This diagram assumes we only want the low-order 4 bits of the 8-bit product. A3 A2 A1 A0 * B3 B2 B1 B0 --------------------------A3*B0 A2*B0 A1*B0 A0*B0 + A2*B1 A1*B1 A0*B1 0 + A1*B2 A0*B2 0 0 + A0*B3 0 0 0 -------------------------P3 P2 P1 P0 6.004 Computation Structures - 10 - (multiplicand) (multiplier) (partial product) Lab #3 This diagram can be extended in a straightforward way to 32-bit by 32-bit multiplication. Note that since we only want the low-order 32-bits of the result, you don’t need to include the circuitry that generates the rest of the 64-bit product. As you can see from the diagram above, forming the partial products is easy! Multiplication of two bits can be implemented using an AND gate. The hard part is adding up all the partial products (there will be 32 partial products in your circuit). One can use full adders (FAs) hooked up in a ripple-carry configuration to add each partial product to the accumulated sum of the previous partial products (see the diagram below). The circuit closely follows the diagram above but omits an FA module if two of its inputs are “0”. The circuit above works with both unsigned operands and signed two’s complement operands. This may seem strange – don’t we have to worry about the most significant bit (MSB) of the operands? With unsigned operands the MSB has a weight of 2MSB (assuming the bits are numbered 0 to MSB) but with signed operands the MSB has a weight of –2MSB. Doesn’t our circuitry need to take that into account? 6.004 Computation Structures - 11 - Lab #3 It does, but when we’re only saving the lower half of the product, the differences don’t appear. The multiplicand (A in the figure above) can be either unsigned or two’s complement, the FA circuits will perform correctly in either case. When the multiplier (B in the figure above) is signed, we should subtract the final partial product instead of adding it. But subtraction is the same as adding the negative, and the negative of a two’s complement number can be computed by taking its complement and adding 1. When we work this through we see that the low-order bit of the partial product is the same whether positive or negated. And the low-order bit is all that we need when saving only the lower half of the product! If we were building a multiplier that computed the full product, we’d see many differences between a multiplier that handles unsigned operands and one that handles two’s complement operands, but these differences only affect how the high half of the product is computed. We’ve created a test jig to help debug your multiplier. Your netlist should incorporate the following three .include statements .include "/mit/6.004/jsim/nominal.jsim" .include "/mit/6.004/jsim/stdcell.jsim" .include "/mit/6.004/jsim/lab3multiply.jsim" and the standard alu subcircuit definition .subckt alu ALUFN[5:0] A[31:0] B[31:0] alu[31:0] z v n … your ALU with multiplier circuit here … .ends This test jig includes test cases for all combinations of (0, 1, -1)*(0,1,-1), 2i*1 for i = 0, 1, …, 31 -1*2i for i = 0, 1, …, 31 (3 i) * 3 for i = 0, 1, …, 31 When you’ve completed your design, you can use lab3checkoff_10.jsim to test your improved ALU implementation. This checkoff file contains all the tests from lab3checkoff_6.jsim plus additional tests to verify that your multiplier circuitry is working correctly. There’s also a handy set of debugging tests in lab3multiply.jsim which can help track down problems in your design. Design Note: Combinational multipliers implemented as described above are pretty slow! There are many design tricks we can use to speed things up – see the appendix on “Computer Arithmetic” in any of the editions of Computer Architecture A Quantitative Approach by John Hennessy and David Patterson (Morgan Kauffmann publishers). 6.004 Computation Structures - 12 - Lab #3