指令級(jí)流水指令級(jí)并行

1、計(jì)算機(jī)體系結(jié)構(gòu)Report2指令級(jí)流水和指令級(jí)并行永無(wú)休止的“完美”追求戚洪源目錄一、性能瓶頸來(lái)源41、單周期、多周期MIPS結(jié)構(gòu)性能瓶頸42、簡(jiǎn)單的五級(jí)流水MIPS性能瓶頸來(lái)源4相關(guān)4沖突5二、突破瓶頸的可能性5三、性能提升的具體方法61、簡(jiǎn)單的硬件實(shí)現(xiàn)方法6定向技術(shù)6投機(jī)62、基于軟件（編譯器）的靜態(tài)調(diào)度方法7預(yù)測(cè)分支73、軟硬件結(jié)合的動(dòng)態(tài)調(diào)度方法8Tomasulo算法8動(dòng)態(tài)分支預(yù)測(cè)84、多指令流出9基于靜態(tài)調(diào)度的多流出技術(shù)9基于動(dòng)態(tài)調(diào)度的多流出技術(shù)9超長(zhǎng)指令字技術(shù)10超流水線技術(shù)105、循環(huán)展開和指令調(diào)度10四、總結(jié)10摘要：有人說(shuō)，如果計(jì)算機(jī)科學(xué)與技術(shù)是一座金字塔，位于塔尖的一定是高性

2、能計(jì)算。從計(jì)算機(jī)誕生至今，每一次進(jìn)步都是對(duì)于計(jì)算機(jī)性能極限的一次刷新。人類對(duì)于計(jì)算性能日益膨脹的需求，前沿科技對(duì)于高性能計(jì)算的考驗(yàn)，都促使這一領(lǐng)域不斷發(fā)展。單純硬件技術(shù)上的改革是非常重要的：主頻的提高、穩(wěn)定的晶體管但我們同樣驚艷于并行技術(shù)在其中發(fā)揮的神奇的作用。各種并行技術(shù)猶如催化劑一般，使提高計(jì)算機(jī)性能的進(jìn)程大大加快。這些技術(shù)的應(yīng)用，不斷挖掘著計(jì)算機(jī)潛在的性能，也讓人類在一條追求“完美”的道路上不斷前行。何謂“完美”？這是一個(gè)看起來(lái)復(fù)雜實(shí)際上非常簡(jiǎn)單的問(wèn)題?！巴昝馈保褪亲層?jì)算機(jī)每一個(gè)部件每時(shí)每刻全負(fù)荷運(yùn)作，發(fā)揮最高的性能?？此坪?jiǎn)單，但卻很難實(shí)現(xiàn)，也不可能實(shí)現(xiàn)。并行技術(shù)的發(fā)展，也是追求“完美

3、”的嘗試。然而程序“性本惡”，程序本身的許多特性為并行化帶來(lái)了不小的麻煩。我們其實(shí)是在和自己斗爭(zhēng)?！罢ジ捎?jì)算機(jī)每一滴性能”，這是ASC15上浪潮集團(tuán)首席科學(xué)家王恩東演講時(shí)說(shuō)的一句話。在我看來(lái)，不論是指令級(jí)流水還是指令級(jí)并行，目的都是為了“榨干計(jì)算機(jī)每一滴性能”。在這個(gè)過(guò)程中，出于需要又出現(xiàn)了一些非常特殊的結(jié)構(gòu)上的支持。本文將基于MIPS結(jié)構(gòu)，通過(guò)對(duì)于性能瓶頸的來(lái)源、性能突破的可能性、性能提升的具體方法這三方面全面系統(tǒng)地闡述指令級(jí)流水和指令級(jí)并行的相關(guān)知識(shí)。最后再提出一些感想。在第一部分中，我們會(huì)講述單周期到多周期再到流水線的發(fā)展過(guò)程，并對(duì)流水線的性能瓶頸進(jìn)行具體分析。在限制流水線性能的三個(gè)方面

