計(jì)算機(jī)組成與體系結(jié)構(gòu) 課件 12并行計(jì)算系統(tǒng)

并行計(jì)算系統(tǒng)計(jì)算機(jī)組成與體系結(jié)構(gòu)內(nèi)容提要Flynn分類法并行計(jì)算技術(shù)指令級(jí)并行指令多發(fā)射并發(fā)與并行超線程技術(shù)多核技術(shù)Flynn'sTaxonomy

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

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

令

指令狀態(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)處理機(jī)超流水線(Superpipelining)處理機(jī)超標(biāo)量超流水線(SuperscalarSuperpipeling)處理機(jī)超長指令字(VeryLongInstructionWord)處理機(jī)超標(biāo)量處理機(jī)亂序發(fā)射-指令的調(diào)度順序發(fā)射順序完成順序發(fā)射亂序完成亂序發(fā)射亂序完成亂序發(fā)射順序完成超流水線處理機(jī)分時(shí)發(fā)射多條指令超標(biāo)量超流水線處理機(jī)執(zhí)行時(shí)間加速比單流水線處理機(jī)超標(biāo)量處理機(jī)超流水線處理機(jī)超標(biāo)量超流水線處理機(jī)性能計(jì)算

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

超長指令字（VLIW）處理機(jī)由編譯程序在編譯時(shí)找出指令間潛在的并行性，進(jìn)行適當(dāng)調(diào)度安排，把多個(gè)能并行執(zhí)行的操作組合在一起，成為一條具有多個(gè)操作段的超長指令。由這條超長指令去控制VLIW處理機(jī)中多個(gè)互相獨(dú)立工作的功能部件，每個(gè)操作段控制一個(gè)功能部件，相當(dāng)于同時(shí)執(zhí)行多條指令。VLIW處理機(jī)的主要特點(diǎn)超長指令字的生成是由編譯器來完成的，由它將串行的操作序列合并為可并行執(zhí)行的指令序列，以最大限度實(shí)現(xiàn)操作并行性單一的控制流，只有一個(gè)控制器，每個(gè)時(shí)鐘周期啟動(dòng)一條長指令超長指令字被分成多個(gè)控制字段，每個(gè)字段直接獨(dú)立地控制每個(gè)功能部件含有大量的數(shù)據(jù)通路和功能部件。由于編譯器在編譯時(shí)間已解決可能出現(xiàn)的數(shù)據(jù)相關(guān)和資源沖突，故控制硬件比較簡單VLIW處理機(jī)的結(jié)構(gòu)模型FMULFADDLD/ST2LD/ST1VLIW中的操作字段浮點(diǎn)乘浮點(diǎn)加存/取2存/取1FMULFADDLD/ST2LD/ST1寄存器堆RF主存儲(chǔ)器線程級(jí)并行進(jìn)程與線程Thread0(ProgramCounter,Registers,etc.)AddressSpaceFileDescriptorsOtherDataAprocesshasthemainthreadthatinitializestheprocessandbeginsexecutingtheinstructions.2xSingleThreadRunningWithinaProgramProcessMultithreadedProgram2xThread0(ProgramCounter,Registers,etc.)AddressSpaceFileDescriptorsOtherDataThread1(ProgramCounter,Registers,etc.)CodesegmentDatasegmentStackStackStackthreadmain()…threadthreadProcessesandThreadsModernoperatingsystemsloadprogramsasprocessesResourceholderExecutionAprocessstartsexecutingatitsentrypointasathreadThreadscancreateotherthreadswithintheprocessEachthreadgetsitsownstackAllthreadswithinaprocesssharecode&datasegments線程CPU執(zhí)行內(nèi)核(executioncore)programcounterprogramcounterCopyofCPUregistersregistersasequenceofinstructionsALU進(jìn)程計(jì)算機(jī)Addressspace,data,memorymanagementinformationmemoryFileDescriptorsdiskProgramcounter,Code,processstate,valuesofCPUregistersCPU進(jìn)程與線程進(jìn)程：OS進(jìn)行計(jì)算機(jī)資源分配的單位一個(gè)進(jìn)程可以理解成：OS為用戶創(chuàng)建的、一個(gè)邏輯的計(jì)算機(jī)資源包括：內(nèi)存，顯卡，磁盤……線程：OS進(jìn)行CPU資源調(diào)度的單位一個(gè)線程可以理解成：進(jìn)程內(nèi)順序執(zhí)行的一個(gè)指令序列只涉及CPU資源線程之間共享進(jìn)程的資源為什么要多線程(multithreading)？減少程序的響應(yīng)時(shí)間與進(jìn)程相比，線程的創(chuàng)建和切換開銷更小資源共享和通信更方便簡化程序的結(jié)構(gòu)并發(fā)與并行并發(fā)(concurrency)幾件事情都在解決過程中，不是等到一件事情解決之后再解決另一件事情事情A和B都使用同一個(gè)資源（例如CPUexecutioncore），也使用不同的資源（內(nèi)存單元）A和B各使用cache中的一半頁面在把A需要的數(shù)據(jù)交換到cache時(shí)，可以用CPUexecutioncore處理B的一部分?jǐn)?shù)據(jù)（已在cache中）通過并發(fā)，提高了公用資源的利用率：如何合理安排對(duì)共用資源的使用成為關(guān)鍵并發(fā)與并行并行(parallelism)同時(shí)解決幾件事情，每件事情分別由不同的實(shí)體（人、計(jì)算機(jī)等）解決事情A和B分別使用不同的資源：A和B是兩個(gè)獨(dú)立的子問題A使用計(jì)算機(jī)1解決B使用計(jì)算機(jī)2解決通過并行，縮短了整個(gè)問題的解決周期，尋找到無關(guān)的子問題成為關(guān)鍵線程并行現(xiàn)實(shí)世界本質(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ā)：改變算法如何實(shí)現(xiàn)線程并行？執(zhí)行內(nèi)核寄存器Cache線程間共享的資源主存空間文件句柄其他I/O超線程與多核超線程(Hyper-Threading)：支持將一個(gè)執(zhí)行內(nèi)核模擬成多個(gè)邏輯處理器（并發(fā)）每個(gè)邏輯處理器上運(yùn)行一個(gè)線程邏輯處理器之間分享執(zhí)行內(nèi)核多核(Multi-core)：為進(jìn)程的運(yùn)行提供多個(gè)執(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)時(shí)稱為Super-Threading。之后陸續(xù)應(yīng)用在Pentium4HT中通過此技術(shù)，英特爾實(shí)現(xiàn)在一個(gè)實(shí)體CPU中，提供兩個(gè)邏輯線程超線程技術(shù)充分利用空閑CPU資源，在相同時(shí)間內(nèi)完成更多工作雖然采用超線程技術(shù)能夠同時(shí)執(zhí)行兩個(gè)線程，當(dāng)兩個(gè)線程同時(shí)需要某個(gè)資源時(shí)，其中一個(gè)線程必須讓出資源暫時(shí)掛起，直到這些資源空閑以后才能繼續(xù)IntelHyper-ThreadingIntelHyper-Threading單核技術(shù)的瓶頸多年來，在單線程性能方面已取得重大的進(jìn)展為提高單線程性能，采用了各種微體系結(jié)構(gòu)技術(shù)超標(biāo)量發(fā)射亂序發(fā)射超流水技術(shù)推測執(zhí)行但近年來，通過這些技術(shù)并未獲得更好的性能能量和存儲(chǔ)延時(shí)問題，已經(jīng)成為提高單線程性能的障礙一些高頻率芯片方案已被取消48能耗問題能量消耗大約與主頻成立方關(guān)系P~c*f3處理器能量的消耗已經(jīng)到了現(xiàn)有技術(shù)的極限對(duì)于有足夠多線程的應(yīng)用加倍并發(fā)線程的數(shù)目，能量消耗*2減半線程的工作頻率，能量消耗