計(jì)算機(jī)組織與系統(tǒng)結(jié)構(gòu)第四章習(xí)題答案

1、第4章習(xí)題答案3.已知某機(jī)主存空間大小為 64KB，按字節(jié)編址。要求：(1) 若用1KX4位的SRAM芯片構(gòu)成該主存儲(chǔ)器，需要多少個(gè)芯片？(2) 主存地址共多少位？幾位用于選片？幾位用于片內(nèi)選址？(3) 畫出該存儲(chǔ)器的邏輯框圖。參考答案：(1) 64KB / 1K X4 位=64 >2 = 128 片。(2) 因?yàn)槭前醋止?jié)編址，所以主存地址共16位，6位選片，10位片內(nèi)選址。(3) 顯然，位方向上擴(kuò)展了 2倍，字方向擴(kuò)展了 64倍。下圖中片選信號(hào) CS為高電平有效。A9AoDoWEA 15D7A 104. 用64KX1位的DRAM 芯片構(gòu)成 256KX8位的存儲(chǔ)器。要求：(1) 計(jì)算所需

2、芯片數(shù)，并畫出該存儲(chǔ)器的邏輯框圖。(2) 若采用異步刷新方式，每單元刷新間隔不超過2ms,則產(chǎn)生刷新信號(hào)的間隔是多少時(shí)間？若采 用集中刷新方式，則存儲(chǔ)器刷新一遍最少用多少讀寫周期？參考答案：(1) 256KB / 64K>1位=4冷=32片。存儲(chǔ)器邏輯框圖見下頁(圖中片選信號(hào)CS為高電平有效)。(2) 因?yàn)槊總€(gè)單元的刷新間隔為2ms,所以，采用異步刷新時(shí)，在2ms內(nèi)每行必須被刷新一次，且僅被刷新一次。因?yàn)镈RAM芯片存儲(chǔ)陣列為 64K=256X 256,所以一共有256行。因此，存儲(chǔ)器 控制器必須每隔 2ms/256=7.8聞產(chǎn)生一次刷新信號(hào)。采用集中刷新方式時(shí)，整個(gè)存儲(chǔ)器刷新一 遍需要

3、256個(gè)存儲(chǔ)(讀寫)周期，在這個(gè)過程中，存儲(chǔ)器不能進(jìn)行讀寫操作。YoA 16A15AoDRAM 64K*1 CS DRAM 64K*1cSDRAM 64K*1J+cSDRAM64K*1JDRAM64K*1DRAM64K*1DRAM64K*1DRAM64K*1-CSDRAM64K*1csDRAM 64K*1DRAM64K*1CSDRAM64K*1DRAM64K*1DRAM64K*1D7Do5.用8KX8位的EPROM芯片組成32KX16位的只讀存儲(chǔ)器，試問：（1）數(shù)據(jù)寄存器最少應(yīng)有多少位？（ 2）地址寄存器最少應(yīng)有多少位？（3）共需多少個(gè)EPROM芯片？（ 4）畫出該只讀存儲(chǔ)器的邏輯框圖。參考答

4、案：（1）數(shù)據(jù)寄存器最少有 16位。（2）地址寄存器最少有：15位（若按16位的字編址）；16位（若按字節(jié)編址）。（3） 共需要 32KX 16 位 / 8K >8 位=4 >2 = 8 片。（4） 該只讀存儲(chǔ)器的邏輯框圖如下（假定按字編址，圖中片選信號(hào)CS為高電平有效）A 14A 13A12AoDl5D8D7DoWEYo6.某計(jì)算機(jī)中已配有 0000H7FFFH的ROM區(qū)域，現(xiàn)在再用8K>4位的RAM 芯片形成32KX8位的存 儲(chǔ)區(qū)域，CPU地址總線為A0-A15 ,數(shù)據(jù)總線為D0-D7,控制信號(hào)為R/W# （讀/寫）、MREQ# （訪存）。 要求說明地址譯碼方案，并畫出R

5、OM芯片、RAM芯片與CPU之間的連接圖。假定上述其他條件不變，只是CPU地址線改為24根，地址范圍000000H007FFFH為ROM區(qū)，剩下的所有地址空間都 用8KX4位的RAM芯片配置，則需要多少個(gè)這樣的RAM芯片？參考答案：CPU地址線共16位，故存儲(chǔ)器地址空間為 0000HFFFFH ,其中，8000HFFFFH 為RAM 區(qū),15共2 =32K個(gè)單元，其空間大小為 32KB，故需8KX4位的芯片數(shù)為 32KB/8K X4位=4九=8片。因?yàn)?ROM 區(qū)在0000H7FFFH , RAM 區(qū)在8000HFFFFH，所以可通過最高位地址A15來區(qū)分，當(dāng)A15為0時(shí)選中ROM芯片；為1時(shí)

