計算機系統(tǒng)結構課后習題四、五答案

習題四

1.教材P88存儲層次的訪問效率e計算公式。

e=TAi/(HTAI+(1-H)TA2)

eHTAI+e(l-H)TA2=TAI

HTAI+(1-H)TA2=TA./e

HTAI-HTA2=TAI/e-TA2

H(TAI-TA2)=TAI/e-TA2

H=TAI/e-TA2/(TAI-TA2)

H=TAI(1/e-TA2/TAI)/TAI(1-TA2/TAI)

H=(l/e-TA2/TAi)/(l-TA2/TAi)

把題意的條件帶入，命中率H=(l/e-TA2/TAI)/(1-TA2/TAI)

=(1/0.8-IO2/10"10-7)

=0.999999975

實際上，這樣高的命中率是極難達到的。

在主輔存之間增設一級存儲器，讓其速度介于主存輔存之間，讓主存與中間級的

訪問時間比為1：100,中間級與輔存之間的訪問時間比為1：1000,將它們配上

相應輔助軟硬件，組成一個三級存儲層次，這樣，可以使第1級主存的命中率降

低至！J

57

H=(l/0.8-10-5/10-7)/(i.io-/IO)

=0.997

1.教材P84每個存儲周期能訪問到的平均字數(shù)

B=(l-(1-X)m)/X=(l-O.7532)/0.25

心4

既每個存儲周期能訪問到的平均字數(shù)為4。

若將入=25%,m=16代入得

B=(l-(1-X)m)/X=(1-0.7516)/0.25

=3.96

既每個存儲周期能訪問到的平均字數(shù)為3.96o

可見，模數(shù)m不宜太大，否則性能改進不大。

3.教材P81。m個存儲體并行的最大頻寬Bn=W*m/T.,根據題意，實際

頻寬要低于最大頻寬。即實際頻寬W0.6最大頻寬。

4*106B/S^0.6*4B*m/(2*10-6s)

4WO.6*m*4/2

2W0.6*m

3.333Wm

m取2的幕，即m為4。

4.教材P91。根據題意，畫出頁表。

虛存頁號實頁號裝入位

031

111

220

330

421

510

601

700

⑴發(fā)生頁面失效的全部虛頁號就是頁映像表中所有裝入位為0的行所對應的虛

頁號的集合。本題為2,3,5,7o

⑵按以下虛地址計算主存實地址的情況列表

裝

存

虛地址頁內位移入實頁號頁內位移實地址

位

號

000130(3*1024+0)3072

3728(3*1024+656)36560頁面失效頁面失效無

1023(0*1024+1023)01023131023(3*1024+1023)4095

1024(1*1024+0)10110(1*1024+0)1024

2055(2*1024+7)270頁面失效頁面失效無

7800(7*1024+632)76320頁面失效頁面失效無

4096(4*1024+0)40120(2*1024+0)2048

6800(6*1024+656)665610656(0*1024+656)656

5.教材P93。圖4.14

⑴

用戶標志段號頁號頁內位移

段號2位，頁號2位，最多可以有4*4=16個虛頁。

（2）頁表和保護位如下表所示

段號段0段1段2段3

訪問方式只讀可讀/執(zhí)行可讀/寫/執(zhí)行可讀/寫

虛頁0所在位置實頁9在輔存上實頁14

虛頁1所在位置實頁3實頁0頁表不在實頁1

虛頁2所在位置在輔存上實頁15主存內實頁6

虛頁3所在位置實頁12實頁8在輔存上

實地址=實頁號*2］。頁內位移

方式段頁頁內位移段失效頁失效實頁號實地址保護失效

取數(shù)011無無33*2048+1=6145無

取數(shù)1110無無00*2048+10=10無

取數(shù)332047無有（在輔存）無無/

存數(shù)014無無33*2048+4=6148有（寫）

存數(shù)212有（無頁表）/無無/

存數(shù)1014無有（在輔存）無無/

轉移至此13100無無88*2048+100=16484無

取數(shù)0250無有（在輔存）無無/

取數(shù)205有/無無/

轉移至此3060無無1414*2048+60=28732有（執(zhí)行）

6.LRU算法、OPT算法都是堆棧型替換算法。教材P101。

453251322513

S(l)

453251322513

S(2)

45325133251

S(3)

4532511325

S(4)

443255132

S(5)

4444444

S(6)

n=lH

n=2H

n=3HH

n=4HHHHHHH

n=5HHHHHHH

時,S={2},A=2GS,所以命中。其余都不命中。

時898

,S=[2,3),A=2GS,所以命中。其余都不命中。

時898

,

S4={2,3,5},A5=5es4,所以命中。

S8={2,3,1},A9=2GS8,所以命中。其余都不命中。

n=4時，S4={2,3,5,4},A5=5GS4,所以命中。

Ss={2,3,5,4},A?=l不屬于Sj,所以不命中。

余類推。

儲擬結果表明，使用LRU算法替換，對該程序至少應分配4個實頁。

如果只分配3個實頁，命中率只有2/12,太低。

如果分配5個實頁，命中率雖有7/12,和分配4個實頁比較沒有增長。

7

7.ABCDE

-4-3

+20

0+1

當1=1時，B(1)=A(1)-C(1)=-4-(-3)=-loB(l)<0GOTO40E(l)=0

程序X的頁面地址流ACBE

ACDE

-4-1-30

+20

0+1

當1=2時，B(2)=A(2)-C(2)=+2-0=2OB(2)>0

D(2)=2*C(2)-A(2)=2*0-2=-2oD(2)WOGOTO40E(2)=0

程序X的頁面地址流ACBCADE

ABCDE

-4-1-30

+220-20

0+1

當1=3時，B(3)=A(3)-C(3)=0-1=-1。B(3)<0GOTO40E(3)=0

程序X的頁面地址流ACBE

01+T-0

0I-0Zz+

0￡■V

av

程序程序丫

XHxHyH

353/1510/156.5/15

448/1510/159/15

5310/154/157/15

程序X和程序丫各占4個頁最佳。

8.⑴畫出其虛、實地址經快表變換的邏輯結構示意圖I。教材P105。圖4.25

教材P106。圖4.26教材P107。圖4.27

①可對應1K個任務，即需要10位二進制表示，u需要10位。

②每個任務的程序空間最大可達4096頁。即需要12位二進制表示，NrN；需要

12位。

③只有4個任務在使用。容量為4行的相聯(lián)寄存器組。ID為2位二進制表示。

④實主存容量為22。，與虛地址Nr對應，實地址的％為12位二進制表示，實頁

號nv為20-12=8位二進制表示。

⑵由圖示可知，相聯(lián)寄存器組中的每個寄存器的相聯(lián)比較位數(shù)為u,需要10位。

⑶由圖示可知，相聯(lián)寄存器組中的每個寄存器的總位數(shù)為u+ID=12位。

⑷散列變換硬件的輸入位數(shù)為ID+Nv=2+12=14位。

快表的行數(shù)為32,即散列變換硬件的輸出位數(shù)為A=log232=5位。

⑸每個相等比較器的位數(shù)為

N'v+ID=12+2=14位。

⑹快表的總容量(位)為

快表的行數(shù)*(N\+ID+nv)*2=32*(12+2+8)*2=1408位。

9.⑴頁面大小為200字，主存容量為400字，可以知道實存頁數(shù)為2頁。根據

虛地址和頁面的關系，虛頁地址流為0,0,1,1,0,3,1,2,2,4,4,3o

由圖A7給出采用FIFO替換算法時的實際裝入和替換過程。其中，“*”標記的

是候選替換的虛頁頁號，H表示命中。

由圖A7計算可得主存的命中率H=6/12=0.5o

豌虹12022208214146618370490492868916728

虛頁地址

n=2

BA7頁面大小為200字、主存容量為帥字的鬟人常換過和

⑵頁面大小為100字，主存容量為400字，可以知道實存頁數(shù)為4頁。根據虛地

址和頁面的關系，虛頁地址流為0,0,2,2,1,6,3,4,4,8,9,7。

由圖A8給出采用FIFO替換算法時的實際裝入和替換過程。其中，“*”標記的

是候選替換的虛頁頁號，H表示命中。

由圖A8計算可得主存的命中率H=3/l2=0.25o

虛地址2022208214146618370490492868916728

圖A8頁面大小為100字，主存容量為400字的裝人漕換過程

⑶頁面大小為400字，主存容量為400字，可以知道實存頁數(shù)為1頁。根據虛地

址和頁面的關系，虛頁地址流為0,0,0,0,0,1,0,1,1,2,2,lo

由圖A9給出采用FIFO替換算法時的實際裝入和替換過程。其中，“*”標記的

是候選替換的虛頁頁號，H表示命中。

由圖A9計算可得主存的命中率H=6/l2=0.50

虛他址2022208214“6618370490492868'.

中嫩址00000101122'

E0000000HQ000

HHHHHH

用A9頁由大小為400國主存為枷字的頁面強人木快過顯

⑷由⑴⑵⑶的結果可以看出，當實存容量一定時?，頁面大小過小時，命中率H

較低。頁面大小增大后，命中率H會有所上升。

⑸頁面大小為200字，主存容量為800字，可以知道實存頁數(shù)為4頁。根據虛地

址和頁面的關系，虛頁地址流為0,0,1,1,0,3,1,2,2,4,4,3o

由圖A1O給出采用FIFO替換算法時的實際裝入和替換過程。其中，“*”標記的

是候選替換的虛頁頁號，H表示命中。

由圖A10計算可得主存的命中率H=7/l2=0.583o

可以看出，實存容量增大，命中率會有所上升。但不顯著。命中率提高趨于平緩。

虛地址2022

虞頁地址

10.⑴增大輔存容量，對主存命中率H不會有什么影響。

⑵增大主存容量較多，對主存命中率H有明顯提高的趨勢。增大主存容量

較少，命中率H可能略有增大，也可能不變，甚至會少許下降。

⑶因為前提是主存的命中率H很低，在增大主、輔存的頁面大小時，如果

增加量較小，主存命中率H可能沒有太大的波動。因為FIFO是非堆棧型的替換

算法，主存命中率H可能會有所增加，也可能降低或不變。而當頁面大小增加

量較大時，可能會出現(xiàn)兩種相反的情況。當原頁面大小較小時，在顯著增大了頁

面大小之后，一般會使主存命中率H有較大的提高。當原頁面大小已經較大時,

在顯著增大了頁面大小之后，由于在主存中的頁面數(shù)過少，將會使主存命中率H

繼續(xù)有所下降。

⑷頁面替換算法由FIFO改為LRU,一般會使主存命中率H提高。

⑸頁面替換算法由FIFO改為LRU,同時增大主存的容量（頁數(shù)），一般會

使主存命中率H有較大的提高。

⑹頁面替換算法由FIFO改為LRU,且增大頁面大小時，如果原先頁面大小很小,

則會使命中率H顯著上升，如果原先頁面大小已經很大了，因為主存頁數(shù)進一

步減少而使命中率H繼續(xù)有所下降。

11.教材P113-P116。圖4.37

單體4字■機存催暑

■■.37?■或■■立，的一種實現(xiàn)方式

⑴主存模4交叉，組號q為4位。映像表的行數(shù)為2。=24=16行。

映像表的總位數(shù)2q*(nd+s'+s)*4=16*(nd+s'+s)*4

Cache為1KB,主存大小為256KB,分成與Cache同樣大小的2nd個區(qū)，nd為8,

分體寬為32=4*8,s'=2。

⑵映像表的總位數(shù)2q*(nd+s'+s)*4=16*(nd+s'+s)*4=16*(8+2+2)*4=768位。

⑶每個比較電路的位數(shù)為na+s,=10位。

圖如上所示。

12.教材P114。圖4.35

⑴主存有8個塊，需要23個表示。Cache有4個塊，需要22個表示。

nd是主存區(qū)號，q是Cache組號，s'是Cache組內塊號，每組內塊數(shù)為2,用1

位表示。各占1位。如下圖所示。

1位1位1位

1位1位

圖A12題4-12的主存、Cache

地址字段的位數(shù)及對應關系

⑵主存、Cache空間塊的映像對應關系如圖所示。

主存的第0、1、4、5塊只可映像裝入或替換掉物理Cache中的第0、1塊的內容。

主存的第2、3、6、7塊只可映像裝入或替換掉物理Cache中的第2、3塊的內容。

主存塊號

0

>0組

1

>0區(qū)

2

,1組

3

V

4

,0組

5卜區(qū)

6

,1組

7

12的主存、Cache空間塊的映像關系

⑶程序運行時，由給出的主存塊地址流可以得到Cache中各個塊的使用狀況，如

下表所示。*表示候選替換塊的塊號。

t=l時，主存塊地址為1,只能裝入或替換掉物理Cache中的第0塊的內容。

t=2時，主存塊地址為2,只能裝入或替換掉物理Cache中的第2塊的內容。主

存塊地址為1的內容還在Cache中的第0塊中。

t=3時，主存塊地址為4,只能裝入或替換掉物理Cache中的第1塊的內容。主

存塊地址為1的內容還在Cache中的第0塊中。主存塊地址為2的內容還在Cache

中的第2塊中。，在這3個進入物理Cache中的塊中，主存塊地址為1的最少使

用，因此用*表示它是候選替換塊的塊號。

t=4時，主存塊地址為1,只能裝入或替換掉物理Cache中的第0塊的內容。原

來Cache中的第0塊的內容就是主存塊地址為1的內容，因此命中。

⑷發(fā)生Cache塊失效又發(fā)生塊爭用的時刻就是按照最少使用原則替換時的時刻。

即t=6,7,9,10,11,12,14,15o

(5)Cache塊命中率為Hc=3/15=0.2。

13.⑴增大主存容量，對Cache塊命中率He基本不影響。

⑵增大Cache中的塊數(shù)，而塊的大小不變，意味著增大Cache容量，由于

LRU替換算法是堆棧型的替換算法，所以，將使He上升，從而使ta縮短。ta縮

短是否明顯，還要看當前He處在什么水平上。如果原有Cache中的塊數(shù)較少，

He較低，則ta會因He迅速提高而顯著縮短。如果原有Cache中的塊數(shù)較多，Hc

已經較高了，則增大Cache中的塊數(shù)，不會使He再有明顯提高，此時ta縮短就

不明顯了。

⑶增大組相聯(lián)組的大小，塊的大小不變，從而使組內的塊數(shù)有了增加，它

會使塊沖突概率下降，這也會使Cache塊替換次數(shù)減少。而當Cache各組組內的

位置已全部裝滿了主存的塊之后，塊替換次數(shù)減少就意味著He的提高。所以，

增大組的大小能使He提高，從而可提高等效訪問速度。不過，Cache存儲器的

等效訪問速度改進是否明顯，還要看當前He處在什么水平上。如果原有組內的

塊數(shù)較少，增大組的大小，會明顯使ta縮短。如果原有組內的塊數(shù)較多，增大組

的大小，ta縮短就不明顯了。

(4)o組的大小和Cache總容量不變，增大Cache塊的大小，其對ta影響的

分析大致與⑶相同，會使ta縮短，但要視目前的He水平而定。如果He已經很高

了，則增大Cache塊的大小對ta的改進也就不明顯了。

⑸。提高Cache本身器件的訪問速度，即減小L只有當命中率He已經很

高時，才會顯著縮短ta。如果He命中率較低時，對減小ta的作用也就不明顯了。

14.兩種建議都存在盲目性。在做決定之前，應先實測一個程序運行過程中ta

的值，將它與第一級物理Cache的tc比較。如果兩者已經非常接近了，表示He

已經趨于1,這時只有全部更換Cache芯片，使k下降來解決。如果先看

Cache存儲器內部是否已經將查映像表和訪Cache安排成流水方式工作。如果未

采取流水，則可改成流水。在改成流水方式后，如ta仍大于tc,且有一定差距時，

表明He過低。此時，應設法提高He?？上日{整塊的大小，組內的塊數(shù)，讓它們

在Cache容量不增大的情況下，適當取大些，以提高He。在此基礎上，尚不能

達到要求時，就應購買一些同樣速度的Cache芯片，對其物理Cache的容量進行

擴充。這樣，將會使He提高，而顯著縮短ta。

習題五

1.⑴計算執(zhí)行完100條指令所需要的時間：

①順序方式工作時為：教材P125。圖5.2(a)

100*(t取指+t分析+t執(zhí)行)

②僅”執(zhí)行「與”取指k+i”重疊方式工作時為：

t取指+100*t分析+99*max{t取指.t執(zhí)行}+t執(zhí)行

③僅“執(zhí)行廣、”分析k+i”與“取指k+J'重疊方式工作時為：

教材P126。圖5.2(b)

t取指+max{t取指.t分析}+98*max{t取指.t分析.t執(zhí)行}+max{t分析.t執(zhí)行}+t執(zhí)行

⑵當t取指=t分析=2,t執(zhí)行=1時，代入上面的各式，可以求得執(zhí)行完100條指令所需

要的時間是：順序方式工作時為500；僅“執(zhí)行」與"取指k+J'重疊方式工作

時為401；僅“執(zhí)行。'、”分析k+i”與“取指k+i”重疊方式工作時為203。

當t取指=t執(zhí)行=5,t分析=2時，代入上面的各式，可以求得執(zhí)行完100條指令所需要

的時間是：順序方式工作時為1200；僅“執(zhí)行」與"取指k+i”重疊方式工作

時為705；僅”執(zhí)行「、”分析k+i”與“取指k+i”重疊方式工作時為510。

2.按題意可得4個功能部件流水時的時空關系如圖所示。

3.按圖5-35(a)組織，實現(xiàn)A*B*C*D的時空關系如圖所示。

規(guī)格化

尾乘

階加

A，B

C:D

輸出A-BCD

圖A15按圖5-35(a)流水的時空圖

吞吐率為：Tp=3/13At在13At時間內流出3個結果。

效率為：n=(3*5At)/(3*13At)=5/13陰影區(qū)面積(3*5△t)和全部3

個段的總時空面積(3*13At)之比

按圖5-35(b)組織，實現(xiàn)A*B*C*D的時空關系如圖所示。

部件

輸入匕3產產

II

輸出A-BCD

圖A16按圖5-35(b)流水的時空圖

吞吐率為：Tp=3/llAt在11At時間內流出3個結果。

效率為：n=(3*5At)/(5*11At)=5/11陰影區(qū)面積(3*5At)和全部5

個段的總時空面積(5*1lAt)之比

教材P136-P137。圖5.21(a)(b)

4.按((((A+A)+(A+A))+(A+A))+(A+A))+(A+A)))流水的時空如圖

