Answers to tutorial exercises #2: Some basics of machine organization QUESTION 1 Design a circuit for a decoder. A decoder takes n bits of input and generates 2^n bits of output. The output bits are numbered 0 to (2^n)-1. Output bit k should be one if the input bits equal k in binary; otherwise, it should be zero. Design the circuit for n=2. Write down the circuit design as a set of boolean equations. Call the input bits i0 and i1 with i0 being the more significant, and call the output bits o0, o1, o2 and o3. ANSWER The truth table we want is as follows. i0 i1 | o0 o1 o2 o3 ------------------------ 0 0 | 1 0 0 0 0 1 | 0 1 0 0 1 0 | 0 0 1 0 1 1 | 0 0 0 1 The equations for the row signals are row0 = not i0 and not i1 row1 = not i0 and i1 row2 = i0 and not i1 row3 = i0 and i1 In this case, each output signal has a 1 in only one row, so the equations for the output signals are o0 = row0 = not i0 and not i1 o1 = row1 = not i0 and i1 o2 = row2 = i0 and not i1 o3 = row3 = i0 and i1 QUESTION 2 Design a multiplexer circuit. A multiplexer takes n bits of control input bits and 2^n bits of data input bits, and generates a single output data bit. The output is a copy of one of the data input bits; the binary value of the control input bits selects which one. First, design the circuit for n=2 using boolean equations using the usual boolean gates: AND, OR and NOT. Then see whether you can make the circuit smaller by using tristate gates. A tristate gate has a control input and a data input, and a data output. If the control input is one, the gate connects the data input and the data output; if the data input is one, so is the data output, and if the data input is zero, so is the data output. However, if the control input is zero, then the data input and the data output are NOT CONNECTED, so the value of the output bit will have to be computed by another circuit. You can write down a tristate gate as "connect signal1 to signal2 if signal3". ANSWER Call the control input bits c0 and c1 with c0 being the more significant, call the input bits i0, i1, i2 and i3, and call the output bit o. The truth table is quite big. With 6 inputs, it has 2^6 = 64 rows. c0 c1 i0 i1 i2 i3 | o --------------------- 0 0 0 0 0 0 | 0 c0 c1 = 0 0 0 0 0 0 0 1 | 0 0 0 0 0 1 0 | 0 0 0 0 0 1 1 | 0 0 0 0 1 0 0 | 0 0 0 0 1 0 1 | 0 0 0 0 1 1 0 | 0 0 0 0 1 1 1 | 0 0 0 1 0 0 0 | 1 0 0 1 0 0 1 | 1 0 0 1 0 1 0 | 1 0 0 1 0 1 1 | 1 0 0 1 1 0 0 | 1 0 0 1 1 0 1 | 1 0 0 1 1 1 0 | 1 0 0 1 1 1 1 | 1 0 1 0 0 0 0 | 0 c0 c1 = 0 1 0 1 0 0 0 1 | 0 0 1 0 0 1 0 | 0 0 1 0 0 1 1 | 0 0 1 0 1 0 0 | 1 0 1 0 1 0 1 | 1 0 1 0 1 1 0 | 1 0 1 0 1 1 1 | 1 0 1 1 0 0 0 | 0 0 1 1 0 0 1 | 0 0 1 1 0 1 0 | 0 0 1 1 0 1 1 | 0 0 1 1 1 0 0 | 1 0 1 1 1 0 1 | 1 0 1 1 1 1 0 | 1 0 1 1 1 1 1 | 1 1 0 0 0 0 0 | 0 c0 c1 = 1 0 1 0 0 0 0 1 | 0 1 0 0 0 1 0 | 1 1 0 0 0 1 1 | 1 1 0 0 1 0 0 | 0 1 0 0 1 0 1 | 0 1 0 0 1 1 0 | 1 1 0 0 1 1 1 | 1 1 0 1 0 0 0 | 0 1 0 1 0 0 1 | 0 1 0 1 0 1 0 | 1 1 0 1 0 1 1 | 1 1 0 1 1 0 0 | 0 1 0 1 1 0 1 | 0 1 0 1 1 1 0 | 1 1 0 1 1 1 1 | 1 1 1 0 0 0 0 | 0 c0 c1 = 1 1 1 1 0 0 0 1 | 1 1 1 0 0 1 0 | 0 1 1 0 0 1 1 | 1 1 1 0 1 0 0 | 0 1 1 0 1 0 1 | 1 1 1 0 1 1 0 | 0 1 1 0 1 1 1 | 1 1 1 1 0 0 0 | 0 1 1 1 0 0 1 | 1 1 1 1 0 1 0 | 0 1 1 1 0 1 1 | 1 1 1 1 1 0 0 | 0 1 1 1 1 0 1 | 1 1 1 1 1 1 0 | 0 1 1 1 1 1 1 | 1 Since there are 64 rows, there are 64 row signals. However, since the only output signal is 1 only in 32 rows, we need to OR together only those 32 row signals, and we don't need the other 32. The first 8 of those row signals are row8 = not c0 and not c1 and i0 and not i1 and not i2 and not i3 row9 = not c0 and not c1 and i0 and not i1 and not i2 and i3 row10 = not c0 and not c1 and i0 and not i1 and i2 and not i3 row11 = not c0 and not c1 and i0 and not i1 and i2 and i3 row12 = not c0 and not c1 and i0 and i1 and not i2 and not i3 row13 = not c0 and not c1 and i0 and i1 and not i2 and i3 row14 = not c0 and not c1 and i0 and i1 and i2 and not i3 row15 = not c0 and not c1 and i0 and i1 and i2 and i3 Basically, since these eight signals together describe all the possible combinations of the values of the i1, i2 and i3 bits, ORing these signals together yields rowsA = not c0 and not c1 and i0 This is the signal for when the output signal is 1 when the two control signals are 0 and 0. If you do the same for the other three combinations of the two control signals, you get three other signals rowsB = not c0 and c1 and i1 rowsC = c0 and not c1 and i2 rowsD = c0 and c1 and i3 The signal for the output bit is then o = rowsA or rowsB or rowsC or rowsD If we can use tristate gates, we need to decide under what circumstances each input bit should be connected to the output bit. Each circumstance is described by one particular combination of the input bits: decode00 = row0 = not c0 and not c1 decode01 = row1 = not c0 and c1 decode10 = row2 = c0 and not c1 decode11 = row3 = c0 and c1 These are the same circuits as in the previous question; the names of the signals have changed, but the structures of the circuits have not. The multiplexer consists of these circuits, and these four tristate gates: connect i0 to o if decode00 connect i1 to o if decode01 connect i2 to o if decode10 connect i3 to o if decode11 For any combination of the c0 and c1 inputs, exactly one of the decode signals will be 1. This means that the output signal o is always defined, and therefore meaningful. It also means that you never connect *more* than one input signals to the output signal. This is good, since connecting both e.g. i0 and i1 to o would also connect i0 and i1 to each other. If they happened to have different values, that would mean that one was connected to ground (0 volts) and the other was connected to the power supply (which is typically around 2 volts), and any connection between them would be a short circuit that can melt the chip or (if sustained) even cause it to burst into flames. One potential complication in real life that does not show up in these equations is that the circuits that compute decode00, decode01 and so on may not take the exact same time to do their jobs. Therefore there may be short time intervals when e.g. both decode00 and decode01 are true. Electronic engineers have techniques for ensuring that this does not cause problems, but those techniques are way outside the scope of this subject. QUESTION 3 How many different ISAs have you heard of? How many of these ISAs were actually implemented by computers you have used? ANSWER People should have heard of at least two: the x86 (general knowledge), and MIPS (from lectures). However, there are many more. Here are just a few: Motorola 680x0 (original Mac) IBM PowerPC (late 1990s Mac) ARM (many mobile phones) IBM System/360 (IBM mainframes) Sun SPARC (many web servers) QUESTION 4 How do you think the CPU increments the value in the PC register to point to the next instruction? ANSWER Put the value of the PC on the SRC1 bus, and put the constant value 4 on the SRC2 bus. The ALU will read these values from the source buses near the start of a clock cycle; it will wait just long enough to be sure that all the bits from the ultimate sources have reached the ALU. The control unit then selects the ALU's addition circuit, which does its job through the bulk of the clock cycle. Near the end of the clock cycle, when the addition circuit's result is guaranteed to be available, the control unit tells the PC register to throw out its current contents and to replace it with the value now on the DEST bus. QUESTION 5 How do you think constants that don't fit into 16-bit immediates should be loaded into registers in MIPS programs? ANSWER The MIPS instruction set has an instruction, lui (load upper immediate), that loads the 16 bit immediate into the upper 16 bits of the target register, and sets the lower 16 bits of that register to zero. A second ori (OR immediate) instruction can then OR the desired 16 bits into that register. For example, to load the binary value 0000 0000 0000 0101 0000 0000 0000 0110 into register $s0, you can use the two instructions lui $s0, 5 ori $s0, $s0, 6 If you did not have the lui instruction, you could achieve its effect by loading the bits intended for the upper 16 bits into the *lower* 16 bits, and then shifting them 16 bits left: ori $s0, $zero, 5 sll $s0, $s0, 16 ori $s0, $s0, 6