第三章3.26 設16個處理器編號分別為0，1，…，15，要用單級互連網路，當互連函式分別為：（1）cube3（cube1） （5）butterfly（butterfly） （8） （9） （13）
時，第13號處理器分別與哪乙個處理器相連?
解：（1）因為cube3（cube1(x3x2x1x0)）= cube3(x3x2x1x0)= x3x2x1x0
所以13 → cube3（cube1(1101)）= 0100 → 4
（5）因為butterfly（butterfly(x3x2x1x0)）=butterfly（x0x2x1x3）=x3x2x1x0
所以13 →butterfly（butterfly (1101)）= 1101 → 13
（8）因為(x3x2x1x0)= x0x3x2x1 所以13 →(1101)= 1110 → 14
（9）因為(x3x2x1x0)= x3x2x0x1 所以13 →(1101)= 1110 → 14
（13）因為(x3x2x1x0)= x1x2x3x0 所以13 →(1101)= 0111 → 7
3.30 在有16個處理器的均勻洗牌網路中，若要使第0號處理器與第15號處理器相連，需要經過多少次均勻洗牌和交換置換。
解：0（0000b）號處理器與15（1111b）號處理器相連要對四位取反。交換置換一次只能對一位取反，所以要四次交換置換。
交換置換每次取反只對最低位，要有三次移位，所以要四次均勻洗牌置換。
即變換為0000(e)→ 0001(σ)→ 0010(e)→ 0011(σ)→ 0110(e)→ 0111(σ)→1110(e)→ 1111。
3.34 在編號分別為0，1，2，……，9的16個處理器之間，要求按下列配對通訊：(b、1)，(8、2)，(7、d)，(6、c)，(e、4)，(a、0)，(9、3)，(5、f)。
試選擇所用互連網路型別、控制方式，並畫出該互連網路的拓撲結構和各級的交換開關狀態圖。
解：16個處理機通過n = 16的互連網路互聯，通訊配對連線的二進位制編號為：
(0、a)：0000---10108、2)：1000---0010
(1、b)：0001---10119、3)：1001---0011
(2、8)：0010---1000a、0)：1010---0000
(3、9)：0011---1001b、1)：1011---0001
(4、e)：0100---1110c、6)：1100---0110
(5、f)：0101---1111d、7)：1101---0111
(6、c)：0110---1100e、4)：1110---0100
(7、d)：0111---1101f、5)：1111---0101
顯然要求互連網路實現的互聯函式為f（x3x2x1x0）= x3x2x1x0，為多重方體置換。
n = 16的staran網路在級控方式下實現的是方體置換，且當級控訊號為f = f3f2f1f0 = 1010時，實現的互聯函式是cube3（cube1（x3x2x1x0））= x3x2x1x0。所以採用n = 16的staran網路在級控方式且級控訊號f = 1010時，可實現要求配對通訊。
3.41 寫出n=8的蝶式置換的互連函式，如採用omega網路，則需幾次通過才能完成此變換？畫出omega網路實現此變換的控制狀態圖。
解：（1）n=8的蝶式置換的互連函式為：β（x2x1x0）= x0x1x2
（2）根據omega網路採用單元控制終端標記法尋徑方法，蝶式交換的連線關係及用n=8的omega網路實現該連線的開關要求如下表所示。
s d d2 d1 d0 k2級開關k1級開關k0級開關
0 0 0 0 0 與k21上輸出端連線與k11上輸出端連線與k01上輸出端連線
1 4 1 0 0 與k22下輸出端連線與k14上輸出端連線與k03上輸出端連線
2 2 0 1 0 與k23上輸出端連線與k11下輸出端連線與k02上輸出端連線
3 6 1 1 0 與k24下輸出端連線與k14下輸出端連線與k04上輸出端連線
4 1 0 0 1 與k21上輸出端連線與k11上輸出端連線與k01下輸出端連線
5 5 1 0 1 與k22下輸出端連線與k14上輸出端連線與k03下輸出端連線
6 3 0 1 1 與k23上輸出端連線與k11下輸出端連線與k02下輸出端連線
7 7 1 1 1 與k24下輸出端連線與k14下輸出端連線與k04下輸出端連線
由表可見，當實現八個結點對連線時，對k2級開關的要求將發生下列爭用開關輸出端的衝突：
0 → 0 和 4 → 1 爭用開關k21上輸出端
1 → 4 和 5 → 5 爭用開關k22下輸出端
2 → 2 和 6 → 3 爭用開關k23上輸出端
3 → 6 和 7 → 7 爭用開關k24下輸出端
因此，為避免k2級開關輸出端的衝突，八個結點對連線分兩次實現。第一次實現：0 → 0、1 → 4、2 → 2、3 → 6；第二次實現：
4 → 1、5 → 5、6 → 3、7 → 7。分兩次實現連線也避免k1級開關k11和k14輸出端的衝突，k0級四個開關沒有輸出端的衝突。
（3）omega網路分2次連線的開關狀態如下圖。
第一次第二次3.55 對於4方體網路見圖3-65，從結點0000到結點1111，有多少條最短路徑？為什麼？用e—立方維序尋徑演算法找出其中一條最短路徑。
解：（1）當源節點與目的節點的海明距離為h，則有h!條最短路徑。結點0000到結點1111的海明距離為4，所以有1×2×3×4=24條最短路徑。
（2）方向位向量r = s⊕d = 0000⊕1111 = 1111，v = s = 0000（源節點）
r1=1，v = v⊕2i-1 = 0000⊕0001 = 0001；
r2=1，v = v⊕2i-1 = 0001⊕0010 = 0011；
r3=1，v = v⊕2i-1 = 0011⊕0100 = 0111；
r4=1，v = v⊕2i-1 = 0111⊕1000 = 1111（目的結點）。
所以，0000與1111有一條最短路徑為：s=0000→0001→0011→0111→1111=d。
計算機體系結構
平行計算 之我見指導老師 陳麗萍 學院 資訊科學與工程學院 班級 計科0908班 姓名 原海南 學號 0909083125 完成日期 2012年5月21日 目錄1.平行計算簡介 1.1什麼是平行計算 1.2為什麼需要平行計算 1.3平行計算的歷史 1.4平行計算的現狀 2.平行計算與網際網路 2.1...
計算機體系結構習題答案
第1章計算機系統結構的基本概念 1.1 解釋下列術語 層次機構 按照計算機語言從低階到高階的次序，把計算機系統按功能劃分成多級層次結構，每一層以一種不同的語言為特徵。這些層次依次為 微程式機器級，傳統機器語言機器級，組合語言機器級，高階語言機器級，應用語言機器級等。虛擬機器 用軟體實現的機器。翻譯 ...
計算機體系結構第四章練習題參考解答
5 0.05 6 0.08 7 0.13 8 0.03 9 0.01 1 若對數字0 9和空格採用二進位制編碼，試設計編碼平均長度最短的編碼。2 若傳送106個文字元號，且每個文字元號後均自動跟乙個空格，按最短的編碼，共需傳送多少個二進位制位？若傳送波特率為9600bps，共需傳送多少時間？3 若對...