1、3. 某模型機有10條指令丨！g，它們的使用頻度分別為，。 (1) 計算采用等長操作碼表示時的信息冗余量。 (2) 要求操作碼的平均長度最短，試設(shè)計操作碼的編碼，并計算所設(shè)計操作碼的平均長度。 (3) 只有二種碼長，試設(shè)計平均碼長最短的擴(kuò)展操作碼編碼并計算平均碼長。 (4) 只有二種碼長，試設(shè)計平均碼長最短的等長擴(kuò)展碼編碼并計算平均碼長。 3. (1)采用等長操作碼表示時的信息冗余量為% (2) 操作碼的Huffman編碼法如表所示，此種編碼的平均碼長為位。 表 操作碼的Huffman編碼法、2-5擴(kuò)展碼和2-4等長擴(kuò)展碼編碼法 指令 指令使用 頻度Pi Huffman 編碼 操作碼 長度1

2、i 2-5擴(kuò)展碼 操作碼 長度li 2-4等長擴(kuò) 展碼 操作碼 長度1 i 11 0 0 2 0 0 2 0 0 2 I 2 1 0 2 0 1 2 0 1 2 13 0 1 0 3 1 0 2 1 0 0 0 4 I 4 0 1 1 3 1 1 0 0 0 5 1 0 0 1 4 I 5 1 1 0 3 1 1 0 0 1 5 1 0 1 0 4 I 6 1 1 1 0 0 5 1 1 0 1 0 5 1 0 1 1 4 I 7 1 1 1 0 1 5 1 1 0 1 1 5 1 1 0 0 4 I 8 1 1 1 1 0 5 1 1 1 0 0 5 1 1 0 1 4 I 9 1 1 1

3、1 1 0 6 1 1 1 0 1 5 1 1 1 0 4 I 10 1 1 1 1 1 1 6 1 1 1 1 0 5 1 1 1 1 4 (3) 操作碼的2-5擴(kuò)展碼編碼法如表所示，此種編碼的平均碼長為位。 (4)操作碼的2-4等長擴(kuò)展碼編碼法如表所示，此種編碼的平均碼長為位。 5. 若某機設(shè)計有如下格式的指令： 三地址指令12種，一地址指令254種，設(shè)指令字的長度為 16位，每個地址碼字段的位數(shù)均為4位。 若操作碼的編碼采用擴(kuò)展操作碼，問二地址指令最多可以設(shè)計多少種 5. 二地址指令最多可以設(shè)計 48種。 6. 一臺模型機共有9條指令丨1丨9，各指令的使用頻度分別為 30% 20% 20

4、% 10% 8% 6% 3% 2% 1% 該模型機有8位和16位兩種指令字長。8位字長指令為寄存器-寄存器(R-R)二地址類型，16位字長指令 為寄存器-存儲器(R-M) 二地址變址尋址類型。 (1) 試設(shè)計有二種碼長的擴(kuò)展操作碼，使其平均碼長最短，并計算此種編碼的平均碼長。 (2) 在(1)的基礎(chǔ)上，該機允許使用多少個可編址的通用寄存器 (3) 若采用通用寄存器作為變址寄存器，試設(shè)計該機的兩種指令格式，并標(biāo)岀各字段的位數(shù)。 (4) 計算變址尋址的偏移地址范圍。 6. (1)操作碼的2-5擴(kuò)展碼編碼法如表所示，此種編碼的平均碼長為位。 表操作碼的Huffman編碼法和2-4等長擴(kuò)展 碼編碼法

5、指令 指令使用頻度Pi 2-5擴(kuò)展碼 操作碼長度li I 1 0 0 2 I 2 0 1 2 I 3 1 0 2 I 4 1 1 0 0 0 5 I 5 1 1 0 0 1 5 I 6 1 1 0 1 0 5 I 7 1 1 0 1 1 5 I 8 1 1 1 0 0 5 I 9 1 1 1 0 1 5 (2) 在(1)的基礎(chǔ)上，該機允許使用 8個可編址的通用寄存器。 (3) 該機的兩種指令格式及各字段的位數(shù)如下： (4) 變址尋址的偏移地址范圍為 -16+15。 3. 假設(shè)高速緩存Cache工作速度為主存的5倍，且Cache被訪問命中的概率為，則采用Cache后， 能使整個存儲系統(tǒng)獲得的加速

6、比是多少3. 3.57 4. 某機是由Cache和主存組成的二級存儲系統(tǒng)，Cache的存取時間tc=20ns，主存的存取時間tm=80ns S2和C2分別為主存的存取時間、 存儲容量和每字節(jié)成本。若 0=、 t1=20ns、S1=512KB g=$10/KB及C2=$5/KB，12和S2未知，而整個存儲器系統(tǒng)的預(yù)算上限為 $15000。 (1) 推導(dǎo)此存儲器系統(tǒng)的等效存取時間ta的公式。 (2) 推導(dǎo)此存儲器系統(tǒng)的總成本公式。 (3) 在不超出預(yù)算的前提下，S2的最大值為多少 KB (4) 為了使t a=40ns，主存的存取時間12應(yīng)為多少ns 7. (1)t a=19+(2)C total

