Ch8 指令級并行處理

1、高等計算機系統(tǒng)結構計算機科學與技術系研究生課程高等計算機系統(tǒng)結構第一章 高等計算機的核心技術并行處理第二章 加速比性能模型與可擴展性分析第三章 互連與通信第四章 劃分與調度第五章 并行存儲器系統(tǒng)第六章 Cache Coherence第七章 Memory Consistency第八章 指令級并行處理第八章 指令級并行處理8.1 指令級并行概述 8.1.1 指令級并行處理 8.1.2 減少每條指令執(zhí)行的平均周期數(shù) 8.1.3 改進CPI的途徑8.2 多發(fā)射結構8.3 指令級并行的編譯技術8.1 指令級并行概述8.1.1 指令級并行處理過去25年，微機性能差不多每年以50%的速度提高：（1）由于電路

2、速度的改進，占年增長率一半不到。（2）8位16位32位64位，CISC RISC；（3）片上cache，F(xiàn)LP H/W，圖形加速H/W；（4）采用流水技術（5）電路的集成度也以每年40%的比例增長10年來：微處理器的周期從100200ns 少于4ns，大約降低了25倍；DRAM的訪問時間從150 180ns 60 80ns，大約3倍，需要用cache來彌補。指令級并行處理（ILPP，Instruction Level Parallel Processing）是實行低層機器操作的并行執(zhí)行，如存、取、整數(shù)加和浮點乘等。通常的并行處理是指各有一大段代碼在不同的處理機上運行，有些問題要得到較好的加速效

3、果，必須重寫程序，工作量大，代價昂貴，但它們能直接在ILP機上運行。因此，ILP與傳統(tǒng)并行處理可互補。8.1.2 減少每條指令執(zhí)行的平均周期數(shù)RISC比CISC機器的CPI（Cycles per Instruction，平均周期數(shù)）要小。CISC一般用微碼技術，一條指令往往要用好幾個周期才能實現(xiàn)，復雜指令所需的周期數(shù)則更多，CISC機器CPI一般為4-6；RISC一般指令一個周期完成，所以CPI=1，但LOAD、STORE等指令要長些，所以RISC機器的CPI約大于1。 RISC技術未來發(fā)展的方向是進一步減少CPI；CISC機器也在減少CPI；一些新型的微處理器的CPI（不論是RISC還是CI

4、SC），都在逐漸趨向于2和1之間。例：Intel的5MHz的80286（1986），CPI=510MHz的68010（1983），CPI=1222MHz的68030（1988），CPI=5SUN SPARC（1987），CPI=1-28.1.3 改進CPI的途徑給定的工作頻率下，要進一步減小CPI，必須進一步提高RISC內(nèi)部的并行性。（1）哈佛結構：即設計分開的指令cache和數(shù)據(jù)cache，可以并行工作。（2）多端口的寄存器堆。如果一個寄存器堆有兩個源操作數(shù)端口和一個目的操作數(shù)端口，那么兩個源操作數(shù)可以同時取出，還可以寫入或取出另一條指令的目的操作數(shù)。（3）流水線的級分得更細。（4）編譯優(yōu)化

5、技術。充分利用硬件資源、優(yōu)化分配寄存器。（5）超標量（super scalar）結構。即設置多個執(zhí)行部件。（6）超流水線（superpipeline）結構。（7）VLIW（Very Long Instruction Word）第八章 指令級并行處理8.1 指令級并行概述8.2 多發(fā)射結構 8.2.1 流水線結構 8.2.2 超標量機的典型結構 8.2.3 VLIW機的結構框圖8.3 指令級并行的編譯技術8.2 多發(fā)射結構單發(fā)射結構：每個周期只發(fā)射一條指令；多發(fā)射結構：在流水線結構基礎上，每個周期可以發(fā)射多條指令。比如：超標量超流水線VLIW數(shù)據(jù)流8.2.1 流水線結構1.一般流水線結構IPC（

6、Instruction Per Cycle）=1，但由于數(shù)據(jù)相關、轉移相關和資源相關使得IPC1。IFIDEXWRIFIDEXWRIFIDEXWRnn+1n+22.超標量結構主要特點：（1）配置多個處理部件，采用多條流水線并行處理；（2）能同時對若干條指令進行譯碼，將可并行執(zhí)行的指令送往不同的執(zhí)行部件，從而達到每個周期啟動多條指令的目的。（3）在程序運行期間由硬件完成指令調度。下圖中，一個周期內(nèi)同時發(fā)出三條指令，有多個執(zhí)行部件，三條指令發(fā)到三個獨立的執(zhí)行部件去分別執(zhí)行。IFIDEXWRIFIDEXWRIFIDEXWR每拍啟動3條指令，要求并行度=33.超流水線結構下圖中，一個流水段（一個周期）

