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

高等計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)清華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系高性能計(jì)算研究所鄭緯民教授2000年9月計(jì)算機(jī)科學(xué)與技術(shù)系研究生課程高等計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)第一章高等計(jì)算機(jī)的核心技術(shù)——并行處理第二章加速比性能模型與可擴(kuò)展性分析第三章互連與通信第四章劃分與調(diào)度第五章并行存儲(chǔ)器系統(tǒng)第六章CacheCoherence第七章MemoryConsistency第八章指令級(jí)并行處理第八章指令級(jí)并行處理 8.1指令級(jí)并行概述

8.1.1指令級(jí)并行處理 8.1.2減少每條指令執(zhí)行的平均周期數(shù) 8.1.3改進(jìn)CPI的途徑

8.2多發(fā)射結(jié)構(gòu) 8.3指令級(jí)并行的編譯技術(shù)8.1指令級(jí)并行概述

8.1.1指令級(jí)并行處理 過去25年，微機(jī)性能差不多每年以50%的速度提高：

（1）由于電路速度的改進(jìn)，占年增長(zhǎng)率一半不到。

（2）8位16位32位64位，CISCRISC；

（3）片上cache，F(xiàn)LPH/W，圖形加速H/W；

（4）采用流水技術(shù)

（5）電路的集成度也以每年40%的比例增長(zhǎng)10年來(lái)： 微處理器的周期從100200ns少于4ns，大約降低了25倍；

DRAM的訪問時(shí)間從150180ns

6080ns，大約3倍，需要用cache來(lái)彌補(bǔ)。 指令級(jí)并行處理（ILPP，InstructionLevelParallelProcessing）是實(shí)行低層機(jī)器操作的并行執(zhí)行，如存、取、整數(shù)加和浮點(diǎn)乘等。 通常的并行處理是指各有一大段代碼在不同的處理機(jī)上運(yùn)行，有些問題要得到較好的加速效果，必須重寫程序，工作量大，代價(jià)昂貴，但它們能直接在ILP機(jī)上運(yùn)行。 因此，ILP與傳統(tǒng)并行處理可互補(bǔ)。

8.1.2減少每條指令執(zhí)行的平均周期數(shù)

RISC比CISC機(jī)器的CPI（CyclesperInstruction，平均周期數(shù)）要小。

CISC一般用微碼技術(shù)，一條指令往往要用好幾個(gè)周期才能實(shí)現(xiàn)，復(fù)雜指令所需的周期數(shù)則更多，CISC機(jī)器CPI一般為4-6；

RISC一般指令一個(gè)周期完成，所以CPI=1，但LOAD、STORE等指令要長(zhǎng)些，所以RISC機(jī)器的CPI 約大于1。

RISC技術(shù)未來(lái)發(fā)展的方向是進(jìn)一步減少CPI；

CISC機(jī)器也在減少CPI；

一些新型的微處理器的CPI（不論是RISC還是CISC），都在逐漸趨向于2和1之間。

例：

Intel的5MHz的80286（1986），CPI=5

10MHz的68010（1983），CPI=12

22MHz的68030（1988），CPI=5

SUNSPARC（1987），CPI=1-2

8.1.3改進(jìn)CPI的途徑 給定的工作頻率下，要進(jìn)一步減小CPI，必須進(jìn)一步提高RISC內(nèi)部的并行性。

（1）哈佛結(jié)構(gòu)：即設(shè)計(jì)分開的指令cache和數(shù)據(jù)cache，可以并行工作。

（2）多端口的寄存器堆。如果一個(gè)寄存器堆有兩個(gè)源操作數(shù)端口和一個(gè)目的操作數(shù)端口，那么兩個(gè)源操作數(shù)可以同時(shí)取出，還可以寫入或取出另一條指令的目的操作數(shù)。

（3）流水線的級(jí)分得更細(xì)。 （4）編譯優(yōu)化技術(shù)。充分利用硬件資源、優(yōu)化分配寄存器。 （5）超標(biāo)量（superscalar）結(jié)構(gòu)。即設(shè)置多個(gè)執(zhí)行部件。 （6）超流水線（superpipeline）結(jié)構(gòu)。 （7）VLIW（VeryLongInstructionWord）第八章指令級(jí)并行處理 8.1指令級(jí)并行概述 8.2多發(fā)射結(jié)構(gòu)

