并行程序設計

并行計算系統(tǒng)體系結(jié)構(gòu)概述目錄并行計算機系統(tǒng)及結(jié)構(gòu)模型當代并行機系統(tǒng)并行計算性能評測1并行計算機系統(tǒng)及結(jié)構(gòu)模型1.1并行計算機系統(tǒng)互連1.1.1系統(tǒng)互連1.1.2靜態(tài)互聯(lián)網(wǎng)絡1.1.3動態(tài)互連網(wǎng)絡1.1.4標準互聯(lián)網(wǎng)絡1.2

并行計算機系統(tǒng)結(jié)構(gòu)1.2.1并行計算機結(jié)構(gòu)模型1.2.2并行計算機訪存模型系統(tǒng)互連不同帶寬與距離的互連技術: 總線、SAN、LAN、MAN、WAN局部總線、I/O總線、SAN和LAN網(wǎng)絡性能指標節(jié)點度（NodeDegree）：射入或射出一個節(jié)點的邊數(shù)網(wǎng)絡直徑（NetworkDiameter）：網(wǎng)絡中任何兩個節(jié)點之間的最長距離，即最大路徑數(shù)。對剖寬度（BisectionWidth）：對分網(wǎng)絡各半所必須移去的最少邊數(shù)對剖帶寬（BisectionBandwidth）:每秒鐘內(nèi)，在最小的對剖平面上通過所有連線的最大信息位（或字節(jié)）數(shù)如果從任一節(jié)點觀看網(wǎng)絡都一樣，則稱網(wǎng)絡為對稱的（Symmetry）靜態(tài)互連網(wǎng)絡與動態(tài)互連網(wǎng)絡靜態(tài)互連網(wǎng)絡：處理單元間有著固定連接的一類網(wǎng)絡，在程序執(zhí)行期間，這種點到點的鏈接保持不變；典型的靜態(tài)網(wǎng)絡有一維線性陣列、二維網(wǎng)孔、樹連接、超立方網(wǎng)絡、立方環(huán)、洗牌交換網(wǎng)、蝶形網(wǎng)絡等動態(tài)網(wǎng)絡：用交換開關構(gòu)成的，可按應用程序的要求動態(tài)地改變連接組態(tài)；典型的動態(tài)網(wǎng)絡包括總線、交叉開關和多級互連網(wǎng)絡等靜態(tài)互連網(wǎng)絡（1）一維線性陣列（1-DLinearArray）：并行機中最簡單、最基本的互連方式每個節(jié)點只與其左、右近鄰相連N個節(jié)點用N-1條邊串接之，內(nèi)節(jié)點度為2，直徑為N-1，對剖寬度為1當首、尾節(jié)點相連時可構(gòu)成循環(huán)移位器，在拓撲結(jié)構(gòu)上等同于環(huán)。環(huán)可以是單向的或雙向的，其節(jié)點度恒為2，直徑或為int(n/2)

（雙向環(huán)）或為N-1（單向環(huán)），對剖寬度為2靜態(tài)互連網(wǎng)絡（2）二維網(wǎng)孔（2-DMesh）：每個節(jié)點只與其上、下、左、右的近鄰相連（邊界節(jié)點除外），節(jié)點度為4，網(wǎng)絡直徑為，對剖寬度為在垂直方向上帶環(huán)繞，水平方向呈蛇狀，就變成Illiac網(wǎng)孔了，節(jié)點度恒為4，網(wǎng)絡直徑為，而對剖寬度為垂直和水平方向均帶環(huán)繞，則為2-D環(huán)繞（2-DTorus），節(jié)點度恒為4，網(wǎng)絡直徑為，對剖寬度為靜態(tài)互連網(wǎng)絡（3）二叉樹：除了根、葉節(jié)點，每個內(nèi)節(jié)點只與其父節(jié)點和兩個子節(jié)點相連。節(jié)點度為3，對剖寬度為1，而樹的直徑為如果盡量增大節(jié)點度為，則直徑縮小為2，此時就變成了星形網(wǎng)絡傳統(tǒng)二叉樹的主要問題是根易成為通信瓶頸。胖樹節(jié)點間的通路自葉向根逐漸變寬。靜態(tài)互連網(wǎng)絡（4）超立方：一個n-立方由個頂點組成，3-立方如圖(a)所示；4-立方如圖(b)所示，由兩個3-立方的對應頂點連接而成。n-立方的節(jié)點度為n，網(wǎng)絡直徑也是n，而對剖寬度為。如果將3-立方的每個頂點代之以一個環(huán)就構(gòu)成了如圖(d)所示的3-立方環(huán)，此時每個頂點的度為3，而不像超立方那樣節(jié)點度為n。嵌入將網(wǎng)絡中的各節(jié)點映射到另一個網(wǎng)絡中去用膨脹（Dilation）系數(shù)來描述嵌入的質(zhì)量，它是指被嵌入網(wǎng)絡中的一條鏈路在所要嵌入的網(wǎng)絡中對應所需的最大鏈路數(shù)如果該系數(shù)為1，則稱為完美嵌入環(huán)網(wǎng)可完美嵌入到2-D環(huán)繞網(wǎng)中超立方網(wǎng)可完美嵌入到2－D環(huán)繞網(wǎng)中嵌入網(wǎng)絡名稱網(wǎng)絡規(guī)模節(jié)點度網(wǎng)絡直徑對剖寬度對稱鏈路數(shù)線性陣列21非環(huán)形2（雙向）2是2-D網(wǎng)孔

4非Illiac網(wǎng)孔

