南工大系統(tǒng)結(jié)構(gòu)試題庫(kù)

1、一、 選擇題 對(duì)系統(tǒng)程序員不透明的應(yīng)當(dāng)是 。 A Cache B 系列機(jī)各檔不同的數(shù)據(jù)通路寬度 C 指令緩沖器 D 虛擬存儲(chǔ)器 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)不包括 。 A 主存速度 B 機(jī)器工作狀態(tài) C 信息保護(hù) D 數(shù)據(jù)表示 屬于計(jì)算機(jī)系統(tǒng)考慮的是 。 A 主存采用MOS還是TTL B 主存采用多體交叉還是單體結(jié)構(gòu) C 主存的編址方式 D 主存頻寬的確定 從計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)上來(lái)看，機(jī)器語(yǔ)言程序員所看到機(jī)器屬性是 。 A 計(jì)算機(jī)軟件所要完成的功能 B 計(jì)算機(jī)硬件所要完成的功能 C 編程要用到的硬件組織 D 計(jì)算機(jī)各部件的硬件實(shí)現(xiàn) 系列機(jī)軟件應(yīng)做到 。 A 向后兼容，力爭(zhēng)向上兼容性 B 向前兼容，力爭(zhēng)向上兼容性

2、 C 向后兼容，力爭(zhēng)向下兼容性 D 向前兼容，力爭(zhēng)向下兼容性 利用時(shí)間重疊概念實(shí)現(xiàn)并行處理的是 。 A 多處理機(jī) B 相聯(lián)處理機(jī) C 并行（陣列）處理機(jī)動(dòng)性 D 流水處理機(jī) 計(jì)算機(jī)中優(yōu)化使用的操作碼編碼方法是 。 A 霍夫曼編碼 B ASCII 編碼 C 擴(kuò)展操作碼 D BCD碼 程序員編程時(shí)使用的地址是 。 A 物理地址 B 主存地址 C 有效地址 D 邏輯地址 塊沖突率最高的cache地址映象方式是 。 A 組相聯(lián) B 直接相聯(lián) C 段面相聯(lián) D 全相聯(lián) 影響流水線最大吞吐率是 。 A 各個(gè)功能段的時(shí)間 B 最快功能段的時(shí)間 C 最慢功能段的時(shí)間 D 最后一個(gè)功能段的時(shí)間 非線性流水線是指

3、 。 A 一次運(yùn)算中使用流水線中的多功能段 B 一次運(yùn)算中多次使用流水線中的某些多功能段 C 流水線中某些功能段在各次運(yùn)算中的作用不同 D 流水線的各功能段在各種運(yùn)算中有不同的組合 Cache地址映象中塊沖突率最低的是映象是 。A 全相聯(lián) B 頁(yè)相聯(lián)C 直接相聯(lián) D 組相聯(lián) 有8個(gè)結(jié)點(diǎn)的PM2I單級(jí)網(wǎng)絡(luò)的PM2-0(j)=(j-20)mod 8= A (7 6 5 4 3 2 1 0) B (0 1 2 3 4 5 6 7) C (7 5 3 1) (6 4 2 0) D(0 2 4 6) (1 3 5 7) 有8個(gè)結(jié)點(diǎn)的PM2I單級(jí)網(wǎng)絡(luò)的PM2+0(j)=(j+20)mod 8= A (7

4、6 5 4 3 2 1 0) B (0 1 2 3 4 5 6 7)C (7 5 3 1) (6 4 2 0) D(0 2 4 6) (1 3 5 7) 能實(shí)現(xiàn)作業(yè)、任務(wù)級(jí)并行的異構(gòu)型多處理機(jī)屬于 。A SIMD B SISDC MIMD D MISD 下列說(shuō)法正確的是 。A 一次重疊是一次解釋一條指令 B 一次重疊是同時(shí)解釋相鄰兩條指令C 流水方式是同時(shí)只能解釋兩條指令 D 一次重疊是可同時(shí)解釋多條指令 通道程序執(zhí)行結(jié)束后引起的中斷是 。A I/O中斷 B 程序性中斷C 內(nèi)中斷 D 機(jī)器校驗(yàn)中斷 打印機(jī)適合連接在 。A 數(shù)組多路通道 B 字節(jié)多路通道C 選擇通道 D 任意一種通道 disk適

5、合連接在 。A 數(shù)組多路通道或選擇通道 B 字節(jié)多路通道C 數(shù)組多路通道或字節(jié)多路通道 D 任意一種通道 21.通道程序執(zhí)行結(jié)束后引起的中斷是 。A 訪管中斷定 B I/O中斷C 外中斷 D 程序性中斷 22.利用時(shí)間重疊概念實(shí)現(xiàn)并行處理主是 。A 流水處理機(jī)動(dòng) B 多處理機(jī)C 相聯(lián)處理機(jī)動(dòng) D 并行（陣列）機(jī) 23.數(shù)據(jù)表示是 一部分。A 軟件的 B 硬件的C 軟硬件交界面的 D 非軟非硬的24. 是促使計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)發(fā)展的最重要的因素A 軟件 B 硬件 C 固件 D 器件25.計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)研究的范圍不包括 。A 指令系統(tǒng)的定義 B 計(jì)算機(jī)系統(tǒng)性能的評(píng)價(jià)C 軟硬件界面的定義 D 加法器的結(jié)