4、中，前兩點(diǎn)只與硬件工藝有關(guān)，最后一點(diǎn)相關(guān)和沖突卻可以通過(guò)許多技術(shù)來(lái)實(shí)現(xiàn)突破。第二部分中，我們會(huì)繼續(xù)討論第一部分中提出的限制流水線性能的重要因素：相關(guān)和沖突。這一部分，我們將從原理層面闡述突破這一瓶頸是可行的。最后一部分，我們按照分類，具體闡述了多種提升性能的方法。一、 性能瓶頸來(lái)源這一部分將由簡(jiǎn)單到復(fù)雜，只提出限制性能的原因，不提出解決方案。這一部分的討論結(jié)果對(duì)后面的研究至關(guān)重要。1、 單周期、多周期MIPS結(jié)構(gòu)性能瓶頸單周期和多周期最大的問(wèn)題就是部件利用率不高。將每一條指令的執(zhí)行過(guò)程粒度化，我們可以發(fā)現(xiàn)：并不是每時(shí)每刻所有的部件都處于工作狀態(tài)。大多數(shù)時(shí)刻只有一個(gè)部件在工作。這種浪費(fèi)是非?？膳?/p>

5、的，不能讓其他部件都閑在那里等一個(gè)部件。如果在同一時(shí)刻能讓更多部件運(yùn)行起來(lái)，性能一定會(huì)大大提高。2、 簡(jiǎn)單的五級(jí)流水MIPS性能瓶頸來(lái)源簡(jiǎn)單的五級(jí)流水是一種最基本的流水結(jié)構(gòu)，在一定程度上解決了單周期和多周期部件空閑的問(wèn)題。然而，折中簡(jiǎn)單的五級(jí)流水結(jié)構(gòu)并不是沒有缺陷的。一方面，如果在設(shè)計(jì)流水線的時(shí)候考慮不周全，使流水線各段不均勻，即有的段比別的段要長(zhǎng)的多，這個(gè)段就成了瓶頸。計(jì)算機(jī)的時(shí)鐘周期取決于這個(gè)瓶頸段的延遲時(shí)間。因此，在設(shè)計(jì)流水線式要盡可能使各段時(shí)間相等。另一方面，由于流水寄存器延遲和時(shí)鐘偏移開銷，流水線增加了許多額外開銷。由于這些額外開銷的存在，會(huì)使每條指令的執(zhí)行時(shí)間有所增加。這些開銷也限

6、制了流水級(jí)數(shù)的加深。最后，也是最關(guān)鍵的，指令的相關(guān)和沖突。當(dāng)一個(gè)流水線設(shè)計(jì)完成后，上面的兩種問(wèn)題對(duì)使用流水線影響就不會(huì)太大了。因?yàn)檫@些開銷是現(xiàn)實(shí)存在的，不會(huì)消亡。我們只能合理設(shè)計(jì)，提升工藝，盡量縮小它們對(duì)于流水線性能的影響。但指令的相關(guān)和沖突，是確確實(shí)實(shí)限制流水性能的重大瓶頸！相關(guān)1、 數(shù)據(jù)相關(guān)對(duì)于兩條指令i（在前，下同）和j（在后，下同），如果下述條件之一成立，則稱這兩條指令數(shù)據(jù)相關(guān)。i. 指令j使用指令i產(chǎn)生的結(jié)果ii. 指令j與指令k數(shù)據(jù)相關(guān)，而指令k又與指令i數(shù)據(jù)相關(guān)2、 名相關(guān)當(dāng)指令i與指令j出現(xiàn)如下兩種情況，都屬于名相關(guān)。i. 反相關(guān)。如果指令j寫的名與指令i讀的名相同，則稱指令i

