計算機組成與體系結(jié)構(gòu) 課件 11指令流水線、12并行計算系統(tǒng)

指令流水線計算機組成與體系結(jié)構(gòu)如何提高計算機的性能器件的進步摩爾定律體系結(jié)構(gòu)面積換性能（TradeAreaforPerformance）空間換時間（TradeSpaceforTiming）實現(xiàn)方式時間重疊空間重疊時間重疊+空間重疊流水線（Pipeline）為什么工業(yè)化生產(chǎn)采用流水線？在CPU中，一種指令的執(zhí)行方式時間重疊方式狀態(tài)機→流水線指令的幾種執(zhí)行方式T=3ntT=(1+2n)tT=(2+n)t每個執(zhí)行步驟時間為

t，則執(zhí)行

n

條指令的用時

T

為:流水線時空圖表示法流水線的特點把一個任務(wù)（一條指令或一個操作）分解為幾個有聯(lián)系的子任務(wù)，每個子任務(wù)由一個專門的功能部件來實現(xiàn)流水線每一個功能段部件后面都要設(shè)置緩沖寄存器，或稱為鎖存器，其作用是保存本流水段的結(jié)果流水線的特點流水線中各功能段的時間應(yīng)盡量相等，否則將引起堵塞、斷流，要求流水線的時鐘周期不能快于最慢的流水段只有連續(xù)不斷地提供同一種任務(wù)時才能發(fā)揮流水線的效率，所以在流水線中處理的必須是連續(xù)任務(wù)流水線需要有裝入時間和排空時間裝入時間是指第一個任務(wù)進入流水線到輸出流水線的時間排空時間是指第n個（最后一個）任務(wù)進入流水線到輸出流水線的時間流水線的分類（一）部件功能級流水線運算操作流水線（ArithmeticPipelines）。浮點加法器就是一種典型的功能部件級流水線。處理機級流水線指令流水線（InstructionPipelines），它是把執(zhí)行指令的過程按照流水方式處理，使處理機能夠重疊地秩序多條指令。處理機間級流水線宏流水線（MacroPipelines）。這種流水線由兩個或者兩個以上的處理機通過存儲器串行連接起來，每個處理機完成整個任務(wù)的一部分。流水線的分類（二）單功能流水線只能完成一種固定的功能多功能流水線流水線各段可以進行不同的連接流水線的分類（三）靜態(tài)流水線在同一段時間內(nèi)，各功能段只能夠按照一種固定方式連接，實現(xiàn)一種固定功能。動態(tài)流水線在同一段時間內(nèi)，多功能流水線中的各段可以按照不同的方式連接，同時執(zhí)行多種功能。流水線的分類（四）線性流水線LinearPipelines非線性流水線處理機級流水線NonlinearPipelines流水線的性能指標(biāo)吞吐率（ThroughputRate）加速比（SpeedupRatio）效率（Efficiency）最佳段數(shù)流水線的吞吐率ThroughputRate衡量流水線速度的重要指標(biāo)指在單位時間內(nèi)流水線所完成的任務(wù)數(shù)量吞吐率的計算流水線的實際吞吐率為：當(dāng)連續(xù)輸入的任務(wù)n→∞時，得最大吞吐率為：最大吞吐率與實際吞吐率的關(guān)系是：流水線的吞吐率流水線的加速比SpeedupRatio完成同樣一批任務(wù)，不使用流水線所用的時間與使用流水線所用的時間之比稱為流水線的加速比加速比的計算如果流水線各段執(zhí)行時間都相等，則一條k段流水線完成n個連續(xù)任務(wù)實際加速比為：上述情況下的最大加速比為：流水線的加速比流水線的效率Efficiency流水線設(shè)備利用率稱為流水線的效率效率的計算如果流水線的各段執(zhí)行時間均相等，而且輸入的n個任務(wù)是連續(xù)的，則一條k段流水線的效率為：在流水線的各段執(zhí)行時間均相等，輸入到流水線的任務(wù)是連續(xù)的情況下，流水線的最高效率為：流水線的效率流水線的最佳段數(shù)選擇增加流水線段數(shù)時，流水線的吞吐率和加速比都能提高但是每一流水段輸出端必須設(shè)置一個鎖存器，當(dāng)流水段數(shù)增多時，鎖存器的總延遲時間也將增加，且流水線的價格也會增加要綜合考慮各方面的因素，選擇流水線最佳段數(shù)EXETIME

