Re: [理工] unrolling問題 交大

[kyuudonut (善良老百姓)]

: → wacheck: 想在請問一下unrolling有偏好static multiple issue或     12/15 15:02
: → wacheck: dynamic multiple issue嗎                               12/15 15:02
: → anonimo: Loop unrolling 應該是compiler(software)處理的          12/15 16:23

Loop unrolling 最大的好處是減少 branch overhead，
這個好處對於 static/dynamic multiple issue 都會是有益的。

但對於 dynamic multiple issue 可能好處沒有顯著於 static，
畢竟它本來就能夠 speculative execution。

但會說對於 dynamic multiple issue processor 仍有好處的原因是因為:
speculative execution 的 cost 高，每遇到一個 branch 會需要做一份 checkpoint，
branch miss 後整個 processor state 又要 roll back，所以還是有蠻大的 penalty。

所以 loop unrolling 可以減緩這種 dynamic multiple issue 遭遇的情況。

至於 static multiple issue 更需要 loop unrolling 的原因是因為，
loop unrolling 後可以給我們帶來更多的 ILP (Instruction Level Parallelism)，
讓 Compiler backend 更有空間可以去做 instruction scheduling，
以實現 software pipelining，才能夠讓 static multiple issue processor
的所有 pipelines fully utilized。

當然缺點還是有:
1. code size 會變大，做 embedded 上的 library 需要去考慮此問題，
I$ 也因此容易 cache miss。

2. register pressure 會變大，如果 instruction scheduling 沒做好，
因 unrolling 被 spill 掉的 register 會讓整個 performance 掉下來。

想了解更多的話可再參考 Computer Architecture: A Quantitative Approach，
裡面有專門一個章節在探討 loop unrolling。

--
 ◢          ◣  ▁▂█▂▁◢茄你老木！    ◥      ▁▂▁
   你這個茄子     ◤◥◤◥     你有得茄嗎？     ◢█ ◆ █◣ 【茄~】
 ◣          ◤    ˋ  ˊ  ◥  你有得茄嗎？◢  ◤ ◥◥◤◤ ◥ ◤
  ◤                 ㄧ  ◣ ◤  (因為很重要   ▉   ⊙  ⊙   ▏
…               ▍                所以說兩次)▉     △  ◢ ▏
                 ◣     ◤◤                   ◣        ◤◢       ψJeans1020 ◢          ◣  ▁▂█▂▁◢茄你老木！    ◥      ▁▂▁

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.16.173
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1544933746.A.A40.html
推 b10007034: dynamic好像少講OOOE？不然有speculation也沒辦法執行
這邊的 dynamic 其實就是意指 OOOE 了，

而 Speculation 與 OOOE 算是兩件事情，你的問題是?

→ b10007034: 吧？
→ b10007034: 其他的內容都很讚
推 wacheck: 太神啦感謝大神
※ 編輯: kyuudonut (175.96.113.214), 12/17/2018 19:54:41
推 b10007034: http://imgur.com/ZZ5naEZ
推 b10007034: dynamic跟OOOE不是等於吧?
感謝指正! 藉此文我也終於了解柱子本對於 dynamic issue 的定義，
即使是 dual in-order issue processor，dynamic 的地方是在於
單一 cycle 可 issue 0 ~ 2 instructions 不定。

但 VLIW 不一樣，它是由 compiler static time 就決定一次要
issue 多少 instructions。

→ b10007034: 原文書有詳細做分類，另外speculation那邊我的意思是
→ b10007034: 如果要用hardware做loop unrolling，要用
→ b10007034: dynamic scheduling+OOOE+speculation
或許行為上有些許類似，但本質上是完全不一樣的，
一個是 static time 時就確保 unrolled loop 是可以執行的 (還會做 scheduling)，
一個則是使用額外 resource 去偷跑下一個 iteration，我想你也明白。

一個 Architecture 老師應該會嚴正否認這種說法 XD

另外沿著你一開始的 context，我必須說，只要有 Speculation 就可以偷跑，
不一定需要 OOOE。Itanium 2 就是一個典型的例子。
※ 編輯: kyuudonut (175.96.113.214), 12/18/2018 22:30:44
推 b10007034: 沒錯，dynamic那邊我一開始也搞混，搞懂之後也會忘XD
→ b10007034: 然後你這邊指正的一點都沒錯XD，我打完之後才發現我的
→ b10007034: 意思跟我表達的有落差，原本想解釋，但是懶XD
→ b10007034: speculation我還是不太懂，我一直以為他是一個偵測的
→ b10007034: 概念，偵測到某處instr.可以先執行之後，在由OOOE把
→ b10007034: 某處instr.先放到issue slot
→ b10007034: 我在多看看CA.原文書對HW based&SW based的實作與解釋
推 b10007034: 目前是直接看Itanium是寫有speculatively prefetch
→ b10007034: OOOE也看得更懂了一點，以為跟speculation有一定關係
→ b10007034: 看原文書上解釋不太像有一定關係，獨立運作
OOOE 通常會自帶 speculation 是因為想要 exploit 更多的 instruction 塞進 pipeline

看原文書會理解有限，甚至現在商用的 Processor 其實 issue / execute 的定義
都會跟課本不一樣。只能看網路上 ARM Cortex-A8 的架構來多參考 (課本也有~)

或是找最經典的 Alpha 21264 的論文來看，可能都會有更深的體悟，
不過就研究所考試來說，應該不用準備這麼多，連台大可能都不太可能考這麼細，
不過還是歡迎後續討論 :)
※ 編輯: kyuudonut (175.96.113.214), 12/19/2018 20:02:02
推 b10007034: 純粹就是個人興趣而已，CPU其實蠻有趣好玩的
→ b10007034: 這顆沒注意到過，我是關注另外一顆RISC-V
→ b10007034: 還是謝謝你的回復，目前還是處於尷尬的狀態
→ b10007034: 半隻腳進入這個領域，太淺很難聊，太深又無法理解