引言

單處理器超級計算機已經(jīng)接近物理極限，無法繼續(xù)提升計算能力仔掸。因此脆贵，本書將研究利用多處理器并行性的先進計算機體系結(jié)構(gòu)。并行計算在內(nèi)部互連的處理器中已成為主要形式起暮，而計算機網(wǎng)絡(luò)的發(fā)展則引入了一種新類型的并行性卖氨，即聯(lián)網(wǎng)自治計算機。與將所有組件集中在一個盒子中负懦，通過緊耦合處理器和存儲器來獲得并行性不同筒捺，因特網(wǎng)通過松耦合所有組件在盒子外部獲取并行性。為了最大程度地利用計算機系統(tǒng)的內(nèi)部和外部并行性纸厉，設(shè)計師和開發(fā)者必須了解硬件和軟件之間的交互系吭。本書的目的是讓讀者了解多處理器系統(tǒng)的優(yōu)勢和局限性，先進體系結(jié)構(gòu)和并行性既帶來了優(yōu)勢残腌，也帶來了挑戰(zhàn)村斟。本書由十章組成贫导，包括導論、計算機體系結(jié)構(gòu)分類蟆盹、共享存儲器和消息傳遞系統(tǒng)孩灯、互連網(wǎng)絡(luò)、性能評估寨昙、并行算法和復(fù)雜性分析、網(wǎng)絡(luò)計算概念、并行虛擬機編程、消息傳遞接口標準、任務(wù)分配和調(diào)度問題解決方法等內(nèi)容狂秦。適合計算機工程灌侣、計算機科學和電氣工程的大學生閱讀，也可作為研究生課程教材或從業(yè)者的綜合參考書裂问。

第1章 先進計算機體系結(jié)構(gòu)與并行處理導論

• 1.1 計算的四個年代

批處理年代
IBM System/360是一款代表性的大型批處理機器侧啼，具有穿孔卡閱讀機痊乾、磁帶和磁盤驅(qū)動器，并在一個計算機房內(nèi)連接待德。它具有操作系統(tǒng)、多種編程語言和10MB磁盤存儲器纠拔，可支持1MB磁心存儲器容量床嫌。
分時年代
20世紀60年代后，大型機占據(jù)重要地位显押，但小型機仍昂貴且難于使用笤休。分時系統(tǒng)由DEC、Pime和DalaCeneral公司制造的小型機帶來，與集中式數(shù)據(jù)處理主機共存帮匾。同時期超級計算機也出現(xiàn)佣蓉，如CDC6600和Cray-1基显。
臺式機年代
1977年，PC由多公司推出，提高了用戶生產(chǎn)率挨队。Conpaq榨呆、Apple澳化、IBM砌创、Dell等公司的PC普及呻疹，改變了計算方式惶翻。約1990年姑蓝，功能強大的PC和LAN取代大型機和小型機，性價比大幅提高撕予。這些PC后來通過WAN連接成更大的計算聯(lián)合體。
網(wǎng)絡(luò)年代
20世紀90年代，網(wǎng)絡(luò)技術(shù)蓬勃發(fā)展讲衫，超越處理器技術(shù)。商用并行計算機興起，分為共享存儲器和分布式存儲器系統(tǒng)，處理器數(shù)量從幾個增至數(shù)千個粹污。代表機型有Soquen Symmetry段多、Intel CUBE殉农、Thinking Machines（CM-2诗充，CM-5）等脂信。

• 1.2 計算機體系結(jié)構(gòu)的弗林分類方法

弗林分類方法是基于信息流概念失乾，將計算機體系結(jié)構(gòu)分為四種類型：SISD、SIMD韧骗、MISD市栗、MIMD鲫骗。SISD是傳統(tǒng)的單處理器馮·諾依曼計算機系統(tǒng)沈贝，SIMD和MIMD是并行計算機系統(tǒng)杠人，其中SIMD有一個控制部件同步執(zhí)行相同指令，而MIMD每個處理器有自己的控制部件可執(zhí)行不同指令。Kuck在此基礎(chǔ)上進一步擴展分類嗡善，形成16類體系結(jié)構(gòu)辑莫。

• 1.3 SIMD體系結(jié)構(gòu)

SIMD模型是指由前端計算機和處理器陣列組成的并行計算模型。處理器陣列包含多個同步處理單元罩引，可以在不同的數(shù)據(jù)上同時執(zhí)行相同的操作各吨。前端計算機通過存儲器總線與處理器陣列連接，控制其執(zhí)行并行操作袁铐。SIMD模型在大規(guī)模數(shù)據(jù)集上的并行計算非常有效揭蜒，特別適用于規(guī)則的數(shù)值計算。SIMD機器的配置結(jié)構(gòu)可以是每個處理器都有局部存儲器或者處理器和存儲器之間通過互連網(wǎng)絡(luò)通信剔桨。

• 1.4 MIMD體系結(jié)構(gòu)

MMID并行體系結(jié)構(gòu)分為兩大類：共享存儲器和消息傳遞忌锯。共享存儲器使用中央存儲器交換信息，消息傳遞通過互連網(wǎng)絡(luò)完成领炫。SMP系統(tǒng)是一種共享存儲器系統(tǒng)，多處理器平等地訪問全局存儲器张咳，通常通過總線和高速緩存控制器通信帝洪。這降低了多端口存儲器和接口電路的需求，也適用于消息傳遞模式脚猾。

共享存儲器組成
共享存儲器模型中葱峡，處理器通過共享存儲器單元進行通信。訪問控制龙助、同步砰奕、保護和安全是設(shè)計共享存儲器系統(tǒng)時需要考慮的基本問題。系統(tǒng)可以是均勻存儲器訪問（UMA）提鸟、非均勻存儲器訪問（NUMA）或全高速緩存（COMA）架構(gòu)军援。UMA系統(tǒng)中，所有處理器具有相同的訪問時間称勋；NUMA系統(tǒng)中胸哥，訪問時間取決于處理器與存儲器之間的距離；COMA系統(tǒng)中赡鲜，共享存儲器是由高速緩存組成的空厌。
消息傳遞組成
消息傳遞系統(tǒng)中，處理器有獨立存儲银酬，通過發(fā)送和接收操作通信嘲更。節(jié)點包含處理器和存儲器。消息存儲在緩沖器中等待處理和發(fā)送/接收操作揩瞪。操作系統(tǒng)控制并行處理和問題求解赋朦。處理器不共享全局存儲，每個處理器訪問自己的地址空間。處理部件可以用各種連接方式北发，如超立方體網(wǎng)絡(luò)纹因、二維/三維網(wǎng)格。系統(tǒng)設(shè)計考慮可擴展性琳拨、鏈路帶寬和網(wǎng)絡(luò)時延瞭恰。蟲孔路由減小緩沖器和消息時延，包被分割為片順序傳輸狱庇。

• 1.5 互連網(wǎng)絡(luò)

操作方式
互連網(wǎng)絡(luò)有同步和異步操作方式惊畏。同步使用全局時鐘，系統(tǒng)以步調(diào)運行密任。異步不需時鐘颜启，利用握手信號協(xié)調(diào)操作。同步較慢但無競爭浪讳。
控制策略
互連網(wǎng)絡(luò)根據(jù)控制策略可分為集中式和分散式缰盏。集中式控制有單個中央控制部件監(jiān)測和控制系統(tǒng)操作，但可能成為性能瓶頸淹遵。分散式控制功能分布在系統(tǒng)內(nèi)不同部件中口猜。交叉開關(guān)是集中式系統(tǒng)，多級互連網(wǎng)絡(luò)是分散式系統(tǒng)透揣。
交換技術(shù)
互連網(wǎng)絡(luò)根據(jù)交換機制分為電路交換和包交換網(wǎng)絡(luò)济炎。電路交換需要在通信前建立完整路徑并保持通路。包交換則將消息劃分為包辐真，通過存儲轉(zhuǎn)發(fā)方式從源到目的地傳輸须尚。包交換比電路交換更有效利用網(wǎng)絡(luò)資源，但存在可變包延遲侍咱。
拓撲
互連網(wǎng)絡(luò)拓撲是指處理器和存儲器之間的連接方式耐床。它描述了如何將處理器和存儲器連接起來⌒ǜ互連網(wǎng)絡(luò)可以分為靜態(tài)和動態(tài)兩種類型咙咽。靜態(tài)互連網(wǎng)絡(luò)在系統(tǒng)設(shè)計時就建立了所有連接，而動態(tài)互連網(wǎng)絡(luò)是在需要時才建立連接淤年。共享存儲器系統(tǒng)可以使用基于總線或基于交換的互連網(wǎng)絡(luò)钧敞。基于總線的系統(tǒng)使用總線連接處理器和存儲器麸粮，而基于交換的系統(tǒng)使用交換開關(guān)來建立連接溉苛。消息傳遞互連網(wǎng)絡(luò)也可以是靜態(tài)或動態(tài)的。靜態(tài)互連網(wǎng)絡(luò)在系統(tǒng)設(shè)計時就確定了所有連接弄诲，而動態(tài)互連網(wǎng)絡(luò)只在消息傳遞時才建立連接愚战〗课ǎ互連網(wǎng)絡(luò)的拓撲結(jié)構(gòu)對系統(tǒng)性能有很大影響，例如線性陣列寂玲、環(huán)形塔插、網(wǎng)格、樹狀和超立方體等拓撲結(jié)構(gòu)拓哟。

第2章 多處理器互連網(wǎng)絡(luò)

• 2.1 互連網(wǎng)絡(luò)的分類

• 2.2 基于總線的動態(tài)互連網(wǎng)絡(luò)

單總線系統(tǒng)
單總線是連接多處理器系統(tǒng)的簡單方法想许。通用形式包括一條總線連接N個處理器，每個處理器有自己的高速緩存断序，減少處理器與存儲器間通信流纹。系統(tǒng)規(guī)模通常在2~50個處理器，實際規(guī)模取決于通信量和總線帶寬违诗。單總線復(fù)雜性為0（1）漱凝，時間復(fù)雜性為0（N）。雖簡單易擴展诸迟，但受總線帶寬限制茸炒，只允許一個存儲器訪問。
多總線系統(tǒng)
多總線多處理機系統(tǒng)是對單條共享總線系統(tǒng)的自然擴展阵苇，采用多條并行總線連接處理器和存儲器扣典。連接方案包括全總線-存儲器連接的多總線、單總線-存儲器連接的多總線慎玖、部分總線-存儲器連接的多總線和基于類的存儲器連接的多總線。多總線多處理機系統(tǒng)提供高可靠性和易于增量擴展笛粘，但總線競爭會增加趁怔。

總線同步
總線分為同步和異步。同步總線具有預(yù)知的事務(wù)執(zhí)行時間薪前，考慮處理時間润努。異步總線依賴數(shù)據(jù)可用性和部件準備情況。單總線多處理機需總線仲裁解決競爭示括。仲裁邏輯使用優(yōu)先級方案確定哪個處理器控制總線铺浇。握手需要總線請求和總線授予信號。系統(tǒng)使用隨機吼拥、輪轉(zhuǎn)屋确、相等和LRU優(yōu)先級方案纵东。

• 2.3 基于交換的互連網(wǎng)絡(luò)

交叉開關(guān)網(wǎng)絡(luò)
交叉開關(guān)網(wǎng)絡(luò)是單總線網(wǎng)絡(luò)的對立極端症虑，允許所有輸入和輸出的連接。每個交叉點含開關(guān)元件(SE)，提供多路連接孩锡。復(fù)雜度以開關(guān)點數(shù)度量这溅，時間復(fù)雜度低臭胜。交叉開關(guān)非阻塞，支持多連接模式癞尚。但在大型系統(tǒng)中耸三，復(fù)雜性可能成為關(guān)鍵的成本問題。

單級網(wǎng)絡(luò)
單級網(wǎng)絡(luò)使用最簡單的2×2開關(guān)元件(SE)浇揩，下圖展示了四種設(shè)置：直通仪壮、交換、上廣播和下廣播临燃【Σ担混洗-交換是常用的連接模式，通過混洗和交換操作將數(shù)據(jù)循環(huán)傳輸膜廊。單級網(wǎng)絡(luò)中每級的開關(guān)單元數(shù)為N/2乏沸，路徑長度最大為N。PM2I網(wǎng)絡(luò)可模擬立方體網(wǎng)絡(luò)爪瓜，反之亦然蹬跃。

多級網(wǎng)絡(luò)
多級互連網(wǎng)絡(luò)(MIN)改善單總線系統(tǒng)的限制，提供多條通路铆铆。一個通用MIN由多級組成蝶缀，每級有2×2開關(guān)元件。級間連接可采用混洗-交換等路由函數(shù)薄货。MIN的優(yōu)勢是方便的消息路由翁都。在一個NXN網(wǎng)絡(luò)中，每級的路由基于目的地址谅猾，控制每級開關(guān)元件的上下輸出柄慰。榕樹網(wǎng)絡(luò)是一種多級互連網(wǎng)絡(luò)。網(wǎng)絡(luò)的復(fù)雜性由總開關(guān)元件數(shù)度量税娜，延遲和時間復(fù)雜性由經(jīng)過的開關(guān)元件數(shù)衡量坐搔。Omega網(wǎng)絡(luò)是另一種常見的多級互連網(wǎng)絡(luò)類型，由多級混洗-交換網(wǎng)絡(luò)組成敬矩。這些多級互連網(wǎng)絡(luò)被廣泛應(yīng)用于研究和商用領(lǐng)域概行。
多級互連網(wǎng)絡(luò)中的阻塞
多級互連網(wǎng)絡(luò)按阻塞性可分為阻塞網(wǎng)絡(luò)、可重排網(wǎng)絡(luò)和非阻塞網(wǎng)絡(luò)弧岳。阻塞網(wǎng)絡(luò)如Omega凳忙、榕樹业踏、混洗-交換和Baseline，限制新連接的建立消略”こ疲可重排網(wǎng)絡(luò)如Benes，允許重新排布連接以建立其他連接艺演。非阻塞網(wǎng)絡(luò)如Clos却紧，在已連接的情況下總能建立新連接。Clos網(wǎng)絡(luò)由多級交叉開關(guān)組成胎撤，滿足特定的不等式條件晓殊。

• 2.4 靜態(tài)互連網(wǎng)絡(luò)

全連接網(wǎng)絡(luò)
全連接網(wǎng)絡(luò)（CCN）中的每個節(jié)點與其他節(jié)點相連，確保消息快速從源節(jié)點到目的節(jié)點傳遞（經(jīng)過一條鏈路）伤提。節(jié)點之間的路由簡單巫俺，但構(gòu)建所需鏈路昂貴，特別在大規(guī)模情況下肿男。鏈路數(shù)由為N（N-1）/2介汹，網(wǎng)絡(luò)復(fù)雜度為O(N)，延遲復(fù)雜度為O(1)舶沛。
有限連接網(wǎng)絡(luò)
有限連接網(wǎng)絡(luò)（LCN）不提供每個節(jié)點直接鏈接缭贡，通信需經(jīng)過其他節(jié)點路由窍荧。預(yù)期通路長度較全連接網(wǎng)絡(luò)長栖袋。LCN需要互連模式和路由機制舒岸。線性陣列、環(huán)狀網(wǎng)絡(luò)坪它、二維陣列骤竹、樹狀網(wǎng)絡(luò)和立方體網(wǎng)絡(luò)是常見互連模式。線性陣列的速度慢且復(fù)雜度為O(N)往毡。樹狀網(wǎng)絡(luò)的通信需沿樹上行或下行蒙揣，復(fù)雜度為O(2^k)和O(Ib N)。
立方體連接網(wǎng)絡(luò)
立方體連接網(wǎng)絡(luò)模仿立方體結(jié)構(gòu)开瞭，每個節(jié)點有與其他節(jié)點相連的通信鏈路懒震。通過簡單的路由機制，消息可以沿著不共享公共鏈路的路徑從源節(jié)點到達目的節(jié)點惩阶。在超立方體中挎狸，節(jié)點的度為n扣汪，可以通過連接兩個具有類似地址的子立方體來構(gòu)建更大的立方體網(wǎng)絡(luò)断楷。立方環(huán)體系結(jié)構(gòu)是對基本超立方體的改進方案之一，它將節(jié)點以環(huán)形方式連接崭别。

