《計(jì)算機(jī)體系結(jié)構(gòu)》第五章課件

利用堆棧技術(shù)模擬

LRU在不同n條件下頁(yè)面變化時(shí)空?qǐng)D及命中率。LRU算法的實(shí)現(xiàn)方法:

堆棧法、比較對(duì)法§4存貯體系的兩個(gè)分支虛擬存貯器的簡(jiǎn)單工作過(guò)程

Cache—主存體系與虛擬存儲(chǔ)器異同之處§5內(nèi)部定向原理介紹內(nèi)部定向原理的和的繪制

組相聯(lián)映象的例子頁(yè)面替換時(shí)空?qǐng)D主存地址到Cache地址的變換

§3替換算法及其實(shí)現(xiàn)FIFO、LRU、OPT上述算法在給定地址流及主存頁(yè)面數(shù)下頁(yè)面變化時(shí)空?qǐng)D主存頁(yè)面數(shù)n的大小對(duì)命中率的影響6解：1）

主存

NdqsNrq’s’nr

Cache

2）

主存頁(yè)號(hào)1位1位1位1位1位

3)可放入Cache0組的主存塊號(hào):0145

可放入Cache1組的主存塊號(hào):23674)凡是不命中就是失效;失效而發(fā)生替換就是爭(zhēng)用。塊失效、塊爭(zhēng)用的時(shí)刻

t=6,7,9,10,11,12,14,155)tA=H*tc+(1-H)*tm=0.2*2+0.8*15=12.4(ns)時(shí)間t123456789101112131415地址流12413701254647200111#1111#111#44444144#4#4#00#0#55#5#5#5#5#102222#7777#7#7#666#2133#3#3#2222#2#77#命中情況失失失中失爭(zhēng)爭(zhēng)中爭(zhēng)爭(zhēng)爭(zhēng)爭(zhēng)中爭(zhēng)爭(zhēng)[例]考慮一個(gè)920個(gè)字的程序，其訪問(wèn)輔存的地址流為20，22，208，214，146，618，370，490，492，868，916，728。

若頁(yè)面大小為200字，主存容量為400字，采用全相聯(lián)FIFO替換算法，請(qǐng)按訪存的各個(gè)時(shí)刻，寫出其虛頁(yè)地址流，計(jì)算主存的命中率；

[解]虛頁(yè)號(hào)＝└虛地址／頁(yè)面大小┘

頁(yè)面大小為200字，主存容量為400字，可知主存頁(yè)數(shù)為2頁(yè)。其虛頁(yè)地址流為

0，0，1，1，0，3，1，2，2，4，4，3

下圖給出了采用FIFO替換算法替換時(shí)的實(shí)際裝入和替換過(guò)程。其中，“#”標(biāo)記的是候選替換的虛頁(yè)頁(yè)號(hào)，下劃線表示命中。

t虛地址頁(yè)面流

202220821414661837049049286891672800110312244300#0#0#③33#3#④44#

①111#1#②22#2#③H=6/12=0.5123456789101112§6

交叉訪問(wèn)的存儲(chǔ)器

主存儲(chǔ)器由多個(gè)模塊構(gòu)成。 假設(shè)主存儲(chǔ)器包含m=2a個(gè)存儲(chǔ)器模塊，每個(gè)模塊包含w=2b個(gè)存儲(chǔ)單元（字），則總存儲(chǔ)容量為

1）低位交叉方式

存儲(chǔ)器地址的低a位用來(lái)指明存儲(chǔ)器模塊，高b位是每個(gè)模塊內(nèi)的字地址。 低位m路交叉存取如下圖：……b位a位地址譯碼器MAB0m……m(w-1)MDBM0MAB1m+1……mw-m+1MDBM1……MABm-12m-1……mw-1MDBMm-1WAB字模塊……地址ab數(shù)據(jù)總線存儲(chǔ)器數(shù)據(jù)緩沖器模塊地址緩沖器字地址緩沖器

2）高位交叉方式

存儲(chǔ)器地址的高a位作為存儲(chǔ)器模塊地址，鄰接的存儲(chǔ)器單元被分配在同一個(gè)存儲(chǔ)器模塊中，在每個(gè)存儲(chǔ)器周期內(nèi)，只能對(duì)各模塊存取一個(gè)字。所以不支持鄰接單元的成塊存取。 高位m路交叉存取如下圖：3）兩種方式的比較

（1）低位交叉以流水線方式支持成塊存取

將存儲(chǔ)器周期稱為主周期，細(xì)分為m個(gè)小周期（m稱為交叉存取度），如8路交叉，m=8，w=8，a=b=3，設(shè)為主周期，為小周期，則

8路低位交叉存取如下圖：08…56存儲(chǔ)器地址寄存器(6位)M019…57M1210…58M2311…59M3412…60M4513…61M5614…62M6715…63M7數(shù)據(jù)

低位交叉流水線方式示意圖：W0W7W6W5W4W3W2W1時(shí)間

為主周期，=/m為小周期，m為交叉存取度

將高位與低位交叉存取加以組合。 高位交叉時(shí)，各存儲(chǔ)器模塊內(nèi)的地址是按順序連續(xù)編排的。 對(duì)8個(gè)存儲(chǔ)模塊，將它們分為2個(gè)存儲(chǔ)器，體內(nèi)采用4路低位交叉存取。示意圖如下：4）容錯(cuò)04…28存儲(chǔ)器地址寄存器(6位)M015…29M126…30M237…31M33236…60M43337…61M53438…62M63539…63M7體0體1體地址字地址模塊地址

