高等計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)

第4章指令級(jí)并行(Instruction-LevelParallelism)鄭州大學(xué)信息工程學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系高等計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)

ComputerArchitecture第4章指令級(jí)并行數(shù)據(jù)相關(guān)的動(dòng)態(tài)指令調(diào)度控制相關(guān)的動(dòng)態(tài)分支預(yù)測(cè)超標(biāo)量和VLIW編譯器的靜態(tài)指令調(diào)度：循環(huán)展開(kāi)指令級(jí)并行研究程序中指令之間存在的并行性提高指令級(jí)并行度可以從兩個(gè)方面展開(kāi)：基于硬件的動(dòng)態(tài)技術(shù)，基于軟件的靜態(tài)技術(shù)目前處理器的研發(fā)方向正朝著開(kāi)發(fā)出更多指令級(jí)并行操作的方向發(fā)展……J.Fisher[1981],摘自引入“指令級(jí)并行”的論文4.1指令級(jí)并行的概念流水線(xiàn)技術(shù)的處理器性能： CPI流水線(xiàn)＝CPI理想 ＋停頓結(jié)構(gòu)沖突＋停頓數(shù)據(jù)沖突＋停頓控制沖突程序中指令之間的相關(guān)可能導(dǎo)致沖突的發(fā)生保持相關(guān)，但避免發(fā)生沖突代碼變換，消除相關(guān)正確地執(zhí)行程序，必須保持?jǐn)?shù)據(jù)流（dataflow）和異常行為（exceptionbehavior）做到保持程序的數(shù)據(jù)相關(guān)和控制相關(guān)，就能保持?jǐn)?shù)據(jù)流和異常行為4.2指令的動(dòng)態(tài)調(diào)度指令調(diào)度（scheduling）：通過(guò)改變指令在程序中的位置，將相關(guān)指令之間的距離加大到不小于指令執(zhí)行延遲的時(shí)鐘數(shù)，這樣就可以將相關(guān)指令轉(zhuǎn)化為無(wú)關(guān)指令靜態(tài)調(diào)度通過(guò)編譯器在編譯期間進(jìn)行代碼調(diào)度和優(yōu)化動(dòng)態(tài)調(diào)度通過(guò)硬件在程序的執(zhí)行過(guò)程中進(jìn)行代碼調(diào)度，調(diào)整指令實(shí)際執(zhí)行時(shí)的關(guān)系動(dòng)態(tài)指令調(diào)度以硬件的復(fù)雜性換取性能的提高。它可以處理一些編譯時(shí)未發(fā)現(xiàn)的相關(guān)，簡(jiǎn)化編譯器的設(shè)計(jì)。它可以實(shí)現(xiàn)在一種流水線(xiàn)上編譯的代碼在另外一種流水線(xiàn)上有效地執(zhí)行采用靜態(tài)調(diào)度方法生產(chǎn)的代碼也可以在使用動(dòng)態(tài)調(diào)度的處理器中運(yùn)行，同樣可以獲得性能提高4.2.1動(dòng)態(tài)調(diào)度的原理前面所述的流水線(xiàn)技術(shù)的一個(gè)主要局限是指令是順序流出(in-orderissue)和順序執(zhí)行(in-orderexecution)。如果一條指令在流水線(xiàn)中，與之相關(guān)的指令及其后面的指令都不能進(jìn)行處理將基本MIPS流水線(xiàn)中譯碼階段分成兩個(gè)階段：發(fā)射：指令譯碼，并檢查資源沖突讀操作數(shù)：檢查數(shù)據(jù)相關(guān)，沒(méi)有數(shù)據(jù)相關(guān)就可以讀取操作數(shù)只要指令操作數(shù)就緒就執(zhí)行， 即指令會(huì)亂序執(zhí)行(out-of-orderexecution)，指令也會(huì)亂序結(jié)束(out-of-ordercompletion)DIV.DF4,F0,F2SUB.DF10,F4,F6ADD.DF12,F6,F14亂序執(zhí)行引起的WAR和WAW沖突DIV.DF4,F0,F2SUB.DF10,F4,F6

ADD.DF6,F12,F14

WAR沖突（反相關(guān)引起） 如果在SUB.D讀出F6之前ADD.D執(zhí)行結(jié)束，會(huì)出現(xiàn)問(wèn)題DIV.DF4,F0,F2SUB.DF10,F4,F6