=#Insts×

CPI×cycletime硬件成本能耗一般處理機中的流水線段數(shù)在3到12之間，極少有超過15段的流水線一般把8段或超過8段的流水線稱為超流水線，采用8段以上流水線的處理機有時也稱為超流水線處理機流水線練習(xí)有一條靜態(tài)多功能流水線由5段組成，加法用1、3、4、5段，乘法用1、2、5段，第3段的時間為2△t，其余各段的時間均為△t，而且流水線的輸出可以直接返回輸入端或暫存于相應(yīng)的流水寄存器中?，F(xiàn)要在該流水線上計算，畫出其時空圖，并計算其吞吐率、加速比和效率。時空圖結(jié)果如果不用流水線，由于一次求積需3△t，一次求和需5△t，則產(chǎn)生上述7個結(jié)果共需（4×5+3×3）△t=29△t。所以加速比為：18個△t時間中，給出了7個結(jié)果，吞吐率為：效率可由陰影區(qū)的面積和5個段總時空區(qū)的面積的比值求得：時空圖-動態(tài)流水線122334441123154321243abababccc17時空圖-拆分段13234341241543-23-121abababccc11242343214時空圖-資源重復(fù)1223344411231543213abababccc1424流水線中的相關(guān)問題結(jié)構(gòu)相關(guān)，是指在指令重疊執(zhí)行的過程中，遇到了因硬件資源不足而不能正常流水的沖突數(shù)據(jù)相關(guān)，是指在同時重疊執(zhí)行的幾條指令中，遇到了后續(xù)指令用到前面指令的執(zhí)行結(jié)果，但前面指令尚不能提供的沖突控制相關(guān)，它是指流水線中的分支指令或者其他需要改寫PC的指令時，遇到了不能及時確定應(yīng)該取哪一條指令的矛盾經(jīng)典的5段流水線結(jié)構(gòu)相關(guān)解決方案一時空圖解決方案二設(shè)置相互獨立的存儲器哈佛結(jié)構(gòu)指令存儲器數(shù)據(jù)存儲器分立Cache指令Cache數(shù)據(jù)Cache數(shù)據(jù)相關(guān)采用定向（旁路）技術(shù)無法定向的情況流水線互鎖編譯器調(diào)度方法例如對于最常見的A＝B＋C這樣的操作形式，采用比較典型的代碼生成方法可以得到如下的指令序列：

LWR1,BLWR2,CADDR3,R1,R2SWA,R3編譯器調(diào)度方法處理數(shù)據(jù)相關(guān)編譯器是如何通過指令調(diào)度來消除流水線暫停的呢？例如有下面連續(xù)的兩個操作：a＝b＋c；d＝e－f；指令調(diào)度前后代碼對比（左：調(diào)度前，右：調(diào)度后）LWRb，bLWRc，cADDRa，Rb，RcSWa，RaLWRe，eLWRf，fSUBRd，Re，RfSWd，RdLWRb，bLWRc，cLWRe，e；交換指令,消除ADD指令暫停ADDRa，Rb，RcLWRf，fSWa，Ra；交換指令,消除SUB指令暫停SUBRd，Re，RfSWd，Rd控制相關(guān)控制相關(guān)是因程序執(zhí)行轉(zhuǎn)移類指令而引起的相關(guān)控制相關(guān)會使流水線的連續(xù)流動受到破壞會引起程序執(zhí)行段落的改變，使流水線損失更多的性能，所以稱為全局相關(guān)控制相關(guān)的解決方法凍結(jié)或者排空流水線的方法(Flush)最簡單的處理方式分支延遲（延遲轉(zhuǎn)移）的方法分支預(yù)測的方法猜測條件表達式兩路分支中哪一路最可能發(fā)生，然后推測執(zhí)行這一路的指令，來避免流水線停頓造成的時間浪費并行計算系統(tǒng)計算機組成與體系結(jié)構(gòu)內(nèi)容提要Flynn分類法并行計算技術(shù)指令級并行指令多發(fā)射并發(fā)與并行超線程技術(shù)多核技術(shù)Flynn'sTaxonomy

