ICS第六章習(xí)題答案

習(xí)題

1.給出以下概念的解釋說明。

隨機存取存儲器（RAM）順序存取存儲器（SAM）直接存取存儲器（DAM）相聯(lián)存儲器（AM）

只讀存儲器（ROM）讀寫存儲器易失性存儲器記憶單元（cell）

存儲陣列（bank）編址單位編址方式最大可尋址范圍

讀出時間寫入時間存儲周期存儲器帶寬

靜態(tài)RAM(SRAM)動態(tài)RAM(DRAM)閃存（Flash存儲器）

行地址選通信號（RAS）列地址選通信號（CAS）超元(superceH)內(nèi)部行緩沖

磁盤驅(qū)動器磁盤控制器未格式化容量格式化容量

尋道時間旋轉(zhuǎn)（等待）時間數(shù)據(jù)傳輸時間平均存取時間

固態(tài)硬盤（SSD）多模塊交叉存儲高速緩存（cache）時間局部性

空間局部性主存塊cache行（槽）命中率

命中時間缺失率缺失損失直接映射

全相聯(lián)映射組相聯(lián)映射替換策略FIFO算法

LRU算法LRU位cache一■致性回寫法（write

back)

全寫法(writethrough)關(guān)聯(lián)度虛擬地址（邏輯地址）虛擬頁號

物理地址頁框（頁幀）物理頁號未分配頁

已分配頁未緩存頁已緩存頁請求分頁

頁故障(Pagefault)頁表頁表基址寄存器有效位（裝入

位）

修改位（臟位）訪問權(quán)限位快表（TLB）段表

段頁式特權(quán)指令特權(quán)模式內(nèi)核態(tài)（模式）

用戶態(tài)（模式）存儲保護地址越界訪問越權(quán)

2.簡單回答下列問題。

（1）計算機內(nèi)部為何要采用層次結(jié)構(gòu)存儲體系？層次結(jié)構(gòu)存儲體系如何構(gòu)成？

（2）SRAM芯片和DRAM芯片各有哪些特點？各自用在哪些場合？

（3）為什么采用地址對齊方式能減少數(shù)據(jù)訪問DRAM的時間？

（4）為什么在CPU和主存之間引入cache能提高CPU的訪存效率？

（5）為什么說cache對程序員來說是透明的？

（6）什么是cache映射的關(guān)聯(lián)度？關(guān)聯(lián)度與命中率、命中時間的關(guān)系各是什么？

（7）為什么直接映射方式不需要考慮替換策略？

（8）為什么要考慮cache的一致性問題？讀操作時是否要考慮cache的一致性問題？為什么？

（9）什么是物理地址？什么是邏輯地址？地址轉(zhuǎn)換由硬件還是軟件實現(xiàn)？為什么？

（10）什么是頁表？什么是快表（TLB）?

（11）在存儲器層次化結(jié)構(gòu)中，"cache-主存”、“主存湍盤，這兩個層次有哪些不同？

3.某計算機主存最大尋址空間為4GB,按字節(jié)編址，假定用64Mx8位的具有8個位平面的DRAM芯片

組成容量為512MB、傳輸寬度為64位的內(nèi)存條。

回答下列問題：

（1）每個內(nèi)存條需要多少個DRAM芯片？

（2）構(gòu)建容量為2GB的主存時，需要幾個內(nèi)存條？

（3）主存地址共有多少位？其中哪幾位用作DRAM芯片內(nèi)地址？哪幾位為DRAM芯片內(nèi)的行地址？哪

幾位為DRAM芯片內(nèi)的列地址？哪幾位用于選擇芯片？

參考答案：

(1)512MB/64MX8位=8片DRAM。

(2)2GB/512MB=4個內(nèi)存條。

(3)因為是按字節(jié)編址，所以主存地址共32位：A31A3,…Ak“AA,。因為每次在總線上傳輸64位數(shù)

據(jù)，因此，內(nèi)存條內(nèi)8個芯片同時進行讀寫，每個芯片有8個位平面，因而同時讀出64位數(shù)據(jù)。芯片按

交叉編址方式組織,每個內(nèi)存條有512MB容量，故內(nèi)存條內(nèi)存儲單元的地址有29位，即A28-A4A3A2A3A。。

其中，A2A3Ao表示芯片號，Az8…A4A3表示芯片內(nèi)存儲單元的地址。其中芯片內(nèi)的行地址為A28…AQ列

地址為A”…A3。

某計算機主存最大尋址空間為64KB,按字節(jié)編址，假定用1KX8位的DRAM芯片組成容量為16KB的內(nèi)

存條(主存模塊)。回答下列問題。

(1)每個內(nèi)存條需要多少DRAM芯片？