ADD.DF10,F6,F14WAW沖突（輸出相關(guān)引起） 如果在SUB.D寫(xiě)入F10之前ADD.D執(zhí)行結(jié)束，會(huì)出現(xiàn)問(wèn)題寄存器換名可以消除WAR和WAW沖突DIV.DF4,F0,F2SUB.DF10,F4,F6

ADD.DF8,F12,F14

消除WAR沖突 ADD.D指令的F6更名為F8DIV.DF4,F0,F2SUB.DF10,F4,F6

ADD.DF8,F6,F14消除WAW沖突 ADD.D指令的F10更名為F8動(dòng)態(tài)調(diào)度：記分牌記分牌(scoreboard)：在資源部件充足，沒(méi)有數(shù)據(jù)相關(guān)的前提下，允許亂序執(zhí)行的技術(shù)。它的命名起源于CDC6600的記分牌每條指令均經(jīng)過(guò)記分牌，并記錄下有關(guān)數(shù)據(jù)相關(guān)的信息；然后記分牌判斷何時(shí)可以讀操作數(shù)并開(kāi)始執(zhí)行；記分牌還控制指令寫(xiě)目標(biāo)寄存器的時(shí)機(jī)。阻塞及其解除的檢測(cè)全都集中在記分牌上記分牌的性能受限于程序中可開(kāi)發(fā)的指令并行性、記分牌容量、功能部件的數(shù)目和種類(lèi)、反相關(guān)和輸出相關(guān)名相關(guān)在動(dòng)態(tài)調(diào)度的亂序執(zhí)行情況下更加嚴(yán)重4.2.2動(dòng)態(tài)調(diào)度：Tomasulo算法Tomasulo算法結(jié)合了記分牌的關(guān)鍵部分和寄存器重命名技術(shù)，其核心是通過(guò)寄存器重命名來(lái)解決名相關(guān)引起的阻塞。IBM360/91浮點(diǎn)部件采用，由RobertTomasulo發(fā)明在Tomasulo算法中，寄存器重命名是通過(guò)保留站(reservationstation)來(lái)實(shí)現(xiàn)，它保存等待發(fā)射和已經(jīng)發(fā)射指令所需要的操作數(shù)。其基本思想是只要操作數(shù)有效，就將其送到保留站，避免指令直接從寄存器取數(shù)據(jù)。即將執(zhí)行的指令從相應(yīng)的保留站取得操作數(shù)，并將結(jié)果直接送到等待數(shù)據(jù)的保留站保留站的數(shù)目多于實(shí)際的寄存器，通過(guò)使用保留站將寄存器重命名，就消除了名相關(guān)4.3動(dòng)態(tài)分支預(yù)測(cè)技術(shù)處理器可達(dá)到的指令級(jí)并行度越高，控制相關(guān)的影響越大動(dòng)態(tài)解決技術(shù)利用硬件對(duì)程序運(yùn)行時(shí)分支的行為進(jìn)行預(yù)測(cè)，提前對(duì)分支操作做出反應(yīng)，加快分支處理的速度。分支預(yù)測(cè)的效果不僅取決于其準(zhǔn)確性，而且與分支預(yù)測(cè)時(shí)的開(kāi)銷(xiāo)密切相關(guān)。分支轉(zhuǎn)移的最終延遲取決于流水線(xiàn)的結(jié)構(gòu)、預(yù)測(cè)的方法和預(yù)測(cè)錯(cuò)誤后恢復(fù)所采取的策略動(dòng)態(tài)分支預(yù)測(cè)技術(shù)要記錄分支指令的歷史、并據(jù)此決定預(yù)測(cè)的分支，還要盡快找到分支目標(biāo)地址，從而避免控制相關(guān)造成流水線(xiàn)停頓4.3.1分支歷史表分支歷史表（BranchHistoryTable，BHT） 分支預(yù)測(cè)緩沖（BranchPredictionBuffer） 將分支指令的地址和分支歷史情況保存在分支歷史表。用分支指令的低位地址作為索引，用1位、2位（或N位）作歷史記錄（預(yù)測(cè)位），記錄最近一次或幾次的分支歷史：①根據(jù)歷史記錄（預(yù)測(cè)位狀態(tài)）進(jìn)行分支預(yù)測(cè)②根據(jù)實(shí)際分支情況修改預(yù)測(cè)位實(shí)際應(yīng)用中N位分支預(yù)測(cè)的性能和2位分支預(yù)測(cè)差不多，多數(shù)處理器只采用2位分支預(yù)測(cè)1位預(yù)測(cè)(1-bitpredictor)假設(shè)：一個(gè)循環(huán)共循環(huán)10次，它將9次分支成功，最后1次分支失敗。如果預(yù)測(cè)位始終在分支歷史表中，那么：第一次預(yù)測(cè)錯(cuò)誤（因上次最后是失?。┳詈笠淮晤A(yù)測(cè)錯(cuò)誤（因前面都是成功）對(duì)循環(huán)，1位預(yù)測(cè)將有2次錯(cuò)誤歷史：1預(yù)測(cè)：成功成功失敗成功歷史：0預(yù)測(cè)：失敗失敗2位預(yù)測(cè)(2-bitpredictor)需要預(yù)測(cè)錯(cuò)誤兩次，才會(huì)改變預(yù)測(cè)結(jié)果2位預(yù)測(cè)(另一個(gè)版本)需要預(yù)測(cè)錯(cuò)誤兩次，才會(huì)改變預(yù)測(cè)結(jié)果歷史：11預(yù)測(cè)：成功成功失敗成功歷史：10預(yù)測(cè)：成功歷史：01預(yù)測(cè)：失敗失敗失敗成功歷史：00預(yù)測(cè)：失敗成功失敗4.3.2分支目標(biāo)緩沖器分支目標(biāo)緩沖器(BTB:BranchTargetBuffer,BranchTargetCache)：將分支成功的分支指令的地址和它的分支目標(biāo)地址都存放在分支目標(biāo)緩沖區(qū)。以分支指令的地址為標(biāo)示，并在取指令階段與所有指令進(jìn)行比較。比較相同，就認(rèn)為本指令是分支指令，且認(rèn)為它轉(zhuǎn)移成功，保存在分支目標(biāo)緩沖器的分支目標(biāo)地址就是下一條指令的地址由于確認(rèn)了分支指令及其目標(biāo)地址，所以正確預(yù)測(cè)的分支，其延遲可以降為0還可以在緩沖器中存入一個(gè)或多個(gè)目標(biāo)指令分支目標(biāo)緩沖BTB的結(jié)構(gòu)BranchPCPredictedPC=?Extrapredictionstate

