第八章基本通訊操作

第八章基本通訊操作第一頁(yè)，共三十九頁(yè)，編輯于2023年，星期四第三篇并行數(shù)值算法

第八章基本通訊操作

第九章稠密矩陣運(yùn)算

第十章線性方程組的求解

第十一章快速傅里葉變換

第二頁(yè)，共三十九頁(yè)，編輯于2023年，星期四第八章并行數(shù)值算法

8.0預(yù)備知識(shí)

8.1選路方法與開關(guān)技術(shù)

8.2單一信包一到一傳輸

8.3一到多播送

8.4多到多播送

第三頁(yè)，共三十九頁(yè)，編輯于2023年，星期四

預(yù)備知識(shí)選路(Routing)又稱為選徑或路由。產(chǎn)生消息從發(fā)源地到目的地所取的路徑,要求具有較低通訊延遲、無(wú)死鎖和容錯(cuò)能力。應(yīng)用于網(wǎng)絡(luò)或并行機(jī)上的信息交換。消息、信包、片

消息(Message)：是在多計(jì)算機(jī)系統(tǒng)的處理接點(diǎn)之間傳遞包含數(shù)據(jù)和同步消息的信息包。它是一種邏輯單位，可由任意數(shù)量的包構(gòu)成。包(Packet)：包的長(zhǎng)度隨協(xié)議不同而不同，它是信息傳送的最小單位，64-512位。片(Flit)：片的長(zhǎng)度固定，一般為8位。第四頁(yè)，共三十九頁(yè)，編輯于2023年，星期四預(yù)備知識(shí)消息、信包、片的相互關(guān)系包消息包據(jù)片頭片尾片……順序號(hào)數(shù)片F(xiàn)FFFFFFF第五頁(yè)，共三十九頁(yè)，編輯于2023年，星期四

預(yù)備知識(shí)一些術(shù)語(yǔ)

信道帶寬b：每個(gè)信道有w位寬和信號(hào)傳輸率f=1/t(t是時(shí)鐘周期),

b=wfbits/sec節(jié)點(diǎn)和開關(guān)的度：與節(jié)點(diǎn)和開關(guān)相連的信道數(shù)目路徑：信包在網(wǎng)絡(luò)中走過(guò)的開關(guān)和鏈路(link)序列路由長(zhǎng)度或距離：路由路徑中包括的鏈路(link)數(shù)目信包傳輸性能參數(shù)啟動(dòng)時(shí)間ts(startuptime)：準(zhǔn)備包頭信息等節(jié)點(diǎn)延遲時(shí)間th(per-hoptime)：包頭穿越相鄰節(jié)點(diǎn)的時(shí)間字傳輸時(shí)間tw(transfertime)：傳輸每個(gè)字的時(shí)間鏈路數(shù)l、信包大小m第六頁(yè)，共三十九頁(yè)，編輯于2023年，星期四

預(yù)備知識(shí)選路算法的三種機(jī)制

基于算術(shù)的:開關(guān)中具有簡(jiǎn)單的算術(shù)運(yùn)算功能，如維序選路；基于源地址的:在源點(diǎn)時(shí)就將沿路徑的各個(gè)開關(guān)的輸出端口地址p0,p1,…,pn包在信包的頭部，每個(gè)開關(guān)只是對(duì)信包頭的輸出端口地址進(jìn)行剝離；基于查表的:開關(guān)中含有一個(gè)選路表，對(duì)信包頭中的選路域查出輸出端口地址。第七頁(yè)，共三十九頁(yè)，編輯于2023年，星期四

預(yù)備知識(shí)選路方式

第八頁(yè)，共三十九頁(yè)，編輯于2023年，星期四第八章并行數(shù)值算法

8.0預(yù)備知識(shí)

8.1選路方法與開關(guān)技術(shù)

8.2單一信包一到一傳輸

8.3一到多播送

8.4多到多播送

第九頁(yè)，共三十九頁(yè)，編輯于2023年，星期四8.1選路方法與開關(guān)技術(shù)

8.1.1選路方法

8.1.2開關(guān)技術(shù)

第十頁(yè)，共三十九頁(yè)，編輯于2023年，星期四

選路方法分類最短路徑/非最短路徑(貪心選路/隨機(jī)選路)，如維序選路是貪心的，二階段維序選路是隨機(jī)的確定選路/自適應(yīng)選路(尋徑確定/尋徑視網(wǎng)絡(luò)狀況)維序選路(Dimension-OrderedRouting)：一種確定的最短路徑選路二維網(wǎng)孔中的維序選路:X-Y選路超立方中的維序選路:E-立方選路

第十一頁(yè)，共三十九頁(yè)，編輯于2023年，星期四