4非2-D環(huán)繞4是二叉樹31非星形2非超立方

nn是立方環(huán)3是靜態(tài)互連網(wǎng)絡特性比較動態(tài)互連網(wǎng)絡(1)總線：PCI、VME、Multics、Sbus、MicroChannel多處理機總線系統(tǒng)的主要問題包括總線仲裁、中斷處理、協(xié)議轉(zhuǎn)換、快速同步、高速緩存一致性協(xié)議、分事務、總線橋和層次總線擴展等動態(tài)互連網(wǎng)絡（2）交叉開關（Crossbar）單級交換網(wǎng)絡，可為每個端口提供更高的帶寬。象電話交換機一樣，交叉點開關可由程序控制動態(tài)設置其處于“開”或“關”狀態(tài)，而能提供所有（源、目的）對之間的動態(tài)連接。交叉開關一般有兩種使用方式：一種是用于對稱的多處理機或多計算機機群中的處理器間的通信；另一種是用于SMP服務器或向量超級計算機中處理器和存儲器之間的存取。動態(tài)互聯(lián)網(wǎng)絡（3）單級交叉開關級聯(lián)起來形成多級互連網(wǎng)絡MIN（MultistageInterconnectionNetwork）標準互聯(lián)網(wǎng)絡Myrinet由Myricom公司設計的千兆位包交換網(wǎng)絡，其目的是為了構(gòu)筑計算機機群，使系統(tǒng)互連成為一種商業(yè)產(chǎn)品基于加州理工學院開發(fā)的多計算機和VLSI技術以及在南加州大學開發(fā)的ATOMIC/LAN技術能假設任意拓撲結(jié)構(gòu)，不必限定為開關網(wǎng)孔或任何規(guī)則的結(jié)構(gòu)在數(shù)據(jù)鏈路層具有可變長的包格式，對每條鏈路施行流控制和錯誤控制，并使用切通選路法以及定制的可編程的主機接口。在物理層上，Myrinet網(wǎng)使用全雙工SAN鏈路Myrinet#4SystemonTop500listSystemsustains64%ofpeakperformanceButsmallersystemshit70-75%ofpeakMareNostrum:largestMyrinetclusterintheworldIBMsystematBarcelonaSupercomputerCenter4812PowerPC970processors,9.6TBmemoryQuadricsQsNetIIE-seriesReleasedattheendofMay2004Deliver128-portstandaloneswitchesPerformance:Latency:3usBandwidth:900MB/sCost/port(basedon64-portconfiguration):Switch+NIC+cableQuadrics#5onTop500listSustains74%ofpeakOthersystemsonTop500listsustain70-75%ofpeakInfinibandNewestinterconnectCurrentlyshipping32-portswitchesRequires20switchestosupportafullbisectionbandwidthnetworkfor128nodesPerformance:Latency:6.8usBandwidth:840MB/sInfiniband#3onTop500listSustained58%ofpeakTheother2InfinibandmachinesonTop500listachieved64%and68%Interconnects/Systems1并行計算機系統(tǒng)及結(jié)構(gòu)模型1.2

并行計算機系統(tǒng)結(jié)構(gòu)1.2.1并行計算機結(jié)構(gòu)模型1.2.2并行計算機訪存模型并行計算機結(jié)構(gòu)模型并行計算機體系合一結(jié)構(gòu)

SMP(SymmetricMultiprocessor)、MPP(MassivelyParallelProcessor)、DSM和COW(ClusterofWorksations)并行結(jié)構(gòu)漸趨一致。大量的節(jié)點通過高速網(wǎng)絡互連起來五種結(jié)構(gòu)特性一覽表屬性PVPSMPMPPDSMCOW結(jié)構(gòu)類型MIMDMIMDMIMDMIMDMIMD處理器類型專用定制商用商用商用商用互連網(wǎng)絡定制交叉開關總線、交叉開關定制網(wǎng)絡定制網(wǎng)絡商用網(wǎng)絡（以太ATM）通信機制共享變量共享變量消息傳遞共享變量消息傳遞地址空間單地址空間單地址空間多地址空間單地址空間多地址空間系統(tǒng)存儲器集中共享集中共享分布非共享分布共享分布非共享訪存模型UMAUMANORMANUMANORMA代表機器CrayC-90，CrayT-90，銀河1號IBMR50，SGIPowerChallenge，曙光1號IntelParagon，IBMSP2，曙光1000/2000StanfordDASH，CrayT3DBerkeleyNOW，AlphaFarm存儲器層次存儲器存取模型(UMANUMACOMANORMA)LM1P1LM2P2LMnPn互連網(wǎng)絡(a)共享本地存儲模型全局互連網(wǎng)絡(b)層次式機群模型GSMGSMGSM…………PCINCSMPPCSMCSM群1……PCINCSM群NPPCSMCSM……NORMACOMANUMAUMA并行計算機訪存模型（1)均勻存儲訪問模型UMA（UniformMemoryAccess）。其特點是：物理存儲器被所有處理器均勻共享所有處理器訪問任何存儲字時間相同每臺處理器可帶私有高速緩存外圍設備也可以一定形式共享并行計算機訪存模型（2)非均勻存儲訪問模型NUMA(NonuniformMemoryAccess)。特點是：被共享的存儲器在物理上分布在所有的處理器中，其所有本地存儲器的集合就組成了全局地址空間；訪問存儲器的時間不一樣:訪問本地存儲器LM或群內(nèi)共享存儲器CSM較快，而訪問外地的存儲器或全局共享存儲器GSM較慢每臺處理器照例可帶私有高速緩存