6、選中RAM芯片，此時(shí)，根據(jù)和進(jìn)行譯碼，得到 4個(gè)譯碼信號(hào)，分別用于 4 組字?jǐn)U展芯片的片選信號(hào)。 （圖略，可參照?qǐng)D 4.15）若CPU地址線為 24位，ROM 區(qū)為000000H007FFFH，貝U ROM 區(qū)大小為 32KB，總大小為 1416MB=2 KB=512X32KB，所以 RAM 區(qū)大小為 511 >32KB，共需使用 RAM 芯片數(shù)為 511 X32KB/8K X4 位=511X4>2個(gè)芯片。7. 假定一個(gè)存儲(chǔ)器系統(tǒng)支持4體交叉存取， 某程序執(zhí)行過程中訪問地址序列為 3, 9, 17, 2, 51, 37, 13, 4, 8, 41,67, 10，貝哪些地址訪問會(huì)發(fā)生

7、體沖突？參考答案：對(duì)于 4 體交叉訪問的存儲(chǔ)系統(tǒng)，每個(gè)存儲(chǔ)模塊的地址分布為：Bank0: 0、4、8、12、16 Bank1: 1 、5、9、13、173741Bank2: 2、6、10、14、18 Bank3: 3、7、11、15、195167如果給定的訪存地址在相鄰的4次訪問中出現(xiàn)在同一個(gè) Bank內(nèi)，就會(huì)發(fā)生訪存沖突。 所以，17和9、37和 17、13和 37、8和 4發(fā)生沖突。8. 現(xiàn)代計(jì)算機(jī)中，SRAM 一般用于實(shí)現(xiàn)快速小容量的cache,而DRAM用于實(shí)現(xiàn)慢速大容量的主存。以前超級(jí)計(jì)算機(jī)通常不提供 cache,而是用SRAM來實(shí)現(xiàn)主存（如，Cray巨型機(jī)），請(qǐng)問：如果不考慮 成本

8、，你還這樣設(shè)計(jì)高性能計(jì)算機(jī)嗎？為什么？參考答案： 不這樣做的理由主要有以下兩個(gè)方面： 主存越大越好,主存大,缺頁率降低,因而減少了訪問磁盤所需的時(shí)間。顯然用DRAM 芯片比用 SRAM 芯片構(gòu)成的主存容量大的多。 程序訪問的局部性特點(diǎn)使得cache的命中率很高，因而，即使主存沒有用快速的SRAM芯片而是用 DRAM 芯片,也不會(huì)影響到訪問速度。9. 分別給出具有下列要求的程序或程序段的示例：（ 1）對(duì)于數(shù)據(jù)的訪問，幾乎沒有時(shí)間局部性和空間局部性。（ 2）對(duì)于數(shù)據(jù)的訪問，有很好的時(shí)間局部性，但幾乎沒有空間局部性。（ 3）對(duì)于數(shù)據(jù)的訪問，有很好的空間局部性，但幾乎沒有時(shí)間局部性。（ 4）對(duì)于數(shù)據(jù)的

9、訪問，空間局部性和時(shí)間局部性都好。 參考答案（略） ：可以給出許多類似的示例。例如，對(duì)于按行優(yōu)先存放在內(nèi)存的多維數(shù)組，如果按列優(yōu)先訪問數(shù) 組元素，貝空間局部性就差，如果在一個(gè)循環(huán)體中某個(gè)數(shù)組元素只被訪問一次，貝時(shí)間局部性就差。10. 假定某機(jī)主存空間大小 1GB，按字節(jié)編址。cache的數(shù)據(jù)區(qū)（即不包括標(biāo)記、有效位等存儲(chǔ)區(qū)）有64KB , 塊大小為 128字節(jié)，采用直接映射和全寫（ write-through ）方式。請(qǐng)問：（ 1）主存地址如何劃分？要求說明每個(gè)字段的含義、位數(shù)和在主存地址中的位置。（2）cache的總?cè)萘繛槎嗌傥?？參考答案：? ）主存空間大小為 1GB，按字節(jié)編址，說明主存

10、地址為30位。cache共有64KB/128B=512行，因 此，行索引(行號(hào))為 9 位；塊大小 128 字節(jié)，說明塊內(nèi)地址為 7 位。因此， 30 位主存地址中， 高14位為標(biāo)志(Tag);中間9位為行索引；低7位為塊內(nèi)地址。(2)因?yàn)椴捎弥苯佑成?，所以cache中無需替換算法所需控制位，全寫方式下也無需修改(dirty )位，而標(biāo)志位和有效位總是必須有的，所以，cache總?cè)萘繛?12X(128冷+14+1)=5佃.5K位。11. 假定某計(jì)算機(jī)的cache共 16行，開始為空，塊大小為1個(gè)字，采用直接映射方式。CPU執(zhí)行某程序時(shí)，依次訪問以下地址序列：2， 3， 11， 16， 21，

