【教學(xué)課件】第六章-并行處理技術(shù)

第六章并行處理技術(shù)北京航空航天大學(xué)計(jì)算機(jī)學(xué)院2005年5月2021/8/171第六章并行處理技術(shù)北京航空航天大學(xué)計(jì)算機(jī)學(xué)院2021/什么是并行處理為什么要開(kāi)發(fā)并行處理技術(shù)并行機(jī)的分類及基本結(jié)構(gòu)并行處理的基本問(wèn)題和技術(shù)主要內(nèi)容2021/8/172什么是并行處理主要內(nèi)容2021/8/172多個(gè)處理單元(acollectionofcomputingelements)協(xié)作、通信（cooperate&communicate）快速求解大型問(wèn)題（tosolvelargeproblemsfast）并行體系結(jié)構(gòu)：用通信體系結(jié)構(gòu)(CommunicationArchitecture)對(duì)傳統(tǒng)的體系結(jié)構(gòu)進(jìn)行擴(kuò)展。并行處理的基本問(wèn)題2021/8/173多個(gè)處理單元(acollectionofcomputi處理器之間協(xié)同的基礎(chǔ)是什么？互連與通信編程人員使用何種方式編程？編程模型如何保證并行程序的正確性？存儲(chǔ)一致性并行處理的基本問(wèn)題2021/8/174并行處理的基本問(wèn)題2021/8/1741、互連與通信的問(wèn)題互連網(wǎng)絡(luò)的定義及特性靜態(tài)網(wǎng)絡(luò)動(dòng)態(tài)網(wǎng)絡(luò)多處理器通信問(wèn)題并行處理的基本問(wèn)題2021/8/1751、互連與通信的問(wèn)題并行處理的基本問(wèn)題2021/8/175

并行計(jì)算機(jī)往往采用多個(gè)處理節(jié)點(diǎn)。其根本思想就是將要完成的任務(wù)盡量分布到各個(gè)處理節(jié)點(diǎn)并發(fā)執(zhí)行，在最理想的情況下并行計(jì)算機(jī)的性能是所有節(jié)點(diǎn)計(jì)算性能的簡(jiǎn)單相加。但是由于節(jié)點(diǎn)間存在著通信延時(shí)和各個(gè)節(jié)點(diǎn)間的同步關(guān)系，使得系統(tǒng)的整體性能通常達(dá)不到理想情況。比如在某些MPP上其持續(xù)速度只是峰值速度的3%～10%。同時(shí)，并行計(jì)算也逐步向著松耦合（looselyCoupled）和復(fù)雜化的方向發(fā)展。大量的SMP集群(CLUMPs)的出現(xiàn)，使得并行計(jì)算機(jī)內(nèi)部節(jié)點(diǎn)與節(jié)點(diǎn)間的通信瓶頸愈發(fā)明顯。因此，解決并行計(jì)算機(jī)的通信問(wèn)題也就成為了一個(gè)研究的熱點(diǎn)。互連與通信的問(wèn)題2021/8/176并行計(jì)算機(jī)往往采用多個(gè)處理節(jié)點(diǎn)。其根互連與通信的問(wèn)題互連網(wǎng)絡(luò)的定義及特性定義：由開(kāi)關(guān)元件按一定拓?fù)浣Y(jié)構(gòu)和控制方式構(gòu)成的網(wǎng)絡(luò)，以實(shí)現(xiàn)計(jì)算機(jī)系統(tǒng)內(nèi)部多個(gè)處理機(jī)或多個(gè)功能部件間的相互連接。互連網(wǎng)絡(luò)對(duì)并行處理機(jī)的性能影響很大，是系統(tǒng)構(gòu)成的主要部分?；ミB網(wǎng)絡(luò)有三大要素，即互連拓?fù)洌òㄟB接通路）、開(kāi)關(guān)元件和控制方式。由于這三大要素的工作方式和所處的地位不同，才出現(xiàn)了各種各樣的互聯(lián)網(wǎng)絡(luò)。2021/8/177互連與通信的問(wèn)題互連網(wǎng)絡(luò)的定義及特性2021/8/177操作方式：同步通信（SynchronousCommunication)：收發(fā)雙方必須在時(shí)間上同步。這類似于電話網(wǎng)中需要呼叫方和被呼叫方同步。異步通信(AsynchronousCommunication)：收發(fā)雙方不需要同步。這類似于發(fā)送和接收mail?；ミB與通信的問(wèn)題2021/8/178操作方式：互連與通信的問(wèn)題2021/8/178控制策略：集中控制(Centralizedcontrol)：互連網(wǎng)絡(luò)中的各級(jí)互連開(kāi)關(guān)由一組信號(hào)統(tǒng)一控制。其優(yōu)點(diǎn)是控制簡(jiǎn)單，實(shí)現(xiàn)容易，但網(wǎng)絡(luò)的靈活性相對(duì)較差。分布控制(Distributedcontrol)：互連網(wǎng)絡(luò)中的各級(jí)互連開(kāi)關(guān)由多個(gè)或多組信號(hào)分別控制，各（組）開(kāi)關(guān)可處于不同狀態(tài)。其優(yōu)點(diǎn)是網(wǎng)絡(luò)的靈活性強(qiáng)，但控制相對(duì)復(fù)雜，實(shí)現(xiàn)相對(duì)困難?；ミB與通信的問(wèn)題2021/8/179控制策略：互連與通信的問(wèn)題2021/8/179

電路交換(Circuitswitching)：采用與電話網(wǎng)類似的方式，在數(shù)據(jù)傳輸期間，從發(fā)送節(jié)點(diǎn)到接收節(jié)點(diǎn)的整個(gè)連接通路必須保持。

優(yōu)點(diǎn)：信息的傳輸延遲小，對(duì)一次接續(xù)而言，傳輸時(shí)延固定不變。信息的編碼方案和信息格式由雙方協(xié)調(diào)，不受網(wǎng)絡(luò)限制。缺點(diǎn)：電路資源被通信雙方獨(dú)占，電路利用率低。交換方式：

分組交換(Packetswitching)：采用存儲(chǔ)轉(zhuǎn)發(fā)方式，把數(shù)據(jù)分解成許多比較短的、規(guī)格化的片段，進(jìn)行交換和傳輸。優(yōu)點(diǎn)：為用戶提供了靈活的通信環(huán)境（不同速率、不同代碼、不同通信協(xié)議機(jī)制等）。實(shí)現(xiàn)線路動(dòng)態(tài)統(tǒng)計(jì)復(fù)用，通信線路利用率高，可以在一條物理線路上同時(shí)提供多條信息通路?？煽啃愿?，經(jīng)濟(jì)性好。缺點(diǎn)：由于網(wǎng)絡(luò)附加的傳輸信息較多，對(duì)長(zhǎng)報(bào)文通信的傳輸效率比較低。技術(shù)實(shí)現(xiàn)復(fù)雜。互連與通信的問(wèn)題2021/8/1710電路交換(Circuitswitching)：采用與網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)：

靜態(tài)網(wǎng)絡(luò)(Staticnetwork)靜態(tài)網(wǎng)絡(luò)的特點(diǎn)與指標(biāo)典型的靜態(tài)網(wǎng)絡(luò) 動(dòng)態(tài)網(wǎng)絡(luò)(Dynamicnetwork)互連函數(shù)多級(jí)互聯(lián)網(wǎng)絡(luò)互連與通信的問(wèn)題2021/8/1711網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)：互連與通信的問(wèn)題2021/8/1711A.靜態(tài)網(wǎng)絡(luò)的特點(diǎn)

靜態(tài)網(wǎng)絡(luò)由點(diǎn)—點(diǎn)直接相連而成，這種連結(jié)方式在程序執(zhí)行過(guò)程中不會(huì)改變。