1972年費林（MichaelJ.Flynn）單指令流單數(shù)據(jù)流SingleInstruction,SingleData,SISD單指令流多數(shù)據(jù)流SingleInstruction,MultipleData,SIMD多指令流單數(shù)據(jù)流MultipleInstruction,SingleData,MISD多指令流多數(shù)據(jù)流MultipleInstruction,MultipleData,MIMDSISDSIMDMIMD不同層面的并行計算技術(shù)指令級并行線程級并行進程級并行并行對象指令序列多個線程多個進程主要技術(shù)亂序發(fā)射超線程/多核處理器多處理機系統(tǒng)實施者硬件程序員程序員指令級并行指令級并行技術(shù)指令級并行度ILPInstructionLevelParallelism是指在一個時鐘周期內(nèi)流水線上流出的指令條數(shù)CPI（ClockCyclesPerInstruction）目標(biāo)：使CPI＜1主要方法：亂序執(zhí)行，指令調(diào)度指令調(diào)度靜態(tài)調(diào)度依靠編譯器對代碼進行靜態(tài)調(diào)度，以減少相關(guān)和沖突它不是在程序執(zhí)行的過程中、而是在編譯期間進行代碼調(diào)度和優(yōu)化通過把相關(guān)的指令拉開距離來減少可能產(chǎn)生的停頓動態(tài)調(diào)度在程序的執(zhí)行過程中，依靠專門硬件對代碼進行調(diào)度，減少數(shù)據(jù)相關(guān)導(dǎo)致的停頓動態(tài)指令調(diào)度優(yōu)點能夠處理一些在編譯時情況不明的相關(guān)（比如涉及到存儲器訪問的相關(guān)），并簡化了編譯器能夠使本來是面向某一流水線優(yōu)化編譯的代碼在其他的流水線（動態(tài)調(diào)度）上也能高效地執(zhí)行以硬件復(fù)雜性的顯著增加為代價典型算法CDC記分牌法Tomasulo令牌法指令調(diào)度中的數(shù)據(jù)依賴RAWReadAfterWrite，假設(shè)指令j是在指令i后面執(zhí)行的指令，RAW表示指令i將數(shù)據(jù)寫入寄存器后，指令j才能從這個寄存器讀取數(shù)據(jù)。如果指令j在指令i寫入寄存器前嘗試讀出該寄存器的內(nèi)容，將得到不正確的數(shù)據(jù)WARWriteAfterRead，假設(shè)指令j是在指令i后面執(zhí)行的指令，WAR表示指令i讀出數(shù)據(jù)后，指令j才能寫這個寄存器。如果指令j在指令i讀出數(shù)據(jù)前就寫該寄存器，將使得指令i讀出的數(shù)據(jù)不正確WAWWriteAfterWrite，假設(shè)指令j是在指令i后面執(zhí)行的指令，WAW表示指令i將數(shù)據(jù)寫入寄存器后，指令j才能將數(shù)據(jù)寫入這個寄存器。如果指令j在指令i之前寫該寄存器，將使得該寄存器的值不是最新值動態(tài)指令調(diào)度示例DIV.D F4，F(xiàn)0，F(xiàn)2SUB.D F10，F(xiàn)4，F(xiàn)6ADD.D F12，F(xiàn)6，F(xiàn)14SUB.D指令與DIV.D指令關(guān)于F4相關(guān)，導(dǎo)致流水線停頓。ADD.D指令與流水線中的任何指令都沒有關(guān)系，但也因此受阻。在前述5段流水線中，是不會發(fā)生WAR沖突和WAW沖突的。但亂序執(zhí)行就使得它們可能發(fā)生了。