網(wǎng)格連接網(wǎng)絡(luò)
n維網(wǎng)格通過互連結(jié)構(gòu)連接K×K×…·×K個結(jié)點冬筒，n為維數(shù)恐锣，K為i維基。多種路由機制可用于消息傳遞舞痰，如維序路由土榴。網(wǎng)格互連網(wǎng)絡(luò)支持科學計算，具有緊湊布局和可擴展性响牛。許多分布式存儲器計算機使用網(wǎng)格互連網(wǎng)絡(luò)玷禽，如GoodyearAeroepace的MPP、Itel的Paragon呀打。
k元n立方體網(wǎng)絡(luò)
k元n立方體是一種具有k為基數(shù)的n維立方體網(wǎng)絡(luò)矢赁。每個維度上都有k個結(jié)點。消息在網(wǎng)絡(luò)中采用類似網(wǎng)格網(wǎng)絡(luò)的路由方法贬丛。最短路由是根據(jù)鏈路方向確定的撩银，最長遍歷距離為0（n+k）。

• 2.5 分析和性能指標

動態(tài)網(wǎng)絡(luò)
交叉開關(guān)和多總線是常見的動態(tài)互連網(wǎng)絡(luò)豺憔。交叉開關(guān)的成本取決于內(nèi)部交叉點的數(shù)量额获，延遲是固定的。它具有非阻塞特性和容錯性恭应，但對于大規(guī)模系統(tǒng)來說可能成本高抄邀。多總線系統(tǒng)的成本與總線數(shù)量成正比，延遲與總線數(shù)和處理器數(shù)量成正比暮屡。多總線提供高可靠性和容錯性撤摸，但可能會增加總線沖突。多級互連網(wǎng)絡(luò)的成本衡量開關(guān)元件的數(shù)量褒纲，延遲取決于通過的開關(guān)元件數(shù)准夷。它具有簡化的路由機制，但容錯性較差莺掠。為了改善容錯性可以增加一級開關(guān)元件衫嵌。

靜態(tài)網(wǎng)絡(luò)
全連接網(wǎng)絡(luò)（CCN）中，每個結(jié)點與網(wǎng)絡(luò)中所有其他結(jié)點相連彻秆。該網(wǎng)絡(luò)的成本為N(N-1)/2楔绞，即O(N2)，消息從任何源到目的遍歷的鏈路數(shù)為常數(shù)唇兑，即O(1)酒朵，結(jié)點度為N-1，直徑為常數(shù)扎附。線性陣列網(wǎng)絡(luò)中蔫耽，每個結(jié)點與兩個直接鄰接結(jié)點相連，兩端結(jié)點只與一個鄰接結(jié)點相連留夜。該網(wǎng)絡(luò)的成本為O(N)匙铡，源結(jié)點到目的結(jié)點平均需遍歷的結(jié)點數(shù)為N/2图甜，即O(N)，結(jié)點度為2鳖眼，直徑為N-1黑毅。樹狀網(wǎng)絡(luò)中，每個結(jié)點與父結(jié)點和所有子結(jié)點相連钦讳。在k級全二叉樹中矿瘦，該網(wǎng)絡(luò)的成本為O(2^k)，延遲為O(log(N))愿卒，結(jié)點度為3匪凡，直徑為O(log(N))。立方體連接網(wǎng)絡(luò)中掘猿，任意兩個結(jié)點的二進制地址表示僅有一位不同就相連病游。網(wǎng)絡(luò)成本為O(2^n)，延遲為O(log(N))稠通，結(jié)點度為O(log(N))衬衬，直徑為O(n)。網(wǎng)格連接網(wǎng)絡(luò)中改橘，位于(i,j)的結(jié)點與(i±1,j±1)的鄰居結(jié)點相連滋尉。網(wǎng)絡(luò)成本為O(n2)，延遲為O(1)飞主，結(jié)點度為4狮惜，直徑為O(n)。k元n立方體網(wǎng)絡(luò)是一個基為k的n維立方體碌识。網(wǎng)絡(luò)成本為O(k^n)碾篡，延遲為O(n+k)，結(jié)點度為2n筏餐，直徑為O(n×k)开泽。

第3章 多處理器體系結(jié)構(gòu)的性能分析

• 3.1 計算模型

等持續(xù)時間模型
該模型假設(shè)任務(wù)可劃分為n個等子任務(wù)，每個處理器執(zhí)行一個子任務(wù)魁瞪。使用單處理器執(zhí)行整個任務(wù)所需時間t穆律，每處理器執(zhí)行子任務(wù)時間t/n。模型中忽略通信開銷导俘，實際每處理器執(zhí)行子任務(wù)時間為tm=(t/n)+tco峦耘。加速定義單處理器求解時間與n處理器求解時間比值。效率定義每處理器獲得加速度旅薄。模型基于等持續(xù)時間假設(shè)，實際算法含不可分割串行部分。模型簡單但不現(xiàn)實利朵。處理器間通信和數(shù)據(jù)交換需時間tco。加速與處理器數(shù)n相關(guān)猎莲，tco相對較小時加速接近n绍弟，相對較大時接近t/(t+tco)<1。
具有串行部分的并行計算模型
在計算模型中著洼，部分任務(wù)不可并行化樟遣，其余可拆分成并發(fā)子任務(wù)。在n處理器上執(zhí)行任務(wù)需要時間t=f+(1-f)(t/n)身笤，加速由公式lim[S(n)]=1/f決定豹悬，阿姆達爾定律表明性能改善取決于不可并行部分。通信開銷和不可并行計算部分影響最大加速液荸。效率由加速和處理器數(shù)決定瞻佛，維持處理器效率在增加處理器數(shù)時挑戰(zhàn)重重。性能定律（如Croech娇钱、Amdahl和Custafson-Braeis）關(guān)注并行體系結(jié)構(gòu)潛在性能提升伤柄。

• 3.2 關(guān)于并行體系結(jié)構(gòu)的爭論

Grosch定律
20世紀40年代末，H. Groech研究計算機系統(tǒng)能力P和成本C之間的關(guān)系文搂，提出P=K×C的假設(shè)适刀。他進一步假設(shè)s≈2。按照Groech定律煤蹭，計算機能力的增加與成本平方成正比笔喉，即C=√(P/K)，假設(shè)s=2硝皂。銷售一臺貴一倍的計算機常挚，其速度必須四倍于原來的速度，使計算便宜一半稽物，則計算速度必須為原來的四分之一待侵。隨著計算技術(shù)進步，定律已不適用姨裸。
Amdahl定律
并行系統(tǒng)加速是單處理器求解任務(wù)時間與n個處理器求解同一任務(wù)時間的比值秧倾。阿姆達爾定律與Groech定律類似，強調(diào)性能改善受限傀缩，處理器數(shù)量對加速影響有限那先。但實際中發(fā)現(xiàn)某些并行算法的部分與處理器數(shù)量有關(guān)。當limf(n)=0時赡艰，可實現(xiàn)大規(guī)模問題的線性加速售淡。例如，Sandia國家實驗室使用1024個處理器的系統(tǒng)展示了工程問題的線性加速。算法采用二叉樹結(jié)構(gòu)揖闸，通過三個步驟完成計算揍堕。
Gustafson-Barsis定律
1988年，Sandia實驗室的Gustafson和Barsis研究了阿姆達爾定律和數(shù)百個處理器的并行體系結(jié)構(gòu)在性能改進方面的應(yīng)用汤纸。他們發(fā)現(xiàn)問題規(guī)模隨處理器數(shù)量增大而增大衩茸，與阿姆達爾定律相矛盾。他們提出了比例加速因子SS（n）贮泞，通過使問題規(guī)模與處理器數(shù)量成比例增長楞慈，可以實現(xiàn)更高效的并行性能。他們還強調(diào)關(guān)注互連網(wǎng)絡(luò)性能而非處理器計算啃擦。這一研究對并行計算領(lǐng)域有重要啟示囊蓝。

• 3.3 互連網(wǎng)絡(luò)的性能問題

交叉開關(guān)的帶寬
交叉開關(guān)的帶寬是在一個周期內(nèi)所能接受的平均請求數(shù)。當多個處理器請求訪問同一存儲器模塊時可能發(fā)生爭用令蛉。以三個處理器和三個存儲器模塊的交叉開關(guān)為例聚霜，根據(jù)不同的請求情況計算帶寬。帶寬計算公式為BW = M(1-(1-(p/M))）珠叔。這個公式基于假設(shè)俯萎，即處理器在周期內(nèi)均會對存儲器模塊產(chǎn)生請求。當僅部分處理器請求存儲器模塊時运杭，可得到相似的帶寬表達式夫啊。
多級互連網(wǎng)絡(luò)的帶寬
本節(jié)介紹了多級互連網(wǎng)絡(luò)的帶寬計算方法。對于Delta網(wǎng)絡(luò)辆憔，假設(shè)第一級的請求率為ro撇眯，通過推導可以計算出每一級的輸出請求數(shù)。帶寬計算公式為BW = b × r虱咧。此外熊榛，還探討了時延和平均距離的概念，并介紹了靜態(tài)網(wǎng)絡(luò)的復(fù)雜性腕巡、網(wǎng)絡(luò)互連性和連接性的重要性玄坦。最后，對動態(tài)和靜態(tài)互連網(wǎng)絡(luò)的性能進行了比較绘沉，并討論了并行體系結(jié)構(gòu)的可伸縮性問題煎楣。

• 3.4 并行體系結(jié)構(gòu)的可擴展性

一個可擴展的并行系統(tǒng)可以通過擴大規(guī)模或縮小成本來線性提高性能车伞≡穸可擴展性的表現(xiàn)形式包括速度、效率另玖、規(guī)模困曙、應(yīng)用表伦、代和異構(gòu)性。對于速度而言慷丽，可擴展系統(tǒng)能夠隨處理器數(shù)目的增加成比例地提高速度蹦哼。效率上，可擴展系統(tǒng)應(yīng)能在處理器增加時保持固定效率要糊「傺可擴展性的程度取決于問題規(guī)模相對于處理器數(shù)的增長速率。高可擴展系統(tǒng)的等效率值較小杨耙，而不可擴展系統(tǒng)的等效率值較大。Gustafson證明了在1024個處理器上通過擴展問題規(guī)钠矗可以獲得近線性的加速珊膜。可擴展并行系統(tǒng)的加速與效率之間有關(guān)系宣脉。增加處理器數(shù)通常提高加速车柠，但可能降低效率。引入平均并行性參數(shù)(Q)表示平均繁忙處理器數(shù)塑猖。最大加速部分(S(n)/Q)和效率之和應(yīng)大于1竹祷。平均并行性決定加速和效率權(quán)衡⊙蚬叮可擴展性允許通過增加硬件資源改善性能而無需改變程序塑陵。設(shè)計趨勢是將可擴展性作為主要設(shè)計目標，包括過度設(shè)計和向后兼容性設(shè)計蜡励×罨ǎ基準測試程序用于衡量性能。

• 3.5 基準測試程序性能

基準測試程序用于測試計算機系統(tǒng)性能凉倚。Dhrystone和Whetstone是早期的基準程序兼都，但不夠可靠。現(xiàn)在使用真實應(yīng)用軟件進行性能評估稽寒，如PERFECT扮碧、TPC和SPEC。SPBC是一個非盈利組織杏糙，致力于標準化基準測試程序慎王。SPEC92包含CINT92和CFP92兩套測試程序集，使用SPECratio測量執(zhí)行時間比率宏侍。使用工具和輔助文件編譯和執(zhí)行代碼柬祠，并計算SPEC指標。幾何平均在評估性能時存在批評负芋。SPEC92和SPEC95是計算機性能評測基準逼争，SPEC95取代了SPEC92茴厉，使用幾何平均計算性能結(jié)果姓言。編譯器標志對SPEC評分有影響，調(diào)整參數(shù)可提高評分蠕嫁，但再現(xiàn)性困難。SPEC95是衡量單個基準測試程序的速度毯盈，SPEC率是衡量多個基準測試程序的速度剃毒。AlphaStation和Personal Workstation性能相似，AlphaServer性能稍優(yōu)搂赋。

第4章 共享存儲器體系結(jié)構(gòu)

共享存儲器系統(tǒng)中赘阀，多處理器共享全局存儲器，通過讀寫全局存儲器進行任務(wù)通信和協(xié)調(diào)脑奠。性能衰退和一致性問題是需要考慮的主要挑戰(zhàn)基公。高速緩存可以解決爭用問題，但多個數(shù)據(jù)副本可能導致一致性問題宋欺。本章研究不同的共享存儲器系統(tǒng)和一致性解決方法轰豆。
最簡共享存儲器系統(tǒng)由一個存儲器模塊（M）和兩個處理器（P和P）組成。通過仲裁部件齿诞，請求傳遞給存儲器控制器進行滿足酸休。系統(tǒng)根據(jù)互連網(wǎng)絡(luò)的不同可分為不同類型。

• 4.1 共享存儲器系統(tǒng)的分類

均勻存儲器訪問
均勻存儲器訪問（UMA）系統(tǒng)中祷杈，處理器通過互連網(wǎng)絡(luò)訪問共享存儲器斑司。處理器具有相同訪問時間。UMA稱為SMP系統(tǒng)但汞，常見商用實例有Sun Microsystem的多處理器服務(wù)器陡厘。
非均勻存儲器訪問
非均勻存儲器訪問（NUMA）系統(tǒng)中，每處理器連接部分共享存儲器特占，地址空間單一糙置，但訪問時間依賴距離。導致非均勻訪問時間是目。多種NUMA體系結(jié)構(gòu)谤饭，如樹狀和層次式總線網(wǎng)絡(luò)，將處理器與存儲器模塊相連懊纳。實例包括BBN TC-2000揉抵、SGI Origin 3000。
全高速緩存存儲器體系結(jié)構(gòu)
全高速緩存存儲器體系結(jié)構(gòu)（COMA）類似于NUMA嗤疯，每個處理器有部分共享存儲器冤今，但該存儲器是由高速緩存構(gòu)成的。COMA要求數(shù)據(jù)遷移到需要的處理器茂缚。無存儲器層次戏罢，地址空間由所有高速緩存構(gòu)成屋谭。高速緩存目錄（D）實現(xiàn)遠程緩存訪問。實例包括Kendall Square Research公司的KSR-1龟糕。

• 4.2 基于總線的對稱多處理機系統(tǒng)

共享存儲器系統(tǒng)使用總線或交叉開關(guān)互連網(wǎng)絡(luò)桐磁，總線/高速緩存體系結(jié)構(gòu)減少了存儲器和接口電路成本，但當多個處理器同時訪問總線時可能飽和讲岁。高命中率是目標我擂，減少處理器對總線的使用次數(shù)。缺失率表示無法滿足需求的比例缓艳。對于N個處理器系統(tǒng)校摩，當N（1-h）V≤BI時，總線飽和阶淘。其中h為命中率衙吩，V為處理器速度，B為總線速度舶治，I為工作周期速率分井〕碘總線能夠支持的具有高速緩沖存儲器的最大處理器數(shù) N≤BI/(1-h)V霉猛。

• 4.3 基本的高速緩存一致性方法

高速緩存一存儲器一致性
高速緩存中多個數(shù)據(jù)副本導致一致性問題，需算法維護一致性珠闰。通寫策略每次更新高速緩存時都更新存儲器惜浅，回寫策略僅在替換塊時更新。處理器請求存儲單元數(shù)據(jù)復(fù)制到高速緩存伏嗜，更新后需保持一致坛悉。下表給出了通寫和回寫策略。

高速緩存-高速緩存一致性
多處理機系統(tǒng)中承绸，處理器P請求全局存儲單元X數(shù)據(jù)裸影，復(fù)制到本地高速緩存。若Q寫新值到X军熏，則基于寫-無效策略轩猩，其他副本無效〉磁欤基于寫-更新策略均践，立即更新所有緩存副本。下表給出了兩種策略摩幔。

共享存儲器系統(tǒng)一致性
有四種緩存一致性組合：寫-更新和通寫彤委、寫-更新和回寫、寫-無效和通寫或衡、寫-無效和回寫焦影。直接在X上進行寫-更新和通寫會使總線忙碌车遂，處理器最終等待寫完成并變?yōu)榭臻e。寫-更新和回寫只更新緩存副本偷办，限制寫入高速緩存0導致不一致艰额。污染位可防止X值擴散，但不一致副本最終需要更新椒涯。