對(duì)8個(gè)存儲(chǔ)模塊，將它們分為4個(gè)存儲(chǔ)器，體內(nèi)采用2路低位交叉存取。示意圖如下：

在一個(gè)模塊發(fā)生故障的情況下：

8路（1體）交叉存取存儲(chǔ)器的最大存儲(chǔ)器帶寬減少到零；

4路2體交叉存儲(chǔ)器的最大帶寬減少到每周期4個(gè)字（只有一個(gè)體被廢棄）；

2路4體交叉存儲(chǔ)器中，仍有3個(gè)體工作，所以最大帶寬為6個(gè)字。

習(xí)題：假定一個(gè)由16個(gè)存儲(chǔ)器模塊構(gòu)成的主存儲(chǔ)器系統(tǒng)有下列三種交叉存儲(chǔ)器設(shè)計(jì)方案。每個(gè)模塊的容量為1M字節(jié)，機(jī)器按字節(jié)尋址。 設(shè)計(jì)1：用1個(gè)存儲(chǔ)體16路交叉。 設(shè)計(jì)2：用2個(gè)存儲(chǔ)體8路交叉。 設(shè)計(jì)3：用4個(gè)存儲(chǔ)體4路交叉。

（a）確定上述存儲(chǔ)器組織的地址構(gòu)成。

（b）在上述每種存儲(chǔ)器組織中，假定只有一個(gè)存儲(chǔ)器模塊失效，確定能獲得的最大存儲(chǔ)器帶寬。

設(shè)計(jì)1：1個(gè)存儲(chǔ)體16路交叉。

a)地址構(gòu)成：存儲(chǔ)器地址寄存器(24位)b）帶寬為0?！?0位4位設(shè)計(jì)2：2個(gè)存儲(chǔ)體8路交叉。

a)地址構(gòu)成：存儲(chǔ)器地址寄存器(24位)b）帶寬為50%。存儲(chǔ)器地址寄存器(24位)體地址模塊地址08…223-8M0715…M7…M8

…M15體0體1字地址存儲(chǔ)器地址寄存器(24位)體地址模塊地址……223-1223224-8223+7224-1…設(shè)計(jì)1：1個(gè)存儲(chǔ)體16路交叉。

a)地址構(gòu)成：存儲(chǔ)器地址寄存器(24位)b）帶寬為0?！?0位4位數(shù)據(jù)024…224-16存儲(chǔ)器地址寄存器(24位)M0124+1…224-15M124-125-1…224-1M15……設(shè)計(jì)2：2個(gè)存儲(chǔ)體8路交叉。

a)地址構(gòu)成：存儲(chǔ)器地址寄存器(24位)b）帶寬為50%。c）存儲(chǔ)器地址寄存器(24位)體地址模塊地址08…223-8M0715…M7…M8

…M15體0體1字地址存儲(chǔ)器地址寄存器(24位)體地址模塊地址……223-1223224-8223+7224-1…存儲(chǔ)器地址寄存器(24位)體地址模塊地址a)地址構(gòu)成：存儲(chǔ)器地址寄存器(24位)b）帶寬為75%。04…222-4M037…M3…M12

…M15體0體3字地址……222-13*222224-43*222+3224-1…存儲(chǔ)器地址寄存器(24位)體地址模塊地址…多體交叉存儲(chǔ)器的兩種組織方式

(1)低位交叉方式（體內(nèi)斷續(xù)，體間連續(xù)）

(2)高位交叉方式（體內(nèi)連續(xù)，體間斷續(xù)）

第五章重疊、流水和向量處理機(jī)

§1重疊方式一、重疊解釋方式1.一條指令的幾個(gè)過(guò)程段

1）取指令：根據(jù)PC（指令計(jì)數(shù)器）從M（存儲(chǔ)器）取出指令送到IR（指令寄存器）

2）譯碼分析：譯出指令的操作性質(zhì)，準(zhǔn)備好所需數(shù)據(jù)

3）執(zhí)行：將準(zhǔn)備好的數(shù)按譯出性質(zhì)進(jìn)行處理，主要涉及ALU（算術(shù)邏輯運(yùn)算部件）

2.對(duì)指令執(zhí)行的幾種方式1）順序執(zhí)行(傳統(tǒng)機(jī)采用)

只有在前一條指令的各過(guò)程段全部完成后，才從存儲(chǔ)器取出下一條指令。2)僅兩條指令重疊：第i條指令的執(zhí)行與第i+1條的取指重疊。3)三條指令重疊第i條指令的執(zhí)行與第i+1條的譯碼及第i+2條的取指重疊。

取

譯

執(zhí)

取

譯

執(zhí)

i條

i+1條

i條取譯執(zhí)取譯執(zhí)i+1條i條取譯執(zhí)i+1條取譯執(zhí)i+2條取譯執(zhí)

若指令的過(guò)程段劃分更多時(shí)，重疊組合方式更多。