(2)構(gòu)建容量為48KB的主存時，需要幾個內(nèi)存條？

(3)主存地址共有多少位？其中哪幾位用作DRAM芯片內(nèi)地址？哪幾位為DRAM芯片內(nèi)的行地址？

哪幾位為DRAM芯片內(nèi)的列地址？

參考答案：

(1)16KB/1KX8位=16X1=16片DRAM。

(2)48KB/16KB=3個內(nèi)存條。

(3)因為是按字節(jié)編址，所以主存地址共16位：若每次在總線上傳輸8位數(shù)據(jù)，

則內(nèi)存條中16個芯片按連續(xù)編址方式組織，其中，Ar-AiA。用于DRAM芯片內(nèi)地址，A9-A5

為行地址，A「?A。為列地址。芯片內(nèi)各個存儲單元的排列如下圖所示，由此可見，在同一行中的

存儲單元是連續(xù)的，也即在行緩存中數(shù)據(jù)的地址是連續(xù)的。

031

0,31|

0,00,1

3263

1,0

9929931023

31-031,31

4.某計算機按字節(jié)編址，其中已配有0000H~7FFFH的ROM區(qū)域，現(xiàn)在再用16Kx4位的RAM芯片形

成32Kx8位的存儲區(qū)域，CPU地址線為A0~A15?；卮鹣铝袉栴}。

(DRAM區(qū)的地址范圍是什么？共需要多少RAM芯片？地址線中哪一位用來區(qū)分ROM區(qū)和RAM

區(qū)？

(2)假定CPU地址線改為24根，地址范圍0()00()0H~()07FFFH為ROM區(qū)，剩下的所有地址空間都

用16Kx4位的RAM芯片配置，則需要多少個這樣的RAM芯片？

參考答案：

(1)地址共16位，故存儲器地址空間為0000H?FFFFH,其中，8000H?FFFFH為RAM區(qū)，共

215=32K個單元，其空間大小為32KB,故需8KX4位的芯片數(shù)為32KB/8KX4位=4X2=8片。

因為ROM區(qū)在0000H?7FFFH,RAM區(qū)在8000H?FFFFH,所以可通過最高位地址A15來

區(qū)分，當A15為0時選中ROM芯片；為1時選中RAM芯片，此時，根據(jù)A14和A13進行譯

碼，得到4個譯碼信號，分別用于4組字擴展芯片的片選信號。(圖略，可參照圖4.15)

(2)若CPU地址線為24根，ROM區(qū)為000000H-007FFFH,則ROM區(qū)大小為32KB，總大小為

16MB=214KB=512X32KB,所以RAM區(qū)大小為511X32KB,共需使用RAM芯片數(shù)為5UX

32KB/8KX4位=511X4X2個芯片。

5.假設(shè)一個程序重復(fù)完成將磁盤上一個4KB的數(shù)據(jù)塊讀出，進行相應(yīng)處理后，寫回到磁盤的另外一個數(shù)

據(jù)區(qū)。各數(shù)據(jù)塊內(nèi)信息在磁盤上連續(xù)存放，數(shù)據(jù)塊隨機位于磁盤的一個磁道上。磁盤轉(zhuǎn)速為7200RPM,

平均尋道時間為10ms,磁盤最大內(nèi)部數(shù)據(jù)傳輸率為40MBps,磁盤控制器的開銷為2ms,沒有其他程

序使用磁盤和處理器，并且磁盤讀寫操作和磁盤數(shù)據(jù)的處理時間不重疊。若程序?qū)Υ疟P數(shù)據(jù)的處理需

要20000個時鐘周期，處理器時鐘頻率為500MHz,則該程序完成一次數(shù)據(jù)塊“讀出一處理一寫回”

操作所需的時間為多少？每秒鐘可以完成多少次這樣的數(shù)據(jù)塊操作？

參考答案：

磁盤轉(zhuǎn)一圈的時間為lO'QZOO/GOASJBms,故平均旋轉(zhuǎn)等待時間為8.33/2=4.17ms.

數(shù)據(jù)傳輸時間：0x4KB/40MBps=0.1024ms

平均存取時間T：控制器開銷+尋道時間+旋轉(zhuǎn)等待時間+數(shù)據(jù)傳輸時間

=2ms+10ms+4.17ms+0.1024ms=16.27ms

