Test on Computer Organization and Design. 15 MCQs and 7 short answer questions. The deadline is strict and cannot be extended.
Computer Organization and Design test If you need to work anything out on paper, such as datapath or state diagrams, please take a picture of it and insert it in the Word document at the proper position Part I. Multiple choice questions Please write down one answer for each question in the following table. 2 points for each question. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 The 2’s complement representation of -37ten in 8 bits is (a) 1101 1010 (b) 1101 1011 (c) 1110 1101 (d) None of the above. The single precision floating point representation of 17.125ten in hexadecimal is (a) 0x41890000 (b) 0x40890000 (c) 0x41120000 (d) None of the above. Consider a MIPS function F1 that calls another function F2 in the inner loop of a nested loop with two levels. Which of the following statements is true? (a) F1 must save at least 3 values on the stack. (b) F1 must save $ra on the stack. (c) Both of the above. (d) None of the above. Which of the following statements about the following code segment is true? li.s $f0, 5.0 li.s $f1, 7.0 c.lt.s $f0, $f1 bc1t p4L1 p4L0:add.s $f0, $f0, $f1 p4L1: bc1t p4L0 p4L2: (a) The program will execute the instruction at p4L1. (b) The program will never get to p4L2. (c) Both of the above. (d) None of the above. Consider the MIPS ALU we designed. Which of the following statements is true? It performs addition when the instruction is lw It performs subtraction when the instruction is jal Both of the above None of the above Consider the datapath of the single cycle MIPS processor that supports R-type, lw, sw, and beq shown in the following figure: If only beq and lw are needed, how many 2-1 MUXes can be removed from the datapath? (a) 1. (b) 2. (c) 3. (d) None of the above. Consider the same datapath shown in Problem 6. Suppose $t0 is 10, $t1 is 20, when the following instruction is executed: sw $t0, 8($t1) Suppose the control signal for a 2-1 MUX is 0 if we do not care about its value. What will be the stable values at ReadData1 and WriteData ports of the register file during the execution of this instruction? (a) 20 and 28 (b) 10 and 18 (c) 10 and 20 (d) None of the above. Consider the same datapath shown in Problem 6. If we want to support a new instruction swp rs, rt, which swaps the values in registers rs and rt, which of the following statements is true? The current datapath can already support swp, we just need to generate new control signals. The current datapath cannot support swp, but can support it after adding some 2-1 MUXes. The current datapath cannot support swp, Adding more 2-1 MUXes will not help either. None of the above Suppose we build a single cycle datapath that supports the jal instruction and R-type instruction. Which of the following statements about the datapath is true? It also supports j It also supports jr Both of the above None of the above Pipeline speeds up the processor compared to the single-cycle design because Multiple instructions are executed at the same time Each stage is made faster by using the pipeline register Both of the above None of the above Which of the following statements about MIPS pipeline is true? If a lw instruction is followed immediately by an R-type instruction, a stall always occurs A beq instruction always stalls the pipeline Both of the above None of the above Pipeline can be sped up by forwarding because The ALU computes faster with the forwarded data The data can be available to the ALU sooner Both of the above None of the above Consider the following code segment to be executed on the pipeline processor shown below: lw $t0, 0($t1) sw $t0, 0($t2) add $s0, $s0, $s1 It is possible to speed up the execution by rearranging the order of the instructions It is possible to speed up the execution by exploiting the existing forwarding paths (compared with no forwarding). Both of the above None of the above Which of the following statements about memory hierarchy and cache is true? The fully associative scheme is only practical for caches with a small number of entries. Level 1 is faster than Level 2, but smaller. Both of the above None of the above Which of the following statements about virtual memory is true? Translation lookaside buffer may help reduce memory access time Write-through is not preferred, because writing the disk takes too long Both of the above None of the above Part II. Short answer questions Problem 1 (20 points). Please complete the code segments by writing exactly one instruction in each box. In some boxes, part of the instruction has been given, which can be used as a hint. (4 points) If $t0 >= $t1, add $t0 with $t1; otherwise, do nothing. bgt sa1a_L1: # the instruction after this segment (6 points) The following code is supposed to find the location of the first 1 in $s0 and store it in $t0. For example, if $s0 is holding 12, which is 00001100 in 8 bits, $t0 should be 3. Note that you will not need to preserve the value in $s0 and $t1. li $t0, 0 sa1b_LOOP:andi $t1, addi $t0, $t0, 1 srl beq (10 points) The following code is supposed to reverse the order of a non-empty word array. The starting address of the array is in $a0 the number of elements is in $a1. ori $t0, $a0, 0 sll $t1, $a1, 2 add $t1, $t1, $a0 addi $t1, $t1, -4 sa1c_LOOP: lw $t8, 0($t0) lw $t9, 0($t1) sw $t8, sw $t9, addi $t0, addi $t1, Problem 2 (6 points) Please and use the Karnaugh map to find the logic function for Y. Please use the following symbols in the logic function: or + Example: A or B is written as A + B and nothing Example: A and B is written as AB not ‘ Example: not A is written as A’ X2 X1 X0 Y 0 0 0 1 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 0 1 1 1 1 ’ Problem 3 (7 points) Suppose we need to design a circuit that has two inputs, clk and X, and produces one output bit Y. X may change every clock cycle, where the change happens at the falling edge of the clock. The circuit samples X at every rising edge of the clock. Y should be 1 if the last 6 bits of X are “001101” from the least recent to the most recent. Please write down the names of the states as S0, S1, … , and so on, and clearly describe the meanings of each state. Please draw the state transition diagram of this circuit. Close to an arc, show X=0 or X=1. Problem 4 (6 points) Consider the implementation of a finite state machine with 2 D flip-flops according to the following logic functions: D1 = Q1 ^ Q0 // Q1 exclusive or with Q0 D0 = Q1’ // not Q1 (4 points) Please fill the following current state to next state table: Q1 Q0 D1 D0 0 0 0 1 1 0 1 1 (2 points) Please write down the sequence of numbers generated by this finite state machine, where, for example, if Q1 and Q0 are 1 and 0, respectively, the number is 2. Assume initially, Q1 and Q0 are both 0. It will be a repeating pattern and please write down the first two complete cycles followed by an ellipsis. Problem 5 (6 points) Consider the following single cycle data path. Please determine whether or not it supports the following instructions by marking [Y] or [N]: add --- [ ] lw --- [ ] sw --- [ ] beq --- [ ] addi --- [ ] jr --- [ ] Problem 6 (15 points) Please design a single cycle MIPS processor that supports only the sw and the AAA rs, rt, rd instructions. The AAA rs, rt, rd is an R-type instruction that does the following: PC will be rs + rt rd will be the memory value at address rt if rs is non-negative Assume the opcode of addi is 000000, and the opcode of AAA is 100000. We use ins31 and rs31 to refer to bit 31 of the instruction and rs, respectively. (9 points) Please design the datapath, add 2-1 MUX when necessary. Please show clearly the indices of the bits near the wires. Please number the 2-1 MUXes starting from 1. (4 points) Please determine the values of the control signals, including the selection signal of the 2-1 MUXes, as well as RegWrite, by filling in the table. In case of “don’t care”, please write down “X.” Assume other control signals have been generated correctly. (2 points) Please write down the logic functions of the control signals. In case of “don’t care,” assume the control signal should be 0. ins31 rs31 RegWrite MuxCtrl1 MuxCtrl2 MuxCtrl3 0 0 0 1 1 0 1 1 RegWrite = MuxCtrl1 = MuxCtrl2 = MuxCtrl3 = Problem 7 (10 points) Consider the following instructions: lw $t0, 0($t0) beq