選路方法X-Y選路算法算法8.1：二維網(wǎng)孔上的X-Y選路算法

beginstep1:沿X方向?qū)⑿虐椭聊康牡靥幚砥魉诘牧衧tep2:沿Y方向?qū)⑿虐椭聊康牡靥幚砥魉诘男衑nd第十二頁(yè)，共三十九頁(yè)，編輯于2023年，星期四

選路方法例8.1(P186)第十三頁(yè)，共三十九頁(yè)，編輯于2023年，星期四

選路方法E-立方選路算法路由計(jì)算：sn-1sn-2…s1s0(源地址)異或dn-1dn-2…d1d0(目的地址)rn-1rn-2…r1r0(路由值)路由過(guò)程：sn-1sn-2…s1s0sn-1sn-2…s1s0r0

sn-1sn-2…s1s0r1…算法8.2：超立方網(wǎng)絡(luò)上的E-立方選路算法(P186)第十四頁(yè)，共三十九頁(yè)，編輯于2023年，星期四

選路方法例8.2(P187)

0110(S)1101(D)1011(R)第十五頁(yè)，共三十九頁(yè)，編輯于2023年，星期四8.1選路方法與開關(guān)技術(shù)

8.1.1選路方法

8.1.2開關(guān)技術(shù)

第十六頁(yè)，共三十九頁(yè)，編輯于2023年，星期四

開關(guān)技術(shù)存儲(chǔ)轉(zhuǎn)發(fā)(Store-and-Forward)選路消息被分成基本的傳輸單位----信包(Packet),每個(gè)信包都含有尋徑信息；當(dāng)一個(gè)信包到達(dá)中間節(jié)點(diǎn)A時(shí)，A把整個(gè)信包放入其通信緩沖器中，然后在選路算法的控制下選擇下一個(gè)相鄰節(jié)點(diǎn)B，當(dāng)從A到B的通道空閑并且B的通信緩沖器可用時(shí)，把信包從A發(fā)向B；信包的傳輸時(shí)間:tcomm

(SF)=ts+(mtw+th)l=O(ml)

缺點(diǎn)：每個(gè)結(jié)點(diǎn)必須對(duì)整個(gè)消息和信包進(jìn)行緩沖，緩沖器較大；網(wǎng)絡(luò)時(shí)延與發(fā)送消息所經(jīng)歷的節(jié)點(diǎn)數(shù)成正比第十七頁(yè)，共三十九頁(yè)，編輯于2023年，星期四

開關(guān)技術(shù)切通(CutThrough)選路在傳遞一個(gè)消息之前，就為它建立一條從源結(jié)點(diǎn)到目的結(jié)點(diǎn)的物理通道。在傳遞的全部過(guò)程中，線路的每一段都被占用，當(dāng)消息的尾部經(jīng)過(guò)網(wǎng)絡(luò)后，整條物理鏈路才被廢棄。傳輸時(shí)間:tcomm

(CT)=ts+mtw+lth=O(m+l)缺點(diǎn)：物理通道非共享傳輸過(guò)程中物理通道一直被占用第十八頁(yè)，共三十九頁(yè)，編輯于2023年，星期四

開關(guān)技術(shù)蟲孔(Wormhole)選路Dally于1986年提出，利用了前二種方法的優(yōu)點(diǎn)，減少了緩沖區(qū)，提高了物理通道的利用。首先把一個(gè)消息分成許多很小的片，消息的頭片包含了這個(gè)消息的所有尋徑信息。尾片是一個(gè)其最后包含了消息結(jié)束符的片。中間的片均為數(shù)據(jù)片；片是最小信息單位。每個(gè)結(jié)點(diǎn)上只需要緩沖一個(gè)片就能滿足要求；用一個(gè)頭片直接牽引一條從輸入鏈路到輸出鏈路的路徑的方法來(lái)進(jìn)行操作。每個(gè)消息中的片以流水的方式在網(wǎng)絡(luò)中向前“蠕動(dòng)”。每個(gè)片相當(dāng)于Worm的一個(gè)節(jié)，“蠕動(dòng)”以節(jié)為單位順序地向前爬行。當(dāng)消息的尾片向前“蠕動(dòng)”一步后，它剛才所占用的結(jié)點(diǎn)就被放棄了。第十九頁(yè)，共三十九頁(yè)，編輯于2023年，星期四

開關(guān)技術(shù)蟲孔(Wormhole)選路