數(shù)據(jù)塊的處理時間：2000(V500MHz=0.04ms

完成一次數(shù)據(jù)塊的“讀出-處理-寫回”操作時間：16.27msx2+0.04ms=32.58ms

每秒中可以完成這樣的數(shù)據(jù)塊操作次數(shù)：1000ms/32.58ms=30次

6.現(xiàn)代計算機中，SRAM一般用于實現(xiàn)快速小容量的cache,而DRAM用于實現(xiàn)慢速大容量的主存。以

前超級計算機通常不提供cache,而是用SRAM來實現(xiàn)主存(如，Cray巨型機)，請問：如果不考慮

成本，你還這樣設(shè)計高性能計算機嗎？為什么？

參考答案：

不這樣做的理由主要有以下兩個方面：

①主存越大越好，主存大可使缺頁率降低，因而也就減少了訪問磁盤所需的時間。顯然用DRAM芯

片比用SRAM芯片構(gòu)成的主存容量大的多。

②程序訪問的局部性特點使得cache的命中率很高，因而，即使主存沒有用快速的SRAM芯片而是

用DRAM芯片，也不會影響到訪問速度。

7.對于數(shù)據(jù)的訪問，分別給出具有下列要求的程序或程序段的示例：

(1)幾乎沒有時間局部性和空間局部性

(2)有很好的時間局部性，但幾乎沒有空間局部性

(3)有很好的空間局部性，但幾乎沒有時間局部性

(4)空間局部性和時間局部性都好

參考答案：

可以給出許多類似的示例.例如，對于按行優(yōu)先存放在內(nèi)存的多維數(shù)組，如果按列優(yōu)先訪問數(shù)組元素，

則空間局部性就差，如果在一個循環(huán)體中某個數(shù)組元素只被訪問一次，則時間局部性就差。

假定二維數(shù)組a[1000][1000]按行優(yōu)先存放在內(nèi)存，以下給出的4個程序片段用于對數(shù)組a進行相應(yīng)的

處理，它們具有相同的功能，但數(shù)組訪問的時間局部性和空間局部性截然不同(不考慮編譯器的優(yōu)化)。

(1)時間局部性和空間局部性都好的程序片段。

for(i=0;i<1000;i++)

for(j=0;j<1000;j++){

sum=sum+a[i][j];

product=product*a[i][j];

square=square+a[i][j]*a[i][j];

2

(2)時間局部性好，空間局部性差

for0=0;j<1000;j++)

for(i=0;i<1000;i++){

sum=sum+a[i][j];

product=product*a[iJLj];

square=square+a[i][j]*a[i][j];

)

(3)空間局部性好，時間局部性差

for(i=0;i<1000;i++)

for(j=0;j<1000;j++)

sum=sum+a[i][j];

for(i=();i<1000;i++)

for(j=0;j<1000;j++)

product=product*a[i][j];

for(i=0;i<100();i++)

for(j=0;j<1000;j++)

square=square+a[i][j]*a[i][j];

(4)時間局部性和空間局部性都差

for(j=0;j<1000;j++)

for(i=0;i<1000;i++)

sum=sum+a[i][j];

for(j=0;j<1000;j++)

for(i=();i<1000;i++)

product=product*a[i][j];

for(j=0;j<1000;j++)

for(i=0;i<1000;i++)

square=square+a[i][j]*a[i][j];

8.假設(shè)某計算機主存地址空間大小為1GB,按字節(jié)編址，cache的數(shù)據(jù)區(qū)(即不包括標記、有效位等存儲

區(qū))有64KB,塊大小為128B,采用直接映射和全寫(write-through)方式?；卮鹣铝袉栴}。

(1)主存地址多少位？如何劃分？要求說明每個字段的含義、位數(shù)和在主存地址中的位置。

(2)cache的總?cè)萘繛槎嗌傥唬?/p>

參考答案：

(1)主存空間大小為1GB,按字節(jié)編址，說明主存地址為30位。cache共有64KB/128B=512行，因

此，行索引(行號)為9位；塊大小128字節(jié)，說明塊內(nèi)地址為7位。因此，30位主存地址中，

高14位為標志(Tag)；中間9位為行索引；低7位為塊內(nèi)地址。

(2)因為采用直接映射，所以cache中無需替換算法所需控制位，全寫方式下也無需修改(dirty)位，

而標志位和有效位總是必須有的，所以，cache總?cè)萘繛?12x(128x8+14+l)=519.5K位。

9.假設(shè)某計算機的cache共16行，開始為空，主存塊大小為1個字，采用直接映射方式，按字編址。CPU

執(zhí)行某程序時，依次訪問以下地址序列：2,3,11,16,21,13,64,48,19,11,3,22,4,27,6

和11。回答下列問題。

(1)訪問上述地址序列得到的命中率是多少？

(2)若cache數(shù)據(jù)區(qū)容量不變，而塊大小改為4個字，則上述地址序列的命中情況又如何？

參考答案

(1)cache采用直接映射方式，其數(shù)據(jù)區(qū)容量為16行xl字桁=16字；主存被劃分成1字膚，所以，

3

主存塊號=字號。因此，映射公式為：cache行號=主存塊號mod16=字號mod16。

