并行計算系統計算機組成與體系結構內容提要Flynn分類法并行計算技術指令級并行指令多發射并發與并行超線程技術多核技術Flynn'sTaxonomy

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

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

令

指令狀態表

流出

執行

寫結果

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]

寄存器狀態表

F0F2F4F6F8F10…F30QiMult1

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

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

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