所示。

段

4

3

2

一時間

170(ns)

4?附

/ij4AfA94+4;4+4;4?4

444??右（4；州4。

I;?};10

4%”5+4j/和叫

/j+44+44?44~4Mio

—1^1——

—

由圖可知，流水最少時間為170ns。

5.提高流水線效率，消除速度瓶頸主要有將瓶頸段再細分以及重復設置多個瓶頸

段并聯(lián)工作，給其輪流分配任務的兩種途徑。

⑴在3段流水線，各段經過時間依次為At,3At,At的情況下，連續(xù)流入3

條指令時，將n=3,m=3,Ati=At,At2=3At,At3=△t,2X3=3At代入，可

得吞吐率Tp和效率n為:教材P137和P139o

而連續(xù)流入30條指令時，只需將上面式子的n改為30,其他參數(shù)不變，得

(2)若采取將2段細分成3個子段，每個子段均為△t,構成的流水線結構如圖所

ZjsO

缶A/A/A/M

段1段2段3

圖A182段細分成3段

連續(xù)流入3條指令時，將n=3,m=5,At尸43=41代入，可得吞吐率Tp和效率

n為：

3?g△/

7=5X7AZ

連續(xù)流入30條指令時，只需將上面式子的n改為30,其他參數(shù)不變，得