7、與指令j發(fā)生了反相關(guān)。ii. 輸出相關(guān)。如果指令j與指令i寫的名相同，則指他們發(fā)生了輸出相關(guān)。名相關(guān)的兩條指令之間并沒有數(shù)據(jù)流動(dòng)，只是使用了相同的名。沖突1、 結(jié)構(gòu)沖突因硬件資源滿足不了指令重疊執(zhí)行的要求而發(fā)生的沖突。如：當(dāng)只有一個(gè)存儲(chǔ)器時(shí)，存數(shù)和取指就會(huì)發(fā)生結(jié)構(gòu)沖突。2、 數(shù)據(jù)沖突當(dāng)指令重疊執(zhí)行時(shí)，因需要用前面指令產(chǎn)生的結(jié)果而發(fā)生的沖突。這其中又分為寫后讀沖突和寫后寫沖突。其中寫后讀沖突只發(fā)生在這樣的流水線中：流水線中不止一個(gè)段可以進(jìn)行寫操作。3、 控制沖突流水線遇到分支指令和其他會(huì)改變PC值的指令所引起的沖突?？偟膩?lái)說(shuō)，確定指令之間存在什么樣的相關(guān)，對(duì)于確定程序中有多少并行性以及如何開發(fā)并

8、行性具有重要的意義。如果兩條指令相關(guān)，它們就不可以并行執(zhí)行，只能部分重疊執(zhí)行。沖突時(shí)針對(duì)具體的流水線來(lái)說(shuō)的，由于相關(guān)的存在，使指令流中下一條指令不能在指定的時(shí)鐘周期內(nèi)執(zhí)行。相關(guān)是程序固有的一種屬性，即“性本惡”，它反映了程序中指令相互依賴的關(guān)系。而具體的一次相關(guān)是否會(huì)帶來(lái)沖突以及會(huì)導(dǎo)致多長(zhǎng)時(shí)間的停頓，則是由流水線自身決定的。二、突破瓶頸的可能性自上世紀(jì)80年代中期以來(lái)，幾乎所有的處理機(jī)都利用流水線來(lái)使指令重疊并行執(zhí)行。這種指令之間存在的潛在并行性成為指令級(jí)并行。但上一個(gè)部分出現(xiàn)的問(wèn)題，大多限制了指令級(jí)并行。我們?cè)谶@一部分首先概述開發(fā)并行性的可能性。為下一部分的具體策略做鋪墊。程序的執(zhí)行應(yīng)當(dāng)有自

9、身的一個(gè)順序。但是這個(gè)順序并不是一成不變的。有些語(yǔ)句的調(diào)度并不會(huì)影響程序的執(zhí)行結(jié)果，這也是我們可以進(jìn)行指令調(diào)度的一個(gè)前提。我們介紹的各種軟硬件技術(shù)的目標(biāo)是開發(fā)程序并行性，但同時(shí)也不能護(hù)士程序順序執(zhí)行的要求。那么為了保證程序執(zhí)行結(jié)果正確，我們必須保證程序的什么屬性不受破壞呢？這兩個(gè)屬性就是數(shù)據(jù)流和異常行為。保持異常行為是指無(wú)論怎么改變指令的執(zhí)行順序都不能改變程序中異常的發(fā)生情況。而這兩個(gè)特性經(jīng)常被具體化為：如果能做到保證程序的數(shù)據(jù)相關(guān)和控制相關(guān)，就能保持程序的數(shù)據(jù)流和異常行為。下面一個(gè)部分論述的所有技術(shù)，都是在保證程序的數(shù)據(jù)相關(guān)和控制相關(guān)的基礎(chǔ)上，最大限度地開發(fā)程序的并行性。三、 性能提升的具體

10、方法書上的第三章和第四章都提到了很多技術(shù)來(lái)提升流水線性能?？偟膩?lái)說(shuō)，第三章大多采用了基于軟件的實(shí)現(xiàn)方法或者基于簡(jiǎn)單硬件的實(shí)現(xiàn)方法。第四章主要講解了較為復(fù)雜的軟硬件結(jié)合的實(shí)現(xiàn)方法。此外第四章還包括對(duì)于對(duì)指令流出和循環(huán)展開技術(shù)的介紹。按照這種分類，我們來(lái)具體看一看提升性能1、簡(jiǎn)單的硬件實(shí)現(xiàn)方法定向技術(shù)定向技術(shù)是針對(duì)數(shù)據(jù)沖突的。具體思想是：在某條指令產(chǎn)生結(jié)果前，其他指令并不是真正需要這條指令的計(jì)算結(jié)果，如果能將該計(jì)算結(jié)果從其產(chǎn)生的地方直接送到其他指令需要它的地方，那么就可以避免停頓了。實(shí)現(xiàn)方式如下：l EX段和MEM段之間的流水寄存器中保存的ALU運(yùn)算結(jié)果總是送回到ALU入口。l 當(dāng)定向硬件檢測(cè)到一

