Overcoming_Data_Hazard_with_Dynamic_Scheduling docx

Overcoming Data Hazard with Dynamic

Scheduling

Designed by:

Trần Trung Trực 0912504

Lê Văn Vĩ 0912540

Hồ Thế Vũ 0912543

1

Simple statically scheduled Pipeline

 Fetches an instruction and issues it, if there was no data dependence or it can be hidden

by bypassing or forwarding.

 If there was a data dependence that cannot be

hidden by bypassing or forwarding:

 Hardware stalls the pipeline.

 No new instructions are fetched or issued until the dependence is cleared.

=>> In-order execution.

2

Dynamic Scheduling:

the hardware rearranges the instruction execution to reduce the stalls while maintaining data

flow and exception behavior.

Advantages:

Enables handling some cases when dependences are unknown at compile time (memory

reference…).

Simplifies the compiler.

Allows the processor to tolerate unpredictable delays such as cache misses.

Allows code that was compiled with one pipeline in mind to run efficiently on a different pipeline.

=>> costs a significant increase in hardware complexity.

3

Dynamic Scheduling: The Idea!

‰Extend the scope to extract parallelism:

div.d $F0, $F2, $F4

add.d $F10, $F0, $F8

sub.d $F12, $F8, $F14

‰Why not to execute sub.d while add.d waits for

the result of div.d?

‰Relax a fundamental rule: instructions can be

executed out of program order! (but the

result must still be correct…).

4

Out-of-Order Execution

essentially split the ID pipe stage of our simple five-stage pipeline into two stages:

1. Issue—Decode instructions, check for structural hazards.

2. Read operands—Wait until no data hazards, then read operands.

Instructions are issued from the register or queue.

The EX stage follows the read operands stage, just as in the five-stage pipeline. Execution may

take multiple cycles, depending on the operation.

5

In-order completion

6