6、構(gòu)26. 交換互連網(wǎng)(立方體結(jié)構(gòu))編號(hào)為011的PE的3個(gè)相鄰PE的編號(hào)是 。 A 001，010，111 B 100，101，111 C 101，110，111 D 001，101，11027. 交換互連網(wǎng)(立方體結(jié)構(gòu))編號(hào)為000的PE的3個(gè)相鄰PE的編號(hào)是 。 A 001，010，111 B 100，101，111 C 101，110，111 D 001，010，10028. 在Cache更新策略中，在Cache不命中時(shí)把數(shù)據(jù)同時(shí)寫入Cache和M·M的策略是 。A 寫回法 B 寫直達(dá)法(全寫法) C 按寫分配法 D 不安寫分配法29. 在Cache更新策略中，在Cache不命

7、中時(shí)把數(shù)據(jù)從M·M調(diào)入Cache的策略是 。A 寫回法 B 寫直達(dá)法(全寫法) C 按寫分配法 D 不安寫分配法30. 相關(guān)專用通路 。A 解除數(shù)據(jù)相關(guān)性 B 減少數(shù)據(jù)相關(guān)引起的流水線停頓C 解除控制相關(guān)性 D 不能緩解流水線的相關(guān)性問(wèn)題31. 開(kāi)發(fā)粗粒度并行主要采用 。 P184 A 硬件手段 B 軟件手段C 軟硬件同時(shí)并舉 D 指令級(jí)并行32. 開(kāi)發(fā)細(xì)粒度并行主要采用 。 P184 A 硬件手段 B 軟件手段C 軟硬件同時(shí)并舉 D 作業(yè)級(jí)并行 33. SIMD結(jié)構(gòu)主要實(shí)現(xiàn)的是的 。 P200 A 作業(yè)級(jí)并行 B 任務(wù)級(jí)并行 C 指令操作級(jí)并行 D 指令內(nèi)操作步驟并行34. MIM

8、D結(jié)構(gòu)主要實(shí)現(xiàn)的是的 。 P200 A 作業(yè)級(jí)并行 B 任務(wù)級(jí)并行 C 指令操作級(jí)并行 D 指令內(nèi)操作步驟并行35. 設(shè)計(jì)互連網(wǎng)絡(luò)時(shí)應(yīng)考慮的特征有 個(gè)。 P190 A 4 B 3 C 2 D 1 36. 歸約機(jī)按歸約模型可分為 。A 數(shù)值歸約和串歸約 B 串歸約和圖歸約 C 數(shù)值歸約和圖歸約 D 指令歸約和數(shù)值歸約37. 模擬是采用 解決執(zhí)行方法。A 純硬件 B 以軟件為主，硬件為輔 C 純軟件 D 以硬件為主，軟件為輔38. 仿真是采用 解決執(zhí)行方法。A 純硬件 B 以軟件為主，硬件為輔 C 純軟件 D 以硬件為主，軟件為輔39. 對(duì)Amdahl提出關(guān)于計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)定義中所提到的“程序員”

9、比較一致的看法是 。A 機(jī)器語(yǔ)言程序員或編譯程序員 B 應(yīng)用程序員 C 高級(jí)語(yǔ)言程序員 D 任何程序員40. RWC(真實(shí)世界計(jì)算機(jī))計(jì)劃的主要研究?jī)?nèi)容有 方面。A 3 B 4 C 1 D 241. 在程序執(zhí)行中有 個(gè)方面因素會(huì)引起順序控制流發(fā)生變化。 P72A 1 B 3 C 4 D 2 42 依數(shù)據(jù)令牌的不同數(shù)據(jù)流計(jì)算機(jī)可分為 兩大類。A 數(shù)值流和非數(shù)值流 B 靜態(tài)和動(dòng)態(tài) C 數(shù)值流和圖流 D 令牌流和非令牌流二、填空 程序的局部性包括 的局部性和 的局部性。 CPU的Channel 輸入輸出指令的基本功能主要是： ， 以及 。虛擬存儲(chǔ)器對(duì) 程序員是透明的，對(duì) 程序員是不透明 的。通道按信

10、息傳送方式可分為 ， ， 三 類通道。 設(shè)通道數(shù)據(jù)傳送周期選擇一次設(shè)備的時(shí)間為TS，傳送一個(gè)字節(jié)的時(shí)間是TD，則傳 送n個(gè)字節(jié)的選擇通道的極限流量是fs.max= 。設(shè)通道數(shù)據(jù)傳送周期選擇一次設(shè)備的時(shí)間為TS，傳送一個(gè)字節(jié)的時(shí)間是TD，則有 K臺(tái)I/O設(shè)備的成組傳送極限流量fB.max= ，在“一次重疊”解釋時(shí)，第k條指令需等待第k-1條指令執(zhí)行后才能形成，稱此 時(shí)發(fā)生了 相關(guān)。在“一次重疊”解釋時(shí)，第k條指令的源數(shù)據(jù)與第k-1條指令的結(jié)果數(shù)據(jù)的地址 一樣，稱此時(shí) 發(fā)生了 相關(guān)。 多功能流水線各功能段同時(shí)只能按某一種功能聯(lián)接的稱為 流水線。 多功能流水線各功能段同時(shí)可以按不同的運(yùn)算或功能聯(lián)接工