優(yōu)點(diǎn)：(1)每個(gè)結(jié)點(diǎn)的緩沖器的需求量小，易于用VLSI實(shí)現(xiàn)；(2)較低的網(wǎng)絡(luò)傳輸延遲。存儲(chǔ)轉(zhuǎn)發(fā)傳輸延遲基本上正比于消息在網(wǎng)絡(luò)中傳輸?shù)木嚯x;Wormhole與線路開關(guān)的網(wǎng)絡(luò)傳輸延遲正比于消息包的長(zhǎng)度，傳輸距離對(duì)它的影響很?。ㄏ^長(zhǎng)時(shí)的情況）；(3)通道共享性好、利用率高；(4)易于實(shí)現(xiàn)Multicast和Broadcast。第二十頁(yè)，共三十九頁(yè)，編輯于2023年，星期四

開關(guān)技術(shù)幾種開關(guān)技術(shù)的時(shí)空?qǐng)D

第二十一頁(yè)，共三十九頁(yè)，編輯于2023年，星期四第八章并行數(shù)值算法

8.0預(yù)備知識(shí)

8.1選路方法與開關(guān)技術(shù)

8.2單一信包一到一傳輸

8.3一到多播送

8.4多到多播送

第二十二頁(yè)，共三十九頁(yè)，編輯于2023年，星期四

單一信包一到一傳輸距離l的計(jì)算：對(duì)于p個(gè)處理器一維環(huán)形：帶環(huán)繞Mesh()：超立方：tcomm(SF)的計(jì)算(可由(8.1b)式得到)一維環(huán)形：帶環(huán)繞Mesh：超立方：tcomm(CT)的計(jì)算(可由(8.2b)式得到)

如果m>>p：tcomm(SF)≈tcomm(CT)=ts+mtw第二十三頁(yè)，共三十九頁(yè)，編輯于2023年，星期四第八章并行數(shù)值算法

8.0預(yù)備知識(shí)

8.1選路方法與開關(guān)技術(shù)

8.2單一信包一到一傳輸

8.3一到多播送

8.4多到多播送

第二十四頁(yè)，共三十九頁(yè)，編輯于2023年，星期四8.3一到多播送

8.3.1SF模式

8.3.2CT模式

第二十五頁(yè)，共三十九頁(yè)，編輯于2023年，星期四一到多播送—SF模式環(huán)步驟：①先左右鄰近傳送;②再左右二個(gè)方向同時(shí)播送示例：

通訊時(shí)間：

第二十六頁(yè)，共三十九頁(yè)，編輯于2023年，星期四一到多播送—SF模式環(huán)繞網(wǎng)孔步驟：①先完成一行中的播送;②再同時(shí)進(jìn)行各列的播送示例：共4步(2步行、2步列)通訊時(shí)間：

第二十七頁(yè)，共三十九頁(yè)，編輯于2023年，星期四一到多播送—SF模式超立方步驟：從低維到高維，依次進(jìn)行播送;示例：

通訊時(shí)間：

第二十八頁(yè)，共三十九頁(yè)，編輯于2023年，星期四8.3一到多播送

8.3.1SF模式

8.3.2CT模式

第二十九頁(yè)，共三十九頁(yè)，編輯于2023年，星期四一到多播送—CT模式環(huán)步驟：

(1)先發(fā)送至p/2遠(yuǎn)的處理器;(2)再同時(shí)發(fā)送至p/22遠(yuǎn)的處理器;……(i)再同時(shí)發(fā)送至p/2i遠(yuǎn)的處理器;示例：圖8.8通訊時(shí)間：

第三十頁(yè)，共三十九頁(yè)，編輯于2023年，星期四一到多播送—CT模式網(wǎng)孔步驟：

(1)先進(jìn)行行播送;(2)再同時(shí)進(jìn)行列播送;

示例：圖8.9通訊時(shí)間：

第三十一頁(yè)，共三十九頁(yè)，編輯于2023年，星期四一到多播送—CT模式超立方步驟：

依次從低維到高維播送,d-立方,d=0,1,2,3,4…;通訊時(shí)間：

第三十二頁(yè)，共三十九頁(yè)，編輯于2023年，星期四第八章并行數(shù)值算法

8.0預(yù)備知識(shí)

8.1選路方法與開關(guān)技術(shù)

8.2單一信包一到一傳輸

8.3一到多播送

8.4多到多播送

第三十三頁(yè)，共三十九頁(yè)，編輯于2023年，星期四8.3一到多播送

8.3.1SF模式

8.3.2CT模式

第三十四頁(yè)，共三十九頁(yè)，編輯于2023年，星期四多到多播送—SF模式環(huán)步驟：同時(shí)向右(或左)播送剛接收到的信包示例：圖8.10通訊時(shí)間：

已有數(shù)據(jù)第2步傳送數(shù)據(jù)2第三十五頁(yè)，共三十九頁(yè)，編輯于2023年，星期四多到多播送—SF模式環(huán)繞網(wǎng)孔步驟：(1)先進(jìn)行行的播送；(2)再進(jìn)行列的播送；示例：圖8.1