11、13， 64， 48， 19， 11， 3， 22， 4， 27， 6和11。要求：( 1)說明每次訪問是命中還是缺失，試計(jì)算訪問上述地址序列的命中率。(2)若cache數(shù)據(jù)區(qū)容量不變，而塊大小改為4個(gè)字，則上述地址序列的命中情況又如何？參考答案(1) cache采用直接映射方式，其數(shù)據(jù)區(qū)容量為16行X1字/行 =16字；主存被劃分成1字/塊，所以，主存塊號(hào)=字號(hào)。因此，映射公式為：cache行號(hào)=主存塊號(hào) mod 16 =字號(hào) mod 16。開始cache為空，所以第一次都是miss,以下是映射關(guān)系(字號(hào) -cache行號(hào))和命中情況。2-2: miss， 3-3: miss， 11-11:

12、 miss， 16-0: miss, 21-5: miss， 13-13: miss， 64-0: miss、replace， 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、replace。只有一次命中！(2) cache采用直接映射方式，數(shù)據(jù)區(qū)容量不變，為16個(gè)字，每塊大小為4個(gè)字，所以，cache共有4行；主存被劃分為 4個(gè)字/塊，所以，主存塊號(hào)=

13、字號(hào)/4。因此，映射公式為：cache行號(hào)=主存塊號(hào) mod 4 = 字號(hào) /4 mod 4。以下是映射關(guān)系(字號(hào) -主存塊號(hào) -cache 行號(hào))和命中情況。2-0-0: miss, 3-0-0: hit, 11-2-2: miss, 16-4-0: miss、replace, 21-5-1、13-3-3: miss, 64-16-0、48-12-0、19-4-0: miss, replace, 11-2-2: hit, 3-0-0: miss、replace, 22-5-1: hit, 4-1-1: miss、replace, 27-6-2: miss、replace, 6-1-1: hi

14、t, 11-2-2: miss、replace。 命中 4 次。由此可見,塊變大后,能有效利用訪問的空間局部性,從而使命中率提高！12. 假定數(shù)組元素在主存按從左到右的下標(biāo)順序存放。試改變下列函數(shù)中循環(huán)的順序,使得其數(shù)組元素的 訪問與排列順序一致,并說明為什么修改后的程序比原來的程序執(zhí)行時(shí)間短。int sum_array ( int aNNN)int i, j, k, sum=0;for (i=0; i < N; i+)for (j=0; j < N; j+)for (k=0; k < N; k+)sum+=akij;return sum;參考答案：int sum_array

15、 ( int aNNN)int i, j, k, sum=0;for (k=0; k < N; k+)for (i=0; i < N; i+)for (j=0; j < N; j+)sum+=akij;return sum;修改后程序的數(shù)組元素的訪問與排列順序一致，使得空間局部性比原程序好，故執(zhí)行時(shí)間更短。13.分析比較以下三個(gè)函數(shù)的空間局部性，并指出哪個(gè)最好，哪個(gè)最差?# define N 1000# define N 1000# define N 1000typedef struct typedef struct typedef struct in t vel3;in t

16、 vel3;in t vel3;int acc3;int acc3;int acc3; poi nt; poi nt; poi nt;poi nt pN;poi nt pN;poi nt pN;void clear1(po int *p, int n)void clear2(po int *p, int n)void clear3(po int *p, int n)int i, j;int i, j;int i, j;for (i = 0; i < n; i+) for (i=0; i<n; i+) for (j=0; j<3; j+) for (j = 0; j<3;

17、 j+)for (j=0; j<3; j+) for (i=0; i<n; i+)pi.velj = 0;pi.velj = 0;pi.velj = 0;for (j = 0; i<3; j+)pi.accj = 0;for (i=0; i<n; i+)pi.accj = 0;pi.accj = 0;參考答案：對(duì)于函數(shù)clearl，其數(shù)組訪問順序與在內(nèi)存的存放順序完全一致，因此，空間局部性最好。對(duì)于函數(shù)clear2，其數(shù)組訪問順序在每個(gè)數(shù)組元素內(nèi)跳越式訪問，相鄰兩次訪問的單元最大相差3個(gè)int型變量(假定 sizeof(int)=4，則相當(dāng)于12B)，因此空間局部性比