LM1P1LM2P2LMnPn互連網(wǎng)絡(a)共享本地存儲模型全局互連網(wǎng)絡(b)層次式機群模型GSMGSMGSM…………PCINCSMPPCSMCSM群1……PCINCSM群NPPCSMCSM……并行計算機訪存模型（3)全高速緩存存儲訪問COMA(Cache-OnlyMemoryAccess)模型。其特點是：各處理器節(jié)點中沒有存儲層次結(jié)構(gòu)，全部高速緩存組成了全局地址空間；利用分布的高速緩存目錄D進行遠程高速緩存的訪問;COMA中的高速緩存容量一般都大于2級高速緩存容量；使用COMA時，數(shù)據(jù)開始時可任意分配，因為在運行時它最終會被遷移到要用到它們的地方。

并行計算機訪存模型（4)高速緩存一致性非均勻存儲訪問模型CC-NUMA（Coherent-CacheNonuniformMemoryAccess）多數(shù)使用基于目錄的高速緩存一致性協(xié)議；保留SMP結(jié)構(gòu)易于編程的優(yōu)點，也改善SMP的可擴放性；實際上是一個分布共享存儲的DSM多處理機系統(tǒng)；程序員無需明確地在節(jié)點上分配數(shù)據(jù)，系統(tǒng)的硬件和軟件自動在各節(jié)點分配數(shù)據(jù)，在運行期間，高速緩存一致性硬件會自動地將數(shù)據(jù)遷移至要用到它的地方。

并行計算機訪存模型（5)非遠程存儲訪問模型NORMA（No-RemoteMemoryAccess）。NORMA的特點是：所有存儲器是私有構(gòu)筑并行機系統(tǒng)的不同存儲結(jié)構(gòu)2當代并行機系統(tǒng)2.1共享存儲多處理機系統(tǒng)2.1.1對稱多處理機SMP結(jié)構(gòu)特性2.2分布存儲多計算機系統(tǒng)2.2.1大規(guī)模并行機MPP結(jié)構(gòu)特性2.3機群系統(tǒng)2.3.1工作站機群COW對稱多處理機SMP(1)SMP:采用商用微處理器，通常有片上和片外Cache，基于總線連接，集中式共享存儲，UMA結(jié)構(gòu)例子：SGIPowerChallenge,DECAlphaServer,Dawning1對稱多處理機SMP(2)優(yōu)點對稱性單地址空間，易編程性，動態(tài)負載平衡，無需顯式數(shù)據(jù)分配高速緩存及其一致性，數(shù)據(jù)局部性，硬件維持一致性低通信延遲，Load/Store完成問題欠可靠，BUS,OS,SM通信延遲（相對于CPU），競爭加劇慢速增加的帶寬（MBdouble/3年,IOB更慢）不可擴放性〉CC-NUMA大規(guī)模并行機MPP成百上千個處理器組成的大規(guī)模計算機系統(tǒng)，規(guī)模是變化的。NORMA結(jié)構(gòu)，高帶寬低延遲定制互連?？蓴U放性：Mem,I/O,平衡設計系統(tǒng)成本：商用處理器，相對穩(wěn)定的結(jié)構(gòu)，SMP,分布通用性和可用性：不同的應用，PVM,MPI,交互，批處理，互連對用戶透明通信要求存儲器和I/O能力例子：IntelOptionRedIBMSP2Dawning1000典型MPP系統(tǒng)特性比較MPP模型Intel/SandiaASCIOptionRedIBMSP2SGI/CrayOrigin2000一個大型樣機的配置9072個處理器，1.8Tflop/s(NSL)400個處理器，100Gflop/s(MHPCC)128個處理器，51Gflop/s(NCSA)問世日期1996年12月1994年9月1996年10月處理器類型200MHz,200Mflop/sPentiumPro67MHz，267Mflop/sPOWER2200MHz，400Mflop/sMIPSR10000節(jié)點體系結(jié)構(gòu)和數(shù)據(jù)存儲器2個處理器，32到256MB主存，共享磁盤1個處理器，64MB到2GB本地主存，1GB到14.5GB本地磁盤2個處理器，64MB到256MB分布共享主存和共享磁盤互連網(wǎng)絡和主存模型分離兩維網(wǎng)孔，NORMA多級網(wǎng)絡，NORMA胖超立方體網(wǎng)絡，CC-NUMA節(jié)點操作系統(tǒng)輕量級內(nèi)核（LWK）完全AIX（IBMUNIX）微內(nèi)核CellularIRIX自然編程機制基于PUMAPortals的MPIMPI和PVMPowerC，PowerFortran其他編程模型Nx，PVM，HPFHPF，LindaMPI，PVM工作站機群COW分布式存儲，MIMD，工作站+商用互連網(wǎng)絡，每個節(jié)點是一個完整的計算機，有自己的磁盤和操作系統(tǒng)，而MPP中只有微內(nèi)核優(yōu)點：投資風險小系統(tǒng)結(jié)構(gòu)靈活性能/價格比高能充分利用分散的計算資源可擴放性好問題通信性能并行編程環(huán)境例子：BerkeleyNOW，AlphaFarm,FXCOWP/CMMIOMIOMP/CNICNICDDLANSMP\MPP\機群比較系統(tǒng)特征SMPMPP機群節(jié)點數(shù)量(N)O(10)O(100)-O(1000)O(100)節(jié)點復雜度中粒度或細粒度細粒度或中粒度中粒度或粗粒度節(jié)點間通信

