并 行 計 算 中國科學(xué)技術(shù)大學(xué)計算機科學(xué)與技術(shù)系國家高性能計算中心(合肥)2004年12月Date1現(xiàn)代密碼學(xué)理論與實踐之五第三篇 并行數(shù)值算法 第八章 基本通訊操作 第九章 稠密矩陣運算 第十章 線性方程組的求解 第十一章 快速傅里葉變換 Date2現(xiàn)代密碼學(xué)理論與實踐之五第八章 并行數(shù)值算法 8.0 預(yù)備知識 8.1 選路方法與開關(guān)技術(shù) 8.2 單一信包一到一傳輸 8.3 一到多播送 8.4 多到多播送 Date3現(xiàn)代密碼學(xué)理論與實踐之五 預(yù)備知識 選路(Routing) 又稱為選徑或路由產(chǎn)生消息從發(fā)源地到目的地所取的路徑, 要求具有較低通訊延遲、無死鎖和容錯能力應(yīng)用于網(wǎng)絡(luò)或并行機上的信息交換 消息、信包、片 消息(Message)：是在多計算機系統(tǒng)的處理接點之間傳遞包含數(shù)據(jù)和同步消息的信息包它是一種邏輯單位，可由任意數(shù)量的包構(gòu)成 包(Packet)：包的長度隨協(xié)議不同而不同，它是信息傳送的最小單位，64-512位 片(Flit)：片的長度固定，一般為8位Date4現(xiàn)代密碼學(xué)理論與實踐之五預(yù)備知識 消息、信包、片的相互關(guān)系包消息包據(jù)片頭片尾片 順序號數(shù)片F(xiàn) F F F F F F FDate5現(xiàn)代密碼學(xué)理論與實踐之五 預(yù)備知識 一些術(shù)語 信道帶寬b：每個信道有w位寬和信號傳輸率f = 1/t (t是時鐘周期), b = wf bits/sec 節(jié)點和開關(guān)的度：與節(jié)點和開關(guān)相連的信道數(shù)目 路徑：信包在網(wǎng)絡(luò)中走過的開關(guān)和鏈路(link)序列 路由長度或距離：路由路徑中包括的鏈路(link)數(shù)目 信包傳輸性能參數(shù) 啟動時間ts(startup time)：準(zhǔn)備包頭信息等 節(jié)點延遲時間th(per-hop time)：包頭穿越相鄰節(jié)點的時間 字傳輸時間tw(transfer time)：傳輸每個字的時間 鏈路數(shù)l 、信包大小mDate6現(xiàn)代密碼學(xué)理論與實踐之五 預(yù)備知識 選路算法的三種機制 基于算術(shù)的: 開關(guān)中具有簡單的算術(shù)運算功能，如維序選路； 基于源地址的: 在源點時就將沿路徑的各個開關(guān)的輸出端口地址p0,p1,pn包在信包的頭部，每個開關(guān)只是對信包頭的輸出端口地址進(jìn)行剝離； 基于查表的: 開關(guān)中含有一個選路表，對信包頭中的選路域查出輸出端口地址。