18、clearl差。若主存塊大小比 12B小的話，則大大影響命中率。對(duì)于函數(shù)clear3，其數(shù)組訪問順序與在內(nèi)存的存放順序不一致，相鄰兩次訪問的單元都相差6個(gè)int型變量(假定sizeof(int)=4，則相當(dāng)于24B)因此，空間局部性比 clear2還差。若主存塊大小比 24B 小的話，則大大影響命中率。14. 以下是計(jì)算兩個(gè)向量點(diǎn)積的程序段：float dotproduct (float x8, float y8)float sum = 0.0;int i,;for (i = 0; i < 8; i+) sum += xi * yi;return sum;要求：(1 )試分析該段代碼中數(shù)

19、組x和y的時(shí)間局部性和空間局部性，并推斷命中率的高低。(2)假定該段程序運(yùn)行的計(jì)算機(jī)的數(shù)據(jù)cache采用直接映射方式，其數(shù)據(jù)區(qū)容量為32字節(jié)，每個(gè)主存塊大小為16字節(jié)。假定編譯程序?qū)⒆兞縮um和i分配給寄存器，數(shù)組x存放在00000040H開始的32字節(jié)的連續(xù)存儲(chǔ)區(qū)中，數(shù)組y緊跟在x后進(jìn)行存放。試計(jì)算該程序數(shù)據(jù)訪問的命中率， 要求說明每次訪問的 cache命中情況。(3) 將上述(2)中的數(shù)據(jù)cache改用2-路組相聯(lián)映射方式，塊大小改為8字節(jié)，其他條件不變，則 該程序數(shù)據(jù)訪問的命中率是多少？(4) 在上述(2)中條件不變的情況下，如果將數(shù)組x定義為float12,則數(shù)據(jù)訪問的命中率是多少？

20、參考答案：(1) 數(shù)組x和y都按存放順序訪問，不考慮映射的情況下，空間局部性都較好，但都只被訪問一次， 故沒有時(shí)間局部性。命中率的高低與塊大小、映射方式等都有關(guān)，所以，無法推斷命中率的高 低。(2) cache采用直接映射方式，塊大小為16字節(jié)，數(shù)據(jù)區(qū)大小為 32字節(jié)，故cache共有2行。數(shù)組 x的8個(gè)元素(共32B)分別存放在主存 40H開始的32個(gè)單元中，共有2個(gè)主存塊，其中x0 x3在第4塊，x4 x7在第5塊中；數(shù)組y的8個(gè)元素(共32B)分別在主存第6塊和第7 塊中。所以，x0 x3和y0 y3都映射到cache第0行；x4 x7和 y4 y7都映射到 cache第 1 行。cac

21、he第0-3次循環(huán)第4-7次循環(huán)第0行rx0-3，y0-3第1行x4-7，y4-7每調(diào)入一塊，裝入4個(gè)數(shù)組元素，因?yàn)?xi和yi總是映射到同一行，相互淘汰對(duì)方，故每次都不命中，命中率為 0.(3) 改用2路組相聯(lián)，塊大小為8B，則cache共有4行，每組兩行，共兩組。數(shù)組 x有 4 個(gè)主存塊，x0 x1、x2 x3，x4 x5，x6 x7分別在第 811 塊中； 數(shù)組 y 有 4 個(gè)主存塊，y0 y1、y2 y3，y4 y5，y6 y7分別在第 1215 塊中;cache第0行第1行第0組x0-1,x4-5y0-1,y4-5第1組x2-3,x6-7y2-3,y6-7每調(diào)入一塊，裝入兩個(gè)數(shù)組元素

22、，第二個(gè)數(shù)組元素的訪問總是命中，故命中率為50%。(4) 若(2)中條件不變，數(shù)組x定義了 12個(gè)元素，共有48B,使得y從第7塊開始，因而，xi和yi就不會(huì)映射到同一個(gè)cache行中，即: x0 x3在第4塊,x4 x7在第5塊，x8 x11在第6塊中,y0 y3在第7塊,y4 x7在第8塊。cache第0-3次循環(huán)第4-7次循環(huán)第0行x0-3y4-7第1行y0-3x4-7每調(diào)入一塊，裝入 4個(gè)數(shù)組元素，第一個(gè)元素不命中，后面3個(gè)總命中，故命中率為 75%。15. 以下是對(duì)矩陣進(jìn)行轉(zhuǎn)置的程序段：typedef int array44;void transpose(array dst, arr

23、ay src) int i, j;for (i = 0; i < 4; i+)for (j = 0; j < 4; j+)dstji = srcij;假設(shè)該段程序運(yùn)行的計(jì)算機(jī)中sizeof（int）=4，且只有一級(jí) cache,其中L1 data cache的數(shù)據(jù)區(qū)大小為32B,采用直接映射、寫回方式，塊大小為16B，初始為空。數(shù)組 dst從地址OOOOCOOOH開始存放，數(shù)組src從地址0000C040H開始存放。填寫下表，說明數(shù)組元素srcrowcol和dstrowcol映射到cache的哪一行，其訪問是命中（hit）還是失效（miss）。若L1 data cache的數(shù)據(jù)區(qū)容

