About a RISC problem , Compic Help~

[zc0000]

This question comes from CS SUB Practice Book:

 

17. A certain pipelined RISC machine has 8 general-purpose registers R0, R1, . . . , R7 and supports the following operations.

 

ADD Rs1, Rs2, Rd Add Rs1 to Rs2 and put the sum in Rd

MUL Rs1, Rs2, Rd Multiply Rs1 by Rs2 and put the product in Rd

 

 

An operation normally takes one cycle; however, an operation takes two cycles if it produces a result required by the immediately following operation in an operation sequence. Consider the expression AB+ ABC+ BC,

where variables A, B, C are located in registers R0, R1, R2. If the contents of these three registers must not be modified, what is the minimum number of clock cycles required for an operation sequence that computes the

value of AB+ ABC+ BC ?

 

(A) 5 (B) 6 © 7 (D) 8 (E) 9

 

 

The answer is B , how to get it?

[GRE_Fighter]

1> MUL R0,R1,R3 ; calculate AB

2> MUL R1,R2,R4 ; calculate BC

3> MUL R3,R2,R5 ; compute ABC ( = AB * C)

4> ADD R3,R4,R6 ; compute AB + BC

5> One Cycle Delay ; Result produced( R6 = AB +BC ) will be used in the following operation

6> ADD R6,R5,R7 ; compute ABC + (AB+BC)

 

There's probably one other way to get it done within 6 cycles.

The single-cycle delay here is caused by "pipeline stall" which stems from the data-dependency inherent in such programs.

 

A more formal approach to find out the least number of cycles would be to form a "Dependency graph" of subexpressions or a DAG (Directed acyclic graph) and then running a Topological Sort to get the "order-of-evaluation". After that, you can shuffle instructions to remove "data hazards" ( i.e. one of the operands come from the result produced in immediately preceding instruction) as long as shuffling doesn't hamper the "Evaluation Order" obtained.

 

However, for such short problems it is better to use common-sense and try several possible derivations to deduce the least number of cycles, especially when time matters the most.