11、作，此流水線稱為 流水線。 消除流水線速度瓶頸的方法有 和 兩種方法。P81解決重疊和流水線中的操作數(shù)相關(guān)，不外乎是 和 兩 種方法。P85系列機(jī)軟件兼容必須做到向 兼容，盡可能爭(zhēng)取向 兼 容。 提高計(jì)算機(jī)系統(tǒng)并行性重疊的主要技術(shù)途徑有時(shí)間重疊、 和 。 多處理機(jī)可以有同構(gòu)型、 和 三種。 多處理機(jī)有 和 兩種基本構(gòu)型。 并行性主要是指 和 兩重含義。多處理機(jī)系統(tǒng)在系統(tǒng)結(jié)構(gòu)上可分為 耦合和 耦合系 統(tǒng)。 按連接方式分，流水線可分為 流水線和 流水線。按功能分類，流水線可分為 流水線和 流水線。21.評(píng)價(jià)存儲(chǔ)器性能的基本要求是大容量、 和低價(jià)格。22.解決重疊和流水中的操作數(shù)相關(guān)，有推后法和 兩

12、種方法。23.從對(duì)執(zhí)行程序或指令的控制方式上，將計(jì)算機(jī)系統(tǒng)分為由控制驅(qū)動(dòng)的 流 和由數(shù)據(jù)驅(qū)動(dòng)的 流方式，按 驅(qū)動(dòng)的歸約方式和模式驅(qū)動(dòng)的匹配 方式。24.流水線按工作方式可分為 流水線和 流水線。25.流水線按處理級(jí)別可分為操作部件級(jí)、 級(jí)和 級(jí)三種。26.根據(jù)處理數(shù)據(jù)令牌的不同，數(shù)據(jù)流機(jī)的基本結(jié)構(gòu)可分為 和 兩大類。27.一個(gè)指令系統(tǒng)的設(shè)計(jì)主要是確定它的 、 、操作及對(duì)操作數(shù)的 訪問(wèn)方式。28.對(duì)實(shí)現(xiàn)基本操作來(lái)講，指令系統(tǒng)的不同只是反映在 和 不一樣。29.指令系統(tǒng)設(shè)計(jì)原則是應(yīng)特別注意如何支持 、簡(jiǎn)易地將源程序翻譯成 。30.在指令系統(tǒng)設(shè)計(jì)時(shí)應(yīng)注意 、 、 、 。31.指令系統(tǒng)結(jié)構(gòu)的分類主要是

13、依據(jù)在CPU中以何種存儲(chǔ)方式來(lái)存放操作數(shù)。 按照 這一特征，可將指令系統(tǒng)結(jié)構(gòu)分為 型、 型、 型三類。32.計(jì)算機(jī)應(yīng)用對(duì)系統(tǒng)結(jié)構(gòu)不斷提出的最基本要求是 、 和 。33.在RISC結(jié)構(gòu)中為了減少過(guò)程調(diào)用中保存現(xiàn)場(chǎng)和建立新現(xiàn)場(chǎng)，以及返回時(shí)恢復(fù)現(xiàn)場(chǎng) 等輔助操作，通常將全部寄存器分成若干組，稱為 。34. 對(duì)實(shí)現(xiàn)基本操作來(lái)講，指令系統(tǒng)的不同只是反映在 和 。P4235. 一般指令系統(tǒng)由 和 兩類指令組成。P4236. 指令系統(tǒng)結(jié)構(gòu)的分類主要是依據(jù)在CPU中以何種存儲(chǔ)方式來(lái)存放操作數(shù)。 按照這一特征，可將指令系統(tǒng)結(jié)構(gòu)分為 、 和 型三類。P4337. 通用寄存器型指令系統(tǒng)中，按照ALU指令有多少個(gè)個(gè)操作

14、數(shù)需要到存儲(chǔ)器中去存取，可以進(jìn)一步分為 、 和 型三類。P4438. 陣列機(jī)可分為兩個(gè)基本結(jié)構(gòu)， 和 。P18539. 在數(shù)據(jù)流計(jì)算機(jī)中信息項(xiàng)以操作包和“數(shù)據(jù)令牌”形式出現(xiàn)，其中數(shù)據(jù)包由 ， 和 組成。 P22840. AI處理的基本要點(diǎn)是基本知識(shí)的 ， 和 地加以利用。P242 41. “數(shù)據(jù)令牌”由 和 組成。 P22842. 構(gòu)成函數(shù)程序的主要成份是 、 和 。 P23543. 人工智能研究的關(guān)鍵在于 和 。 P24444. 陣列機(jī)通常由一個(gè) 、N個(gè) M個(gè) 和一個(gè) 組成。 P18545. 存儲(chǔ)器的命中率是 和 之比。 P12846. 緊耦合系統(tǒng)按所用處理機(jī)類型是否相同，常見(jiàn)的組合可分為

15、和 兩種基本構(gòu)型。 P20147. 在層次存儲(chǔ)結(jié)構(gòu)價(jià)格體系中命中判斷和數(shù)據(jù)傳輸對(duì)較高層次而言應(yīng)由 實(shí)現(xiàn)，對(duì)較低層次而言應(yīng)由 實(shí)現(xiàn)。48.依據(jù)處理數(shù)據(jù)令牌的不同，數(shù)據(jù)流機(jī)可分為 和 兩在類。 P23249.通常流水過(guò)程中會(huì)出現(xiàn) 、 和 三種相關(guān)。 P8350. 數(shù)據(jù)相關(guān)沖突可分為 、 和 三種類型 P8751. I/O控制操作：包括 、 。P158 三、計(jì)算假定要在一個(gè)時(shí)鐘速率為40MHz的標(biāo)量處理機(jī)上執(zhí)行一個(gè)典型測(cè)試程序，該程序 中含有4種類型指令，每種指令的條數(shù)和每種指令的CPI如下所示： 指令類型指令數(shù)CPIALU1200001Load/Store指令(Cache命中時(shí))360002轉(zhuǎn)移指

