《計算機體系結構》第五章課件

利用堆棧技術模擬

LRU在不同n條件下頁面變化時空圖及命中率。LRU算法的實現(xiàn)方法:

堆棧法、比較對法§4存貯體系的兩個分支虛擬存貯器的簡單工作過程

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

組相聯(lián)映象的例子頁面替換時空圖主存地址到Cache地址的變換

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

主存

NdqsNrq’s’nr

Cache

2）

主存頁號1位1位1位1位1位

3)可放入Cache0組的主存塊號:0145

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

t=6,7,9,10,11,12,14,155)tA=H*tc+(1-H)*tm=0.2*2+0.8*15=12.4(ns)時間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#命中情況失失失中失爭爭中爭爭爭爭中爭爭[例]考慮一個920個字的程序，其訪問輔存的地址流為20，22，208，214，146，618，370，490，492，868，916，728。

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

[解]虛頁號＝└虛地址／頁面大小┘

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

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

下圖給出了采用FIFO替換算法替換時的實際裝入和替換過程。其中，“#”標記的是候選替換的虛頁頁號，下劃線表示命中。

t虛地址頁面流

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

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

交叉訪問的存儲器

主存儲器由多個模塊構成。 假設主存儲器包含m=2a個存儲器模塊，每個模塊包含w=2b個存儲單元（字），則總存儲容量為

1）低位交叉方式

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

2）高位交叉方式

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

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

將存儲器周期稱為主周期，細分為m個小周期（m稱為交叉存取度），如8路交叉，m=8，w=8，a=b=3，設為主周期，為小周期，則

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

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

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

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

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

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

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

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

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

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

（a）確定上述存儲器組織的地址構成。

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

設計1：1個存儲體16路交叉。

a)地址構成：存儲器地址寄存器(24位)b）帶寬為0?！?0位4位設計2：2個存儲體8路交叉。

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

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

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

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

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

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

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

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

第五章重疊、流水和向量處理機

§1重疊方式一、重疊解釋方式1.一條指令的幾個過程段

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

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

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

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

只有在前一條指令的各過程段全部完成后，才從存儲器取出下一條指令。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í)

若指令的過程段劃分更多時，重疊組合方式更多。

重疊解釋并不能加快一條指令的實現(xiàn)，但能加快一段程序的解釋。3.重疊方式中所需時間表達式及所需時間計算1）條件：設一條指令分為三個過程段，各過程段分別用t取、t譯、t執(zhí)表示。執(zhí)行K條指令，分別采用順序執(zhí)行、兩條重疊、三條重疊。2）分別列出上述三種執(zhí)行方式所需時間表達式順序執(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)例子

當k=200，t取=3Δt，t譯=4Δt，t執(zhí)=5Δt，時，分別計算上述三種執(zhí)行方式的時間。順序執(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.重疊方式需要解決的問題1）對存儲器的頻繁訪問①有哪些訪問：取指令、取操作數(shù)、存放執(zhí)行結果,I/O通道訪問.②希望存儲器為多體結構，以適應多種訪問源的需要。③當存儲器為單體結構時，需要將訪問源排隊，先后順序為：取指令、取數(shù)據(jù)、I/O通道訪問、存結果2）應具有先行控制部件①

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

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

Ⅱ）先行指令站，用來存放多條指令；

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

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

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

后行部件：對指令執(zhí)行后的結果進行處理的器件，稱

后行部件。包括：

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

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

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

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

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

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

如計算A=B﹡CifA＜0GoTon

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

LDR，AADDR，BSUBR，C

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

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

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

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

譯執(zhí)取譯

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

重迭方式未按時間單位來劃分過程段，比較粗糙。

3流水線上對各過程段進行時間匹配的辦法。

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

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

Ⅰ）時間匹配的非均勻流水線。

Ⅱ）時間不匹配的非均勻流水線。

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

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

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

時－空圖

時－空圖從時間和空間兩個方面描述了流水

線的工作過程。時－空圖中，橫坐標代表時間，

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

…⑧S7=a7+b7

畫出各算式在流水線上執(zhí)行過程時空圖

S0

S1S2S3S4

S5S6S7

過程段①②③④⑤⑥⑦⑧①②③④⑤⑥⑦⑧123456789101112①②③④⑤⑥⑦⑧①②③④⑤⑥⑦⑧54321①②③④⑤⑥⑦⑧t(Δt)性能計算：吞吐率（TP）：單位時間輸出的結果數(shù)。TP=(輸出結果數(shù))/（完成算式總用時）

=8/12=2/3（條/Δt）而無流水時：TP=1/5（條/Δt）2）相關算式計算：S=a0+a1+a2+a3+a4+a5+a6+a7對相關算式要合理分解算式——盡量分解為少相關算式：①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ū)域面積）/（完成運算所需時間矩形面積）

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

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

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

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

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

2)畫出時空圖過程段

M0M1M2M3M4M5M

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

TP=7/27（個/Δt）

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

重疊方式中所需時間的表達式推導及計算

解決條件轉移的全局相關

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

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

二、流水線的執(zhí)行過程及性能評價均勻流水線:不相關算式\相關算式時間匹配的非均勻流水線:不相關算式時間不匹配的非均勻流水線:相關算式三、向量處理機與向量流水處理

