基本通信操作

1、第八章基本通信操作習(xí)題例題:1、對于一個2 4的網(wǎng)孔（處理器按行主方式依次編號為0, 1, 2, 3, 4, 5, 6, 7）,如何將其嵌入 3維超立方中?提示：將2 4的網(wǎng)孔使用Gray碼按行主對其進行編號。2、如圖8.15所示，信包中的片0, 1, 2, 3要分別去向目的地A,B,C,D。此日片0占據(jù)信道CB,片1占據(jù)信道DC片2占據(jù)信道BA。試問：這將會產(chǎn)生什么現(xiàn)象？11 il ikmIJ如果采用X-Y選路策略，可避免上述現(xiàn)象嗎？為什么？ri圖8.15蟲蝕選路網(wǎng)絡(luò)中所出現(xiàn)的現(xiàn)象3、假定在二叉樹中, 的二叉樹中，進行葉結(jié)點為處理器節(jié)點，內(nèi)結(jié)點為開關(guān)節(jié)點（參照圖 m個字的一到多傳播的通信時間

2、為：8.16）。試證明在p個葉節(jié)點ts mtw th log p 1 log p提示：信包穿越l1個開關(guān)節(jié)點所需要的時間為ts mtw thl。1圖8.16 8 個處理器的樹上一到多播送過程Ski 04、給定p個數(shù)n0,n1,冊1。所謂求前綴和(Pre巾xSum就是計算。其中0 k p 18個處理器的超立方上前綴和。算法8.3給出了超立方上的求前綴和的方法。試按此算法，計算算法8.3 d維超立方上前綴和算法輸入：p個數(shù)開始存在p個處理器中knii 0, 0 k p 1Sk輸出：第k個處理器存有前綴和Begin(1)result = my_number(2)msg = resultfor i =

3、 0 to d - 1 do(3.(1) Partner = my_id 2(3.(2) nd msg to Partner(3.(3) ceive number from Partner(3.(4) g = msg + number(3.(5) if ( Partner my_id ) then result =result + number endifend forEnd5、一到多個人通信又稱之為 單點散播(Single-Node Scatter ),它與一到多播送不同之處是，此時源 處理器有p個信包，每一個去向一個目的地(見圖 8.14 (c)。圖8.17示出了 8個處理器上的超立方 單

4、點散射的過程。試證明：使用 SF和CT方式在超立方上施行一到多個人通信的通信時間為：one to allperstslog p mtw p 1(h) Initial dislnbuticn 01 ni輻區(qū)aggf bi D ist ribut ion before th早 second skp(c) Distribution before the third step圖8.17 8個處理器的超立方上單點散射過程6、多到多個人通信又稱之為全交換( Total Exchange),每個處理器發(fā)送各自彼此不同的大小為m的信包給其余處理器(見圖 8.14 (d)。圖8.18示出了 6個處理器的環(huán)上全交

5、換的過程，其中， x, y表 示源處理器，目的處理器, (xi,y,x2,y2,，xn,yn)表示傳輸過程中的信包流，每個處理器只接收屬于它的信包。試證明：利用 SF方式，在環(huán)上施行全交換的通信時間為：ttotal -exchange，1、，、(t - mtw p)( p 1)提示：第i步傳送的信包大小為 m(p i)卜I i !i-feai I ! B4“ ；ZJi1Q!l j I5J;.： 心 氏4 E=Hh-I!V j ji (4tlJ!叫j _i ；Ofk”if 1.2: .RrSHici - i -( i rirfaifli-a-i SiaTpr dri i id*，irrtirira iii HiJ!翌Lgdlnu#也知44,1舟， .M：i：.；-L/ l 23圖8.18 6 個處理器的環(huán)上全交換過程7、在p個處理器所謂循環(huán)q-移位系指處理器i發(fā)送包給處理器（i q）modP 。圖8.19示出了按行主編號的Vp p 4 4環(huán)繞網(wǎng)孔上施行 5-移位的過程：首先按行同時循環(huán)移位（qm0dd;。次；然后作q/dp 1次列補償移位（如圖 8.19