Date7現(xiàn)代密碼學(xué)理論與實踐之五 預(yù)備知識 選路方式 Date8現(xiàn)代密碼學(xué)理論與實踐之五第八章 并行數(shù)值算法 8.0 預(yù)備知識 8.1 選路方法與開關(guān)技術(shù) 8.2 單一信包一到一傳輸 8.3 一到多播送 8.4 多到多播送 Date9現(xiàn)代密碼學(xué)理論與實踐之五8.1 選路方法與開關(guān)技術(shù) 8.1.1 選路方法 8.1.2 開關(guān)技術(shù)Date10現(xiàn)代密碼學(xué)理論與實踐之五 選路方法 分類 最短路徑/非最短路徑(貪心選路/隨機選路)，如維序選路是貪心的，二階段維序選路是隨機的 確定選路/自適應(yīng)選路(尋徑確定/尋徑視網(wǎng)絡(luò)狀況) 維序選路(Dimension-Ordered Routing)： 一種確定的最短路徑選路 二維網(wǎng)孔中的維序選路: X-Y選路 超立方中的維序選路: E-立方選路 Date11現(xiàn)代密碼學(xué)理論與實踐之五 選路方法 X-Y選路算法 算法8.1：二維網(wǎng)孔上的X-Y選路算法 begin step1: 沿X方向?qū)⑿虐椭聊康牡靥幚砥魉诘牧?step2: 沿Y方向?qū)⑿虐椭聊康牡靥幚砥魉诘男?endDate12現(xiàn)代密碼學(xué)理論與實踐之五 選路方法 例8.1 (P186)Date13現(xiàn)代密碼學(xué)理論與實踐之五 選路方法 E-立方選路算法 路由計算： sn-1sn-2s1s0(源地址) 異或 dn-1dn-2d1d0(目的地址) rn-1 rn-2 r1 r0 (路由值) 路由過程： sn-1sn-2s1s0 sn-1sn-2s1s0 r0 sn-1sn-2s1s0 r1 算法8.2 ：超立方網(wǎng)絡(luò)上的E-立方選路算法(P186)Date14現(xiàn)代密碼學(xué)理論與實踐之五 選路方法 例8.2 (P187) 0110(S) 1101(D) 1011(R)Date15現(xiàn)代密碼學(xué)理論與實踐之五8.1 選路方法與開關(guān)技術(shù) 8.1.1 選路方法 8.1.2 開關(guān)技術(shù)Date16現(xiàn)代密碼學(xué)理論與實踐之五 開關(guān)技術(shù) 存儲轉(zhuǎn)發(fā)(Store-and-Forward)選路 消息被分成基本的傳輸單位-信包(Packet), 每個信包都含有尋徑信息； 當(dāng)一個信包到達(dá)中間節(jié)點A時，A把整個信包放入其通信緩沖器中，然后在選路算法的控制下選擇下一個相鄰節(jié)點B，當(dāng)從A到B的通道空閑并且B的通信緩沖器可用時，把信包從A發(fā)向B； 信包的傳輸時間: tcomm (SF) = ts + (mtw + th)l=O(ml) 缺點： 每個結(jié)點必須對整個消息和信包進(jìn)行緩沖，緩沖器較大； 網(wǎng)絡(luò)時延與發(fā)送消息所經(jīng)歷的節(jié)點數(shù)成正比Date17現(xiàn)代密碼學(xué)理論與實踐之五 開關(guān)技術(shù) 切通(Cut Through)選路 在傳遞一個消息之前，就為它建立一條從源結(jié)點到目的結(jié)點的物理通道。

在傳遞的全部過程中，線路的每一段都被占用，當(dāng)消息的尾部經(jīng)過網(wǎng)絡(luò)后，整條物理鏈路才被廢棄 傳輸時間: tcomm (CT) = ts + mtw + lth = O(m+l)缺點： 物理通道非共享 傳輸過程中物理通道一直被占用Date18現(xiàn)代密碼學(xué)理論與實踐之五 開關(guān)技術(shù) 蟲孔(Wormhole)選路 Dally于1986年提出，利用了前二種方法的優(yōu)點，減少了緩沖區(qū)，提高了物理通道的利用 首先把一個消息分成許多很小的片，消息的頭片包含了這個消息的所有尋徑信息尾片是一個其最后包含了消息結(jié)束符的片中間的片均為數(shù)據(jù)片； 片是最小信息單位每個結(jié)點上只需要緩沖一個片就能滿足要求； 用一個頭片直接牽引一條從輸入鏈路到輸出鏈路的路徑的方法來進(jìn)行操作每個消息中的片以流水的方式在網(wǎng)絡(luò)中向前“蠕動”每個片相當(dāng)于Worm的一個節(jié)，“蠕動”以節(jié)為單位順序地向前爬行當(dāng)消息的尾片向前“蠕動”一步后，它剛才所占用的結(jié)點就被放棄了Date19現(xiàn)代密碼學(xué)理論與實踐之五 開關(guān)技術(shù) 蟲孔(Wormhole)選路 優(yōu)點： (1)每個結(jié)點的緩沖器的需求量小，易于用VLSI實現(xiàn)； (2)較低的網(wǎng)絡(luò)傳輸延遲存儲轉(zhuǎn)發(fā)傳輸延遲基本上正比于消息在網(wǎng)絡(luò)中傳輸?shù)木嚯x; Wormhole與線路開關(guān)的網(wǎng)絡(luò)傳輸延遲正比于消息包的長度，傳輸距離對它的影響很?。ㄏ^長時的情況）； (3)通道共享性好、利用率高； (4)易于實現(xiàn)Multicast和Broadcast。