共享存儲器消息傳遞或共享變量（有DSM時）消息傳遞節(jié)點操作系統(tǒng)1N(微內(nèi)核)和1個主機OS(單一)N(希望為同構(gòu))支持單一系統(tǒng)映像永遠部分希望地址空間單一多或單一（有DSM時）多個作業(yè)調(diào)度單一運行隊列主機上單一運行隊列協(xié)作多隊列網(wǎng)絡協(xié)議非標準非標準標準或非標準可用性通常較低低到中高可用或容錯性能/價格比一般一般高互連網(wǎng)絡總線/交叉開關定制商用Top10FastestComputers(Linpack)Rank Site Computer Processors Year Rmax

DOE/NNSA/LLNLUSA IBMBlueGene 131072 2005 280600 NNSA/SandiaLabs,USA CrayRedStorm,Opteron 26544 2006 101400 IBMResearch,USA, IBMBlueGeneSolution 40960 2005 91290 DOE/NNSA/LLNL,USA ASCIPurple-IBMeServerp5 12208 2006 75760BarcelonaCenter,Spain IBMJS21Cluster,PPC970 10240 2006 62630NNSA/SandiaLabs,USA DellThunderbirdCluster 9024 2006 53000CEA,France BullTera-10Itanium2Cluster 9968 2006 52840NASA/Ames,USA SGIAltix1.5GHz,Infiniband 10160 2004 51870GSICCenter,Japan NEC/SunGridCluster(Opteron) 11088 2006 47380OakRidgeLab,USA CrayJaguarXT3,2.6GHzdual 10424 2006 43480

NECEarthSimulator(topfor5lists)movesdownto#14#10systemhasdoubledinperformancesincelastyearTop500:ArchitecturalStylesTop500:ProcessorType3并行計算性能評測3.1并行機的一些基本性能指標3.2加速比性能定律3.2.1Amdahl定律3.2.2Gustafson定律3.2.3Sun和Ni定律3.3可擴放性評測標準3.3.1并行計算的可擴放性3.3.2等效率度量標準3.3.3等速度度量標準3.3.4平均延遲度量標準CPU的某些基本性能指標工作負載執(zhí)行時間浮點運算數(shù)指令數(shù)目并行執(zhí)行時間Tcomput

為計算時間，Tparo為并行開銷時間，Tcomm為相互通信時間

Tn=Tcomput+Tparo+Tcomm存儲器性能存儲器的層次結(jié)構(gòu)(C,L,B)估計存儲器的帶寬RISCaddr1,r2,r3r8bytes100MHzB=3*8*100*106B/s=2.4GB/s并行與通信開銷并行和通信開銷：相對于計算很大。PowerPC(每個周期15ns執(zhí)行4flops;創(chuàng)建一個進程1.4ms可執(zhí)行372000flops)開銷的測量：乒--乓方法（Ping-PongScheme）節(jié)點0發(fā)送m個字節(jié)給節(jié)點1；節(jié)點1從節(jié)點0接收m個字節(jié)后，立即將消息發(fā)回節(jié)點0?？偟臅r間除以2，即可得到點到點通信時間，也就是執(zhí)行單一發(fā)送或接收操作的時間。Ping-PongSchemeif（my_node_id=0）then/*發(fā)送者*/

start_time=second（） sendanm-bytemessagetonode1 receiveanm-bytemessagefromnode1 end_time=second（） total_time=end_time–start_timecommunication_time[i]=total_time/2 elseif（my_node_id=1）then/*接收者*/

receiveanm-bytemessagefromnode0 sendanm-bytemessagetonode0 endif并行開銷的表達式：整體通信典型的整體通信有：播送（Broadcasting）：處理器0發(fā)送m個字節(jié)給所有的n個處理器收集（Gather）：處理0接收所有n個處理器發(fā)來在消息，所以處理器0最終接收了mn個字節(jié)；散射（Scatter）：處理器0發(fā)送了m個字節(jié)的不同消息給所有n個處理器，因此處理器0最終發(fā)送了mn個字節(jié)；全交換（TotalExchange）：每個處理器均彼此相互發(fā)送m個字節(jié)的不同消息給對方，所以總通信量為mn2個字節(jié)；循環(huán)移位（Circular-shift）：處理器i發(fā)送m個字節(jié)給處理器i+1，處理器n-1發(fā)送m個字節(jié)給處理器0，所以通信量為mn個字節(jié)。機器的成本、價格與性/價比機器的成本與價格機器的性能/價格比Performance/CostRatio：系指用單位代價（通常以百萬美元表示）所獲取的性能（通常以MIPS或MFLOPS表示）利用率（Utilization）：可達到的速度與峰值速度之比算法級性能評測加速比性能定律并行系統(tǒng)的加速比是指對于一個給定的應用，并行算法（或并行程序）的執(zhí)行速度相對于串行算法（或串行程序）的執(zhí)行速度加快了多少倍。Amdahl定律Gustafson定律SunNi定律可擴放性評測標準等效率度量標準等速度度量標準平均延遲度量標準Amdahl定律P：處理器數(shù)；W：問題規(guī)模（計算負載、工作負載，給定問題的總計算量）；Ws：應用程序中的串行分量，f是串行分量比例（f=Ws/W，Ws=W1）；WP：應用程序中可并行化部分，1-f為并行分量比例；Ws+Wp=W；Ts=T1：串行執(zhí)行時間，Tp：并行執(zhí)行時間；S：加速比，E：效率；出發(fā)點：固定不變的計算負載固定的計算負載分布在多個處理器上的增加處理器加快執(zhí)行速度，從而達到加速的目的Amdahl定律（cont‘d)固定負載的加速公式：

