并行計(jì)算機(jī)體系結(jié)構(gòu)

#第2章并行計(jì)算機(jī)體系結(jié)構(gòu)內(nèi)容提要：2.1并行機(jī)網(wǎng)絡(luò)互聯(lián)拓?fù)浣Y(jié)構(gòu)2.2并行機(jī)訪存模型與多級(jí)存儲(chǔ)結(jié)構(gòu)2.3并行機(jī)分類2.4并行機(jī)舉例2.5并行計(jì)算機(jī)的發(fā)展史2.1并行機(jī)網(wǎng)絡(luò)互聯(lián)拓?fù)浣Y(jié)構(gòu)參考資料：文獻(xiàn)1：第1.2節(jié)；文獻(xiàn)2：詳細(xì)闡述；當(dāng)代并行機(jī)拓?fù)浣Y(jié)構(gòu)：?并行機(jī)體系結(jié)構(gòu)的幾個(gè)要素：結(jié)點(diǎn)：包含一個(gè)或多個(gè)CPU，這些CPU通過(guò)HUB或全互聯(lián)交叉開(kāi)關(guān)相互聯(lián)接，并共享內(nèi)存，也可以直接與外部進(jìn)行I/O操作；路由器：聯(lián)接計(jì)算結(jié)點(diǎn)與互聯(lián)網(wǎng)絡(luò)，負(fù)責(zé)數(shù)據(jù)在結(jié)點(diǎn)間的路由尋址；互聯(lián)網(wǎng)絡(luò)：將所有路由器以某種拓?fù)浣Y(jié)構(gòu)相互聯(lián)接，保證它們之間可以自由地通信。?互聯(lián)網(wǎng)絡(luò)：拓?fù)浣Y(jié)構(gòu)：將并行機(jī)各結(jié)點(diǎn)之間物理上相互聯(lián)接的關(guān)系用圖來(lái)表示，其中圖中結(jié)點(diǎn)代表并行機(jī)的結(jié)點(diǎn)，圖中連線代表它所聯(lián)接的兩個(gè)結(jié)點(diǎn)的路由器之間存在物理上的直接聯(lián)接關(guān)系，我們稱該圖為并行機(jī)互聯(lián)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)；拓?fù)浣Y(jié)構(gòu)的幾個(gè)重要定義：并行機(jī)規(guī)模：并行機(jī)包含的結(jié)點(diǎn)總數(shù)，或者包含的CPU總數(shù)；結(jié)點(diǎn)度：互聯(lián)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中聯(lián)入或聯(lián)出的一個(gè)結(jié)點(diǎn)的邊的條數(shù)，稱為該結(jié)點(diǎn)的度；結(jié)點(diǎn)距離：兩個(gè)結(jié)點(diǎn)之間跨越的圖的邊的條數(shù)；網(wǎng)絡(luò)直徑：網(wǎng)絡(luò)中任意兩個(gè)結(jié)點(diǎn)之間的最長(zhǎng)距離；點(diǎn)對(duì)點(diǎn)帶寬：圖中邊對(duì)應(yīng)的物理聯(lián)接的物理帶寬；點(diǎn)對(duì)點(diǎn)延遲：圖中任意兩個(gè)結(jié)點(diǎn)之間的一次零長(zhǎng)度消息傳遞必須花費(fèi)的時(shí)間。延遲與結(jié)點(diǎn)間距離相關(guān)，其中所有結(jié)點(diǎn)之間的最小延遲稱為網(wǎng)絡(luò)的最小延遲，所有結(jié)點(diǎn)之間的最大延遲稱為網(wǎng)絡(luò)的最大延遲；折半寬度：對(duì)分網(wǎng)絡(luò)成兩個(gè)部分（它們的結(jié)點(diǎn)個(gè)數(shù)至多相差1）所必須去掉的邊的網(wǎng)絡(luò)帶寬的總和；總通信帶寬：所有邊的帶寬之和；互聯(lián)網(wǎng)絡(luò)評(píng)價(jià)：大：結(jié)點(diǎn)度、點(diǎn)對(duì)點(diǎn)帶寬、折半寬度、總通信帶寬；小:網(wǎng)絡(luò)直徑、點(diǎn)對(duì)點(diǎn)延遲；互聯(lián)網(wǎng)絡(luò)的分類：靜態(tài)拓?fù)浣Y(jié)構(gòu)、動(dòng)態(tài)拓?fù)浣Y(jié)構(gòu)、寬帶互聯(lián)網(wǎng)絡(luò)；靜態(tài)拓?fù)浣Y(jié)構(gòu)：結(jié)點(diǎn)之間存在固定的物理聯(lián)接方式，程序執(zhí)行過(guò)程中，結(jié)點(diǎn)間的點(diǎn)對(duì)點(diǎn)聯(lián)接關(guān)系不變，例如：［文獻(xiàn)1：P10-P11，給出各類定義的具體值，文獻(xiàn)2詳細(xì)討論］；一維陣列（Array）、環(huán)（Ring）；多維網(wǎng)格（Mesh）、多維環(huán)（Torus）；樹(shù)（Tree）：二叉樹(shù)、X-樹(shù)、星樹(shù)、胖樹(shù)；超立方體（Hypercube）;動(dòng)態(tài)拓?fù)浣Y(jié)構(gòu)：結(jié)點(diǎn)之間無(wú)固定的物理聯(lián)接關(guān)系，而是在聯(lián)接路徑的交叉點(diǎn)處用電子開(kāi)關(guān)、路由器或仲裁器等提供動(dòng)態(tài)聯(lián)接的特性，主要包含單一總線、多層總線、交叉開(kāi)關(guān)、多級(jí)互聯(lián)網(wǎng)絡(luò)：A單一總線：聯(lián)接處理器、存儲(chǔ)模塊和I/O設(shè)備等的一組導(dǎo)線和插座，在主設(shè)備（處理器）和從設(shè)備（存儲(chǔ)器）之間傳遞數(shù)據(jù)，特征有：公用總線以分時(shí)工作為基礎(chǔ)，各處理器模塊分時(shí)共享總線帶寬，即在同一個(gè)時(shí)種周期，至多只有一個(gè)設(shè)備能占有總線；總線帶寬=總線主頻X總線寬度，例如ASUS主板的總線頻率=150MHz,總線寬度為64位，則該總線的帶寬=1.2GB/s；監(jiān)聽(tīng)協(xié)議與仲裁算法：選擇哪個(gè)設(shè)備占有總線；例如：微機(jī)主板外部數(shù)據(jù)總線、PCI總線、ASCIWhite每個(gè)結(jié)點(diǎn)包含16個(gè)CPU，CPU之間通過(guò)總線共享局部存儲(chǔ)器；多層總線：各設(shè)備內(nèi)部存在本地總線（結(jié)點(diǎn)、存儲(chǔ)器、I/O設(shè)備），本地總線之間以系統(tǒng)總線相互聯(lián)接，系統(tǒng)總線一般在通信主板中實(shí)現(xiàn)，例如文獻(xiàn)1P14圖1.9。交叉開(kāi)關(guān)（CrossbarSwitcher）：所有結(jié)點(diǎn)通過(guò)交叉開(kāi)關(guān)陣列相互連接，每個(gè)交叉開(kāi)關(guān)均為其中兩個(gè)結(jié)點(diǎn)之間提供一條專用聯(lián)接通路，同時(shí)，任意兩個(gè)結(jié)點(diǎn)之間也能找到一個(gè)交叉開(kāi)關(guān)，在它們之間建立專用聯(lián)接通路。交叉開(kāi)關(guān)的狀態(tài)可根據(jù)程序的要求動(dòng)態(tài)地設(shè)置為“開(kāi)”和“關(guān)”。例如4X4交叉開(kāi)關(guān)聯(lián)接8個(gè)結(jié)點(diǎn)（黑板上畫圖說(shuō)明）。交叉開(kāi)關(guān)特征：結(jié)點(diǎn)之間聯(lián)接：交叉開(kāi)關(guān)一般構(gòu)成NxN陣列，但在每一行和每一列同時(shí)只能有一個(gè)交叉點(diǎn)開(kāi)關(guān)處于“開(kāi)”狀態(tài)，從而它同時(shí)只能接通N對(duì)結(jié)點(diǎn)；結(jié)點(diǎn)與存儲(chǔ)器之間的聯(lián)接：每個(gè)存儲(chǔ)器模塊同時(shí)只允許一個(gè)結(jié)點(diǎn)訪問(wèn)，故每一列只能接通一個(gè)交叉點(diǎn)開(kāi)關(guān)，但是為了支持并行存儲(chǔ)訪問(wèn)，每一行同時(shí)可以接通多個(gè)交叉點(diǎn)開(kāi)關(guān)。交叉開(kāi)關(guān)的成本為N2,N為端口數(shù)，限制了它在大規(guī)模并行機(jī)中的應(yīng)用，一般適合8-16個(gè)處理器的情形.多級(jí)互聯(lián)網(wǎng)絡(luò)（MIN：MultistageInterconnectionNetwork）：由多個(gè)單級(jí)交叉開(kāi)關(guān)級(jí)聯(lián)接起來(lái)形成大型交叉開(kāi)關(guān)網(wǎng)絡(luò)，相鄰交叉開(kāi)關(guān)級(jí)之間存在固定的物理聯(lián)接拓?fù)?。為了在輸入與輸出之間建立聯(lián)接，可以動(dòng)態(tài)地設(shè)置開(kāi)關(guān)狀態(tài)。例如：一般聯(lián)接圖：文獻(xiàn)1圖1.11，其中ISC為該級(jí)互聯(lián)網(wǎng)絡(luò)，主要有混洗、蝶網(wǎng)、縱橫交叉等；（詳細(xì)參考文獻(xiàn)2）蝶網(wǎng)、CCC網(wǎng)、Benes網(wǎng)：均為超立方體網(wǎng)絡(luò)的推廣，參考文獻(xiàn)2的P215-P225。0網(wǎng)：等價(jià)于蝶網(wǎng)，參考文獻(xiàn)1的P16圖1.12。寬帶互聯(lián)網(wǎng)絡(luò)：快速以太網(wǎng)（10Mbps（82年）、100Mbps（94年）、1Gbps（97年））：IEEE802.3國(guó)際標(biāo)準(zhǔn)，三代網(wǎng)絡(luò)性能比較參考文獻(xiàn)1的P18表1.6,特征類似于單一總線：分時(shí)共享、競(jìng)爭(zhēng)仲裁：帶寬100Mbps，8臺(tái)處理機(jī)共享，每臺(tái)處理機(jī)的平均帶寬為12.5Mbps。FDDI:光纖分布式數(shù)據(jù)接口（FiberDistributedDataInterface）采用雙向光纖令牌環(huán)，所有結(jié)點(diǎn)聯(lián)接在該環(huán)中，提供100-200Mbps數(shù)據(jù)傳輸速度，雙向環(huán)提供冗余通路以提供可靠性，距離可達(dá)100米、2公里、60公里等，比快速以太網(wǎng)具有更好的可靠性、適應(yīng)性；Switcher:交叉開(kāi)關(guān)，可同時(shí)為N/2對(duì)端口提供100Mbps的直接聯(lián)接通路，其中N為端口總數(shù)。多個(gè)Switcher堆疊（不多于7個(gè)）可形成多級(jí)Switcher0Beowulf微機(jī)機(jī)群采用這種結(jié)構(gòu)互聯(lián)所有結(jié)點(diǎn)。（參考張林波講義之圖）。ATM：異步傳輸模式（ATM：AsynchronousTransferMode）是在光纖通信基礎(chǔ)上建立起來(lái)的一種新的寬帶綜合業(yè)務(wù)數(shù)字網(wǎng)的交換技術(shù)。介質(zhì)無(wú)關(guān)的信息傳輸協(xié)議，采用53字節(jié)的定長(zhǎng)短數(shù)據(jù)單元（cell）進(jìn)行傳輸。大的數(shù)據(jù)包進(jìn)入ATM網(wǎng)絡(luò)時(shí)，分解成多個(gè)定長(zhǎng)的單元，各個(gè)單元獨(dú)立傳輸，到達(dá)目的地址后,這些單元匯集成原來(lái)的數(shù)據(jù)包。ATM網(wǎng)絡(luò)適合高速度傳輸聲音、圖像、視頻和數(shù)據(jù)等的所有形式的媒體。Myrinet：專用機(jī)群互聯(lián)網(wǎng)絡(luò)，帶寬可達(dá)200MB/秒，延遲小于10us。Infiniband：專用機(jī)群互聯(lián)網(wǎng)絡(luò)，帶寬可達(dá)1.25GB/秒，延遲小于6us。Qudrics:專用機(jī)群互聯(lián)網(wǎng)絡(luò)，帶寬可達(dá)400MB/秒，延遲小于6us。HiPPI:高性能并行接口（HighPerformanceParallelInterface），1993年標(biāo)準(zhǔn)（ANSIX3T9.3）形成。單工點(diǎn)對(duì)點(diǎn)的數(shù)據(jù)傳輸界面，帶寬可達(dá)800Mb/s-1.6Gb/s。互聯(lián)網(wǎng)絡(luò)的路由選擇算法：定義：數(shù)據(jù)包（Packet:結(jié)點(diǎn)間數(shù)據(jù)在網(wǎng)絡(luò)中傳輸?shù)淖钚挝?，一般為幾十個(gè)、或者幾百個(gè)字節(jié)。路由選擇算法：網(wǎng)絡(luò)中數(shù)據(jù)包傳輸?shù)穆窂竭x擇。申請(qǐng)隊(duì)列長(zhǎng)度：在某條邊上等待傳輸?shù)臄?shù)據(jù)包的個(gè)數(shù)。常用路由選擇算法：貪心法：每個(gè)數(shù)據(jù)包沿最短路徑傳輸（二維陣列舉例），該方法容易在某一條邊上形成通信阻塞。動(dòng)態(tài)路由選擇算法:數(shù)據(jù)包根據(jù)當(dāng)前邊的申請(qǐng)隊(duì)列長(zhǎng)度，動(dòng)態(tài)地改變傳輸路徑。蟲(chóng)孔算法（Wormhole:數(shù)據(jù)包分解為長(zhǎng)度更小的字節(jié)流，所有字節(jié)流在網(wǎng)絡(luò)中按動(dòng)態(tài)路由選擇算法在網(wǎng)絡(luò)中傳輸，最后在目的地址合并還原成數(shù)據(jù)包。作業(yè)：作業(yè)2.1：假設(shè)網(wǎng)絡(luò)包含P=2n=M3個(gè)結(jié)點(diǎn)，請(qǐng)給出一維陣列（環(huán)）、二維網(wǎng)格（Torus）、三維網(wǎng)格（Torus）、超立方體、二叉樹(shù)（葉結(jié)點(diǎn)個(gè)數(shù)為P）、蝶網(wǎng)、Benes網(wǎng)的結(jié)點(diǎn)度、點(diǎn)對(duì)點(diǎn)延遲（以跨越的邊的條數(shù)為單位）、折半寬度（以邊的條數(shù)為單位）、網(wǎng)絡(luò)直徑。作業(yè)2.2：假設(shè)存在8個(gè)結(jié)點(diǎn)，分別聯(lián)接在1Gbps的快速以太網(wǎng)和100Mbps的24端口的Switcher上，請(qǐng)問(wèn)任意兩個(gè)結(jié)點(diǎn)間的平均帶寬為多少，如果結(jié)點(diǎn)數(shù)增加一倍，則平均帶寬又為多少。2.2并行機(jī)存儲(chǔ)結(jié)構(gòu)參考資料：文獻(xiàn)1：第1.3節(jié);文獻(xiàn)8、文獻(xiàn)10；并行機(jī)存儲(chǔ)模塊■內(nèi)存模塊與結(jié)點(diǎn)分離結(jié)點(diǎn)0結(jié)點(diǎn)P圖2.2.1■內(nèi)存模塊局部于結(jié)點(diǎn)內(nèi)部結(jié)點(diǎn)0結(jié)點(diǎn)P圖2.2.2并行機(jī)訪存模型均勻訪存模型（UMA：UniformMemoryAccess:內(nèi)存模塊與結(jié)點(diǎn)分離，分別位于互聯(lián)網(wǎng)絡(luò)的兩側(cè)（圖2.2.1），互聯(lián)網(wǎng)絡(luò)一般采用系統(tǒng)總線、交叉開(kāi)關(guān)和多級(jí)網(wǎng)絡(luò)，稱之為緊耦合系統(tǒng)（TightlyCoupledSystem）。具有如下特征：?物理存儲(chǔ)器被所有結(jié)點(diǎn)均勻共享；所有結(jié)點(diǎn)訪問(wèn)任意存儲(chǔ)單元的時(shí)間相同；訪存競(jìng)爭(zhēng)時(shí)，仲裁策略對(duì)每個(gè)結(jié)點(diǎn)均是機(jī)會(huì)等價(jià)的；各結(jié)點(diǎn)的CPU可帶有局部私有高速緩存（Cache）；外圍I/O設(shè)備也可以共享，且對(duì)各結(jié)點(diǎn)等價(jià)。非均勻訪存模型（NUMA：NonuniformMemoryAccess:內(nèi)存模塊局部在各個(gè)結(jié)點(diǎn)內(nèi)部（圖2.2.2），所有局部?jī)?nèi)存模塊構(gòu)成并行機(jī)的全局內(nèi)存模塊。具有如下特征：任意結(jié)點(diǎn)可以直接訪問(wèn)任意內(nèi)存模塊；結(jié)點(diǎn)訪問(wèn)內(nèi)存模塊的時(shí)間不一致：訪問(wèn)本地存儲(chǔ)模塊的速度一般是訪問(wèn)其他結(jié)點(diǎn)內(nèi)存模塊的3倍以上；訪存競(jìng)爭(zhēng)時(shí)，仲裁策略對(duì)結(jié)點(diǎn)可能是不等價(jià)的；各結(jié)點(diǎn)的CPU可帶有局部私有高速緩存（Cache）；外圍I/O設(shè)備也可以共享。Cache一致性非均勻訪存模型（CC-NUMA：Coherent-CacheNonuniformMemoryAccess：存在專用硬件設(shè)備保證在任意時(shí)刻，各結(jié)點(diǎn)Cache中數(shù)據(jù)與全局內(nèi)存數(shù)據(jù)的一致性，具有特征：各CPU的局部Cache數(shù)據(jù)來(lái)源于全局內(nèi)存，并保證所有結(jié)點(diǎn)中數(shù)據(jù)的一致性（畫圖簡(jiǎn)單說(shuō)明）；?大多數(shù)訪存可以局部在本地高速Cache；基于目錄的Cache一致性協(xié)議（Cache原理參考下章）。分布式訪存模型（DMA：DistributedMemoryAccess:各個(gè)結(jié)點(diǎn)的存儲(chǔ)模塊只能被局部CPU訪問(wèn)，其他結(jié)點(diǎn)無(wú)法直接訪問(wèn)局部存儲(chǔ)模塊，稱之為分布式存儲(chǔ)（圖2.2.2），具有特征：內(nèi)存模塊分布局部于各個(gè)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)只能直接訪問(wèn)其局部存儲(chǔ)模塊，對(duì)其他結(jié)點(diǎn)的內(nèi)存訪問(wèn)只能通過(guò)消息傳遞程序設(shè)計(jì)來(lái)實(shí)現(xiàn)；每個(gè)結(jié)點(diǎn)均是一臺(tái)由處理器、存儲(chǔ)器、I/O設(shè)備組成的自洽計(jì)算機(jī)。?多級(jí)存儲(chǔ)結(jié)構(gòu):CPUchip；寄存器二級(jí)Cache一級(jí)Cache本地局部?jī)?nèi)存冠程內(nèi)存(MPI消息傳遞500MHzPentium-IIIClusterCPUchip；寄存器二級(jí)Cache一級(jí)Cache本地局部?jī)?nèi)存冠程內(nèi)存(MPI消息傳遞500MHzPentium-IIICluster容量(B)帶寬(MB/s)延遲(ns)2566000232K40006512K200080500M1200320海量100100,000處理機(jī)每位成本增加訪存延遲比例：微機(jī)機(jī)群1:3:40:160:50,000Origin20001:3:30:50:500一次消息傳遞延遲相當(dāng)于峰值浮點(diǎn)運(yùn)算的次數(shù)>微機(jī)機(jī)群：50,000次Origin2000:1000次通信與CPU計(jì)算速度不匹配：2.3并行機(jī)分類參考資料：文獻(xiàn)1：P21-P25；文獻(xiàn)6：第1章；文獻(xiàn)8、10、11；指令與數(shù)據(jù)流分類：■單指令多數(shù)據(jù)流(SIMD)：按同一條指令，并行機(jī)的各個(gè)不同的功能部件同時(shí)對(duì)不同的數(shù)據(jù)進(jìn)行不同的處理，例如：傳統(tǒng)的向量機(jī)、80年代初期的陣列機(jī)CM-2,目前已經(jīng)退出歷史舞臺(tái)；多指令多數(shù)據(jù)流(MIMD)：不同的處理器可同時(shí)對(duì)不同的數(shù)據(jù)執(zhí)行不同的指令，目前所有并行機(jī)均屬于這一類；多指令單數(shù)據(jù)流(MISD)：至今沒(méi)出現(xiàn)當(dāng)前流行的高性能并行機(jī)體系結(jié)構(gòu)分類：(五類)對(duì)稱多處理共享存儲(chǔ)并行機(jī)(SMP：SymmetricMultiProcessing)；分布共享存儲(chǔ)并行機(jī)(DSM：DistributedSharedMemory)；大規(guī)模并行機(jī)(MPP：MassivelyParallelProcessors)；工作站(微機(jī))機(jī)群(COW：ClusterOfWorkstation、BeowulfPC-Cluster)■并行向量多處理機(jī)(PVP：ParallelVectorProcessors)對(duì)稱多處理共享存儲(chǔ)并行機(jī)(SMP)：圖2.3.1SMP體系結(jié)構(gòu)示意圖SMP具有如下特征：?對(duì)稱共享存儲(chǔ):系統(tǒng)中任何處理器均可直接訪問(wèn)任何存儲(chǔ)模塊中的存儲(chǔ)單元和I/O模塊聯(lián)接的I/O設(shè)備，且訪問(wèn)的延遲、帶寬和訪問(wèn)成功的概率是一致的。