bitsYes:instructionisbranchandusepredictedPCasnextPCNo:branchnotpredicted,proceednormally(NextPC)PCofcurrentinstructionPentium的動(dòng)態(tài)分支預(yù)測(cè)（分支目標(biāo)緩沖器）32位32位2位轉(zhuǎn)移指令地址目標(biāo)指令地址歷史不分支歷史：11預(yù)測(cè)：分支歷史：10預(yù)測(cè)：分支分支不分支歷史：01預(yù)測(cè)：分支分支不分支歷史：00

預(yù)測(cè)：不分支分支不分支新項(xiàng)分支發(fā)生分支的移動(dòng)方向不發(fā)生分支的移動(dòng)方向PentiumII靜態(tài)分支預(yù)測(cè)解決BTB中沒(méi)有記錄的轉(zhuǎn)移指令的分支預(yù)測(cè)問(wèn)題：預(yù)測(cè)無(wú)條件轉(zhuǎn)移指令發(fā)生分支預(yù)測(cè)向后分支的條件轉(zhuǎn)移指令發(fā)生分支預(yù)測(cè)向前分支的條件轉(zhuǎn)移指令不發(fā)生分支;例1begin: …

jcbegin;向后的轉(zhuǎn)移指令，靜態(tài)預(yù)測(cè)發(fā)生分支;例2

jcbegin;向前的轉(zhuǎn)移指令，靜態(tài)預(yù)測(cè)不發(fā)生分支 …begin:

callconvert;無(wú)條件轉(zhuǎn)移指令，靜態(tài)預(yù)測(cè)發(fā)生分支4.3.3基于硬件的前瞻執(zhí)行處理器推測(cè)（推斷、前瞻Speculation）指令是否可以執(zhí)行，在未確認(rèn)之前就提前執(zhí)行（克服控制相關(guān)）。如果推測(cè)正確，就可以消除延遲；所以在大多數(shù)推測(cè)正確的前提下，可以有效地加快分支處理的速度前瞻執(zhí)行結(jié)合了三種思想：動(dòng)態(tài)分支預(yù)測(cè)決定執(zhí)行哪條指令消除控制相關(guān)前推斷執(zhí)行動(dòng)態(tài)調(diào)度不同的基本塊實(shí)質(zhì)是數(shù)據(jù)流執(zhí)行(dataflowexecution)：只要操作數(shù)有效，指令就執(zhí)行再定序緩沖區(qū)要前瞻執(zhí)行，就要將推測(cè)執(zhí)行的結(jié)果和最終結(jié)果區(qū)別開(kāi)，指令執(zhí)行后就需要附加一個(gè)階段用于確認(rèn)結(jié)果，這就是指令確認(rèn)（指令提交instructioncommit）推斷執(zhí)行的關(guān)鍵思想是允許指令亂序執(zhí)行但必須順序確認(rèn)，只有確認(rèn)后的結(jié)果才是最終的結(jié)果再定序緩沖區(qū)（ROB:ReorderBuffer）用于保存那些執(zhí)行完但未確認(rèn)的指令及其結(jié)果，同時(shí)還用于在推測(cè)執(zhí)行的指令之間傳送結(jié)果再定序緩沖區(qū)還提供額外的虛擬寄存器，替代保留站實(shí)現(xiàn)了寄存器重命名功能4.4多指令流出技術(shù)將等于1的理想CPI減小，必須實(shí)現(xiàn)一個(gè)時(shí)鐘周期流出（發(fā)射issue）多條指令超標(biāo)量(Superscalar)處理器：每個(gè)時(shí)鐘周期流出多條指令（1～8），可以采用編譯器進(jìn)行靜態(tài)調(diào)度順序執(zhí)行，也可以采用硬件動(dòng)態(tài)調(diào)度亂序執(zhí)行超長(zhǎng)指令字(VLIW:VeryLongInstructionWord)：通過(guò)編譯器調(diào)度無(wú)關(guān)的多條指令（4～16）形成一條長(zhǎng)指令，每個(gè)時(shí)鐘周期流出一條長(zhǎng)指令超級(jí)流水線(xiàn)(Superpipelining)：將每個(gè)功能部件進(jìn)一步流水化，使得一個(gè)功能部件在一個(gè)時(shí)鐘周期中可以處理多條指令（可以簡(jiǎn)單地理解為很長(zhǎng)的流水線(xiàn)）于是引入IPC(InstructionsPerCycle)描述性能多指令流出流水線(xiàn)01234567T正常流水線(xiàn)超標(biāo)量流水線(xiàn)0123456T0123456T超長(zhǎng)指令字流水線(xiàn)3個(gè)操作01234567T超級(jí)流水線(xiàn)4.4.1基于靜態(tài)調(diào)度的多流出技術(shù)編譯器基于多流出方式調(diào)度指令，指令按序流出，所有的沖突檢測(cè)都在流出時(shí)由硬件進(jìn)行檢測(cè)當(dāng)前流出的指令之間是否存在沖突當(dāng)前流出的指令與正在執(zhí)行的指令是否有沖突如果在當(dāng)前流出的指令序列中，某條指令存在沖突，就只流出該指令之前的指令Pentium的超標(biāo)量流水線(xiàn)類(lèi)似80486的5級(jí)流水線(xiàn)，后3級(jí)可以在兩個(gè)流水線(xiàn)同時(shí)進(jìn)行指令預(yù)取PF和指令譯碼D1步驟可以并行取出、譯碼2條簡(jiǎn)單指令，然后分別發(fā)向U和V流水線(xiàn)在滿(mǎn)足指令配對(duì)的條件下，Pentium可以每個(gè)時(shí)鐘周期執(zhí)行完2條指令V流水線(xiàn)U流水線(xiàn)地址生成D2地址生成D2指令預(yù)取PF指令譯碼D1執(zhí)行EX執(zhí)行EX回寫(xiě)WB回寫(xiě)WBPentium的超標(biāo)量結(jié)構(gòu)轉(zhuǎn)移指令地址寄存器V流水線(xiàn)ALUU流水線(xiàn)ALU移位器指令譯碼和配對(duì)控制單元分支目標(biāo)緩沖器V流水線(xiàn)存儲(chǔ)地址產(chǎn)生器U流水線(xiàn)存儲(chǔ)地址產(chǎn)生器隊(duì)列B隊(duì)列A指令Cache指令預(yù)取電路分支目標(biāo)地址產(chǎn)生分支地址Pentium的指令配對(duì)檢測(cè)過(guò)程（近似表達(dá)）IF i1是簡(jiǎn)單指令 并且i2也是簡(jiǎn)單指令 并且i1不是轉(zhuǎn)移指令 并且i1和i2不存在數(shù)據(jù)相關(guān)THEN i1發(fā)往U流水線(xiàn) i2發(fā)往V流水線(xiàn)ELSE i1發(fā)往U流水線(xiàn) i2做為下對(duì)指令的第1條指令i14.4.2基于動(dòng)態(tài)調(diào)度的多流出技術(shù)動(dòng)態(tài)調(diào)度可以克服指令流出所受的限制實(shí)現(xiàn)多流出的主要方法：用更短的時(shí)間完成流出步驟，這樣一個(gè)時(shí)鐘周期就能處理多條指令設(shè)置一次能同時(shí)處理多條指令的邏輯電路PentiumIII的動(dòng)態(tài)執(zhí)行結(jié)構(gòu)取指取數(shù)順序發(fā)送前端(取指與譯碼單元)讀取指令譯碼指令為微代碼處理指令分支亂序執(zhí)行核心(分派與執(zhí)行單元)調(diào)度和執(zhí)行微代碼包含5個(gè)執(zhí)行端口順序退出單元(退出單元)順序退出指令寫(xiě)入寄存器和存儲(chǔ)器結(jié)果L1指令CacheL1數(shù)據(jù)Cache存數(shù)總線(xiàn)接口單元L2Cache系統(tǒng)總線(xiàn)重排序緩沖區(qū)ROB(指令池)等待執(zhí)行的微代碼緩沖區(qū)PentiumIII的流水線(xiàn)14clocksintotal(~3statemachines)8stagesareusedforin-orderinstructionfetch,decode,andissueTakes1clockcycletodeterminelengthof80x86instructions+2moretocreatethemicro-operations(uops)3stagesareusedforout-of-orderexecutioninoneof5separatefunctionalunits3stagesareusedforinstructioncommitInstr