7、=5120+5s2(3)1976KB420ns 8. 有16個存儲器模塊，每個模塊的容量為4MB字長為32位。現(xiàn)在要用這16個存儲器模塊構(gòu)成一個主存 儲器，有如下二種組織方式： 方式1 : 16個存儲器模塊用高位交叉方式構(gòu)成存儲器； 方式2 : 16個存儲器模塊用低位交叉方式構(gòu)成存儲器。 (1) 寫岀訪問各種存儲器的地址格式； (2) 比較各種存儲器的優(yōu)缺點； (3) 不考慮訪問沖突，計算各種存儲器的頻帶寬度； (4) 畫出各種存儲器的邏輯示意圖。 8. (1)方式1 (高位交叉)的存儲器的地址格式為： 4 位20位 模塊選擇 字地址 方式2 (低位交叉)的存儲器的地址格式為： 20 位4位

8、字地址 模塊選擇 (2) 方式1 (高位交叉)的存儲器的優(yōu)點為：當(dāng)多處理機發(fā)出的訪存地址的高4位均不相同時，可對共 享存儲器內(nèi)的不同存儲體進(jìn)行同時存取，這種存儲器一般適合于共享存儲器的多處理機系統(tǒng)；缺點為：當(dāng) 多處理機發(fā)出的訪存地址的高 4位均相同時，便產(chǎn)生了存儲器的分體沖突，此時的存儲器的頻寬與單體存 儲器的相同。 方式2 (低位交叉)的存儲器的優(yōu)點為：當(dāng)處理機依次發(fā)出的訪存地址的低4位均不相同時，可對存 儲器內(nèi)的不同存儲體進(jìn)行并行存取，這種存儲器一般適合于單處理機內(nèi)的高速數(shù)據(jù)存取及帶Cache的主存; 缺點為：當(dāng)處理機依次發(fā)岀的訪存地址的低4位均相同時，便產(chǎn)生了存儲器的分體沖突，此時的存儲

9、器的 頻寬與單體存儲器的相同。 (3) 若不考慮訪問沖突，二種方式的存儲器的頻帶寬度均為64字節(jié)/存儲周期； (4) 二種存儲器的邏輯示意圖類似課本第3章圖和圖。 9. 在一個具有8個存儲體的低位多體交叉存儲器中，如果處理器的訪存地址為以下8進(jìn)制或16進(jìn)制值，分 別求該存儲器的平均訪問速率為單體存儲器的多少倍。(忽略初啟時的延遲) (1) 1001 8、10028、10038、11008 (2) 10028、10048、10068、12008 (3) 1003 16、100616、100916、130016 9. (1)8 ; (2)4 ; (3)8 11.在頁式虛擬存儲器中，一個程序由P1P

10、5共5個頁面組成。在程序執(zhí)行過程中依次訪問到的頁面如下： P2, P3, P2, P1，P5, P2, P4, P5, P3, P2, P5, P2 假設(shè)系統(tǒng)分配給這個程序的主存有3個頁面，分別采用FIFO、LRU和OPT三種頁面替換算法對這 3頁 主存進(jìn)行調(diào)度。分別畫岀這三種替換算法對同一頁地址流的調(diào)度過程，并計算每種替換算法獲得的命中率。 11.FIFO替換算法對頁地址流的調(diào)度過程如圖所示。 圖FIFO替換算法對頁地址流的調(diào)度過程 采用FIFO替換算法的頁命中率為。 LRU替換算法對頁地址流的調(diào)度過程如圖所示。 圖LRU替換算法對頁地址流的調(diào)度過程 采用LRU替換算法的頁命中率為。 OPT

11、替換算法對頁地址流的調(diào)度過程如圖所示。 圖OPT替換算法對頁地址流的調(diào)度過程 采用OPT替換算法的頁命中率為。 16. 假設(shè)在一個采用組相聯(lián)映象的 Cache存儲器中，Cache的容量為1KB,要求Cache的每一塊在一個主存 周期內(nèi)能從主存取得。主存采用模 32交叉，每個分體的寬度為 64位，主存的總?cè)萘繛?4MB采用按地址 訪問存儲器構(gòu)成的相聯(lián)目錄表，實現(xiàn)主存地址到Cache地址的變換，并約定采用 2個外相等比較電路。 (1) 請設(shè)計主存地址格式和 Cache地址格式，并標(biāo)出各段的位數(shù)； (2) 若替換算法采用LRU算法，對于如下主存塊地址流：1、4、1、4、7、1、9、4、27、7,如主