如果用圖來(lái)表示，結(jié)點(diǎn)代表開(kāi)關(guān)，邊代表通信鏈路，則：結(jié)點(diǎn)間的鏈路無(wú)源，不能重構(gòu)；開(kāi)關(guān)元件與處理機(jī)相連；不直接相連結(jié)點(diǎn)間的通信需通過(guò)中間結(jié)點(diǎn)中轉(zhuǎn)。靜態(tài)網(wǎng)絡(luò)的特點(diǎn)與指標(biāo)2021/8/1712A.靜態(tài)網(wǎng)絡(luò)的特點(diǎn)靜態(tài)網(wǎng)絡(luò)的特點(diǎn)與指標(biāo)2021/8/1712B.靜態(tài)網(wǎng)絡(luò)的指標(biāo)結(jié)點(diǎn)度：與結(jié)點(diǎn)相連接的邊（鏈路或通道）數(shù)，表示節(jié)點(diǎn)所需要的I/O端口數(shù)，模塊化要求結(jié)點(diǎn)度保持恒定。根據(jù)通道到結(jié)點(diǎn)的方向，結(jié)點(diǎn)度可以進(jìn)一步表示為：

結(jié)點(diǎn)度=入度+出度 其中入度是進(jìn)入結(jié)點(diǎn)的通道數(shù)，出度是從結(jié)點(diǎn)出來(lái)的通道數(shù)。距離：與兩個(gè)結(jié)點(diǎn)之間相連的最少邊數(shù)。網(wǎng)絡(luò)直徑：網(wǎng)絡(luò)中任意兩個(gè)結(jié)點(diǎn)間距離的最大值。靜態(tài)網(wǎng)絡(luò)的特點(diǎn)與指標(biāo)2021/8/1713B.靜態(tài)網(wǎng)絡(luò)的指標(biāo)靜態(tài)網(wǎng)絡(luò)的特點(diǎn)與指標(biāo)2021/8/1713網(wǎng)絡(luò)規(guī)模：網(wǎng)絡(luò)中結(jié)點(diǎn)數(shù)，表示該網(wǎng)絡(luò)功能連結(jié)部件的多少。等分寬度：某一網(wǎng)絡(luò)被切成相等的兩半時(shí)，沿切口的最小邊數(shù)稱為該網(wǎng)絡(luò)的等分寬度。結(jié)點(diǎn)間的線長(zhǎng)：兩個(gè)結(jié)點(diǎn)間的線的長(zhǎng)度。對(duì)稱性：從任何結(jié)點(diǎn)看，拓?fù)浣Y(jié)構(gòu)都一樣，這種網(wǎng)絡(luò)實(shí)現(xiàn)和編程都很容易。結(jié)點(diǎn)是否同構(gòu)。通道是否有緩沖。靜態(tài)網(wǎng)絡(luò)的特點(diǎn)與指標(biāo)2021/8/1714網(wǎng)絡(luò)規(guī)模：網(wǎng)絡(luò)中結(jié)點(diǎn)數(shù)，表示該網(wǎng)絡(luò)功能連結(jié)部件的多少。靜態(tài)網(wǎng) 1).線性陣列對(duì)N個(gè)結(jié)點(diǎn)的線性陣列，有N-1條鏈路，直徑為N-1（任意兩點(diǎn)之間距離的最大值），度為2，不對(duì)稱，等分寬度為1。N很大時(shí)，通信效率很低。典型的靜態(tài)網(wǎng)絡(luò)2021/8/1715 1).線性陣列對(duì)N個(gè)結(jié)點(diǎn)的線性陣列，有N-1條鏈路，直徑

2).環(huán)對(duì)N個(gè)結(jié)點(diǎn)的環(huán)，考慮相鄰結(jié)點(diǎn)數(shù)據(jù)傳送方向：

單向環(huán)：鏈路數(shù)為N，直徑N-1，度為2，對(duì)稱，等分寬度為2。

雙向環(huán)：鏈路數(shù)為N，直徑N/2，度為2，對(duì)稱，等分寬度為2。比如KSR-1（1990）。典型的靜態(tài)網(wǎng)絡(luò)2021/8/1716 2).環(huán)對(duì)N個(gè)結(jié)點(diǎn)的環(huán)，考慮相鄰結(jié)點(diǎn)數(shù)據(jù)傳送方向：典型的3).帶弦環(huán)對(duì)上圖中12個(gè)結(jié)點(diǎn)的帶弦雙向環(huán)，結(jié)點(diǎn)度為3：鏈路數(shù)為18，直徑4（比如紅色結(jié)點(diǎn)），度為3，不對(duì)稱，等分寬度為2。度為3的帶弦環(huán)度為4的帶弦環(huán)

結(jié)點(diǎn)度為4：鏈路數(shù)為24，直徑3（比如紅色結(jié)點(diǎn)），度為4，對(duì)稱，等分寬度為8。典型的靜態(tài)網(wǎng)絡(luò)2021/8/17173).帶弦環(huán)對(duì)上圖中12個(gè)結(jié)點(diǎn)的帶弦雙向環(huán)，度為3的帶弦環(huán)度4).鏈接（全互聯(lián)）

鏈接是帶弦環(huán)的一種特殊情形。鏈接中的每個(gè)結(jié)點(diǎn)和其他結(jié)點(diǎn)之間都有單一的直接鏈路。如下圖中8個(gè)結(jié)點(diǎn)的鏈接：

有28條鏈路，直徑為1，度為7，對(duì)稱，等分寬度為16。 典型的靜態(tài)網(wǎng)絡(luò)2021/8/17184).鏈接（全互聯(lián)） 有28條鏈路，直徑為1，度為7，對(duì)稱，

5).樹(shù)形

4層的二叉樹(shù)

一棵K層完全二叉樹(shù)應(yīng)有N=2K-1個(gè)結(jié)點(diǎn)，對(duì)大結(jié)點(diǎn)度為3，直徑為2（K-1）（即右邊任意一個(gè)葉子結(jié)點(diǎn)到左邊任意一個(gè)葉子結(jié)點(diǎn)）。不對(duì)稱，等分度為1。 由于結(jié)點(diǎn)度為常數(shù)，所以樹(shù)是一種可擴(kuò)展的系統(tǒng)結(jié)構(gòu)。K=4典型的靜態(tài)網(wǎng)絡(luò)2021/8/1719 5).樹(shù)形 4層的二叉樹(shù) 一棵K層完全二叉樹(shù)應(yīng)有N=

樹(shù)形的擴(kuò)展：

帶環(huán)樹(shù)二叉胖樹(shù)

這兩種結(jié)構(gòu)都可以緩解根結(jié)點(diǎn)的瓶頸問(wèn)題。典型的靜態(tài)網(wǎng)絡(luò)2021/8/1720 樹(shù)形的擴(kuò)展： 帶環(huán)樹(shù)二叉胖樹(shù) 這兩種結(jié)構(gòu)都可以緩

6).星形

星形實(shí)際上是一種二層樹(shù)（如右圖）。有N個(gè)結(jié)點(diǎn)的星形網(wǎng)絡(luò)，有N-1條鏈路，直徑為2，最大結(jié)點(diǎn)度為N-1，非對(duì)稱。 典型的靜態(tài)網(wǎng)絡(luò)2021/8/1721 6).星形 星形實(shí)際上是一種二層樹(shù)（如右圖）。有N

有N個(gè)結(jié)點(diǎn)的rr網(wǎng)（其中 )，有2r(r-1)

=2N-2r條鏈路，直徑為2（r-1)，結(jié)點(diǎn)度為4，非對(duì)稱，等分寬度為r。

7).網(wǎng)