開始cache為空，所以第一次都是miss,以下是映射關(guān)系(字號-cache行號)和命中情況。

2-2:miss,3-3:miss,11-11:miss,16-0:miss,21-5:miss,13-13:miss,64-0:miss、replace9

48-0:miss、replace?19-3:miss、replace,11-11:hit,3-3:miss、replace,22-6:miss,

4-4:miss,27-11:miss^replace,6-6:miss>replace>11-11:miss>replaceo

只有一次命中！

(2)cache采用直接映射方式，數(shù)據(jù)區(qū)容量不變，為16個字，每塊大小為4個字，所以，cache共有

4行；主存被劃分為4個字球，所以，主存塊號=[字號/4]。因此，映射公式為：cache行號=

主存塊號mod4=[字號/4]mod4。

以下是映射關(guān)系(字號?主存塊號?cache行號)和命中情況。

2-0-0:miss,3-0-0:hit,11-2-2:miss,16-44):miss、replace)21-5-l>13-3-3:miss,

64-16-0>48-12-(k19-4-0:miss,replaces11-2-2:hit,3-0-0:miss>replace,

22-5-1:hit,4?1-1:miss、replace,27-6-2:miss>replacet6-1-1:hit,11-2-2:miss>replace?

命中4次。

由此可見，塊變大后，能有效利用訪問的空間局部性，從而使命中率提高！

10.假設(shè)數(shù)組元素在主存按從左到右的下標順序存放，N是用#define定義的常量。試改變下列函數(shù)中循環(huán)

的順序，使得其數(shù)組元素的訪問與排列順序一致，并說明為什么在A較大的情況下修改后的程序比原

來的程序執(zhí)行時間更短。

intsum_array(inta[N][N][N])

{

inti,j,k,sum=0;

for(i=0;i<N;i++)

for(j=0;j<N;j++)

for(k=0;k<N;k++)sum+=a[k][i][j];

returnsum;

)

參考答案：

intsum_array(inta[N][N][N])

(

intLj,k,sum=0;

for(k=0;k<N;k++)

for(i=-i<N;i++)

for(j=0;j<N;j++)sum+=a[k][i][j];

returnsum;

}

修改后程序的數(shù)組元素的訪問與排列順序一致，使得空間局部性比原程序好，故執(zhí)行時間更短。

11.分析比較以下三個函數(shù)中數(shù)組訪問的空間局部性，并指出哪個最好，哪個最差？

4

#defineN1000#defineN1000#defineN1000

typedefstruct{typedefstruct{typedefstruct{

intvel[3];intvel[3];intvel[3];

intacc[3];intacc[3];intacc[3];

}point;}point;)point;

pointp[N];pointp[N];pointp[N];

voidclear1(point*p,intn)voidclear2(point*p,intn)voidclear3(point*p,intn)

({(

inti,j;inti,j;inti,j;

for(i=0;i<n;i++){for(i=0;i<n;i++){for(j=0;j<3;j++){

for(j=0;j<3;j++)for(j=0;j<3;j++){for(i=0;i<n;i++)

p[?]vel[jl=0;p[i].vel[j]=0;Pli]-vel[j]=0;

for(j=0;j<3;j++)p[ij.acc|jj=0;for(i=0;i<n;i++)

p|i].acc[j]=0;}p[i].acc[j]=0;

)})

)}1

參考答案：

對于函數(shù)clearl,其數(shù)組訪問順序與在內(nèi)存的存放順序完全一致，因此，空間局部性最好。

對于函數(shù)dearZ,其數(shù)組訪問順序在每個數(shù)組元素內(nèi)跳越式訪問，相鄰兩次訪問的單元最大相差

3個int型變量(假定si沈of(int)=4,則相當于12B),因此空間局部性比clearl差。若主存塊大小比

12B小的話，則大大影響命中率。

對于函數(shù)clear3,其數(shù)組訪問順序與在內(nèi)存的存放順序不一致，相鄰兩次訪問的單元都相差6個

int型變量(假定sizeof(int)=4,則相當于24B)因此，空間局部性比clear2還差。若主存塊大小比24B

小的話，則大大影響命中率。

12.以下是計算兩個向量點積的程序段：

floatdotproduct(floatx[8],floaty[8])

(

floatsum=0.0;

intL;

for(i=0;i<8;i++)sum+=x[i]*y[i];

returnsum;

)

回答下列問題或完成下列任務(wù)。

(1)試分析該段代碼中訪問數(shù)組X和y的時間局部性和空間局部性，并推斷命中率的高低。

(2)假設(shè)該段程序運行的計算機中的數(shù)據(jù)cache采用直接映射方式，其數(shù)據(jù)區(qū)容量為32B,主存塊大

小為16B；編譯程序?qū)⒆兞縮um和i分配給寄存器，數(shù)組x存放在0x8049040開始的主存區(qū)域，

數(shù)組y緊跟在x后?試計算該程序中數(shù)據(jù)訪問的命中率，要求說明每次訪問時cache的命中情況。

(3)將(2)中的數(shù)據(jù)cache改用2-路組相聯(lián)映射方式，主存塊大小改為8B,其他條件不變，則該程

序數(shù)據(jù)訪問的命中率是多少？

(4)在(2)中條件不變的情況下，將數(shù)組x定義為floatx[12],則數(shù)據(jù)訪問的命中率又是多少？

參考答案：

5

(1)數(shù)組x和y都按存放順序訪問，不考慮映射的情況下，空間局部性都較好，但都只被訪問一次,

故沒有時間局部性。命中率的高低與塊大小、映射方式等都有關(guān)，所以，無法推斷命中率的高

低。

(2)cache采用直接映射方式，塊大小為16字節(jié)，數(shù)據(jù)區(qū)大小為32字節(jié)，故cache共有2行。數(shù)組

x的8個元素(共32B)分別存放在主存40H開始的32個單元中，共有2個主存塊，其中xfOJ

~x[3]在第4塊，x[4卜xr7]在第5塊中；數(shù)組y的8個元素(共32B)分別在主存第6塊和第7

塊中。所以，x[0]~x[3]和y[0]~刑都映射至！|cache第0行；

x[4]~x[7]和y[4]~y⑺都映射至（Jcache第1行。

Cache第(13次循環(huán)第4-7次循環(huán)

第0行x[0-3],y[0-3]

第1行x[4-7],y[4-7]

每調(diào)入一塊，裝入4個數(shù)組元素，因為x|i]和y[i]總是映射到同一行，相互淘汰對方，故每次都

不命中，命中率為0.

(3)改用2路組相聯(lián)，塊大小為8B,則cache共有4行，每組兩行，共兩組。

數(shù)組x有4個主存塊，x[0]~x[l],x[2]-x[3],x[4]~x[5],x[6]~x[7]分別在第8~11塊中；

數(shù)組y有4個主存塊，y[0]~y[l]、y[2]~y[3],y[4]~y[5],.6]~y[7]分別在第12~15塊中；