11、個(gè)ALU運(yùn)算結(jié)果寫入的寄存器就是當(dāng)前ALU操作的源寄存器時(shí)，那么控制邏輯就選擇定向的數(shù)據(jù)作為ALU入口，而不采用通用寄存器讀出來(lái)的值。投機(jī)這是一種正對(duì)控制沖突的方法，在流水線中加入一個(gè)ALU部件，專門用來(lái)計(jì)算轉(zhuǎn)移的地址。使分支目的地址盡早得出。這是一種硬件上的處理方法，在書中提到了。2、基于軟件（編譯器）的靜態(tài)調(diào)度方法編譯器實(shí)現(xiàn)的指令調(diào)度為了減少停頓，對(duì)于無(wú)法用定向技術(shù)解決的數(shù)據(jù)沖突，可以通過(guò)在編譯時(shí)讓編譯器重新組織指令執(zhí)行順序來(lái)消除沖突。實(shí)際上，對(duì)于各種沖突都有可能用指令調(diào)度來(lái)解決。這里的指令調(diào)度，通過(guò)編譯器實(shí)現(xiàn)，具體實(shí)現(xiàn)方法不展開了。預(yù)測(cè)分支當(dāng)在譯碼段ID檢測(cè)到分支指令時(shí)，如果流水不空等，

12、而是預(yù)測(cè)分支的兩條執(zhí)行路徑中的一條，繼續(xù)處理后續(xù)指令，就可以體改分支指令的處理性能。預(yù)測(cè)有兩種選擇，即預(yù)測(cè)分支成功或預(yù)測(cè)分支失敗。不管采用哪一種，都可以通過(guò)編譯器來(lái)優(yōu)化性能。1) 預(yù)測(cè)分支失敗預(yù)測(cè)分支失敗的方法就是沿失敗的分支繼續(xù)處理指令。當(dāng)確定分支是失敗的，就把分支指令看成一條普通的指令；當(dāng)確定分支是成功的，就把分支之后取出的所有指令轉(zhuǎn)化為空操作，并按照目的地址重新取指執(zhí)行。2) 預(yù)測(cè)分支成功基本與上述一致，但是有一個(gè)不同的地方：在沒有投機(jī)的流水線中，轉(zhuǎn)移地址和分支判斷結(jié)果是同時(shí)得出的，這時(shí)候預(yù)測(cè)分支成功就沒有意義了。因此，預(yù)測(cè)分支成功要在投機(jī)的流水線中才可以使用。3) 延遲分支這種方法的主

13、要思想就是在分支指令的后面加上幾條指令，把它們看成一個(gè)整體。不管分支是否成功，都要按照順序執(zhí)行這些指令。這幾條指令被稱為指令槽。放入延遲槽的指令是由編譯器完成的，實(shí)際上延遲分支是否能帶來(lái)好處完全取決于編譯器能否把有用的指令調(diào)入延遲槽。常用的調(diào)度策略有三種：從前調(diào)度，從目標(biāo)處調(diào)度，從失敗處調(diào)度。上述的方法受兩方面限制：一方面是可以被放入延遲槽中的指令要滿足一定要求，另一個(gè)是編譯器預(yù)測(cè)分支轉(zhuǎn)移方向的能力。3、軟硬件結(jié)合的動(dòng)態(tài)調(diào)度方法第三章中討論的簡(jiǎn)單流水線有一個(gè)主要的局限性，即指令是按程序順序流出和按序執(zhí)行的。如果某條指令在流水線中被停頓了，則后面所有的指令都將停止執(zhí)行。如果系統(tǒng)中有多個(gè)部件，這些