• 4.4 監(jiān)聽協(xié)議

監(jiān)聽協(xié)議基于監(jiān)測總線活動并執(zhí)行一致性命令柄沮。全局存儲器以塊移動，每塊有狀態(tài)確定其內(nèi)容變化废岂。讀寫操作可能改變塊狀態(tài)祖搓。高速緩存不命中表示請求的塊不在高速緩存中或已無效。監(jiān)聽協(xié)議根據(jù)更新/無效和數(shù)據(jù)來源處理寫操作和缺失操作湖苞。
寫一無效和通寫：確保存儲器與最新更新的高速緩存副本一致拯欧。處理器可以安全地讀取存儲器副本，直到有處理器更新它财骨。所有高速緩存副本無效镐作，存儲器更新以保持一致性。
寫一無效和回寫（所有權(quán)協(xié)議）：該協(xié)議允許一個有效塊在存儲器擁有隆箩，并在多個高速緩存之間共享该贾，這些高速緩存只包含塊的共享副本。處理器可以安全地從高速緩存中讀取這些塊捌臊，直到有一個處理器更新其副本杨蛋。此時，更新者成為唯一的擁有者理澎，其他副本無效逞力。
寫一次：Goodman于1983年提出了寫無效協(xié)議，該協(xié)議使用通寫和回寫策略的組合糠爬。第一次寫塊時采用通寫策略寇荧，以后的寫則采用回寫策略。
寫更新和部分通寫：更新高速緩存后立即寫入存儲器执隧，并廣播給其他共享該塊的高速緩存揩抡。高速緩存監(jiān)聽總線并更新本地緩存。專用總線指示至少有一個高速緩存共享該塊殴玛。
寫-更新和回寫：此協(xié)議類似于前面一個協(xié)議捅膘，只需將共享塊被更新時通寫存儲器改為當塊要被普換時才更新存儲器。

• 4.5 基于目錄的協(xié)議

互連網(wǎng)絡(luò)和大型共享存儲系統(tǒng)中滚粟，使用監(jiān)聽協(xié)議更新或使緩存無效不現(xiàn)實寻仗。基于目錄的協(xié)議是解決方案凡壤，消息存儲在塊副本的高速緩存中署尤，目錄維護處理器和存儲塊的狀態(tài)信息耙替。目錄可以集中式或分布式。集中式目錄存在搜索時間長的問題曹体，分布式目錄允許每個存儲模塊保持獨立的目錄項俗扇，緩解了問題。
協(xié)議分類
每個數(shù)據(jù)塊的目錄項包含指向副本位置的指針和一個污染位箕别，用于允許高速緩存寫入存儲器塊铜幽。基于目錄的協(xié)議分為三類：全映射目錄串稀、有限目錄和鏈目錄除抛。全映射目錄中，每個目錄項有N個指針母截，其中N為處理器數(shù)到忽。有限目錄中，每個目錄項的指針數(shù)是固定的清寇，不考慮處理器數(shù)喘漏。鏈目錄通過在高速緩存中分布存放目錄來解決目錄規(guī)模問題。
使無效協(xié)議
(1) 集中式目錄使無效的步驟：1.發(fā)送寫請求华烟。2.中央目錄確定處理器副本翩迈。3.使無效信號和指向處理器的指針傳送給所有含有該副本的處理器。4.被使無效的高速緩存向請求處理器發(fā)送確認消息垦江。5.只有寫處理器高速緩存中保留該塊的副本帽馋。
(2) 可擴展一致性接口（SCI）協(xié)議：1.基于分布式目錄雙向鏈表搅方。2.每個高速緩存塊在共享處理器表中加入比吭。3.存儲器和高速緩存項有標志位。4.存儲器中的目錄大小等于存儲器塊數(shù)乘以高速緩存數(shù)姨涡。
(3) 斯坦福分布式目錄（SDD）協(xié)議：1.基于分布式目錄單向鏈表衩藤。2.存儲器指向共享表頭。3.每個處理器指向前驅(qū)處理器涛漂。4.加入和退出共享表的處理與SCI協(xié)議有所不同赏表。

• 4.6 共享存儲器的編程

任務(wù)創(chuàng)建
共享存儲器系統(tǒng)可用于大粒度級的分時處理，新進程分配給閑置處理器或最少工作量處理器匈仗。重量級任務(wù)包括頁表瓢剿、存儲器和文件描述。細粒度級采用輕量級進程悠轩，并適用于同構(gòu)和異構(gòu)任務(wù)间狂。應(yīng)用以分叉-匯合構(gòu)造的監(jiān)督者-工作者模型創(chuàng)建。
通信
進程有三種存儲段：文本火架、數(shù)據(jù)和堆棧鉴象。文本存儲執(zhí)行的二進制代碼忙菠，數(shù)據(jù)存儲程序數(shù)據(jù)，堆棧存儲活動記錄和動態(tài)數(shù)據(jù)纺弊。串行進程只能訪問自身的數(shù)據(jù)和堆棧段牛欢。并行進程添加一個共享數(shù)據(jù)段，允許共享范圍增長淆游。并行進程通過共享變量進行通信傍睹。
同步
同步保護共享變量犹菱，確保只有一個進程可以訪問焰望。同步協(xié)調(diào)并行進程執(zhí)行和同步點。共享存儲器系統(tǒng)有兩種主要的同步構(gòu)造：鎖和障柵已亥。圖（a）中熊赖，使用鎖的3個進程保證互斥。P2等待P1解鎖臨界區(qū)虑椎，P3等待P2解鎖震鹉。圖（b）中，P3和P1到達障柵語句捆姜，但必須等待P2到達传趾。當所有進程到達障柵時，它們可以繼續(xù)執(zhí)行泥技。

• 4.7 小結(jié)

共享存儲器系統(tǒng)由處理器和存儲器組成浆兰，處理器通過讀寫存儲器進行通信和同步。系統(tǒng)面臨爭用和高速緩存一致性挑戰(zhàn)珊豹，通過本地高速緩存緩解瓶頸簸呈。高速緩存一致性方案有監(jiān)聽協(xié)議和基于目錄的協(xié)議。分布式共享存儲器體系結(jié)構(gòu)興起店茶，硬件采用消息傳遞設(shè)計蜕便，編程模型采用共享存儲器思想。對程序員而言贩幻，體系結(jié)構(gòu)表現(xiàn)為共享存儲器機器轿腺，實際上包含消息傳遞體系結(jié)構(gòu)。

第5章 消息傳遞體系結(jié)構(gòu)

消息傳遞系統(tǒng)用于多處理器間通信和數(shù)據(jù)移動丛楚。每個結(jié)點有處理器和本地存儲器族壳，通過互連網(wǎng)絡(luò)進行通信。數(shù)據(jù)通過消息傳遞在結(jié)點之間移動趣些。程序員使用發(fā)送/接收指令編寫應(yīng)用軟件仿荆。消息傳遞系統(tǒng)逐漸被互聯(lián)網(wǎng)系統(tǒng)取代。本章討論編程模型、消息路由赖歌、網(wǎng)絡(luò)交換枉圃、支持消息傳遞的處理器和實例。

• 5.1 消息傳遞簡介

消息傳遞體系結(jié)構(gòu)用于處理器間的數(shù)據(jù)通信庐冯，不需要全局存儲器孽亲。每個處理器有本地存儲器，通過消息傳遞與其他處理器通信展父。這種模式消除了對大型全局存儲器和同步的需求，比共享存儲器模式更高級。消息傳遞體系結(jié)構(gòu)主要包括處理器P和本地存儲器M的多個結(jié)點N，通過外部通道和互連網(wǎng)絡(luò)進行通信怎诫。鏈路帶寬和網(wǎng)絡(luò)時延是設(shè)計互連網(wǎng)絡(luò)時必須考慮的重要因素玄窝。

應(yīng)用程序分成多個并發(fā)進程镊逝，在不同處理器上執(zhí)行升略，并使用內(nèi)部通道或外部通道進行消息交換压固。消息傳遞的優(yōu)點包括無需同步以及靈活可擴展的處理器容納能力靠闭。進程粒度描述了進程的計算時間與通信時間之比帐我，可以是粗粒度、中粒度或細粒度愧膀。消息傳遞多處理器主要使用中粒度或粗粒度拦键。

• 5.2 消息傳遞網(wǎng)絡(luò)中的路由

廣播和多播的路由
路由是選擇消息路徑的技術(shù)。路由識別目標路徑并選擇一條合適路徑檩淋。自適應(yīng)路由依賴網(wǎng)絡(luò)環(huán)境芬为，確定路由只考慮源和目的。集中式路由在發(fā)送前確定路徑蟀悦，分布式由節(jié)點決定矮烹。確定路由效率低下妆绞，而自適應(yīng)路由能根據(jù)網(wǎng)絡(luò)狀態(tài)選擇路徑。例如e-cube、維序路由熬的。
通信操作有單播和集合通信销睁。單播是一對一通信粒梦，集合通信定義了廣播和多播土童。廣播是發(fā)送相同消息給所有結(jié)點，多播是發(fā)送消息給多個目的地弯屈。廣播用于分布式存儲器程序蜗帜，多播用于多處理機系統(tǒng)。實用的廣播和多播路由算法應(yīng)無死鎖资厉，以最短路徑傳遞消息厅缺。一種實現(xiàn)是在路徑上復(fù)制消息，分支直到達目的結(jié)點宴偿。另一種方法是單獨尋址湘捎，但效率較低。
路由的潛在問題
消息傳遞系統(tǒng)中的路由機制可能導致死鎖酪我、活鎖和機餓消痛。死鎖發(fā)生在兩個消息相互占用資源并相互阻塞的情況下，解決方法可以是重新路由消息或丟棄消息都哭。避免死鎖的方法是通過資源排序和嚴格順序請求資源的方式防止循環(huán)等待。活鎖指消息在網(wǎng)絡(luò)中傳遞卻無法到達目的地欺矫，解決方法可以是根據(jù)優(yōu)先級路由消息并限制同時注入的消息數(shù)量纱新。機餓意味著某個結(jié)點的消息被禁止注入到網(wǎng)絡(luò)，可以通過允許結(jié)點維護自己的消息隊列并使用公平隊列管理策略來避免機餓穆趴。

• 5.3 消息傳遞中的交換機制

交換機制確定數(shù)據(jù)從輸入通道移出放入輸出通道脸爱。時延取決于交換機制，如存儲轉(zhuǎn)發(fā)未妹、電路交換簿废、虛擬直通、蟲孔和流水線交換络它。電路交換靜態(tài)分配帶寬族檬，無緩沖，最小總延遲化戳。存儲-轉(zhuǎn)發(fā)靈活動態(tài)帶寬分配单料，包括包交換和虛擬直通。包交換劃分為包傳輸点楼，端到端組裝扫尖，減少緩沖。虛擬直通存儲包掠廓，忙時發(fā)送换怖，避免延遲。蟲孔路由使用小緩沖蟀瞧，在不受路徑長度影響下產(chǎn)生時延狰域，存儲空間較少。下圖展示了存儲轉(zhuǎn)發(fā)和蟲孔路由性能黄橘。

網(wǎng)格網(wǎng)絡(luò)中的蟲孔路由
Meah是n維網(wǎng)格兆览，有Ko×K1×…×K-1個結(jié)點。每個結(jié)點用n維坐標向量標識塞关。路由技術(shù)包括維序抬探、維逆序、轉(zhuǎn)向和消息流模型帆赢。在二維網(wǎng)格中小压，即X-Y路由，包先按X維發(fā)送椰于，再按Y維發(fā)送怠益。通過前兩個片中的坐標實現(xiàn)路由。根據(jù)正負進行增減量瘾婿，到達Y維后判斷結(jié)果決定下一步操作蜻牢。下圖展示了8x8網(wǎng)格中的X-Y路由烤咧。

虛擬通道
虛擬通道用于設(shè)計無死鎖的路由算法，提供了低成本增加邏輯通道數(shù)量的方法抢呆，無需增加更多線路煮嫌。虛擬通道允許阻塞的消息通過，提高吞吐量抱虐，并增加資源分配自由度昌阿。通過將物理鏈路劃分為單向虛擬通道，實現(xiàn)多路復(fù)用和數(shù)據(jù)引導恳邀。虛擬通道避免死鎖懦冰，每個節(jié)點分配緩沖區(qū)，收到的數(shù)據(jù)放入緩沖區(qū)并在適當時間發(fā)送谣沸。

• 5.4 消息傳遞編程模型

消息傳遞體系結(jié)構(gòu)使用send刷钢、receive、broadcast和barrier等原語實現(xiàn)進程間通信鳄抒。發(fā)送進程使用send原語將緩沖內(nèi)容發(fā)送到目標節(jié)點闯捎，接收進程使用receive原語接收來自源節(jié)點的消息并存儲到指定緩沖區(qū)。發(fā)送和接收是阻塞的许溅，需要使用三階段協(xié)議瓤鼻，導致通信時延增加且無法充分利用帶寬。為避免此缺點贤重，許多實現(xiàn)采用非阻塞操作茬祷，將消息緩沖在消息層直到網(wǎng)絡(luò)端口可用，并在接收方緩沖直到匹配接收執(zhí)行并蝗。不同消息傳遞機器性能有所差異祭犯，考慮到消息啟動代價(T)、每字節(jié)代價(T)和每浮點操作平均代價(T)等指標滚停。