Fetch

16B

/clkInstr

Decode

3Instr

/clkRenaming

3uops

/clkExecu-

tion

units

(5)Gradu-

ation3uops

/clk16B6uopsReserv.

StationReorder

BufferPentiumIII的微結(jié)構(gòu)4.4.3超長(zhǎng)指令字技術(shù)依靠編譯器在編譯時(shí)找出指令之間潛在的并行性，并通過(guò)指令調(diào)度把可能出現(xiàn)的數(shù)據(jù)沖突減少到最小，最后把能并行執(zhí)行的多條指令組裝成一條很長(zhǎng)的指令。這種指令字經(jīng)常是100到幾百位控制硬件比較簡(jiǎn)單超標(biāo)量處理機(jī)較超長(zhǎng)指令字處理機(jī)的優(yōu)點(diǎn)超標(biāo)量結(jié)構(gòu)對(duì)程序員透明沒(méi)有經(jīng)過(guò)編譯器優(yōu)化調(diào)度的代碼仍然可以運(yùn)行4.4.4多流出處理器受到的限制程序內(nèi)在的指令級(jí)并行性最簡(jiǎn)單、最根本的因素超標(biāo)量處理器硬件實(shí)現(xiàn)的限制動(dòng)態(tài)調(diào)度的超標(biāo)量結(jié)構(gòu)需要大量的硬件資源并且設(shè)計(jì)復(fù)雜、實(shí)現(xiàn)困難超長(zhǎng)指令字處理器固有的技術(shù)限制程序代碼長(zhǎng)度增加鎖步機(jī)制導(dǎo)致同步限制機(jī)器代碼的不兼容性顯式并行指令計(jì)算EPICEPIC(ExplicitlyParallelInstructionComputing) 結(jié)合VLIW和Superscalar的特點(diǎn)，軟硬件相互協(xié)作，提高指令級(jí)并行處理能力設(shè)計(jì)理念：在編譯期間設(shè)計(jì)需要的執(zhí)行計(jì)劃編譯器選擇運(yùn)行期間才能確定的信息，構(gòu)造和優(yōu)化執(zhí)行計(jì)劃將執(zhí)行計(jì)劃有效地傳遞給硬件IA-64(IntelArchitecture-64) Intel-HP合作開(kāi)發(fā)的、基于EPIC的64位微處理器體系結(jié)構(gòu)。HP更愿意稱(chēng)其為安騰處理器系列結(jié)構(gòu)IPF(ItaniumProcessorFamilyArchitecture)IA-64的主要特點(diǎn)顯式并行性編譯器與處理器間的協(xié)作機(jī)制利用指令級(jí)并行度的大量資源128個(gè)整數(shù)寄存器、128個(gè)浮點(diǎn)寄存器、64個(gè)一位判定寄存器、8個(gè)分支寄存器和大量應(yīng)用寄存器對(duì)多個(gè)執(zhí)行部件和存儲(chǔ)端口的支持增強(qiáng)的指令級(jí)并行推測(cè)執(zhí)行（用以減少存儲(chǔ)器時(shí)延的影響）判定執(zhí)行（用以消除分支）低開(kāi)銷(xiāo)的循環(huán)軟件流水線(xiàn)操作分支預(yù)測(cè)減少分支損耗改善軟件性能對(duì)軟件模塊的專(zhuān)門(mén)支持高性能浮點(diǎn)結(jié)構(gòu)特殊多媒體指令I(lǐng)A-64指令編碼格式128位，3個(gè)指令捆綁而成一個(gè)指令束(Bundle)每個(gè)指令為41位，稱(chēng)為指令槽(Slot)另外，有5位模板域(Template)模板顯式指明并行性程序中以指令組(Group)實(shí)現(xiàn)并行語(yǔ)義IA-64的分支判定(Predication)允許編譯程序同時(shí)執(zhí)行來(lái)自多個(gè)條件分支的指令，進(jìn)而消除錯(cuò)誤分支產(chǎn)生的延遲程序中顯式指明判定標(biāo)記，硬件利用64個(gè)判定寄存器IA-64的數(shù)據(jù)推測(cè)(DataSpeculation)允許編譯程序?qū)?shù)據(jù)讀取（Load）提到一個(gè)或多個(gè)數(shù)據(jù)存儲(chǔ)（Store）之前，即使編譯程序無(wú)法確定數(shù)據(jù)讀取和存儲(chǔ)是否為同一個(gè)存儲(chǔ)器地址單元硬件配合先行讀取地址表ALATIA-64的控制推測(cè)(ControlSpeculation)將存儲(chǔ)器操作數(shù)讀取提到分支之前，并可以延緩異常的處理硬件配合通用寄存器的附加位NaT和NaTVal軟件流水線(xiàn)(SoftwarePipelining)一種重疊執(zhí)行循環(huán)體的軟件方法，用以提高循環(huán)程序的并行性O(shè)bservation:ifiterationsfromloopsareindependent,thencangetmoreILPbytakinginstructionsfromdifferentiterationsSoftwarepipelining:reorganizesloopssothateachiterationismadefrominstructionschosenfromdifferentiterationsoftheoriginalloop把不同循環(huán)體間的指令交織在一起形成循環(huán)IA-64的軟件流水線(xiàn)硬件配合循環(huán)記數(shù)寄存器LC和后序記數(shù)寄存器EC、特殊的分支指令和寄存器循環(huán) movlc=199 //LC＝循環(huán)次數(shù)－1 movec=4 //EC＝后序階段＋1 movpr.rot=1<<16 ;; //設(shè)置p16＝1，其他判定寄存器＝0L1:(p16) ld4r32=[r5],4(p18) addr35=r34,r9(p19) st4[r6]=r36,4 br.ctopL1 ;;安騰處理器結(jié)構(gòu)圖4.5循環(huán)展開(kāi)和指令調(diào)度在程序的一個(gè)基本塊（除入口和出口外沒(méi)有其他分支的順序指令序列）中可以利用的并行性通常是很小的為了能夠獲得更多的性能提高，就必須開(kāi)發(fā)多個(gè)基本塊之間的指令級(jí)并行常見(jiàn)的基本塊是循環(huán)體一次循環(huán)體內(nèi)的指令間并行性很小，但在多次循環(huán)體的指令間卻往往存在并行性（循環(huán)級(jí)并行性）循環(huán)展開(kāi)（loopunrolling）展開(kāi)循環(huán)體若干次，通過(guò)換名和指令調(diào)度，將循環(huán)級(jí)并行性轉(zhuǎn)化為指令級(jí)并行指令調(diào)度受限于兩個(gè)特性：程序固有的指令級(jí)并行性流水線(xiàn)功能部件的執(zhí)行延遲（表4.3，p146）循環(huán)實(shí)例分析C/C++語(yǔ)言：for(i=1000;i>0;i=i-1) x[i]=x[i]+s;MIPS64匯編語(yǔ)言：;assumeR1=addressofx[i],F2=s,R2=0loop: L.DF0,0(R1) ;loadF0=x[i] ADD.DF4,F0,F2 ;sumF4=x[i]+s S.DF4,0(R1) ;storeF4=x[i]+s DADDUIR1,R1,#-8 ;R1=R1-8 BNER1,R2,loop ;ifR1!=R2,repeat執(zhí)行延遲浮點(diǎn)流水線(xiàn)的執(zhí)行延遲產(chǎn)生結(jié)果的指令使用結(jié)果的指令延遲的時(shí)鐘周期浮點(diǎn)ALU操作浮點(diǎn)ALU操作3浮點(diǎn)ALU操作浮點(diǎn)STORE操作2浮點(diǎn)LOAD操作浮點(diǎn)ALU操作1浮點(diǎn)LOAD操作浮點(diǎn)STORE操作0RETURN未經(jīng)指令調(diào)度的循環(huán)程序執(zhí)行情況 ;Clockcycleissuedloop: L.DF0,0(R1) ;1

