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

/第4章習(xí)題答案3.已知某機(jī)主存空間大小為64KB，按字節(jié)編址。要求：（1）若用1K×4位的SRAM芯片構(gòu)成該主存儲器，須要多少個芯片？（2）主存地址共多少位？幾位用于選片？幾位用于片內(nèi)選址？（3）畫出該存儲器的邏輯框圖。參考答案：（1）64KB/1K×4位=64×2=128片。（2）因為是按字節(jié)編址，所以主存地址共16位，6位選片，10位片內(nèi)選址。（3）明顯，位方向上擴(kuò)展了2倍，字方向擴(kuò)展了64倍。下圖中片選信號CS為高電平有效。4.用64K×1位的DRAM芯片構(gòu)成256K×8位的存儲器。要求：（1）計算所需芯片數(shù)，并畫出該存儲器的邏輯框圖。（2）若接受異步刷新方式，每單元刷新間隔不超過2ms，則產(chǎn)生刷新信號的間隔是多少時間？若接受集中刷新方式，則存儲器刷新一遍最少用多少讀寫周期？參考答案：（1）256KB/64K×1位=4×8=32片。存儲器邏輯框圖見下頁（圖中片選信號CS為高電平有效）。（2）因為每個單元的刷新間隔為2ms，所以，接受異步刷新時，在2ms內(nèi)每行必需被刷新一次，且僅被刷新一次。因為DRAM芯片存儲陣列為64K=256×256，所以一共有256行。因此，存儲器限制器必需每隔2ms/256=7.8μs產(chǎn)生一次刷新信號。接受集中刷新方式時，整個存儲器刷新一遍須要256個存儲（讀寫）周期，在這個過程中，存儲器不能進(jìn)行讀寫操作。5.用8K×8位的EPROM芯片組成32K×16位的只讀存儲器，試問：（1）數(shù)據(jù)寄存器最少應(yīng)有多少位？（2）地址寄存器最少應(yīng)有多少位？（3）共需多少個EPROM芯片？ （4）畫出該只讀存儲器的邏輯框圖。參考答案：（1）數(shù)據(jù)寄存器最少有16位。（2）地址寄存器最少有：15位（若按16位的字編址）；16位（若按字節(jié)編址）。（3）共須要32K×16位/8K×8位=4×2=8片。（4）該只讀存儲器的邏輯框圖如下（假定按字編址，圖中片選信號CS為高電平有效）。某計算機(jī)中已配有0000H～7FFFH的ROM區(qū)域，現(xiàn)在再用8K×4位的RAM芯片形成32K×8位的存儲區(qū)域，CPU地址總線為A0-A15，數(shù)據(jù)總線為D0-D7，限制信號為R/W#（讀/寫）、MREQ#（訪存）。要求說明地址譯碼方案，并畫出ROM芯片、RAM芯片和CPU之間的連接圖。假定上述其他條件不變，只是CPU地址線改為24根，地址范圍000000H～007FFFH為ROM區(qū)，剩下的全部地址空間都用8K×4位的RAM芯片配置，則須要多少個這樣的RAM芯片？參考答案：CPU地址線共16位，故存儲器地址空間為0000H～FFFFH，其中，8000H～FFFFH為RAM區(qū)，共215=32K個單元，其空間大小為32KB，故需8K×4位的芯片數(shù)為32KB/8K×4位=4×2=8片。因為ROM區(qū)在0000H～7FFFH，RAM區(qū)在8000H～FFFFH，所以可通過最高位地址A15來區(qū)分，當(dāng)A15為0時選中ROM芯片；為1時選中RAM芯片，此時，依據(jù)A14和A13進(jìn)行譯碼，得到4個譯碼信號，分別用于4組字?jǐn)U展芯片的片選信號。（圖略，可參照圖4.15）若CPU地址線為24位，ROM區(qū)為000000H～007FFFH，則ROM區(qū)大小為32KB，總大小為16MB=214KB=512×32KB，所以RAM區(qū)大小為511×32KB，共需運(yùn)用RAM芯片數(shù)為511×32KB/8K×4位=511×4×2個芯片。假定一個存儲器系統(tǒng)支持4體交叉存取，某程序執(zhí)行過程中訪問地址序列為3,9,17,2,51,37,13,4,8,41,67,10，則哪些地址訪問會發(fā)生體沖突？參考答案：對于4體交叉訪問的存儲系統(tǒng)，每個存儲模塊的地址分布為：Bank0:0、4、8、12、16……Bank1:1、5、9、13、17…37…41…Bank2:2、6、10、14、18……Bank3:3、7、11、15、19…51…67假如給定的訪存地址在相鄰的4次訪問中出現(xiàn)在同一個Bank內(nèi)，就會發(fā)生訪存沖突。所以，17和9、37和17、13和37、8和4發(fā)生沖突。現(xiàn)代計算機(jī)中，SRAM一般用于實(shí)現(xiàn)快速小容量的cache，而DRAM用于實(shí)現(xiàn)慢速大容量的主存。以前超級計算機(jī)通常不供應(yīng)cache，而是用SRAM來實(shí)現(xiàn)主存（如，Cray巨型機(jī)），請問：假如不考慮成本，你還這樣設(shè)計高性能計算機(jī)嗎？為什么？參考答案：不這樣做的理由主要有以下兩個方面：=1\*GB3①主存越大越好，主存大，缺頁率降低，因而削減了訪問磁盤所需的時間。明顯用DRAM芯片比用SRAM芯片構(gòu)成的主存容量大的多。=2\*GB3②程序訪問的局部性特點(diǎn)使得cache的命中率很高，因而，即使主存沒有用快速的SRAM芯片而是用DRAM芯片，也不會影響到訪問速度。分別給出具有下列要求的程序或程序段的示例：（1）對于數(shù)據(jù)的訪問，幾乎沒有時間局部性和空間局部性。（2）對于數(shù)據(jù)的訪問，有很好的時間局部性，但幾乎沒有空間局部性。（3）對于數(shù)據(jù)的訪問，有很好的空間局部性，但幾乎沒有時間局部性。（4）對于數(shù)據(jù)的訪問，空間局部性和時間局部性都好。參考答案（略）：可以給出許多類似的示例。例如，對于按行優(yōu)先存放在內(nèi)存的多維數(shù)組，假如按列優(yōu)先訪問數(shù)組元素，則空間局部性就差，假如在一個循環(huán)體中某個數(shù)組元素只被訪問一次，則時間局部性就差。假定某機(jī)主存空間大小1GB，按字節(jié)編址。cache的數(shù)據(jù)區(qū)（即不包括標(biāo)記、有效位等存儲區(qū)）有64KB，塊大小為128字節(jié)，接受干脆映射和全寫（write-through）方式。請問：（1）主存地址如何劃分？要求說明每個字段的含義、位數(shù)和在主存地址中的位置。（2）cache的總?cè)萘繛槎嗌傥?？參考答案：?）主存空間大小為1GB，按字節(jié)編址，說明主存地址為30位。cache共有64KB/128B=512行，因此，行索引（行號）為9位；塊大小128字節(jié)，說明塊內(nèi)地址為7位。因此，30位主存地址中，高14位為標(biāo)記（Tag）；中間9位為行索引；低7位為塊內(nèi)地址。（2）因為接受干脆映射，所以cache中無需替換算法所需限制位，全寫方式下也無需修改（dirty）位，而標(biāo)記位和有效位總是必需有的，所以，cache總?cè)萘繛?12×(128×8+14+1)=519.5K位。假定某計算機(jī)的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個字，則上述地址序列的命中狀況又如何？參考答案cache接受干脆映射方式，其數(shù)據(jù)區(qū)容量為16行×1字/行=16字；主存被劃分成1字/塊，所以，主存塊號=字號。因此，映射公式為：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、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。只有一次命中?。?）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-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:hit，11-2-2:miss、replace。命中4次。由此可見，塊變大后，能有效利用訪問的空間局部性，從而使命中率提高！假定數(shù)組元素在主存按從左到右的下標(biāo)依次存放。試變更下列函數(shù)中循環(huán)的依次，使得其數(shù)組元素的訪問和排列依次一樣，并說明為什么修改后的程序比原來的程序執(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]){ inti,j,k,sum=0; for(k=0;k<N;k++) for(i=0;i<N;i++) for(j=0;j<N;j++)sum+=a[k][i][j];returnsum;}修改后程序的數(shù)組元素的訪問和排列依次一樣，使得空間局部性比原程序好，故執(zhí)行時間更短。分析比較以下三個函數(shù)的空間局部性，并指出哪個最好，哪個最差？#defineN1000typedefstruct{#defineN1000typedefstruct{ intvel[3]; intacc[3]; }point;pointp[N];voidclear3(point*p,intn){ inti,j; for(j=0;j<3;j++){ for(i=0;i<n;i++) p[i].vel[j]=0; for(i=0;i<n;i++)p[i].acc[j]=0; }}#defineN1000typedefstruct{ intvel[3]; intacc[3]; }point;pointp[N];voidclear1(point*p,intn){ inti,j; for(i=0;i<n;i++){ for(j=0;j<3;j++) p[i].vel[j]=0; for(j=0;i<3;j++)p[i].acc[j]=0; }}#defineN1000typedefstruct{ intvel[3]; intacc[3]; }point;pointp[N];voidclear2(point*p,intn){ inti,j; for(i=0;i<n;i++){ for(j=0;j<3;j++){ p[i].vel[j]=0; p[i].acc[j]=0; }}}參考答案：對于函數(shù)clear1，其數(shù)組訪問依次和在內(nèi)存的存放依次完全一樣，因此，空間局部性最好。對于函數(shù)clear2，其數(shù)組訪問依次在每個數(shù)組元素內(nèi)跳越式訪問，相鄰兩次訪問的單元最大相差3個int型變量（假定sizeof(int)=4，則相當(dāng)于12B），因此空間局部性比clear1差。若主存塊大小比12B小的話，則大大影響命中率。對于函數(shù)clear3，其數(shù)組訪問依次和在內(nèi)存的存放依次不一樣，相鄰兩次訪問的單元都相差6個int型變量（假定sizeof(int)=4，則相當(dāng)于24B）因此，空間局部性比clear2還差。若主存塊大小比24B小的話，則大大影響命中率。以下是計算兩個向量點(diǎn)積的程序段：floatdotproduct(floatx[8],floaty[8]){ floatsum=0.0;inti,; for(i=0;i<8;i++)sum+=x[i]*y[i]; returnsum;}要求：（1）試分析該段代碼中數(shù)組x和y的時間局部性和空間局部性，并推斷命中率的凹凸。（2）假定該段程序運(yùn)行的計算機(jī)的數(shù)據(jù)cache接受干脆映射方式，其數(shù)據(jù)區(qū)容量為32字節(jié)，每個主存塊大小為16字節(jié)。假定編譯程序?qū)⒆兞縮um和i支配給寄存器，數(shù)組x存放在00000040H起先的32字節(jié)的連續(xù)存儲區(qū)中，數(shù)組y緊跟在x后進(jìn)行存放。試計算該程序數(shù)據(jù)訪問的命中率，要求說明每次訪問的cache命中狀況。（3）將上述（2）中的數(shù)據(jù)cache改用2-路組相聯(lián)映射方式，塊大小改為8字節(jié)，其他條件不變，則該程序數(shù)據(jù)訪問的命中率是多少？（4）在上述（2）中條件不變的狀況下，假如將數(shù)組x定義為float[12]，則數(shù)據(jù)訪問的命中率是多少？參考答案：（1）數(shù)組x和y都按存放依次訪問，不考慮映射的狀況下，空間局部性都較好，但都只被訪問一次，故沒有時間局部性。命中率的凹凸和塊大小、映射方式等都有關(guān)，所以，無法推斷命中率的凹凸。（2）cache接受干脆映射方式，塊大小為16字節(jié)，數(shù)據(jù)區(qū)大小為32字節(jié)，故cache共有2行。數(shù)組x的8個元素（共32B）分別存放在主存40H起先的32個單元中，共有2個主存塊，其中x[0]~x[3]在第4塊，x[4]~x[7]在第5塊中；數(shù)組y的8個元素（共32B）分別在主存第6塊和第7塊中。所以，x[0]~x[3]和y[0]~y[3]都映射到cache第0行；x[4]~x[7]和y[4]~y[7]都映射到cache第1行。cache第0-3次循環(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[1]、x[2]~x[3]，x[4]~x[5]，x[6]~x[7]分別在第8~11塊中；數(shù)組y有4個主存塊，y[0]~y[1]、y[2]~y[3]，y[4]~y[5]，y[6]~y[7]分別在第12~15塊中；cache第0行第1行第0組x[0-1],x[4-5]y[0-1],y[4-5]第1組x[2-3],x[6-7]y[2-3],y[6-7]每調(diào)入一塊，裝入兩個數(shù)組元素，其次個數(shù)組元素的訪問總是命中，故命中率為50%。（4）若（2）中條件不變，數(shù)組x定義了12個元素，共有48B，使得y從第7塊起先，因而，x[i]和y[i]就不會映射到同一個cache行中，即：x[0]~x[3]在第4塊，x[4]~x[7]在第5塊，x[8]~x[11]在第6塊中，y[0]~y[3]在第7塊，y[4]~x[7]在第8塊。cache第0-3次循環(huán)第4-7次循環(huán)第0行x[0-3]y[4-7]第1行y[0-3]x[4-7]每調(diào)入一塊，裝入4個數(shù)組元素，第一個元素不命中，后面3個總命中，故命中率為75%。以下是對矩陣進(jìn)行轉(zhuǎn)置的程序段：typedef int array[4][4];void transpose(arraydst, arraysrc){ int i,j; for(i=0;i<4;i++) for(j=0;j<4;j++) dst[j][i]=src[i][j];}假設(shè)該段程序運(yùn)行的計算機(jī)中sizeof(int)=4，且只有一級cache，其中L1datacache的數(shù)據(jù)區(qū)大小為32B，接受干脆映射、寫回方式，塊大小為16B，初始為空。數(shù)組dst從地址0000C000H起先存放，數(shù)組src從地址0000C040H起先存放。填寫下表，說明數(shù)組元素src[row][col]和dst[row][col]映射到cache的哪一行，其訪問是命中（hit）還是失效（miss）。若L1datacache的數(shù)據(jù)區(qū)容量改為128B時，重新填寫表中內(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=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ù)組訪問過程如下：src[0][0]、dst[0][0]、src[0][1]、dst[1][0]、src[0][2]、dst[2][0]、src[0][3]、dst[3][0]src[1][0]、dst[0][1]、src[1][1]、dst[1][1]、src[1][2]、dst[2][1]、src[1][3]、dst[3][1]src[2][0]、dst[0][2]、src[2][1]、dst[1][2]、src[2][2]、dst[2][2]、src[2][3]、dst[3][2]src[3][0]、dst[0][3]、src[3][1]、dst[1][3]、src[3][2]、dst[2][3]、src[3][3]、dst[3][3]因為塊大小為16B，每個數(shù)組元素有4個字節(jié)，所以4個數(shù)組元素占一個主存塊，因此每次總是調(diào)入4個數(shù)組元素到cache的一行。當(dāng)數(shù)據(jù)區(qū)容量為32B時，L1datacache中共有2行。數(shù)組元素dst[0][i]、dst[2][i]、src[0][i]、src[2][i](i=0～3)都映射到cache第0行，數(shù)組元素dst[1][i]、dst[3][i]、src[1][i]、src[3][i](i=0～3)都映射到cache第1行。因此，從上述訪問過程來看，src[0][0]所在的一個主存塊（即存放src[0][i](i=0～3)四個數(shù)組元素）剛調(diào)入cache后，dst[0][0]所在主存塊又把src[0][0]替換掉了?！?dāng)數(shù)據(jù)區(qū)容量為128B時，L1datacache中共有8行。數(shù)組元素dst[0][i]、dst[1][i]、dst[2][i]、dst[3][i]、src[0][i]、src[1][i]、src[2][i]、src[3][i](i=0～3)分別映射到cache第0、1、2、3、4、5、6、7行。因此，不會發(fā)生數(shù)組元素的替換。每次總是第一個數(shù)組元素不命中，后面三個數(shù)組元素都命中。通過對方格中每個點(diǎn)設(shè)置相應(yīng)的CMYK值就可以將方格圖上相應(yīng)的顏色。以下三個程序段都可實(shí)現(xiàn)對一個8×8的方格中圖上黃色的功能。structpstructpt_color{ intc; intm; inty; intk;}structpt_colorsquare[8][8];inti,j;for(i=0;i<8;i++){ for(j=0;j<8;j++){ square[i][j].c=0;square[i][j].m=0;square[i][j].y=1;square[i][j].k=0; }}structpt_color{ intc; intm; inty; intk;}structpt_colorquare[8][8];inti,j;for(i=0;i<8;i++){ for(j=0;j<8;j++){ square[j][i].c=0;square[j][i].m=0;square[j][i].y=1;square[j][i].k=0; }}structpt_color{ intc; intm; inty; intk;}structpt_colorsquare[8][8];inti,j;for(i=0;i<8;i++)for(j=0;j<8;j++) square[i][j].y=1;for(i=0;i<8;i++) for(j=0;j<8;j++){ square[i][j].c=0;square[i][j].m=0;square[i][j].k=0; } 程序段A 程序段B 程序段C假設(shè)cache的數(shù)據(jù)區(qū)大小為512B，接受干脆映射，塊大小為32B，存儲器按字節(jié)編址，sizeof(int)=4。編譯時變量i和j支配在寄存器中，數(shù)組square按行優(yōu)先方式存放在000008C0H起先的連續(xù)區(qū)域中，主存地址為32位。要求：對三個程序段A、B、C中數(shù)組訪問的時間局部性和空間局部性進(jìn)行分析比較。畫出主存中的數(shù)組元素和cache中行的對應(yīng)關(guān)系圖。計算三個程序段A、B、C中的寫操作次數(shù)、寫不命中次數(shù)和寫缺失率。參考答案：（1）對于時間局部性來說：程序段A、B和C中，都是每個數(shù)組元素只被訪問一次，所以都沒有時間局部性；對于空間局部性來說：程序段A訪問依次和存放依次一樣，所以，空間局部性好；程序段B訪問依次和存放依次不一樣，所以，空間局部性不好；程序段C雖然訪問依次和存放依次一樣，但同一個主存塊有兩次訪問，所以空間局部性不好；（2）cache的行數(shù)為512B/32B=16；數(shù)組首地址為00000C80H，因為00000C80H正好是主存第1100100B（100）塊的起始地址。所以數(shù)組從主存第100塊起先存放，一個數(shù)組元素占4×4B=16B，所以每2個數(shù)組元素占用一個主存塊。8×8的數(shù)組共占用32個主存塊，正好是cache數(shù)據(jù)區(qū)大小的2倍。主存中的數(shù)組元素和cache行的映射關(guān)系圖如下：Cache行號主存塊號Cache行號主存塊號100#101#102#103#Square[0][0]/[0][1]Square[0][2]/[0][3]Square[0][4]/[0][5]Square[0][6]/[0][7]Square[1][0]/[1][1]128#129#130#131#Square[7][0]/[7][1]Square[7][2]/[7][3]Square[7][4]/[7][5]Square[7][6]/[7][7]0#1#2#3#15#4#5#115#114#116#Square[3][4]/[3][5]Square[3][6]/[3][7]Square[4][0]/[4][1]（3）對于程序段A：每兩個數(shù)組元素（共涉及8次寫操作）裝入到一個cache行中，總是第一次訪問時未命中，后面7次都命中，所以，總的寫操作次數(shù)為64×4=256次，寫不命中次數(shù)為256×1/8=32次，因而寫缺失率為12.5%。對于程序段B：每兩個數(shù)組元素（共涉及8次寫操作）裝入到一個cache行中，但總是只有一個數(shù)組元素（涉及4次寫操作）在被淘汰之前被訪問，并且總是第一次不命中，后面3次命中。即寫不命中次數(shù)為256×1/4=64次，因而寫缺失率為25%。對于程序段C：第一個循環(huán)共64次訪問，每次裝入兩個數(shù)組元素，第一次不命中，其次次命中；其次個循環(huán)，共訪問64×3次，每兩個數(shù)組元素（共涉及6次寫操作）裝入到一個cache行中，并且總是第一次不命中，后面5次命中。所以總的寫不命中次數(shù)為32+(3×64)×1/6=64次，因而總?cè)笔蕿?5%。假設(shè)某計算機(jī)的主存地址空間大小為64MB，接受字節(jié)編址方式。其cache數(shù)據(jù)區(qū)容量為4KB，接受4路組相聯(lián)映射方式、LRU替換和回寫（writeback）策略，塊大小為64B。請問：（1）主存地址字段如何劃分？要求說明每個字段的含義、位數(shù)和在主存地址中的位置。（2）該cache的總?cè)萘坑卸嗌傥?？?）若cache初始為空，CPU依次從0號地址單元依次訪問到4344號單元，重復(fù)按此序列共訪問16次。若cache命中時間為1個時鐘周期，缺失損失為10個時鐘周期，則CPU訪存的平均時間為多少時鐘周期？參考答案：（1）cache的劃分為：4KB=212B=24組×22行/組×26字節(jié)/行，所以，cache組號（組索引）占4位。主存地址劃分為三個字段：高16位為標(biāo)記字段、中間4位為組號、最低6位為塊內(nèi)地址。即主存空間劃分為：64MB=226B=216組群×24塊/組群×26字節(jié)/塊（2）cache共有64行，每行中有16位標(biāo)記、1位有效位、1位修改(dirty)位、2位LRU位，以及數(shù)據(jù)64B。故總?cè)萘繛?4×(16+1+1+2+64×8)=34048位。（3）因為每塊為64B，CPU訪問的單元范圍為0～4344，共4345個單元，4345/64=67.89，所以CPU訪問的是主存前68塊（第0～67塊），也即CPU的訪問過程是對前68塊連續(xù)訪問16次，總訪存次數(shù)為16×4345=69520。00631434412842886416次1#2#67#0#6568#4352cache共有16組，每組4行，接受LRU算法的替換狀況如下圖所示：依據(jù)圖中所示可知，第一次循環(huán)的每一塊只有第一次未命中，其余都命中；以后15次循環(huán)中，有20塊的第一字未命中，其余都命中。所以命中率p為(69520–68–15×20)/69520=99.47%平均訪存時間為：HitTime+(1–p)×MissPenalty=1+10×(1–p)=1+0.0053×10=1.053個時鐘周期假定某處理器可通過軟件對高速緩存設(shè)置不同的寫策略，那么，在下列兩種狀況下，應(yīng)分別設(shè)置成什么寫策略？為什么？（1）處理器主要運(yùn)行包含大量存儲器寫操作的數(shù)據(jù)訪問密集型應(yīng)用。（2）處理器運(yùn)行程序的性質(zhì)和（1）相同，但平安性要求高，不允許有任何數(shù)據(jù)不一樣的狀況發(fā)生。參考答案：（1）接受writeback策略較好，可削減訪存次數(shù)。（2）接受writethrough策略較好，能保證數(shù)據(jù)的一樣性。已知cache1接受干脆映射方式，共16行，塊大小為1個字，缺失損失為8個時鐘周期；cache2也接受干脆映射方式，共4行，塊大小為4個字，缺失損失為11個時鐘周期。假定起先時cache為空，接受字編址方式。要求找出一個訪問地址序列，使得cache2具有更低的缺失率，但總的缺失損失反而比cache1大。參考答案：假設(shè)cache1和cache2的缺失次數(shù)分別為x和y，依據(jù)題意，x和y必需滿足以下條件：11×y>8×x且x>y，明顯，滿足該條件的x和y有許多，例如，x=4，y=3、x=5，y=4等等。對于以下的訪問地址序列：0，1，4，8，cache1缺失4次，而cache2缺失3次；對于以下的訪問地址序列：0，2，4，8，12，cache1缺失5次，而cache2缺失4次；對于以下的訪問地址序列：0，3，4，8，12，16，20，cache1缺失7次，而cache2缺失6次；如此等等，可以找出許多。提高關(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/…命中率可達(dá)33.3%。對于組相聯(lián)cache，因為A、B、C映射到同一個組，每組只有2行，接受LRU替換算法，所以，每個地址處的數(shù)據(jù)剛調(diào)出cache就又被訪問到，每次都是miss，命中率為0。例如：假定干脆映射cache為4行×1字/行，同樣大小的2-路組相聯(lián)cache為2組×2行/組×1字/行當(dāng)訪問序列為：0、2、4、0、2、4、0、2、4、…（局部塊大小為3）時，則出現(xiàn)上述狀況。當(dāng)訪問的局部塊大于組的大小時，可能會發(fā)生“顛簸”現(xiàn)象：剛被替換出去的數(shù)據(jù)又被訪問，導(dǎo)致缺失率為100%！假定有三個處理器，分別帶有以下不同的cache：cache1：接受干脆映射方式，塊大小為1個字，指令和數(shù)據(jù)的缺失率分別為4%和6%；cache2：接受干脆映射方式，塊大小為4個字，指令和數(shù)據(jù)的缺失率分別為2%和4%；cache3：接受2-路組相聯(lián)映射方式，塊大小為4個字，指令和數(shù)據(jù)的缺失率分別為2%和3%。在這些處理器上運(yùn)行相同的程序，該程序的CPI為2.0，其中有一半是訪存指令。若缺失損失為（塊大小+6）個時鐘周期，處理器1和處理器2的時鐘周期都為420ps，帶有cache3的處理器3的時鐘周期為450ps。請問：哪個處理器因cache缺失而引起的額外開銷最大？哪個處理器執(zhí)行速度最快？參考答案：假設(shè)所運(yùn)行的程序共執(zhí)行N條指令，每條訪存指令僅讀寫一次內(nèi)存數(shù)據(jù)，則在該程序執(zhí)行過程中各處理器因cache缺失而引起的額外開銷和執(zhí)行時間計算如下。對于處理器1： 額外開銷為：N×(4%+6%×50%)×(1+6)=0.49N個時鐘周期 執(zhí)行程序所需時間為：(N×2.0+0.49N)×420ps=1045.8Nps對于處理器2： 額外開銷為：N×(2%+4%×50%)×(4+6)=0.40N個時鐘周期 執(zhí)行程序所需時間為：(N×2.0+0.40N)×420ps=1008Nps對于處理器3： 額外開銷為：N×(2%+3%×50%)×(4+6)=0.35N個時鐘周期 執(zhí)行程序所需時間為：(N×2.0+0.35N)×450ps=1057.5Nps由此可見，處理器1的cache缺失引起的額外開銷最大，處理器2的執(zhí)行速度最快。假定某處理器帶有一個數(shù)據(jù)區(qū)容量為256B的cache，其塊大小為32B。以下C語言程序段運(yùn)行在該處理器上，sizeof(int)=4，編譯器將變量i,j,c,s都支配在通用寄存器中，因此，只要考慮數(shù)組元素的訪存狀況。若cache接受干脆映射方式，則當(dāng)s=64和s=63時，缺失率分別為多少？若cache接受2-路組相聯(lián)映射方式，則當(dāng)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，cache容量為256B=8行×8字/行×4B/字，僅考慮數(shù)組訪問狀況。1)干脆映射，s=64:訪存依次為a[0]、a[64],a[0]、a[64],……,共循環(huán)10000次。這兩個元素被映射到同一個cache行中，每次都會發(fā)生沖突，因此缺失率為100%。2)干脆映射，s=63:訪存依次為a[0]、a[63]、a[126],a[0]、a[63]、a[126],……共循環(huán)10000次。這三個元素中后面兩個元素因為映射到同一個cache行中，因此每次都會發(fā)生沖突，而a[0]不會發(fā)生沖突，故缺失率為67%。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[0]、a[63]、a[126],a[0]、a[63]、a[126],……共循環(huán)10000次。這三個元素中后面兩個元素雖映射到同一個cache組中，但可放在不同cache行中,而a[0]不會發(fā)生沖突，故缺失率為0。假定一個虛擬存儲系統(tǒng)的虛擬地址為40位，物理地址為36位，頁大小為16KB，按字節(jié)編址。若頁表中有有效位、存儲愛惜位、修改位、運(yùn)用位，共占4位，磁盤地址不在頁表中，則該存儲系統(tǒng)中每個進(jìn)程的頁表大小為多少？假如按計算出來的實(shí)際大小構(gòu)建頁表，則會出現(xiàn)什么問題？參考答案：因為每頁大小有16KB，所以虛擬頁數(shù)為240B/16KB=2(40-14)=226頁。物理頁面和虛擬頁面大小相等，所以物理頁號的位數(shù)為36–14=22位。頁表項位數(shù)為：有效位+愛惜位