DIV.D F10,F0,F2SUB.D F10,F4,F6ADD.D F6,F8,F14存在反相關(guān)存在輸出相關(guān)CDC記分牌法在資源充足時，盡可能早地執(zhí)行沒有數(shù)據(jù)阻塞的指令，達到每個時鐘周期執(zhí)行一條指令如果某條指令被暫停，而后面的指令與流水線中正在執(zhí)行的或被暫停的指令不相關(guān)，那么這條指令可以繼續(xù)流出并執(zhí)行下去記分牌電路負(fù)責(zé)記錄資源的使用，并負(fù)責(zé)相關(guān)檢測，控制指令的流出和執(zhí)行記分牌指令狀態(tài)表：它登記已取指到指令流水線的各條指令的狀態(tài)：是否已完成發(fā)射、是否已取完操作數(shù)、是否已完成執(zhí)行、是否已完成寫回功能部件狀態(tài)表：每一個功能部件占有一個表項，登記是否“忙”、目的寄存器名、源寄存器名等是否就緒目標(biāo)寄存器表：每一個寄存器與預(yù)約使用它作為目標(biāo)寄存器的功能部件相聯(lián)系，1個寄存器只能作為1個功能部件而不能同時作為兩個功能部件的目標(biāo)寄存器定向邏輯指令發(fā)射條件一條譯碼后的指令若它所需的功能部件可用，并且目標(biāo)寄存器也不是其他功能部件已預(yù)約的目標(biāo)寄存器，那么這條指令就可發(fā)射，否則等待直到條件滿足再發(fā)射，這樣首先杜絕了WAW相關(guān)在取寄存器操作數(shù)時要判測是否有WAR相關(guān)若先前發(fā)射出的指令以某寄存器為目標(biāo)寄存器，則只有該指令向目標(biāo)寄存器寫入后（目標(biāo)寄存器表中此項清除），此寄存器才作為其他指令的源寄存器就緒，從而消除WAR相關(guān)在寫回(W)段要判測是否有RAW相關(guān)先前發(fā)射出的指令若以本指令預(yù)定的目標(biāo)寄存器為源寄存器，而還沒有讀取的話，則本指令的寫回操作要推遲，直到RW相關(guān)清除再寫回CDC記分牌法(A×B)＋(C+D)I1LOADR1,M(A)I2LOADR2,M(B)I3MULR5,R1,R2I4LOADR3,M(C)I5LOADR4,M(D)I6ADDR2,R3,R4I7ADDR2,R2,R5按序發(fā)射但不按序完成Tomasulo算法核心思想記錄和檢測指令相關(guān)，操作數(shù)一旦就緒就立即執(zhí)行，把發(fā)生RAW沖突的可能性減少到最小通過寄存器換名來消除WAR沖突和WAW沖突只要操作數(shù)有效，就將其取到保留站，避免指令流出時才到寄存器中取數(shù)據(jù)，這就使得即將執(zhí)行的指令從相應(yīng)的保留站中取得操作數(shù)，而不是從寄存器中指令的執(zhí)行結(jié)果也是直接送到等待數(shù)據(jù)的其它保留站中去基于Tomasulo算法的MIPS處理器浮點部件的基本結(jié)構(gòu)保留站reservationstation每個保留站中保存一條已經(jīng)流出并等待到本功能部件執(zhí)行的指令（相關(guān)信息）。包括：操作碼、操作數(shù)以及用于檢測和解決沖突的信息浮點加法器有3個保留站：ADD1，ADD2，ADD3浮點乘法器有兩個保留站：MULT1，MULT2每個保留站都有一個標(biāo)識字段，唯一地標(biāo)識了該保留站保留站Op：要對源操作數(shù)進行的操作。Qj，Qk：將產(chǎn)生源操作數(shù)的保留站號。等于0表示操作數(shù)已經(jīng)就緒且在Vj或Vk中，或者不需要操作數(shù)。Vj，Vk：源操作數(shù)的值。對于每一個操作數(shù)來說，V或Q字段只有一個有效。對于load來說，Vk字段用于保存偏移量。Busy：為“yes”表示本保留站或緩沖單元“忙”。A：僅load和store緩沖器有該字段。開始是存放指令中的立即數(shù)字段，地址計算后存放有效地址。Qi：寄存器狀態(tài)表每個寄存器在該表中有對應(yīng)的一項，用于存放將把結(jié)果寫入該寄存器的保留站的站號為0表示當(dāng)前沒有正在執(zhí)行的指令要寫入該寄存器，也即該寄存器中的內(nèi)容就緒公共數(shù)據(jù)總線CDB所有功能部件的計算結(jié)果都是送到CDB上，由它把這些結(jié)果直接送到（播送到）各個需要該結(jié)果的地方在具有多個執(zhí)行部件且采用多流出（即每個時鐘周期流出多條指令）的流水線中，需要采用多條CDBload緩沖器和store緩沖器load緩沖器存放用于計算有效地址的分量記錄正在進行的load訪存，等待存儲器的響應(yīng)保存已經(jīng)完成了的load的結(jié)果（即從存儲器取來的數(shù)據(jù)），等待CDB傳輸store緩沖器存放用于計算有效地址的分量保存正在進行的store訪存的目標(biāo)地址，該store正在等待存儲數(shù)據(jù)的到達保存該store的地址和數(shù)據(jù)，直到存儲部件接收示例指

