Computer Architecture and Implementation

Сентябрь 15, 2022

Главная
Алгебра
Computer Architecture and Implementation

Содержание

2. Instruction-Level Parallelism Relevant Book Reading (HP3): Dynamic Scheduling (in hardware): Appendix A & Chapter 3 Compiler
3. Hardware Schemes for ILP Why do it in hardware at run time? Works when can’t know
4. Dynamic Scheduling DIV.D F0, F2, F4 ADD.D F10, F0, F8 SUB.D F12, F8, F14 7-cycle divider
5. Explanation of I To be able to execute the SUB.D instruction A function unit must be
6. Out-of-order Execution and Renaming WAW hazard on register F10: prevents out-of-order execution on machine like CDC
7. Memory Consistency Memory consistency refers to the order of main memory accesses as compared to the
8. Four Possibilities for Load/Store Motion Load-Load LW R1, (R2) LW R3, (R4) Load-Load can always be
9. More on Load Bypassing and Forwarding Either transformation can be performed at compile time if the
10. Load Bypassing in Hardware Requires two separate queues for LOADs and STOREs Every LOAD has to
11. Example of Load Bypassing Memory access takes four cycles Actions at various points in time End
13. Скачать презентацию

Слайд 2

Instruction-Level Parallelism
Relevant Book Reading (HP3):
Dynamic Scheduling (in hardware): Appendix A

& Chapter 3
Compiler Scheduling (in software): Chapter 4

Слайд 3

Hardware Schemes for ILP
Why do it in hardware at run time?
Works

when can’t know dependences at compile time
Simpler compiler
Code for one machine runs well on another machine
Key idea: Allow instructions behind stall to proceed
DIV.D F0, F2, F4
ADD.D F10, F0, F8
SUB.D F8, F8, F14
Enables out-of-order execution
Implies out-of-order completion
ID stage check for both structural and data dependences

Слайд 4

Dynamic Scheduling
DIV.D F0, F2, F4
ADD.D F10, F0, F8
SUB.D F12, F8, F14
7-cycle divider
4-cycle adder
Instructions are

issued in order (leftmost I)
Execution can begin out of order (leftmost E)
Execution can terminate out of order (W)
What is I?

Слайд 5

Explanation of I
To be able to execute the SUB.D instruction
A function

unit must be available
Adder is free in example
There should be no data hazards preventing early execution
None in this example
We must be able to recognize the two previous conditions
Must examine several instructions before deciding on what to execute
I represents the instruction window (or issue window) in which this examination happens
If every instruction starts execution in order, then I is superfluous
Otherwise:
Instruction enter the issue window in order
Several instructions may be in issue window at any instant
Execution can begin out of order

Слайд 6

Out-of-order Execution and Renaming
WAW hazard on register F10: prevents out-of-order execution

on machine like CDC 6600
If processor was capable of register renaming:
the WAW hazard would be eliminated
SUB.D could execute early as before
example: IBM 360/91

DIV.D F0, F2, F4
ADD.D F10, F0, F8
SUB.D F10, F8, F14

Слайд 7

Memory Consistency
Memory consistency refers to the order of main memory accesses

as compared to the order seen in sequential (unpipelined) execution
Strong memory consistency: All memory accesses are made in strict program order
Weak memory consistency: Memory accesses may be made out of order, provided that no dependences are violated
Weak memory consistency is more desirable
leads to increased performance
In what follows, ignore register hazards
Q: When can two memory accesses be re-ordered?

Слайд 8

Four Possibilities for Load/Store Motion
Load-Load
LW R1, (R2)
LW R3, (R4)
Load-Load can always be interchanged

(if no volatiles)
Load-Store and Store-Store are never interchanged
Store-Load is the only promising program transformation
Load is done earlier than planned, which can only help
Store is done later than planned, which should cause no harm
Two variants of transformation
If load is independent of store, we have load bypassing
If load is dependent on store through memory (e.g., (R1) == (R4)), we have load forwarding

Load-Store
LW R1, (R2)
SW (R3), R4

Store-Store
SW R1, (R2)
SW R3, (R4)

Store-Load
SW (R1), R2
LW R3, (R4)

Слайд 9

More on Load Bypassing and Forwarding
Either transformation can be performed at

compile time if the memory addresses are known, or at run-time if the necessary hardware capabilities are available
Compiler performs load bypassing in loop unrolling example (next lecture)
In general, if compiler is not sure, it should not do the transformation
Hardware is never “not sure”

Слайд 10

Load Bypassing in Hardware
Requires two separate queues for LOADs and STOREs
Every

LOAD has to be checked for every STORE waiting in the store queue to determine whether there is a hazard on a memory location
assume that processor knows original program order of all these memory instructions
In general, LOAD has priority over STORE
For the selected LOAD instruction, if there exists a STORE instruction in the store queue such that …
LOAD is behind STORE (in program order), and
their memory addresses are the same
… then the LOAD cannot be sent to memory, and must wait to be executed only after the store is executed

Слайд 11

Example of Load Bypassing
Memory access takes four cycles
Actions at various points

in time
End of cycle 1: LQ = [(0)]; SQ = [ ]; execute first load
End of cycle 5: LQ = [(3), (4)]; SQ = [(1)]; execute first load
End of cycle 9: LQ = [(4), (5)]; SQ = [(1), (7)]; execute first load
End of cycle 13: LQ = [(5)]; SQ = [(1), (7)]; load yields to store
We are assuming that no LOADs or STOREs issue between instructions 7 and 22

Computer Architecture and Implementation

Содержание

Instruction-Level ParallelismRelevant Book Reading (HP3): Dynamic Scheduling (in hardware): Appendix A

Hardware Schemes for ILPWhy do it in hardware at run time?Works

Dynamic SchedulingDIV.D F0, F2, F4ADD.D F10, F0, F8SUB.D F12, F8, F147-cycle divider4-cycle adderInstructions are

Explanation of ITo be able to execute the SUB.D instructionA function

Out-of-order Execution and RenamingWAW hazard on register F10: prevents out-of-order execution

Memory ConsistencyMemory consistency refers to the order of main memory accesses

Four Possibilities for Load/Store MotionLoad-LoadLW R1, (R2)LW R3, (R4)Load-Load can always be interchanged

More on Load Bypassing and ForwardingEither transformation can be performed at

Load Bypassing in HardwareRequires two separate queues for LOADs and STOREsEvery

Example of Load BypassingMemory access takes four cyclesActions at various points

Похожие презентации