Ws+Wp可相應地表示為fW+（1-f）W

p→∞時，上式極限為：S=1/fWo為額外開銷 Amdahl’slaw(cont’d)Gustafson定律出發(fā)點：對于很多大型計算，精度要求很高，而計算時間要求固定不變。此時為了提高精度，必須加大計算量，相應地亦必須增多處理器數(shù)才能維持時間不變沒有必要固定工作負載而計算程序運行在不同數(shù)目的處理器上，增多處理器必須相應地增大問題規(guī)模才有實際意義

Gustafson加速定律:并行開銷Wo：Gustafson定律（cont‘d)Sun和Ni定律基本思想：只要存儲空間許可，應盡量增大問題規(guī)模以產(chǎn)生更好和更精確的解（此時可能使執(zhí)行時間略有增加）。假定在單節(jié)點上使用了全部存儲容量M并在相應于W的時間內(nèi)求解之，此時工作負載W=fW+（1-f）W。在p個節(jié)點的并行系統(tǒng)上，能夠求解較大規(guī)模的問題是因為存儲容量可增加到pM。令因子G（p）反應存儲容量增加到p倍時并行工作負載的增加量，所以擴大后的工作負載W=fW+（1-f）G（p）W。存儲受限的加速公式：Sun和Ni定律(cont’d)G（p）=1時就是Amdahl加速定律；

G（p）=p變?yōu)閒+p（1-f），就是Gustafson加速定律G（p）>p時，相應于計算機負載比存儲要求增加得快，此時Sun和Ni加速均比Amdahl加速和Gustafson加速為高。可擴展性評測標準并行計算的可擴展性（Scalability）在確定的應用背景下，計算機系統(tǒng)（或算法或程序等）性能隨處理器數(shù)的增加而按比例提高的能力影響加速比的因素：處理器數(shù)與問題規(guī)模求解問題中的串行分量并行處理所引起的額外開銷（通信、等待、競爭、冗余操作和同步等）加大的處理器數(shù)超過了算法中的并發(fā)程度增加問題的規(guī)模有利于提高加速的因素：較大的問題規(guī)?？商峁┹^高的并發(fā)度；額外開銷的增加可能慢于有效計算的增加；算法中的串行分量比例不是固定不變的（串行部分所占的比例隨著問題規(guī)模的增大而縮?。?。增加處理器數(shù)會增大額外開銷和降低處理器利用率，所以對于一個特定的并行系統(tǒng)（算法或程序），它們能否有效利用不斷增加的處理器的能力應是受限的，而度量這種能力就是可擴展性這一指標?？蓴U展性評測標準（cont‘d)可擴展性:調(diào)整什么和按什么比例調(diào)整并行計算要調(diào)整的是處理數(shù)p和問題規(guī)模W，兩者可按不同比例進行調(diào)整，此比例關系（可能是線性，多項式或指數(shù)等）反映了可擴放的程度。主要目的：確定解決某類問題用何種并行算法與何種并行體系結(jié)構(gòu)的組合，可以有效地利用大量處理器；對于運行于某種體系結(jié)構(gòu)并行機上的某種算法當移植到大規(guī)模處理機上后運行的性能；對固定的問題規(guī)模，確定在某類并行機上最優(yōu)的處理器數(shù)與可獲得的最大的加速比；用于指導改進并行算法和并行機體系結(jié)構(gòu)，以使并行算法盡可能地充分利用可擴充的大量處理器目前無一個公認的、標準的和被普遍接受的嚴格定義和評判它的標準等效率度量標準令tie

和tio

分別是并行系統(tǒng)上第i個處理器的有用計算時間和額外開銷時間（包括通信、同步和空閑等待時間等）Tp

是p個處理器系統(tǒng)上并行算法的運行時間，對于任意i有Tp=tie+tio，且Te+To=pTp問題的規(guī)模W為最佳串行算法所完成的計算量W=Te

如果問題規(guī)模W保持不變，處理器數(shù)p增加，開銷To增大，效率E下降。為了維持一定的效率（介于0與1之間），當處理數(shù)p增大時，需要相應地增大問題規(guī)模W的值。由此定義函數(shù)fE（p）為問題規(guī)模W隨處理器數(shù)p變化的函數(shù)，為等效率函數(shù)（ISO-efficiencyFunction）（Kumar1987）等效率度量標準（cont‘d)曲線1表示算法具有很好的擴放性；曲線2表示算法是可擴放的；曲線3表示算法是不可擴放的。優(yōu)點：簡單可定量計算的、少量的參數(shù)計算等效率函數(shù)缺點：如果To無法計算出（在共享存儲并行機中）等速度度量標準p表示處理器個數(shù)，W表示要求解問題的工作量或稱問題規(guī)模，T為并行執(zhí)行時間，定義并行計算的速度V為工作量W除以并行時間Tp個處理器的并行系統(tǒng)的平均速度定義為并行速度V除以處理器個數(shù)p：W是使用p個處理器時算法的工作量，令W’表示當處理數(shù)從p增大到p’時，為了保持整個系統(tǒng)的平均速度不變所需執(zhí)行的工作量，則可得到處理器數(shù)從p到p’時平均速度可擴放度量標準公式等速度度量標準（cont’d）優(yōu)點：直觀地使用易測量的機器性能速度指標來度量缺點：某些非浮點運算可能造成性能的變化并行算法概述

