計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)課后習(xí)題四、五答案

習(xí)題四

1.教材P88存儲(chǔ)層次的訪問效率e計(jì)算公式。

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

實(shí)際上，這樣高的命中率是極難達(dá)到的。

在主輔存之間增設(shè)一級(jí)存儲(chǔ)器，讓其速度介于主存輔存之間，讓主存與中間級(jí)的

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

相應(yīng)輔助軟硬件，組成一個(gè)三級(jí)存儲(chǔ)層次，這樣，可以使第1級(jí)主存的命中率降

低至！J

57

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

=0.997

1.教材P84每個(gè)存儲(chǔ)周期能訪問到的平均字?jǐn)?shù)

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

心4

既每個(gè)存儲(chǔ)周期能訪問到的平均字?jǐn)?shù)為4。

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

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

=3.96

既每個(gè)存儲(chǔ)周期能訪問到的平均字?jǐn)?shù)為3.96o

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

3.教材P81。m個(gè)存儲(chǔ)體并行的最大頻寬Bn=W*m/T.,根據(jù)題意，實(shí)際

頻寬要低于最大頻寬。即實(shí)際頻寬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。根據(jù)題意，畫出頁表。

虛存頁號(hào)實(shí)頁號(hào)裝入位

031

111

220

330

421

510

601

700

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

頁號(hào)的集合。本題為2,3,5,7o

⑵按以下虛地址計(jì)算主存實(shí)地址的情況列表

裝

存

虛地址頁內(nèi)位移入實(shí)頁號(hào)頁內(nèi)位移實(shí)地址

位

號(hào)

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

⑴

用戶標(biāo)志段號(hào)頁號(hào)頁內(nèi)位移

段號(hào)2位，頁號(hào)2位，最多可以有4*4=16個(gè)虛頁。

（2）頁表和保護(hù)位如下表所示

段號(hào)段0段1段2段3

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

虛頁0所在位置實(shí)頁9在輔存上實(shí)頁14

虛頁1所在位置實(shí)頁3實(shí)頁0頁表不在實(shí)頁1

虛頁2所在位置在輔存上實(shí)頁15主存內(nèi)實(shí)頁6

虛頁3所在位置實(shí)頁12實(shí)頁8在輔存上

實(shí)地址=實(shí)頁號(hào)*2］。頁內(nèi)位移

方式段頁頁內(nèi)位移段失效頁失效實(shí)頁號(hào)實(shí)地址保護(hù)失效

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

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

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

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

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

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

轉(zhuǎn)移至此13100無無88*2048+100=16484無

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

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

轉(zhuǎn)移至此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

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

時(shí)898

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

時(shí)898

,

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

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

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

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

余類推。

儲(chǔ)擬結(jié)果表明，使用LRU算法替換，對(duì)該程序至少應(yīng)分配4個(gè)實(shí)頁。

如果只分配3個(gè)實(shí)頁，命中率只有2/12,太低。

如果分配5個(gè)實(shí)頁，命中率雖有7/12,和分配4個(gè)實(shí)頁比較沒有增長(zhǎng)。

7

7.ABCDE

-4-3

+20

0+1

當(dāng)1=1時(shí)，B(1)=A(1)-C(1)=-4-(-3)=-loB(l)<0GOTO40E(l)=0

程序X的頁面地址流ACBE

ACDE

-4-1-30

+20

0+1

當(dāng)1=2時(shí)，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

當(dāng)1=3時(shí)，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個(gè)頁最佳。

8.⑴畫出其虛、實(shí)地址經(jīng)快表變換的邏輯結(jié)構(gòu)示意圖I。教材P105。圖4.25

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

①可對(duì)應(yīng)1K個(gè)任務(wù)，即需要10位二進(jìn)制表示，u需要10位。

②每個(gè)任務(wù)的程序空間最大可達(dá)4096頁。即需要12位二進(jìn)制表示，NrN；需要

12位。

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

④實(shí)主存容量為22。，與虛地址Nr對(duì)應(yīng)，實(shí)地址的％為12位二進(jìn)制表示，實(shí)頁

號(hào)nv為20-12=8位二進(jìn)制表示。

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

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

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

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

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

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

⑹快表的總?cè)萘?位)為

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

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

虛地址和頁面的關(guān)系，虛頁地址流為0,0,1,1,0,3,1,2,2,4,4,3o

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

是候選替換的虛頁頁號(hào)，H表示命中。

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

豌虹12022208214146618370490492868916728

虛頁地址

n=2

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

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

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

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

是候選替換的虛頁頁號(hào)，H表示命中。

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

虛地址2022208214146618370490492868916728

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

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

址和頁面的關(guān)系，虛頁地址流為0,0,0,0,0,1,0,1,1,2,2,lo

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

是候選替換的虛頁頁號(hào)，H表示命中。

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

虛他址2022208214“6618370490492868'.

中嫩址00000101122'

E0000000HQ000

HHHHHH

用A9頁由大小為400國(guó)主存為枷字的頁面強(qiáng)人木快過顯

⑷由⑴⑵⑶的結(jié)果可以看出，當(dāng)實(shí)存容量一定時(shí)?，頁面大小過小時(shí)，命中率H

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

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