24、量改為128B時(shí)，重新填寫表中內(nèi)容。src數(shù)組dst數(shù)組32Bcol=0col=1col=2col=3col=0col=1col=2col=3row=00/miss0/miss0/hit0/miss0/miss0/miss0/miss0/missrow=11/miss1/hit1/miss1/hit1/miss1/miss1/miss1/missrow=20/miss0/miss0/hit0/miss0/miss0/miss0/miss0/missrow=31/miss1/hit1/miss1/hit1/miss1/miss1/miss1/misssrc數(shù)組dst數(shù)組128Bcol=0col=

25、1col=2col=3col=0col=1col=2col=3row=04/miss4/hit4/hit4/ hit0/miss0/hit0/hit0/hitrow=15/ miss5/hit5/hit5/hit1/miss1/hit1/hit1/hitrow=26/ miss6/hit6/hit6/hit2/miss2/hit2/hit2/hitrow=37/ miss7/hit7/hit7/hit3/miss3/hit3/hit3/hit參考答案：從程序來看，數(shù)組訪問過程如下:src0 0、src1 0、src2 0、src3 0、因?yàn)閴K大小為16B，每個(gè)數(shù)組元素有 4個(gè)字節(jié)，所以4個(gè)數(shù)組

26、元素占一個(gè)主存塊，因此每次總是 調(diào)入4個(gè)數(shù)組元素到cache的一行。當(dāng)數(shù)據(jù)區(qū)容量為 32B 時(shí)，L1 data cache 中共有 2 行。數(shù)組元素 dst0i、dst2i、src0i、src2idstO 0、 dst0 1、 dst0 2、 dst0 3、src0 1、 src1 1、 src2 1、 src3 1、dst1 0、 dst1 1、 dst1 2、 dst1 3、src0 2、 src1 2、 src2 2、 src3 2、dst2 0、 dst2 1、 dst2 2、 dst2 3、src0 3、 src1 3、 src2 3、 src3 3、dst3 0 dst3 1 ds

27、t3 2 dst3 3（i=0 3）都映射到 cache 第 0 行，數(shù)組元素 dst1i、dst3i、src1i、src3i （i=0 3）都映射到 cache第1行。因此，從上述訪問過程來看，src00所在的一個(gè)主存塊（即存放 src0i （i=03）四個(gè)數(shù)組元素）剛調(diào)入 cache后，dst00所在主存塊又把 src00替換掉了。當(dāng)數(shù)據(jù)區(qū)容量為 128B時(shí),L1 data cache中共有8行。數(shù)組元素 dst0i、dst1i、dst2i、 dst3i、src0i、src1i、src2i、src3i（i=0 3）分別映射到 cache 第 0、1、2、3、4、5、6、7行。因此，不會(huì)發(fā)生

28、數(shù)組元素的替換。每次總是第一個(gè)數(shù)組元素不命中，后面三個(gè)數(shù)組元素都命 中。16. 通過對(duì)方格中每個(gè)點(diǎn)設(shè)置相應(yīng)的CMYK值就可以將方格圖上相應(yīng)的顏色。以下三個(gè)程序段都可實(shí)現(xiàn)對(duì)一個(gè)8X8的方格中圖上黃色的功能。struct pt_color struct pt_color struct pt_color int c;int c;int c;int m;int m;int m;int y;int y;int y;int k;int k;int k;struct pt_color square88;struct pt_color quare88;struct pt_color square88;int

29、i, j;int i, j;int i, j;for (i = 0; i < 8; i+) for (i = 0; i < 8; i+) for (i = 0;< 8; i+)for (j = 0; j < 8; j+) for (j = 0; j < 8; j+) for (j=0; j < 8; j+)squareij.c = 0;square j i.c = 0;squareij.y = 1;squareij.m = 0;square j i.m = 0;for (i = 0;< 8; i+)squareij.y = 1;square j i.y

30、 = 1;for (j=0; j < 8; j+) squareij.k = 0;square j i.k = 0;squareij.c = 0;squareij.m = 0;squareij.k = 0;程序段A程序段B程序段C假設(shè)cache勺數(shù)據(jù)區(qū)大小為512B，采用直接映射，塊大小為 32B,存儲(chǔ)器按字節(jié)編址，sizeof（int）=4。 編譯時(shí)變量i和j分配在寄存器中，數(shù)組square按行優(yōu)先方式存放在 000008C0H開始的連續(xù)區(qū)域中， 主存 地址為32位。要求：（1）對(duì)三個(gè)程序段A、B、C中數(shù)組訪問的時(shí)間局部性和空間局部性進(jìn)行分析比較。（2）畫出主存中的數(shù)組元素和 cach