Date20現(xiàn)代密碼學(xué)理論與實踐之五 開關(guān)技術(shù) 幾種開關(guān)技術(shù)的時空圖 Date21現(xiàn)代密碼學(xué)理論與實踐之五第八章 并行數(shù)值算法 8.0 預(yù)備知識 8.1 選路方法與開關(guān)技術(shù) 8.2 單一信包一到一傳輸 8.3 一到多播送 8.4 多到多播送 Date22現(xiàn)代密碼學(xué)理論與實踐之五 單一信包一到一傳輸 距離l的計算： 對于p個處理器 一維環(huán)形： 帶環(huán)繞Mesh( )： 超立方： tcomm(SF)的計算(可由(8.1b)式得到) 一維環(huán)形： 帶環(huán)繞Mesh： 超立方： tcomm(CT)的計算(可由(8.2b)式得到) 如果mp： tcomm(SF) tcomm(CT) = ts+mtwDate23現(xiàn)代密碼學(xué)理論與實踐之五第八章 并行數(shù)值算法 8.0 預(yù)備知識 8.1 選路方法與開關(guān)技術(shù) 8.2 單一信包一到一傳輸 8.3 一到多播送 8.4 多到多播送 Date24現(xiàn)代密碼學(xué)理論與實踐之五8.3 一到多播送 8.3.1 SF模式 8.3.2 CT模式Date25現(xiàn)代密碼學(xué)理論與實踐之五 一到多播送SF模式 環(huán) 步驟： 先左右鄰近傳送;再左右二個方向同時播送 示例： 通訊時間： Date26現(xiàn)代密碼學(xué)理論與實踐之五 一到多播送SF模式 環(huán)繞網(wǎng)孔 步驟：先完成一行中的播送;再同時進(jìn)行各列的播送 示例： 共4步(2步行、2步列) 通訊時間： Date27現(xiàn)代密碼學(xué)理論與實踐之五 一到多播送SF模式 超立方 步驟：從低維到高維，依次進(jìn)行播送; 示例： 通訊時間： Date28現(xiàn)代密碼學(xué)理論與實踐之五8.3 一到多播送 8.3.1 SF模式 8.3.2 CT模式Date29現(xiàn)代密碼學(xué)理論與實踐之五 一到多播送CT模式 環(huán) 步驟： (1)先發(fā)送至p/2遠(yuǎn)的處理器; (2)再同時發(fā)送至p/22遠(yuǎn)的處理器; (i)再同時發(fā)送至p/2i遠(yuǎn)的處理器; 示例：圖8.8 通訊時間： Date30現(xiàn)代密碼學(xué)理論與實踐之五 一到多播送CT模式 網(wǎng)孔 步驟： (1)先進(jìn)行行播送; (2)再同時進(jìn)行列播送; 示例：圖8.9 通訊時間： Date31現(xiàn)代密碼學(xué)理論與實踐之五 一到多播送CT模式 超立方 步驟： 依次從低維到高維播送, d-立方, d=0,1,2,3,4; 通訊時間： Date32現(xiàn)代密碼學(xué)理論與實踐之五第八章 并行數(shù)值算法 8.0 預(yù)備知識 8.1 選路方法與開關(guān)技術(shù) 8.2 單一信包一到一傳輸 8.3 一到多播送 8.4 多到多播送 Date33現(xiàn)代密碼學(xué)理論與實踐之五8.3 一到多播送 8.3.1 SF模式 8.3.2 CT模式Date34現(xiàn)代密碼學(xué)理論與實踐之五 多到多播送SF模式 環(huán) 步驟： 同時向右(或左)播送 剛接收到的信包 示例：圖8.10 通訊時間： 已有數(shù)據(jù)第2步傳送數(shù)據(jù)2Date35現(xiàn)代密碼學(xué)理論與實踐之五 多到多播送SF模式 環(huán)繞網(wǎng)孔 步驟： (1)先進(jìn)行行的播送； (2)再進(jìn)行列的播送； 示例：圖8.11 通訊時間： Date36現(xiàn)代密碼學(xué)理論與實踐之五 多到多播送SF模式 超立方 步驟： 依次按維進(jìn)行 多到多的播送； 示例：圖8.12 通訊時間： Date37現(xiàn)代密碼學(xué)理論與實踐之五8.3 一到多播送 8.3.1 SF模式 8.3.2 CT模式Date38現(xiàn)代密碼學(xué)理論與實踐之五 多到多播送CT模式 使用一到多的策略會造成鏈路競爭 Date39現(xiàn)代密碼學(xué)理論與實踐之五。