Example RISC problems

Of course I could ask you simply to write some code, like the programming problems we've been doing in VELMA, as done in the last tutorial.

Here are some further possible kinds of problems.

1. The "delayed branch rule" on some RISC CPUs says that the instruction following a branch is executed even if the branch is taken. That is, in the instruction sequence

100	ADD R0, R1, R2
101	JUMP 110
102	ADD R3, R4, R5

, if we have the "delayed branch rule", then the instruction at location 102 is executed despite the jump (although the instructions at locations 103, 104, and so on, are not executed, of course). We call this extra-instruction location following the JUMP the "delayed branch slot".

To write programs for this situation we sometimes first write out the programs with NOP instructions (does nothing) in the delayed branch slot, then rearrange the steps to try to avoid wasting a cycle on the execution of the NOP.

For each of the following instruction sequences, either rearrange it to speed it up, or explain why it cannot be improved.

(a)

ADD R0, R1, R2
ADD R3, R3, R3
BEQ 110
NOP

(b)

ADD R0, R1, R2
JUMP 110
NOP

(c)

ADD R0, R1, R2
BEQ 110
NOP

2. The "delayed load rule" on some RISC CPUs says that the instruction immediately following a LOAD may not reference the target register of the LOAD operation (either as operand source or result destination). That is, in the instruction sequence

100	LOAD 500, R3
101	ADD R0, R1, R2
102	ADD R3, R4, R5

the instruction at location 102 may reference R3, but the instruction at location 101 may not. The following instruction sequences violate the delayed load rule. Rearrange them so as not to violate the delayed load rule. Try not to introduce NOP instructions if avoidable, but they might be unavoidable in some cases.

(a)

LOAD 500, R3
ADD R3, R3, R3
LOAD 502, R2
ADD R2, R2, R2

LOAD 500, R1
LOAD 502, R2
ADD R1, R2, R3

ADD R0, R1, R2
LOAD 500, R3
ADD R0, R2, R3