令

指令狀態(tài)表

流出

執(zhí)行

寫結(jié)果

L.D F6,34(R2)√√√L.D F2,45(R3)√√MUL.D F0,F2,F4√SUB.D F8,F6,F2√DIV.D F10,F0,F6√ADD.D F6,F8,F2√

名稱

保留站

Load1Load2Add1Add2Add3Mult1Mult2BusynoyesyesyesnoyesyesOp

LDSUBADD

MULDIVVj

Vk

Mem[34+Regs[R2]]

Reg[F4]Mem[34+Regs[R2]]Qj

Load2Add1

Load2Mult1Qk

Load2A

45+Regs[R3]

寄存器狀態(tài)表

F0F2F4F6F8F10…F30QiMult1

Load2Add2Add1Mult2…多指令發(fā)射技術(shù)超標(biāo)量(Superscalar)處理機超流水線(Superpipelining)處理機超標(biāo)量超流水線(SuperscalarSuperpipeling)處理機超長指令字(VeryLongInstructionWord)處理機超標(biāo)量處理機亂序發(fā)射-指令的調(diào)度順序發(fā)射順序完成順序發(fā)射亂序完成亂序發(fā)射亂序完成亂序發(fā)射順序完成超流水線處理機分時發(fā)射多條指令超標(biāo)量超流水線處理機執(zhí)行時間加速比單流水線處理機超標(biāo)量處理機超流水線處理機超標(biāo)量超流水線處理機性能計算

性能計算現(xiàn)有12個任務(wù)需要進入流水線，流水線的功能段都為4個，流經(jīng)每個功能段的時間相同，設(shè)為Δt?，F(xiàn)在計算再下列情況下完成12個任務(wù)分別需要多少時間？（1） 單發(fā)射基準(zhǔn)流水線。（2） 超標(biāo)量流水線，每個時鐘周期可以發(fā)射三條指令。（3） 超流水線，每個時鐘周期可以分時發(fā)射三次，每次可以發(fā)射3條指令。T(1,1)=(4+12-1)Δt=15Δt