31、e中行的對(duì)應(yīng)關(guān)系圖。（3）計(jì)算三個(gè)程序段A、B、C中的寫操作次數(shù)、寫不命中次數(shù)和寫缺失率。 參考答案：（1）對(duì)于時(shí)間局部性來說：程序段A、B和C中，都是每個(gè)數(shù)組元素只被訪問一次，所以都沒有時(shí)間局部性；對(duì)于空間局部性來說：程序段A訪問順序和存放順序一致，所以，空間局部性好； 程序段B訪問順序和存放順序不一致，所以，空間局部性不好； 程序段C雖然訪問順序和存放順序一致，但同一個(gè)主存塊有兩次訪問，所以空間局部性不好；（2）cache的行數(shù)為 512B/32B=16 ;數(shù)組首地址為 0000 0C80H，因?yàn)?0000 0C80H 正好是主存第 1100100B（ 100）塊的起始地址。所以數(shù)組從主存

32、第 100塊開始存放，一個(gè)數(shù)組元素占 4MB=16B , 所以每2個(gè)數(shù)組元素占用一個(gè)主存塊。8X8的數(shù)組共占用32個(gè)主存塊，正好是 cache數(shù)據(jù)區(qū)大小的2倍。主存中的數(shù)組元素與 cache行的映射關(guān)系圖如下：Cache行號(hào)主存塊號(hào)0#kSquare00/01100#1#Square02/ 03101#2#Square04/ 05102#3#Square06/ 07103#4#Square10/ 115#Square34/ 35:114#15#Square36/ 37:115#Square40/ 41116#Square70/ 71128#Square72/ 73129#Square74/ 7

33、5130#Square76/ 77131#(3)對(duì)于程序段 A:每?jī)蓚€(gè)數(shù)組元素(共涉及8次寫操作)裝入到一個(gè)cache行中，總是第一次訪問時(shí)未命中，后面7次都命中，所以，總的寫操作次數(shù)為64 X4 = 256次，寫不命中次數(shù)為 256X1/8 = 32次，因而寫缺失率為12.5%。對(duì)于程序段B:每?jī)蓚€(gè)數(shù)組元素(共涉及8次寫操作)裝入到一個(gè)cache行中，但總是只有一個(gè)數(shù)組元素(涉及4次寫操作)在被淘汰之前被訪問，并且總是第一次不命中，后面3次命中。即寫不命中次數(shù)為256X1/4 = 64次，因而寫缺失率為 25%。對(duì)于程序段C :第一個(gè)循環(huán)共64次訪問，每次裝入兩個(gè)數(shù)組元素，第一次不命中，第二

34、次命中；第二個(gè)循環(huán)，共訪問64X3次，每?jī)蓚€(gè)數(shù)組元素(共涉及 6次寫操作)裝入到一個(gè) cache行中，并且總是第一 次不命中，后面 5次命中。所以總的寫不命中次數(shù)為 32+(3 X64) X/6 = 64次，因而總?cè)笔蕿?25%。17. 假設(shè)某計(jì)算機(jī)的主存地址空間大小為64MB，采用字節(jié)編址方式。其 cache數(shù)據(jù)區(qū)容量為4KB，采用4路組相聯(lián)映射方式、LRU替換和回寫(write back)策略，塊大小為 64B。請(qǐng)問：(1) 主存地址字段如何劃分？要求說明每個(gè)字段的含義、位數(shù)和在主存地址中的位置。(2 )該cache的總?cè)萘坑卸嗌傥唬?3) 若cache初始為空，CPU依次從0號(hào)地址單元

35、順序訪問到 4344號(hào)單元，重復(fù)按此序列共訪問16次。若cache命中時(shí)間為1個(gè)時(shí)鐘周期，缺失損失為 10個(gè)時(shí)鐘周期，則CPU訪存的平均時(shí)間為多少時(shí) 鐘周期？參考答案：(1) cache的劃分為：4KB = 2 12b = 24組疋2行/組X6字節(jié)/行，所以，cache組號(hào)(組索引)占 4位。主存地址劃分為三個(gè)字段：高16位為標(biāo)志字段、中間 4位為組號(hào)、最低6位為塊內(nèi)地址。即主存空間劃分為：64MB = 2 26B = 216組群 怎4塊/組群X26字節(jié)/塊 cache共有64行，每行中有 16位標(biāo)志、1位有效位、1位修改(dirty)位、2位LRU位，以及數(shù)據(jù) 64B。故總?cè)萘繛?64M16