若采取將3個2段并聯(lián)構成的流水線，其構成如圖所示。

圖A193個2段子過程并聯(lián)

連續(xù)流入3條指令和30條指令時的實際吞吐率Tp和效率n分別和子過程細分的

相同。

⑶將⑴題中n=3和n=30的計算結果進行比較可以看出，只有當連續(xù)流入流水線

的指令越多時，流水線的實際吞吐率Tp和效率n才會提高。

將⑴⑵題的計算結果進行比較可以看出，無論采用瓶頸子過程再細分，還是將多

個瓶頸子過程并聯(lián)來消除流水線瓶頸，都只有當連續(xù)流入流水線的指令越多時，

流水線的實際吞吐率Tp和效率n才會提高。若連續(xù)流入流水線的指令數(shù)太少，

消除流水線瓶頸雖可以提高流水線的實際吞吐率Tp,而效率n卻可能下降。從

0.45下降為0.43o

6.根據題意，對算法經過調整后，能使流水吞吐率盡量高的流水時空圖如圖所

示。

可以看出，完成全部運算的時間為24At。在此期間的流水線效率為

n=(6*4At+3*4At)/(4*24At)=3/8陰影區(qū)面積(6*4At+3*4At)和全

部4個段的總時空面積(4*24AI)

之比