cache第0行第1行

第0組x[0-l],x[4-5]y[0-l],y[4-S]

第1組x[2-3],x[6-7]y[2-3],y[6-7]

每調(diào)入一塊，裝入兩個數(shù)組元素，第二個數(shù)組元素的訪問總是命中，故命中率為5()%。

(4)若(2)中條件不變，數(shù)組x定義了12個元素，共有48B,使得y從第7塊開始，因而，x[i]和

y[i]就不會映射到同一個cache行中，即：x[0]~對3]在第4塊,x[4]~x[7]在第5塊，x[8]~x[U]

在第6塊中，y[0]~y[3]在第7塊，y[4]~x⑺在第8塊。

cache第0-3次循環(huán)第4-7次循環(huán)

第0行x[0?3]y[4-7]

第1行yl?-3]x[4-7]

每調(diào)入一塊，裝入4個數(shù)組元素，第一個元素不命中，后面3個總命中，故命中率為75%。

13.以下是對矩陣進行轉(zhuǎn)置的程序段：

typedefintarray[4][4];

voidtranspose(arraydst,arraysrc)

(

inti,j;

for(i=0;i<4;i++)

for(j=0;j<4;j++)dst[j][i]=src[i][j];

)

假設(shè)該段程序運行的計算機中sizeof(int)=4,且只有一級cache,其中LIdatacache的數(shù)據(jù)區(qū)大小為

32B,采用直接映射、回寫方式，塊大小為16B,初始為空。數(shù)組dsf從地址0x804c000開始存放，數(shù)

組src從地址0x804c010H開始存放。仿照例子填寫下表，說明數(shù)組元素src[row][coZ]和ds“row][coZ]

各自映射到cache哪一行，訪問是命中(hit)還是缺失(miss)。若LIdatacache的數(shù)據(jù)區(qū)容量改為

128B時，重新填寫表中內(nèi)容。

src數(shù)組dst數(shù)組

co/=0col=lcol-2col=3co/=0col=lcol-2col=3

0/miss

row=l

6

row=2

row=3

參考答案：

從程序來看，數(shù)組訪問過程如下:

src[0][()]>dst[O][0]>src[O][l]>dst[l][O]>src[O][2]>dst[2][()]>src[O][3]^dst[3][0]

src[l][0]>dst[O][1].src[l][1]^dst[l][1]>src[l]⑵、dst[2][l]>src[l][3]>dst[3][1]

