【正文】 完成全部運算最少需要45拍。 (3)在這種結構的處理器上求點積A*B的時空圖如圖0512所示： 圖0512 完成全部運算最少需要30拍。 (4)在這種結構的處理器上求點積A*B的時空圖如圖0513所示： 圖0513完成全部運算最少需要26拍。 剖析：向量A*B的點積為A*B=(8)∑(i=1)ai*bi=a1*b1+a2*b2+a3*b3+a4*b4+a5*b*+a6*b*+a7*b7+a8*b8,共需8次乘法和7次加法。 360/91解決流水線控制的一般方法、途徑和特點。 在流水線中設置相關直接通路解決局部相關； 用猜測法解決全局相關； 設置向后8條檢查，加快短循環(huán)程序的處理； 對流水線的中斷處理用不精確斷點法。 ，其預約表為： t0t1t2t3t4t5t6t7t8s1∨∨s2∨∨s3∨∨∨s4∨∨s5∨∨分別寫出延遲禁止表F、沖突向量C。畫出流水線狀態(tài)轉移圖。求出最小平均延遲及流水線的最大吞吐率及其高度方案。按此流水高度方案輸入6個任務，求實際吞吐率。 解： 根據(jù)預約表，延遲禁止表F={1，3，4，8} 沖突向量為C:10001101 狀態(tài)轉移圖如圖0514所示 圖0514 各種方案的平均延遲表：調度方案(2,5)(2,7)5(5,6)(6)(6,7)(7)平均延遲567，其調度方案為（2，5）。 按調度方案（2，5）輸入6個任務時的時空圖如圖0515所示： 圖0515 實際吞吐率TP=6/25(任務/拍)。 剖析：求延遲禁止表F={1，3，4，8}，第一行間隔8，第二行間隔1，第三行間隔1，3，4，然后間隔都為1，合并。 求沖突向量，寫一個8位兩進制數(shù)，根據(jù)禁止表倒著寫。 由于初始沖突向量的c2,c5,c6,c7為0，所以第二個任務可以距第一個任務2，5，6或7拍流入流水線。 =A*(B+C)，各向量元素均為N，參照CRAY－1方式分解為3條向量指令： 1：V3＜存儲器｛訪存取A送入V3寄存器組｝ 2：V2＜V0＋V1｛B＋C＞K｝ 3：V4＜V2＋V3｛K＊A＞D｝ 當采用下列3種方式工作時需多少拍才能得到全部結果？ （1）串行執(zhí)行。 （2）1和2并行執(zhí)行完后，再執(zhí)行3。 （3）采用鏈接技術。 解: （1）每條指令所需拍數(shù)為： 指令1：1（啟動訪存）+6（訪存）+1（存V3）+N1（第一個分量后每隔1拍出一個結果）=7+N 指令2：1（送浮加部件）+6（浮加）+1（存V2）+N1=7+N 指令3：1（送浮乘部件）+7（浮乘）+1（存V4）+N1=8+N 串行：7+N+7+N+8+N=22+3N （2）指令1和2并行執(zhí)行：1（啟動訪存，送浮加部件）+6（訪存，浮加）+1（存V3，存V2）+N1=7+N 1，2并行：7+N+8+N=15+2N （3）1+6+1+1++7+1+N1=16+N ，以CRAY1機上所用浮點功能部件的執(zhí)行時間分別為：相加6拍，相乘7拍，求倒數(shù)近似值14拍。從存儲器讀數(shù)6拍，打入寄存器及啟動功能部件各1拍。問下列各指令組內的哪些指令可以鏈接？哪些指令不能鏈接？不能鏈接的原因是什么？分別計算出各指令組全部完成所需的拍數(shù)。 (1)(2)(3)(4)V0←存儲器V1←V2+V3V4←V5*V6V2←V0*V1V3←存儲器V4←V2+V3V0←存儲器V2←V0*V1V3←V2+V0V5←V3+V4V0←存儲器V1←1/V0V3←V1*V2V5←V3+V4解：(1)3條向量指令之間既沒有發(fā)生源Vi沖突，也沒有Vi的先寫后讀相關，又不存在功能部件的使用沖突，所以這3條向量指令可以同時并行流水。max{(1+6(訪存)+1+641),(1+6(浮加)+1+641),(1+(7浮乘)+1+641)}=72拍。所以向量指令組全部完成需要72(拍)。 (2)3條向量指令之間沒有功能部件的使用沖突，但是在第2兩條向量指令與第3條向量指令之間有V2及V3的先寫后讀相關。只要讓第1條向量指令較第2條向量指令提前1拍啟動，則第1,2兩條向量指令的第1個結果元素就可以被同時鏈接到第3條向量指令中。max{(1+(7浮乘)+1+641),(1+6(訪存)+1+641)}+(1+6(浮加)+1+641)=80(拍)。 (3)第1條向量指令與第2條向量指令之間有V0的先寫后讀相關，兩者可以鏈接。第3條向量指令與第2條向量指令之間有源向量寄存器V0的沖突，它們之間只能串行。第3條向量指令與第4條向量指令之間有加法功能部件的使用沖突，它們之間也只能串行。(1+6(訪存)+1+1+(7浮乘)+1+641)+(1+6(訪存)+1+641)(1+6(浮加)+1+641)=222(拍)。 (4)4條向量指令均依次有Vi的先寫后讀相關，但無源Vi沖突，也無功能部件的使用沖突，所以，這4條向量指令可以全部鏈接在一直，進行流水。(1+6(訪存)+1)+(1+14(求倒數(shù))+1)+(1+(7浮乘)+1)+(1+6(浮加)+1)+641=104拍。 、分析、執(zhí)行三個子部件組成。每個子部件經(jīng)過時間為△t，連續(xù)執(zhí)行12條指令。請分別畫出在常規(guī)標量流水處理機及度m均為4的超標量處理機、超長指令字處理機、超流水線處理機上工作的時空圖，分別計算它們相對常規(guī)標量流水處理機的加速比Sp。 解： 常規(guī)標量處理機的時空圖： 度m為4的超標量處理機的時空圖： 其相對于常規(guī)標量流水處理機的加速比Sp=14△t/5△t= 度m為4的超長指令字處理機的時空圖：其相對于常規(guī)標量流水處理機的加速比Sp=14△t/5△t= 度m為4的超流水線處理機的時空圖： 其相對于常規(guī)標量流水處理機的加速比Sp=14△t/△t=56/23≈ 第六章　陣列處理機 Ⅳ 的模式進行互連的互連結構圖，列出PE0分別只經(jīng)一步、二步和三步傳送能將信息傳送到的各處理器號。 答:6臺處理器仿ILLIAC Ⅳ 處理單元的互連結構如圖所示： 圖中第個PU中包含PE、PEM和MLU。 PE0(PU0)經(jīng)一步可將信息傳送至PUPUPU1PU15。 PE0(PU0)至少需經(jīng)二步才能將信息傳送至PUPUPUPUPU1PU1PU14。 PE0(PU0)至少需經(jīng)三步步才能將信息傳送至PUPUPUPU10。 、...、15的16個處理器，用單級互連網(wǎng)互連。當互連函數(shù)分別為 (1)Cube3 (2)PM2+3 (3)PM20 (4)Shuffle (5)Shuffle(Shuffle) 時，第13號處理器各連至哪一個處理器？ 解答：(1)5號處理器 (2)5號處理器 (3)12號處理器 (4)11號處理器 (5)7號處理器 剖析：由題意知，有16個處理器，即N=16,n=log2(N)=log2(16)=4。 Cube3(13)=Cube3(1101)=0101=5 PM2+3(13)=(13+2^3)mod16=5 PM20(13)=(132^0)mod16=12 Shuffle(13)=Shuffle(1101)=1011=11 Shuffle(Shuffle)=Shuffle(11)=Shuffle(1011)=0111=7 、...、F的16個處理器之間要求按下列配對通信：(B、1)，(2)，(D)，(C)，(E、4)，(A、0)，(3)，(F)。試選擇所用互連網(wǎng)絡類型、控制方式，并畫出該互連網(wǎng)絡的拓補結構和各級交換開關狀態(tài)圖。 解答：采用4級立方體網(wǎng)絡，級控制。該互連網(wǎng)絡的拓補結構和各級交換開關狀態(tài)圖如下圖所示： 剖析：從處理器號的配對傳送關系可以轉成處理器二進制編號的配對傳送關系： (B,1) (1011,0001) (8,2) (1000,0010) (7,D) (0111,1101) (6,C) (0110,1100) (E,4) (1110,0100) (A,0) (1010,0000) (9,3) (1001,0011) (5,F) (0101,1111) 不難得出其一般規(guī)律是：二進制編號為P3P2P1P0的處理器與(￣P3)P2(￣P1)P0的處理器配對交換數(shù)據(jù)。由于實現(xiàn)的都是交換函數(shù)的功能，采用成本最低的級控制多級立方體互聯(lián)網(wǎng)絡就可以實現(xiàn)。 N=16的多級立方體網(wǎng)絡，由n=log2(16)=4組成。每一級均使用N/2=8個二功能交換開關。多級網(wǎng)絡各級的級號由入端到出端依次為0、(P3...Pi...P0)=P3...(￣Pi)...P0函數(shù)。根據(jù)本題的要求，應當讓第3級的各交換單元處于“交換”狀態(tài)，第0、2級的各交換單元處于“直連”狀態(tài)。 、...、F共16個處理器之間實現(xiàn)多級立方體互連的互連網(wǎng)絡，采用級控制信號為1100(從右至左分別控制第0級至第3級)時，9號處理器連向哪個處理器？ 解答：多級立方體互連網(wǎng)絡的圖和第3題的圖基本一致，不同之處在于，第0、1級的開關狀態(tài)為直連，第3級的開關狀態(tài)為交換。 9號處理器在經(jīng)過0級和1級交換開關后，連向哪第10個處理器。在經(jīng)過2級交換開關后，連向第4個處理器。在經(jīng)過3級交換開關后，連向第9個處理器。 ，當?shù)趇級(0=i=2)為直連狀態(tài)時，不能實現(xiàn)哪些結點之間的通信？為什么？反之，當?shù)趇級為交換狀態(tài)呢？ 解答：當?shù)趇級為直連狀態(tài)時，不能實現(xiàn)入、出兩端的處理器二進制編碼的編號中，第Pi位取反的處理器之間的連接。例如，第0級為直連狀態(tài)時，入端號為0的處理器僅能與出端號為0的處理器進行數(shù)據(jù)傳送，不能與出端號為1的處理器進行數(shù)據(jù)傳送。因為交換開關的直連狀態(tài)被定義為i入連i出，j入連j出，所以，反映出實現(xiàn)互連的入、出端號的二進制碼中的Pi位是不能變反的，其它的各位可以不變，也可以變反。 當?shù)趇級為交換狀態(tài)時，不能實現(xiàn)入、出兩端的處理器二進制編碼的編號中，第Pi位相同的處理器之間的連接。例如，第0級為交換狀態(tài)時，入端號為0的處理器僅能與出端號為1的處理器進行數(shù)據(jù)傳送，不能與出端號為0的處理器進行數(shù)據(jù)傳送。因為交換開關的直連狀態(tài)被定義為i入連j出，j入連i出，所以，反映出實現(xiàn)互連的入、出端號的二進制碼中的Pi位必須變反，其它的各位可以不變，也可以變反。 *8矩陣A=(aij)，順序存放在存儲器的64個單元中，用什么機關報單級互連網(wǎng)絡可實現(xiàn)對該矩陣的轉置變換？總共需要傳送多少步？ 解答： 采用單級混洗互連網(wǎng)絡可實現(xiàn)對8*8矩陣的轉置變換，共需傳送3步。 剖析：8*8矩陣中任一元素aij，它在存儲器中所占的位置是i*8+j(即i*2^3+j)。每個元素的行坐標和列坐標均用3位表示，設b5b4b3為行下標的二進制編號，b2b1b0為列下標的二進制編號，經(jīng)過3次全混洗后，元素下標號b5b4b3b2b1b0就變成了b2b1b0b5b4b3，即行下標的二進制編號改成了b2b1b0，列下標的二進制編號改成了b5b4b3，這樣，就實現(xiàn)了矩陣的行列轉置。 ~7號共8個處理器的三級混洗交換網(wǎng)絡，在該圖上實現(xiàn)將6號處理器數(shù)據(jù)播送給0~4號，同時將3號處理器數(shù)據(jù)播送給其余3個處理器時的各有關交換開關的控制狀態(tài)。 解答：8個處理器的三級混洗交換網(wǎng)絡及其交換開關控制狀態(tài)設置如下圖所示： ，然后是2組8元交換，再次是1組16元交換的交換函數(shù)功能，請寫出此時各處理器之間所實現(xiàn)的互連函數(shù)的一般式，畫出相應多級網(wǎng)絡的拓撲結構圖，標出各組交換形狀的狀態(tài)。 解答：互連函數(shù)的一般式為：Cubei(P3P2P1P0)=(￣P3P2￣P1￣P0)。 多級立方體互連網(wǎng)絡的拓撲結構圖和第3題的圖基本一致，不同之處在于，第0、3級的開關狀態(tài)為直連，第2級的開關狀態(tài)為交換。 =2^n個輸入端的Omega網(wǎng)絡，采用單元控制。 (1)N個輸入總共可有多少種不同的排列； (2)該Omega網(wǎng)絡通過一次可以實現(xiàn)的置換可有多少種是不同的。 (3)若N=8,計算出一次通過能實現(xiàn)的置換數(shù)占全部排列數(shù)的百分比。 解答： (1)N個輸入總共可有N!種不同的排列。 (2)該Omega網(wǎng)絡通過一次可以實現(xiàn)的置換可有2^((N/2)log2(N))=N^(N/2)種是不同的。 (3)若N=8,通過Omega網(wǎng)絡一次可以實現(xiàn)的不重復置換有8^4=4096種。8個輸入總共可實現(xiàn)的不重復排列有8!=40320種。所以，一次通過能實現(xiàn)的置換數(shù)占全部排列數(shù)的百分比為4096/40320*100%≈% =8的立方體全排列多級網(wǎng)絡，標出采用單元控制，實現(xiàn)0→3,1→7,2→4,3→0,4→2,5→6,6→1,7→5的同時傳送時的各交換開關的狀態(tài)。說明為什么不會發(fā)生阻塞。 解答： 實現(xiàn)N=8的立方體全排列多級網(wǎng)絡及交換形狀狀態(tài)如下圖所示 在一到的映射時，交換開關