Example RISC problems

These problems are presented here not to specify the kind of question I might ask on the exam, but to clarify what sorts of things I expect you to know; and what sorts of things I expect you to be familiar with; as opposed to the sorts of things I would feel that I ought to give you an explanation of or reminder of.

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
100ADD R0, R1, R2
101JUMP 110
102ADD 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
100LOAD 500, R3
101ADD R0, R1, R2
102ADD 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
(b)
LOAD 500, R1
LOAD 502, R2
ADD R1, R2, R3
(c)
ADD R0, R1, R2
LOAD 500, R3
ADD R0, R2, R3
Answers to both the above questions


[CSC 258 additional problems] [main course page]