12、存中 內(nèi)容一開始未裝入 Cache中，請列出隨時間變化 Cache中各塊的使用狀況，求出此期間Cache的塊命中率。 16. (1) 主存地址格式如下： (2) 隨時間變化Cache中各塊的使用狀況如圖所示。 圖隨時間變化Cache中各塊的使用狀況 此期間Cache的塊命中率為。 17. 一個組相聯(lián)映象 Cache由64個存儲塊構(gòu)成，每組包含 4個存儲塊，主存包含 4096個存儲塊，每 塊由128字組成，訪存地址為字地址。設(shè)計主存地址格式和Cache地址格式并標(biāo)出各字段的位數(shù)。 17. 主存地址格式如下： 20.設(shè)某計算機的Cache-主存存儲層次采用組相聯(lián)映象和LRU替換算法，已知主存容量為

13、1MB Cache 容量為8KB，按4字塊分組，每個字塊的長度為8個字(32位/字)。假設(shè)Cache起始內(nèi)容為空，CPU從主 存單元0，1，2， ， 2079依次讀出2080個字，并重復(fù)此一讀數(shù)序列共5次。問Cache的地址命中率為 多少 20. 3. 指令的解釋方式采用順序、一次重疊和流水，其主要差別在什么地方流水方式與完全重復(fù)增加多 套解釋部件的方式相比各有什么優(yōu)缺點 3. 指令的解釋方式采用順序、一次重疊和流水，其主要差別在于可并行解釋指令的條數(shù)；流水方式 與完全重復(fù)增加多套解釋部件的方式相比，其優(yōu)點是省硬件、成本低，但缺點是控制復(fù)雜，要解決好指令 相關(guān)、數(shù)據(jù)相關(guān)，以及流水線的中斷等問題

14、。 5. 一臺非流水處理器 X的時鐘頻率為25MHZ平均CPI為4。處理器Y是對X機的改進(jìn)，它有一條5級流水 線，各級經(jīng)過的時間為一個時鐘周期。但由于鎖定器延遲和時鐘扭斜效應(yīng)，其時鐘頻率僅為20MHZ。 (1) 若含有 100 條指令的程序運行在兩臺處理機上時，假設(shè)每條指令之間不發(fā)生任何相關(guān)，求處理機Y 相對于處理機X的加速比為多少 (2) 計算執(zhí)行此程序時每臺處理機的MIPS速率。 5.(1) ； (2)X 處理機的MIPS速率為；Y處理機的MIPS速率為。 9. 已知一條由5個功能段組成的浮點加法流水線，每個功能段的延遲時間均t，流水線的輸出端 和輸入端之間有直接數(shù)據(jù)通路， 而且設(shè)置有足夠

15、的緩沖寄存器。 要求用盡可能短的時間完成計算 ，畫出流 水線時 - 空圖，并計算流水線的實際吞吐率、加速比和效率。 9. 流水線時-空圖如圖所示；流水線的實際吞吐率、加速比和效率分別為3/(7 t)、和%。 10. 一條線性靜態(tài)多功能流水線由6個功能段組成，加法操作使用其中的 1、 2、 3、 6功能段，乘法 操作使用其中的1、4、5、6功能段，每個功能段的延遲時間均t。流水線的輸入端與輸出端之間有直 接數(shù)據(jù)通路，而且設(shè)置有足夠的緩沖寄存器。現(xiàn)在用這條流水線計算，畫出流水線時 -空圖，并計算流水 線的實際吞吐率、加速比和效率。 10. 流水線時-空圖如圖所示；流水線的實際吞吐率、加速比和效率分

16、別為1/(2 t)、2和%。 13. 已知一流水線有5個功能段，依次分別為 S1、S2、S3、S4、S5,其中流經(jīng)S2需要2 t的時間，流經(jīng) S4需要3At的時間，其余各段所需時間均為t。現(xiàn)有6個任務(wù)流入流水線，要求： (1) 求流水線的實際吞吐率和效率； (2) 若把S2段進(jìn)一步細(xì)分，S4段并聯(lián)，令流水線最大吞吐率為1/ t，畫出流水線時-空圖，并求流水 線的效率。 13. (1) 流水線的實際吞吐率為 6/(23 t) ；效率為 % 。 (2) 流水線時 -空圖如圖所示；流水線的效率為 % 。 14. 在一個 5 段的流水線處理機上需經(jīng) 9 拍才能完成一個任務(wù)，其預(yù)約表如圖所示，分別寫出延

