计算系统概论ics第五章习题

Homework4

T1

List five addressing modes. Given instructions ADD, JMP, LEA,LDR and NOT, identify whether the instructions are operate instructions, data movement instructions, or control instructions. For each instruction, list the addressing modes that can be used with the instruction.

T2

Say we have a memory consisting of 256 locations, and each location contains 16 bits.

a. How many bits are required for the address?

$256=2^8$，至少需要$8bits$

b.If we use the PC-relative addressing mode, and want to allow control transfer between instructions 20 locations away, how many bits of a branch instruction are needed to specify the PC-relative offset?

$6bit$的补码表示范围为$[-32,31]$，所以要表示$\ge 20$的范围需要$6bits$。

c.If a control instruction is in location 3, what is the PC-relative offset of address 10? Assume that the control transfer instructions work the same way as in the LC-3.

$\text{3+1+PCoffset=10}$，偏移值为$6$。

T3

Recall the machine busy example from Section 2.6.7. Assuming the BUSYNESS bit vector is stored in R2, we can use the LC-3 instruction 0101 011 010 1 00001 (AND R3, R2, #1) to determine whether machine 0 is busy or not. If the result of this instruction is 0, then machine 0 is busy.

a. Write an LC-3 instruction that determines whether machine 2 is busy.

$\text{0101 011 010 1 00100 (AND R3, R2, \#4)}$

b. Write an LC-3 instruction that determines whether both machines 2 and 3 are busy.

$\text{0101 011 010 1 01100 (AND R3, R2, \#12)}$

c. Write an LC-3 instruction that indicates none of the machines are busy.

$\text{1001 011 010 1 11111 (NOT R3,R2)}$

d. Can you write an LC-3 instruction that determines whether machine 6 is busy? Is there a problem here?

不能，我们需要对$\text{ 0000 0000 0100 0000 }$执行$AND$操作，而立即数只有$5$位。

T4

We would like to have an instruction that does nothing. Many ISAs actually have an opcode devoted to doing nothing. It is usually called NOP, for NO OPERATION. The instruction is fetched, decoded, and executed. The execution phase is to do nothing! Which of the following three instructions could be used for NOP and have the program still work correctly?

a. 0001 001 001 1 00000

$\text{(ADD R1,R1,\#0)}$，不能用作$NOP$，因为$ADD$指令会执行$setcc();$

b. 0000 111 000000001

$BR$指令，$n,z,p$均为$1$，会跳转至$PC$增量与$PCoffset$字段的符号扩展之和的地址处。

c. 0000 000 000000000

可以用作$NOP$，$n,z,p$均为零，$PC$内容不变，在下一个指令周期，将顺序地读取下一条指令。

What does the ADD instruction do that the others do not do?

$ADD$指令存在取操作数操作以及存数操作。

T5

a. How might one use a single LC-3 instruction to move the value in R2 into R3?

$\text{0001 011 010 1 00000 (ADD R3, R2, \#0)}$

b. The LC-3 has no subtract instruction. How could one perform the following operation using only three LC-3 instructions: R1 ← R2 − R3
$$\begin{gathered} \text{1001 0011 0011 1 11111 (NOT R3,R3)} \\ \text{0001 011 011 1 00001 (ADD R3,R3,\#1)} \\ \text{0001 001 010 0 00 011 (ADD R1,R2,R3)} \end{gathered}$$
c. Using only one LC-3 instruction and without changing the contents of any register, how might one set the condition codes based on the value that resides in R1?

$\text{0001 001 001 1 00000 (ADD R1,R1,\#0)}$

d. Is there a sequence of LC-3 instructions that will cause the condition codes at the end of the sequence to be N = 1, Z = 1, and P = 0? Explain.

$n=1,z=1$说明即是负数又是零，但不存在这样的数，所以不可能。

e. Write an LC-3 instruction that clears the contents of R2.

$\text{0101 010 010 1 00000 (AND R2,R2,\#0)}$

T6

The LC-3 does not have an opcode for the logical function XOR. That is, there is no instruction in the LC-3 ISA that performs the XOR operation. However, we can write a sequence of instructions to implement the XOR operation.

Assume that the reserved instruction 1101 is OR instruction，its addressing mode is the same as AND.

The following five-instruction sequence performs the XOR of the contents of register 1 and register 2 and puts the result in register 3.

Fill in the two missing instructions so that the five-instruction sequence will do the job.

(1): 1001 100 001 111111

(2): $\text{0101 100 100 0 00 010 (AND R4,R4,R2)}$

(3): 1001 101 010 111111

(4): $\text{0101 101 101 0 00 001 (AND R5,R5,R1)}$

(5): 1101 011 100 000 101

T7

State the contents of R1, R2, R3, and R4 after the program starting at location x3100 halts.

$$\begin{gathered} \text{1110 001 000100000 ( LEA R1, 0x20 ) R1 ← 0x3121} \\ \text{0010 010 000100000 ( LD R2, 0x20 ) R2 ← mem[0x3122] = 0x4566} \\ \text{1010 011 000100001 ( LDI R3, 0x20 ) R3 ← mem[mem[0x3123]] = 0xabcd} \\ \text{0110 100 010 000001 ( LDR R4, R2, 0x1 ) R4 ← mem[R2 + 0x1] = 0xabcd} \\ \text{1111 0000 0010 0101 ( TRAP 0x25 )} \end{gathered}$$

T8

How many times does the LC-3 make a read or write request to memory during the processing of the LD instruction?

两次：一次取指令，一次取操作数，没有execute​节拍

How many times during the processing of the LDI instruction?

三次：一次取指令，一次取数据地址，一次取操作数，不需要execute节拍

How many times during the processing of the LEA instruction?

一次：一次取指令操作，不需要evluate address、execute节拍

Also indicate what phases the instructions don’t need. Processing includes all phases of the instruction cycle.

T9

Suppose the following LC-3 program is loaded into memory starting at location x30FF:

x30FF 1110 001 000000001 👉 $\text{(LEA R1 x0001) R1←x3101}$

x3100 0110 010 001 000010 👉 $\text{(LDR R2 R1 ,\#2) R2←mem[R1+2]}$

x3101 1111 0000 0010 0101 👉$\text{(TRAP x0025)}$

x3102 0001 010 001 0 00 001

x3103 0001 010 010 0 00 010

If the program is executed, what is the value in R2 at the end of execution?

$\text{0001 0100 1000 0010 = x1482}$

T10

If the value stored in R0 is 5 at the end of the execution of the following instructions, what can be inferred about R5?

x2FFF 0101 000 000 1 00000 AND $R0\leftarrow 0$
x3000 0101 111 111 1 00000 AND $R7\leftarrow 0$
x3001 0001 110 111 1 00001 ADD $R6\leftarrow R7+1$
x3002 0101 100 101 0 00 110 AND $R4\leftarrow R5andR6$
x3003 0000 010 000000001 BR $BRzx3005$
x3004 0001 000 000 1 00001 ADD $R0\leftarrow R0+1$
x3005 0001 110 110 0 00 110 ADD $R6\leftarrow R6+R6$
x3006 0001 111 111 1 00001 ADD $R7\leftarrow R7+1$
x3007 0001 001 111 1 11000 ADD $R1\leftarrow R7-8$
x3008 0000 100 111111001 BR $BRnx3009-x0007=x3002$
x3009 0101 111 111 1 00000 AND $R7\leftarrow 0$

只有当$R4$为$0$的时候，才会执行$BRzx3005$，此时会跳过$R0\leftarrow R0+1$，要让$R0$增量至$5$，$R4\leftarrow R5andR6$的结果至少有$5$次结果不为$0$，即执行$5$次$R0\leftarrow R0+1$，当$R1\leftarrow R7-8$置状态$\ge 0$时程序会执行至结束，$R6：1\to 10\to \dots \to 10000000$，与$R5$做共$8$次与运算，其中$5$次运算结果不为$0$，所以可推出$R5$低$8$位中有$5$位为$1$。

T11

The LC-3 macho-company has decided to use opcode 1101 to implement a new instruction. They need your help to pick the most useful one from the following:

a. MOVE Ri, Rj; The contents of Rj are copied into Ri.

b. NAND Ri, Rj, Rk; Ri is the bit-wise NAND of Rj, Rk

c. SHFL Ri, Rj, #2; The contents of Rj are shifted left 2 bits and stored into Ri.

d. MUL Ri, Rj, Rk; Ri is the product of 2’s complement integers in Rj, Rk.

Justify your answer.

$a,b,c$可以分别由以下指令代替，所以$MUL$是其中最有意义的。

a.$ADDRi,Rj,\#0$

b.$ANDRi,Rj,Rk;NOTRi,Ri$

c.$MULRi,Rj,\#4$

T12

The following diagram describes a 22 by 16-bit memory. Each of the four muxes has four-bit input sources and a four-bit output, and each four-bit source is the output of a single four-bit memory cell.

a. Unfortunately, the memory was wired by a student, and he got the inputs to some of the muxes mixed up. That is, instead of the four bits from a memory cell going to the correct four-bit input of the mux, the four bits all went to one of the other four-bit sources of that mux. The result was, as you can imagine, a mess. To figure out the mix-up in the wiring, the following sequence of memory accesses was performed:

Note: On a write, MDR is loaded before the access. On a read, MDR is loaded as a result of the access. Your job is to identify the mix-up in the wiring. Show which memory cells were wired to which mux inputs by filling in their corresponding addresses in the blanks provided. Note that one address has already been supplied for you.

对于第二个MUX，因为从$MAR=01$读出$C$，但是向$MAR=10$写入$C$，所以可知第二个MUX的$01$位置实际接的是$10$，其余依此类推

b. After rewiring the muxes correctly and initializing all memory cells to xF, the following sequence of accesses was performed. Note that some of the information about each access has been left out. Your job:

Fill in the blanks.

Show the contents of the memory cells by putting the hex digit that is stored in each after all the accesses have been performed.