重疊解釋并不能加快一條指令的實(shí)現(xiàn)，但能加快一段程序的解釋。3.重疊方式中所需時(shí)間表達(dá)式及所需時(shí)間計(jì)算1）條件：設(shè)一條指令分為三個(gè)過(guò)程段，各過(guò)程段分別用t取、t譯、t執(zhí)表示。執(zhí)行K條指令，分別采用順序執(zhí)行、兩條重疊、三條重疊。2）分別列出上述三種執(zhí)行方式所需時(shí)間表達(dá)式順序執(zhí)行k*（t取+t譯+t執(zhí)）兩條重疊t取+k*t譯+(k-1)*(t取,t執(zhí))max+t執(zhí)三條重疊t取+(t譯,t取)max+(k-2)*(t取,t譯,t執(zhí))

max+(t執(zhí),t譯)max+t執(zhí)3)例子

當(dāng)k=200，t取=3Δt，t譯=4Δt，t執(zhí)=5Δt，時(shí)，分別計(jì)算上述三種執(zhí)行方式的時(shí)間。順序執(zhí)行：200×(3+4+5)=2400Δt

兩條重疊：3+200×4+(200-1)×5+5=1803Δt

三條重疊：3+4+(200-2)×5+5+5=1007Δt4.重疊方式需要解決的問(wèn)題1）對(duì)存儲(chǔ)器的頻繁訪問(wèn)①有哪些訪問(wèn)：取指令、取操作數(shù)、存放執(zhí)行結(jié)果,I/O通道訪問(wèn).②希望存儲(chǔ)器為多體結(jié)構(gòu)，以適應(yīng)多種訪問(wèn)源的需要。③當(dāng)存儲(chǔ)器為單體結(jié)構(gòu)時(shí)，需要將訪問(wèn)源排隊(duì)，先后順序?yàn)椋喝≈噶睢⑷?shù)據(jù)、I/O通道訪問(wèn)、存結(jié)果2）應(yīng)具有先行控制部件①

先行：在重疊操作中，當(dāng)前一條指令在執(zhí)行過(guò)程中就需要提前取出后面的指令進(jìn)行相應(yīng)處理，這種提前取出后繼指令進(jìn)行相應(yīng)處理，稱為先行。②先行控制部件主要包括

Ⅰ）先行地址站，包括先行指令地址站和先行操作數(shù)地址站；

Ⅱ）先行指令站，用來(lái)存放多條指令；

Ⅲ）先行操作數(shù)站，用來(lái)存放多個(gè)操作數(shù)；

Ⅳ）先行地址形成部件，用來(lái)形成先行指令地址以及先行操作數(shù)地址；

Ⅴ）先行操作碼譯碼站，用來(lái)完成對(duì)多條指令的譯碼并保留譯碼輸出狀態(tài)。3）也應(yīng)具有后行部件

后行部件：對(duì)指令執(zhí)行后的結(jié)果進(jìn)行處理的器件，稱

后行部件。包括：

①后行數(shù)地址站，提供后行數(shù)存放地址。

②后行數(shù)站，存放運(yùn)行的結(jié)果，并且，這些結(jié)果需送存

儲(chǔ)器。二、相關(guān)問(wèn)題1何謂相關(guān)：在重疊方式的指令執(zhí)行過(guò)程中，由于發(fā)生了某種關(guān)聯(lián)，使正在被解釋的指令無(wú)法再繼續(xù)下去的現(xiàn)象，稱相關(guān)。2相關(guān)類型1）從性質(zhì)上分①指令相關(guān)：重新修改了正在被解釋的指令②數(shù)相關(guān)：因等待前面指令執(zhí)行的結(jié)果，使后面指令等待而不能連續(xù)解釋。如：S=a/b+cLDR,ADIVR,BADDR,C；要等DIV結(jié)果

STR,S；存結(jié)果ABabcsCS2）按影響面大小分①局部相關(guān)：相關(guān)發(fā)生時(shí)只能影響鄰近幾條指令的執(zhí)行，這種相關(guān)影響面不大。如等待結(jié)果的數(shù)相關(guān)。②全局相關(guān)：相關(guān)發(fā)生時(shí)影響面很大——全局。如條件轉(zhuǎn)移指令，當(dāng)條件具備時(shí)，就轉(zhuǎn)到其他地方去執(zhí)行程序，而轉(zhuǎn)移指令之后的幾條語(yǔ)句已先后被解釋了部分功能，但此時(shí)全部廢棄。3解決指令相關(guān)1）盡可能避免指令相關(guān),

需要修改指令時(shí)變指令相關(guān)為操作數(shù)相關(guān)，統(tǒng)一按操作相關(guān)去處理。

2）用分支程序代替被修改的指令4解決條件轉(zhuǎn)移的全局相關(guān)1）猜測(cè)法①按成功支路猜測(cè)：凡是條件轉(zhuǎn)移指令都將成功支路指令提前取到指令站中，此時(shí)將不成功支路指令取到后援寄存器組。②按不成功支路猜測(cè)：做法與①正好相反。2）分支預(yù)測(cè)：允許CPU對(duì)分支以后的指令進(jìn)行譯碼，如P6系列CPU中，取指/譯碼單元使用一種優(yōu)化的分支預(yù)測(cè)算法，用來(lái)在多級(jí)分支、過(guò)程調(diào)用和返回時(shí)預(yù)測(cè)指令的流向。

如計(jì)算A=B﹡CifA＜0GoTon