17、遲禁止表、 沖突向量，并求出最小平均延遲、流水線的最大吞吐率及其調(diào)度方案。若按此調(diào)度方案輸入6 個任務(wù)，求 實際吞吐率 TP。 圖 預(yù)約表 14. 延遲禁止表 F=1 ， 3， 4， 8 ； 沖突向量 C=； 最小平均延遲為拍； 調(diào)度方案為 (2 ， 5) ； 實際吞吐率 TP=6/(25 拍)。 4. 設(shè)32個處理器的編號分別為0、1、2、31,用單級互連網(wǎng)絡(luò)互連，若互連函數(shù)為： (1) Cube 3 (2) PM2 +3 (3) PM2 -4 (4) Shuffle (5) Butterfly (6) Shuffle(Shuffle) (7) Shuffle(Cube0(PM2-1 ) 時

18、，第 11 號處理器各與哪一個處理器相連 4. (1)3 ； (2)19； (3)27； (4)22； (5)26； (6)13； (7)16 5. 在有 8 個處理器的混洗交換網(wǎng)絡(luò)中，若要使第 0 號處理器與第 5號處理器相連需要經(jīng)過多少次混 洗和多少交換以連接圖的形式表明其變化過程。 5. 需要經(jīng)過 2 次混洗和 2 次交換，其連接圖如圖所示。 圖 實現(xiàn)第 0 號處理器與第 5號處理器相連的連接圖 6. 一個N=8的混洗交換網(wǎng)絡(luò)如圖所示。試問此網(wǎng)絡(luò)結(jié)點度為多少網(wǎng)絡(luò)直徑為多少網(wǎng)絡(luò)的等分帶寬為 多少 6. 此網(wǎng)絡(luò)結(jié)點度為 4；網(wǎng)絡(luò)直徑為 5；網(wǎng)絡(luò)的等分帶寬為 4 條鏈路的帶寬之和。 13.試在

19、含一個PE的SISD機和在含8個PE且連接成一線性環(huán)的 SIMD機上計算下列求內(nèi)積的表達(dá)式： 假定完成每次加操作需 2個單位時間，完成每次乘操作需4個單位時間，沿雙向環(huán)在相鄰PE間移數(shù)需 1 個單位時間。 (1) SISD計算機上計算S的時間是多少 (2) SIMD計算機上計算S的時間是多少 (3) 用SIMD機計算S相對于SISD機計算的加速比是多少 13.(1)190 個單位時間； (2)32 個單位時間； (3) 17.當(dāng)編號分別為0、1、2、15的16個處理器之間，要求按下列配對通信： (12,7 )，( 1,10 )，( 1 5,4 )，( 5,14)，( 8,3 )，( 6,13)

20、，( 11,0)，( 2,9 )。試選擇互連 網(wǎng)絡(luò)類型、控制方式，并畫出該互連網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和各級交換開關(guān)狀態(tài)圖。 17. 采用 4 級立方體網(wǎng)絡(luò)，級控制。互連網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和各級開關(guān)的狀態(tài)設(shè)置如圖所示。 圖 N=16 的互連網(wǎng)絡(luò)拓?fù)浼伴_關(guān)狀態(tài)圖 19. 并行處理機有 16 個處理器，要實現(xiàn)相當(dāng)于先 8組 2元交換，然后是 4 組 4 元交換，最后是 2 組 8 元交換，請寫出此時各處理器之間所實現(xiàn)的互連函數(shù)的一般關(guān)系式。 (P 3P2P1P0)=P 3P2P1P0 5.在CRAY-1向量處理機上，V為向量寄存器，設(shè)向量長度均為64,所用浮點功能執(zhí)行部件的執(zhí)行時間分別 為：加法需 6 拍，相乘

21、需 7 拍，從存儲器讀數(shù)需 6 拍，求倒數(shù)近似值需 14拍，打入寄存器及啟動功能部件 (包括存儲器)各需 1 拍。問下列各指令組中的哪些指令可以鏈接執(zhí)行哪些指令可以并行執(zhí)行試說明其原 因并分別計算出各指令組全部執(zhí)行完所需的拍數(shù)。 5.(1)3 條向量指令并行執(zhí)行；全部向量指令執(zhí)行完所需的時間為72 拍。 (2) 第 1、 2 條向量指令并行執(zhí)行；由于第 3 條向量指令與第 1、 2條向量指令之間存在源目向量相關(guān)， 因此它們之間可以鏈接執(zhí)行；全部向量指令執(zhí)行完所需的時間為80 拍。 (3) 第 1、 2 條向量指令并行執(zhí)行；第 3 條與第 2 條向量指令之間存在功能部件沖突，因此第 3 條向量 指令只能與前 2 條向量指令串行執(zhí)行；第 4 條向量指令與第 3 條向量指令之間存在源目向量相關(guān)，因此它 們之間可以鏈接執(zhí)行；全部向量指令執(zhí)行完所需的時間為 151 拍。 (4) 第 2 條向量指令與第 1 條向量指令之間、 第 3 條向量指令與第 2 條向量指令之間均存在源目向量相 關(guān)，因此這 3 條向量之間可以鏈接