ContentParallelComputingModelBasicTechniquesofParallelAlgorithm71VonNeumannModel馮諾依曼模型72InstructionProcessing73DecodeinstructionEvaluateaddressFetchoperandsfrommemoryExecuteoperationStoreresultFetchinstructionfrommemoryParallelComputingModelComputingmodelBridgebetweenSWandHWgeneralpurposeHW,scalableHWtransportableSWAbstractarchitectureforalgorithmdevelopmentEx)PRAM,BSP,LogP74ParallelProgrammingModelWhatprogrammerusesincodingapplications?SpecifiescommunicationandsynchronizationCommunicationprimitivesexposedtouser-levelrealizestheprogrammingmodelEx)Uniprocessor,Multiprogramming,Dataparallel,message-passing,shared-address-space75AspectsofParallelProcessing76AlgorithmdeveloperApplicationdeveloperInterconnectionNetworkMemoryPPPPMemoryPPPPMemoryPPPPMemoryPPPPMultiprocessorsMultiprocessorsMultiprocessorsMultiprocessorsParallelcomputingmodelParallelprogrammingmodelSystemprogrammerArchitecturedesigner3421MiddlewareParallelComputingModelsPRAMParallelRandomAccessMemoryAsetofpprocessorsGlobalsharedmemoryEachprocessorcanaccessanymemorylocationinonetimestepGloballysynchronizedExecutingsameprograminlockstep77IllustrationofPRAM78P1P2P3PpSharedMemoryCLKPprocessorsconnectedtoasinglesharedmemoryEachprocessorhasauniqueindex.SingleprogramexecutedinMIMDmodeMIMD多指令多數(shù)據(jù)FeaturesModelarchitectureSynchronizedRAMwithcommonclock,butnotSIMDoperation:MIMDNolocalmemoryineachRAMOneglobalsharedmemorysingleaddressspacearchitectureSynchronization,communication,parallelismoverheadarezero.79Features(Cont’d)續(xù)OperationsperstepRead/writeawordfrom/tothememoryLocaloperationAninstructioncouldperformthefollowingthreeoperationsinonecycleFetchoneortwowordsfromthememoryasoperandsPerformanarithmetic/logicoperationStoretheresultbackinmemory80ProblemswithPRAM

(ParallelRandomAccessMemory)Inaccuratedescriptionofreal-worldparallelsystemsUnaccountedcostsLatency(潛伏因素),bandwidth,non-localmemoryaccess,memoryaccesscontention(接入爭用)issues,synchronizationcosts,etcAlgorithmsperceivedtoworkwellinPRAMmayhavepoorperformanceinpractice81PRAMVariants(變種)VariantsarisetomodelsomeofthesecostsEachintroducessomepracticalaspectofmachineGivesalgorithmdesignerbetterideaforoptimizationVariantscanbegroupedinto4categoriesMemoryaccessSynchronizationLatencyBandwidth82MemoryAccessImpracticaltohaveconcurrentreadandwritetosamememorylocation(不能同時讀寫存儲器)ContentionissuesCRCWPRAM(并發(fā)讀并發(fā)寫)CPRAM-CRCW(CommonPRAM-CRCW)：僅允許寫入相同數(shù)據(jù)PPRAM-CRCW(PriorityPRAM-CRCW)：僅允許優(yōu)先級最高的處理器寫入APRAM-CRCW(ArbitraryPRAM-CRCW)：允許任意處理器自由寫入EREWorCREWPRAMQRQW(queue-read,queue-write)ExpensiveMultipleportsrequiredforconcurrentaccessmaybeprohibitivelyexpensive.83SynchronizationStandardPRAMgloballysynchronizedStandardPRAMmodeldonotchargeacostforsynchronizationUnrealistic!SynchronizationisnecessaryandexpensiveinpracticalparallelsystemsVariantsmodelcostofsynchronizationAPRAM(asynchronyPRAM):每個處理器有其局部存儲器、局部時鐘、局部程序；無全局時鐘，各處理器異步執(zhí)行；處理器通過SM進行通訊；處理器間依賴關系，需在并行程序中顯式地加入同步路障XPRAM(bulksynchronousPRAM,alsoknownasBSPmodel)Providesanincentiveforalgorithmdesignerstosynchronizeonlywhennecessary84Synchronization(cont.)BPRAM(Block-ParallelRAM)assumes

n

nodes,eachcontainingaprocessorandamemorymodule,interconnectedbyacommunicationmedium.Acomputationisasequenceofphases,calledsupersteps:inonesuperstep,eachprocessorcanexecuteoperationsondataresidinginthelocalmemory;sendmessages;executeaglobalsynchronizationinstruction.ChargeLunitstoaccess1st

messageandbunitsforeachsubsequentcontiguousblock 85Latency等待時間StandardPRAMassumesunit-costfornon-localmemoryaccessInpractice,non-localmemoryaccesshassevereeffectonperformancePRAMvariantLPRAM(Local-memoryPRAM)Asetofnodeseachwithaprocessorandalocalmemory;thenodescancommunicatethroughagloballysharedmemory.Twotypesofsteps(紅色)aredefinedandseparatelyaccountedfor:computationsteps,whereeachprocessorperformsoneoperationonlocaldata,andcommunicationsteps,whereeachprocessorcanwrite,andthenreadawordfromglobalmemoryChargeacostofLunitstoaccessglobalmemory86BandwidthStandardPRAMassumesunlimitedbandwidth