8.2.1流水線結(jié)構(gòu) 8.2.2超標(biāo)量機(jī)的典型結(jié)構(gòu) 8.2.3VLIW機(jī)的結(jié)構(gòu)框圖 8.3指令級(jí)并行的編譯技術(shù)8.2多發(fā)射結(jié)構(gòu)

單發(fā)射結(jié)構(gòu)：每個(gè)周期只發(fā)射一條指令；

多發(fā)射結(jié)構(gòu)：在流水線結(jié)構(gòu)基礎(chǔ)上，每個(gè)周期可以發(fā)射多條指令。比如：

超標(biāo)量 超流水線

VLIW

數(shù)據(jù)流

8.2.1流水線結(jié)構(gòu)1.一般流水線結(jié)構(gòu)

IPC（InstructionPerCycle）=1，但由于數(shù)據(jù)相關(guān)、轉(zhuǎn)移相關(guān)和資源相關(guān)使得IPC<1。IFIDEXWRIFIDEXWRIFIDEXWRnn+1n+22.超標(biāo)量結(jié)構(gòu)

主要特點(diǎn)：

（1）配置多個(gè)處理部件，采用多條流水線并行處理；

（2）能同時(shí)對(duì)若干條指令進(jìn)行譯碼，將可并行執(zhí)行的指令送往不同的執(zhí)行部件，從而達(dá)到每個(gè)周期啟動(dòng)多條指令的目的。

（3）在程序運(yùn)行期間由硬件完成指令調(diào)度。下圖中，一個(gè)周期內(nèi)同時(shí)發(fā)出三條指令，有多個(gè)執(zhí)行部件，三條指令發(fā)到三個(gè)獨(dú)立的執(zhí)行部件去分別執(zhí)行。IFIDEXWRIFIDEXWRIFIDEXWR每拍啟動(dòng)3條指令，要求并行度=33.超流水線結(jié)構(gòu) 下圖中，一個(gè)流水段（一個(gè)周期）分成三個(gè)子段，每個(gè)子段取出的仍只有一條指令，但總體來(lái)看，一個(gè)周期內(nèi)取出了三條指令，執(zhí)行部件可以一套，每個(gè)部件在一個(gè)子段時(shí)間內(nèi)完成。IFIDEXWRIFIDEXWRIFIDEXWR每1/3個(gè)周期啟動(dòng)一條指令，要求并行度=3IFIDEXWRIFIDEXWR

超標(biāo)量和超流水線的比較

超標(biāo)量：工作部件多，晶體管數(shù)目也多， 每個(gè)部件的工作速度相對(duì)的可以低一些。以空間換取時(shí)間。

超流水線：工作部件少，晶體管數(shù)目少了，單每一個(gè)部件必須在一個(gè)子周期內(nèi)執(zhí)行，工作速度較高。以時(shí)間換取了空間。 大部分新一代的RISC都屬于超標(biāo)量結(jié)構(gòu)，比如：i860，i960，Motorola88110，IBMPower6000，SUN/TI的SuperSPARC。

MIPS的R4000屬于超流水線結(jié)構(gòu)。4.超流水線超標(biāo)量RISC

如DEC的Alpha和IntelPentium。IFIDEXWR每拍啟動(dòng)9條指令，要求并行度=9IFIDEXWRIFIDEXWR5.VLIW（超長(zhǎng)指令字）

1983年，Yale大學(xué)Fisher教授首先提出。 一條長(zhǎng)指令來(lái)實(shí)現(xiàn)多個(gè)操作的并行執(zhí)行，以減少對(duì)存儲(chǔ)器的訪問，這種長(zhǎng)指令往往達(dá)上百位，甚至上千位。 如下面的圖。每拍啟動(dòng)一條長(zhǎng)指令，執(zhí)行3個(gè)操作，相當(dāng)于3條指令，要求并行度為3。IFIDEXWR每拍啟動(dòng)1條指令，要求并行度=3IFIDEXWRIFIDEXWREXEXEXEXEXEX主要特點(diǎn)：