在進(jìn)行B﹡C之前，可先對(duì)SB⊕SC=？進(jìn)行判斷，決定流向。3）盡可能作成短轉(zhuǎn)移，短循環(huán)：使轉(zhuǎn)去的指令都在指令站中。4）增加指令站容量（P6體系中稱為指令池——重排序緩沖器，是一個(gè)按內(nèi)容尋址的存儲(chǔ)器陣列?？纱娣?0個(gè)等待執(zhí)行的微操作，執(zhí)行單元能夠以任意順序執(zhí)行重排序緩沖器中的指令。）5解決等待結(jié)果的數(shù)相關(guān)1）推遲法：包括推遲譯碼分析，推遲執(zhí)行。適用范圍寬，但不利于速度的提高。2）相關(guān)專用通路法當(dāng)上一條的運(yùn)算結(jié)果需作下一條的源操作數(shù)時(shí)，如：

LDR，AADDR，BSUBR，C

可建一個(gè)相關(guān)專用比常規(guī)通路提前1τ獲取源操作數(shù)。ALUABregisters相關(guān)專用通路常規(guī)通路數(shù)據(jù)總線產(chǎn)品生產(chǎn)流水線舉例

◆兩種方案的工作過(guò)程對(duì)比◆流水線生產(chǎn)過(guò)程的抽象描述§2流水技術(shù)◆

兩種方案一、流水方式的出現(xiàn)1重疊方式的兩種等待1）等待譯碼當(dāng)ti譯＞ti+1取時(shí)，即：2）等待執(zhí)行

ti執(zhí)＞ti+1譯時(shí)，即：i+1i等待譯碼時(shí)間取譯執(zhí)取

譯執(zhí)取譯

執(zhí)ii+1執(zhí)取譯等待執(zhí)行時(shí)間2產(chǎn)生等待的原因

重迭方式未按時(shí)間單位來(lái)劃分過(guò)程段，比較粗糙。

3流水線上對(duì)各過(guò)程段進(jìn)行時(shí)間匹配的辦法。

1）將一條指令分為以Δt為單位的多個(gè)Δt過(guò)程段。如某指令用時(shí)5Δt，可分為5個(gè)過(guò)程段：(均勻流水線）1Δt2Δt3Δt4Δt5Δt2）當(dāng)某過(guò)程段用時(shí)較長(zhǎng)，又不便于細(xì)分時(shí)，可用多套相同設(shè)備來(lái)實(shí)現(xiàn)時(shí)間匹配。如第3個(gè)過(guò)程段用時(shí)2Δt，其余1，2，4用時(shí)均為Δt：（非均勻流水線）

4流水線的分類1）按各過(guò)程段用時(shí)是否全等劃分①均勻流水線：各過(guò)程段用時(shí)全等②非均勻流水線：各過(guò)程段用時(shí)不全等（如上圖）

Ⅰ）時(shí)間匹配的非均勻流水線。

Ⅱ）時(shí)間不匹配的非均勻流水線。

1Δt2Δt4Δt32Δt3212）按處理的數(shù)據(jù)類型①標(biāo)量流水線：用于對(duì)標(biāo)量數(shù)據(jù)進(jìn)行流水處理。②向量流水線：用于對(duì)向量數(shù)據(jù)進(jìn)行流水處理。（向量很適合流水處理）3）按流水線的規(guī)模①操作流水線：如將一條指令劃分為多個(gè)過(guò)程段進(jìn)行流水處理。規(guī)模最小②指令流水線：以指令為單位進(jìn)行處理，用于多進(jìn)程、多任務(wù)。規(guī)模較大③宏流水線：以程序的邏輯功能段為單位進(jìn)行流水處理。規(guī)模最大

4）按流水線具有功能的多少①單功能流水線：各過(guò)程段之間固定連接，不能重新構(gòu)成其它流水線——固定流水線②多功能流水線：流水線的各段可以進(jìn)行不同的

連接，從而實(shí)現(xiàn)不同的功能。例：TIASC運(yùn)算器靜態(tài)流水線：各過(guò)程段之間可重新連接，但不同時(shí)刻只能重構(gòu)成一種不同的流水線。動(dòng)畫演示動(dòng)態(tài)流水線：各過(guò)程段之間可重新連接，不同時(shí)刻可重構(gòu)成多種流水線。動(dòng)畫演示5）按部件在同一時(shí)刻送出支路數(shù)的多少來(lái)分。①一維流水線：在同一時(shí)刻，部件只能向一個(gè)地方傳送結(jié)果。②陣列流水線：在同一時(shí)刻，部件可同時(shí)向多個(gè)地方傳送結(jié)果。

時(shí)－空?qǐng)D

時(shí)－空?qǐng)D從時(shí)間和空間兩個(gè)方面描述了流水

線的工作過(guò)程。時(shí)－空?qǐng)D中，橫坐標(biāo)代表時(shí)間，

縱坐標(biāo)代表流水線的各個(gè)段。二、流水線的執(zhí)行過(guò)程及性能評(píng)價(jià)1.均勻流水線加法流水線：1）不相關(guān)算式計(jì)算：Si=ai+bi(i=0～7)共有8個(gè)算式①S0=a0+b0②S1=a1+b1

…⑧S7=a7+b7

畫出各算式在流水線上執(zhí)行過(guò)程時(shí)空?qǐng)D

S0

S1S2S3S4

S5S6S7