7、分成三個子段，每個子段取出的仍只有一條指令，但總體來看，一個周期內(nèi)取出了三條指令，執(zhí)行部件可以一套，每個部件在一個子段時間內(nèi)完成。IFIDEXWRIFIDEXWRIFIDEXWR每1/3個周期啟動一條指令，要求并行度=3IFIDEXWRIFIDEXWR超標量和超流水線的比較超標量：工作部件多，晶體管數(shù)目也多，每個部件的工作速度相對的可以低一些。以空間換取時間。超流水線：工作部件少，晶體管數(shù)目少了，單每一個部件必須在一個子周期內(nèi)執(zhí)行，工作速度較高。以時間換取了空間。大部分新一代的RISC都屬于超標量結構，比如：i860，i960 ，Motorola 88110 ，IBM Power 6000 ，

8、SUN/TI的Super SPARC。MIPS的R4000屬于超流水線結構。4.超流水線超標量RISC如DEC的Alpha和Intel Pentium。IFIDEXWR每拍啟動9條指令，要求并行度=9IFIDEXWRIFIDEXWR5.VLIW（超長指令字）1983年，Yale大學Fisher教授首先提出。一條長指令來實現(xiàn)多個操作的并行執(zhí)行，以減少對存儲器的訪問，這種長指令往往達上百位，甚至上千位。如下面的圖。每拍啟動一條長指令，執(zhí)行3個操作，相當于3條指令，要求并行度為3。IFIDEXWR每拍啟動1條指令，要求并行度=3IFIDEXWRIFIDEXWREXEXEXEXEXEX主要特點：單一的

9、控制流。只有一個控制器，每個周期啟動一條長指令。超長指令字被分成多個控制字段，每個字段直接獨立的控制每個功能部件。含有大量的數(shù)據(jù)通路和功能部件，由于編譯器在編譯時間已經(jīng)考慮可能出現(xiàn)的數(shù)據(jù)相關和資源相關，故控制硬件比較簡單。在編譯階段完成超長指令中多個可并行執(zhí)行操作的調度（超長指令字的生成是由編譯器完成）。區(qū)分一條指令和一個操作：一個操作是指一個計算單位，如加、取、轉移等。這在順序結構中就是一條指令。而一條VLIW指令是包含一組同時發(fā)出的操作。編譯器的任務就是要確定哪些操作可以組合在一條指令中。組合在一條VLIW指令中的所有操作是同時開始執(zhí)行的。8.2.2 超標量的典型結構主存D-cache存儲

10、器操作部件ALU12條指令并行取出并同時譯碼I-cache2指令調度轉移控制部件狀態(tài)記錄部件RF寄存器堆指令的執(zhí)行部件：存儲器操作部件：執(zhí)行Load、Store指令ALU：整數(shù)運算轉移控制部件：執(zhí)行轉移指令狀態(tài)記錄部件（調度部件）：進行流水動態(tài)調度。依靠硬件在程序運行過程中對可能出現(xiàn)的相關情況加以檢測，從而保證流水線中的各個功能部件能最大限度的重疊工作。它對流水線中的各個功能部件的工作狀態(tài)、進入流水線中的各條指令的工作狀態(tài)、它們所使用的源寄存器和目的寄存器情況等進行集中的統(tǒng)一記錄和調度。在譯碼階段，狀態(tài)記錄部件根據(jù)所記錄的狀態(tài)決定是否將譯碼后的指令發(fā)送給有關功能部件進行處理。狀態(tài)記錄部件主要檢

11、查：該指令要使用的功能部件是否已被流水線中的其它指令占用（資源沖突）；該指令的源操作數(shù)寄存器是否為其它指令的目的寄存器，或者它所要寫入的目的寄存器又正好是前面其它指令所要讀出的操作數(shù)，或是要寫入的目的寄存器。即檢查是否存在RAW、WAR、WAW的數(shù)據(jù)相關。RAW（Read After Write）：指令j試圖在指令i寫入寄存器前就讀出該寄存器的內(nèi)容；WAR（Write After Read）：指令j試圖在指令i讀出寄存器前就寫入該寄存器的內(nèi)容；WAW（Write After Write）：指令j試圖在指令i寫入寄存器前就寫入該寄存器的內(nèi)容；8.2.3 VLIW機的結構框圖主存VLIW中的操作字