• 5.5 支持消息傳遞的處理器

消息傳遞處理器支持進程間通信沃粗，使用端口進行發(fā)送和接收操作。消息由頭和體組成键畴，端口集合指定權(quán)限最盅。IPAX432處理器使用條件操作實現(xiàn)非阻塞消息傳遞。還有非阻塞操作如代理發(fā)送和接收起惕。AS/400處理器使用事件對象類型支持消息傳遞涡贱，包含事件數(shù)據(jù)字段。發(fā)送通過處理器操作SIGNAL-EVENT惹想，接收使用WAIT-ON-EVENT等操作问词。注意，接收操作沒有真正的阻塞嘀粱，超時由每個進程執(zhí)行的操作決定激挪。

• 5.6 消息傳遞體系結(jié)構(gòu)實例

實例有CaltochHperube辰狡、IrsTtansputersyslems、MeikoCS-2等灌灾，這些系統(tǒng)支持并行計算和消息傳遞搓译，具有不同的架構(gòu)和特性悲柱。其中锋喜，CaltechHypereube和CoemicCube是基于超立方體的系統(tǒng)，而CS-1則是基于IaTnpuerT00的系統(tǒng)豌鸡。IPSC/I和PSCI使用286處理器和NXI軟件環(huán)境嘿般。HCUBE/2采用20MHz處理器互連超立方體。CM-5是分布式存儲器消息傳遞系統(tǒng)涯冠，基于SPARC處理器炉奴。最新的系統(tǒng)是IBM Scalable POWERparallel3。
IBM Scalable POWERparallel3：IBM POWER3 (SP3) 是IBM超級計算機（1999/2000）系列蛇更。SP3由2到512個POWER3處理器節(jié)點組成瞻赶，每個節(jié)點有私有存儲和AI操作系統(tǒng)副本。POWER3是8級流水線處理器派任，每個周期執(zhí)行兩條指令砸逊，乘法需2周期，除法需13-17周期掌逛。FPU包含兩個雙精度浮點執(zhí)行部件师逸，遵循IEEE754標準。節(jié)點通過高性能包交換網(wǎng)絡(luò)互連豆混，采用消息傳遞編程模型篓像，支持PVM、MPL和MPI庫皿伺。通信協(xié)議支持異步/阻塞的發(fā)送和接收操作员辩。

• 5.7 消息傳遞體系結(jié)構(gòu)與共享存儲器體系結(jié)構(gòu)

共享存儲器和消息傳遞是并行計算中常見的通信模型。共享存儲器適合應(yīng)用編寫者鸵鸥，提供隱式的地址空間共享和分離的同步和通信機制奠滑。消息傳遞適合操作系統(tǒng)設(shè)計者，使用顯式的進程間消息交互和統(tǒng)一的同步機制脂男。雖然兩種模型可互相模擬养叛，但消息傳遞更容易模擬共享存儲器。共享存儲器簡化了程序員對通信細節(jié)的考慮宰翅，擴展了單處理器編程模式弃甥。然而共享存儲器需要輪詢接口和完整的往返路由，而消息傳遞使用中斷驅(qū)動的通信模型汁讼。兩種模型各有適用領(lǐng)域淆攻，而類似FLASH系統(tǒng)則綜合二者的優(yōu)勢阔墩，實現(xiàn)高效的多處理機通信。

第6章 抽象模型

并行計算可以分為共享存儲器系統(tǒng)和消息傳遞系統(tǒng)瓶珊。本章將學習共享存儲器和消息傳遞的抽象模型啸箫，并研究并評估并行算法。抽象模型是理想化的伞芹，但在研究算法的性能和復(fù)雜性時非常有用忘苛。我們從PRAM共享存儲器系統(tǒng)模型開始，討論其與消息傳遞系統(tǒng)的關(guān)系唱较，并提供同步消息傳遞模型扎唾。通過這些模型，我們將討論算法的復(fù)雜性南缓，并對這兩種模型的算法進行評估胸遇。

• 6.1 PRAM模型及其變體

并行計算理論模型描述和分析算法的框架，用于性能限制和復(fù)雜性估計汉形。PRAM模型是常用模型之一纸镊，抽象化并行計算機，忽略通信成本和同步開銷概疆。PRAM由控制器逗威、p個處理器和共享全局存儲器組成，每個處理器有私有存儲器届案。

處理器在同步的讀庵楷、計算、寫周期操作楣颠，執(zhí)行相同指令尽纽，稱為共享存儲器的單指令多數(shù)據(jù)機器。PRAM保證對共享存儲器中數(shù)據(jù)的原子訪問童漩。PRAM中讀寫操作有不同模式弄贿，如互斥讀、互斤寫矫膨、并發(fā)讀和并發(fā)寫差凹。根據(jù)不同模式，PRAM可分為EREW侧馅、ERCW危尿、CREW、CRCW等子類型馁痴。

• 6.2 在EREWPRAM上模擬多個訪問

EREWPRAM是最嚴格的4種子類型之一谊娇，只允許單個處理器讀寫給定存儲器單元。為該模型設(shè)計的算法不能依賴并發(fā)訪問相同存儲器單元以提高性能罗晕。EREWPRAM算法可在CRCWPRAM上運行济欢，只需避免使用并發(fā)訪問特性赠堵。反之不成立》ㄈ欤可以在EREW模型中模擬并發(fā)讀寫操作茫叭，但需花費時間和更多存儲器。廣播機制可實現(xiàn)處理器對存儲器單元x的并發(fā)讀取半等。用大小為p的數(shù)組L作為共享存儲器揍愁，實現(xiàn)處理器間發(fā)布x的內(nèi)容。下圖展示了當p=8時的Broadcast_EREW算法酱鸭。

• 6.3 并行算法的分析

并行算法的復(fù)雜性主要由時間和空間復(fù)雜性決定吗垮。時間復(fù)雜性以問題大小為基礎(chǔ)垛吗，空間復(fù)雜性表示所需存儲器空間凹髓。時間復(fù)雜性是衡量算法性能的重要指標。并行算法中怯屉，性能取決于運行時間和處理器數(shù)量锨络。成本是運行時間乘以處理器數(shù)量。成本最優(yōu)的并行算法與串行算法最低復(fù)雜度匹配。增加處理器數(shù)量可能加速成本最優(yōu)PRAM算法恍风，但需謹慎以避免增加成本颠黎。設(shè)計有效并行算法時，需考慮問題大小限制處理器數(shù)量滞项、運行時間明顯小于串行算法狭归、成本最優(yōu)化。
NC類和P完全：在算法理論中蓖扑，有不同類別的問題唉铜，如P類（多項式時間可解）、NP類（多項式時間可驗證）律杠、NP-困難類（與NP問題一樣難）和NP-完全類（難以計算解決）潭流。在并行計算中，我們有NC類（可充分并行解決）與P類的關(guān)系未解柜去。P完全類是那些與P問題一樣難以并行解決的問題灰嫉。這些類別涵蓋了組合數(shù)學、圖論和計算機科學中的許多經(jīng)典問題嗓奢。在未解決的問題中讼撒，我們探討了PCNP與NCCP的關(guān)系。P完全問題包括深度優(yōu)先搜索、最大流和回路值問題根盒。這些類別之間的關(guān)系如圖示钳幅。

• 6.4 計算和與所有和

EREW模型上數(shù)字數(shù)組的求和
PRAM算法用并行化和二叉樹總和，在O(log n)時間和O(n log n)成本內(nèi)計算數(shù)字數(shù)組的部分和炎滞。該算法使用n/2個處理器敢艰，將數(shù)組數(shù)字分布在二叉樹葉子節(jié)點上，并逐層計算總和册赛。運行時間O(log n)钠导，處理器數(shù)量n/2，成本O(n log n)森瘪。

數(shù)組的所有部分和
使用AlISuns_EREW算法在n-1個處理器的EREWPRAM上計算數(shù)組的所有部分和牡属。運行時間O(log n)，處理器數(shù)量n-1扼睬，成本O(n log n)逮栅。算法利用空閑處理器提高效率。

• 6.5 矩陣乘法

使用n^3個處理器
研究并行矩陣乘法痰驱，提出兩個nxn矩陣相乘的算法证芭。運行時間O(log n)，處理器數(shù)量n2担映，成本O(n2log n)势篡。優(yōu)化算法需減少處理器數(shù)量以降低成本朽缴。

減少處理器的數(shù)量
優(yōu)化算法：在改進的MatMulCREW算法中，每個處理器計算lgn個乘積和樊卓。然后將這些乘積和相加矗蕊。使用n2/lgn個處理器短蜕，算法的運行時間為O(log n)，處理器數(shù)量為n2/lgn傻咖，成本為O(n2)朋魔。這種優(yōu)化方法能夠降低處理器數(shù)量并提高運行效率。

• 6.6 排序

這基于枚舉思想的排序算法通過計算比每個元素小的元素的個數(shù)來確定排序順序卿操。使用n2個處理器的CRCWPRAM模型警检，兩個步驟實現(xiàn)排序：1. 每行的處理器計算元素的小于它的個數(shù)。2. 每行第一個處理器將元素放入排序列表的適當位置害淤。該算法的復(fù)雜性指標：1. 運行時間T(n) = O(1)扇雕，2. 處理器數(shù)量P(n) = n2，3. 成本C(n) = O(n2)窥摄。盡管該算法在常數(shù)時間內(nèi)完成排序镶奉，但使用了大量處理器，且基于強大的CRCWPRAM模型，不是最優(yōu)解哨苛。

• 6.7 消息傳遞模型

同步消息傳遞模型
消息傳遞系統(tǒng)算法由本地程序組成鸽凶，分布于分布式系統(tǒng)的處理單元上。程序執(zhí)行計算和消息傳遞建峭。通信圖用于建模吱瘩，節(jié)點表示處理器，邊表示通信鏈路迹缀。同步模式下使碾，本地程序在同步回合處理。異步模式?jīng)]有嚴格的同步祝懂，程序按任意順序和速率執(zhí)行票摇。部分同步系統(tǒng)在定時事件上限制執(zhí)行。本節(jié)主要研究同步消息傳遞系統(tǒng)砚蓬，使用形式化模型描述矢门。算法復(fù)雜性分析包括時間和消息復(fù)雜性灰蛙。
給定n個進程的消息傳遞系統(tǒng)，每個進程在獨立處理器上運行。系統(tǒng)初始化并以任意初始狀態(tài)開始。每個進程以同步回合方式執(zhí)行消息生成和狀態(tài)轉(zhuǎn)換函數(shù)煌茴，發(fā)送和接收消息來改變系統(tǒng)狀態(tài)纪蜒。系統(tǒng)基于進程間的消息改變當前狀態(tài)躏敢。系統(tǒng)模型包括狀態(tài)機描述：初始狀態(tài)遭居、狀態(tài)集合啼器、消息字母表、消息生成函數(shù)和狀態(tài)轉(zhuǎn)換函數(shù)俱萍。該同步系統(tǒng)可使用模板STemplate描述并研究算法端壳。

復(fù)雜性分析
復(fù)雜性分析量化算法所需資源總量。在消息傳遞系統(tǒng)中枪蘑，時間復(fù)雜性表示算法執(zhí)行時間损谦，消息復(fù)雜性表示發(fā)送的消息數(shù)量岖免。復(fù)雜性通常以系統(tǒng)節(jié)點和邊數(shù)量的函數(shù)形式表示。例如成翩，超立方體算法的復(fù)雜性為O(log n)的時間復(fù)雜性和O(n log n)的消息復(fù)雜性觅捆。

• 6.8 領(lǐng)導者選舉問題

分布式系統(tǒng)中選舉領(lǐng)導者問題：n個處理器，一個必須成為領(lǐng)導者麻敌。每個處理器只知道自己的標識栅炒，最終要決定是否成為領(lǐng)導者。領(lǐng)導者負責協(xié)調(diào)分配术羔、路由等任務(wù)赢赊。在令牌網(wǎng)中，領(lǐng)導者處理丟失令牌問題级历。領(lǐng)導者問題在相同進程的名系統(tǒng)中無意義释移。定理6.1：名環(huán)中不存在領(lǐng)導者選舉算法。多種算法思想：廣播標識符給其他結(jié)點寥殖，最高標識符的結(jié)點成為領(lǐng)導者玩讳。復(fù)雜性取決于節(jié)點數(shù)和邊數(shù)，可以優(yōu)化消息數(shù)量嚼贡。同步模型下熏纯，一個回合完成標識符交換，最高標識符者成為領(lǐng)導者粤策。復(fù)雜性可優(yōu)化樟澜，節(jié)點逐層發(fā)送標識符給鄰居。

• 6.9 同步環(huán)中的領(lǐng)導者選舉

簡單領(lǐng)導者選舉算法
簡單選舉領(lǐng)導者算法：沿環(huán)發(fā)送標識符叮盘，收到自身標識的成為領(lǐng)導者秩贰。復(fù)雜性：時間0(n)，消息0(n2)柔吼。
改進的領(lǐng)導者選舉算法
為了減小消息復(fù)雜性毒费，進程不需要沿著環(huán)發(fā)送自身ID，只需將消息發(fā)送給一定距離的鄰居愈魏，距離逐步增加蝗罗。這思想由Hirschberg和Sinclair（1980）提出。假設(shè)通信雙向蝌戒，環(huán)大小未知，每處理器標識唯一沼琉。算法如下：1.每進程雙向發(fā)送標識消息到鄰居北苟，間隔2倍跳躍，然后返回原位置打瘪。2.若標識在外環(huán)行進友鼻，進程根據(jù)收到的標識比較發(fā)送給輸出鄰居傻昙。3.若標識在內(nèi)環(huán)行進，若收到標識較大彩扔，發(fā)送給路徑上輸出鄰居妆档。4.若兩消息回到原位，k增加1虫碉，重復(fù)步驟2贾惦。復(fù)雜性：運行時間O(n)，消息復(fù)雜性O(shè)(n lg n)敦捧。

第7章 網(wǎng)絡(luò)計算

因特網(wǎng)的增長推動了全球大規(guī)模網(wǎng)絡(luò)計算的發(fā)展须板。因特網(wǎng)是目前范圍最廣的分布式系統(tǒng)，結(jié)點可以是不同類型的系統(tǒng)兢卵。鏈路是TCP/IP包交換的連接习瑰，帶寬受負載、跳數(shù)和通信技術(shù)影響秽荤。網(wǎng)絡(luò)計算利用不同系統(tǒng)的能力甜奄，將應(yīng)用劃分為多個部分分配給不同結(jié)點。此外窃款，網(wǎng)絡(luò)技術(shù)可用于構(gòu)建商用計算基礎(chǔ)設(shè)施课兄，最大化利用空閑資源。

• 7.1 計算機網(wǎng)絡(luò)基礎(chǔ)