r-1條邊R個(gè)節(jié)點(diǎn)典型的靜態(tài)網(wǎng)絡(luò)2021/8/1722 有N個(gè)結(jié)點(diǎn)的rr網(wǎng)（其中 )，有2r(r-1)=

有N個(gè)結(jié)點(diǎn)的rr網(wǎng)（其中 )，有2N條鏈路，直徑為r-1，結(jié)點(diǎn)度為4。

網(wǎng)的變形：

Illiac網(wǎng)

典型的靜態(tài)網(wǎng)絡(luò)2021/8/1723 有N個(gè)結(jié)點(diǎn)的rr網(wǎng)（其中 )，有2N條鏈路，直徑為r

有N個(gè)結(jié)點(diǎn)的rr網(wǎng)（其中 )，有2N

條鏈路，直徑為2r/2，結(jié)點(diǎn)度為4，對(duì)稱。

網(wǎng)的變形：

環(huán)形網(wǎng)（2D—Torus）

典型的靜態(tài)網(wǎng)絡(luò)2021/8/1724 有N個(gè)結(jié)點(diǎn)的rr網(wǎng)（其中 )，有2N條鏈路，

網(wǎng)的變形：搏動(dòng)式陣列（SystolicArray）

典型的靜態(tài)網(wǎng)絡(luò)2021/8/1725 網(wǎng)的變形：搏動(dòng)式陣列（SystolicArray）

8).超立方體0-立方體1-立方體2-立方體3-立方體4-立方體典型的靜態(tài)網(wǎng)絡(luò)2021/8/1726 8).超立方體0-立方體1-立方體2-立方體3-立方體4

一個(gè)n-立方體由N=2n個(gè)結(jié)點(diǎn)構(gòu)成，它們分布在n維上，每維有兩個(gè)結(jié)點(diǎn)。直徑為n，結(jié)點(diǎn)度為n，對(duì)稱。由于結(jié)點(diǎn)度隨維數(shù)線性增加，所以超立方體不是一種可擴(kuò)展結(jié)構(gòu)。

例子：

Intel的iPSC/1、iPSC/2、nCUBE典型的靜態(tài)網(wǎng)絡(luò)2021/8/1727 一個(gè)n-立方體由N=2n個(gè)結(jié)點(diǎn)構(gòu)成，它們分布在n維上，

9).帶環(huán)立方體

一個(gè)帶環(huán)n-立方體由N=2n個(gè)結(jié)點(diǎn)環(huán)構(gòu)成，每個(gè)結(jié)點(diǎn)環(huán)是一個(gè)有n個(gè)結(jié)點(diǎn)的環(huán)，所以結(jié)點(diǎn)總數(shù)為n2n個(gè)。直徑通常為2n，結(jié)點(diǎn)度為3，對(duì)稱。帶環(huán)3-立方體典型的靜態(tài)網(wǎng)絡(luò)2021/8/1728 9).帶環(huán)立方體 一個(gè)帶環(huán)n-立方體由N=2n個(gè)結(jié)點(diǎn)

特點(diǎn)：

網(wǎng)絡(luò)的開(kāi)關(guān)元件有源，鏈路可通過(guò)設(shè)置這些開(kāi)關(guān)的狀態(tài)來(lái)重構(gòu)。 只有在網(wǎng)絡(luò)邊界上的開(kāi)關(guān)元件才能與處理機(jī)相連。動(dòng)態(tài)網(wǎng)絡(luò)2021/8/1729 特點(diǎn)：動(dòng)態(tài)網(wǎng)絡(luò)2021/8/1729

互連函數(shù)是一級(jí)動(dòng)態(tài)互聯(lián)網(wǎng)絡(luò)的一種抽象描述，是從輸入到輸出的一個(gè)映射。

排列：N個(gè)數(shù)的每一種有確定次序的放置方法叫做一個(gè)N排列。

置換：把一個(gè)N排列變成另一個(gè)N排列的變換叫做N階置換。 在有N個(gè)輸入端和N個(gè)輸出端的網(wǎng)絡(luò)中，輸入端和輸出端的連接關(guān)系可以用置換來(lái)表示（輸入端與輸出端一一對(duì)應(yīng)）。互聯(lián)函數(shù)2021/8/1730互連函數(shù)是一級(jí)動(dòng)態(tài)互聯(lián)網(wǎng)絡(luò)的一種抽象描述，是從輸入到輸出1).恒等函數(shù)其中，Xn-1Xn-2

Xk

X0是PE的地址（通常為二進(jìn)制）。n為3時(shí)的恒等函數(shù)的連接情形如下：000001010011100101110111000001010011100101110111互聯(lián)函數(shù)2021/8/17311).恒等函數(shù)其中，Xn-1Xn-2XkX2).方體函數(shù)（cube0，cube1，…，cuben-1)方體函數(shù)是由n個(gè)互連函數(shù)組成，其中0kn。比如，n為3時(shí)，3-立方體各結(jié)點(diǎn)地址如下：YZX010011110000111001100101互聯(lián)函數(shù)2021/8/17322).方體函數(shù)（cube0，cube1，…，cuben-1000001001000010011011010100101101100110111111110Cube0:01234567YZX010011110000111001100101互聯(lián)函數(shù)2021/8/1733000001001000010011011010100101Cube1:00001000101101000001100110010111011110010111011101234567YZX010011110000111001100101互聯(lián)函數(shù)2021/8/1734Cube1:000010001011010000011001Cube2:01234567000100001101100000010011101110111001010011110111YZX0100111100001110011001012021/8/1735Cube2:0123456700010000110110000000003).洗牌函數(shù)：

均勻洗牌（Shuffle-Exchange)11111101234567001010010100011110100001101011110101201012)(XXXXXXSh=互聯(lián)函數(shù)2021/8.洗牌函數(shù)：均勻洗牌（Shuffle-E子洗牌即最低k位循環(huán)左移一位。000000001010010001011011110111111100100110101101012345671020121)(XXXXXXSh=互聯(lián)函數(shù)2021/8/1737子洗牌即最低k位循環(huán)左移一位。000000001010010超洗牌即最高k-1位循環(huán)左移一位。0210123)(XXXXXXSh=00000000100101010001010001110101110111011111111001234567互聯(lián)函數(shù)2021/8/1738超洗牌即最高k-1位循環(huán)左移一位。0210123)(XXXX000000逆洗牌函數(shù)11111101234567001100010001011101100010101110110011互聯(lián)函數(shù)2021/8/1739000000逆洗牌函數(shù)1111110123456700110000000010010101101111111012345674).蝶式001100100001110011011110互聯(lián)函數(shù)2021/8/17400000000100101011011111110123455).PM2I函數(shù)（加減2i）

共有2n個(gè)互連函數(shù)，對(duì)N個(gè)結(jié)點(diǎn)的網(wǎng)絡(luò)為例1：