36、+1+1+2+64X 8)=34048 位。(3)因?yàn)槊繅K為 64B, CPU訪問的單元范圍為 04344，共4345個(gè)單元，4345/64=67.89，所以CPU 訪問的是主存前 68塊(第067塊)，也即CPU的訪問過程是對(duì)前 68塊連續(xù)訪問16次，總訪 存次數(shù)為 16M345 = 69520。16次0 * 163 64 65128 4288434443520#1#2#67#68#cache共有16組，每組4行，采用LRU算法的替換情況如下圖所示：第。行第1行和行第3行0<11,0/64/4816/0/6432/1648/32im1/65/4917/1/6533/1749/332組2

37、/66/5016/2/6634/1850/343組3/67/5119/3/6735/1951/354組4203E5215汕15314763根據(jù)圖中所示可知，第一次循環(huán)的每一塊只有第一次未命中，其余都命中；以后15次循環(huán)中，有20塊的第一字未命中，其余都命中。所以命中率p為(69520 -68 -5X20)/69520 = 99.47%平均訪存時(shí)間為：Hit Time + (1 -p) XMiss Penalty=1+10 X1 -p) = 1+0.0053 1(X= 1.053 個(gè)時(shí)鐘周期18. 假定某處理器可通過軟件對(duì)高速緩存設(shè)置不同的寫策略，那么，在下列兩種情況下，應(yīng)分別設(shè)置成什 么寫策略

38、？為什么？(1 )處理器主要運(yùn)行包含大量存儲(chǔ)器寫操作的數(shù)據(jù)訪問密集型應(yīng)用。(2) 處理器運(yùn)行程序的性質(zhì)與(1)相同，但安全性要求高，不允許有任何數(shù)據(jù)不一致的情況發(fā)生。 參考答案：(1) 采用write back策略較好，可減少訪存次數(shù)。(2) 采用write through策略較好，能保證數(shù)據(jù)的一致性。19. 已知cache睬用直接映射方式，共 16行，塊大小為1個(gè)字，缺失損失為8個(gè)時(shí)鐘周期；cache2也采用直接映射方式，共4行，塊大小為4個(gè)字，缺失損失為11個(gè)時(shí)鐘周期。假定開始時(shí) cache為空，采用字編址 方式。要求找出一個(gè)訪問地址序列，使得cache2具有更低的缺失率，但總的缺失損失反

39、而比cache1大。參考答案：假設(shè)cache1和cache2的缺失次數(shù)分別為 x和y,根據(jù)題意，x和y必須滿足以下條件：11 X > 8 X且x > y，顯然，滿足該條件的x和y有許多，例如，x=4, y=3、x=5, y=4等等。對(duì)于以下的訪問地址序列：0, 1, 4, 8, cache1缺失4次，而cache2缺失3次；對(duì)于以下的訪問地址序列：0, 2, 4, 8, 12, cache1缺失5次，而cache2缺失4次；對(duì)于以下的訪問地址序列：0, 3, 4, 8, 12, 16 , 20, cachel缺失7次，而cache2缺失6次;如此等等，可以找出很多。20. 提高關(guān)聯(lián)

40、度通常會(huì)降低缺失率,但并不總是這樣。請(qǐng)給出一個(gè)地址訪問序列,使得采用LRU 替換算法的2-路組相聯(lián)映射cache比具有同樣大小的直接映射 cache的缺失率更高。參考答案：2-路組相聯(lián)cache的組數(shù)是直接映射 cache的行數(shù)的一半，所以，可以找到一個(gè)地址序列A、B、C，使得：A映射到某一個(gè) cache行，B和C同時(shí)映射到另一個(gè) cache行，并且A、B、C映射到同一個(gè) cache組。這樣，如果訪存的地址序列為A、B、C、A、B、C、A、B、C，則對(duì)于直接映射cache,其命中情況為：miss/miss/miss /hit/miss/miss /hit/miss/miss/ 命中率可達(dá) 33

41、.3%。對(duì)于組相聯(lián)cache,因?yàn)锳、B、C映射到同一個(gè)組，每組只有2行，采用LRU替換算法，所以，每個(gè)地址處的數(shù)據(jù)剛調(diào)出cache就又被訪問到，每次都是miss,命中率為0。例如：假定直接映射cache為4行X1字/行，同樣大小的2-路組相聯(lián)cache為2組疋行/組X1字/行當(dāng)訪問序列為：0、2、4、0、2、4、0、2、4、(局部塊大小為3)時(shí)，則出現(xiàn)上述情況。當(dāng)訪問的局部塊大于組的大小時(shí),可能會(huì)發(fā)生 “顛簸”現(xiàn)象：剛被替換出去的數(shù)據(jù)又被訪問,導(dǎo)致缺失 率為 100%！21. 假定有三個(gè)處理器,分別帶有以下不同的cache：cache1 :采用直接映射方式，塊大小為 1個(gè)字，指令和數(shù)據(jù)的缺失