如果現(xiàn)在將瓶頸子過程2和3均細分成兩個子過程，則時空圖如圖所示。

由圖可見，完成全部運算的時間為18At。

在此期間的流水線效率為

n=(6*4At+3*4At)/(6*18At)=1/3陰影區(qū)面積(6*4△t+3*4△t)和全

部6個段的總時空面積(6*18At)

之比

由圖可見，完成全部運算的時間為18At。

在此期間的流水線效率為

n=(6*4At+3*4At)/(6*18At)=1/3陰影區(qū)面積(6*4At+3*4△t)和全

部6個段的總時空面積(6*18At)

之比

7.⑴乘法部件和加法部件不能同時工作，部件內也只能順序方式工作時的時空

圖如圖所示。教材P139-P140。圖5.23(a)(b)計算向量點積。

長度為8,意味要先做8次乘法。每次乘法需5拍。

即aibi>a2b2、a3b3、34b4、a5b5、a6b6、a7b7、a8b8。

再做7次加法。每次加法需5拍。

即a1bI+a2b2+a3b3+a4b4+a5b5+a6b6+a7b7+a8b8。

由圖可知，完成全部運算最少為：

8*5+7*5=75拍。

⑵乘法部件和加法部件能同時工作的時空圖如圖所示。

解題算法步驟為：

