[EE_CSIE] Tomasulo's algorithm

呼，終於把 Tomasulo's Argorithm 推完ㄌ，

這個人真的是很厲害啊～
Scoreboard 計分版 (註1) 已經有一點小複雜了，

1967年(四十年前) IBM Robert Tomasulo 這個老傢伙還推出了進化版，

可見他內心的能量非常的強，才能又發現這麼強大的咒語 ...

( ㄆ，又寫到魔法少年賈修那邊去了... Orz ...

Tomasulo 演算法第一次實現(implemented)

是在 IBM360/91 的浮點運算單元FPU(Floating Point Unit)，
運用了暫存器重新命名(Register Renaming)、

共用資料匯流排CDB(Common data bus) 廣播到訂位站(Reservation Station)
來增強指令的平行執行 (Improved Parallel execution of Instructions)。
而這是一種 Hardware 的 ILP (Instruction-Level Parallelism)方式，

所以是 Dynamic 的。
... ... ... more ... ... ...

跟 Scoreboard 一樣，運用了暫存器重新命名(Register Renaming)能夠解決

WAR(Write after Read：又稱 Anti-Dependence)、

WAW(Write after Write：又稱 Output-Dependence)的危障(Harzard)，
這個在第一步驟 Issue 時，便能消除。

而 RAW(Read after Write：又稱 True-Dependence)，

只能藉由延後指令執行直到所有的Oprand(運算元)都到齊才能避免掉。
這個在第二步驟 Execute 時，便能消除。
最後，第三個步驟 Write Back，

就能運用 CDB傳到 Register 以及任何一個等待這個結果的

訂位站(Reservation Station)作一個緩衝。

(註1) : Scoreboarding; is a technique for allowing instructions to execute out-of-order when there are sufficient resources and no data dependences;

Example : The following is an example of the reservation station status when all of the instructions have issued, but only the first load instruction has completed and written its result to the CDB.

1. L.D F6, 34(R2)

2. L.D F2, 45(R3)

3. MUL.D F0, F2, F4

4. SUB.D F8, F2, F6

5. DIV.D F10, F0, F6

6. ADD.D F6, F8, F2

.End.