12、段：RF（寄存器堆）LD/ST1LD/ST2FADDFMULLD/ST1LD/ST2FADDFMUL存/取1存/取2浮點加浮點乘例：要執(zhí)行以下賦值語句。 C = A + BK = I + JL = M - KQ = C K假設LOAD/STORE，F(xiàn)ADD一個周期完成，F(xiàn)MUL二個周期完成。若按串行操作進行，則其所用的指令序列如下圖所示。共需14個周期。源代碼源代碼所需周期C=A+BLOAD ALOAD BC=A+BSTORE C1111K=I+JLOAD ILOAD JK=I+JSTORE K1111L=M-KLOAD ML=M-KSTORE L111Q=C*KQ=C*KSTORE Q21共

13、需14個周期壓縮技術表調度法：LOAD ALOAD BLOAD ILOAD JC=A+BLOAD MSTORE CK=I+J STORE KL=M-KQ=C*K STORE LSTORE Q只需要6個周期。超標量結構、超流水線結構一般采用指令窗方法，把一段指令（長度為窗口的大小，例為8）取到窗口中，判斷這段指令能否并行執(zhí)行。第八章 指令級并行處理8.1 指令級并行概述8.2 多發(fā)射結構8.3 指令級并行的編譯技術 8.3.1 軟件流水方法 8.3.2 循環(huán)體展開8.3 指令級并行的編譯技術8.3.1 軟件流水方法例1：在一臺2發(fā)射處理機上執(zhí)行下列程序。DoI =1，NA(I) = A(I) *

14、 B + CEnd do假定存儲器訪問Read(讀)Write(寫)用一個周期。每一個算術操作Mul、Add需二個周期，執(zhí)行一次迭代需要6個周期。如下： 周期指令注釋1READ/取AI/2MUL/乘B/34ADD/加C/56WRITE/存AI/ 完成N次迭代需要6N個周期。采用流水方法（做4次迭代情況）的情形如下：周期迭代11234read2mul3read4mul5addread6mul7addread8writemul9add10write11add12write1314write 每次迭代通過流水線需要8個周期，但4次迭代只需要14個時鐘周期。與非流水線執(zhí)行相比，加速比可達到：7.114

15、24 用流水線執(zhí)行N次迭代需要2N+6個周期，加速比為：3,33626加速比當 NNNNN8.3.2 循環(huán)體展開例1：一個循環(huán)體，對存儲器中的一個指定向量（雙精度）加上一個標量值： Loop：LDF0, 0(R1) /M(R1)+0F0,讀向量元素/ADDD F4, F0, F2 /(F0)+(F2)F4/SD0(R1), F4 /(F4)M(R1)+0 存向量元素/SUB R1, R1, #8 /(R1)-8R1 將指針減去8個字節(jié)/BNEZ R1, Loop /若(R1)0, 則跳轉/假設FP ALU 使用另一個FP ALU指令操作結果需要等待3個周期，STORE指令欲使用由FP ALU指

16、令產(chǎn)生的結果需要等待2個周期，F(xiàn)P ALU指令使用LOAD的結果等待1個周期。則上面過程的實際執(zhí)行情況如下： Loop：LDF0, 0(R1)STALL /停頓/ADDD F4, F0, F2STALLSTALLSD0(R1), F4SUB R1, R1, #8BNEZ R1, LoopSTALL執(zhí)行一遍循環(huán)體需要9個時鐘周期。 Loop：LDF0, 0(R1)STALLADDD F4, F0, F2SUB R1, R1, #8BNEZ R1, LoopSD8(R1), F4對上述循環(huán)體進行調度，使其變成如下：由于SUB和SD交換了先后順序，因此SD指令中的R1的偏移量需由原來的0變?yōu)?。 周期Loop：LDF0, 0(R1) 2ADDD F4, F0, F2 3 SD0(R1), F4 1LDF6, -8(R1) 2ADDD F8, F6, F2 3SD-8(R1), F8 1LDF10, -16(R1) 2ADDD F12, F10, F2 3SD-16(R1), F1 1將循環(huán)體展開3次后再進行調度： 周期LDF14, -24(R1) 2ADDD F16, F14, F2 3SD-24(R1), F16 1SUB R1, R1, #32 1BNEZ R1, Loop 2循環(huán)展開3次，總計27