N=8（8個(gè)結(jié)點(diǎn)），則n=log28=3，所以：i=0，1，2；j=0，1，…，7。 6個(gè)PM2I函數(shù)如下：互聯(lián)函數(shù)2021/8/17415).PM2I函數(shù)（加減2i）例1：互聯(lián)函數(shù)2021/8/PM2+0: (01234567）01234567PM2-0: (76543210）01234567互聯(lián)函數(shù)2021/8/1742PM2+0: (0123456PM2+1: (0246）（1357）01234567PM2-1: (6420）（7531）01234567互聯(lián)函數(shù)2021/8/1743PM2+1: (0246）（135PM2

2: (04）（15）（26）（37）01234567互聯(lián)函數(shù)2021/8/1744PM22: (04）（15）（26）（3 A.多級(jí)網(wǎng)絡(luò)的三要素

（1）開(kāi)關(guān)單元：a個(gè)輸入a個(gè)輸出的開(kāi)關(guān)單元記做aa的開(kāi)關(guān)單元，其中，a是2的整數(shù)倍。常見(jiàn)的有2

2、44、88等。 根據(jù)開(kāi)關(guān)單元功能的多少，2

2又可以分為兩功能和四功能開(kāi)關(guān)。如下圖所示：多級(jí)互連網(wǎng)絡(luò)2021/8/1745 A.多級(jí)網(wǎng)絡(luò)的三要素多級(jí)互連網(wǎng)絡(luò)2021/8/17450101直送0101交叉0101上播0101下播多級(jí)互連網(wǎng)絡(luò)2021/8/17460101直送0101交叉0101上播0101下播多級(jí)互連網(wǎng)絡(luò)

（2）級(jí)間互連模式（InterStageConnection）： 均勻洗牌、蝶式、多路洗牌（比如四路洗牌即是把牌平均分成4份，然后4堆分別進(jìn)行均勻洗牌）、縱橫開(kāi)關(guān)（CrossSwitch)及立方體連結(jié)等。 （3）控制方式

級(jí)控制：每級(jí)只有一個(gè)控制信號(hào)

單元控制：每個(gè)開(kāi)關(guān)一個(gè)控制信號(hào)

部分級(jí)控制：幾個(gè)開(kāi)關(guān)合用一個(gè)控制信號(hào)多級(jí)互連網(wǎng)絡(luò)2021/8/1747 （2）級(jí)間互連模式（InterStageConnecti

B.Ω網(wǎng)0123456701234567第0級(jí)第1級(jí)第2級(jí)201012)(XXXXXXSh=2021/8/1748 B.Ω網(wǎng)0123456701234567第0級(jí)第1級(jí)第2

Ω網(wǎng)的特點(diǎn)：

開(kāi)關(guān)單元：22四功能開(kāi)關(guān)

ISC：洗牌變換

控制方式：采用單元控制方式。當(dāng)目的地址編碼從高位開(kāi)始的第i位（從0開(kāi)始）為0時(shí)，第i級(jí)的22開(kāi)關(guān)的輸入端與上輸出端連接，否則輸入端與下輸出端連接。 例子：

UIUC的Cedar IBM的RP3 NYU的Ultracomputer多級(jí)互連網(wǎng)絡(luò)2021/8/1749 Ω網(wǎng)的特點(diǎn)：多級(jí)互連網(wǎng)絡(luò)2021/8/17490123456701234567第0級(jí)第1級(jí)第2級(jí)

無(wú)阻塞的實(shí)現(xiàn)置換

π1=（07642）（13）（5）多級(jí)互連網(wǎng)絡(luò)2021/8/17500123456701234567第0級(jí)第1級(jí)第2級(jí) 無(wú)阻塞的0123456701234567第0級(jí)第1級(jí)第2級(jí)

置換π2=（06473）（15）（2）

在開(kāi)關(guān)F、G、H、I和J上發(fā)生阻塞FGHJI多級(jí)互連網(wǎng)絡(luò)2021/8/17510123456701234567第0級(jí)第1級(jí)第2級(jí) 置換π

Ω網(wǎng)的特點(diǎn)(2)：

并不是所有的置換在Ω網(wǎng)中一次通過(guò)便可以實(shí)現(xiàn)。 Ω網(wǎng)是阻塞網(wǎng)絡(luò)：出現(xiàn)沖突時(shí)，可以采用幾次通過(guò)的方法來(lái)解決沖突。多級(jí)互連網(wǎng)絡(luò)2021/8/1752 Ω網(wǎng)的特點(diǎn)(2)：多級(jí)互連網(wǎng)絡(luò)2021/8/17520123456701234567第0級(jí)第1級(jí)第2級(jí)

Ω網(wǎng)的廣播功能：

0018個(gè)輸出端多級(jí)互連網(wǎng)絡(luò)2021/8/17530123456701234567第0級(jí)第1級(jí)第2級(jí) Ω網(wǎng)的廣44開(kāi)關(guān)構(gòu)成的Ω網(wǎng)：多路洗牌

如16輸入4路洗牌：網(wǎng)路級(jí)數(shù)為log416=2

01第1級(jí)234567891011121314150123456789101112131415第0級(jí)級(jí)間變換:Sh(Sh())可以認(rèn)為是由4個(gè)2*2開(kāi)關(guān)組成多級(jí)互連網(wǎng)絡(luò)2021/8/175444開(kāi)關(guān)構(gòu)成的Ω網(wǎng)：多路洗牌01第1級(jí)2345678910

Ω網(wǎng)的特點(diǎn)(3)：

當(dāng)采用kk開(kāi)關(guān)元件時(shí)，則可以定義k路洗牌函數(shù)來(lái)構(gòu)造更大的級(jí)數(shù)為logkn的Ω網(wǎng)絡(luò)。多級(jí)互連網(wǎng)絡(luò)2021/8/1755 Ω網(wǎng)的特點(diǎn)(3)：多級(jí)互連網(wǎng)絡(luò)2021/8/1755

C.蝶式網(wǎng)絡(luò)（Butterflyswitchnetwork）

蝶式網(wǎng)絡(luò)的開(kāi)關(guān)不允許廣播功能，它實(shí)際上是Omega網(wǎng)的一個(gè)子集。 兩級(jí)6464的蝶式網(wǎng)絡(luò)如下圖所示：它采用16個(gè)88交叉開(kāi)關(guān)構(gòu)成，兩級(jí)間采用8路洗牌連接。多級(jí)互連網(wǎng)絡(luò)2021/8/1756 C.蝶式網(wǎng)絡(luò)（Butterflyswitchnetw8888880...7888888第1級(jí)第0級(jí)8...1556...63.........078155663........................兩級(jí)6464的蝶式網(wǎng)絡(luò)多級(jí)互連網(wǎng)絡(luò)2021/87888888第1級(jí)第0級(jí)8.1

總線本質(zhì)上是一組導(dǎo)線和插座，用于處理器、存儲(chǔ)模塊和外圍設(shè)備之間的數(shù)據(jù)傳輸。系統(tǒng)總線用于主設(shè)備如處理器和從設(shè)備如存儲(chǔ)模塊之間傳輸數(shù)據(jù)。總線仲裁邏輯每次只授予一個(gè)請(qǐng)求存儲(chǔ)總線，因此也稱爭(zhēng)用總線。單總線層次總線

總線2021/8/1758總線本質(zhì)上是一組導(dǎo)線和插座，用于處理器、存儲(chǔ)模塊和外圍設(shè)

目前已建立了許多標(biāo)準(zhǔn)總線，例如PCI、VME、Multibus、Sbus、MicroChannel、IEEEFuturebus。大多數(shù)總線在構(gòu)造單處理機(jī)系統(tǒng)時(shí)價(jià)格很低。我們關(guān)心的是多處理機(jī)總線和層次總線，用它們來(lái)構(gòu)造SMP、NUMA和DSM機(jī)器。這些可擴(kuò)展的總線一般用硬件來(lái)支持高速緩存一致性、快速多處理機(jī)同步、以及分離事務(wù)中斷處理等。

總線2021/8/1759 目前已建立了許多標(biāo)準(zhǔn)總線，例如PCI、VME、MMPC高速緩存IF系統(tǒng)總線（在底板或中夾板上）局部總線存儲(chǔ)器存儲(chǔ)器總線CIFIOPIFIFIFIFC緩存器緩存器局部總線局部總線CPU板I/O板網(wǎng)絡(luò)接口卡以太網(wǎng)打印機(jī)磁盤(pán)存儲(chǔ)板總線2021/8/1760MPC高速緩存IF系統(tǒng)總線（在底板或中夾板上）局部總

總線互連的缺陷總線有多個(gè)處理機(jī)分時(shí)共享，因此即使當(dāng)總線帶寬很高，每個(gè)處理器的帶寬也只是總帶寬的一部分。此外總線由于缺乏冗余機(jī)制易于出錯(cuò)，請(qǐng)總線也有有限的可擴(kuò)展性。這些缺陷主要是受封裝技術(shù)和價(jià)格因素的約束。總線一般限制在很小的機(jī)架內(nèi)，當(dāng)層次總線擴(kuò)展到幾個(gè)機(jī)架時(shí)，始終扭轉(zhuǎn)和全局時(shí)問(wèn)題就變得難于克服。使用交叉開(kāi)關(guān)和多級(jí)網(wǎng)絡(luò)代替總線結(jié)構(gòu)將在一定程度上克服這些缺陷。

總線2021/8/1761 總線互連的缺陷總線2021/8/1761基本術(shù)語(yǔ)與性能指標(biāo)通信方式尋徑算法軟件開(kāi)銷多處理器通信問(wèn)題2021/8/1762基本術(shù)語(yǔ)與性能指標(biāo)多處理器通信問(wèn)題2021/8/1762基本通信方式

無(wú)論網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)如何，高性能計(jì)算機(jī)節(jié)點(diǎn)間通信對(duì)于用戶是透明的。其通信模式無(wú)外乎以下4種：?jiǎn)尾?Unicast):一個(gè)源節(jié)點(diǎn)到一個(gè)目的節(jié)點(diǎn)；多播(Multicast):一個(gè)源節(jié)點(diǎn)到多個(gè)目的節(jié)點(diǎn);廣播(Broadcast):一個(gè)源節(jié)點(diǎn)到全體節(jié)點(diǎn)；會(huì)議(Conference):多個(gè)源節(jié)點(diǎn)到一個(gè)目的節(jié)點(diǎn)。多處理器通信問(wèn)題2021/8/1763基本通信方式多處理器通信問(wèn)題2021/8/1763

1).消息、包和片消息（Message）：是在多計(jì)算機(jī)系統(tǒng)的處理接點(diǎn)之間傳遞包含數(shù)據(jù)和同步消息的信息包。它是一種邏輯單位，可由任意數(shù)量的包構(gòu)成。包（Packet）：包的長(zhǎng)度隨協(xié)議不同而不同，它是信息傳送的最小單位，64-512位。片（Flit）：片的長(zhǎng)度固定，一般為8位。

它們的相互關(guān)系如下圖：基本術(shù)語(yǔ)與性能指標(biāo)2021/8/1764 1).消息、包和片基本術(shù)語(yǔ)與性能指標(biāo)2021/8/176包……消息包據(jù)片頭片尾片……順序號(hào)數(shù)片bbbbbbbb基本術(shù)語(yǔ)與性能指標(biāo)2021/8/1765包……消息包據(jù)片頭片尾片……順序號(hào)數(shù)片bbbbbbbb基本術(shù)

2).互連網(wǎng)絡(luò)

互連網(wǎng)絡(luò)用來(lái)在多處理機(jī)(計(jì)算機(jī))系統(tǒng)的處理結(jié)點(diǎn)之間傳遞消息。

互連網(wǎng)絡(luò)性能的兩個(gè)重要指標(biāo)：

傳輸時(shí)延（TransmissionLatency）

吞吐量（Throughput）

互連網(wǎng)絡(luò)的描述：

拓?fù)洌═opology）