(((((((aibi+a2b2)+a3b3)+a4b4)+a5b5)+a6b6)+a7b7)+a8b8)

圖A24乘、加部件可并行的時空關系圖

由圖可知，完成全部運算為45拍。8次乘法和7次加法有重疊。

⑶處理器有乘、加雙功能靜態(tài)流水線，完成點積運算的流水時空圖如圖所示。

解題算法步驟為：

(((aibi+a2b2)+(a3b3+0464))+((asbs+aebg)+(a7b7+a8b8)))

乘、加均由5個流水段構成，每段經過時間為1拍。

每段先做8次乘法，五段均一次重疊。做完12拍。

aibna2b2、a3b3、a4b4、a5b5、36b6、a7b7、a8b8。與⑴乘法部件和加法部件不能同

時工作比較，做完40拍。

再做4次加法，五段均一次重疊。做完8拍。

(aibi+a2b2)(a3b3+a4b4)(a5b5+a6b6)(a7b7+a8b8)

再做2次加法，做完7拍。

(aibi+a2b2)+(a3b3+a4b4))(a5b5+a6b6)+(a7b7+a8b8)

其中(aibi+a2b2)+(a3b3+a4b4)可以在第五段的(aibi+a2b2)(a3b3+a4b4)完成

時開始。(有重疊)(第18拍開始)