過(guò)程段①②③④⑤⑥⑦⑧①②③④⑤⑥⑦⑧123456789101112①②③④⑤⑥⑦⑧①②③④⑤⑥⑦⑧54321①②③④⑤⑥⑦⑧t(Δt)性能計(jì)算：吞吐率（TP）：?jiǎn)挝粫r(shí)間輸出的結(jié)果數(shù)。TP=(輸出結(jié)果數(shù))/（完成算式總用時(shí)）

=8/12=2/3（條/Δt）而無(wú)流水時(shí)：TP=1/5（條/Δt）2）相關(guān)算式計(jì)算：S=a0+a1+a2+a3+a4+a5+a6+a7對(duì)相關(guān)算式要合理分解算式——盡量分解為少相關(guān)算式：①S0=a0+a1⑤S4=S0+S1②S1=a2+a3⑥S5=S2+S3③S2=a4+a5⑦S6=S4+S5④S3=a6+a7TP=7/18（條/Δt）效率（η）：即流水線上部件的利用率η=（作用區(qū)域面積）/（完成運(yùn)算所需時(shí)間矩形面積）

=（7*5Δt）/（18Δt*5）=7/18結(jié)論：相關(guān)發(fā)生時(shí)，對(duì)單條流水線而言會(huì)降低流水線性能。

2.時(shí)間匹配的非均勻流水線右圖所示乘法流水線完成計(jì)算:Mi=ai*bi(i=0~7)（也是不相關(guān)式子）1）①M(fèi)0=a0*b0…

⑧M7=a7*b72）畫出各算式在流水線上執(zhí)行過(guò)程示意圖3）性能:TP=8/13（個(gè)/Δt）

η=（8*6Δt）/（13Δt*6）=8/133.時(shí)間不匹配的非均勻流水線按右圖所示乘法流水線完成算式:

M=a0*a1*a2*a3*a4*a5*a6*a71）合理分解算式①M(fèi)0=a0*a1②M1=a2*a3③M2=a4*a5④M3=a6*a7⑤M4=M0*M1⑥M5=M2*M3⑦M(jìn)=M4*M51Δt2Δt4Δt33Δt

2)畫出時(shí)空?qǐng)D過(guò)程段

M0M1M2M3M4M5M

4321①②③④⑤⑥⑦①①①②②②③③③④④④⑤⑤⑤⑥⑥⑥⑦⑦⑦①②③④⑤⑥⑦①②③④⑤⑥⑦051015202527Δt3）性能

TP=7/27（個(gè)/Δt）

η=（7*6Δt）/（27Δt*4）=7/18§1重疊方式

重疊方式中所需時(shí)間的表達(dá)式推導(dǎo)及計(jì)算

解決條件轉(zhuǎn)移的全局相關(guān)

解決等待結(jié)果的數(shù)相關(guān)§2流水方式一、流水方式

重疊方式的2種等待流水線的分類用時(shí)\數(shù)據(jù)類型\規(guī)模\功能的多少\同一時(shí)刻送出支路數(shù)均勻流水線、非均勻流水線

二、流水線的執(zhí)行過(guò)程及性能評(píng)價(jià)均勻流水線:不相關(guān)算式\相關(guān)算式時(shí)間匹配的非均勻流水線:不相關(guān)算式時(shí)間不匹配的非均勻流水線:相關(guān)算式三、向量處理機(jī)與向量流水處理

1.向量處理機(jī)◆

向量處理機(jī)：具有向量數(shù)據(jù)表示及指令的流水線處理機(jī)。運(yùn)算速度常用每秒取得多少個(gè)浮點(diǎn)運(yùn)算結(jié)果表示機(jī)器速度,以MFLOPS(MillionofFloatingPointPerSecond)作為測(cè)量單位。

◆

標(biāo)量處理機(jī):

不具有向量數(shù)據(jù)表示和向量指令的處理機(jī)。運(yùn)算速度通常用每秒執(zhí)行多少指令表示機(jī)器速度，以MIPS(MillionInstructionsPerSecond)作為測(cè)量單位。

2.向量的處理方式

計(jì)算：fi=ai*bi+ci

（i=0~99）

設(shè)各向量元素分別放在大寫字母單元中:1）橫向（水平）處理

按照算式一個(gè)一個(gè)地進(jìn)行計(jì)算，即按行計(jì)算

第1步計(jì)算：f0=a0*b0+c0

LDR,A0MULR,B0ADDR,C0STR,F0

第2步計(jì)算：f1=a1*b1+c1

即將第一步中的腳標(biāo)0改為1，同樣用上述四條指令。

……直到第100步計(jì)算f99

優(yōu)點(diǎn)：作為工作單元的通用寄存器少（本例僅用一個(gè)R）

缺點(diǎn)：條條指令發(fā)生相關(guān)。2）縱向（垂直）處理

將所有算式列出后，按列進(jìn)行計(jì)算。

如對(duì)f0~

f99可分為4大步完成。

第1大步：取向量

LDR0,A0

：

LDR99,A99

第2大步：向量乘

MULR0,B0

：

MULR99,B99

第3大步：向量加

ADDR0,C0

：

ADDR99,C99LDR,A0MULR,B0ADDR,C0STR,F0第4大步：送結(jié)果

STR0,F0

：