16、令240004訪存指令(Cache不命中時(shí))200008 計(jì)算在單處理機(jī)上執(zhí)行該程序的平均CPI。 根據(jù)所得的CPI值，計(jì)算相應(yīng)的MIPS速率。假定要在一個(gè)時(shí)鐘速率為40MHz的標(biāo)量處理機(jī)上運(yùn)行具有200000條指令的目標(biāo)代 碼，程序中含有4種類型指令，根據(jù)程序?qū)嶒?yàn)結(jié)果，已知指令混合比和每種指令 的CPI如下所示： 指令類型混合比CPIALU60%1Load/Store指令(Cache命中時(shí))18%2轉(zhuǎn)移指令12%4訪存指令(Cache不命中時(shí))10%8 計(jì)算在單處理機(jī)上執(zhí)行該程序的平均CPI。 根據(jù)所得的CPI值，計(jì)算相應(yīng)的MIPS速率。某模擬機(jī)有10條機(jī)器指令，使用頻度分別為：0.01，0

17、.15，0.12，0.07，0.08， 0.13，0.15，0.03，0.17，0.09。 寫出等長(zhǎng)操作碼編碼的平均碼長(zhǎng)； 構(gòu)造霍夫曼樹； 寫出只有兩種碼長(zhǎng)的最短的霍夫曼擴(kuò)展編碼及其平均碼長(zhǎng)。 某模擬機(jī)有7 條機(jī)器指令，使用頻度分別為：0.04，0.04，0.05，0.06，0.15， 0.26，0.40。 寫出等長(zhǎng)操作碼編碼的平均碼長(zhǎng)； 構(gòu)造霍夫曼樹； 寫出只有兩種碼長(zhǎng)的最短的霍夫曼擴(kuò)展編碼及其平均碼長(zhǎng)。有一個(gè)具有5個(gè)功能段組成的乘、加雙功能的靜態(tài)流水線，“乘”由1234 完成，“加”由154完成，各段時(shí)延均為Dt（見(jiàn)下圖），輸出可直接返回輸入 或存入緩沖存儲(chǔ)器?，F(xiàn)計(jì)算長(zhǎng)度均為8的A、B兩個(gè)

18、向量對(duì)應(yīng)元素求和的連乘積。 靜態(tài)雙功能流水線圖 畫出完成此運(yùn)算的流水線的運(yùn)行時(shí)空?qǐng)D； 完成全部運(yùn)算需要多少個(gè)Dt？其效率是多少？ 解：（共10分，時(shí)空?qǐng)D對(duì)了給3分。計(jì)算時(shí)公式對(duì)了而結(jié)果錯(cuò)了扣1分，公式錯(cuò)了全扣）時(shí)空?qǐng)D(4分)(6分，每個(gè)答案3分) TP=15/25t =3/5t E=(8×3t+7×4t)/(25×t)=52/125=0.416有一個(gè)具有4個(gè)功能段組成浮點(diǎn)加的靜態(tài)流水運(yùn)算器，各段時(shí)延均為Dt（見(jiàn)下圖）， 輸出可直接返回輸入或存入緩沖存儲(chǔ)器?，F(xiàn)以下述方式計(jì)算Z=a+b+c+d+e+f+g+h 畫出完成此運(yùn)算的流水線的運(yùn)行時(shí)空?qǐng)D； 分析其吞吐率和效率。

19、采用組相聯(lián)映象的Cache容量為1KB，要求Cache的每一塊能在1個(gè)主存周期內(nèi) 從主存讀取。主存結(jié)構(gòu)是模4交叉，每個(gè)分體寬為32位，總?cè)萘繛?56KB。用按 地址訪問(wèn)訪問(wèn)存儲(chǔ)器構(gòu)成相聯(lián)目錄表實(shí)現(xiàn)主存地址到Cache地址的變換，并約定 用4路比較電路。請(qǐng)?jiān)O(shè)計(jì)此相聯(lián)目錄表，求出該表行數(shù)、總位數(shù)和比較電路的位 數(shù)。對(duì)于一個(gè)有如下特征的虛擬存儲(chǔ)系統(tǒng)：l 40位虛擬地址l 16KB頁(yè)面l 36位物理地址 每個(gè)進(jìn)程的頁(yè)表的總長(zhǎng)度是多少？ 假定TLB用兩路組相聯(lián)方式的Cache，塊長(zhǎng)為8個(gè)字（4B），總?cè)萘繛?6KB，寫出其地址格式。假設(shè)Cache的工作速度為主存的5倍，且Cache被訪問(wèn)的概率為90%，

20、則采用Cache 后，整個(gè)存儲(chǔ)系統(tǒng)獲得多高的加速成比？ 胡越明 P103某字節(jié)多路通道欲連接6臺(tái)外設(shè)，其數(shù)據(jù)傳輸速率見(jiàn)下表。而通道選擇設(shè)備時(shí)間 需9.8ms，每個(gè)字節(jié)傳送需0.2ms，問(wèn)通道能否勝任所有設(shè)備同時(shí)工作？設(shè)通道在數(shù)據(jù)傳送期中，選擇設(shè)備需4.9s，傳送一個(gè)字節(jié)數(shù)據(jù)需0.1s。 其低速設(shè)備每隔250s發(fā)出一個(gè)字節(jié)數(shù)據(jù)傳送請(qǐng)求，問(wèn)最多可接多少臺(tái)這種設(shè) 備？若有AE共5種高速設(shè)備，要求字節(jié)傳送的時(shí)間時(shí)間如表，其時(shí)間單位為s。 若一次通信傳送的字節(jié)數(shù)不少于1024B，問(wèn)哪些設(shè)備可掛在此通道？如果某一計(jì)算任務(wù)用向量方式求解比用標(biāo)量方式求解要快20倍，稱可用向量方式 求解部分所花時(shí)間占總的時(shí)間的