尋徑算法（Routing）

流控制（FlowControl）基本術(shù)語(yǔ)與性能指標(biāo)2021/8/1766 2).互連網(wǎng)絡(luò) 互連網(wǎng)絡(luò)性能的兩個(gè)重要指標(biāo)：用戶程序

3).傳輸時(shí)延與吞吐量

一個(gè)消息的傳輸時(shí)延：從它在源結(jié)點(diǎn)進(jìn)行發(fā)送初始化到它在目的結(jié)點(diǎn)完整的被接收所耗費(fèi)的時(shí)間。基本術(shù)語(yǔ)與性能指標(biāo)2021/8/1767用戶程序 3).傳輸時(shí)延與吞吐量基本術(shù)語(yǔ)與性能指標(biāo)2021/

一個(gè)網(wǎng)絡(luò)的傳輸時(shí)延：在一定條件下發(fā)送消息的平均時(shí)延。

網(wǎng)絡(luò)的吞吐量：?jiǎn)挝粫r(shí)間內(nèi)網(wǎng)絡(luò)所能傳輸?shù)南?shù)目或長(zhǎng)度?；拘g(shù)語(yǔ)與性能指標(biāo)2021/8/1768 一個(gè)網(wǎng)絡(luò)的傳輸時(shí)延：在一定條件下發(fā)送消息的平均時(shí) 4).傳輸時(shí)延的公式

其中，Ts稱為建立時(shí)延，Tn稱為網(wǎng)絡(luò)時(shí)延，Tb稱為阻塞時(shí)延。 它們具體定義如下：基本術(shù)語(yǔ)與性能指標(biāo)2021/8/1769 4).傳輸時(shí)延的公式 其中，Ts稱為建立時(shí)延，Tn稱

建立時(shí)延Ts：一個(gè)消息在源結(jié)點(diǎn)和目的結(jié)點(diǎn)上裝配和分解、從存儲(chǔ)器拷貝到通信緩沖區(qū)以及正確性驗(yàn)證等所耗費(fèi)的時(shí)間。它和機(jī)器本身的硬件、軟件技術(shù)有關(guān)。

其中：

Tss稱為源結(jié)點(diǎn)時(shí)延：從發(fā)送進(jìn)程開(kāi)始消息發(fā)送初始化到消息的頭部進(jìn)入網(wǎng)絡(luò)所經(jīng)歷的時(shí)間。

Tsd稱為目的結(jié)點(diǎn)時(shí)延：從消息的尾部到達(dá)目的結(jié)點(diǎn)到消息完全被接收進(jìn)程接收所經(jīng)歷的時(shí)間。基本術(shù)語(yǔ)與性能指標(biāo)2021/8/1770 建立時(shí)延Ts：一個(gè)消息在源結(jié)點(diǎn)和目的結(jié)點(diǎn)上裝配和分TssTsd基本術(shù)語(yǔ)與性能指標(biāo)2021/8/1771TssTsd基本術(shù)語(yǔ)與性能指標(biāo)2021/8/1771

網(wǎng)絡(luò)時(shí)延Tn：消息頭部從源結(jié)點(diǎn)進(jìn)入網(wǎng)絡(luò)到消息的尾部到達(dá)目的結(jié)點(diǎn)的時(shí)間間隔。其中：

TpD稱為結(jié)點(diǎn)時(shí)延：其中Tp是消息在它所經(jīng)過(guò)的路徑上的每個(gè)中間結(jié)點(diǎn)上的平均時(shí)延，D為源結(jié)點(diǎn)與目的結(jié)點(diǎn)之間中間結(jié)點(diǎn)的數(shù)量。中間結(jié)點(diǎn)上的平均時(shí)延中間結(jié)點(diǎn)的數(shù)量L/B稱為線路時(shí)延：其中L為消息長(zhǎng)度，B為結(jié)點(diǎn)之間的通道帶寬?；拘g(shù)語(yǔ)與性能指標(biāo)2021/8/1772 網(wǎng)絡(luò)時(shí)延Tn：消息頭部從源結(jié)點(diǎn)進(jìn)入網(wǎng)絡(luò)到消息的尾部到達(dá)目

阻塞時(shí)延Tb：消息傳遞過(guò)程中其他所有可能的時(shí)延（主要原因是資源沖突）?；拘g(shù)語(yǔ)與性能指標(biāo)2021/8/1773 阻塞時(shí)延Tb：消息傳遞過(guò)程中其他所有可能的時(shí)延（主要原因

5).網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)

第一代并行計(jì)算機(jī)：HyperCubeTMC:CM-2Intel:iPSCnCUBE