網(wǎng)絡(luò)性能
網(wǎng)絡(luò)可分為廣域網(wǎng)(WAN)雁乡、城域網(wǎng)(MAN)第喳、局域網(wǎng)(LAN)和系統(tǒng)/存儲區(qū)域網(wǎng)(SAN)。廣域網(wǎng)連接大量計算機踱稍，覆蓋大范圍曲饱；局域網(wǎng)連接少量計算機，覆蓋小范圍珠月；城域網(wǎng)介于兩者之間扩淀；SAN連接計算機或存儲設(shè)備。Gilder定律表示通信系統(tǒng)帶寬每12個月增加2倍啤挎，Metcalfe定律說明網(wǎng)絡(luò)價值與結(jié)點數(shù)量的平方成正比驻谆。這些規(guī)律解釋了網(wǎng)絡(luò)增長和性能限制。
因特網(wǎng)
因特網(wǎng)是全球覆蓋的協(xié)同虛擬網(wǎng)絡(luò)庆聘，基于TCP/IP協(xié)議胜臊。它推動了電子出版、瀏覽和分布式計算的快速發(fā)展伙判。用戶數(shù)量持續(xù)增加象对。

其他網(wǎng)絡(luò)技術(shù)
除了TCP/IP協(xié)議外，還有其他協(xié)議和協(xié)議集合宴抚，如以太網(wǎng)勒魔、FDDI甫煞、HIPPI、ATM和SCI冠绢。它們提供了不同的網(wǎng)絡(luò)技術(shù)和速度抚吠。以太網(wǎng)有快速以太網(wǎng)和千兆以太網(wǎng)，F(xiàn)DDI使用光纖電纜傳輸數(shù)據(jù)弟胀，HIPPI是點對點通信通道楷力，ATM適用于局域網(wǎng)和廣域網(wǎng)，SCI提供了機群范圍的共享存儲器系統(tǒng)邮利。

• 7.2 客戶/服務(wù)器系統(tǒng)

客戶/服務(wù)器是分布式系統(tǒng)的一種形式弥雹，將應(yīng)用劃分為客戶和服務(wù)器⊙咏欤客戶通過網(wǎng)絡(luò)連接到服務(wù)器剪勿，執(zhí)行特定任務(wù)。這種架構(gòu)可以是2層或3層的》酵ィ現(xiàn)代編程語言提供了開發(fā)基于客戶/服務(wù)器的分布式系統(tǒng)的基礎(chǔ)厕吉。在傳統(tǒng)的客戶/服務(wù)器環(huán)境中，處理能力強的機器充當服務(wù)器械念，為多個客戶提供服務(wù)头朱。多線程的進程是一種有效的服務(wù)器應(yīng)用方法。
套接字：套接字連接應(yīng)用程序使不同機器間能互相通信龄减。創(chuàng)建套接字可等待連接（被動）或主動初始化連接（主動）项钮。客戶端創(chuàng)建套接字實例主動連接遠程服務(wù)器希停。服務(wù)器套接字實例綁定端口等待客戶連接烁巫。連接建立后，客戶與服務(wù)器可通過輸入輸出流讀寫套接字宠能。
Java中使用Socket類創(chuàng)建客戶端套接字亚隙，ServerSocket類創(chuàng)建服務(wù)器套接字。使用DataInputStream和DataOutputStream類讀寫套接字违崇“⑵客戶：連接服務(wù)器并接收字符串顯示。服務(wù)器：等待連接羞延，發(fā)送字符串渣淳，關(guān)閉連接。
遠程過程調(diào)用：RPC簡化了遠程過程調(diào)用的復(fù)雜性伴箩，實現(xiàn)跨計算機的過程調(diào)用水由，參數(shù)通過網(wǎng)絡(luò)傳遞，返回結(jié)果繼續(xù)執(zhí)行。RPC可阻塞或非阻塞砂客，后者需顯式詢問回復(fù)。
中間件：中間件簡化客戶/服務(wù)器系統(tǒng)的互操作性呵恢，整合新舊系統(tǒng)鞠值，解決互操作問題，隔離組件渗钉，降低開發(fā)成本彤恶，無需了解網(wǎng)絡(luò)和分布式編程細節(jié)。
并行應(yīng)用的客戶/服務(wù)器框架：并行應(yīng)用使用客戶/服務(wù)器模型鳄橘，將大應(yīng)用劃分成小問題声离，由多個服務(wù)器同時處理。服務(wù)器計算結(jié)果發(fā)送給客戶瘫怜，客戶組合結(jié)果輸出給用戶术徊。客戶創(chuàng)建套接字數(shù)組和數(shù)據(jù)流與服務(wù)器連接鲸湃≡蹋客戶主體劃分任務(wù)給服務(wù)器，并等待結(jié)果返回暗挑。服務(wù)器創(chuàng)建套接字笋除、等待連接，并調(diào)用服務(wù)器主體線程處理客戶炸裆。

• 7.3 機群

20世紀90年代垃它，從專用并行機轉(zhuǎn)向經(jīng)濟高效的PC和工作站機群。機群是獨立計算機集合烹看，提供經(jīng)濟高性能計算国拇。機群可同構(gòu)或異構(gòu)，互連網(wǎng)絡(luò)需高帶寬低時延通信听系。專用機群放在單獨房間贝奇，節(jié)點除前端外無鍵鼠顯示器。機群實現(xiàn)高可用性環(huán)境靠胜，中間件支持錯誤恢復(fù)掉瞳。統(tǒng)一訪問屬性包括入口點、文件系統(tǒng)浪漠、系統(tǒng)管理映像、協(xié)同資源管理址愿。編程環(huán)境提供開發(fā)并行程序的工具和庫，如線程响谓、PVM和MPI损合。

線程：現(xiàn)代操作系統(tǒng)支持進程內(nèi)線程省艳，它們是處理器的基本執(zhí)行單元。線程可以被中斷和切換嫁审，使處理器能夠執(zhí)行其他線程跋炕。一個進程可以包含多個線程，線程是輕量級的律适，與重量級進程不同辐烂。線程之間的上下文切換較為容易，不同進程的線程可以并發(fā)執(zhí)行捂贿，并且相同進程的多個線程可以在不同處理器上運行纠修。線程可以用于發(fā)送和接收消息，同時進行其他任務(wù)操作厂僧。例如扣草，一個任務(wù)可能有多個線程等待接收和處理請求消息，在處理消息的同時吁系，其他線程可以并發(fā)地處理其他消息德召。Java語言內(nèi)置對多線程的支持，能夠映射到底層操作系統(tǒng)的線程汽纤，使使用Java編寫的應(yīng)用程序能夠在多處理器環(huán)境中并行執(zhí)行上岗。

• 7.4 互連網(wǎng)絡(luò)

機群性能取決于處理器和互連網(wǎng)絡(luò)速度。帶寬決定傳輸速度蕴坪，時延是傳輸消息的時間肴掷。以太網(wǎng)是早期的互連網(wǎng)絡(luò)，其他高速網(wǎng)絡(luò)提供更好的性能背传。

以太網(wǎng)：以太網(wǎng)是局域網(wǎng)技術(shù)呆瞻，多臺主機共享總線，采用CSMA/CD訪問控制径玖。速度從10Mbps發(fā)展到100Mbps和1Gbps痴脾。每臺主機有唯一48位以太網(wǎng)地址。主機根據(jù)目的地址傳輸數(shù)據(jù)包梳星。配置需平衡以太網(wǎng)速度和處理器速度赞赖。建議高性能機群使用16臺200MHz處理器連接到快速以太網(wǎng)。配置取決于規(guī)模冤灾、處理器速度和網(wǎng)絡(luò)帶寬關(guān)系及價格表前域。
交換機：一個nxn交換機由n個輸入端口、n個輸出端口韵吨、鏈路匿垄、控制邏輯和緩沖器組成。交換機用于建立輸入端口到輸出端口的連接，可以是一對一或一對多椿疗。允許多對一連接時需要仲裁解決沖突漏峰。交叉開關(guān)可以建立n!個一對一連接。路由可采用源路徑或基于表的方式变丧，前者將完整路徑存儲在包頭芽狗，后者使用路由表選擇輸出端口。
MyrinetClos網(wǎng)絡(luò)：Myrinet是高性能的交換式包通信技術(shù)痒蓬，可替代以太網(wǎng)。交換機有多個端口，包通過輸入通道進入端口，并路由到輸出通道選擇的端口校镐。交換機可有4序芦、8、12挂疆、16個端口。使用交叉開關(guān)和接口芯片實現(xiàn)，能建立不同大小和拓撲的網(wǎng)絡(luò)给梅，如Clos網(wǎng)絡(luò)。主機之間有最短路由双揪。Myrinet包的路由采用源路徑方法动羽，包含完整的路由信息，通過控制程序在交換機進行源路由轉(zhuǎn)換渔期。
Quadrics網(wǎng)絡(luò)：Qualrics由Elan網(wǎng)絡(luò)接口和Elite通信交換機組成运吓。Elan連接處理節(jié)點，提供本地處理和消息傳遞協(xié)議支持疯趟。QNet使用四元胖樹拓撲連接Elite交換機拘哨，采用源路由和蟲孔路由流控制。Elite附加路由信息到包頭信峻，并遞歸轉(zhuǎn)發(fā)到目的地倦青。網(wǎng)絡(luò)節(jié)點可使用廣播發(fā)送包到多個目的地。

• 7.5 機群實例

加州大學伯克利分校的工作站網(wǎng)絡(luò)：加州大學伯克利分校的工作站網(wǎng)絡(luò)（NOW）是機群系統(tǒng)的重要代表盹舞，使用Myrinet交換機網(wǎng)絡(luò)連接产镐。編程環(huán)境包括套接字、MPI和SplinC并行版本C語言矾策。主動消息是NOW的基本通信原語磷账。

Beowulf 機群：Beowulf機群項目利用商用機器實現(xiàn)超級計算機處理能力。通過以太網(wǎng)連接處理器贾虽，通信使用TCP/IP協(xié)議逃糟。Loki和Avalon是成功的機群，分別具有高能奔騰處理器和Alpha微處理器，速度分別達到1.2Gflops和47.7Gops绰咽。
FlashMob1：日金山大學2004年創(chuàng)建FlashMobI臨時計算機菇肃，連接700臺計算機，目標是構(gòu)建最快超級計算機取募。最佳Linpack值為180Gflops琐谤，最佳完成結(jié)果為77Gflops，遇到的挑戰(zhàn)在于識別計算機連接和最佳配置玩敏。

• 7.6 網(wǎng)格計算

機群由多臺計算機構(gòu)成斗忌，表現(xiàn)為單個系統(tǒng)；網(wǎng)格由多個系統(tǒng)組成旺聚，保持自主性织阳。網(wǎng)格中間件較機群復(fù)雜，用于連接分布和異構(gòu)的計算資源砰粹。全球網(wǎng)格資源包括硬件唧躲、軟件、數(shù)據(jù)和儀器碱璃，支持復(fù)雜應(yīng)用和協(xié)作弄痹。虛擬組織提供統(tǒng)一資源視圖，實現(xiàn)資源共享嵌器。網(wǎng)格挑戰(zhàn)在于共享資源同時保持自治性肛真，需解決資源管理、安全嘴秸、通信毁欣、性能等問題。Globus和TeraGrid是網(wǎng)格工具岳掐，支持資源共享和管理凭疮。TeraGrid旨在構(gòu)建全球最大、最快的分布式基礎(chǔ)設(shè)施串述，支持科學研究执解。

第8章 并行虛擬機的并行編程

PVM是并行虛擬機，由Oak Ridge國家實驗室和田納西大學開發(fā)纲酗。它使得在網(wǎng)絡(luò)連接的異構(gòu)計算機上開發(fā)應(yīng)用程序成為可能衰腌，以單一的并行計算機形式呈現(xiàn)給用戶。PVM提供進程控制和資源管理功能觅赊，通過消息傳遞實現(xiàn)通信右蕊，在不同計算機間具有互操作性。一個PVM應(yīng)用由任務(wù)組成吮螺，共同解決問題饶囚，通過消息交換進行通信帕翻。

• 8.1 PVM環(huán)境和應(yīng)用結(jié)構(gòu)

管理者-工作者結(jié)構(gòu)
PVM中的結(jié)構(gòu)包括管理者和工作者，管理者負責初始化和與用戶交互萝风，工作者獨立執(zhí)行計算任務(wù)并將結(jié)果返回給管理者嘀掸。工作者可以相互通信。例如规惰，使用管理者-工作者結(jié)構(gòu)對數(shù)組排序睬塌，工作者獨立排序子數(shù)組，最終由管理者合并結(jié)果歇万。
層次結(jié)構(gòu)
層次結(jié)構(gòu)允許工作者創(chuàng)建新工作者層次揩晴，如數(shù)組排序。頂層管理者創(chuàng)建工作者贪磺，它們創(chuàng)建下一層工作者文狱，以此類推。葉子工作者獨立排序子數(shù)組缘挽，并將結(jié)果返回給父級工作者。最終呻粹，頂層管理者合并排序結(jié)果壕曼。這個過程適用于分而治之的應(yīng)用。

• 8.2 創(chuàng)建任務(wù)

PVM中的任務(wù)手動創(chuàng)建或派生等浊。初始化任務(wù)手動激活腮郊，用pvm_spawn()創(chuàng)建子任務(wù)，指定機器筹燕、路徑轧飞、數(shù)量和參數(shù)。任務(wù)標識(TID)區(qū)分發(fā)送和接收撒踪，給任務(wù)分配功能过咬。
任務(wù)標識符的獲取
并行虛擬機提供函數(shù)獲取TID，標記任務(wù)及其父任務(wù)及其他任務(wù)制妄。通過pvmmytid()獲取自身TID掸绞，pvmspawn()返回創(chuàng)建子任務(wù)的TIDs數(shù)組。pvmparent()獲取父任務(wù)TID耕捞，沒有則返回PvmNoParent衔掸。通過pvm_tidtohost()確定任務(wù)運行在哪臺主機上。
動態(tài)任務(wù)創(chuàng)建
pvm_spawn()函數(shù)用于在同一機器或不同機器上創(chuàng)建任務(wù)俺抽。參數(shù)包括可執(zhí)行文件名敞映、參數(shù)、派生目標磷斧、機器名或體系結(jié)構(gòu)類型振愿、任務(wù)數(shù)量和返回TIDs的數(shù)組捷犹。參數(shù)Flag控制派生操作的目標。派生命令需確卑Ｒ撸可執(zhí)行文件存在于目標機器上伏恐。

例子中在homer和femmi上創(chuàng)建2份和4份"worker"程序的副本，通過&tid1和&tid2返回任務(wù)的TID栓霜，n1和n2表示實際創(chuàng)建的任務(wù)數(shù)量翠桦。

• 8.3 任務(wù)組

PVM允許任務(wù)隸屬于命名組并變更隸屬關(guān)系，組可用于集合操作胳蛮。例如销凑，廣播操作通過命名組向所有任務(wù)發(fā)送消息。任務(wù)可隨時加入或離開組仅炊，無需通知斗幼。通過pvmjoingroup()將任務(wù)加入組，返回實例號抚垄。組在首次調(diào)用pvmjoingroup()時創(chuàng)建蜕窿，實例號從0開始遞增。實例號可能有間隙呆馁，因為任務(wù)離開組桐经。新成員加入有間隙的組時，獲得最小可用實例號浙滤。程序員需維護無間隙實例號集合阴挣。通過pvmlvgroup()使任務(wù)離開組，返回信息或負值纺腊。重新加入組將獲得不同實例號畔咧。其他函數(shù)如pvmgsize()獲取組大小，pvmgettid()根據(jù)實例號和組名獲取任務(wù)的TID揖膜，pvmgetinst()根據(jù)TID和隸屬組名獲取實例號誓沸。