stall ;2 ADD.DF4,F0,F2 ;3

stall ;4

stall ;5 S.DF4,0(R1) ;6 DADDUIR1,R1,#-8 ;7

stall ;8(RAW) BNER1,R2,loop ;9

stall ;10(branchdelay)執(zhí)行延遲每個(gè)循環(huán)體需要10個(gè)時(shí)鐘周期指令調(diào)度后的循環(huán)程序執(zhí)行情況 ;Clockcycleissuedloop: L.DF0,0(R1) ;1 DADDUIR1,R1,#-8 ;2 ADD.DF4,F0,F2 ;3

stall ;4 BNER1,R2,loop ;5

S.DF4,8(R1) ;6

(delayedbranch)執(zhí)行延遲每個(gè)循環(huán)體需要6個(gè)時(shí)鐘周期。但循環(huán)體針對(duì)數(shù)組的實(shí)際操作只用3個(gè)時(shí)鐘周期；循環(huán)開(kāi)銷(xiāo)是3個(gè)時(shí)鐘周期循環(huán)展開(kāi)（未優(yōu)化）loop: L.DF0,0(R1) ;firstcopyofloopbody ADD.DF4,F0,F2 S.DF4,0(R1) L.DF0,-8(R1) ;secondcopy ADD.DF4,F0,F2 S.DF4,-8(R1) L.DF0,-16(R1) ;thirdcopy ADD.DF4,F0,F2 S.DF4,-16(R1) L.DF0,-24(R1) ;fourthcopy ADD.DF4,F0,F2 S.DF4,-24(R1) DADDUIR1,R1,-32 BNER1,R2,loop藍(lán)色箭頭表示數(shù)據(jù)相關(guān)紅色箭頭表示名相關(guān)名相關(guān)使得指令幾乎無(wú)法調(diào)度，采用重命名消除循環(huán)展開(kāi)（重命名、未調(diào)度）loop: L.DF0,0(R1) ;1st ADD.DF4,F0,F2 S.DF4,0(R1) L.DF6,-8(R1) ;2nd ADD.DF8,F6,F2 S.DF8,-8(R1) L.DF10,-16(R1) ;3rd ADD.DF12,F10,F2 S.DF12,-16(R1) L.DF14,-24(R1) ;4th ADD.DF16,F14,F2 S.DF16,-24(R1) DADDUIR1,R1,-32 BNER1,R2,loop藍(lán)色箭頭表示數(shù)據(jù)相關(guān)共28個(gè)時(shí)鐘周期，每個(gè)循環(huán)體平均7個(gè)時(shí)鐘周期（＝28/4）循環(huán)展開(kāi)（重命名、調(diào)度后）loop: L.DF0,0(R1) L.DF6,-8(R1) L.DF10,-16(R1) L.DF14,-24(R1) ADD.DF4,F0,F2 ADD.D