第二代并行計(jì)算機(jī)：n—Mesh

Stanford:DashMIT:AlewifeIntel:Paragon基本術(shù)語(yǔ)與性能指標(biāo)2021/8/1774 5).網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)基本術(shù)語(yǔ)與性能指標(biāo)2021/8/177

6).網(wǎng)絡(luò)的尋徑算法

決定發(fā)送一個(gè)消息到其目的地所經(jīng)過(guò)的路徑。 可以分為：

最短路徑算法 非最短路徑算法 或者：

確定性算法：路徑的選擇只依賴于它所發(fā)送的消息的源結(jié)點(diǎn)和目的結(jié)點(diǎn)。

可適應(yīng)算法：消息從結(jié)點(diǎn)A到結(jié)點(diǎn)B可以由幾條不同的路徑。基本術(shù)語(yǔ)與性能指標(biāo)2021/8/1775 6).網(wǎng)絡(luò)的尋徑算法基本術(shù)語(yǔ)與性能指標(biāo)2021/8/177

7).網(wǎng)絡(luò)的流控制

當(dāng)一個(gè)消息在網(wǎng)絡(luò)中沿著某條路徑傳送時(shí)，互連網(wǎng)絡(luò)如何來(lái)為它分配通道和緩沖器。基本術(shù)語(yǔ)與性能指標(biāo)2021/8/1776 7).網(wǎng)絡(luò)的流控制基本術(shù)語(yǔ)與性能指標(biāo)2021/8/1776

1)、同步通信方式

同步通信方式是指發(fā)送節(jié)點(diǎn)和接收節(jié)點(diǎn)在時(shí)間上和空間上都要同步動(dòng)作，任何一個(gè)環(huán)節(jié)發(fā)生問(wèn)題，都會(huì)形成阻塞。所謂時(shí)間上的同步是指發(fā)送節(jié)點(diǎn)和接收節(jié)點(diǎn)必須在做好傳送準(zhǔn)備后，才能開(kāi)始進(jìn)行消息傳遞。所謂空間上的同步是指從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的通信路徑都已開(kāi)通。通信方式2021/8/1777 1)、同步通信方式通信方式2021/8/1777發(fā)方計(jì)算機(jī)收方計(jì)算機(jī)發(fā)送接收

因發(fā)生阻塞而使計(jì)算機(jī)節(jié)點(diǎn)等待的時(shí)間稱為同步時(shí)間。處于等待狀態(tài)的處理機(jī)是空閑的，特別是通信距離長(zhǎng)時(shí)，每經(jīng)過(guò)一個(gè)中繼點(diǎn)，就會(huì)發(fā)生同步，是同步時(shí)間過(guò)長(zhǎng)，并行處理的效率下降。在同步方式下，一般不設(shè)置通信緩沖區(qū)，一次傳送的數(shù)據(jù)量不受緩沖區(qū)大小的限制。通信方式2021/8/1778發(fā)方計(jì)算機(jī)收方計(jì)算機(jī)發(fā)送接收因發(fā)生阻塞而使計(jì)2)、異步通信方式

異步通信方式是指在通信通道上設(shè)置足夠大的緩沖區(qū)，發(fā)方計(jì)算機(jī)將消息寫(xiě)入緩沖區(qū)，在緩沖區(qū)寫(xiě)滿之前，不必等待收方節(jié)點(diǎn)接收消息；而接收方只需在必要的時(shí)候，從緩沖區(qū)中把數(shù)據(jù)讀走。在時(shí)間上，收發(fā)雙方不必同步。在空間上，只要緩沖區(qū)不滿，發(fā)方就可以寫(xiě)；緩沖區(qū)不空，收方就可以讀。異步方式需要足夠大的緩沖區(qū)，增加了硬件開(kāi)銷，但它是非阻塞的通信系統(tǒng)。通信方式2021/8/17792)、異步通信方式通信方式2021/8/1779發(fā)方計(jì)算機(jī)收方計(jì)算機(jī)發(fā)送接收

同步方式下，發(fā)送的數(shù)據(jù)量和接收的數(shù)據(jù)量必須相等；而異步方式下沒(méi)有這種要求，因此，異步方式可以增加并行程序的靈活性。從速度上看，同步方式是收發(fā)雙方同時(shí)工作，數(shù)據(jù)依次傳遞成功，而異步方式下，收發(fā)雙方與緩沖區(qū)之間需要傳遞兩次，因此異步方式所用時(shí)間較長(zhǎng)。通信方式2021/8/1780發(fā)方計(jì)算機(jī)收方計(jì)算機(jī)發(fā)送接收同步方式下，發(fā)送的

在使用總線方式的消息傳遞通路中，可在發(fā)放或受方計(jì)算機(jī)中設(shè)置緩沖區(qū)，并采用向?qū)Ψ桨l(fā)中斷信號(hào)的方式進(jìn)行異步通信。以收方有緩沖區(qū)為例：發(fā)送方向收方發(fā)中斷信號(hào)后，向接收方的緩沖區(qū)發(fā)送數(shù)據(jù)。收到中斷信號(hào)的接收方計(jì)算機(jī)中斷正常運(yùn)行的程序，接收緩沖區(qū)的數(shù)據(jù)，接收完成后，重返被中斷的程序。發(fā)方計(jì)算機(jī)收方計(jì)算機(jī)發(fā)送接收中斷信號(hào)通信方式2021/8/1781 在使用總線方式的消息傳遞通路中，可在發(fā)放或受方計(jì)算

在使用中斷的異步方式中，緩沖區(qū)的管理要占用CPU的時(shí)間，這與在互連線路中設(shè)置緩沖區(qū)的方式相比，效率相對(duì)要低，但比同步方式要高。發(fā)方計(jì)算機(jī)收方計(jì)算機(jī)發(fā)送接收中斷信號(hào)通信方式2021/8/1782 在使用中斷的異步方式中，緩沖區(qū)的管理要占用

介紹四種尋徑方式：

存儲(chǔ)轉(zhuǎn)發(fā)（Store-and-Forward）

虛擬直通（Virtualcutthrough） 線路交換（CircuitSwitching） Wormhole交換（WormholeSwitching)尋徑算法2021/8/1783 介紹四種尋徑方式： 尋徑算法2021/8/1783

1).存儲(chǔ)轉(zhuǎn)發(fā) 當(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。缺點(diǎn)： 每個(gè)結(jié)點(diǎn)必須對(duì)整個(gè)消息進(jìn)行緩沖，緩沖器較大。 網(wǎng)絡(luò)時(shí)延與發(fā)送消息所經(jīng)歷的結(jié)點(diǎn)數(shù)成正比尋徑算法2021/8/1784 1).存儲(chǔ)轉(zhuǎn)發(fā)尋徑算法2021/8/1784

2).虛擬直通

中間結(jié)點(diǎn)沒(méi)有必要等到整個(gè)消息全部被緩沖后再作出路由選擇，只要消息的目的信息域可用后，就可以作出路由選擇。

其中，Lh為消息頭部開(kāi)始到其目的信息域的長(zhǎng)度，顯然有L>>Lh，所以D的影響比較小。 而當(dāng)通向下一結(jié)點(diǎn)的通道忙或結(jié)點(diǎn)的緩沖器非空閑時(shí)，必須把整個(gè)消息緩沖起來(lái)，這時(shí)和存儲(chǔ)轉(zhuǎn)發(fā)一樣。尋徑算法2021/8/1785 2).虛擬直通 其中，Lh為消息頭部開(kāi)始到其目的信息

3).線路開(kāi)關(guān)

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