超長指令字（VLIW）處理機由編譯程序在編譯時找出指令間潛在的并行性，進行適當(dāng)調(diào)度安排，把多個能并行執(zhí)行的操作組合在一起，成為一條具有多個操作段的超長指令。由這條超長指令去控制VLIW處理機中多個互相獨立工作的功能部件，每個操作段控制一個功能部件，相當(dāng)于同時執(zhí)行多條指令。VLIW處理機的主要特點超長指令字的生成是由編譯器來完成的，由它將串行的操作序列合并為可并行執(zhí)行的指令序列，以最大限度實現(xiàn)操作并行性單一的控制流，只有一個控制器，每個時鐘周期啟動一條長指令超長指令字被分成多個控制字段，每個字段直接獨立地控制每個功能部件含有大量的數(shù)據(jù)通路和功能部件。由于編譯器在編譯時間已解決可能出現(xiàn)的數(shù)據(jù)相關(guān)和資源沖突，故控制硬件比較簡單VLIW處理機的結(jié)構(gòu)模型FMULFADDLD/ST2LD/ST1VLIW中的操作字段浮點乘浮點加存/取2存/取1FMULFADDLD/ST2LD/ST1寄存器堆RF主存儲器線程級并行進程與線程Thread0(ProgramCounter,Registers,etc.)AddressSpaceFileDescriptorsOtherDataAprocesshasthemainthreadthatinitializestheprocessandbeginsexecutingtheinstructions.2xSingleThreadRunningWithinaProgramProcessMultithreadedProgram2xThread0(ProgramCounter,Registers,etc.)AddressSpaceFileDescriptorsOtherDataThread1(ProgramCounter,Registers,etc.)CodesegmentDatasegmentStackStackStackthreadmain()…threadthreadProcessesandThreadsModernoperatingsystemsloadprogramsasprocessesResourceholderExecutionAprocessstartsexecutingatitsentrypointasathreadThreadscancreateotherthreadswithintheprocessEachthreadgetsitsownstackAllthreadswithinaprocesssharecode&datasegments線程CPU執(zhí)行內(nèi)核(executioncore)programcounterprogramcounterCopyofCPUregistersregistersasequenceofinstructionsALU進程計算機Addressspace,data,memorymanagementinformationmemoryFileDescriptorsdiskProgramcounter,Code,processstate,valuesofCPUregistersCPU進程與線程進程：OS進行計算機資源分配的單位一個進程可以理解成：OS為用戶創(chuàng)建的、一個邏輯的計算機資源包括：內(nèi)存，顯卡，磁盤……線程：OS進行CPU資源調(diào)度的單位一個線程可以理解成：進程內(nèi)順序執(zhí)行的一個指令序列只涉及CPU資源線程之間共享進程的資源為什么要多線程(multithreading)？減少程序的響應(yīng)時間與進程相比，線程的創(chuàng)建和切換開銷更小資源共享和通信更方便簡化程序的結(jié)構(gòu)并發(fā)與并行并發(fā)(concurrency)幾件事情都在解決過程中，不是等到一件事情解決之后再解決另一件事情事情A和B都使用同一個資源（例如CPUexecutioncore），也使用不同的資源（內(nèi)存單元）A和B各使用cache中的一半頁面在把A需要的數(shù)據(jù)交換到cache時，可以用CPUexecutioncore處理B的一部分?jǐn)?shù)據(jù)（已在cache中）通過并發(fā)，提高了公用資源的利用率：如何合理安排對共用資源的使用成為關(guān)鍵并發(fā)與并行并行(parallelism)同時解決幾件事情，每件事情分別由不同的實體（人、計算機等）解決事情A和B分別使用不同的資源：A和B是兩個獨立的子問題A使用計算機1解決B使用計算機2解決通過并行，縮短了整個問題的解決周期，尋找到無關(guān)的子問題成為關(guān)鍵線程并行現(xiàn)實世界本質(zhì)上是并發(fā)的并行是并發(fā)的一種特例：并發(fā)的事件之間，沒有公用的資源并發(fā)的問題可以轉(zhuǎn)換成并行的問題系統(tǒng)資源引起的并發(fā)：增加系統(tǒng)資源，如Multi-core代替Hyper-Threading，SMP代替UP，Cluster代替server，……應(yīng)用領(lǐng)域資源引起的并發(fā)：改變算法如何實現(xiàn)線程并行？執(zhí)行內(nèi)核寄存器Cache線程間共享的資源主存空間文件句柄其他I/O超線程與多核超線程(Hyper-Threading)：支持將一個執(zhí)行內(nèi)核模擬成多個邏輯處理器（并發(fā)）每個邏輯處理器上運行一個線程邏輯處理器之間分享執(zhí)行內(nèi)核多核(Multi-core)：為進程的運行提供多個執(zhí)行內(nèi)核（并行）無關(guān)的線程在不同的執(zhí)行內(nèi)核上并行執(zhí)行執(zhí)行內(nèi)核之間共享FSB、cache超線程Hyper-Threading,HT英特爾研發(fā)的一種技術(shù)，于2002年發(fā)布。超線程技術(shù)原先只應(yīng)用于Xeon處理器中，當(dāng)時稱為Super-Threading。之后陸續(xù)應(yīng)用在Pentium4HT中通過此技術(shù)，英特爾實現(xiàn)在一個實體CPU中，提供兩個邏輯線程超線程技術(shù)充分利用空閑CPU資源，在相同時間內(nèi)完成更多工作雖然采用超線程技術(shù)能夠同時執(zhí)行兩個線程，當(dāng)