單一的控制流。只有一個(gè)控制器，每個(gè)周期啟動(dòng)一條長(zhǎng)指令。 超長(zhǎng)指令字被分成多個(gè)控制字段，每個(gè)字段直接獨(dú)立的控制每個(gè)功能部件。 含有大量的數(shù)據(jù)通路和功能部件，由于編譯器在編譯時(shí)間已經(jīng)考慮可能出現(xiàn)的數(shù)據(jù)相關(guān)和資源相關(guān)，故控制硬件比較簡(jiǎn)單。 在編譯階段完成超長(zhǎng)指令中多個(gè)可并行執(zhí)行操作的調(diào)度（超長(zhǎng)指令字的生成是由編譯器完成）。區(qū)分一條指令和一個(gè)操作：

一個(gè)操作是指一個(gè)計(jì)算單位，如加、取、轉(zhuǎn)移等。這在順序結(jié)構(gòu)中就是一條指令。而一條VLIW指令是包含一組同時(shí)發(fā)出的操作。編譯器的任務(wù)就是要確定哪些操作可以組合在一條指令中。組合在一條VLIW指令中的所有操作是同時(shí)開始執(zhí)行的。

8.2.2超標(biāo)量的典型結(jié)構(gòu)主存D-cache存儲(chǔ)器操作部件ALU12條指令并行取出并同時(shí)譯碼I-cache2指令調(diào)度轉(zhuǎn)移控制部件狀態(tài)記錄部件RF寄存器堆指令的執(zhí)行部件：

存儲(chǔ)器操作部件：執(zhí)行Load、Store指令

ALU：整數(shù)運(yùn)算 轉(zhuǎn)移控制部件：執(zhí)行轉(zhuǎn)移指令狀態(tài)記錄部件（調(diào)度部件）： 進(jìn)行流水動(dòng)態(tài)調(diào)度。依靠硬件在程序運(yùn)行過程中對(duì)可能出現(xiàn)的相關(guān)情況加以檢測(cè)，從而保證流水線中的各個(gè)功能部件能最大限度的重疊工作。 它對(duì)流水線中的各個(gè)功能部件的工作狀態(tài)、進(jìn)入流水線中的各條指令的工作狀態(tài)、它們所使用的源寄存器和目的寄存器情況等進(jìn)行集中的統(tǒng)一記錄和調(diào)度。 在譯碼階段，狀態(tài)記錄部件根據(jù)所記錄的狀態(tài)決定是否將譯碼后的指令發(fā)送給有關(guān)功能部件進(jìn)行處理。狀態(tài)記錄部件主要檢查： 該指令要使用的功能部件是否已被流水線中的其它指令占用（資源沖突）； 該指令的源操作數(shù)寄存器是否為其它指令的目的寄存器，或者它所要寫入的目的寄存器又正好是前面其它指令所要讀出的操作數(shù)，或是要寫入的目的寄存器。即檢查是否存在RAW、WAR、WAW的數(shù)據(jù)相關(guān)。RAW（ReadAfterWrite）：

指令j試圖在指令i寫入寄存器前就讀出該寄存器的內(nèi)容；WAR（WriteAfterRead）：

指令j試圖在指令i讀出寄存器前就寫入該寄存器的內(nèi)容；WAW（WriteAfterWrite）：

指令j試圖在指令i寫入寄存器前就寫入該寄存器的內(nèi)容；

8.2.3VLIW機(jī)的結(jié)構(gòu)框圖主存VLIW中的操作字段：RF（寄存器堆）LD/ST1LD/ST2FADDFMULLD/ST1LD/ST2FADDFMUL存/取1存/取2浮點(diǎn)加浮點(diǎn)乘例：要執(zhí)行以下賦值語(yǔ)句。

C=A+B K=I+J L=M-K Q=CK