21、百分比為可向量化百分比。問(wèn)為達(dá)到加速比為2， 可向量化百分比應(yīng)是多少？某系統(tǒng)某一功能改進(jìn)后其速度是原來(lái)的10倍，而該功能的處理時(shí)間僅為整個(gè)系統(tǒng) 運(yùn)行時(shí)間的40%，則用此增強(qiáng)功能方法后，整個(gè)系統(tǒng)的性能提高多少？設(shè)二級(jí)虛擬存儲(chǔ)器的TV1=10-7s，TV2=10-2s，若要求訪問(wèn)時(shí)間TV達(dá)到1ms，問(wèn)訪問(wèn) 一級(jí)存儲(chǔ)器的命中率應(yīng)是多少？設(shè)Cache塊為16字，對(duì)于下列2種M·M結(jié)構(gòu)：如果M·M的訪問(wèn)延時(shí)為4個(gè)時(shí)鐘周期，訪存地址和1個(gè)字的傳輸時(shí)間各為1時(shí)鐘個(gè)周期，數(shù)據(jù)傳輸后還需1個(gè)周期的恢復(fù)時(shí)間，問(wèn)這兩種M·M結(jié)構(gòu)在Cache訪問(wèn)失效時(shí)的塊訪問(wèn)時(shí)間各是多少？假設(shè)Cache

22、命中時(shí)的指令平均執(zhí)行時(shí)間為1.2周期，平均每條指令訪存時(shí)間為1.5次，Cache的命中命中率為99%，問(wèn)這兩種M·M結(jié)構(gòu)中指令的平均執(zhí)行時(shí)間。設(shè)1個(gè)任務(wù)的處理時(shí)間為64s，CPU在這段時(shí)間內(nèi)始終忙于處理，I/O處理時(shí)間為36s。為了提高系統(tǒng)性能，有兩種方案：使CPU的速度增加1倍，或者使CPU和I/O的處理速度同時(shí)增加1倍。計(jì)算這兩種情況下的處理時(shí)間。 設(shè)16 個(gè)處理器編號(hào)分別為0，1，15。采用單級(jí)互網(wǎng)互連，當(dāng)互連函數(shù)分別為Cube3PM2-3ShuffleBtterflyExchange時(shí)第11號(hào)處理器各與哪一個(gè)處理器相連。設(shè)16個(gè)處理器編號(hào)分別為0，1，15。采用單級(jí)互網(wǎng)互連，

23、當(dāng)互連函數(shù)分別為Cube3PM2-3ShuffleBtterflyExchange時(shí)第9號(hào)處理器各與哪一個(gè)處理器相連。某模擬機(jī)有7 條機(jī)器指令，使用頻度分別為：0.01，0.01，0.03，0.05，0.15， 0.30，0.45。 寫出等長(zhǎng)操作碼編碼的平均碼長(zhǎng)； 構(gòu)造霍夫曼樹； 寫出只有兩種碼長(zhǎng)的最短的霍夫曼擴(kuò)展編碼及其平均碼長(zhǎng)。某模擬機(jī)有10條機(jī)器指令，使用頻度分別為：I1：0.2，I2：0.12，I3：0.11，I4：0.05，I5：0.08，I6：0.03，I7：0.02，I8：0.18，I9：0.10，I10：0.01。 寫出等長(zhǎng)操作碼編碼的平均碼長(zhǎng)； 構(gòu)造霍夫曼樹； 寫出只有兩種碼

24、長(zhǎng)的最短的霍夫曼擴(kuò)展編碼及其平均碼長(zhǎng)。 胡越民書P12321.某模擬機(jī)有10條機(jī)器指令，使用頻度分別為：I1：0.2，I2：0.12，I3：0.11，I4：0.05，I5：0.08，I6：0.03，I7：0.02，I8：0.18，I9：0.10，I10：0.01。 寫出等長(zhǎng)操作碼編碼的平均碼長(zhǎng)； 構(gòu)造霍夫曼樹； 寫出只有兩種碼長(zhǎng)的最短的霍夫曼擴(kuò)展編碼及其平均碼長(zhǎng)。22.假定要在一個(gè)時(shí)鐘速率為40MHz的標(biāo)量處理機(jī)上執(zhí)行一個(gè)典型測(cè)試程序，該程序 中含有4種類型指令，每種指令的條數(shù)和每種指令的CPI如下所示： 指令類型指令數(shù)CPIALU450001Load/Store指令(Cache命中時(shí))320