• 8.4 任務(wù)間的通信

PVM使用消息傳遞實現(xiàn)任務(wù)通信，采用例程庫和守護進程次氨。通過發(fā)送和接收異步消息進行通信蔽介，守護進程決定消息目的地。發(fā)送任務(wù)可以發(fā)送消息給多個接收者煮寡，接收任務(wù)在阻塞或非阻塞情況下接收消息虹蓄。控制線程在守護進程短暫阻塞幸撕。發(fā)送命令發(fā)送消息給守護進程薇组，守護進程將消息傳送至物理鏈接。接收命令以阻塞或非阻塞方式等待消息坐儿。一條完整消息經(jīng)初始化律胀、打包和解包過程到達目的地宋光。

消息緩沖區(qū)：PVM提供兩個創(chuàng)建緩沖區(qū)的函數(shù)：pvminitsend()和pvmmkbuf()，它們用于裝配發(fā)送消息之前的數(shù)據(jù)炭菌。緩沖區(qū)創(chuàng)建時有三種編碼選項罪佳，其中默認為XDR編碼，適用于不同機器間無法讀取原始格式的消息發(fā)送黑低。第二種選項跳過編碼步驟赘艳，直接發(fā)送原始格式的消息。第三種選項是直接從用戶存儲空間復(fù)制數(shù)據(jù)克握，節(jié)省時間但要求在發(fā)送前不修改數(shù)據(jù)蕾管。若只使用一個發(fā)送緩沖區(qū)，使用pvminitsend()清空緩沖區(qū)菩暗。pvm_mkbuf()則適用于需要多個緩沖區(qū)的應(yīng)用掰曾。PVM提供函數(shù)設(shè)置活動發(fā)送和接收緩沖區(qū)，并獲取它們的標識停团。
數(shù)據(jù)打包：PVM提供打包函數(shù)pvmpk()將給定數(shù)據(jù)類型的數(shù)組打包到發(fā)送緩沖區(qū)旷坦，在第一個參數(shù)指針、第二個參數(shù)項數(shù)佑稠、第三個參數(shù)步長的設(shè)置下進行操作塞蹭。針對不同數(shù)據(jù)類型有相應(yīng)的打包函數(shù)，例如pvmpkstr()用于打包字符串讶坯。可以多次調(diào)用打包函數(shù)將數(shù)據(jù)打包到同一消息中岗屏。注意消息的打包與解包需要一致辆琅。
發(fā)送消息：在PVM中，消息發(fā)送采用異步方式这刷。pvmsend()用于點對點發(fā)送婉烟，pvmmcast()用于多目標發(fā)送，pvmbcast()用于組廣播暇屋，pvmpsend()實現(xiàn)打包和發(fā)送似袁。發(fā)送任務(wù)無需等待接收任務(wù)。
接收消息：PVM支持三種消息接收方式：阻塞咐刨、非阻塞和時限昙衅。阻塞式接收需等待消息到達并創(chuàng)建接收緩沖區(qū)。非阻塞接收立即返回定鸟，若消息不存在則bufid=0而涉。時限接收在指定時間內(nèi)等待消息，返回bufid=0表示未接收到联予。pvnrecv函數(shù)阻塞接收來自tid啼县、tag的消息材原，返回緩沖區(qū)標識。pymnrecv函數(shù)非阻塞接收季眷，bufid非零表示有消息余蟹。pvmtrecv根據(jù)timeout設(shè)定時限接收，bufid=0表示超時子刮。pvmprecv函數(shù)將阻塞接收和解包整合威酒，返回實際值。
數(shù)據(jù)解包：接收消息需與發(fā)送任務(wù)的打包方式匹配解包函數(shù)话告。PVM提供多種解包函數(shù)兼搏，如pvm_upk，對應(yīng)特定打包函數(shù)沙郭。示例調(diào)用中解包字符串和數(shù)組佛呻。

• 8.5 任務(wù)同步

優(yōu)先權(quán)同步
同步結(jié)構(gòu)用于強制執(zhí)行次序，例如任務(wù)等待計算完成后繼續(xù)執(zhí)行病线。并行任務(wù)無論是否有數(shù)據(jù)相關(guān)吓著，都需要在某個同步點同步。PVM中常用的同步方式是阻塞接收和障柵操作送挑。阻塞接收（pvm_recv）可強制等待匹配的消息绑莺。通過掛起消息，發(fā)送者可讓接收者等待惕耕。例如纺裁，任務(wù)TO調(diào)用f后，使用發(fā)送操作司澎，任務(wù)TI調(diào)用g前使用匹配的阻塞接收操作欺缘，確保特定的執(zhí)行次序。
障柵
使用障柵作為同步點可實現(xiàn)并行任務(wù)的同步挤安。所有任務(wù)必須到達障柵后才能繼續(xù)執(zhí)行谚殊。PVM提供pvmbarrier()函數(shù)實現(xiàn)障柵同步，需指定組名和成員數(shù)蛤铜。示例中嫩絮，任務(wù)組slave通過pvmbarrier(slave, 3)實現(xiàn)同步，使得T0和TI在等待围肥，直至T2到達障柵后才繼續(xù)執(zhí)行剿干。

• 8.6 歸約操作

歸約操作將多個值歸約為一個結(jié)果，可以是最大值穆刻、最小值怨愤、乘積或其他二元操作的結(jié)果。PVM提供pvmreduce()函數(shù)支持歸約操作蛹批。函數(shù)格式為：info=pvmreduce(func, data, n, datatype, tag, groupname, root)撰洗。參數(shù)意義見下表篮愉。

可對組內(nèi)數(shù)據(jù)數(shù)組的元素執(zhí)行歸約操作，歸約值返回給指定的根節(jié)點差导。用戶可自定義函數(shù)或使用PVM預(yù)定義函數(shù)如PvmMin试躏、PvmMax、PvmSum和PvmProduct设褐。下示例針對組"slave"的dataarray數(shù)組執(zhí)行歸約和颠蕴，組有三個成員：T0、TI和T2助析。歸約值返回給根節(jié)點犀被，此例中根節(jié)點為任務(wù)TI。三個任務(wù)需調(diào)用函數(shù)：info=pvmreduce(PvmSum, dataarray, 5, PVM_INT, tag, "slave", root)外冀。

• 8.7 工作分配

采用不同程序
向工作者分配工作有兩種方式寡键。如果工作者并發(fā)地對不同數(shù)據(jù)集執(zhí)行相同操作，則編寫單一程序適合所有工作者雪隧。另一方面西轩，如果工作者執(zhí)行不同功能，則可以采用不同程序脑沿。
管理者通過pvmspawn()激活不同的工作者任務(wù)藕畔，并通過pvmparent()返回管理者的TID以進行通信。例如庄拇，在主機cselab01注服、cselab02、cselab03和cselab04中激活任務(wù)"worker1"措近、"worker2"祠汇、"worker3"和"worker4"，可以使用以下語句創(chuàng)建所需任務(wù)：
info1 = pvmspawn("/user/rewini/worker1", 0, 1, "cselab01", 1, &tid1)
info2 = pvmspawn("/user/rewini/worker2", 0, 1, "cselab02", 1, &tid2)
info3 = pvmspawn("/user/rewini/worker3", 0, 1, "cselab03", 1, &tid3)
info4 = pvmspawn("/user/rewini/worker4", 0, 1, "cselab04", 1, &tid4)
這樣可以根據(jù)并行任務(wù)的需要分配工作給不同的工作者熄诡。
采用同一程序
若事先知道并行任務(wù)的標識號，可以輕松為運行同一程序的任務(wù)分配工作诗力。通過使用條件語句和任務(wù)的標識號凰浮，可以將工作分配給相應(yīng)的任務(wù)。然而苇本，在PVM中袜茧，任務(wù)的標識號可以是任意整數(shù)，不僅限于1瓣窄、2笛厦、3等“诚Γ可以通過任務(wù)組或任務(wù)ID數(shù)組來克服此問題裳凸。
在任務(wù)組中贱鄙，所有任務(wù)加入一個組，實例號作為任務(wù)的標識號姨谷。在任務(wù)ID數(shù)組中，管理者將包含所有任務(wù)TID的數(shù)組發(fā)送給工作者，并使用下標來標識相應(yīng)的工作者哩都。

第9章 消息傳遞接口

MPI是標準的消息傳遞接口月洛，用于編寫高效的移植性消息傳遞程序。MPI提供點對點通信和集合操作捌议，支持并行計算哼拔、數(shù)據(jù)移動和同步。MPI應(yīng)用程序由并發(fā)通信任務(wù)集合組成瓣颅，每個任務(wù)具有唯一編號倦逐，在發(fā)送和接收消息時進行協(xié)作。任務(wù)可以在同一處理器上或并發(fā)運行在不同處理器上弄捕。

• 9.1 通信

MPI使用通信子來實現(xiàn)安全通信僻孝，它將通信上下文與任務(wù)組綁定。通信子分為內(nèi)部通信子和互連通信子守谓，用于任務(wù)組內(nèi)和不同任務(wù)組之間的操作穿铆。MPI應(yīng)用程序啟動時，所有任務(wù)關(guān)聯(lián)通信子"world"斋荞。當需要新的上下文環(huán)境時荞雏，通過同步調(diào)用創(chuàng)建新的通信子。
任務(wù)組：MPI任務(wù)可隸屬于命名組平酿，組是一個對象凤优，通過MPI_Group句柄訪問。任務(wù)組提供上下文環(huán)境蜈彼，限制MPI操作在組內(nèi)執(zhí)行筑辨。組成員具有唯一編號，從零開始幸逆。MPI提供函數(shù)從現(xiàn)有組創(chuàng)建新組棍辕，不直接創(chuàng)建組。初始時还绘，任務(wù)屬于基本組楚昭，其他組基于基本組形成。新組成員可來自一個或多個組拍顷。新組可通過刪除組任務(wù)或僅包含一個任務(wù)形成抚太。可對兩組執(zhí)行并、交尿贫、差操作以生成新組电媳。
默認通信子：MPI提供通信子MPI.COMMWORLD作為默認上下文環(huán)境，在MPIInit()調(diào)用后帅霜，這個通信子包含了所有任務(wù)的集合匆背。MPI.COMMWORLD的值在所有進程中相同，并在任務(wù)生命周期中不變身冀。MPI還提供預(yù)定義通信子MPI.COMMSELF钝尸，僅包含調(diào)用進程本身。
任務(wù)編號：通信子中的任務(wù)被賦予連續(xù)整數(shù)標識搂根，范圍為0到組大小減1珍促，稱為編號。
通過MPICommrank()函數(shù)獲取任務(wù)在通信子中的編號：
MPIComm communicator; // 通信子句柄
int my_rank; // 調(diào)用任務(wù)編號
MPICommrank(communicator, &my_rank);
該函數(shù)返回調(diào)用任務(wù)在通信子中的編號（my_rank）剩愧，基于給定的通信子（communicator）猪叙。編號用于區(qū)分組內(nèi)不同任務(wù)執(zhí)行不同的工作。
通信子組：通信子關(guān)聯(lián)的組通過MPICommgroup()獲取仁卷，MPI不支持創(chuàng)建空組穴翩。
MPICommsize()函數(shù)獲取組大小。例如锦积，啟動時有5個任務(wù)（T0芒帕、T1、T2丰介、T3背蟆、T4），T3調(diào)用MPICommrank()得編號3哮幢。調(diào)用MPICommgroup(MPICOMMWORLD, &worldgroup)創(chuàng)建包含T0至T4的組带膀，MPICommsize(MPICOMM_WORLD, &n)得到5。

• 9.2 虛擬拓撲

笛卡兒拓撲
對于組內(nèi)任務(wù)的編排橙垢，線性編號無法完全反映任務(wù)間的邏輯通信模式垛叨。通過為通信子添加拓撲屬性，可以采用不同形式的任務(wù)邏輯安排柜某，如二維或三維網(wǎng)格嗽元。MPI提供了笛卡兒拓撲和圖拓撲兩種虛擬拓撲。使用MPIcartcreate()函數(shù)可以創(chuàng)建任意維度的笛卡兒結(jié)構(gòu)莺琳，其中包括已存在的通信子、維度大小载慈、周期性等參數(shù)惭等。創(chuàng)建通信子后，可以對任務(wù)編號變更办铡。

獲取任務(wù)坐標和編號
MPI的函數(shù)可以幫助任務(wù)查詢其編號和在笛卡兒結(jié)構(gòu)中的坐標辞做。使用MPICartrank函數(shù)可以根據(jù)任務(wù)的笛卡兒結(jié)構(gòu)坐標琳要，返回在通信子中的編號。類似地秤茅，MPICartcoords函數(shù)可以根據(jù)任務(wù)的編號返回其在笛卡兒結(jié)構(gòu)中的坐標稚补。這些函數(shù)在管理笛卡兒拓撲中的任務(wù)編號和坐標時非常有用。
圖拓撲
MPIGraphcreate()函數(shù)用于創(chuàng)建關(guān)聯(lián)圖拓撲的新通信子框喳。通過提供已存在的通信子课幕、節(jié)點數(shù)量、節(jié)點度信息等參數(shù)五垮，可以創(chuàng)建一個新的圖拓撲通信子乍惊。如果允許系統(tǒng)優(yōu)化虛擬拓撲到物理處理器的映射，則可能會導致任務(wù)編號的變化放仗。下面是一個示例代碼段润绎，將圖相關(guān)聯(lián)到包含所有任務(wù)的通信子(MPIWORLDCOMM)，使用MPIGraphcreate()函數(shù)創(chuàng)建新通信子graphcomm：MPIComm graphcomm; // 新通信子 int nnodes = 6; int index[6] = {2, 5, 8, 12, 14, 16}; int edges[16] = {1, 2, 0, 3, 4, 0, 3, 5, 1, 2, 4, 5, 1, 3, 2, 3}; int mapping = 0; MPIGraphcreate(MPIWORLD_COMM, nnodes, index, edges, mapping, &graphcomm);

• 9.3 任務(wù)通信

