目錄

引言

流水線定義

指令執(zhí)行流水

指令流水圖

循環(huán)展開優(yōu)化

---

引言

詳細(xì)的流水線分析大家可以參考：計(jì)算機(jī)體系結(jié)構(gòu)——流水線技術(shù)（Pipelining）。本篇只是由探討循環(huán)展開如何提高代碼執(zhí)行效率延申過來的，因此只說明基本的流水線定義以及關(guān)于循環(huán)展開的部分。

?

流水線定義

計(jì)算機(jī)中的流水線是把一個重復(fù)的過程分解為若干個子過程，每個子過程與其他子過程并行進(jìn)行。由于這種工作方式與工廠中的生產(chǎn)流水線十分相似， 因此稱為流水線技術(shù)，從本質(zhì)上講，流水線技術(shù)是一種時(shí)間并行技術(shù)。

?

流水線工作設(shè)計(jì)

• 基本思想：延伸重疊方式，使指令解釋過程進(jìn)一步細(xì)化，提高各部件的利用率，以提高指令執(zhí)行速度
• 理想目標(biāo)：完成任務(wù)的時(shí)間與其中某個指令執(zhí)行時(shí)間無關(guān)，只與指令執(zhí)行的頻率有關(guān)（假設(shè)一個任務(wù)有n個指令，將完成一個指令分為m個段，每段執(zhí)行時(shí)間為△t ，則理想目標(biāo)是完成任務(wù)的時(shí)間是T=m△t+(n-1)△t；當(dāng)n >> m時(shí)，T=(n-1)△t。 指令執(zhí)行頻率為 ?1 / △t： 即 與m無關(guān)，只和指令執(zhí)行的速度△t有關(guān)）

指令執(zhí)行流水

取指：

　　指令取指（InstrucTIon Fetch）是指將指令從存儲器中讀取出來的過程。

譯碼：

　　指令譯碼（InstrucTIon Decode）是指將存儲器中取出的指令進(jìn)行翻譯的過程。經(jīng)過譯碼之后得到指令需要的操作數(shù)寄存器索引，可以使用此索引從通用寄存器組（Register File，Regfile）中將操作數(shù)讀出。

執(zhí)行：

　　指令譯碼之后所需要進(jìn)行的計(jì)算類型都已得知，并且已經(jīng)從通用寄存器組中讀取出了所需的操作數(shù)，那么接下來便進(jìn)行指令執(zhí)行（InstrucTIon Execute）。指令執(zhí)行是指對指令進(jìn)行真正運(yùn)算的過程。譬如，如果指令是一條加法運(yùn)算指令，則對操作數(shù)進(jìn)行加法操作；如果是減法運(yùn)算指令，則進(jìn)行減法操作。

　　在“執(zhí)行”階段的最常見部件為算術(shù)邏輯部件運(yùn)算器（ArithmeTIc Logical Unit，ALU），作為實(shí)施具體運(yùn)算的硬件功能單元。

訪存：

　　存儲器訪問指令往往是指令集中最重要的指令類型之一，訪存（Memory Access）是指存儲器訪問指令將數(shù)據(jù)從存儲器中讀出，或者寫入存儲器的過程。

寫回：

　　寫回（Write-Back）是指將指令執(zhí)行的結(jié)果寫回通用寄存器組的過程。如果是普通運(yùn)算指令，該結(jié)果值來自于“執(zhí)行”階段計(jì)算的結(jié)果；如果是存儲器讀指令，該結(jié)果來自于“訪存”階段從存儲器中讀取出來的數(shù)據(jù)。

?

指令流水圖

橫坐標(biāo)：表示時(shí)間，即各個任務(wù)或指令在流水線中 所在該時(shí)刻所對應(yīng)的子過程

縱坐標(biāo)：表示某個任務(wù)或某條指令，即流水線依次 處理的任務(wù)或指令

?

循環(huán)展開優(yōu)化

? ? ?在流水線中，往往因?yàn)橹噶铐樞虬才挪缓侠矶鴮?dǎo)致CPU等待空轉(zhuǎn)，產(chǎn)生延遲，影響流水線效率。

? ? ?解決辦法：循環(huán)展開和指令調(diào)度

? ? ?前提假設(shè)：假設(shè)采用MIPS的5段整數(shù)流水線：

? ? ? ? ? ? ? ? ? ?? ? 分支的延遲：1個時(shí)鐘周期。

? ? ? ? ? ? ? ? ? ?? ? 整數(shù)load指令的延遲：1個時(shí)鐘周期。

? ? ? ? ? ? ? ? ? ?? ? 整數(shù)運(yùn)算部件是全流水或者重復(fù)設(shè)置了足夠的份數(shù)。

? ? ?從例題入手理解：

? ? ?例: 對于下面的源代碼，轉(zhuǎn)換成MIPS匯編語言， 在不進(jìn)行指令調(diào)度和進(jìn)行指令調(diào)度兩種情況下，分析其代碼一次循環(huán)所需的執(zhí)行時(shí)間。