25、002轉(zhuǎn)移指令150002訪存指令(Cache不命中時(shí))80002計(jì)算在單處理機(jī)上執(zhí)行該程序的平均CPI。根據(jù)所得的CPI值，計(jì)算相應(yīng)的MIPS速率。 計(jì)算總的CPU執(zhí)行時(shí)間TCPU。23.某模擬機(jī)有9 條機(jī)器指令，使用頻度分別為：I1：0.3，I2：0.24，I3：0.06，I4：0.07，I5：0.07，I6：0.02，I7：0.03，I8：0.2，I9：0.01 寫出等長(zhǎng)操作碼編碼的平均碼長(zhǎng)； 構(gòu)造霍夫曼樹； 寫出只有兩種碼長(zhǎng)的最短的霍夫曼擴(kuò)展編碼及其平均碼長(zhǎng)。24.一臺(tái)流水計(jì)算機(jī)A的工作頻率為25MHz，平均CPI為4。計(jì)算機(jī)B是A的改進(jìn)型，有一條5段的線性指令流水線，時(shí)鐘頻率為20

26、MHz。問(wèn)：若在A和B兩臺(tái)計(jì)算機(jī)上執(zhí)行含有100條指令的程序，則計(jì)算機(jī)B對(duì)A的加速比是多少？在執(zhí)行上述程序時(shí)，計(jì)算機(jī)A和B的MIPS速率各是多少？25.某單功能非線性流水線的預(yù)約表如下：1234567S1*S2*S3*S4*寫出禁止表F和沖突向量C。畫出該流水線狀態(tài)圖，確定其最佳調(diào)度方案和最小平均流水速率。 計(jì)算按此流水線調(diào)度方案執(zhí)行8個(gè)任務(wù)所需的時(shí)間。計(jì)算按此流水線在執(zhí)行8個(gè)任務(wù)時(shí)的吞吐率、加速比和利用率。 胡越明書P22926.某單功能非線性流水線的預(yù)約表如下： 123456789S1*S2*S3*S4*S5*寫出禁止表F和沖突向量C。畫出該流水線狀態(tài)圖，確定其最佳調(diào)度方案和最小平均流水速

27、率。 計(jì)算按此流水線調(diào)度方案執(zhí)行8個(gè)任務(wù)所需的時(shí)間。計(jì)算按此流水線在執(zhí)行8個(gè)任務(wù)時(shí)的吞吐率、加速比和利用率。 27. 假定要在一個(gè)時(shí)鐘速率為40MHz的標(biāo)量處理機(jī)上運(yùn)行具有200000條指令的目標(biāo)代碼，程序中含有4種類型指令，根據(jù)程序?qū)嶒?yàn)結(jié)果，已知指令混合比和每種指令的CPI如下所示： 指令類型混合比CPIALU43%1Load/Store指令(Cache命中時(shí))21%2轉(zhuǎn)移指令24%2訪存指令(Cache不命中時(shí))12%2 計(jì)算在單處理機(jī)上執(zhí)行該程序的平均CPI。 根據(jù)所得的CPI值，計(jì)算相應(yīng)的MIPS速率。28 某臺(tái)計(jì)算機(jī)只有Load/Store指令能對(duì)M·M進(jìn)行讀/寫操作,其他

28、指令只能對(duì)寄存器 進(jìn)行操作。根據(jù)實(shí)驗(yàn)的結(jié)果，已知每種指令所占的比例和CPI如下表所示： 指令類型混合比CPIALU43%1Load/Store指令(Cache命中時(shí))21%2轉(zhuǎn)移指令24%2訪存指令(Cache不命中時(shí))12%2 計(jì)算上述情況的平均CPI。 假設(shè)程序由M條指令組成，算術(shù)邏輯運(yùn)算中，25%的指令兩個(gè)操作數(shù)中的一個(gè)已在寄存器中，另一個(gè)必須在算術(shù)邏輯指令執(zhí)行前用Load指令從M·M中讀取到寄存器中。因此，有人建議增加另一種算術(shù)邏輯指令，其特點(diǎn)是一個(gè)操作數(shù)取自寄存器中，另一個(gè)操作數(shù)取自M·M，即寄存器-存儲(chǔ)器型。做假設(shè)這種指令的CPI等于2，同時(shí)轉(zhuǎn)移指令的CPI變?yōu)?/p>

29、3。求新指令系統(tǒng)的平均CPI。胡越明P2229.某計(jì)算機(jī)字長(zhǎng)32位，包含兩個(gè)選擇通道和一個(gè)多路通道，每個(gè)選擇通道上連接2臺(tái)磁盤機(jī)和2臺(tái)磁帶機(jī)，多路通道上連接2臺(tái)行式打印機(jī)、兩2臺(tái)讀卡機(jī)和10臺(tái)終端。假定各設(shè)備傳輸速率如下：磁盤機(jī)：800KBps磁帶機(jī)：200KBps行打機(jī)：6.6KBps讀卡機(jī)：1.2KBps終端： 1KBps求該計(jì)算機(jī)系統(tǒng)的最大I/O數(shù)據(jù)傳輸速率。 張春元P17030. 一個(gè)字節(jié)多路通道連接有5臺(tái)設(shè)備，它們的數(shù)據(jù)傳輸率如下表：設(shè)備名稱D1D2D3D4D5數(shù)據(jù)傳輸速率(KB/s)10033.333.32010 計(jì)算這個(gè)字節(jié)多路通道的實(shí)際工作流量。 為了使通道能夠正常上作，請(qǐng)?jiān)O(shè)計(jì)