MPI任務(wù)間的通信基于消息傳遞模式诞挨，其中包括發(fā)送者莉撇、接收者、消息數(shù)據(jù)惶傻、消息標簽和通信子等部分棍郎。MPI提供了豐富的發(fā)送和接收消息的函數(shù)，使得任務(wù)之間的通信變得靈活达罗。通過這些函數(shù)坝撑，可以實現(xiàn)不同類型的任務(wù)間通信。
通信模式
MPI中的基本發(fā)送和接收消息函數(shù)是阻塞式的粮揉，支持多種通信模式巡李。標準發(fā)送是一種阻塞模式，發(fā)送者將被阻塞扶认，直到消息被安全地復(fù)制到匹配的接收緩沖區(qū)或臨時系統(tǒng)緩沖區(qū)侨拦。標準接收也是阻塞模式，接收者將被阻塞辐宾，直到接收到期望的消息狱从。緩沖發(fā)送（B）可以在發(fā)送調(diào)用返回后繼續(xù)操作，而不必等待匹配接收叠纹。同步發(fā)送（S）要求發(fā)送者和接收者都阻塞季研，直到發(fā)送和接收調(diào)用完成。就緒發(fā)送（H）只能在匹配接收已被發(fā)出后啟動誉察，并不依賴于接收端的狀態(tài)与涡。
非阻塞通信
消息傳遞接口支持非阻塞通信，任務(wù)啟動發(fā)送/接收操作后繼續(xù)執(zhí)行其他工作，再檢查操作完成狀態(tài)驼卖。非阻塞發(fā)送/接收可與標準操作交替使用氨肌，不必配對。三步：啟動發(fā)送/接收操作（MPIIsend/MPIIrecv）酌畜，執(zhí)行計算怎囚，完成通信（MPIWait/MPITest）∏虐可通過MPIIsend啟動標準模式的發(fā)送操作恳守，參數(shù)與其他發(fā)送函數(shù)相同，最后一個參數(shù)是標識通信操作的句柄埠戳。MPIIrecv類似井誉，立即返回，用于查詢或等待通信狀態(tài)整胃。MPI提供函數(shù)測試或等待非阻塞操作颗圣，如MPITest和MPIWait，還有MPITestall屁使、MPITestany在岂、MPIWaitall多個操作。
持續(xù)通信
MPI提供持續(xù)通信請求結(jié)構(gòu)蛮寂，減少通信開銷蔽午。通過綁定參數(shù)列表到請求、啟動和結(jié)束消息酬蹋，實現(xiàn)重復(fù)使用及老。可使用MPISendinit()范抓、MPIBsendinit()骄恶、MPISsendinit()、MPIRsendinit()和MPIRecvinit()創(chuàng)建請求匕垫。使用MPIStart()和MPIStartall()啟動通信僧鲁，處理方式與非阻塞通信相同。請求參數(shù)通過句柄訪問象泵。

• 9.4 同步

MPI提供同步結(jié)構(gòu)寞秃，用于強制并行任務(wù)按特定順序執(zhí)行。并行任務(wù)可能需要在某個同步點等待偶惠，直到其他任務(wù)到達春寿。MPI中的同步通過消息傳遞和障柵操作實現(xiàn)。阻塞接收可導致任務(wù)等待直到收到匹配的消息忽孽。通信同步允許兩個任務(wù)在同步點會合绑改。障柵允許任務(wù)在同步點進行同步馋缅。MPIBarrier函數(shù)用于到達障柵前任務(wù)等待。例9.5和9.6說明了如何使用MPIBarrier等實現(xiàn)同步绢淀。MPI提供的同步機制使得并行任務(wù)的執(zhí)行按照預(yù)定義的順序進行，以確保正確的通信和協(xié)調(diào)瘾腰。

• 9.5 集合操作

MPT中的集合操作是對通信子組中所有成員進行的操作皆的，通常基于任務(wù)組定義蹋盆。當組中所有成員使用匹配參數(shù)調(diào)用集合例程時费薄，集合操作會執(zhí)行。集合操作分為三類：任務(wù)控制栖雾、全局計算和數(shù)據(jù)移動楞抡。MPI_Barrier函數(shù)屬于任務(wù)控制集合操作。后續(xù)將討論全局計算和數(shù)據(jù)移動操作析藕。
全局計算
這里將討論全局歸約和掃描操作召廷。全局歸約是將結(jié)合和交換操作應(yīng)用于任務(wù)成員提供的數(shù)據(jù)元素。歸約操作可以是用戶定義的函數(shù)或預(yù)定義操作账胧，結(jié)果可返回給每個任務(wù)或僅返回給根任務(wù)竞慢。掃描操作有前綴和后綴掃描兩種類型，結(jié)果根據(jù)任務(wù)編號不同治泥。MPI提供了歸約函數(shù)MPIReduce筹煮，結(jié)果僅返回給根。MPI還提供了多對多歸約函數(shù)MPIAllreduce居夹，結(jié)果返回給所有成員败潦。掃描操作可使用MPI_Scan函數(shù)執(zhí)行，編號為i的任務(wù)的接收緩沖區(qū)將得到編號為0到i的任務(wù)發(fā)送緩沖區(qū)的歸約結(jié)果准脂。
數(shù)據(jù)移動操作
MPI提供廣播劫扒、散播和匯聚等基本數(shù)據(jù)移動集合函數(shù)。廣播允許進程向組中的每個成員發(fā)送相同的消息意狠。散播操作允許進程給每個成員發(fā)送不同的消息粟关。匯聚操作是散播的對偶操作，進程可以從組中的每個成員接收消息环戈。這些基本操作可以組合成更復(fù)雜的操作闷板。MPI提供了MPIBcast函數(shù)用于廣播，MPIScatter和MPI_Gather函數(shù)用于散播和匯聚院塞。這些函數(shù)需要在通信子組中的所有成員調(diào)用遮晚，并使用相同的根和通信子參數(shù)。散播操作中拦止，根的發(fā)送緩沖區(qū)被分為多個片段县遣，并復(fù)制到組中每個成員的接收緩沖區(qū)糜颠。匯聚操作中，每個任務(wù)將發(fā)送緩沖區(qū)的內(nèi)容發(fā)送到根任務(wù)萧求，并按順序保存在根接收緩沖區(qū)中其兴。

• 9.6 任務(wù)創(chuàng)建

這節(jié)介紹MPI應(yīng)用程序在MPI-2中創(chuàng)建新任務(wù)、建立通信的方法夸政。父任務(wù)派生子任務(wù)元旬，使用MPICommspawn()和MPICommspawn_multiple()兩個函數(shù)，這些函數(shù)必須由父任務(wù)調(diào)用守问。成功執(zhí)行函數(shù)會生成一組新的子任務(wù)匀归，父任務(wù)和子任務(wù)共享一個新的互連通信子。
聯(lián)系被派生和派生任務(wù)
MPI-2支持動態(tài)任務(wù)耗帕，但并非必須創(chuàng)建新任務(wù)穆端。可能需要在新任務(wù)和現(xiàn)有任務(wù)之間建立通信仿便，MPI-2通過互連通信子實現(xiàn)這種銜接体啰。下圖展示了通過互連通信子在父任務(wù)和子任務(wù)之間建立通信。在派生一方嗽仪，互連通信子的本地組是完成派生的組狡赐，遠程組是被派生的組。在被派生一方钦幔，本地組是新任務(wù)的MPI_COMM_WORLD枕屉，遠程組是完成派生的組。

啟動相同任務(wù)
MPICommspawn()函數(shù)創(chuàng)建程序副本并建立通信鲤氢。參數(shù)：command（派生程序名）搀擂、argv（傳遞給派生任務(wù)的參數(shù)）、maxprocs（副本數(shù)）卷玉，返回互連通信子和錯誤代碼數(shù)組哨颂。該函數(shù)在父任務(wù)中返回互連通信子，包含本地父任務(wù)和遠程派生的子任務(wù)相种。子任務(wù)可使用MPICommgetparent()獲得父任務(wù)的互連通信子威恼。參數(shù)arrayerrorcodes是用于報告啟動任務(wù)狀態(tài)的數(shù)組。成功任務(wù)對應(yīng)MPISUCCESS寝并，其余為錯誤碼箫措。
啟動多個可執(zhí)行代碼
MPICommspawnmultiple函數(shù)可同時派生多個可執(zhí)行代碼或同一程序的多組參數(shù)。派生任務(wù)共用一個MPICOMM_WORLD衬潦，且任務(wù)編號與命令次序?qū)?yīng)斤蔓。

• 9.7 單邊通信

MPI提供RMA結(jié)構(gòu)，允許任務(wù)間的遠程存儲器訪問镀岛。適用于動態(tài)改變數(shù)據(jù)訪問模式弦牡、但數(shù)據(jù)分布相對固定的應(yīng)用友驮。傳統(tǒng)發(fā)送/接收通信需要多個任務(wù)參與和按順序匹配操作。RMA模式只需要一個任務(wù)發(fā)起傳輸操作驾锰，可以是源或目標卸留。使用源和目標表示發(fā)起和相關(guān)任務(wù)。遠程存儲器訪問通過put和get操作進行椭豫。put將參數(shù)發(fā)送給目標任務(wù)艾猜，get相反。這些操作可以在一個調(diào)用中完成捻悯。
指定目標窗口
RMA操作之前，每個任務(wù)需指定存儲器窗口淤毛，供遠程任務(wù)訪問今缚。使用MPIWininit函數(shù)創(chuàng)建窗口對象。任務(wù)需執(zhí)行該函數(shù)指定現(xiàn)有存儲區(qū)窗口低淡。窗口大小為size字節(jié)姓言，起始地址為base。disp_unit用于偏移計算蔗蹋。info提供優(yōu)化信息何荚。任務(wù)可指定不同目標窗口，有不同的位置猪杭、大小和偏移單位餐塘。若任務(wù)選擇禁用遠程訪問，則size=0皂吮。返回的win窗口對象包含與comm關(guān)聯(lián)的組信息及目標窗口集的信息戒傻。
put和get操作
MPIPut函數(shù)用于將一組連續(xù)元素從源任務(wù)傳送到遠程目標任務(wù)的緩沖區(qū)，傳輸方向相反的是MPIGet函數(shù)蜂筹。這兩個函數(shù)需共享通信子和使用窗口對象關(guān)聯(lián)源和目標任務(wù)需纳。MPIPut有8個參數(shù)：源緩沖區(qū)地址、元素數(shù)量艺挪、數(shù)據(jù)類型不翩，目標任務(wù)編號、目標緩沖區(qū)偏移量麻裳、元素數(shù)量口蝠、數(shù)據(jù)類型以及窗口對象。調(diào)用MPIPut將數(shù)據(jù)傳送到與窗口對象關(guān)聯(lián)的目標任務(wù)津坑。目標緩沖區(qū)地址計算方法(window_base+Target_disp*disp_unit)亚皂，窗口基地址和偏移單位在MPIWininit中指定。MPI_Get函數(shù)從目標任務(wù)緩沖區(qū)傳送一組連續(xù)元素至源任務(wù)緩沖區(qū)国瓮。

第10章 調(diào)度與任務(wù)分配

調(diào)度問題是并行與分布式計算中的挑戰(zhàn)性問題灭必，目標是優(yōu)化任務(wù)的分配方案狞谱，評估調(diào)度系統(tǒng)的性能和效率〗欤基于性能標準評判調(diào)度跟衅，低算法復(fù)雜性更好。在復(fù)雜情況下播歼，通過加入限制條件獲得最優(yōu)算法伶跷。解決通用問題需采用啟發(fā)式算法，尋找近似最優(yōu)解秘狞。本章討論調(diào)度問題的解法叭莫，包括程序與系統(tǒng)模型、優(yōu)化算法烁试、啟發(fā)式算法雇初、調(diào)度與分配技術(shù)，同構(gòu)與異構(gòu)環(huán)境减响。

• 10.1 調(diào)度問題

一個經(jīng)典問題
調(diào)度問題在不同領(lǐng)域描述方式各異靖诗。在生產(chǎn)管理中，作業(yè)排序影響調(diào)度問題解法支示。主要目標是為管理消費者對資源的訪問找到高效策略刊橘，優(yōu)化性能指標米辐。程序逐哈、工廠作業(yè)或銀行客戶都需服務(wù)。在分布式系統(tǒng)中槽奕，調(diào)度問題源于程序的并發(fā)部分或一組程序的時間空間安排嘴纺，以優(yōu)化整體性能绞愚。任務(wù)間的優(yōu)先約束需要考慮。調(diào)度目標是確定任務(wù)向處理單元的分配和執(zhí)行次序颖医。解決調(diào)度問題常采用啟發(fā)式算法位衩，靜態(tài)或動態(tài)方法，包括混合方法熔萧。本章介紹的技術(shù)屬于靜態(tài)調(diào)度技術(shù)糖驴。
調(diào)度模型
調(diào)度系統(tǒng)包括任務(wù)、機器和調(diào)度方法佛致。任務(wù)圖映射到處理器和啟動時間贮缕，最小化完成時間。執(zhí)行時間為任務(wù)計算量除以速度俺榆，通信時間為數(shù)據(jù)傳輸量除以傳輸率感昼。任務(wù)圖表示任務(wù)間優(yōu)先約束，無向圖表示任務(wù)間通信罐脊。目標機器由處理器和互連網(wǎng)絡(luò)組成定嗓。調(diào)度將任務(wù)映射到處理器和啟動時間蜕琴，Gant圖表示任務(wù)的時間。調(diào)度目標是最小化總完成時間宵溅。執(zhí)行時間為任務(wù)計算量除以速度凌简，通信時間為數(shù)據(jù)量除以傳輸率。

• 10.2 未考慮通信的DAG調(diào)度

本節(jié)介紹了多項式時間優(yōu)化算法恃逻，解決了三種調(diào)度問題：入森林/出森林任務(wù)圖雏搂、間隔序列任務(wù)圖、兩個處理器情況寇损。目標是最小化總執(zhí)行時間凸郑。這些算法都屬于表調(diào)度，按降序給任務(wù)分配優(yōu)先級矛市，然后構(gòu)建任務(wù)表芙沥。任務(wù)無前驅(qū)或前驅(qū)已執(zhí)行即為執(zhí)行就緒。處理器無任務(wù)時執(zhí)行表中最高優(yōu)先級的就緒任務(wù)尘盼。多處理器情況下，不同調(diào)度程序的差異在于任務(wù)優(yōu)先級分配方法烦绳。
入森林/出森林任務(wù)圖調(diào)度
介紹了Hu提出的多項式時間調(diào)度算法卿捎，適用于入森林任務(wù)圖，時間復(fù)雜度O(n)径密，采用最高級優(yōu)先策略午阵。每節(jié)點級別是從源到終端最長路徑上節(jié)點數(shù)，用于確定優(yōu)先級享扔。反向森林情況下無法保證最優(yōu)結(jié)果底桂。舉例說明了算法應(yīng)用，示范最優(yōu)調(diào)度惧眠，關(guān)鍵路徑長度為5籽懦。

間隔次序任務(wù)調(diào)度
介紹了間隔次序任務(wù)，這種任務(wù)圖描述系統(tǒng)任務(wù)的優(yōu)先級關(guān)系氛魁，它具有一定的結(jié)構(gòu)屬性暮顺。Papadimitriou和Yannakakis提出了解決此問題的O(n+c)復(fù)雜度算法。算法的核心是將每個節(jié)點的后繼任務(wù)數(shù)量作為其優(yōu)先級秀存，然后分配給可用處理器的未執(zhí)行任務(wù)中具有最高優(yōu)先級的任務(wù)捶码。
二處理器調(diào)度
在這種情況下，有兩個處理器（m=2）和任意結(jié)構(gòu)的任務(wù)圖優(yōu)先關(guān)系或链。首個多項式時間算法由Fuji等（1969）基于匹配技術(shù)提出惫恼，時間復(fù)雜度為O(n2-3)。改進算法包括Cofiman（1976）澳盐、Fujii等（1969）祈纯、Sethi（1976）和Gabow（1982）令宿，其時間復(fù)雜度分別為O(n2)、O(min(en,n^2.61))和O(e+mα(n))盆繁，其中n是節(jié)點數(shù)掀淘，e是任務(wù)圖中的弧數(shù)。本節(jié)介紹了Cofinan和Graham提出的算法油昂，步驟包括為終端任務(wù)分配標號革娄，定義任務(wù)優(yōu)先級，以及根據(jù)優(yōu)先級分配任務(wù)給可用處理器冕碟。最終拦惋，通過下圖說明了算法的工作原理，任務(wù)被有效調(diào)度安寺，處理器1和2同時可用厕妖，最終完成任務(wù)的調(diào)度。