所有內(nèi)存地址單元統(tǒng)一編址。各個(gè)處理器之間的地位等價(jià)，不存在任何特權(quán)處理器。操作系統(tǒng)可在任意處理器上運(yùn)行。?單一的操作系統(tǒng)映像：全系統(tǒng)只有一個(gè)操作系統(tǒng)駐留在共享存儲(chǔ)器中，它根據(jù)各個(gè)處理器的負(fù)載情況，動(dòng)態(tài)地分配各個(gè)進(jìn)程到各個(gè)處理器，并保持各處理器間的負(fù)載平衡。局部高速緩存Cache及其數(shù)據(jù)一致性：每個(gè)處理器均配備局部Cache，它們可以擁有獨(dú)立的局部數(shù)據(jù)，但是這些數(shù)據(jù)必須保持與存儲(chǔ)器中數(shù)據(jù)是一致的。低通信延遲：各個(gè)進(jìn)程通過(guò)讀/寫操作系統(tǒng)提供的共享數(shù)據(jù)緩存區(qū)來(lái)完成處理器間的通信，其延遲通常小于網(wǎng)絡(luò)通信的延遲。共享總線帶寬：所有處理器共享總線的帶寬，完成對(duì)內(nèi)存模塊和I/O模塊的訪問(wèn)。支持消息傳遞、共享存儲(chǔ)并行程序設(shè)計(jì)。SMP具有如下缺點(diǎn)：欠可靠：總線、存儲(chǔ)器或操作系統(tǒng)失效可導(dǎo)致系統(tǒng)崩潰。可擴(kuò)展性（scalability）較差：由于所有處理器共享總線帶寬，而總線帶寬每3年才增加2倍，跟不上處理器速度和內(nèi)存容量的增加步伐，因此，SMP并行機(jī)的處理器個(gè)數(shù)一般少于32個(gè)，且只能提供每秒數(shù)百億次的浮點(diǎn)運(yùn)算性能。SMP典型代表：SGIPOWERChallengeXL系列并行機(jī)（36個(gè)MIPSR1000微處理器）；COMPAQAlphaserver84005/440（12個(gè)Alpha21264個(gè)微處理器）；HP9000/T600（12個(gè)HPPA9000微處理器）；IBMRS6000/R40（8個(gè)RS6000微處理器）。分布共享存儲(chǔ)并行機(jī)（DSM）：結(jié)點(diǎn)PCPU0CPU111irCacheCache結(jié)點(diǎn)0二結(jié)點(diǎn)PCPU0CPU111irCacheCache結(jié)點(diǎn)0二M0OOOOOOOOOOCPU0CPU1ir11CacheCacher-SHUBRouterMP互聯(lián)網(wǎng)絡(luò)圖2.3.2DSM體系結(jié)構(gòu)示意圖DSM較好地改善了SMP并行機(jī)的可擴(kuò)展能力，具有如下特征：并行機(jī)以結(jié)點(diǎn)為單位，每個(gè)結(jié)點(diǎn)包含一個(gè)或多個(gè)CPU,每個(gè)CPU擁有自己的局部Cache，并共享局部存儲(chǔ)器和I/O設(shè)備，所有結(jié)點(diǎn)通過(guò)高性能互聯(lián)網(wǎng)絡(luò)相互聯(lián)接；物理上分布存儲(chǔ)：內(nèi)存模塊局部在各結(jié)點(diǎn)中，并通過(guò)高性能互聯(lián)網(wǎng)絡(luò)相互聯(lián)接避免了SMP訪存總線的帶寬瓶頸，增強(qiáng)了并行機(jī)的可擴(kuò)展能力。單一的內(nèi)存地址空間：盡管內(nèi)存模塊分布在各個(gè)結(jié)點(diǎn)，但是，所有這些內(nèi)存模塊都由硬件進(jìn)行了統(tǒng)一的編址，并通過(guò)互聯(lián)網(wǎng)絡(luò)聯(lián)接形成了并行機(jī)的共享存儲(chǔ)器。各個(gè)結(jié)點(diǎn)即可以直接訪問(wèn)局部?jī)?nèi)存單元，又可以直接訪問(wèn)其他結(jié)點(diǎn)的局部?jī)?nèi)存單元。非一致內(nèi)存訪問(wèn)（NUMA）模式：由于遠(yuǎn)端訪問(wèn)必須通過(guò)高性能互聯(lián)網(wǎng)絡(luò)，而本地訪問(wèn)只需直接訪問(wèn)局部?jī)?nèi)存模塊，因此，遠(yuǎn)端訪問(wèn)的延遲一般是本地訪問(wèn)延遲的3倍以上。單一的操作系統(tǒng)映像：類似于SMP，在DSM并行機(jī)中，用戶只看到一個(gè)操作系統(tǒng)，它可以根據(jù)各結(jié)點(diǎn)的負(fù)載情況，動(dòng)態(tài)地分配進(jìn)程。基于Cache的數(shù)據(jù)一致性：通常采用基于目錄的Cache一致性協(xié)議來(lái)保證各結(jié)點(diǎn)的局部Cache數(shù)據(jù)與存儲(chǔ)器中數(shù)據(jù)的一致性。同時(shí)，我們也稱這種DSM并行機(jī)結(jié)構(gòu)為CC-NUMA結(jié)構(gòu)。低通信延遲與高通信帶寬：專用的高性能互聯(lián)網(wǎng)絡(luò)使得結(jié)點(diǎn)間的延遲很小，通信帶寬可以擴(kuò)展。例如，目前最先進(jìn)的DSM并行機(jī)SGIOrigin3000的雙向點(diǎn)對(duì)點(diǎn)通信帶寬可達(dá)3.2GB/秒，而延遲小于1個(gè)微秒。DSM并行機(jī)可擴(kuò)展到上百個(gè)結(jié)點(diǎn)，能提供每秒數(shù)千億次的浮點(diǎn)運(yùn)算性能。例如，SGIOrigin2000可以擴(kuò)展到64個(gè)結(jié)點(diǎn)（128個(gè)CPU），而SGIOrigin3000可以擴(kuò)展到256個(gè)結(jié)點(diǎn)（512個(gè)CPU）。但是，由于受Cache一致性要求和互聯(lián)網(wǎng)絡(luò)性能的限制，當(dāng)結(jié)點(diǎn)數(shù)目進(jìn)一步增加時(shí)，DSM并行機(jī)的性能也將大幅下降。支持消息傳遞、共享存儲(chǔ)并行程序設(shè)計(jì)。DSM典型代表：SGIOrigin2000；SGIOrigin3800。大規(guī)模并行機(jī)（MPP）：數(shù)百個(gè)乃至數(shù)千個(gè)處理器組成的大規(guī)模并行機(jī)?！龅湫痛恚寒?dāng)前位于TOP500前列（參考第7章并行機(jī)性能測(cè)試）的并行機(jī)均屬于這一類，其中包括IBMASCIWhite（8192個(gè)處理器）、IntelASCIRed（9632個(gè)處理器）、IBMASCIBluePacific（5808個(gè)處理器）、SGIASCIBlueMountain（6144個(gè)處理器）、IBMSPPOWER3（1336個(gè)處理器）、CRAYT3E1200（1084個(gè)處理器）等?！龅湫腕w系結(jié)構(gòu):圖2.3.3MPP體系結(jié)構(gòu)示意圖■MPP特征:由數(shù)百個(gè)乃至數(shù)千個(gè)計(jì)算結(jié)點(diǎn)和I/O結(jié)點(diǎn)組成，這些結(jié)點(diǎn)由局部網(wǎng)卡（NIC）通過(guò)高性能互聯(lián)網(wǎng)絡(luò)相互聯(lián)接。?每個(gè)結(jié)點(diǎn)相對(duì)獨(dú)立，并擁有一個(gè)或多個(gè)微處理器（P/C）。這些微處理器均配備有局部Cache，并通過(guò)局部總線或互聯(lián)網(wǎng)絡(luò)與局部?jī)?nèi)存模塊和I/O設(shè)備相聯(lián)接。MPP的各個(gè)結(jié)點(diǎn)均擁有不同的操作系統(tǒng)映像。一般情況下，用戶可以將作業(yè)提交給作業(yè)管理系統(tǒng)，由它負(fù)責(zé)調(diào)度當(dāng)前最空閑、最有效的計(jì)算結(jié)點(diǎn)來(lái)執(zhí)行該作業(yè)。但是，MPP也允許用戶登錄到某個(gè)特定的結(jié)點(diǎn)，或在某些特定的結(jié)點(diǎn)上運(yùn)行作業(yè)。各個(gè)結(jié)點(diǎn)間的內(nèi)存模塊相互獨(dú)立，且不存在全局內(nèi)存單元的統(tǒng)一硬件編址。一般情形下，各個(gè)結(jié)點(diǎn)只能直接訪問(wèn)自身的局部?jī)?nèi)存模塊，如果要求直接訪問(wèn)其他結(jié)點(diǎn)的局部?jī)?nèi)存模塊，則必須有操作系統(tǒng)的特殊軟件支持?！霭创鎯?chǔ)結(jié)構(gòu)的不同，MPP又可以分為兩類：分布式存儲(chǔ)大規(guī)模并行機(jī)（DM-MPP）、多臺(tái)SMP或DSM并行機(jī)通過(guò)高性能互聯(lián)網(wǎng)絡(luò)相互聯(lián)接的大規(guī)模機(jī)群（SMP-MPP或DSM-MPP）：DM-MPP:每個(gè)結(jié)點(diǎn)僅包含一個(gè)微處理器，早期的MPP均屬于這一類。例如CRAYT3D、CRAYT3E、IntelParagon、IBMSP-2、YH-3等。SMP-MPP:每個(gè)結(jié)點(diǎn)是一臺(tái)SMP并行機(jī)，例如當(dāng)前位于Top500排名前列的多臺(tái)MPP并行機(jī)均屬于這一類，其中包括IBMASCIWhite、IntelASCIRed、IBMBluePacific等；DSM-MPP:每個(gè)結(jié)點(diǎn)是一臺(tái)DSM并行機(jī)，其典型代表為包含6144臺(tái)處理器的ASCIBlueMountainMPP并行機(jī)，它由48臺(tái)Origin2000構(gòu)成，其中每臺(tái)含128個(gè)微處理器。