Inpractice,bandwidthislimitedPRAMVariantDRAM(Distributionrandomaccessmachine)2levelmemoryhierarchyAccesstoglobalmemoryischargedacostbasedonpossibledatacongestionPRAM(m)GlobalmemorysegmentedintomodulesAnygivenstep,onlymmemoryaccessescanbeserviced87OtherDistributedModelsDistributedMemoryModelNoglobalmemoryEachprocessorassociatedwithsomelocalmemoryPostalModelProcessorsendsrequestfornon-localmemoryInsteadofstalling,itcontinuesworkingwhiledataisen-route88NetworkModelsFocusonimpactoftopologyofcommunicationsnetworkEarlyfocusofparallelcomputationDistributedMemoryModelCostofremotememoryaccessisafunctionofbothtopologyandtheaccesspatternProvidesincentivesforefficientDatamappingsCommunicationsrouting89LogPModeldesignstronglyinfluencedbytrendsinparallelcomputerdesignModelofadistributedmemorymultiprocessorProcessorscommunicateviapointtopointmessagesAttemptstocaptureimportantbottleneckofparallelmachines90LogPSpecifiesperformancecharacteristicsofcommunicationnetworkProvideincentiveforcleverdataplacementIllustratesimportanceofbalancedcommunication91ParallelMachineTrendsMachineorganizationformostparallelmachinesissimilarAcollectionofcompletecomputersMicroprocessorCachememorySizable(很大的)

DRAMmemoryConnectedbyrobustcommunicationsnetworkNosingleprogrammingmethodologyisdominant92OtherconsiderationsProcessorCountNumberofnodesrelativetopriceofmostexpensivesupercomputer/costofnodeCommunicationIntervallagsfarbehindprocessormemorybandwidthPresenceofadaptiveroutingandfault-recoverynetworkingsystemsAffectsalgorithmdesignParallelalgorithmsdevelopedwithlargenumberofdataelementsperprocessorAttemptstoexploitnetworktopologyorprocessorcountisnotveryrobust93ModelParameters(logP)Latency(L)(等待時間)Delayincurredincommunicatingamessagefromsourcetodestination(延遲)HopcountandHopdelayCommunicationOverhead(o通信消耗)LengthoftimeaprocessorisengagedinsendingorreceivingamessageNodeoverheadforprocessingasendorreceiveCommunicationbandwidth(g通信帶寬)MinimumtimeintervalbetweenmessagesProcessorcount(P處理器數(shù)量)Processorcount94LogPModel95senderreceiveroLgott=兩次通信消耗時間、一次通信延遲時間BulkSynchronousParallelBulk(大塊、大量)SynchronousParallel(BSP)PprocessorswithlocalmemoryRouterFacilitiesforperiodicglobalsynchronizationEverylstepsModelsBandwidthlimitationsLatencySynchronizationcostsDoesnotmodelCommunicationoverheadProcessortopology(布局、拓撲學)96BSPComputerDistributedmemoryarchitecture3componentsNodeProcessorLocalmemoryRouter(CommunicationNetwork)Point-to-point,messagepassing(orsharedvariable)BarriersynchronizingfacilityAllorsubset97IllustrationofBSP98CommunicationNetwork(g)PMPMPMNode(w)NodeNodeBarrier(l)wparameterMaximumcomputationtimewithineachsuperstepComputationoperationtakesatmostwcycles.gparameter#ofcyclesforcommunicationofunitmessagewhenallprocessorsareinvolvedincommunication-networkbandwidthh

ThemaximumnumberofincomingoroutgoingmessagesforasuperstepCommunicationoperationtakesghcycles.lparameterBarriersynchronizationtakeslcycles.BSPProgramABSPcomputationconsistsofSsuperstepsAsuperstepisasequenceofstepsfollowedbyabarriersynchronizationSuperstepAnyremotememoryaccessestakeeffectatbarrier-looselysynchronous99BSPProgram100Superstep1Superstep2BarrierP1P2P3P4ComputationCommunicationModelSurveySummaryNosinglemodelisacceptable!Betweenmodels,subsetofcharacteristicsarefocusedinmajorityofmodelsComputationalParallelismCommunicationLatencyCommunicationOverheadCommunicationBandwidthExecutionSynchronizationMemoryHierarchyNetworkTopology101ComputationalParallelismNumberofphysicalprocessorsStaticversusdynamicparallelismShouldnumberofprocessorsbefixed?Fault-recoverynetworksallowfornodefailureManyparallelsystemsallowincrementalupgradesbyincreasingnodecount102LatencyFixedmessagelengthorvariablemessagelength?Networktopology?CommunicationOverhead?Contentionbasedlatency?Memoryhierarchy?103BandwidthLimitedresourceWithlowlatencyTendencyforbandwidthabusebyfloodingnetwork104SynchronizationAbilitytosolveawideclassofproblemsrequireasynchronousparallelismSynchronizationachievedviamessagepassingSynchronizationasacommunicationcost105UnifiedModel?DifficultParallelmachinesarecomplicatedStillevolvingDifferentusersfromdiversedisciplinesRequiresacommonsetofcharacteristicsderivedfromneedsofdifferentusersAgainneedforbalancebetweendescriptivityandprescriptivity106ContentParallelComputingModelBasicTechniquesofParallelAlgorithm(紅色標注)IntroductiontoParallelAlgorithms(紅色標注)Decomposition(紅色標注)Mapping(紅色標注)107IntroductiontoParallelAlgorithmsTasksandDecomposition任務和分解

ProcessesandMapping處理和映射108Preliminaries:Decomposition,Tasks,and