(a5b5+a6b6)+(a7b7+a8b8)只能在第五段的(a5b5+a6b6)(a7b7+asb8)完成時開

始。(第20拍開始)

最后1次加法，做完5拍。

由圖可知，完成全部運算為30拍。

⑷乘、加兩條流水線可同時工作，完成點積運算的流水時空圖如圖所示。

解題算法步驟為：

(((aibi+a2b2+(a7b7))+(a5b5+a6b6))+((a3b3+a4b4)+a8b8))

每段先做8次乘法，五段均一次重疊。做完12拍。

(ab+a2b2)在第五段乘法輸出時，開始相加。(第7拍開始，第11拍結束)

(aibi+a2b2)在第五段相加結束時,與(a7b7)第五段乘法輸出時(第11拍結束)

開始相加。(第12拍開始，第16拍結束)

(aibi+a2b2)+(a7b7)在第五段相加結束時，與(a5b5+a6b6)第五段加法輸出時

(第15拍結束)開始相加。(第16拍開始，第20拍結束)

其余類推。

由圖可知，完成全部運算為26拍。

8.教材P142-P144。圖5.25。

采用流水控制的方法是總線式分布處理。

解決流水控制的途徑如下：

⑴在各個寄存器中設置忙位標志來判斷是否相關。當寄存器正在使用時，置該寄