?微機(jī)機(jī)群(BeowulfPC-Cluster)：隨著商用微處理器性能的飛速發(fā)展，低延遲、高帶寬商用網(wǎng)絡(luò)父換機(jī)的出現(xiàn)，和LINUX操作系統(tǒng)等自由軟件的成熟，并行計(jì)算機(jī)不再是一個(gè)只有大型科研單位才能擁有的設(shè)備。例如，將128臺(tái)當(dāng)前市場(chǎng)上最高性能的IntelPentium-III/800MHz的微機(jī)通過(guò)6個(gè)24端口的100Mbps的網(wǎng)絡(luò)交換機(jī)相互聯(lián)接，即可構(gòu)成浮點(diǎn)峰值性能在1000億次左右的并行機(jī)，而其成本不超過(guò)200萬(wàn)元人民幣，性能價(jià)格比遠(yuǎn)遠(yuǎn)高于以上提到的各類并行機(jī)(30倍以上)，國(guó)際上稱該類自行研制的并行機(jī)為Beowulf機(jī)群。盡管微機(jī)機(jī)群在通信性能、穩(wěn)定性和使用方便等方面有待大幅度提高，但是，它們以其他并行機(jī)無(wú)法比擬的性能價(jià)格比，近年來(lái)已經(jīng)成為了高性能并行計(jì)算中的一支不可忽視的重要力量。目前，在我國(guó)的各個(gè)大學(xué)和科研機(jī)構(gòu)，例如中科院、北京大學(xué)、清華大學(xué)等，微機(jī)機(jī)群也得到了快速發(fā)展和推廣應(yīng)用。特別地，在2000年底的Top500排名中，美國(guó)Sandi國(guó)家重點(diǎn)實(shí)驗(yàn)室自行研制的機(jī)群Cplant排名第84位。圖2.3.4Beowulf微機(jī)機(jī)群示意圖(參考張林波講義之圖)Beowulf微機(jī)機(jī)群的體系結(jié)構(gòu)如圖2.3.4所示，多臺(tái)高性能微機(jī)通過(guò)商用網(wǎng)絡(luò)交換機(jī)相互聯(lián)接，并擁有各自獨(dú)立的操作系統(tǒng)、主板、內(nèi)存、硬盤和其他I/O設(shè)備，構(gòu)成機(jī)群的計(jì)算結(jié)點(diǎn)。配置一臺(tái)或多臺(tái)文件服務(wù)器，一方面管理機(jī)群計(jì)算結(jié)點(diǎn)共享的所有軟件和用戶計(jì)算資源，另一方面充當(dāng)機(jī)群與外部網(wǎng)絡(luò)的聯(lián)接橋梁，外部科研網(wǎng)的用戶只有通過(guò)文件服務(wù)器才能使用機(jī)群的計(jì)算資源。由于受商用交換機(jī)網(wǎng)絡(luò)性能和操作系統(tǒng)功能的影響，Beowulf微機(jī)機(jī)群的處理機(jī)規(guī)模一般限制在100臺(tái)左右。但是，如果將交換機(jī)替換成專用機(jī)群網(wǎng)絡(luò)，例如GigaNet、Myrinet等，則它們的規(guī)?？梢赃M(jìn)一步擴(kuò)大。因此，在當(dāng)前技術(shù)條件下，微機(jī)機(jī)群一般可提供千億次左右的浮點(diǎn)峰值性能。?并行向量多處理并行機(jī)(PVP)：體系結(jié)構(gòu)類似于DM-MPP，但是每個(gè)CPU為向量多處理機(jī)。僅日本研制，應(yīng)用不廣。2.4并行機(jī)舉例SMP并行機(jī)：SGIPowerChallengeXLR10000：多個(gè)（＜18）個(gè)SGIR10000微處理器、共享存儲(chǔ)模塊、I/O設(shè)備通過(guò)系統(tǒng)總線相互聯(lián)接?？偩€帶寬：2.4GB/秒。單一操作系統(tǒng)影像。DSM并行機(jī)：SGIOrigin2000、SGIOrigin3800：?jiǎn)我挥跋癫僮飨到y(tǒng)。Origin2000可擴(kuò)展到8個(gè)機(jī)柜，每個(gè)機(jī)柜含8個(gè)結(jié)點(diǎn)，結(jié)點(diǎn)是構(gòu)成Origin2000的基本單位，它包含：1-2個(gè)主頻為195MHz或250MHz的MIPSR10000CPU,每個(gè)CPU含4MB的二級(jí)Cache；內(nèi)存512MB-4GB，分主存和目錄內(nèi)存兩類，后者主要用于保持結(jié)點(diǎn)間的Cache數(shù)據(jù)一致性；集線器（HUB）含4個(gè)端口：CPU端口、內(nèi)存端口、XIO端口和CrayLink互聯(lián)網(wǎng)絡(luò)端口，采用交叉開(kāi)關(guān)實(shí)現(xiàn)兩個(gè)CPU、內(nèi)存、輸入輸出和互聯(lián)網(wǎng)絡(luò)路由器（router）之間的全互聯(lián)，分別提供780MB/Sec、780MB/Sec、1.5GB/Sec、1.5GB/Sec的傳送速度。Origin2000的所有結(jié)點(diǎn)通過(guò)CrayLink高性能互聯(lián)網(wǎng)絡(luò)相互聯(lián)接,路由器是構(gòu)成CrayLink的基本單位，它包含6個(gè)端口，內(nèi)部采用交叉開(kāi)關(guān)實(shí)現(xiàn)端口間的全互聯(lián)，具有9.3GB/Sec的峰值帶寬。每個(gè)路由器的兩個(gè)端口用于聯(lián)接結(jié)點(diǎn)，其余4個(gè)端口實(shí)現(xiàn)路由器間的互聯(lián)，形成互聯(lián)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。該CrayLink的半分帶寬與結(jié)點(diǎn)個(gè)數(shù)成線性遞增關(guān)系，對(duì)任意兩個(gè)結(jié)點(diǎn),至少能提供兩條路徑，保證了結(jié)點(diǎn)間的高帶寬、低延遲聯(lián)接和互聯(lián)網(wǎng)絡(luò)的穩(wěn)定性和容錯(cuò)能力。圖3.2.5SGIOrigin2000并行機(jī)體系結(jié)構(gòu)示意圖?SMP-MPP：ASCIWhite：512臺(tái)IBMSMPNH-2結(jié)點(diǎn)通過(guò)SP交換機(jī)相互聯(lián)接；每個(gè)結(jié)點(diǎn)為SMP并行機(jī)，含16個(gè)IBMPowerP3/375MHz微處理器，共享16GB內(nèi)存；總計(jì)計(jì)算處理器8192個(gè)，內(nèi)存4-6TB,峰值性能12.3TFLOPS，磁盤總?cè)萘?50TB（可擴(kuò)展到160TB）；總投資1.1億美元，美國(guó)能源部向IBM租借，年租金為8500萬(wàn)美元；重106噸，兩個(gè)籃球場(chǎng)大；結(jié)點(diǎn)間支持消息傳遞并行程序設(shè)計(jì)，結(jié)點(diǎn)內(nèi)部支持共享存儲(chǔ)、消息傳遞兩種并行編程模式，也支持消息傳遞和共享存儲(chǔ)混合編程模式?！鑫C(jī)機(jī)群：聯(lián)想深騰