11．設有乙個15000條指令地程式在一台時鐘頻率為25mhz的流水處理機上執行。假設該指令流水線有5段，並且每個時鐘週期發射一條指令。忽略由於指令相關造成的損失。
(a) 用該流水線執行這一程式，並用通過延遲時間與其相等的乙個等效非流水線處理機執行同一程式，將兩者加以比較，並計算其加速比。
(b) 該流水線處理機的效率和吞吐率是多少？
解：(a) 等效的非流水處理機執行一條指令需要的時間是5個時鐘週期。按照加速比定義，應有
(b) 效率為
(c) 吞吐率為
2．（15分）一動態多功能流水線由６個功能段組成，如下圖：
其中：s1、s4、s5、s6組成乘法流水線，s1、s2、s3、s6組成加法流水線，各個功能段時間均為50ns。假定該流水線的輸出結果可以直接返回流水線輸入端，而且設定有足夠的緩衝暫存器。
若按照最快的方式用該流水線計算。
（1）（8分）請畫出其處理過程的時空圖。
（2）（7分）計算其實際吞吐率，加速比和效率。
[答案]
(1)：
乘法操作用到的流水段有：s1、s4、s5、s6；加法操作用到的流水段有：s1、s2、s3、s6。以最快的方式處理的流水線時空圖如圖所示：
(2)：a部分所處理的是；b部分所處理的是；c部分所處理的是。
整個處理過程共需22個時鐘週期。而進行了14次不同的運算，所以其實際吞吐率為：
這些運算序列處理所需要的時鐘週期為56個時鐘週期，所以其加速比為：
效率為：
3. （13分）如圖所示，輸入端為8個處理機，輸出端為8個儲存器，通過**立
方體互連網路連線，採用級控方式。其中所有交換開關均為二功能(控制訊號
為「0」時直通，為「1」時交換)。若級控訊號為：①k0k1k2＝100；②k0k1k2
＝110；③k0k1k2＝111；請在表中填寫出對應於8個處理機而實際連通的8
個儲存器的排列順序 。
解輸入排列輸出排列（存貯器處理機） k0k1k2=100 k0k1k2=110 k0k1k2=11104671576264537544023513262017310
4. 請用塊結構語言 cobegin-coend 寫出圖 4.3 中所示巢狀並行演算法優
先關係圖的程式。
解：begin s0; cobegins1begins2cobegin s3; s4; s5; s6; s7; coends8ends9; coend s10; end
5．一台單處理機採用如下序列程式實現 s＝a1＋a2＋a3＋a4＋a5＋a6＋a7
＋a8 各矩陣（均為n×n）的累加求和運算：
a1＝a1＋a2a3＝a3＋a4a5＝a5＋a6a7＝a7＋a8a1＝a1＋a3a5＝a5＋a7a1＝a1＋a5 現用4臺多處理機系統實現上述矩陣的求和運算。請畫出任務優先關係
圖，並用塊結構語言 cobegin-coend 寫出並行程式。
解：根據所給條件，採用 4 臺處理機時序列程式可做如下改造：
s0 傳送資料
s1 a1 = a1+a2
s2 a3 = a3+a4
s3 a5 = a5+a6
s4 a7 = a7+a8
s5 傳送資料
s6 a1 = a1+a3
s7 a5 = a5+a7
s8 傳送資料
s9 a1 = a1+a5
由此可畫出並行優先關係圖如圖 5.5 所示。
並行程式如下：
begin
s0;cobegin s1; s2; s3; s4; coend
s5;cobegin s6; s7; coend
s8;s9;end6. （13分）設 e 為交換函式，s 為均勻洗牌函式，b 為蝶式函式，pm2i為移
數函式，函式的自變數是十進位制數表示的處理機編號。現有 32 臺處理機，其
編號為 0、1、2、……、31。 （1）分別計算下列互連函式e2(12) s(8) b(9) pm2i+3(28) e0(s(4)) s(e0(18)) （2）用 e0 和 s 構成均勻洗牌交換網（每步只能使用 e0 和 s 一次）,網路
直徑是多少？從 5 號處理機傳送資料到 7 號處理機,最短路徑需要經過幾
步？列出經過的處理機編號。 解：
（1）e2（12）= 8 s（8）= 16 b（9）= 24 pm2i+3（28）= 4 e0（s（4））= e0（8）= 9 s（e0（18））= s（19）= 7 （2）網路直徑是 9 ，最短路徑需要經過 6 步00101 e000101 s 01000 e001001 s 10010 e010011 s 00111
7.（13分）（1）畫出 2×2開關構成的 16 個輸入端的 omega 網路。 （2）結點 11 傳送資訊給結點 5 ，同時結點 7 傳送資訊給結點 9 ，畫出完
成這一尋徑的開關設定。這種情況會出現阻塞嗎？ 解：
（1）16 個輸入端的 omega 網路如圖8.5 所示。 （2）尋徑開關設定見圖8.5 所示，因此不會出現阻塞
8.分布儲存器的simd並行處理機，8個pe用pm2i移數網連線。計算，求最短執行時間。
向量x分布存放在各個pe的區域性儲存器中，標量a存放在控制部件cu的儲存器中，從記憶體讀乙個資料到暫存器需要10ns，做一次乘法需要20ns，做一次加法需要15ns，從cu廣播乙個資料到所有pe或在相鄰pe之間傳送乙個資料需要5ns，最終結果s可以放在任意pe的暫存器中，取指令、解碼、讀暫存器、寫暫存器的時間忽略不計。寫出主要計算步驟。
t＝讀a＋廣播a＋加a＋pm2＋乘法＋pm2i
＋乘法＋pm2i＋乘法
＝10＋5＋15＋ 5＋20＋5＋20＋5＋20
＝105ns
體系結構複習題
41.在dlx流水線中，可以在id段檢測所有資料相關。42.容量失效卻隨著容量的增加而增加。43.預取必須和正常訪存操作並行才有意義。44.採用容量小 結構簡單的cache會減小cache的命中時間。45.cache失效中必定包含容量失效。46.mips是測量計算機效能的一致性指標。47.平均每條指...
計算機體系結構習題答案
第1章計算機系統結構的基本概念 1.1 解釋下列術語 層次機構 按照計算機語言從低階到高階的次序，把計算機系統按功能劃分成多級層次結構，每一層以一種不同的語言為特徵。這些層次依次為 微程式機器級，傳統機器語言機器級，組合語言機器級，高階語言機器級，應用語言機器級等。虛擬機器 用軟體實現的機器。翻譯 ...
計算機體系結構複習題 有答案
體系結構複習題 一 選擇題 15分 1 計算機系統多級層次中，從下層到上層，各級相對順序正確的應當是 a.組合語言機器級 作業系統機器級 高階語言機器級 b.微程式機器級 傳統機器語言機器級 組合語言機器級 c.傳統機器語言機器級 高階語言機器級 組合語言機器級 d.組合語言機器級 應用語言機器級 ...