STR99,F99優(yōu)點(diǎn)：解決了相關(guān)問(wèn)題，將原來(lái)?xiàng)l條發(fā)生相關(guān)改為條條不相關(guān)。缺點(diǎn)：在向量數(shù)據(jù)較多時(shí)，所用的寄存器數(shù)目多。

如本例共用了一百個(gè)寄存器（R0~R99），因而在向量數(shù)據(jù)不多時(shí)，可用縱向處理，而向量數(shù)據(jù)較多時(shí)，可用縱橫處理。

第1組，第2組，……第10組。組內(nèi)采用縱向處理，組間采用橫向處理。如第1組：取向量

LDR0,A0

：

LDR9,A9

向量乘

MULR0,B0

：

MULR9,B9基本思想：將所有向量算式分為若干組，如f0~f99可分為10個(gè)組：3）縱橫（分組）處理

向量加

ADDR0,C0

：

ADDR9,C9

送結(jié)果

STR0,F0

：

STR9,F9

其余各組與第1組類似，因而總共用了10個(gè)寄存器（R0~R9）

3.提高向量處理機(jī)性能的主要技術(shù)1)CRAY-1簡(jiǎn)介

◆

美國(guó)CRAY公司

◆

1976年

◆

每秒億次浮點(diǎn)運(yùn)算

◆

主頻：80MHz

◆字長(zhǎng)：64位3）向量寄存器組結(jié)構(gòu)

共有8個(gè)向量寄存器組（V0～V7），每個(gè)組可存放64個(gè)長(zhǎng)度為64位的二進(jìn)制數(shù)的向量數(shù)據(jù)。

2）CRAY-1向量指令類型

CRAY-1有標(biāo)量類和向量類指令128條，其中有4種向量類指令：◆

Vk←ViopVj

◆

Vk←SiopVj

◆

Vk←主存

◆

主存←Vi4）

CRAY-1的基本結(jié)構(gòu)5）CRAY-1向量指令

每個(gè)部件都以1τ(=10ns=10-8S)為單位的流水線結(jié)構(gòu)。

①邏輯運(yùn)算：②定點(diǎn)加：③移位：④浮點(diǎn)加：⑤訪存儲(chǔ)器：⑥浮點(diǎn)乘：⑦倒數(shù)：

此外，在功能部件和向量寄存器組之間相互傳送也用1τ。6）獨(dú)立總線結(jié)構(gòu)

每個(gè)向量寄存器組到每個(gè)功能部件之間都有單獨(dú)總線連接，在不沖突條件下，可實(shí)現(xiàn)功能部件之間并行運(yùn)行。

4.向量指令的執(zhí)行過(guò)程及性能計(jì)算

已知向量指令：V2←V1+V0（浮點(diǎn)加）

向量長(zhǎng)度為64，實(shí)際上是64組向量數(shù)據(jù)求和。1）寫出64組算式①V2.0←V1.0+V0.0②V2.1←V1.1+V0.1

…

64V2.63←V1.63+V0.63

2）畫出向量指令結(jié)構(gòu)圖（如右上圖所示）3）畫出各算式執(zhí)行過(guò)程示意圖送數(shù)1τ，加法6τ，輸出結(jié)果1τ，共8τ。4）完成運(yùn)算時(shí)間第一個(gè)結(jié)果時(shí)間+（長(zhǎng)度-1）τ=(1+6+1)τ+(64-1)τ=71τ5）向量數(shù)據(jù)處理速度計(jì)算

（向量指令條數(shù)*長(zhǎng)度）/（完成運(yùn)算用時(shí)）

=（1*64）/（71*10-8S）=90MFLOPS(每秒處理的浮點(diǎn)數(shù)個(gè)數(shù))

5.多條向量指令的執(zhí)行過(guò)程

若有多條向量指令，且可并行執(zhí)行時(shí)，完成運(yùn)算用時(shí)，可選用時(shí)最多的那條向量指令。如:V0←存儲(chǔ)器V3←V2×V1V5←1/V4

由于除法用時(shí)最長(zhǎng)，以它為準(zhǔn)。1+14+1+(64-1)=79(τ)3*64/(79*10-8S)≈244MFLOPS可并行執(zhí)行向量長(zhǎng)度為64四、向量的鏈接特性1.鏈接：當(dāng)兩條指令出現(xiàn)“寫后讀”相關(guān)時(shí)，若它們不存在沖突（源、目、功能部件），就可以通過(guò)向量寄存器組把所用的功能部件頭尾相接。將多條相關(guān)的向量指令鏈接起來(lái)組成更大規(guī)模的流水線，從而進(jìn)一步提高向量數(shù)據(jù)處理速度，這種鏈接稱為向量鏈接。2.向量指令之間的幾種鏈接情況1）既不相關(guān)，又無(wú)沖突

不能鏈接，但可并行執(zhí)行（執(zhí)行時(shí)間以最長(zhǎng)向量指令時(shí)間為準(zhǔn)）2）條條指令相關(guān)，且無(wú)沖突

可順利鏈接3）條條指令相關(guān)，但有沖突不能順利鏈接

執(zhí)時(shí)間往往需要推遲。3.可順利鏈接的情況有如下向量指令：

V0←存儲(chǔ)器;V2←V0+V1;V3←V2位移;V5←V3×V4;V7←1/V5

向量長(zhǎng)度64