存器的忙位標志為“1”；當寄存器被釋放時，其忙位標志清為“0”。因此，訪問

寄存器時，先看忙位標志，如為“1”，表示相關(不能使用)。教材P143。

⑵設置多條流水線，讓它們并行地工作，同時在分布于各流水線的入、出端上分

別設置若干個保存站來緩沖存放信息。一旦相關后，采用異步方式流動。教材

P142o

⑶通過分布設置的站號來控制相關專用通路的連接。教材P143。

⑷相關專用通路采用總線方式，相關后通過更改站號來實現(xiàn)不同相關專用通路的

連接。

解決流水控制的特點：

⑴不必對進入流水線各條指令的源操作數(shù)地址和目的操作數(shù)地址做兩兩配對的

比較，就可判知是否發(fā)生了相關。所以，相關判斷的控制大大簡化。教材P142。

⑵對于異步流動的先寫后讀、先讀后寫及寫-寫三類相關都能很方便且不加區(qū)分

地予以解決。教材P144。

⑶相關專用通路采用總線方式，使該通路可以為各種相關所共用，大大簡化了硬

件。教材P143。

⑷多條流水線采取異步并行，且多條相關的指令可以一直鏈接下去，使系統(tǒng)有高

的性能。

對預約表中各個行中打的拍數(shù)求出差值，并將這些差值匯集在一起，就可

得到延遲禁止表。教材P147-P148。

第一段Si相隔8拍。

第二段S2相隔1拍。

第三段S相隔3、4、1拍。

第四段S4相隔1拍。

第五段S5相隔1拍。

即延遲禁止表F={1,3,4,8)

由延遲禁止表F可轉換得初始沖突向量C=(10001101)

根據初始沖突向量可畫出狀態(tài)轉移圖如圖所示。

由于初始沖突向量的C2c5c6c7為0,所以第二個任務可以距第一個任務2、5、6、

7拍流入流水線。

第二個任務在間隔2拍時流入流水線，對第一個任務而言初始沖突向量右移2

位成了(00100011)。新的沖突向量應該是第一個任務當前的沖突向量(00100011)

和第二個任務的初始沖突向量(10001101)的按位“或”，其結果為

(00100011)

+(10001101)

10101111狀態(tài)轉移圖左下角

第二個任務在間隔5拍時流入流水線，對第一個任務而言初始沖突向量右移5

位成了(00000100)。新的沖突向量應該是第一個任務當前的沖突向量(00000100)

和第二個任務的初始沖突向量(10001101)的按位“或”，其結果為

(00000100)

+(10001101)

10001101狀態(tài)轉移圖右上角

第二個任務在間隔6拍時流入流水線，對第一個任務而言初始沖突向量右移6

位成了(00000010)。新的沖突向量應該是第一個任務當前的沖突向量(00000010)

和第二個任務的初始沖突向量(10001101)的按位“或。其結果為

(00000010)

+(10001101)

10001111狀態(tài)轉移圖右下角

第二個任務在間隔7拍時流入流水線，對第一個任務而言初始沖突向量