DependencyGraphsThefirststepindevelopingaparallelalgorithmistodecomposetheproblemintotasksthatcanbeexecutedconcurrentlyAgivenproblemmaybedecomposedintotasksinmanydifferentwaysTasksmaybeofsame,different,oreveninterminatesizesAdecompositioncanbeillustratedintheformofadirectedgraphwithnodescorrespondingtotasksandedgesindicatingthattheresultofonetaskisrequiredforprocessingthenext.Suchagraphiscalledataskdependencygraph

109110開發(fā)一個并行算法的第一個步驟是可并發(fā)執(zhí)行的任務的問題分解成一個給定的問題可以被分解為許多不同的方式中的任務任務可以是相同的，不同的，或甚至無限制的大小的分解，可以用一個帶有節(jié)點相對應的任務和表明是必需的，處理下一個任務的結(jié)果的邊緣的一個有向圖的形式示出。這樣的曲線被稱為任務依賴關系圖Example:MultiplyingaDenseMatrixwithaVector111Computationofeachelementofoutputvectoryisindependentofotherelements.Basedonthis,adensematrix-vectorproductcanbedecomposedintontasks.ThefigurehighlightstheportionofthematrixandvectoraccessedbyTask1.Observations:Whiletaskssharedata(namely,thevectorb),theydonothaveanycontroldependencies-i.e.,notaskneedstowaitforthe(partial)completionofanyother.Alltasksareofthesamesizeintermsofnumberofoperations.Example:DatabaseQueryProcessingConsidertheexecutionofthequery:MODEL=``CIVIC''ANDYEAR=2001AND (COLOR=``GREEN''ORCOLOR=``WHITE)

onthefollowingdatabase:ID#ModelYearColorDealerPrice4523Civic2002BlueMN$18,0003476Corolla1999WhiteIL$15,0007623Camry2001GreenNY$21,0009834Prius2001GreenCA$18,0006734Civic2001WhiteOR$17,0005342Altima2001GreenFL$19,0003845Maxima2001BlueNY$22,0008354Accord2000GreenVT$18,0004395Civic2001RedCA$17,0007352Civic2002RedWA$18,000112Example:DatabaseQueryProcessingTheexecutionofthequerycanbedividedintosubtasksinvariousways.Eachtaskcanbethoughtofasgeneratinganintermediatetableofentriesthatsatisfyaparticularclause.113Decomposingthegivenqueryintoanumberoftasks.Edgesinthisgraphdenotethattheoutputofonetaskisneededtoaccomplishthenext.Example:DatabaseQueryProcessingNotethatthesameproblemcanbedecomposedintosubtasksinotherwaysaswell.114Analternatedecompositionofthegivenproblemintosubtasks,alongwiththeirdatadependencies.Differenttaskdecompositionsmayleadtosignificantdifferenceswithrespecttotheireventualparallelperformance.Granularity(間隔尺寸)ofTaskDecompositionsThenumberoftasksintowhichaproblemisdecomposeddeterminesitsgranularity.Decompositionintoalargenumberoftasksresultsinfine-graineddecompositionandthatintoasmallnumberoftasksresultsinacoarsegraineddecomposition.115Acoarsegrainedcounterparttothedensematrix-vectorproductexample.Eachtaskinthisexamplecorrespondstothecomputationofthreeelementsoftheresultvector.被分解到其中一個問題的任務的數(shù)量決定其粒度。成大量的任務的結(jié)果在細粒分解和分解，在粗粒分解成一個小數(shù)量的任務的結(jié)果。一個粗粒度的對應的密集矩陣向量的產(chǎn)品的一個例子。在這個例子中的每個任務對應的計算的結(jié)果矢量的三個元素。DegreeofConcurrencyThenumberoftasksthatcanbeexecutedinparallelisthedegreeofconcurrency

ofadecomposition.Sincethenumberoftasksthatcanbeexecutedinparallelmaychangeoverprogramexecution,themaximumdegreeofconcurrency

isthemaximumnumberofsuchtasksatanypointduringexecution.Theaveragedegreeofconcurrency

istheaveragenumberoftasksthatcanbeprocessedinparallelovertheexecutionoftheprogram.Thedegreeofconcurrencyincreasesasthedecompositionbecomesfineringranularityandviceversa.116117可以被并行執(zhí)行的任務的數(shù)量是一個分解的并發(fā)性的程度。因為可以并行執(zhí)行的任務的數(shù)量可能會改變程序的執(zhí)行，最大程度的并發(fā)性是在任何時候，在執(zhí)行這些任務的最大數(shù)量。并發(fā)的平均程度是，可以在程序的執(zhí)行并行處理的任務的平均數(shù)目。并發(fā)的分解增加的程度變得更細的粒度，反之亦然。CriticalPathLengthAdirectedpathinthetaskdependencygraphrepresentsasequenceoftasksthatmustbeprocessedoneaftertheother.Thelongestsuchpathdeterminestheshortesttimeinwhichtheprogramcanbeexecutedinparallel.Thelengthofthelongestpathinataskdependencygraphiscalledthecriticalpathlength.118CriticalPathLengthConsiderthetaskdependencygraphsofthetwodatabasequerydecompositions:119Whatarethecriticalpathlengthsforthetwotaskdependencygraphs?Howmanyprocessorsareneededineachcasetoachievethisminimumparallelexecutiontime?Whatisthemaximumdegreeofconcurrency?TaskInteractionGraphsSubtasksgenerallyexchangedatawithothersinadecomposition.Forexample,eveninthetrivialdecompositionofthedensematrix-vectorproduct,ifthevectorisnotreplicatedacrossalltasks,theywillhavetocommunicateelementsofthevector.Thegraphoftasks(nodes)andtheiri