• 10.3 通信模型

完成時間的兩個成分
程序完成時間受計算時間和通信延遲兩要素影響挑庶。通信延遲的計算方法因三種模型而異言秸。任務(wù)圖C=(T,E)在m處理器上分配，proc()表示分配迎捺【倩可用不考慮通信的Gantt圖表示分配，顯示任務(wù)優(yōu)先級凳枝。程序完成時間=執(zhí)行時間+總通信延遲抄沮，總通信延遲=消息總數(shù)×每消息通信延遲。消息總數(shù)由兩模型確定：模型A岖瑰，結(jié)點對(u,p)數(shù)目叛买，滿足moc(u),proc(p)。模型B蹋订，處理器-任務(wù)對(P,v)數(shù)目率挣，P未計算任務(wù)，但至少計算一個直接后繼露戒。
由Gantt圖計算完成時間
IO處理器允許處理單元同時計算和通信难礼。任務(wù)可在Gantt圖通信間隙調(diào)度，通信延遲反映在Gantt圖中玫锋。程序完成時間由Gantt圖確定：程序完成時間=調(diào)度長度蛾茉。通信延遲由模型C確定，它假設(shè)VO處理器與每個處理器關(guān)聯(lián)撩鹿。任務(wù)可分配給正在通信的處理器谦炬，同處理器的任務(wù)通信延遲可忽略，不同處理器任務(wù)通信延遲與消息大小、路由和速度有關(guān)键思。示例：任務(wù)圖中础爬，a向b、c吼鳞、d看蚜、c發(fā)送消息。模型A中赔桌，消息數(shù)=2供炎。模型B中，消息數(shù)=1疾党。模型C中音诫，分配給不同處理器的任務(wù)通信延遲為1單位。因此雪位，程序完成時間為4單位竭钝。

• 10.4 考慮通信的DAG調(diào)度

在考慮通信開銷時，有兩種算法用于任務(wù)調(diào)度：入森林雹洗、出森林和間隔次序香罐。目標是最小化總執(zhí)行時間，考慮任務(wù)圖时肿、處理器數(shù)庇茫、任務(wù)執(zhí)行時間、通信模型C嗜侮，通信延遲港令。
在2個處理器上調(diào)度入森林/出森林

算法由EI-Rewini和Ali（1994）提出啥容，用于任務(wù)調(diào)度以最小化總執(zhí)行時間锈颗，考慮通信開銷。它通過增加新的任務(wù)優(yōu)先關(guān)系來補償通信代價咪惠，創(chuàng)建擴展任務(wù)圖击吱。當任務(wù)圖是一個人森林時，算法4可用于生成最優(yōu)調(diào)度遥昧。算法4的核心思想是在擴展任務(wù)圖中從同一集合中選擇具有最大深度的節(jié)點覆醇，并將它們放置在其他成員之后，但在共同孩子之前炭臭。這些額外的關(guān)系用于補償通信延遲永脓。然后，算法1可用于擴展任務(wù)圖鞋仍，生成不考慮通信延遲的調(diào)度常摧。如果通信約束在輸出調(diào)度中被違反，算法提供了Swapall操作，以交換任務(wù)的位置以滿足通信要求落午。算法的時間復(fù)雜性是O(n2 + mm)谎懦，其中n是任務(wù)數(shù)量，m是處理器數(shù)量溃斋。應(yīng)用示例是下圖中的入森林任務(wù)圖界拦，通過算法4進行調(diào)度，最終獲得一個考慮通信的最優(yōu)調(diào)度梗劫。

考慮通信的間隔次序調(diào)度

介紹了Ali和EI-Rewimi（1995）提出的最優(yōu)調(diào)度算法享甸，適用于任意數(shù)量處理器，考慮通信延遲在跳。算法基于任務(wù)優(yōu)先級枪萄，通過start-time和task定義，時間復(fù)雜性O(shè)(e+nm)猫妙。示例中瓷翻，根據(jù)任務(wù)后繼數(shù)，任務(wù)按優(yōu)先級調(diào)度割坠，通信延遲被考慮齐帚。算法動態(tài)分配任務(wù)，最小化執(zhí)行時間彼哼，提高性能对妄。

• 10.5 調(diào)度問題的NP完全性

NP-完全問題是計算難題，包括旅行商敢朱、漢密爾頓電路剪菱、整數(shù)規(guī)劃等，通常要求指數(shù)時間解拴签。這些問題的確切難度尚未確定孝常，是理論計算科學中重要問題。某些調(diào)度問題也被證明是NP-完全問題蚓哩，通彻咕模或有限制條件。
未考慮通信時的 NP 完全結(jié)論
介紹了調(diào)度問題的形式化定義和其特例岸梨。通用調(diào)度問題涉及任務(wù)調(diào)度在多個處理器上喜颁，有時間和資源限制。問題1是最通用的形式曹阔，問題2要求所有任務(wù)單一時間單位執(zhí)行半开，問題3在兩處理器上執(zhí)行，問題4指定了任務(wù)之間的間隔次序赃份，問題5與反向森林相關(guān)寂拆。這些問題都被證明是NP-完全問題，難以在多項式時間內(nèi)解決。

考慮通信的NP 完全結(jié)論
不同通信模型下的調(diào)度問題復(fù)雜性變化大漓库。在模型A下恃慧，任意處理器上的通信樹是NP-完全。模型B下渺蒿，相同執(zhí)行時間和通信成本的兩處理器上的調(diào)度問題是NP-完全痢士，樹形結(jié)構(gòu)程序調(diào)度也NP-完全。在兩處理器上的通信樹調(diào)度問題尚待解決茂装。模型C下怠蹂，最優(yōu)調(diào)度單位時間任務(wù)圖在不限處理器數(shù)量時是NP-完全，要求通信成本相等且大于一個單位時間少态。

• 10.6 啟發(fā)式算法

在解決調(diào)度問題時城侧，需權(quán)衡并行程序和目標機器的限制。復(fù)雜性導致需采用次優(yōu)方法彼妻，如啟發(fā)式方法嫌佑，雖不保證最優(yōu)解但計算迅速。啟發(fā)式方法基于直覺侨歉，利用參數(shù)影響系統(tǒng)屋摇。方法優(yōu)劣取決于方案接近最優(yōu)的頻率和計算時間。啟發(fā)式方法效果取決于系統(tǒng)參數(shù)幽邓，某方法在某系統(tǒng)上最優(yōu)炮温，但不適于其他系統(tǒng)。因此牵舵，多種啟發(fā)式方法應(yīng)對應(yīng)多環(huán)境柒啤。在通用調(diào)度問題中，需要考慮程序設(shè)計原則和啟發(fā)式方法的思想畸颅。
并行性與通信延遲
在沒有通信延遲的情況下担巩，所有就緒任務(wù)可同時分配到可用處理器，降低執(zhí)行時間重斑，適用于共享存儲環(huán)境兵睛，通信速度快肯骇。但通信延遲存在時窥浪，啟發(fā)式調(diào)度算法需考慮延遲。長通信延遲任務(wù)可能與前驅(qū)任務(wù)分配到同處理器笛丙。例如漾脂，若a、b間通信慢胚鸯，b分P1骨稿，a、c間通信快，c分P2坦冠。通信延遲增加了最優(yōu)調(diào)度難度形耗，需檢查每處理器上結(jié)點的開始時間，權(quán)衡最大并行性和最小延遲辙浑。簡而言之激涤，通信延遲考慮下，任務(wù)分配需更復(fù)雜判呕。

粒度大小和數(shù)據(jù)局部性
在并行計算中倦踢，粒度大小是一個重要問題，需要在劃分程序為計算顆粒時解決侠草。顆粒是一組順序指令辱挥，可以小到單個操作或大到整個程序。過大的顆粒會減少并行性边涕，而過小的顆粒會增加上下文切換和通信開銷晤碘。隨著分布式計算的興起，局部化數(shù)據(jù)對粒度變得至關(guān)重要功蜓，以減少跨處理器的數(shù)據(jù)傳輸延遲哼蛆。在最大局部性和最大并行性之間存在權(quán)衡，最優(yōu)的中間粒度可以同時最大化局部性和潛在的并行性霞赫，從而實現(xiàn)最短的并行執(zhí)行時間腮介。
不確定性
確定性調(diào)度在執(zhí)行前所有任務(wù)和關(guān)系都明確。不確定性則源于循環(huán)和條件轉(zhuǎn)移編程端衰。循環(huán)次數(shù)未知叠洗，條件轉(zhuǎn)移高度不確定，增加調(diào)度復(fù)雜度旅东。條件轉(zhuǎn)移使執(zhí)行時間和通信延遲變動灭抑。動態(tài)調(diào)度應(yīng)對不確定性，但成本高抵代，引入額外開銷腾节，可能導致任務(wù)頻繁切換，浪費時間荤牍。相比之下案腺，靜態(tài)調(diào)度預(yù)測不確定性行為，影響調(diào)度質(zhì)量康吵∨ィ可考慮混合方法，兼顧靜態(tài)和動態(tài)調(diào)度晦嵌，降低成本同辣。
基于優(yōu)先級的調(diào)度
表調(diào)度算法在10.2節(jié)介紹拷姿，可擴展用于通用調(diào)度問題。按任務(wù)優(yōu)先級排序旱函，最高優(yōu)先級任務(wù)先執(zhí)行响巢。然后，根據(jù)不同啟發(fā)式算法棒妨，分配任務(wù)優(yōu)先級和選擇處理器抵乓。例如，可基于任務(wù)圖最長路徑或后繼數(shù)確定優(yōu)先級靶衍，也可用最早開始/完成時間選處理器灾炭。算法6，概述通用表調(diào)度算法颅眶。這種方法解決各種調(diào)度挑戰(zhàn)蜈出。

簇化
這種調(diào)度啟發(fā)式方法分兩階段：處理器分配（分配任務(wù)給處理器）和任務(wù)排序（安排任務(wù)在處理器上執(zhí)行）。任務(wù)圖簇化解決分配問題涛酗，將任務(wù)映射到簇铡原，同簇任務(wù)在同一處理器上執(zhí)行。若獨立任務(wù)映射到同一簇商叹，稱非線性簇化燕刻，否則線性。簇化啟發(fā)式非回溯剖笙，以降低并行時間為目標卵洗，確保簇數(shù)不超處理器數(shù)。精練步驟合并簇弥咪，置連接邊為零过蹂，降低通信開銷。關(guān)鍵參數(shù)有關(guān)鍵路徑和主序列聚至。分布式系統(tǒng)任務(wù)調(diào)度兩階段法使用算法7中的任務(wù)簇化酷勺。

任務(wù)復(fù)制
調(diào)度啟發(fā)式算法可采用任務(wù)復(fù)制來降低通信延遲。因為跨處理器的通信開銷較大扳躬，目標是減少任務(wù)間消息交換脆诉。思想是在接收任務(wù)的處理器上盡可能執(zhí)行發(fā)送任務(wù)的多個副本，將通信轉(zhuǎn)為處理器內(nèi)部贷币。例如击胜，圖中任務(wù)a在P1和P2上的復(fù)制可減小任務(wù)c在P2上的開始時間，提高任務(wù)b和c的并行性片择。但要確保復(fù)制開銷不過大潜的，通常對細粒度任務(wù)圖更合適骚揍。

• 10.7 任務(wù)分配

任務(wù)分配模型
在分布式計算中字管，任務(wù)分配是一個關(guān)鍵問題啰挪。當沒有確定的任務(wù)執(zhí)行順序時，必須合理地將任務(wù)分配到處理器上嘲叔，以最小化總開銷亡呵。這包括任務(wù)執(zhí)行和通信開銷。任務(wù)分配的目標是平衡這兩種開銷硫戈，但它們通常相互沖突锰什。將任務(wù)分配給同一處理器可減少通信開銷，但可能導致負載不均衡丁逝。平均分配任務(wù)可提高處理器利用率汁胆，但增加通信。任務(wù)分配技術(shù)旨在找到最佳方案霜幼，以最小化總開銷嫩码。模型假設(shè)了任務(wù)交互圖和執(zhí)行時間向量來表示問題。

二處理器最優(yōu)任務(wù)分配
Harold Stone（1977）提出的優(yōu)化算法解決任務(wù)分配問題罪既，基于兩端網(wǎng)絡(luò)圖和網(wǎng)絡(luò)流算法铸题。在兩端網(wǎng)絡(luò)圖中，有源節(jié)點S和匯節(jié)點T，邊帶權(quán)重。問題是找到最小割集鞍爱，即最小總權(quán)重的節(jié)點分割茬缩，有多項式時間解法。算法適用于兩個處理器的分布式系統(tǒng)嘉涌，將任務(wù)交互圖映射到兩端網(wǎng)絡(luò)圖，通過網(wǎng)絡(luò)流算法找到最小權(quán)重割集，確定最優(yōu)任務(wù)分配墙牌。

處理器陣列上的最優(yōu)任務(wù)分配
本節(jié)算法解決分布式系統(tǒng)中線性陣列處理器情境（Lee等，1992）暗甥。任務(wù)交互圖表示程序任務(wù)喜滨，系統(tǒng)由m處理器通過m-1鏈路連接，類似二處理器情形撤防。借鑒Stone算法8思想虽风，應(yīng)用最大流最小切割算法。首先寄月，構(gòu)建相關(guān)兩端網(wǎng)絡(luò)圖辜膝，割集對應(yīng)任務(wù)分配，權(quán)重是總開銷漾肮。最小割集即最佳任務(wù)分配厂抖。

啟發(fā)式任務(wù)分配
任務(wù)分配問題為NP-完全問題，即使通信開銷僅為0或1克懊，也是NP難題（Ali和El-Rewini忱辅，1994）七蜘。面對問題復(fù)雜性，提出多種啟發(fā)式方法墙懂。某些方法源自Stone算法解決二處理器問題橡卤，通用分配采用最大流最小割算法。其他啟發(fā)式方法利用圖論损搬。

• 10.8 異構(gòu)環(huán)境下的調(diào)度

異構(gòu)計算是解決多種內(nèi)在并行性應(yīng)用程序的調(diào)度問題的有效方法碧库。同構(gòu)系統(tǒng)僅支持一種并行模式，無法滿足多樣性的需求巧勤。異構(gòu)計算提供多種體系結(jié)構(gòu)嵌灰，如混合模式機器和混合機器系統(tǒng)，以協(xié)同執(zhí)行不同需求的子任務(wù)颅悉。任務(wù)需要分解成同構(gòu)子任務(wù)伞鲫，然后分配給合適的機器或模式以最小化總執(zhí)行時間。在異構(gòu)環(huán)境中签舞，程序劃分和調(diào)度需要根據(jù)內(nèi)在并行性類型進行分類秕脓，增加了挑戰(zhàn)。調(diào)度通常分為系統(tǒng)級和機器級儒搭，確保任務(wù)與機器類型匹配吠架。這需要用戶指定任務(wù)分解和分配方式。異構(gòu)計算的目標是最大程度地利用不同機器搂鲫，例如傍药，將任務(wù)劃分為子任務(wù)、代碼段和代碼塊魂仍，并將其分配給匹配的機器拐辽。異構(gòu)計算的方法可以在相關(guān)文獻中找到，如Chen等人（1993）和Freund與Siegel（1993）的研究擦酌。