相關(guān)：上一條向量指令的結(jié)果作下一條指令的一個(gè)源操作數(shù)（“寫后讀”相關(guān)）。1）畫出向量鏈接特性圖2）完成運(yùn)算用時(shí)

6+2+6+2+4+2+7+2+14+2+（64-1）=110(τ)3）計(jì)算向量數(shù)據(jù)處理速度：

5*64/(110*10-8S)≈291MFLOPS此處結(jié)論：相關(guān)在向量鏈接中有利于向量據(jù)處理速度的提高。4.不能順利鏈接的情況

有如下向量指令：

V0←存儲(chǔ)器;V2←V0×V1;V4←V2+V3;V5←V4位移;V7←1/V5;V0←V7×V1

故不能順利鏈接。1）不能順利鏈接時(shí)，對(duì)畫向量鏈接特性圖的影響

①源沖突：第一次送出畫實(shí)線，第二次送出畫虛線②目沖突：第一次接收畫實(shí)線，第二次接收畫虛線③功能部件沖突：第一次出現(xiàn)畫實(shí)線，第二次出現(xiàn)畫虛線向量長(zhǎng)度64，上述向量指令條條相關(guān)，有沖突：2）為了計(jì)算是否需要推遲時(shí)間，以及推遲多少時(shí)間，先計(jì)算沖突部件的有關(guān)時(shí)間。①源沖突：從第一次送出到第二次送出之間的時(shí)間②目沖突：從第一次接收到第二次接收之間的時(shí)間③功能塊：從第一次送出到第二次送入之間的時(shí)間源沖突（V1）1+7+1+1+6+1+1+4+1+1+14+1=39(τ)目沖突（V0）1+7+1+1+6+1+1+4+1+1+14+1+1+7+1=48(τ)功能部件（×）1+1+6+1+1+4+1+1+14+1=31(τ)V0沖突又分為表面沖突與實(shí)際沖突，如上例中，向量長(zhǎng)度為30時(shí)，僅表面沖突。說(shuō)明：乘法功能部件沖突最嚴(yán)重，上述三個(gè)時(shí)間以最短時(shí)間為準(zhǔn)（僅適用本例）。3）推遲時(shí)間計(jì)算：①當(dāng)長(zhǎng)度大于最短有關(guān)時(shí)間時(shí)，實(shí)際需要推遲時(shí)間為：

向量時(shí)間–

有關(guān)時(shí)間②當(dāng)長(zhǎng)度小于等于有關(guān)時(shí)間時(shí)，實(shí)際不用推遲，可視為表面沖突。本例推遲時(shí)間為：64-31=33（τ）4）完成運(yùn)算用時(shí)計(jì)算：順利連接時(shí)間+推遲時(shí)間1+6+1+1+7+1+1+6+1+1+4+1+1+14+1+1+7+1+（64-1）+33=152(τ)5）性能：6*64/（152*10-8S）≈253MFLOPS

三、向量流水處理

向量的處理方式向量指令的執(zhí)行過(guò)程及性能計(jì)算四、向量的鏈接特性

沖突:鄰近向量指令使用了同一個(gè)部件

沖突又分為表面沖突與實(shí)際沖突

向量鏈接特性圖的繪制

完成運(yùn)算用時(shí)計(jì)算：順利連接時(shí)間+推遲時(shí)間

有關(guān)時(shí)間、推遲時(shí)間的計(jì)算P19213題:在CRAY-1機(jī)上，在下列指令組中，組內(nèi)哪些指令可以鏈接？哪些不可以鏈接？不能鏈接的原因是什么？完成各指令所需的拍數(shù)（設(shè)向量長(zhǎng)度均為64,打入寄存器及啟動(dòng)功能部件各需1τ）。

（1）V0←存儲(chǔ)器(6τ);V1←V2+V3(6τ);V4←V5×V6(7τ)（2）V2←V0×V1;V3←存儲(chǔ)器;V4←V2+V3（3）V0←存儲(chǔ)器;V2←V0×V1;V3←V2+V0;V5←V3+V4（4）V0←存儲(chǔ)器;V1←1/V0(14τ);V3←V1×V2;V5←V3+V4解：（1）即不相關(guān)又無(wú)沖突——并行執(zhí)行（不可鏈接）1+7+1+（64-1）=72(τ)3*64/（72*10-8S）≈267MFLOPS（2）有相關(guān)，無(wú)沖突——可鏈接

1+7+1+1+6+1+（64-1）=80(τ)3*64/（80*10-8S）=240MFLOPS（3）條條指令相關(guān)，但有沖突——不能順利鏈接源沖突（V1）:1+7+1=9(τ)→推遲64-9=55τ

功能塊沖突（加）:1τ→推遲64-1=63τ

總推遲：55+63=118(τ)

1+6+2+7+2+6+2+6+1+（64-1）+118=214(τ)4*64/（214*10-8S）≈120MFLOPS

（4）條條相關(guān)，且無(wú)沖突——可順利鏈接

1+6+2+14+2+7+2+6+1+（64-1）=104(τ)4*64/（104*10-8S）≈246MFLOPS

五、加速比的概念

流水線方式相對(duì)于非流水線順序串行方式速度提高的比值稱加速比（Sp）。

概念延伸:某種流水處理機(jī)相對(duì)于另一種流水處理機(jī)的加速比。如超標(biāo)量流水處理機(jī)相對(duì)于常規(guī)標(biāo)量流水處理機(jī)的加速比。