30、通道的最大流量和工作周期 31. 一個(gè)字節(jié)多路通道連接D1、D2、D3、D4、D5共5臺(tái)，這些設(shè)備分別每10s、30s、30s、50s和75s向通道發(fā)出一次數(shù)據(jù)傳送的服務(wù)請(qǐng)求。回答下列問(wèn)題： 計(jì)算這個(gè)字節(jié)多路通道的實(shí)際流量和工作周期。如果設(shè)計(jì)字節(jié)多路通道的最大流量正好等于實(shí)際流量，并假定對(duì)數(shù)據(jù)傳輸率高的設(shè)備，通道響應(yīng)它的數(shù)據(jù)傳送請(qǐng)求助優(yōu)先級(jí)也高。5臺(tái)設(shè)備在0時(shí)刻同時(shí)向通道發(fā)出第一次傳送數(shù)據(jù)的請(qǐng)求，并在以后的時(shí)間里按照各自的數(shù)據(jù)傳輸率連續(xù)工作。畫出通道分時(shí)為各臺(tái)設(shè)備服務(wù)的時(shí)間關(guān)系圖，并計(jì)算這個(gè)字節(jié)多路通道處理完各臺(tái)設(shè)備的第一次數(shù)據(jù)傳送請(qǐng)求的時(shí)刻。從時(shí)間關(guān)系圖上可以發(fā)現(xiàn)什么問(wèn)題?如何解決這個(gè)問(wèn)題?

31、 解這個(gè)字節(jié)多路通道的實(shí)際流量為fbyte(1/10+1/30+1/30+1/50+1/75)=0.2MB/s 通道助工作周期為t1/ f=5s/B，包括通道選擇設(shè)備的時(shí)間Ts和為設(shè)備傳送1個(gè)字節(jié)所用的時(shí)間Td。 5臺(tái)設(shè)備向通道請(qǐng)求傳送數(shù)據(jù)和通道為它們服務(wù)的時(shí)間關(guān)系如圖所示。向上的箭頭表示設(shè)備的數(shù)據(jù)傳送請(qǐng)求，有陰影的長(zhǎng)方形表示通道響應(yīng)設(shè)備的請(qǐng)求并為設(shè)備服務(wù)所用的時(shí)間間隔，包括通道選擇設(shè)備的時(shí)間和為設(shè)備傳送一個(gè)字節(jié)所用的時(shí)間，這兩部分時(shí)間之和為5s。在圖，5臺(tái)設(shè)備在。時(shí)刻同時(shí)向通道發(fā)出第數(shù)據(jù)的請(qǐng)求通道處理各個(gè)設(shè)備第一次請(qǐng)求時(shí)間如下： 處理完設(shè)備D1的第一次請(qǐng)求的時(shí)刻為5s。 處理完設(shè)備D2的第一

32、次請(qǐng)求的時(shí)刻為10s。 處理完設(shè)備D3的第一次請(qǐng)求的時(shí)刻為20s。 處理完設(shè)備D4的第一次請(qǐng)求的時(shí)刻為30s。 設(shè)備D5的第一次請(qǐng)求沒(méi)有得到響應(yīng)，直到第85Ps通道才開(kāi)始響應(yīng)設(shè)備D的服務(wù)請(qǐng)求，這時(shí)，設(shè)備已經(jīng)發(fā)出了2個(gè)傳送數(shù)據(jù)的服務(wù)請(qǐng)求，因此，第次傳送的數(shù)據(jù)有可能要丟失。 由圖可知，當(dāng)字節(jié)多路通道的最大流量與連接在這個(gè)通道上的所有設(shè)備的數(shù)據(jù)流量之和非常接近時(shí)，如果傳輸速度高的設(shè)備頻繁發(fā)出服務(wù)請(qǐng)求，并且優(yōu)先得到響應(yīng)，那么某些低速設(shè)備可能在很長(zhǎng)的一段時(shí)間內(nèi)得不到響應(yīng)。32.個(gè)4段的雙輸入端規(guī)格化浮點(diǎn)加法流水線（見(jiàn)下圖），每段經(jīng)過(guò)時(shí)問(wèn)10ns，輸出可直接返回輸入或?qū)⒔Y(jié)果暫存下相應(yīng)緩沖器中。問(wèn)最少需經(jīng)多

33、少時(shí)間能求出： 在下坐標(biāo)中畫出完成此運(yùn)算的流水線的運(yùn)行時(shí)空?qǐng)D(橫坐標(biāo)每小格代表10ns，縱坐標(biāo)每小格代表1個(gè)功能段)；（4分）y0x 流水線從開(kāi)始流入到結(jié)果流出這段時(shí)間的實(shí)際吞吐率TP和效率EP。（6分，每問(wèn)3分）l 答案解： 時(shí)空?qǐng)D(4分)l (6分)TP=9/17t EP=（4´6+3´4）/ (17´4)=36/68=52.9%33. 有一個(gè)流水線由四段組成，其中每當(dāng)流經(jīng)第三段時(shí)，總要在該段循環(huán)一次才能流到第四段(見(jiàn)下圖)。如果每段經(jīng)過(guò)一次的時(shí)間都是t，現(xiàn)連續(xù)輸入10個(gè)任務(wù)，問(wèn)： 當(dāng)在流水線的輸入端每t時(shí)間輸入任務(wù)時(shí)，該流水線會(huì)發(fā)生什么情況? 2分 畫處理1

