Name: 1CSE 240 Autumn 2005DUE: Mon. 10 October 2005Intro. to Computer Architecture Homework 4Write your answers on these pages. Additional pages may be attached (with staple) if necessary. Please ensure thatyour answers are legible. Please show your work. Due at the beginning of class. Total points: 80.1. [6 Points] Instruction Encoding. Suppose a machine encodes instructions in 32 bits according to the followingformat. Also, suppose the encoding must accommodate 164 opcodes and 50 registers.OPCODE SR DR IMM(a) What is the minimum number of bits required to represent the OPCODE field?(b) What is the minimum number of bits required to represent each of the register fields (e.g., DR)?(c) What is the greatest number of bits that are left for the IMM field? If the IMM field encodes a 2’s comple-ment integer, what range of values can be represented with these bits?22. [8 Points] Instruction Processing. The PC, IR, MAR, MDR, and RF (register file) are structures written (andread) in various phases of the instruction processing cycle, depending on the instruction being executed. Ineach table cell, below, enter the instructions that result in writes to the corresponding structure (row) during thecorresponding phase (column) of the instruction processing cycle. For example, place LDR in the PC row of theFETCH column if LDR causes the PC to be written during the FETCH phase. To make this simpler, let’s onlyconsider the following instructions: ADD, LDR, LEA, ST, and TRAP. The textbook doesn’t directly answer thisquestion (i.e., you can’t just “look it up”), so your answers will need to be based on your understanding of whatshould happen in each execution phase.FETCH DECODE EVAL ADDR FETCH OPERANDS EXECUTE STOREPCIRMARMDRRF3. [20 Points] LC-3 Instruction Encoding. For these questions assume the LC-3 instruction encoding (summa-rized on the inside back cover of your textbook). You may also find Appendix A helpful.(a) What is the range of values (in decimal) that may be specified by the immediate field of an ADD instruc-tion?(b) Give the encoding of two LC-3 instructions that together decrement register R3 by 31 and place the resultback in R3. Complete the following table.Address 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 Instructionx3001x3002Name: 3(c) Different kinds of store instructions (e.g., ST, STI, and STR) are able to access different parts of theaddress space. For each kind of store instruction, below, give the possible range of addresses to whichthe instruction can store (assuming the instruction resides in memory at address x2345 and that the restof memory can contain any possible values). Express your answers as hexadecimal address ranges (e.g.,x100 to x200).i. STii. STIiii. STR (with BaseR=R1=xCEA3)4(d) Like store instructions, different kinds of control instructions are able to transfer control to different partsof the address space. For each of the following control instructions, give the possible range of values forthe next PC (assuming the instruction resides in memory at address x3456 and the registers have the valuesbelow). Express your answers as hexadecimal address ranges (e.g., x100 to x200).R0 R1 R2 R3 R4 R5 R6 R7x0 x1111 x2222 x3333 x4444 x5555 x6666 x7777i. BRnii. BRnzpiii. JMP(with BaseR=R3)iv. RETName: 54. [4 Points] Simple LC-3 Code. Consider the following LC-3 program. Register R1 serves as the input valuefor this code, and R2 holds the output value when the loop terminates. If R1 originally contains some positiveinteger, n, express the output, R2, in terms of n. Assume the values manipulated by this program are smallenough that overflow does not occur.Address Operation Operationx3001 0101 0100 1010 0000 R2 <- 0x3002 0001 0100 1010 0001 R2 <- R2+1x3003 0001 0100 1000 0010 R3 <- R2+R2x3004 0001 0100 1000 0011 R2 <- R2+R3x3005 0001 0010 0111 1111 R1 <- R1-1x3006 0000 0011 1111 1100 BRp x30035. [15 Points] LC-3 Code. Suppose you want to write a program consisting of instructions with the behaviordescribed by the operation in the final column of the following table.Address 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 Operationx3001 R2 <- M[R1+0]x3002R3 <- M[R1+1]x3003R4 <- NOT R3x3004 R4 <- R4 + 1x3005 R5 <- R2 + R4x3006BRzp x3009x3007M[R1+2] <- R3x3008 BRnzp x3010x3009 M[R1+2] <- R2(a) Give the binary encoding of each instruction in the table. Write your answers in the table, above.(b) Trace the execution of the above program, starting at x3001, by completing the following table. Give thePC and operation to execute in the first two columns, and give the state of the registers and condition codesafter the execution of that instruction (leave an entry blank if it is not changed by the instruction). Theinitial register state and the effect of the first instruction are given in the first two rows. Assume memorylocations x3100 and x3101 contain 14 and 27, respectively.6PC Operation R0 R1 R2 R3 R4 R5 R6 R7 CCsinitial register state ⇒ 0 x3100 0 3 4 5 6 7x3001 R2 <- M[R1+0] 14 P(c) In a sentence, what does this code compute?Name: 76. [15 Points] LC-3 Code. The following (bit-level) memory contents represent an LC-3 program.Address 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 Operationx3001 0 1 1 0 0 1 0 0 0 1 0 0 0 0 0 0 R2 <- M[R1+0]x3002 0 1 1 0 0 1 1 0 0 1 0 0 0 0 0 1x3003 1 0 0 1 0 1 1 0 1 1 1 1 1 1 1 1x30040 0 0 1 0 1 1 0 1 1 1 0 0 0 0 1x30050 0 0 1 0 1 0 0 1 0 0 0 0 0 1 1x3006 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0x3007 1 0 0 1 0 1 0 0 1 0 1 1 1 1 1 1x30080 0 0 1 0 1 0 0 1 0 1 0 0 0 0 1x3009 0 1 1 1 0 1 0 0 0 1 0 0 0 0 1 0(a) First, determine what each instruction does. Write this next to each instruction (above, in the final column)in a manner similar to that of the previous problem.(b) Next, trace the execution of the above program, starting at x3001, by completing the following table.Give the PC and operation to execute in the first two columns, and give the state of the registers andcondition codes after the execution of that instruction (leave an entry blank if it is not changed by theinstruction). The initial register state and the effect of the first instruction are given in the first two rows.Assume memory locations x3100 and x3101 contain -34 and -20, respectively.PC Operation R0 R1 R2 R3 R4 R5 R6 R7 CCsinitial register state ⇒ 0 x3100 2 3 4 5 6 7x3001 R2 <- M[R1+0] -34 N(c) In a sentence, what does this code do?87. [12 Points] LC-3 Implementation. Consider the LC-3 datapath, below, from lecture. We are going to buildthe control logic (i.e., part of the contents of