14、部件可能會(huì)因?yàn)闆]有指令處理而處于空閑狀態(tài)，系統(tǒng)效率低下。動(dòng)態(tài)調(diào)度可以實(shí)現(xiàn)多指令同時(shí)處于執(zhí)行狀態(tài)，可以最大限度地利用系統(tǒng)中每一個(gè)部件。Tomasulo算法Tomasulo算法致力于解決程序的數(shù)據(jù)沖突，這個(gè)算法核心思想如下：l 記錄和檢測(cè)指令相關(guān)，操作數(shù)一旦就緒立即執(zhí)行，把發(fā)生RAW沖突的可能性降到最低。l 通過(guò)寄存器換名來(lái)消除WAR沖突和WAW沖突。相比較于記分牌算法，它在硬件上增加了CDB總線、保留站等結(jié)構(gòu)，但是它的記錄表要比記分牌算法簡(jiǎn)單一些，并且無(wú)需等待寫回后再調(diào)用，提高了執(zhí)行速度（書112頁(yè)開始介紹）。動(dòng)態(tài)分支預(yù)測(cè)與Tomasulo算法不同，雖同為動(dòng)態(tài)調(diào)度方法，動(dòng)態(tài)分支預(yù)測(cè)則主要解決控制

15、沖突。當(dāng)所開發(fā)的指令級(jí)并行越多，控制相關(guān)的制約就越大，分支預(yù)測(cè)就需要有更高的精準(zhǔn)度。1) 采用分支歷史表BHTBHT是記錄分支歷史信息的表格，用于判定一條分支指令是否token；這兒記錄的是跳轉(zhuǎn)信息，簡(jiǎn)單點(diǎn)的，可以用1bit位記錄，例如1表示跳轉(zhuǎn)，0表示不跳轉(zhuǎn)，而這個(gè)表格的索引是指令PC值；考慮在32位系統(tǒng)中，如果要記錄完整32位的branch history，則需要4Gbit的存儲(chǔ)器，這超出了系統(tǒng)提供的硬件支持能力；所以一般就用指令的后12位作為BHT表格的索引，這樣用4Kbit的一個(gè)表格，就可以記錄branch history了。研究發(fā)現(xiàn)在BHT中用1bit位記錄分支是否跳轉(zhuǎn)還不夠準(zhǔn)確，用

16、2bit位記錄就非常好了，而用3bit或者更多位記錄，效果與2bit類似。所以在BHT中，一般就用2bit位記錄分支是否跳轉(zhuǎn)：例如11和10表示這條分支會(huì)跳轉(zhuǎn)；01和00表示分支不會(huì)跳轉(zhuǎn)。這個(gè)2bit計(jì)數(shù)器大伙叫做飽和計(jì)數(shù)器（書126頁(yè)轉(zhuǎn)換圖）。2) 采用分至目標(biāo)緩沖器BTB用于記錄一條分支指令的跳轉(zhuǎn)地址，由于這兒存儲(chǔ)的是指令地址，例如32位地址，因此，這個(gè)表格就不能做到存儲(chǔ)BHT那樣多的內(nèi)容了，如果也支持4K條指令，則需要128Kbit的存儲(chǔ)空間，這幾乎可以趕上一個(gè)L1Cache的容量了，所以BTB一般很小，就32項(xiàng)或者64項(xiàng)。由于這個(gè)BTB容量小，并且其用于是記錄分支指令的跳轉(zhuǎn)地址，因此，