假設(shè)LOAD/STORE，F(xiàn)ADD一個(gè)周期完成，F(xiàn)MUL二個(gè)周期完成。 若按串行操作進(jìn)行，則其所用的指令序列如下圖所示。共需14個(gè)周期。源代碼源代碼所需周期C=A+BLOADALOADBC=A+BSTOREC1111K=I+JLOADILOADJK=I+JSTOREK1111L=M-KLOADML=M-KSTOREL111Q=C*KQ=C*KSTOREQ21共需14個(gè)周期壓縮技術(shù)——表調(diào)度法：LOADALOADBLOADILOADJC=A+BLOADMSTORECK=I+J

STOREKL=M-KQ=C*K

STORELSTOREQ只需要6個(gè)周期。超標(biāo)量結(jié)構(gòu)、超流水線結(jié)構(gòu)一般采用指令窗方法，把一段指令（長(zhǎng)度為窗口的大小，例為8）取到窗口中，判斷這段指令能否并行執(zhí)行。第八章指令級(jí)并行處理 8.1指令級(jí)并行概述 8.2多發(fā)射結(jié)構(gòu)

8.3指令級(jí)并行的編譯技術(shù)

8.3.1軟件流水方法 8.3.2循環(huán)體展開8.3指令級(jí)并行的編譯技術(shù)

8.3.1軟件流水方法

例1：在一臺(tái)2發(fā)射處理機(jī)上執(zhí)行下列程序。

Do I=1，N A(I)=A(I)*B+C Enddo

假定存儲(chǔ)器訪問Read(讀)Write(寫)用一個(gè)周期。 每一個(gè)算術(shù)操作Mul、Add需二個(gè)周期，執(zhí)行一次迭代需要6個(gè)周期。如下：

周期指令注釋1READ/取A[I]/2MUL/乘B/34ADD/加C/56WRITE/存A[I]/ 完成N次迭代需要6N個(gè)周期。采用流水方法（做4次迭代情況）的情形如下：周期迭代11234read2mul3read4mul5addread6mul7addread8writemul9add10write11add12write1314write 每次迭代通過流水線需要8個(gè)周期，但4次迭代只需要14個(gè)時(shí)鐘周期。與非流水線執(zhí)行相比，加速比可達(dá)到： 用流水線執(zhí)行N次迭代需要2N+6個(gè)周期，加速比為：

8.3.2循環(huán)體展開

例1：一個(gè)循環(huán)體，對(duì)存儲(chǔ)器中的一個(gè)指定向量（雙精度）加上一個(gè)標(biāo)量值：

Loop： LD F0,0(R1)/M[(R1)+0]F0, 讀向量元素/

ADDDF4,F0,F2/(F0)+(F2)F4/ SD 0(R1),F4 /(F4)M[(R1)+0]

存向量元素/

SUB R1,R1,#8 /(R1)-8R1

將指針減去8個(gè)字節(jié)/

BNEZR1,Loop/若(R1)0,則跳轉(zhuǎn)/ 假設(shè)FPALU

使用另一個(gè)FPALU指令操作結(jié)果需要等待3個(gè)周期，STORE指令欲使用由FPALU指令產(chǎn)生的結(jié)果需要等待2個(gè)周期，F(xiàn)PALU指令使用LOAD的結(jié)果等待1個(gè)周期。 則上面過程的實(shí)際執(zhí)行情況如下：

Loop： LD F0,0(R1) STALL /停頓/

ADDDF4,F0,F2 STALL STALL SD 0(R1),F4

SUB R1,R1,#8

BNEZR1,Loop STALL 執(zhí)行一遍循環(huán)體需要9個(gè)時(shí)鐘周期。

Loop： LD F0,0(R1) STALL

ADDDF4,F0,F2

SUB R1,R1,#8

BNEZR1,Loop SD 8(R1),F4 對(duì)上述循環(huán)體進(jìn)行調(diào)度，使其變成如下： 由于SUB和SD交換了先后順序，因此SD指令中的R1的偏移量需由原來(lái)的0變?yōu)?。

周期

Loop： LD F0,0(R1) 2

ADDDF4,F0,F2 3

SD 0(R1),F4 1

LD F6,-8(R1) 2

ADDDF8,F