址和頁面的關(guān)系，虛頁地址流為0,0,1,1,0,3,1,2,2,4,4,3o

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

是候選替換的虛頁頁號(hào)，H表示命中。

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

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

虛地址2022

虞頁地址

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

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

較少，命中率H可能略有增大，也可能不變，甚至?xí)僭S下降。

⑶因?yàn)榍疤崾侵鞔娴拿新蔋很低，在增大主、輔存的頁面大小時(shí)，如果

增加量較小，主存命中率H可能沒有太大的波動(dòng)。因?yàn)镕IFO是非堆棧型的替換

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

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

面大小之后，一般會(huì)使主存命中率H有較大的提高。當(dāng)原頁面大小已經(jīng)較大時(shí),

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

繼續(xù)有所下降。

⑷頁面替換算法由FIFO改為L(zhǎng)RU,一般會(huì)使主存命中率H提高。

⑸頁面替換算法由FIFO改為L(zhǎng)RU,同時(shí)增大主存的容量（頁數(shù)），一般會(huì)

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

⑹頁面替換算法由FIFO改為L(zhǎng)RU,且增大頁面大小時(shí)，如果原先頁面大小很小,

則會(huì)使命中率H顯著上升，如果原先頁面大小已經(jīng)很大了，因?yàn)橹鞔骓摂?shù)進(jìn)一

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

11.教材P113-P116。圖4.37

單體4字■機(jī)存催暑

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

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

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

Cache為1KB,主存大小為256KB,分成與Cache同樣大小的2nd個(gè)區(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位。

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

圖如上所示。

12.教材P114。圖4.35

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

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

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

1位1位1位

1位1位

圖A12題4-12的主存、Cache

地址字段的位數(shù)及對(duì)應(yīng)關(guān)系

⑵主存、Cache空間塊的映像對(duì)應(yīng)關(guān)系如圖所示。

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

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

主存塊號(hào)

0

>0組

1

>0區(qū)

2

,1組

3

V

4

,0組

5卜區(qū)

6

,1組

7

12的主存、Cache空間塊的映像關(guān)系

⑶程序運(yùn)行時(shí)，由給出的主存塊地址流可以得到Cache中各個(gè)塊的使用狀況，如

下表所示。*表示候選替換塊的塊號(hào)。

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

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

存塊地址為1的內(nèi)容還在Cache中的第0塊中。

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

存塊地址為1的內(nèi)容還在Cache中的第0塊中。主存塊地址為2的內(nèi)容還在Cache

中的第2塊中。，在這3個(gè)進(jìn)入物理Cache中的塊中，主存塊地址為1的最少使

用，因此用*表示它是候選替換塊的塊號(hào)。

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

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

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

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

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

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

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

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

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

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

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

不明顯了。

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

會(huì)使塊沖突概率下降，這也會(huì)使Cache塊替換次數(shù)減少。而當(dāng)Cache各組組內(nèi)的

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

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

等效訪問速度改進(jìn)是否明顯，還要看當(dāng)前He處在什么水平上。如果原有組內(nèi)的

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

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

(4)o組的大小和Cache總?cè)萘坎蛔儯龃驝ache塊的大小，其對(duì)ta影響的

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

了，則增大Cache塊的大小對(duì)ta的改進(jìn)也就不明顯了。

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

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

14.兩種建議都存在盲目性。在做決定之前，應(yīng)先實(shí)測(cè)一個(gè)程序運(yùn)行過程中ta

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

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

Cache存儲(chǔ)器內(nèi)部是否已經(jīng)將查映像表和訪Cache安排成流水方式工作。如果未

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

表明He過低。此時(shí)，應(yīng)設(shè)法提高He?？上日{(diào)整塊的大小，組內(nèi)的塊數(shù)，讓它們

在Cache容量不增大的情況下，適當(dāng)取大些，以提高He。在此基礎(chǔ)上，尚不能

達(dá)到要求時(shí)，就應(yīng)購(gòu)買一些同樣速度的Cache芯片，對(duì)其物理Cache的容量進(jìn)行

擴(kuò)充。這樣，將會(huì)使He提高，而顯著縮短ta。

習(xí)題五

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

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

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

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

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

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

教材P126。圖5.2(b)

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

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

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

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

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

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

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

2.按題意可得4個(gè)功能部件流水時(shí)的時(shí)空關(guān)系如圖所示。

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

規(guī)格化

尾乘

階加

A，B

C:D

輸出A-BCD

圖A15按圖5-35(a)流水的時(shí)空?qǐng)D

吞吐率為：Tp=3/13At在13At時(shí)間內(nèi)流出3個(gè)結(jié)果。

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

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

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

部件

輸入匕3產(chǎn)產(chǎn)

II

輸出A-BCD

圖A16按圖5-35(b)流水的時(shí)空?qǐng)D

吞吐率為：Tp=3/llAt在11At時(shí)間內(nèi)流出3個(gè)結(jié)果。

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

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

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

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

所示。

段

4

3

2

一時(shí)間

170(ns)

4?附

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

444??右（4；州4。

I;?};10

4%”5+4j/和叫