42、率分別為 4%和6% ; cache2：采用直接映射方式，塊大小為 4個(gè)字，指令和數(shù)據(jù)的缺失率分別為 2%和4% ;cache3:采用2-路組相聯(lián)映射方式，塊大小為4個(gè)字，指令和數(shù)據(jù)的缺失率分別為2%和3%。在這些處理器上運(yùn)行相同的程序,該程序的 CPI 為2.0,其中有一半是訪存指令。若缺失損失為(塊大 小+6)個(gè)時(shí)鐘周期，處理器1和處理器2的時(shí)鐘周期都為420ps，帶有cache3的處理器3的時(shí)鐘周期為450ps。請(qǐng)問：哪個(gè)處理器因 cache缺失而引起的額外開銷最大？哪個(gè)處理器執(zhí)行速度最快？參考答案：假設(shè)所運(yùn)行的程序共執(zhí)行N條指令，每條訪存指令僅讀寫一次內(nèi)存數(shù)據(jù)，則在該程序執(zhí)行過程中各處

43、理器因cache缺失而引起的額外開銷和執(zhí)行時(shí)間計(jì)算如下。對(duì)于處理器 1：額外開銷為：NX(4% + 6% X50%) X(1+6) = 0.49 N個(gè)時(shí)鐘周期 執(zhí)行程序所需時(shí)間為：(N >2.0 +0.49N) 420ps = 1045.8N ps對(duì)于處理器 2：額外開銷為：N>(2%+4%> 50%)>(4+6) = 0.40N 個(gè)時(shí)鐘周期執(zhí)行程序所需時(shí)間為： (N>2.0+0.40N) 4>20ps=1008N ps對(duì)于處理器 3：額外開銷為：N>(2%+3%> 50%)>(4+6) = 0.35N 個(gè)時(shí)鐘周期執(zhí)行程序所需時(shí)間為： (N

44、>2.0+0.35N) 4>50ps=1057.5N ps由此可見，處理器 1的cache缺失引起的額外開銷最大，處理器 2的執(zhí)行速度最快。22. 假定某處理器帶有一個(gè)數(shù)據(jù)區(qū)容量為256B的cache,其塊大小為32B。以下C語言程序段運(yùn)行在該處理器上，sizeof(int) = 4，編譯器將變量i, j, c, s都分配在通用寄存器中，因此，只要考慮數(shù)組元素的訪存 情況。若cache采用直接映射方式，則當(dāng)s=64和s=63時(shí)，缺失率分別為多少？若 cache采用2-路組相聯(lián)映射方式，則當(dāng)s=64和s=63時(shí)，缺失率又分別為多少？int i, j, c, s, a128;for (

45、 i = 0; i < 10000; i+ )for ( j = 0; j < 128; j=j+s )c = aj;參考答案：已知塊大小為 32B, cache容量為256B = 8行冷字/行 X4B/字，僅考慮數(shù)組訪問情況。1) 直接映射，s=64:訪存順序?yàn)閍0、a64 , a0、a64, 共循環(huán)10000次。這兩個(gè)元素被映射到同一個(gè)cache行中，每次都會(huì)發(fā)生沖突，因此缺失率為100%。2) 直接映射，s=63:訪存順序?yàn)?a0、a63、a126, a0、a63、a126,共循環(huán) 10000 次。這三個(gè)元素中后面兩個(gè)元素因?yàn)橛成涞酵粋€(gè)cache行中，因此每次都會(huì)發(fā)生沖突，

46、而a0不會(huì)發(fā)生沖突，故缺失率為 67%。3) 2-路組相聯(lián)，s=64:訪存順序?yàn)閍0、a64 , a0、a64,共循環(huán)10000次。這兩個(gè)元素雖然映射到同一個(gè) cache組中，但可以放在該組不同cache行中，所以不會(huì)發(fā)生沖突，缺失率為0。4) 2-路組相聯(lián),s=63:訪存順序?yàn)?a0、a63、a126, a0、a63、a126, 共循環(huán) 10000 次。這三個(gè)元素中后面兩個(gè)元素雖映射到同一個(gè)cache組中，但可放在不同cache行中，而a0不會(huì)發(fā)生沖突，故缺失率為 0。23. 假定一個(gè)虛擬存儲(chǔ)系統(tǒng)的虛擬地址為40位，物理地址為36位，頁大小為16KB，按字節(jié)編址。若頁表中有有效位、存儲(chǔ)保護(hù)位、修改位、使用位，共占4位，磁盤地址不在頁表中，則該存儲(chǔ)系統(tǒng)中每個(gè)進(jìn)程的頁表大小為多少？如果按計(jì)算出來的實(shí)際大小構(gòu)建頁表，則會(huì)出現(xiàn)什么問題？參考答案：因?yàn)槊宽摯笮∮?6KB，所以虛擬頁數(shù)為 240B/16KB=2 (40-14)=2