Name: _________________ NetId: _________________ CS433ug: Computer System Organization Quiz 1 Show all of your work. If you believe a problem is incorrectly or incompletely specified, make a reasonable assumption and solve the problem. The assumption should not result in a trivial solution. In all cases, clearly state any assumptions that you make in your answers. 1. [15 pts] Conditional Encoding a) [10 pts] Predication. Consider the following proposed format for predicated MIPS instructions: (pA) ADD R1, R2, R3 where the ADD instruction is predicated on the predicate register pA. Assume a set of 2 1-bit predicate registers (pA, pB) that are set by a compare instruction of the form: CMP.eq pA, pB, R8, R0 The above compare sets the 1-bit predicate registers as follows: pA = (R8 == R0) pB = (R8 != R0) Rewrite the following code into code that uses no branches and that has as few instructions as possible. Do NOT make any assumption about initial values of pA and pB. Both predicated version and unpredicated version of CMP.eq, LD, and ADD are available for your use. BNE nonzero R1, #0 ; if R1 != 0, jump to nonzero LD R2, R3; ADD R4, R2, R6 JMP done; nonzero: ADD R7, R8, R9; done: ADD R7, R4, R5; Solution: CMP.eq pA, pB, R1, #0 ; or CMP.eq pA, pB, R1, R0, assuming R0 = 0 (pA) LD R2, R3 (pA) ADD R4, R2, R6 (pB) ADD R7, R8, R9 ADD R7, R4, R5;b) [5pts] Give one significant advantage and disadvantage of predicated execution/instructions. Solution: Advantage: Predicated execution can reduce execution times by eliminating branches, which tend to be long-latency operations. Disadvantage: Operations whose predicates are not true, causing them not to be executed, must still be fetched from the instruction cache, and may take up space in the pipeline, depending on how predication is implemented. Any reasonable advantage and disadvantage will work. 2. [5 pts] Vector Encoding Dual register files can be used for vector operations. Having each instruction operate on both register files, we can implement vector instruction with regular instruction encoding. For example, with two register files X and Y that each has 8 registers, we can write regular instructions Rc = Ra OP Rb to achieve the functionality of both xRc = xRa OP xRb and yRc = yRa OP yRb. Here only 3 bits are needed to encode a register pair. Given 128 registers divided into 4 register files, how many bits are needed to encode each register 4-tuple in an instruction? Solution: 5 bits because 128/4 = 32 = 25 3. [10 pts] Condition Codes Suppose a machine has N, Z, V, and C condition code bits and that in a branching instruction, any Boolean expression over the N, Z, V, and C bits can be written using NOT, AND, and OR. For signed comparisons: A < B: (N ⊕V) = 1 A ≤B: ((N ⊕V) ∨Z) = 1 A > B: ((N ⊕V) ∨Z) = 0 A ≥B: (N ⊕V) = 0 The following is a code sequence. if (a == b) a = b+2; else a = a + b; Translate the above code sequence into assembly, using the condition code bits. Use as few instructions as possible. Assume a and b are signed integers.Solution: LOAD R1, A LOAD R2, B MOV R3, #2 ;; immediate 2 to R2 CMP R1, R2 ;; or SUB R4, R1, R2 BR Z L ;; tests for equality MOV R3, R2 L: ADD R1, R3 If a student thinks about equality correctly they should realize that the Z bit by itself is enough. 4. [10 pts] Addressing Modes: Load-Store: all ALU operations occur in registers and register-to-register instructions have 3 registers names per instruction. LOAD R1, A – loads the contents of memory location A into register R1. STORE A, R1 – stores the contents of register R1 into the memory location A. SUB R1, R2, R3 – subtracts the contents of register R3 from R2 and stores the result in register R1. Memory-memory: all instruction addresses reference only memory locations. SUB A, B, C – subtracts the contents of memory location C from B into the memory location A We have the following high-level code sequence: A = B - C; Assume the following: - The opcode is always 1 byte (8 bits) - All memory addresses are 2 bytes - All data operands are 4 bytes - All instructions are an integral number of bytes in length - For a load-store architecture, assume it has 16 general-purpose registers - A, B, and C are initially in memory. a) [2 pts] What is the number of instruction bytes fetched for the following instruction in Memory-memory ISA? ADD A, B, C Solution: 1 byte opcode + 2 bytes per memory address * 3 memory addresses = 7 bytesb) [8 pts] For each instruction set architecture, write the best equivalent assembly code sequence. You can only use the assembly language mnemonics given above. Use as few instructions as possible. Solution: Load-store: LOAD R2, B LOAD R3, C SUB R1, R2, R3 STORE A, R1 Memory-memory: SUB A, B,