1.向量處理機◆

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

◆

標量處理機:

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

2.向量的處理方式

計算：fi=ai*bi+ci

（i=0~99）

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

按照算式一個一個地進行計算，即按行計算

第1步計算：f0=a0*b0+c0

LDR,A0MULR,B0ADDR,C0STR,F0

第2步計算：f1=a1*b1+c1

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

……直到第100步計算f99

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

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

將所有算式列出后，按列進行計算。

如對f0~

f99可分為4大步完成。

第1大步：取向量

LDR0,A0

：

LDR99,A99

第2大步：向量乘

MULR0,B0

：

MULR99,B99

第3大步：向量加

ADDR0,C0

：

ADDR99,C99LDR,A0MULR,B0ADDR,C0STR,F0第4大步：送結果

STR0,F0

：

STR99,F99優(yōu)點：解決了相關問題，將原來條條發(fā)生相關改為條條不相關。缺點：在向量數(shù)據(jù)較多時，所用的寄存器數(shù)目多。

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

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

LDR0,A0

：

LDR9,A9

向量乘

MULR0,B0

：

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

向量加

ADDR0,C0

：

ADDR9,C9

送結果

STR0,F0

：

STR9,F9

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

3.提高向量處理機性能的主要技術1)CRAY-1簡介

◆

美國CRAY公司

◆

1976年

◆

每秒億次浮點運算

◆

主頻：80MHz

◆字長：64位3）向量寄存器組結構

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

2）CRAY-1向量指令類型

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

Vk←ViopVj

◆

Vk←SiopVj

◆

Vk←主存

◆

主存←Vi4）

CRAY-1的基本結構5）CRAY-1向量指令

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

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

此外，在功能部件和向量寄存器組之間相互傳送也用1τ。6）獨立總線結構

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

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

已知向量指令：V2←V1+V0（浮點加）

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

…

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

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

（向量指令條數(shù)*長度）/（完成運算用時）

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

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

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

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

不能鏈接，但可并行執(zhí)行（執(zhí)行時間以最長向量指令時間為準）2）條條指令相關，且無沖突

可順利鏈接3）條條指令相關，但有沖突不能順利鏈接

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

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

向量長度64

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

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

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

有如下向量指令：

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

故不能順利鏈接。1）不能順利鏈接時，對畫向量鏈接特性圖的影響

①源沖突：第一次送出畫實線，第二次送出畫虛線②目沖突：第一次接收畫實線，第二次接收畫虛線③功能部件沖突：第一次出現(xiàn)畫實線，第二次出現(xiàn)畫虛線向量長度64，上述向量指令條條相關，有沖突：2）為了計算是否需要推遲時間，以及推遲多少時間，先計算沖突部件的有關時間。①源沖突：從第一次送出到第二次送出之間的時間②目沖突：從第一次接收到第二次接收之間的時間③功能塊：從第一次送出到第二次送入之間的時間源沖突（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沖突又分為表面沖突與實際沖突，如上例中，向量長度為30時，僅表面沖突。說明：乘法功能部件沖突最嚴重，上述三個時間以最短時間為準（僅適用本例）。3）推遲時間計算：①當長度大于最短有關時間時，實際需要推遲時間為：

向量時間–

有關時間②當長度小于等于有關時間時，實際不用推遲，可視為表面沖突。本例推遲時間為：64-31=33（τ）4）完成運算用時計算：順利連接時間+推遲時間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í)行過程及性能計算四、向量的鏈接特性

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

沖突又分為表面沖突與實際沖突

向量鏈接特性圖的繪制

完成運算用時計算：順利連接時間+推遲時間

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

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

1+7+1+1+6+1+（64-1）=80(τ)3*64/（80*10-8S）=240MFLOPS（3）條條指令相關，但有沖突——不能順利鏈接源沖突（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）條條相關，且無沖突——可順利鏈接

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

五、加速比的概念

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

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

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

則：

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

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

1234567S1×

×

×S2

×

×

S3

×

S4

×

×

時間流水線

非線性流水線的預約表延遲禁止表為：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)轉移圖及各種調(diào)度方案及其相應的平均延遲表建立：由狀態(tài)轉移圖，從初始狀態(tài)開始沿箭頭走向，構成調(diào)度意義上延遲拍數(shù)成周期性重復出現(xiàn)的拍數(shù)循環(huán)。按此方案進行任務調(diào)度，必然無沖突。123456789101112131415S4121233S3123S2121233S1121212333123456789101112131415S4112233S3123S2112233S1121123233（1，7）調(diào)度方案（3，5）調(diào)度方案

時鐘段號123456789S1××S2×××S3×

S4××S5××再看下圖所給出的預約表：

l段相隔8拍，那么兩個任務相隔8拍流入流水線必將會爭用1段；

2段相隔1、5、6拍，則相隔1、5或6拍流入流水線必將會爭用2段；

4段相隔1拍，兩個任務相隔1拍流入流水線必將會爭用4段；

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

調(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)轉移圖及調(diào)度方案：(3,4,7）4.67(4,3,7）4.67

§3指令級高級并行超級處理機

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

01234567891011121314(Δt)

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

過程

481237112610159

4812371126101594812

371126