Problem 1. Exploring Instruction Flow and and Instruction level parallelism: ILP Consider the following pseudo-assembly code. Top: A. LOAD R1 = Mem[1234] B. LOAD R2 = Mem[42] C. ADD R4=R1+R2 D. LOAD R3 = Mem[1976) E. BEQ R4,#0, Foo F. SUB R1 = R3 - #1 G. XOR R5 = RI Oxffff H. ADD RIERI +1 I. JUMP Bar Foo: J. LOAD R3 = Mem[2000] K. ADD R2 =R4 + #13 L. MUL R3 = R3 x R2 Bar: M. ADD R2 = R4 +R5 N. SUB R4 = R1 - #8 0. XOR R1 = R3 Oxf0f0f0f0 (a) Draw the Data-flow Graph observing all control dependencies and all register data dependencies (RAW, WAR and WAW) assuming the conditional branch (E) is not taken (falls through to F). What is the ILP? (b) Repeat, but only for true dependencies (no control dependencies) (c) Repeat, but only for true dependencies (no control dependencies) and assuming (E) is taken branches to HINT: The intention of the problem is not to use a specific pipeline. It is however, to identify different kinds of data dependences and the degree of ILP (Instruction Level Parallelism) achievable. Problems-Homework Assignment Normally you want do this graphically using a data flow graph. Where a node of the graph is one instruction (A, B, C, ...) and you have a directed edge from one node to the other if there is a dependence. You may want to use a different color for different dependence types. Once you have the graph, you can find out what would be the maximum parallelism you would obtain for that graph (computation) if you had all the hardware you needed. So then the depth of the data flow graph gives us the minimum execution time possible for the graph. The total number of instructions in the graph will give up the execution time with out any extra hardware. This means everything must be executed sequentially and one at a time. Then ILP is defined as = (Number of instructions in dataflow graph)/(depth of dataflow graph) Problem 1. Exploring Instruction Flow and and Instruction level parallelism: ILP Consider the following pseudo-assembly code. Top: A. LOAD R1 = Mem[1234] B. LOAD R2 = Mem[42] C. ADD R4=R1+R2 D. LOAD R3 = Mem[1976) E. BEQ R4,#0, Foo F. SUB R1 = R3 - #1 G. XOR R5 = RI Oxffff H. ADD RIERI +1 I. JUMP Bar Foo: J. LOAD R3 = Mem[2000] K. ADD R2 =R4 + #13 L. MUL R3 = R3 x R2 Bar: M. ADD R2 = R4 +R5 N. SUB R4 = R1 - #8 0. XOR R1 = R3 Oxf0f0f0f0 (a) Draw the Data-flow Graph observing all control dependencies and all register data dependencies (RAW, WAR and WAW) assuming the conditional branch (E) is not taken (falls through to F). What is the ILP? (b) Repeat, but only for true dependencies (no control dependencies) (c) Repeat, but only for true dependencies (no control dependencies) and assuming (E) is taken branches to HINT: The intention of the problem is not to use a specific pipeline. It is however, to identify different kinds of data dependences and the degree of ILP (Instruction Level Parallelism) achievable. Problems-Homework Assignment Normally you want do this graphically using a data flow graph. Where a node of the graph is one instruction (A, B, C, ...) and you have a directed edge from one node to the other if there is a dependence. You may want to use a different color for different dependence types. Once you have the graph, you can find out what would be the maximum parallelism you would obtain for that graph (computation) if you had all the hardware you needed. So then the depth of the data flow graph gives us the minimum execution time possible for the graph. The total number of instructions in the graph will give up the execution time with out any extra hardware. This means everything must be executed sequentially and one at a time. Then ILP is defined as = (Number of instructions in dataflow graph)/(depth of dataflow graph)