設(shè)：流水線段數(shù)m，指令有n條，各段經(jīng)過(guò)的時(shí)間均為Δt

則：

線性流水線中各個(gè)段之間串行地鏈接，既無(wú)反饋也無(wú)跳躍，每個(gè)任務(wù)流經(jīng)流水線中各個(gè)段均只有一次，反之就是非線性流水線。

舉例流水線的調(diào)度問(wèn)題六、非線性流水線的調(diào)度

1234567S1×

×

×S2

×

×

S3

×

S4

×

×

時(shí)間流水線

非線性流水線的預(yù)約表延遲禁止表為：F={2，4，6}初始沖突向量為：C=（101010）調(diào)度方案平均延遲（1，7）4（3，5）4（5，3）4（5，7）6（5）5

（7）7上例中：延遲禁止表：F={2，4，6}

初始沖突向量：C=（101010）

狀態(tài)轉(zhuǎn)移圖及各種調(diào)度方案及其相應(yīng)的平均延遲表建立：由狀態(tài)轉(zhuǎn)移圖，從初始狀態(tài)開(kāi)始沿箭頭走向，構(gòu)成調(diào)度意義上延遲拍數(shù)成周期性重復(fù)出現(xiàn)的拍數(shù)循環(huán)。按此方案進(jìn)行任務(wù)調(diào)度，必然無(wú)沖突。123456789101112131415S4121233S3123S2121233S1121212333123456789101112131415S4112233S3123S2112233S1121123233（1，7）調(diào)度方案（3，5）調(diào)度方案

時(shí)鐘段號(hào)123456789S1××S2×××S3×

S4××S5××再看下圖所給出的預(yù)約表：

l段相隔8拍，那么兩個(gè)任務(wù)相隔8拍流入流水線必將會(huì)爭(zhēng)用1段；

2段相隔1、5、6拍，則相隔1、5或6拍流入流水線必將會(huì)爭(zhēng)用2段；

4段相隔1拍，兩個(gè)任務(wù)相隔1拍流入流水線必將會(huì)爭(zhēng)用4段；

5段相隔1拍，兩個(gè)任務(wù)相隔1拍流入流水線必將會(huì)爭(zhēng)用5段。由上圖的預(yù)約表可以得到相應(yīng)非線性流水線的延遲禁止表F為(1，5，6，8)。即要想不出現(xiàn)爭(zhēng)用流水線功能段的現(xiàn)象，相鄰兩個(gè)任務(wù)送入流水線的間隔拍數(shù)就不能為1、5、6、8拍，這些間隔拍數(shù)應(yīng)當(dāng)禁止使用。即有：

調(diào)度方案平均延遲（2，7）4.5（3，4）3.5（4，3）3.5（2,2,7）3.67（3，7）5（7）7（4,7）5.5延遲禁止表為：F={1，5，6，8}初始沖突向量為：C=（）狀態(tài)轉(zhuǎn)移圖及調(diào)度方案：(3,4,7）4.67(4,3,7）4.67

§3指令級(jí)高級(jí)并行超級(jí)處理機(jī)

超標(biāo)量處理機(jī)、超長(zhǎng)指令字處理機(jī)和超流水線處理機(jī)是指令級(jí)高度并行的三種不同的超級(jí)處理機(jī)。讓單處理機(jī)在每個(gè)時(shí)鐘周期里可同時(shí)解釋m（m>1）條指令，稱處理機(jī)并行的度為m。1.超標(biāo)量處理機(jī)是采用設(shè)置m條指令流水線同時(shí)并行處理，以實(shí)現(xiàn)度m(同時(shí)執(zhí)行m條指令)。2.超長(zhǎng)指令字處理機(jī)是將水平型微碼和超標(biāo)量處理相結(jié)合。在編譯時(shí)，將多個(gè)能并行執(zhí)行的不相關(guān)或無(wú)關(guān)的操作組合在一起，形成一條有多個(gè)操作碼字段的超長(zhǎng)指令字。運(yùn)行時(shí)，直接控制機(jī)器中多個(gè)相互獨(dú)立的功能部件并行操作，來(lái)實(shí)現(xiàn)同時(shí)執(zhí)行多條指令。VLIW中的操作字段：存/取浮點(diǎn)加浮點(diǎn)乘轉(zhuǎn)移3.超流水線處理機(jī)：一臺(tái)度為m的超流水線處理機(jī)的時(shí)鐘只是基本機(jī)器周期的1/m。[解]過(guò)程執(zhí)行

01234567891011121314(Δt)

圖1常規(guī)標(biāo)量流水處理機(jī)的時(shí)空?qǐng)D[例]指令由取指、譯碼和執(zhí)行三個(gè)過(guò)程組成。每個(gè)過(guò)程經(jīng)過(guò)的時(shí)間為Δt連續(xù)執(zhí)行12條指令。請(qǐng)分別畫出在常規(guī)標(biāo)量流水處理機(jī)及度m均為4的超標(biāo)量處理機(jī)、超長(zhǎng)指令字處理機(jī)、超流水線處理機(jī)上工作的時(shí)空?qǐng)D，分別計(jì)算出它們相對(duì)常規(guī)標(biāo)量流水處理機(jī)的加速比Sp。123456789101112123456789101112123456789101112譯碼取指

過(guò)程

481237112610159

4812371126101594812

371126