src[2][Ohdst[O][2]>src[2][l]xdst[l][2].src[2][2]^dst[2][2]>src[2][3]>dst[3][2]

src[3]|0hdst[O][3].src[3][l]^dst[l][3]>src[3][2]>dst[2][3]、src[3][3]^dst(3][3]

因為塊大小為16B,每個數(shù)組元素有4個字節(jié)，所以4個數(shù)組元素占一個主存塊，因此每次總是

調(diào)入4個數(shù)組元素到cache的一行。

當數(shù)據(jù)區(qū)容量為32B時，LIdatacache中共有2行。數(shù)組元素dst[0][i]、dst[2][i]、src[0][i]、src[2][i]

(i=0?3)都映射到cache第0行，數(shù)組元素dst[l][i]、dst[3][i]、src[l](i]>src[3][i](i=0?3)都映射到

cache第1行。因此，從上述訪問過程來看，src[O][O]所在的一個主存塊(即存放src[O][i](i=0?3)四

個數(shù)組元素)剛調(diào)入cache后，dst[(川0]所在主存塊又把src[O][O]替換掉了?！?/p>

當數(shù)據(jù)區(qū)容量為128B時，L1由12?2(:?^中共有昭。數(shù)組元素小可()附、出1[1][“、dst[2ni]、dst[3][i]、

src[0][i],src[l][i],src⑵田、src[3][i](i=0?3)分別映射到cache第0、1、2、3、4,5、6、7行。因

此，不會發(fā)生數(shù)組元素的替換。每次總是第一個數(shù)組元素不命中，后面三個數(shù)組元素都命中。

src數(shù)組dst數(shù)組

32Bcol=0col=lcol=2col=3col=0col=lcol=2col=3

row=00/miss0/missO/hit0/miss0/miss0/miss0/miss0/miss

row=l1/miss1/hit1/miss1/hit1/miss1/miss1/miss1/miss

row=20/miss0/missO/hit0/miss0/miss0/miss0/miss0/miss

row=31/miss1/hit1/miss1/hit1/miss1/miss1/miss1/miss

src數(shù)組dst數(shù)組

128Bcol=0col=lcol=2col=3col=0col=lcol=2col=3

row=04/miss4/hit4/hit4/hit0/missO/hitO/hitO/hit

row=l5/miss5/hit5/hit5/hit1/miss1/hit1/hit1/hit

rovv=26/miss6/hit6/hit6/hit2/miss2/hit2/hit2/hit

row=37/miss7/hit7/hit7/hit3/miss3/hit3/hit3/hit

14.假設(shè)某計算機的主存地址空間大小為64MB,按字節(jié)編址。其cache數(shù)據(jù)區(qū)容量為4KB,采用4路

組相聯(lián)映射、LRU替換算法和回寫(writeback)策略，塊大小為64B。請問：

(1)主存地址字段如何劃分？要求說明每個字段的含義、位數(shù)和在主存地址中的位置。

(2)該cache的總?cè)萘坑卸嗌傥唬?/p>

(3)假設(shè)cache初始為空，CPU依次從0號地址單元順序訪問到4344號單元，重復(fù)按此序列共訪問16

次。若cache命中時間為1個時鐘周期，缺失損失為10個時鐘周期，則CPU訪存的平均時間為多

少時鐘周期？

參考答案：

(1)cache的劃分為：4KB=2"B=2'組x2?行閽字節(jié)有，所以，cache組號(組索引)占4位。

主存地址劃分為三個字段：高16位為標志字段、中間4位為組號、最低6位為塊內(nèi)地址。

即主存空間劃分為：64MB=2〃B=盧組群x24塊/組群x2”字節(jié)映

(2)cache共有64行，每行中有16位標志、1位有效位、1位修改(dirty地、2位LRU位，以及數(shù)

7

據(jù)64B.故總?cè)萘繛?4x(16+1+1+2+64x8)=34048位。

(3)因為每塊為64B,CPU訪問的單元范圍為0—4344,共4345個單元，4345/64=67.89,所以CPU

訪問的是主存前68塊(第0-67塊)，也即CPU的訪問過程是對前68塊連續(xù)訪問16次，總訪

存次數(shù)為16x4345=69520。

16次

II

0—a]>63—>64—>65—>[28—>4288—>—>4344—>4352

0#1#2#67#68#

cache共有16組，每組4行，采用LRU算法的替換情況如下圖所示：

笫。行第1行第2行第3行

。組0/64/4816/0/6432/1648/32

1組1/65/4917/1/6533/1749/33

2組2/66/5018/2/6634/1850/34

3組3/67/5119/3/6735/1951/35

4組4203652

15組15314763

根據(jù)圖中所示可知，第一次循環(huán)的每一塊只有第一次未命中，其余都命中；以后15次循環(huán)中，

有20塊的第一字未命中，其余都命中。所以命中率p為(69520-68-15x20)/69520=99.47%

平均訪存時間為：HitTime+(1-p)xMissPenalty

=l+10x(l-p)=1+0.0053x10=1.053個時鐘周期

15.假定某處理器可通過軟件對高速緩存設(shè)置不同的寫策略，那么，在下列兩種情況下，應(yīng)分別設(shè)置

成什么寫策略？為什么？

(1)處理器主要運行包含大量存儲器寫操作的數(shù)據(jù)訪問密集型應(yīng)用。

(2)處理器運行程序的性質(zhì)與(1)相同，但安全性要求很高，不允許有任何數(shù)據(jù)不一致的情況發(fā)生。

參考答案：

(1)采用writeback策略較好，可減少訪存次數(shù)。

(2)采用writethrough策略較好，能保證數(shù)據(jù)的一致性。

16.已知cache1采用直接映射方式，共1俯，塊大小為1個字，缺失損失為的時鐘周期；cache2也采

用直接映射方式，共4ff,塊大小為4個字，缺失損失為11個時鐘周期。假定開始時cache為空，采用

字編址方式。要求找出一個訪問地址序列，使得cache2A有更低的缺失率，但總的缺失損失反而比

cache1大。

參考答案：

假設(shè)cachel和cache2的缺失次數(shù)分別為x和y,根據(jù)題意，x和y必須滿足以下條件：

llxy>8xx且x>y,顯然，滿足該條件的x和y有許多，例如，x=4,y=3、x=5,y=4等等。

對于以下的訪問地址序列：0,1,4,8,cachel缺失4次，而cache2缺失3次；

對于以下的訪問地址序列：0,2,4,8,12,cachel缺失5次，而cache2缺失4次；

對于以下的訪問地址序列：0,3,4,8,12,16,20,cachel缺失7次，而cache2缺失6次；

如此等等，可以找出很多。

8

17.提高關(guān)聯(lián)度通常會降低缺失率，但并不總是這樣。請給出一個地址訪問序列，使得采用LRU替換

算法的2-路組相聯(lián)映射cache比具有同樣大小的直接映射cache的缺失率更高。

參考答案：

2-路組相聯(lián)cache的組數(shù)是直接映射cache的行數(shù)的一半，所以，可以找到一個地址序列A、B、C,

使得：A映射到某一個cache行，B和C同時映射到另一個cache行，并且A、B、C映射到同一個

cache組。這樣，如果訪存的地址序列為A、B、C、A、B、C、A、B、C則對于直接映射cache,

其命中情況為：miss/miss/miss/hit/miss/miss/hit/miss/miss/...命中率可達33.3%。

對于組相聯(lián)cache,因為A、B、C映射到同一個組，每組只有2行，采用LRU替換算法，所以，每

個地址處的數(shù)據(jù)剛調(diào)出cache就又被訪問到，每次都是miss,命中率為0。

例如：假定直接映射cache為4行xl字有，同樣大小的2?路組相聯(lián)cache為2組x2行/組xl字有

當訪問序列為：0、2,4、0、2、4、0、2,4、…(局部塊大小為3)時，則出現(xiàn)上述情況。

18.假定有三個處理器，分別帶有以下不同的cache：

cache1：采用直接映射方式，塊大小為1個字，指令和數(shù)據(jù)的缺失率分別為4%和6%；

cache2：采用直接映射方式，塊大小為4個字，指令和數(shù)據(jù)的缺失率分別為2%和4%；

cache3：采用2-路組相聯(lián)映射方式，塊大小為4個字，指令和數(shù)據(jù)的缺失率分別為2%和3%。

在這些處理器上運行同一個程序，其中有一半是訪存指令，在三個處理器上測得該程序的CPI都為2.0。

已知處理器1和2的時鐘周期都為420ps,處理器3的時鐘周期為450ps。若缺失損失為(塊大小+6)個時

鐘周期，請問：哪個處理器因cache缺失而引起的額外開銷最大？哪個處理器執(zhí)行速度最快？

參考答案：

假設(shè)所運行的程序共執(zhí)行N條指令，每條訪存指令僅讀寫一次內(nèi)存數(shù)據(jù)，則在該程序執(zhí)行過程中各處

理器因cache缺失而引起的額外開銷和執(zhí)行時間計算如下。

對于處理器1：

額外開銷為：Nx(4%+6%x50%)x(l+6)=0.49N個時鐘周期

執(zhí)行程序所需時間為：(NX2.0+0.49N)x420ps=1045.8Nps

對于處理器2：

額外開銷為：Nx(2%+4%x5()%)x(4+6)=0.40N個時鐘周期

執(zhí)行程序所需時間為：(Nx2.0+0.40N)x420ps=1008Nps

對于處理器3：

額外開銷為：Nx(2%+3%x50%)x(4+6)=0.35N個時鐘周期

執(zhí)行程序所需時間為：(Nx2.0+0.35N)x450ps=1057.5Nps

由此可見，處理器1的cache缺失引起的額外開銷最大，處理器2的執(zhí)行速度最快。

19.假定某處理器帶有一個數(shù)據(jù)區(qū)容量為256B的cache,其主存塊大小為32B。以下C語言程序段運行

在該處理器上，設(shè)si沈of(int)=4,編譯器將變量都分配在通用寄存器中，因此，只要考慮數(shù)組元

素的訪存情況。為簡化問題，假定數(shù)組a從一個主存塊開始處存放。若cache采用直接映射方式，則當

s=64和s=63時，缺失率分別為多少？若cache采用2路組相聯(lián)映射方式，則當s=64和s=63時，缺失率又

分別為多少？

inti,j,c,s,a[128];

for(i=0;i<10000;i++)

for(j=0;j<128;j=j+s)

c=a[j];

參考答案：

已知塊大小為32B,占8個數(shù)組元素，cache容量為256B=8行x32B/行，僅考慮數(shù)組訪問情況。

a[0卜a[7]在同一塊；a[8]~a[15底同一塊;……

9

a[0]~a[63]為前8塊(同一個塊群)

1)直接映射，s=64:訪存順序為a[0]>a[64],a[0],a[64]..共循環(huán)10000次。這兩個元素所在

的塊總是被映射到同一個cache行中，每次都會發(fā)生沖突，因此缺失率為100%。

因為a[0]所在塊號與a[64]所在塊號總是相差8,即模8同余。

2)直接映射，s=63:訪存順序為a[0]>a[63]、a[126],a[0]、a[63]、a[126],……共循環(huán)10000次。這

三個元素中后面兩個元素因為映射到同一個cache行中，因此每次都會發(fā)生沖突，而a[0]不會發(fā)生

沖突，故缺失率為67%。

因為a[63]所在塊號與a[126]所在塊號模8同余。

3)2■路組相聯(lián)，s=64:訪存順序為a[0],a[64],a[0]>a[64],共循環(huán)10000次。這兩個元素雖

然映射到同一個cache組中，但可以放在該組不同cache行中，所以不會發(fā)生沖突，缺失率大約為

0?

4)2■路組相聯(lián)，s=63:訪存順序為a[()]、a[63]、a[126],a[()ba[63]、a[126|,共循環(huán)10000次。

這三個元素中后面兩個元素雖映射到同一個cache組中，但可放在不同cache行中，而a[0]不會發(fā)

生沖突，故缺失率大約為0。

(假定s=32和s=31)

已知塊大小為32B,cache容量為256B=8行x32B/tf,僅考慮數(shù)組訪問情況。

1)直接映射，s=32:訪存順序為a[0],a[32]>a[64]、a[96],a(0]、a[32)共循環(huán)10000次。這

四個元素中a[0]和a[64],a[32]和a[96]被映射到同一個cache行中，每次都會發(fā)生沖突，因此缺失

率為100%.[0/8]mod8=[64/8]mod8=0,[32/8]mod8=[96/8]mod8=4

2)直接映射，s=31:訪存順序為a[0]>a[31],a[62]>a[93]>a[124],a[0]>a[31]>a[62]共循環(huán)

10000次。這五個元素中，a[31]和a[93]、a[62]和a[124]被映射到同一個cache行中，每次都會發(fā)

生沖突，而a[0]不會發(fā)生沖突，故缺失率為4/5=80%。

[0/8]mod8=0,[31/8]mod8=[93/8]mod8=3,[62/8]mod8=[124/8]mod8=7

3)2?路組相聯(lián)，s=相:訪存順序為a[0]>a[32],a[64],a網(wǎng),a⑼、a[32]……，共循環(huán)10000次。

這四個元素都映射到同一個cache組中，因為每組只有兩行，所以四個元素每次都會發(fā)生沖突，

缺失率大約為100%。

[0/8]mod4=[32/8]mod4=[64/8]mod4=[96/8]mod4=0

4)2■路組相聯(lián)，s=31:訪存順序為a[0]、a[31]>a[62]>a[93]、a[124],a[0]>a[31]>462],……共循

環(huán)1000()次。這五個元素中，后面四個元素都映射到同一個cache組中，雖可放在不同cache行中，

但只有兩行，故每次都發(fā)生沖突，而a[0]不會發(fā)生沖突，故缺失率為4/5=80%。

[0/8]mod4=0,[31/8]mod4=[62/8]mod4=[93/8]mod4=[124/8]mod4=