17、如果這條指令不跳轉(zhuǎn)，即其下一條指令就是PC+4，則不會(huì)在BTB中記錄的。3) 基于硬件的前瞻執(zhí)行前瞻執(zhí)行能很好解決控制相關(guān)的問(wèn)題，它對(duì)分支指令的結(jié)果進(jìn)行猜測(cè)，并假設(shè)這個(gè)猜測(cè)總是正確的，然后按指令繼續(xù)取、流出、執(zhí)行指令。知識(shí)執(zhí)行指令的結(jié)果不是寫回到寄存器或存儲(chǔ)器，而是放到一個(gè)稱為ROB的緩存器中。等到相應(yīng)指令確認(rèn)后，才將結(jié)果寫入寄存器或存儲(chǔ)器?；谟布那罢皥?zhí)行是吧三種思想結(jié)合在一起：1) 動(dòng)態(tài)分支預(yù)測(cè)。用來(lái)選擇后續(xù)的指令。2) 在控制相關(guān)的結(jié)果尚未出來(lái)之前，前瞻地執(zhí)行后續(xù)指令。3) 用動(dòng)態(tài)調(diào)度對(duì)基本塊的各種組合進(jìn)行跨基本塊的調(diào)度。4、多指令流出單流出的情況下，CPI就不可能小于一。前面的討論可

18、以減少因?yàn)闆_突導(dǎo)致的停頓，是CPI盡可能小。如果想進(jìn)一步提高技能，使CPI小于1，就必須采用多流出技術(shù)，在每個(gè)時(shí)鐘周期流出多條指令。多流出處理機(jī)有兩種基本風(fēng)格：超標(biāo)量和超長(zhǎng)指令字。書中134頁(yè)表4.2給出了各種多流出技術(shù)以及它們的優(yōu)缺點(diǎn)。下面介紹四種重要的多流出技術(shù)。他們是：基于靜態(tài)調(diào)度的多流出技術(shù)、基于動(dòng)態(tài)調(diào)度的多流出技術(shù)、超長(zhǎng)指令字技術(shù)、超流水技術(shù)。基于靜態(tài)調(diào)度的多流出技術(shù)在靜態(tài)調(diào)度的超標(biāo)量處理機(jī)中，指令按序流出。所有沖突檢測(cè)都在流出中實(shí)施，由硬件檢測(cè)當(dāng)前流出的指令之間是否存在沖突以及當(dāng)前流出的指令和正在執(zhí)行的指令是否存在沖突。如果在當(dāng)前流出的指令序列中，某條指令存在上述沖突，那么久只能流

19、出該指令以前的指令。因此，使用基于靜態(tài)調(diào)度的多流出技術(shù)的超標(biāo)量處理機(jī)只能順序執(zhí)行指令。為了能有效利用超標(biāo)量處理機(jī)所具有的并行性，需要采用更有效的編譯技術(shù)或者硬件調(diào)度技術(shù)。如果不采用這些技術(shù)，超標(biāo)量技術(shù)所能帶來(lái)性能上的提高可能很小。基于動(dòng)態(tài)調(diào)度的多流出技術(shù)動(dòng)態(tài)調(diào)度不僅在有數(shù)據(jù)沖突的情況下提高性能，而且還有可能克服指令流出所受的限制。換句話說(shuō)，盡管從硬件角度來(lái)說(shuō)，在每個(gè)時(shí)鐘周期最多只能啟動(dòng)一個(gè)整數(shù)操作和一個(gè)浮點(diǎn)操作的執(zhí)行，但是動(dòng)態(tài)調(diào)度可以使指令流出不受這個(gè)限制。這一部分不作具體學(xué)習(xí)。超長(zhǎng)指令字技術(shù)超長(zhǎng)指令字技術(shù)是另一種多指令流出技術(shù)，與超標(biāo)量不同，他在指令流出時(shí)不需要進(jìn)行復(fù)雜的沖突檢測(cè)，而是依靠編譯器編譯時(shí)找出指令之間潛在的并行性，并通過(guò)指令調(diào)度把可能出現(xiàn)的數(shù)據(jù)沖突減少到最少，最后把能并行執(zhí)行的多條指令組裝成一天很長(zhǎng)的指令。這種指令字經(jīng)常是100多位到幾百位，超長(zhǎng)指令字因此得名