/j+44+44?44~4Mio

—1^1——

—

由圖可知，流水最少時(shí)間為170ns。

5.提高流水線效率，消除速度瓶頸主要有將瓶頸段再細(xì)分以及重復(fù)設(shè)置多個(gè)瓶頸

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

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

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

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

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

(2)若采取將2段細(xì)分成3個(gè)子段，每個(gè)子段均為△t,構(gòu)成的流水線結(jié)構(gòu)如圖所

ZjsO

缶A/A/A/M

段1段2段3

圖A182段細(xì)分成3段

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

n為：

3?g△/

7=5X7AZ

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

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

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

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

相同。

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

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

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

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

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

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

0.45下降為0.43o

6.根據(jù)題意，對(duì)算法經(jīng)過調(diào)整后，能使流水吞吐率盡量高的流水時(shí)空?qǐng)D如圖所

示。

可以看出，完成全部運(yùn)算的時(shí)間為24At。在此期間的流水線效率為

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

部4個(gè)段的總時(shí)空面積(4*24AI)

之比

如果現(xiàn)在將瓶頸子過程2和3均細(xì)分成兩個(gè)子過程，則時(shí)空?qǐng)D如圖所示。

由圖可見，完成全部運(yùn)算的時(shí)間為18At。

在此期間的流水線效率為

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

部6個(gè)段的總時(shí)空面積(6*18At)

之比

由圖可見，完成全部運(yùn)算的時(shí)間為18At。

在此期間的流水線效率為

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

部6個(gè)段的總時(shí)空面積(6*18At)

之比

7.⑴乘法部件和加法部件不能同時(shí)工作，部件內(nèi)也只能順序方式工作時(shí)的時(shí)空

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

長(zhǎng)度為8,意味要先做8次乘法。每次乘法需5拍。

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

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

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

由圖可知，完成全部運(yùn)算最少為：

8*5+7*5=75拍。

⑵乘法部件和加法部件能同時(shí)工作的時(shí)空?qǐng)D如圖所示。

解題算法步驟為：

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

圖A24乘、加部件可并行的時(shí)空關(guān)系圖

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

⑶處理器有乘、加雙功能靜態(tài)流水線，完成點(diǎn)積運(yùn)算的流水時(shí)空?qǐng)D如圖所示。

解題算法步驟為：

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

乘、加均由5個(gè)流水段構(gòu)成，每段經(jīng)過時(shí)間為1拍。

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

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

時(shí)工作比較，做完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)完成

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

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

始。(第20拍開始)

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

由圖可知，完成全部運(yùn)算為30拍。

⑷乘、加兩條流水線可同時(shí)工作，完成點(diǎn)積運(yùn)算的流水時(shí)空?qǐng)D如圖所示。

解題算法步驟為：

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

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

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

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

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

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

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

其余類推。

由圖可知，完成全部運(yùn)算為26拍。

8.教材P142-P144。圖5.25。

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

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

⑴在各個(gè)寄存器中設(shè)置忙位標(biāo)志來判斷是否相關(guān)。當(dāng)寄存器正在使用時(shí)，置該寄

存器的忙位標(biāo)志為“1”；當(dāng)寄存器被釋放時(shí)，其忙位標(biāo)志清為“0”。因此，訪問

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

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

別設(shè)置若干個(gè)保存站來緩沖存放信息。一旦相關(guān)后，采用異步方式流動(dòng)。教材

P142o

⑶通過分布設(shè)置的站號(hào)來控制相關(guān)專用通路的連接。教材P143。

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

連接。

解決流水控制的特點(diǎn)：

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

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

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

地予以解決。教材P144。

⑶相關(guān)專用通路采用總線方式，使該通路可以為各種相關(guān)所共用，大大簡(jiǎn)化了硬

件。教材P143。

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

的性能。

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

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

第一段Si相隔8拍。

第二段S2相隔1拍。

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

第四段S4相隔1拍。

第五段S5相隔1拍。

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

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

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

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

7拍流入流水線。

第二個(gè)任務(wù)在間隔2拍時(shí)流入流水線，對(duì)第一個(gè)任務(wù)而言初始沖突向量右移2

位成了(00100011)。新的沖突向量應(yīng)該是第一個(gè)任務(wù)當(dāng)前的沖突向量(00100011)

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

(00100011)

+(10001101)

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

第二個(gè)任務(wù)在間隔5拍時(shí)流入流水線，對(duì)第一個(gè)任務(wù)而言初始沖突向量右移5

位成了(00000100)。新的沖突向量應(yīng)該是第一個(gè)任務(wù)當(dāng)前的沖突向量(00000100)

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

(00000100)

+(10001101)

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

第二個(gè)任務(wù)在間隔6拍時(shí)流入流水線，對(duì)第一個(gè)任務(wù)而言初始沖突向量右移6

位成了(00000010)。新的沖突向量應(yīng)該是第一個(gè)任務(wù)當(dāng)前的沖突向量(00000010)

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

(00000010)

+(10001101)

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

第二個(gè)任務(wù)在間隔7拍時(shí)流入流水線，對(duì)第一個(gè)任務(wù)而言初始沖突向量