其中，Lc是為消息建立物理通路所傳遞的控制信息的長(zhǎng)度。當(dāng)L>>Lh時(shí)，D的影響較小。 缺點(diǎn)： 物理通道非共享 傳輸過(guò)程中物理通道一直被占用尋徑算法2021/8/1786 3).線路開(kāi)關(guān) 其中，Lc是為消息建立物理通路所傳遞

4).Wormhole

Dally于1986年提出。 首先把一個(gè)消息分成許多片，消息的頭片包含了這個(gè)消息的所有尋徑信息。尾片是一個(gè)其最后包含了消息結(jié)束符的片。中間的片均為數(shù)據(jù)片。 片是最小信息單位。每個(gè)結(jié)點(diǎn)上只需要緩沖一個(gè)片就能滿足要求。 用一個(gè)頭片直接開(kāi)辟一條從輸入鏈路到輸出鏈路的路徑的方法來(lái)進(jìn)行操作。每個(gè)消息中的片以流水的方式在網(wǎng)絡(luò)中向前“蠕動(dòng)”。每個(gè)片相當(dāng)于Worm的一個(gè)節(jié)，“蠕動(dòng)”以節(jié)為單位順序的向前爬行。尋徑算法2021/8/1787 4).Wormhole尋徑算法2021/8/1787

當(dāng)消息的頭片到達(dá)一個(gè)結(jié)點(diǎn)A的尋徑器后，尋徑器根據(jù)頭片的尋徑信息立即做出路由選擇：

（1）如果所選擇的通道空閑而且所選擇的結(jié)點(diǎn)B的通信緩沖器可用，那么這個(gè)頭片就不必等待，直接通過(guò)結(jié)點(diǎn)A傳向下一個(gè)結(jié)點(diǎn)B；隨后的其它片跟著相應(yīng)的向前“蠕動(dòng)”一步。當(dāng)消息的尾片向前“蠕動(dòng)”一步后，它剛才所占用的結(jié)點(diǎn)就被放棄了。尋徑算法2021/8/1788 當(dāng)消息的頭片到達(dá)一個(gè)結(jié)點(diǎn)A的尋徑器后，尋徑器根據(jù)頭片

（2）如果所選擇的通道非空閑或者所選擇的結(jié)點(diǎn)的通信緩沖器非可用，那么這個(gè)頭片就必須在此結(jié)點(diǎn)的通信緩沖器中等待，直到上述兩者都可用為止；其它片也在原來(lái)的結(jié)點(diǎn)上等待。此時(shí)，被阻塞的消息不從網(wǎng)絡(luò)中移去，片不放棄它所占有的結(jié)點(diǎn)和通道。這是Wormhole技術(shù)和其它流控制技術(shù)都不同的地方。尋徑算法2021/8/1789 （2）如果所選擇的通道非空閑或者所選擇的結(jié)點(diǎn)的通信緩沖器優(yōu)點(diǎn)：

（1）每個(gè)結(jié)點(diǎn)的緩沖器的需求量小，易于用VLSI實(shí)現(xiàn)。

（2）較低的網(wǎng)絡(luò)傳輸延遲。所有的片以流水方式向前傳送，時(shí)間并形性。而在存儲(chǔ)轉(zhuǎn)發(fā)中，消息是整個(gè)的從一個(gè)結(jié)點(diǎn)“跳”向另一個(gè)結(jié)點(diǎn)，通道的使用時(shí)串行的。所以它的傳輸延遲基本上正比于消息在網(wǎng)絡(luò)中傳輸?shù)木嚯x。Wormhole與線路開(kāi)關(guān)的網(wǎng)絡(luò)傳輸延遲正比于消息包的長(zhǎng)度，傳輸距離對(duì)它的影響很小（消息包較長(zhǎng)時(shí)的情況）。尋徑算法2021/8/1790優(yōu)點(diǎn)：尋徑算法2021/8/1790

（3）通道共享性好、利用率高。對(duì)通道的預(yù)約和釋放是結(jié)合在一起的一個(gè)完整的過(guò)程：占有一段新的通道后將立即放棄用過(guò)的一段舊通道。

（4）易于實(shí)現(xiàn)Multicast和Broadcast。允許尋徑器復(fù)制消息包的片并把它們從多個(gè)輸出通道輸出。

Wormhole方式中，同一個(gè)包中所有的片象不可分離的同伴一樣以流水方式順序的傳送。包可看作是一列火車，由火車頭（頭片）和被牽引的車廂（數(shù)據(jù)片）組成。尋徑算法2021/8/1791 （3）通道共享性好、利用率高。對(duì)通道的預(yù)約和釋放是結(jié)合在BABABABABA55交叉開(kāi)關(guān)節(jié)點(diǎn)機(jī)尋徑算法2021/8/1792BABABABABA55節(jié)點(diǎn)機(jī)尋徑算法2021/8/179S時(shí)間I1I2D

L/B

D

存儲(chǔ)轉(zhuǎn)發(fā)（Store-and-forward）尋徑技術(shù)的時(shí)空?qǐng)D尋徑算法2021/8/1793S時(shí)間I1I2DL/B存儲(chǔ)轉(zhuǎn)發(fā)（Store-aS時(shí)間I1I2D電路開(kāi)關(guān)尋徑技術(shù)的時(shí)空?qǐng)D尋徑算法2021/8/1794S時(shí)間I1I2D電路開(kāi)關(guān)尋徑技術(shù)的時(shí)空?qǐng)D尋徑算法2021/8S時(shí)間I1I2D

L/B

D

Wormhole尋徑技術(shù)的時(shí)空?qǐng)D包頭數(shù)據(jù)尋徑算法2021/8/1795S時(shí)間I1I2DL/BTssTsd軟件開(kāi)銷2021/8/1796TssTsd軟件開(kāi)銷2021/8/1796傳統(tǒng)互連接口性能的主要瓶頸：同一數(shù)據(jù)反復(fù)拷貝，極大增加消息發(fā)送的時(shí)間。許多研究都表明，數(shù)據(jù)拷貝占整個(gè)發(fā)送、接收時(shí)間的65％。TCP/IP等上層復(fù)雜協(xié)議管理機(jī)制，不但增加了消息收發(fā)的開(kāi)銷，而且占用了大量的CPU資源和存儲(chǔ)資源。研究表明，在連接以太網(wǎng)的主機(jī)上，35％的通信時(shí)間都消耗在TCP/IP的協(xié)議處理開(kāi)銷和操作系統(tǒng)的開(kāi)銷之上。由于協(xié)議處于操作系統(tǒng)核內(nèi)，因此用戶程序在發(fā)送和接收消息時(shí)，操作系統(tǒng)在用戶態(tài)與核心態(tài)之間進(jìn)行切換頻繁，增加了開(kāi)銷。軟件開(kāi)銷2021/8/1797傳統(tǒng)互連接口性能的主要瓶頸：軟件開(kāi)銷2021/8/1797提高互連接口性能的手段:(1)

減少數(shù)據(jù)拷貝次數(shù)，實(shí)現(xiàn)一次數(shù)據(jù)拷貝，即用戶發(fā)送數(shù)據(jù)直接由用戶空間拷貝到接口硬件的緩沖區(qū)中，接收的數(shù)據(jù)直接由接口硬件緩沖區(qū)拷貝到用戶接收緩沖區(qū)中。(2)

簡(jiǎn)化TCP/IP協(xié)議，降低處理開(kāi)銷。復(fù)雜的TCP/IP所具有的許多功能是不必要的，必須以精簡(jiǎn)的消息層、網(wǎng)絡(luò)層替代。(3)

增強(qiáng)接口硬件的協(xié)議處理功能。將上層協(xié)議功能由接口板上的快速處理器或?qū)Ｓ锰幚硇酒瑏?lái)承擔(dān)，降低CPU在網(wǎng)絡(luò)通信處理上的開(kāi)銷。軟件開(kāi)銷2021/8/1798提高互連接口性能的手段:軟件開(kāi)銷2021/8/1798小結(jié)

