Draw the flow-dependence graph for these instructions

Assignment Help Other Subject

Reference no: EM131728592

1. Loop Unrolling

Consider the following loop:

loop: l.d f4,0(r1) l1

l.d f6,0(r2) l2

mul.d f4,f4,f0 m1

mul.d f6,f6,f2 m2

add.d f4,f4,f6 a1

s.d f4,0(r1) s1

daddui r1,r1,#-8 sub1

daddui r2,r2,#-8 sub2

bnez r1,loopbr

Note: Our default is that FP arithmetics have 4 x-boxes.

a) Using the names 'l1' to 's1' for the first six instructions in the loop body, draw the flow-dependence graph for these instructions.

Label each arrow with the dependence gap between the producer and the consumer.

In what follows, focus on three flow-dependence types: i) FP arith to FP arith, ii) FP arith to FP store, and iii) FP load to FP arith. Denote the number of m-boxes in memory references by '#m', and the number of x-boxes in FP arithmetics by '#x'.

b) For each of the three designated flow-dependence types, indicate the number of stalls in adjacent producer-consumer pairs as functions of '#m" and '#x'.

c) Suppose #m = 1 and #x = 4. How many stalls occur in one iteration of the loop if it is executed exactly as written?

d) Unroll the loop twice. If one reschedules the unrolled loop optimally, how many stalls are left? (Keep the branch as the last instruction. Show the rescheduled code using the _short_ names).

e) Increase the 'mul-add dependence gap' to 5 cycles, leaving everything else unchanged. Unroll the loop three times. If one reschedules the unrolled loop optimally, how many stalls are left? (Keep the branch as the last instruction. Show the rescheduled code using the _short_ names).

2. Dynamic Instruction Scheduling I
Imagine that reservation stations only track whether floating-point operands are valid, and that integer operands appear by magic whenever needed.

a) Dispatch instructions 'l1' to 's1' to reservation stations rs1(l1) to rs6(s1). Show the contents of each reservation station. Indicate both valid ("value") and pending ("ear") operands in each station. For the loads, you may make all operand entries 'blank'. That is, mark all load dependences as resolved. For the store, just invent a regular single-operand reservation station. The value of 'test' is either "may issue" or "may not issue". The value of 'free' is either "free" or "not free".

b) After both loads have completed, but no further action has occurred, show the contents of each reservation station. As before, you may mark some reservation stations as 'free'. Syntax: result[rs9(a9)]; val[f12].

c) At this point, dispatch the two loads of the second iteration, viz., 'l3' and 'l4', into reservation stations 'rs1' and 'rs2'. Moreover, let instruction 'm1' of the first iteration complete. Show the contents of each reservation station.

3. Dynamic Instruction Scheduling II

a) Instruction 'op' has been dispatched to reservation station alpha. What statement must be proved to show that all its flow dependences
are respected?

b) Instructions 'op1' and 'op2' are an antidependent pair. The earlier 'op1' is dispatched to reservation station alpha. The later 'op2' is dispatched to reservation station beta. What statement must be proved to show that the antidependence is respected?

c) Instructions 'op1' and 'op2' are an output-dependent pair. The earlier 'op1' is dispatched to reservation station alpha. The later 'op2' is dispatched to reservation station beta. What statement must be proved to show that the output dependence is respected?

Reference no: EM131728592

Questions Cloud

Create a gantt chart for this project using ms project : Establish predecessors and successors for tasks as appropriate. Create a GANTT chart for this project using MS Project.

Calculate the economic run size for hosuing : The annual holding cost for these motors is $1. Calculate the economic run size for this hosuing. Elctric Sheep operates 250 days per year.

What proportion of sample expected to favor candidate : Possible Sample Proportions Favoring a Candidate Suppose that of all voters in the United States, 40% are in favor of Candidate C for president.

What you think should be done to resolve the privacy issue : Why the issue exists; What is being done to address the issue, and what you think should be done to resolve the privacy issue.

Draw the flow-dependence graph for these instructions : COMP 326 - What statement must be proved to show that all its flow dependences are respected and What statement must be proved to show that the antidependence

Amount realized and the character by solar corporation : Determine the amount realized and the character by Solar Corporation on the sale of the following equipment

Define sampling distribution of a sample proportion : Suppose you want to estimate the proportion of students at your college who are left-handed. You decide to collect a random sample of 200 students.

Explain why the decision should be returned notwithstanding : Discussion: Stare Decisis. Provide a rationale for explain why the decision should be returned notwithstanding the doctrine of stare decisis.

Will big data put researchers out of business : Why has big-data analytics become so popular with companies like Kraft Foods, United Airlines, and Ford Motor Company?

User Account

All Pages