for (i=1024； i>=0； i--)x[i] = x[i] + s;

　 Loop：L.D F0,0（R1）?

?????ADD.D F4,F0,F2

?????S.D F4, 0（R1）

?????DADDIU? R1,R1，#-8

?????BNE R1,R2,Loop、

?????其中： ?? 整數(shù)寄存器R1：指向向量中的當(dāng)前元素（初值為向量中最高端元素的地址）

? ? ? ? ? ? ? ? ? 浮點(diǎn)寄存器F2：用于保存常數(shù)s

? ? ? ? ? ? ? ? ? 第二部浮點(diǎn)加法需要4個周期

? ? ?分析：

? ? ?假設(shè)一個浮點(diǎn)計(jì)算部件需要4周期完成一個計(jì)算，若該部件不使用流水線，則延遲為 ：

循環(huán)展開：

? ? ? 在上例中，只有L.D、ADD.D和S.D這3條指令是有效操作 (取、加、存) ，占用3個時(shí)鐘周期。 而DADDIU、空轉(zhuǎn)和BEN這3個時(shí)鐘周期都是附加的循環(huán)控制開銷。可以通過循環(huán)展開的方式消除冗余，減少循環(huán)控制開銷。

• 循環(huán)展開技術(shù)

? ? ? ? 把循環(huán)體的代碼復(fù)制多次并按順序排列，然后相應(yīng)調(diào)整循環(huán)的結(jié)束條件

? ? ? ? 這給編譯器進(jìn)行指令調(diào)度帶來了更大的空間

?

?????將上述例子中的循環(huán)展開3次得到4個循環(huán)體，然后對展開 后的指令序列在不調(diào)度和調(diào)度兩種情況下，分析代碼的性能。

?????分配寄存器（不重復(fù)使用寄存器 ）：

?????? F0、F4：用于展開后的第1個循環(huán)體

?????? F2：保存常數(shù)

?????? F6、F8：展開后的第2個循環(huán)體

?????? F10、F12：第3個循環(huán)體

? ?? ? F14、F16：第4個循環(huán)體

?????下面分三種情況比較循環(huán)展開和指令調(diào)度節(jié)省的時(shí)間：

• 第一種情況：

? ? ?

• 第二種情況：

? ? ?? 對指令序列進(jìn)行優(yōu)化調(diào)度，以減少空轉(zhuǎn)周期

?????? 浮點(diǎn)加法部件采用流水指令流出時(shí)鐘

?

? ? ? ? ??

?

• 第三種情況：

?????? 對指令序列進(jìn)行優(yōu)化調(diào)度，以減少空轉(zhuǎn)周期

?????? 浮點(diǎn)運(yùn)算部件不采用流水

? ? ?

• 循環(huán)展開和指令調(diào)度時(shí)要注意以下幾個方面：

? ? ? ? 保證正確性。 在循環(huán)展開和調(diào)度過程中尤其要注意兩個地方的正確性：循環(huán)控制，操作數(shù)偏移量的修改。

? ? ? ? 注意有效性。 只有能夠找到不同循環(huán)體之間的無關(guān)性，才能有效 地使用循環(huán)展開。

? ? ? ??使用不同的寄存器。 （否則可能導(dǎo)致新的沖突）

? ? ? ? 刪除多余的測試指令和分支指令，并對循環(huán)結(jié)束代碼和新的循環(huán)體代碼進(jìn)行相應(yīng)的修正。

? ? ? ? 注意對存儲器數(shù)據(jù)的相關(guān)性分析 ? ??

? ? ? ? 注意新的相關(guān)性

　　3.指令級并行

　　指令調(diào)度可以通過兩種形式實(shí)現(xiàn)：靜態(tài)調(diào)度和動態(tài)調(diào)度

• 靜態(tài)調(diào)度

　　??依靠編譯器（編譯器需要做的很復(fù)雜，很完善）對代碼進(jìn)行靜態(tài)調(diào)度，以減少相關(guān)和沖突。

　　??它不是在程序執(zhí)行的過程中、而是在編譯期間進(jìn)行代碼調(diào)度和優(yōu)化。

　　? 通過把相關(guān)的指令拉開距離來減少可能產(chǎn)生的停頓。

• ?動態(tài)調(diào)度

　　??在程序的執(zhí)行過程中，依靠專門硬件對代碼進(jìn)行調(diào)度，減少數(shù)據(jù)相關(guān)導(dǎo)致的停頓。

　　? 能夠處理一些在編譯時(shí)情況不明的相關(guān)（比如涉及到存儲器訪問的相關(guān)），并簡化了編譯器；

　　? 能夠使本來是面向某一流水線優(yōu)化編譯的代碼在其他的流水線（動態(tài)調(diào)度）上也能高效地執(zhí)行。

　　??以硬件復(fù)雜性的顯著增加為代價(jià)

總結(jié)

以上是生活随笔為你收集整理的代码执行流水之循环展开优化的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。