owned this note
owned this note
Published
Linked with GitHub
# 2016q3 Homework3 (software-pipelining)
contributed by `<tundergod>`
## 資料閱讀
### Modern Microprocessors - A 90-Minute Guide!
* More Than Just Megahertz
```
SPECint95 SPECfp95
195 MHz MIPS R10000 11.0 17.0
400 MHz Alpha 21164 12.3 17.2
300 MHz UltraSPARC 12.1 15.5
300 MHz Pentium II 11.6 8.8
300 MHz PowerPC G3 14.8 11.4
135 MHz POWER2 6.2 17.6
Table 1 – Processor performance circa 1997.
```
* 文章一開始說明了處理器的效能不能只看處理器的頻率(Clock Cycle),處理器的效能還取決於每一個clock cycle能做多少做工而定,而不是只看速度
* Pipelining
* 利用分段式的架構把處理器架構分爲4個階段(pipieline)或是再細分爲更多階段(deeper pipelines),主要的想法是讓每一個處理器單元都能夠一直保持工作狀態(擁有更高的平行度和頻率)
* Multiple Issue – Superscalar
![](https://i.imgur.com/w6uTFwv.png)
* 把每一個階段在功能上分開
* 可以根據不同的指令做不同的clock cycle(做int的運算會比float的快3倍).
* 可以同時fetch3個指令平行執行對應的運算,但同時fetch到3個需要同一條流水線的指令則會卡着(處理器在優化過程中的reordering就是在針對multiple issue的問題上進行優化)
* multiple issue可以和pipeline結構結合:
![](https://i.imgur.com/LA95NVH.png)
* Explicit Parallelism – VLIW
![](https://i.imgur.com/36Aa5I3.png)
* VLIW(very long instruction word),指令由許多子指令組成形成超級長的指令,裏面也包含着平行運算的信息
* 好處:不必去檢查指令之間的相依性
* 壞處:在cache miss的情況下會阻塞整個處理器的運作(因爲指令只有一條)
* Instruction Dependencies & Latencies
```
a = b * c;
d = a + 1;
```
* 第一條指令和第二條有依賴關係,且乘法的cycle數會比加法的多,第二條指令在等待a的結果出來的時候會形成延遲(會插入bubble)(更多stage的pipeline在延遲中等待的cycle數會比較少的更多,所以pipeline越深不一定是越好的)
* 編譯器會進行指令的調整讓bubble被其他不相關的指令代替
* Branches & Branch Prediction
* 在進行判定式,循環和函式呼叫會發生
* 靜態分支預測:無論執行怎麼樣的指令,編譯器都會用相同的prediction strategy告訴處理器執行哪一條指令
* 動態分支預測:通過分支的歷史去判斷應該在接下來執行哪一條指令.通常都會使用2bit的precditor(00,01,10,11),通過之前的歷史把執行指令的強度分爲4個等級
* 文章中說到即使是90%成功率的predictor也會因爲預測錯誤失去了30%的效能(以Pentium-Pro/II/III爲例)
* 除了以上兩種,branch predictor也有許多種例如局部預測,全局預測,神經預測等.
* 在 James E. Smith的論文[A study of branch prediction strategies](http://dl.acm.org/citation.cfm?id=801871)中發表了7中不同的預測策略,最高可高達99.4%
![](https://i.imgur.com/m5jmbKs.png)
![](https://i.imgur.com/Qy8VSSk.png)
* Eliminating Branches with Predication
* 同時執行else和if的指令,不去做預測的動作.
* 在程式碼較短的時候非常有利(如ARM),在較長程式碼的情況下因爲指令非常多會浪費許多資源
* Instruction Scheduling, Register Renaming & OOO
* 靜態指令調度:編譯器重新排序指令的執行順序盡量避免hazzard或latencies的發生
* 動態指令調度(亂序調度):處理器向前看多組指令並以最佳化的情況分配邏輯單元給他們.通過這種方式處理指令時會使用一組額外的renamed registers.
* renaming register是爲了解決指令的hazard(WAR)問題,通過使用renamed register去代替原本會處於延遲狀態的register並和原本的register保持映射關係,確保結果不會錯誤
* 重排序缓冲区(Re-order buffer):分爲dispatch,issue,execute,commit,write result.
* Re-order buffer通過動態dispatch(分配空閒)(or剛做完工)的處理器單元給在等待並需要用到的指令使用
* commit(提交)把renamed register的結果返回給真正的register(R0 ~ R15).
* Threads – SMT, Hyper-Threading & Multi-Core
* Simultaneous multi-threading (SMT):當一個process發生了延遲,CPU切換到另一個process執行.(多個process共享一個processor)
* SMT並不能有效的幫助部分應用如:圖像,影像或聲音的處理因爲這些程式都被bandwidth(內存大小)影響,不夠會發生page fault
* multi-core:在每一個core上運行一個processor(每一個core上都有一套各自的硬體單元,cache等)
* More Cores or Wider Cores?
* [Why doesn't “add more cores” face the same physical limitations as “make the CPU faster”?](http://superuser.com/questions/797454/why-doesnt-add-more-cores-face-the-same-physical-limitations-as-make-the-cpu)
* SMT的處理器在設計上需要更大容量的核心和更多的邏輯運算單元,這會使核心非常大,而且同樣的大小能夠放多個普通的core在上面
* 對於較活躍但會受內存容量限制的程式,多核比較好,但對於普通的程式,單核多行程是更好的選擇
* Data Parallelism – SIMD Vector Instructions
* 使用一條指令處理多個矢量算法,避免太多的指令(因爲在圖形或影像的處理中,大多數都會對同一個算式進行非常多次簡單的重復運算),例如圖像運算每一個顏色(RGB和alpha)只需要8bits,且不必進位,最多32bits
* Memory & The Memory Wall
* resource:[記憶體參數](http://www.dk101.com/Discuz/viewthread.php?tid=54338)
* 從內存加載數據造成的延遲非常嚴重
* 以 800 MHz SDRAM並擁有2.4 GHz processor的系統爲例,一次加載的延遲爲(1(發送地址到DIMM)+11(RAS-to-CAS)+11(CAS延遲)+1(把結果送回處理器)) * 2400/800 + 20(從cache的檢查->送到core的延遲) = 92 cycles .而頻率越高的處理器所浪費的延遲也越高
* Caches & The Memory Hierarchy
* 現代處理器使用cache來解決memory wall的問題,cache儲存最近使用到的data並能讓processor快速的存取
* cache的缺點:在查找cache時看使用physical address 或 virtual address.
* 使用虛擬地址就造成了不同的程式會使用同樣的虛擬地址並且映射到相同的物理地址,這樣cache就必須在每一次上下文切換的時候進行刷新
* 使用物理地址也必須同時執行虛擬地址到物理地址的映射,這樣效能就會變慢.
* 解決辦法:virtually-indexed physically-tagged cache,物理地址作爲tag,在進行cache查找的時候也並行查找兩地址之間的映射關係
* Cache Conflicts(緩存衝突) & Associativity
* 在cache中儲存的數據越多,你在cache之中找東西的速度也會越慢.所以一些cache使用了只在某些特定的位置進行cache的存取動作.這也就表示會有幾個或更多的memory 映射到cache的特定位置上,當兩個或以上的memory映射到同一個cache之後,就會發生cache conflicts
* 當一個program一直連續讀取cache conflict的地址會發生thrashing(延遲100或更多cycle)
* Memory Bandwidth vs Latency
* bandwidth:最大傳輸容量造成的限制(RDRAM)
* 更寬的buses,但是更高的開銷
* latency:最大傳輸速度造成的限制(SDRAM)
* 與system bus擁有同步的接口,內存系統流水線化
### 在計算機裡頭實踐演算法
### When Prefetching Works, When It Doesn’t, and Why
##### `tundergod` `sysprog` `hw3` `2016q3`