34、0個(gè)任務(wù)的時(shí)空?qǐng)D。（4分） 求連續(xù)處理10個(gè)任務(wù)的實(shí)際吞吐率TP和效率EP。（4分，每問(wèn)2分）l 答案解： 產(chǎn)生流水線的阻塞（產(chǎn)生流水線的停頓或斷流或不連續(xù)）（2分） 時(shí)空?qǐng)D(4分) (6分) TP=10/23t期 EP=（10´3+10´2）/ (23´4)=50/92=54.35 % 34. 假設(shè)一臺(tái)計(jì)算機(jī)的I/O處理占10，當(dāng)其CPU性能改進(jìn)到原來(lái)的10倍時(shí)，而I/O性能僅改進(jìn)為原來(lái)的兩倍時(shí)，則加速比是多少?l 答案解：改進(jìn)后I/O的運(yùn)行時(shí)間是原來(lái)的1/2，CPU為原來(lái)的1/100。所以SP=1/(0.1/2+0.9/100)=16.94 35. 在一個(gè)4段

35、的流水線處理機(jī)上需經(jīng)7柏才能完成一個(gè)任務(wù)，其預(yù)約表如下表所示。 分別寫出延遲禁止表F、沖突向量；畫出流水線狀態(tài)轉(zhuǎn)移圖，求出最小平均延遲及流水線的最大吞吐率及其調(diào)度時(shí)的最佳方案。按此流水調(diào)度方案，輸入6個(gè)任務(wù)求實(shí)際的吞吐率。時(shí)間段號(hào)t1t2t3t4t5t6t7S1×××S2××S3×S4××l 答案解： 禁止表F=2，4，6；初始沖突向量C=（101010） 狀態(tài)轉(zhuǎn)移圖調(diào)度方案平均延遲（1，7）4（3，5）4（5，3）455最小的平均延遲為4拍。此時(shí)流水線的最大吞吐率Tpmax=1/4（任務(wù)/拍）最佳調(diào)度方案宜選其中

36、按(1，7)周期性助調(diào)度的方案接(1，7)調(diào)度方案輸入6個(gè)任務(wù)、全部完成的時(shí)間為 1+7+1+7+1+7=24(拍)實(shí)際吞吐率Tp=6/24（任務(wù)/拍）若按(3、5)調(diào)度方案輸入6個(gè)任務(wù)全部完成的時(shí)間為 3+5+3+5+3+7=26(拍)實(shí)際吞吐率Tp=6/26（任務(wù)/拍）若按(3、5)調(diào)度方案輸入6個(gè)任務(wù)全部完成的時(shí)間為 5+3+5+3+5+7=28(拍)實(shí)際吞吐率Tp=6/28（任務(wù)/拍）可見(jiàn)最傳的方案應(yīng)當(dāng)為(1，7)調(diào)度方案。36. 假設(shè)Tm是主存的R/W時(shí)間，Cache的工作速度為主存的5倍，且Cache訪問(wèn)命中的概率為90，則 求平均訪問(wèn)時(shí)間。 采用Cache后，與單獨(dú)使用主存比性能

37、提高多少? (4分)l 答案解： Cache的工作速度為主存的5倍。則Cache訪問(wèn)時(shí)間TC= Tm/5。Ta0.10×Tm+0.90×Tm/5=0.28 Tm (4分) 性能為原來(lái)的1/0.283.57倍，即提高了2.57倍。(4分)或用阿姆達(dá)爾定律求解：37. 下圖給出了一個(gè)非線性流水線。若有4條指令依次間隔4t進(jìn)入流水線。請(qǐng)畫出時(shí)空?qǐng)D，并求出實(shí)際吞吐率和效率。若要使流水線每隔2t流出一個(gè)結(jié)果，應(yīng)減少流水線上哪個(gè)功能段的經(jīng)過(guò)時(shí)間？應(yīng)減少到多少，方能滿足要求？（10分） l 答案解：解：（共10分，時(shí)空?qǐng)D對(duì)了給3分。計(jì)算時(shí)公式對(duì)了而結(jié)果錯(cuò)了扣1分，公式錯(cuò)了全扣）時(shí)空?qǐng)D：

38、吞吐率Tp=4/(22t) 效率 h =(3´8t+4´2t)/(4´22t)=40/88=5/11將號(hào)功能段時(shí)時(shí)間減少為1t（或號(hào)功能段的總通過(guò)時(shí)時(shí)間為2t），方能滿足要求。38. 某模擬機(jī)有9 條機(jī)器指令，使用頻度分別為：I1：0.3，I2：0.24，I3：0.06，I4：0.07，I5：0.07，I6：0.02，I7：0.03，I8：0.2，I9：0.01 （10分）寫出等長(zhǎng)操作碼編碼的平均碼長(zhǎng)；構(gòu)造霍夫曼樹；寫出只有兩種碼長(zhǎng)的最短的霍夫曼擴(kuò)展編碼及其平均碼長(zhǎng)。l 答案解：解：（共10分，霍夫曼樹編碼不唯一，但平均碼長(zhǎng)的計(jì)算結(jié)果是唯一的，計(jì)算時(shí)公式對(duì)了而結(jié)果錯(cuò)了扣1分；公式錯(cuò)了全扣）等長(zhǎng)操作碼平均碼長(zhǎng)為4位?；舴蚵鼧渌曰舴蚵幋a：I1：10，I2：00，I3：1110，I4：1101，I5：1100，I6：111110，I7：11110，I8：01，I9：111111平均碼長(zhǎng)：2´（0.30+0.24+0.2）+4´（0.06+0.07+0.07）+5´0.03+6´（0.02+0.01）=2.61 只有兩種編碼的最短霍夫曼擴(kuò)展編碼是I1：00，I2：01，I8：10，I3：11000，I4：11001，I5：11010，I6：11011，I7：11100，I9：111