減小通信時(shí)延是提高高性能計(jì)算機(jī)性能的一項(xiàng)非常關(guān)鍵的技術(shù)，其手段大體上有硬件和軟件兩種。

硬件上：對(duì)于通信網(wǎng)絡(luò)可以通過(guò)改進(jìn)拓?fù)浣Y(jié)構(gòu)、提高通信速度的手段實(shí)現(xiàn)；對(duì)于節(jié)點(diǎn)可以使用高速緩存、超線程技術(shù)等。

軟件上：可以通過(guò)精簡(jiǎn)和優(yōu)化協(xié)議改善通信過(guò)程的軟件開(kāi)銷；同時(shí)在更高的層次上，可以通過(guò)改善任務(wù)劃分和處理器的分配，以及適量的任務(wù)復(fù)制（即在不同節(jié)點(diǎn)上執(zhí)行相同的任務(wù)）達(dá)到通信時(shí)延隱藏的效果?；ミB與通信的問(wèn)題2021/8/1799小結(jié)互連與通信的問(wèn)題2021/8/17992、編程模型問(wèn)題如果能對(duì)計(jì)算機(jī)的系統(tǒng)結(jié)構(gòu)進(jìn)行高度的抽象，給出一個(gè)簡(jiǎn)潔的概念模型，那么，程序員在編寫(xiě)程序時(shí)，就不需要了解硬件結(jié)構(gòu)的具體細(xì)節(jié)。這種抽象模型就是我們所說(shuō)的編程模型。并行處理的基本問(wèn)題2021/8/171002、編程模型問(wèn)題并行處理的基本問(wèn)題2021/8/17100

從用戶角度看，一個(gè)理想的抽象模型應(yīng)與一臺(tái)工作站或PC給用戶的映象接近，因而可以使用我們最熟悉的傳統(tǒng)的編程方式：編程模型問(wèn)題RAMFileSystemCPU2021/8/17101從用戶角度看，一個(gè)理想的抽象模型應(yīng)與一臺(tái)工作站或PC就并行計(jì)算機(jī)而言，除了計(jì)算單元以外，通信體系結(jié)構(gòu)也是非常重要的一個(gè)方面。在為并行計(jì)算機(jī)編寫(xiě)程序時(shí)，就不得不考慮到不同節(jié)點(diǎn)上不同進(jìn)程之間的通信問(wèn)題，而這是一項(xiàng)非常復(fù)雜的工作。因此，在并行編程模型中，就必須對(duì)節(jié)點(diǎn)之間的通信、同步、協(xié)作等各種問(wèn)題給出很好的定義。共享地址空間、消息傳遞以及數(shù)據(jù)并行是最常見(jiàn)的三種并行編程模型。編程模型問(wèn)題2021/8/17102就并行計(jì)算機(jī)而言，除了計(jì)算單元以外，共享存儲(chǔ)：具有統(tǒng)一的地址空間。編程模型問(wèn)題分布式存儲(chǔ)：每個(gè)處理器的地址空間單獨(dú)編址?！按髲d式”“包間式”2021/8/17103共享存儲(chǔ)：具有統(tǒng)一的地址空間。編程模型問(wèn)題分布式存儲(chǔ)：每個(gè)處

例：假設(shè)有兩臺(tái)4節(jié)點(diǎn)的的多機(jī)系統(tǒng)，一臺(tái)為共享存儲(chǔ)，另一臺(tái)為分布式存儲(chǔ)，計(jì)算矩陣乘A

B=C。編程模型問(wèn)題P0P1P3P2SharedMemP0P1P3P2LMLMLMLMLM2021/8/17104例：假設(shè)有兩臺(tái)4節(jié)點(diǎn)的的多機(jī)系統(tǒng)，一臺(tái)為共享存儲(chǔ)，另一臺(tái)1）、共享存儲(chǔ)

將矩陣A按行邏輯的均勻分為4塊，矩陣B按列邏輯的均勻分為4塊，均存放在共享存儲(chǔ)器中。編程模型問(wèn)題A=(A0，A1，A2，A3)TB=(B0，B1，B2，B3)A0A1A2A3B0B1B2B3

C00C01C02C03C10C11C12C13C20C21C22C23C30C31C32C33=2021/8/171051）、共享存儲(chǔ)編程模型問(wèn)題A=(A0，A1，A2，A3)節(jié)點(diǎn)機(jī)Pi上程序執(zhí)行步驟：K=i，j=0；各節(jié)點(diǎn)計(jì)算Ai

Bk；K=K+1mod4；j++；如果j<4,goto2；編程模型問(wèn)題2021/8/17106節(jié)點(diǎn)機(jī)Pi上程序執(zhí)行步驟：編程模型問(wèn)題2021/8/17編程模型問(wèn)題A0A1A2A3B0B1B2B3SharedMemoryP0P1P2P3C00C01C02C03C10C11C12C13C20C21C22C23C30C31C32C33矩陣C2021/8/17107編程模型問(wèn)題A0A1A2A3B0B1B2B3SharedM2）、分布式存儲(chǔ)

矩陣A按行物理的均勻分布在4個(gè)計(jì)算結(jié)點(diǎn)上，而矩陣B則按列物理的分布在4個(gè)計(jì)算結(jié)點(diǎn)上。編程模型問(wèn)題A=(A0，A1，A2，A3)TB=(B0，B1，B2，B3)A0A1A2A3B0B1B2B3

C00C01C02C03C10C11C12C13C20C21C22C23C30C31C32C33=2021/8/171082）、分布式存儲(chǔ)編程模型問(wèn)題A=(A0，A1，A2，A3節(jié)點(diǎn)機(jī)Pi上程序執(zhí)行步驟：K=i，J＝0；各節(jié)點(diǎn)計(jì)算Ai

Bk；Send(P4+i-1mod4，Bk)；Rev(Pi+1mod4，Bk+1mod4)；K=K+1mod4J++；如果J<4,goto2；編程模型問(wèn)題2021/8/17109節(jié)點(diǎn)機(jī)Pi上程序執(zhí)行步驟：編程模型問(wèn)題2021/8/17編程模型問(wèn)題P0P1P3P2A0A1A2A3B0B1B2B3數(shù)據(jù)分配2021/8/17110編程模型問(wèn)題P0P1P3P2A0A1A2A3B0B1B2B3編程模型問(wèn)題P0P1P3P2A0A1A2A3B0B1B2B3C00C11C22C33計(jì)算2021/8/17111編程模型問(wèn)題P0P1P3P2A0A1A2A3B0B1B2B3編程模型問(wèn)題P0P1P3P2A0A1A2A3B0B1B2B3C00C11C22C33數(shù)據(jù)交換2021/8/17112編程模型問(wèn)題P0P1P3P2A0A1A2A3B0B1B2B3編程模型問(wèn)題P0P1P3P2A0A1A2A3B1B2B3B0C00C11C22C33計(jì)算C01C12C23C302021/8/17113編程模型問(wèn)題P0P1P3P2A0A1A2A3B1B2B3B0編程模型問(wèn)題P0P1P3P2A0A1A2A3B1B2B3B0數(shù)據(jù)交換C00C01C11C12C33C30C22C232021/8/17114編程模型問(wèn)題P0P1P3P2A0A1A2A3B1B2B3B0編程模型問(wèn)題P0P1P3P2A0A1A2A3B2B3B0B1C00C11C22C33計(jì)算C01C12C23C30C02C13C31C202021/8/17115編程模型問(wèn)題P0P1P3P2A0A1A2A3B2B3B0B1編程模型問(wèn)題P0P1P3P2A0A1A2A3B2B3B0B1數(shù)據(jù)交換C00C01C02C11C12C13C33C30C31