并行算法的同步課件

2023/9/5

ParallelAlgorithms

Chapter

1

FoundationofParallelAlgorithmsSpring,

20172023/7/31

ParallelAlgorithms

2023/9/5主要內(nèi)容1.1并行計(jì)算機(jī)體系結(jié)構(gòu)并行計(jì)算機(jī)的分類并行計(jì)算機(jī)的互連方式1.2并行計(jì)算模型

PRAM模型異步APRAM模型BSP模型LogP模型1.3并行算法的一般概念并行算法的定義和分類相關(guān)性與可并行化并行算法的表示并行算法的復(fù)雜度并行算法的WT表示加速比性能定律并行算法的同步和通訊2023/7/31主要內(nèi)容1.1并行計(jì)算機(jī)體系結(jié)構(gòu)2023/9/51.1并行計(jì)算機(jī)的體系結(jié)構(gòu):并行計(jì)算機(jī)分類Flynn分類（1966年）

(1)單指令流單數(shù)據(jù)流機(jī)SISD，即傳統(tǒng)的單處理機(jī)(2)單指令流多數(shù)據(jù)流機(jī)SIMD(3)多指令流單數(shù)據(jù)流機(jī)MISD，實(shí)際中不存在的機(jī)器(4)多指令流多數(shù)據(jù)流機(jī)MIMD并行機(jī)的結(jié)構(gòu)模型－實(shí)際的機(jī)器體系結(jié)構(gòu)－SIMD(SingleInstructionMultipleData,單指令流多數(shù)據(jù)流機(jī))

－PVP(ParallelVectorProcessor,并行向量機(jī))

－SMP(SymmetricMultiprocessor,對(duì)稱多處理機(jī))

－MPP(MassivelyParallelProcessor,大規(guī)模并行處理機(jī))

－COW(ClusterofWorkstation,工作站機(jī)群)

－DSM(DistributedSharedMemory,分布共享存儲(chǔ)多處理機(jī))

注：SIMD是專用并行機(jī)，后5種屬于MIMD并行機(jī)。2023/7/311.1并行計(jì)算機(jī)的體系結(jié)構(gòu):并行計(jì)算機(jī)2023/9/5SISDcomputer-VonNeumann'smodel1.1并行計(jì)算機(jī)的體系結(jié)構(gòu):并行計(jì)算機(jī)分類SIMDcomputer2023/7/31SISDcomputer-VonNe2023/9/5Symmetricmultiprocessor–MIMD-SM1.1并行計(jì)算機(jī)的體系結(jié)構(gòu):并行計(jì)算機(jī)分類Massivelyparallelprocessor–MIMD-DM2023/7/31Symmetricmultiproces2023/9/5Clusterofworkstations–MIMD-DM1.1并行計(jì)算機(jī)的體系結(jié)構(gòu):并行計(jì)算機(jī)分類2023/7/31Clusterofworkstatio2023/9/5VPVPVP…交叉開關(guān)SM(a)PVPP/CP/CP/C…總線或交叉開關(guān)SM(b)SMP,物理上單一地址空間P/CP/CP/C…定制網(wǎng)絡(luò)LMLMLM(c)MPP,物理/邏輯上多地址空間P/CP/CP/C…定制網(wǎng)絡(luò)LMLMLM虛擬分布共享存儲(chǔ)(DSM)(d)DSM(MPP/Cluster),邏輯上單一地址空間結(jié)構(gòu)模型－物理機(jī)模型P/CP/CP/C…定制/標(biāo)準(zhǔn)網(wǎng)絡(luò)LMLMLM(e)Cluster/COW,物理/邏輯上多地址空間1.1并行計(jì)算機(jī)的體系結(jié)構(gòu):并行計(jì)算機(jī)分類2023/7/31VPVPVP…交叉開關(guān)SM(a)PVPP2023/9/5SMPMPPMPP…WANLMDSMSM(h)Grid(ClusterofClusters)SMPSMPSMP…SAN/LANSMSMSMMPPMPPMPP…SAN/LANDSMDSMDSM(f)SMP-Cluster(g)DSM-Cluster結(jié)構(gòu)模型－物理機(jī)模型1.1并行計(jì)算機(jī)的體系結(jié)構(gòu):并行計(jì)算機(jī)分類2023/7/31SMPMPPMPP…WANLMDSMSM(2023/9/51.1并行計(jì)算機(jī)的體系結(jié)構(gòu):互連方式靜態(tài)互連網(wǎng)絡(luò)(固定連接)

connectedgraphvertices=processingnodesedges=communicationlinks(1)一維線性連接LA(1-DLinearArray)—一維陣列不帶環(huán)繞的1-DLA，帶環(huán)繞的1-DLA(2)網(wǎng)孔連接MC(MeshConnected)—二維陣列不帶環(huán)繞的MC，帶環(huán)繞的MC2023/7/311.1并行計(jì)算機(jī)的體系結(jié)構(gòu):互連方式靜2023/9/51.1并行計(jì)算機(jī)的體系結(jié)構(gòu):互連方式靜態(tài)互連網(wǎng)絡(luò)

(3)樹形連接TC(TreeConnected)二叉樹，胖樹2023/7/311.1并行計(jì)算機(jī)的體系結(jié)構(gòu):互連方式靜2023/9/51.1并行計(jì)算機(jī)的體系結(jié)構(gòu):互連方式靜態(tài)互連網(wǎng)絡(luò)

(4)樹網(wǎng)連接MT(Meshoftree)

2023/7/311.1并行計(jì)算機(jī)的體系結(jié)構(gòu):互連方式靜2023/9/51.1并行計(jì)算機(jī)的體系結(jié)構(gòu):互連方式靜態(tài)互連網(wǎng)絡(luò)(5)金字塔連接(Pyramid)(6)超立方連接HC(HypercubeConnected)3－立方，4－立方(7)立方環(huán)連接CCC(CubeConnected-Cycles)(8)洗牌交換連接SE(ShuffleExchange)(9)蝶形連接(ButterflyConnected)2023/7/311.1并行計(jì)算機(jī)的體系結(jié)構(gòu):互連方式靜2023/9/51.1并行計(jì)算機(jī)的體系結(jié)構(gòu):互連方式靜態(tài)互連網(wǎng)絡(luò):嵌入將網(wǎng)絡(luò)中的各節(jié)點(diǎn)映射到另一個(gè)網(wǎng)絡(luò)中去用膨脹（Dilation）系數(shù)來(lái)描述嵌入的質(zhì)量，它是指被嵌入網(wǎng)絡(luò)中的一條鏈路在所要嵌入的網(wǎng)絡(luò)中對(duì)應(yīng)所需的最大鏈路數(shù)如果該系數(shù)為1，則稱為完美嵌入。環(huán)網(wǎng)可完美嵌入到2-D環(huán)繞網(wǎng)中超立方網(wǎng)可完美嵌入到2－D環(huán)繞網(wǎng)中2023/7/311.1并行計(jì)算機(jī)的體系結(jié)構(gòu):互連方式靜2023/9/51.1并行計(jì)算機(jī)的體系結(jié)構(gòu):互連方式靜態(tài)互連網(wǎng)絡(luò):嵌入Ringonto2-Dtorus

Hypercubeonto2-Dtorus2023/7/311.1并行計(jì)算機(jī)的體系結(jié)構(gòu):互連方式靜2023/9/51.1并行計(jì)算機(jī)的體系結(jié)構(gòu):互連方式動(dòng)態(tài)互連網(wǎng)絡(luò)(非固定連接)(1)總線Bus(2)交叉開關(guān)CrossbarSwitcher：一種高帶寬網(wǎng)絡(luò)(3)多級(jí)互連網(wǎng)絡(luò)MultistageInterconnectionNetwork一種大型開關(guān)網(wǎng)絡(luò)

2023/7/311.1并行計(jì)算機(jī)的體系結(jié)構(gòu):互連方式動(dòng)2023/9/5主要內(nèi)容1.1并行計(jì)算機(jī)體系結(jié)構(gòu)并行計(jì)算機(jī)的分類并行計(jì)算機(jī)的互連方式1.2并行計(jì)算模型

PRAM模型異步APRAM模型BSP模型LogP模型1.3并行算法的一般概念并行算法的定義和分類相關(guān)性與可并行化并行算法的表示并行算法的復(fù)雜度并行算法的WT表示加速比性能定律并行算法的同步和通訊2023/7/31主要內(nèi)容1.1并行計(jì)算機(jī)體系結(jié)構(gòu)2023/9/51.2并行計(jì)算模型:PRAM模型描述由Fortune和Wyllie1978年提出，稱為并行隨機(jī)存取機(jī)器PRAM，又稱SIMD-SM模型。有一個(gè)集中的共享存儲(chǔ)器和一個(gè)指令控制器，通過(guò)SM的R/W交換數(shù)據(jù)，隱式同步計(jì)算。假設(shè)SM的容量無(wú)限有限/無(wú)限個(gè)功能相同的處理器本地指令和SM的R/W操作都取單位時(shí)間結(jié)構(gòu)圖ControlUnitInterconnectionNetworkPLMPLMPLMPLMSharedMemory2023/7/311.2并行計(jì)算模型:PRAM模型描述C2023/9/51.2并行計(jì)算模型:PRAM模型分類PRAM-CRCW并發(fā)讀并發(fā)寫CPRAM-CRCW(CommonPRAM-CRCW)：僅允許寫入相同數(shù)據(jù)PPRAM-CRCW(PriorityPRAM-CRCW)：僅允許優(yōu)先級(jí)最高的處理器寫入APRAM-CRCW(ArbitraryPRAM-CRCW)：允許任意處理器自由寫入PRAM-CREW并發(fā)讀互斥寫PRAM-EREW互斥讀互斥寫計(jì)算能力比較PRAM-CRCW是最強(qiáng)的計(jì)算模型，PRAM-EREW可logp倍模擬PRAM-CREW和PRAM-CRCW。令Tm是在模型M上的運(yùn)行時(shí)間，則：1979年，Eckstain曾經(jīng)使用二叉樹方法來(lái)解決沖突問(wèn)題解決讀沖突：只允許一個(gè)PE從共享存儲(chǔ)單元取內(nèi)容。解決寫沖突：用樹作一種競(jìng)賽機(jī)構(gòu)，確保僅有一個(gè)PE在寫。2023/7/311.2并行計(jì)算模型:PRAM模型分類2023/9/51.2并行計(jì)算模型:PRAM模型優(yōu)點(diǎn)適合并行算法表示和復(fù)雜性分析，易于使用，隱藏了并行機(jī)的通訊、同步等細(xì)節(jié)。缺點(diǎn)不適合MIMD并行機(jī)，忽略了SM的競(jìng)爭(zhēng)、通訊延遲等因素推廣存儲(chǔ)競(jìng)爭(zhēng)模型：將Memory分成一些模塊，每個(gè)模塊一次可處理一個(gè)訪問(wèn)，可以在模塊級(jí)處理存儲(chǔ)器的競(jìng)爭(zhēng)。延遲模型：考慮了信息的產(chǎn)生到能夠使用之間的通信延遲

。局部PRAM模型：考慮了存儲(chǔ)帶寬，假定每個(gè)PE均有無(wú)限局存，而訪問(wèn)全局存儲(chǔ)器是十分昂貴的。

分層存儲(chǔ)模型：將存儲(chǔ)器視為分層的存儲(chǔ)模塊，每個(gè)模塊由其大小及傳送時(shí)間表征。異步PRAM模型2023/7/311.2并行計(jì)算模型:PRAM模型優(yōu)點(diǎn)2023/9/51.2并行計(jì)算模型:SIMD-IN模型描述又稱SIMD-DM模型，分布式存儲(chǔ)，處理器通過(guò)互連網(wǎng)絡(luò)相連，用傳遞數(shù)據(jù)方式實(shí)現(xiàn)通訊，算法時(shí)間復(fù)雜性考慮計(jì)算和選路(時(shí)間)，結(jié)構(gòu)圖如下：

常見模型SIMD-LC一維線性連接SIMD-MC網(wǎng)孔連接SIMD-TC樹形連接SIMD-MT樹網(wǎng)連接SIMD-HC超立方連接SIMD-CCC立方環(huán)連接SIMD-SE洗牌交換連接2023/7/311.2并行計(jì)算模型:SIMD-IN模型2023/9/51.2并行計(jì)算模型:異步APRAM模型描述又稱分相（Phase）PRAM或MIMD-SM。每個(gè)處理器有其局部存儲(chǔ)器、局部時(shí)鐘、局部程序；無(wú)全局時(shí)鐘，各處理器異步執(zhí)行；處理器通過(guò)SM進(jìn)行通訊；處理器間依賴關(guān)系，需在并行程序中顯式地加入同步路障。指令類型(1)全局讀(2)全局寫(3)局部操作(4)同步

2023/7/311.2并行計(jì)算模型:異步APRAM模型2023/9/51.2并行計(jì)算模型:異步APRAM模型計(jì)算過(guò)程由同步障分開的全局相組成

，*號(hào)表示局部操作。2023/7/311.2并行計(jì)算模型:異步APRAM模型2023/9/51.2并行計(jì)算模型:異步APRAM模型計(jì)算時(shí)間

設(shè)局部操作為單位時(shí)間；全局讀/寫平均時(shí)間為d，d隨著處理器數(shù)目的增加而增加；同步路障時(shí)間為B=B(p)非降函數(shù)。令為全局相內(nèi)各處理器執(zhí)行時(shí)間最長(zhǎng)者，則APRAM上的計(jì)算時(shí)間為

優(yōu)缺點(diǎn)

易編程和分析算法的復(fù)雜度，其上并行算法比較有限，不適合MIMD-DM模型。

2023/7/311.2并行計(jì)算模型:異步APRAM模型2023/9/51.2并行計(jì)算模型:BSP模型描述由Valiant(1990)提出的，“塊”同步模型，是一種異步MIMD-DM模型，支持消息傳遞系統(tǒng)，塊內(nèi)異步并行，塊間顯式同步。

模型參數(shù)p：處理器數(shù)(帶有存儲(chǔ)器)L：同步障時(shí)間(Barriersynchronizationtime)g：選路器吞吐率（帶寬因子）發(fā)送一個(gè)消息所用的時(shí)間，帶寬因子(timesteps/packet)=1/bandwidth2023/7/311.2并行計(jì)算模型:BSP模型描述2023/9/51.2并行計(jì)算模型:BSP模型計(jì)算過(guò)程由若干超級(jí)步組成，每個(gè)超級(jí)步計(jì)算模式為右圖優(yōu)缺點(diǎn)

強(qiáng)調(diào)了計(jì)算和通訊的分離，提供了一個(gè)編程環(huán)境，易于程序復(fù)雜性分析。但需要顯式同步機(jī)制，限制至多h條消息的傳遞等。2023/7/311.2并行計(jì)算模型:BSP模型計(jì)算過(guò)程2023/9/51.2并行計(jì)算模型:LogP模型描述由Culler(1993)年提出的，是一種分布存儲(chǔ)的、點(diǎn)到點(diǎn)通訊的多處理機(jī)模型，其中通訊由一組參數(shù)描述，實(shí)行隱式同步。模型參數(shù)L(Latency)：通迅延遲o(overhead)：通訊額外開銷g(gap)：g=1/bandwidth,處理器可連續(xù)進(jìn)行消息發(fā)送或接收的最小時(shí)間間隔P：#processors注：L和g反映了通訊網(wǎng)絡(luò)的容量

2023/7/311.2并行計(jì)算模型:LogP模型描述2023/9/51.2并行計(jì)算模型:LogP模型優(yōu)缺點(diǎn)捕捉了MPC的通訊瓶頸，隱藏了并行機(jī)的網(wǎng)絡(luò)拓?fù)?、路由、協(xié)議，可以應(yīng)用到共享存儲(chǔ)、消息傳遞、數(shù)據(jù)并行的編程模型中；但難以進(jìn)行算法描述、設(shè)計(jì)和分析。BSPvs.LogPBSP

LogP：BSP塊同步

BSP子集同步

BSP進(jìn)程對(duì)同步＝LogPBSP可以常數(shù)因子模擬LogP，LogP可以對(duì)數(shù)因子模擬BSPBSP＝LogP+Barriers－OverheadBSP提供了更方便的程設(shè)環(huán)境，LogP更好地利用了機(jī)器資源BSP似乎更簡(jiǎn)單、方便和符合結(jié)構(gòu)化編程

2023/7/311.2并行計(jì)算模型:LogP模型優(yōu)缺點(diǎn)2023/9/51.2并行計(jì)算模型:各種計(jì)算模型比較模型屬性PRAMAPRAMBSPLogPC3體系結(jié)構(gòu)SIMD-SMMIMD-SMMIMD-DMMIMD-DMMIMD-DM計(jì)算模式同步異步異步異步異步同步方式自動(dòng)同步路障同步路障同步隱式同步路障同步模型參數(shù)單位時(shí)間步d,讀/寫時(shí)間B,同步時(shí)間p,處理器數(shù)g,帶寬因子l,同步間隔L,通信延遲o,額外開銷g,帶寬因子P,處理器數(shù)l,信包長(zhǎng)度s,發(fā)送建立時(shí)間h,通信延遲計(jì)算粒度細(xì)粒度/中粒度中粒度/粗粒度中粒度/粗粒度中粒度/粗粒度粗粒度通信方式讀/寫共享變量讀/寫共享變量發(fā)送/接收消息發(fā)送/接收消息發(fā)送/接收消息地址空間全局地址空間單地址空間單/多地址空間單/多地址空間多地址空間2023/7/311.2并行計(jì)算模型:各種計(jì)算模型比較2023/9/5主要內(nèi)容1.1并行計(jì)算機(jī)體系結(jié)構(gòu)并行計(jì)算機(jī)的分類并行計(jì)算機(jī)的互連方式1.2并行計(jì)算模型

PRAM模型異步APRAM模型BSP模型LogP模型1.3并行算法的一般概念并行算法的定義和分類相關(guān)性與可并行化并行算法的表示并行算法的復(fù)雜度并行算法的WT表示加速比性能定律并行算法的同步和通訊2023/7/31主要內(nèi)容1.1并行計(jì)算機(jī)體系結(jié)構(gòu)2023/9/51.3并行算法的一般概念:定義和分類并行算法

一組可同時(shí)執(zhí)行且可互相協(xié)作的諸進(jìn)程的集合。分類

VLSI并行算法：在VLSI計(jì)算模型上開發(fā)的并行算法

2023/7/311.3并行算法的一般概念:定義和分類并2023/9/51.3并行算法的一般概念:并行算法的表示par-do語(yǔ)句

fori=1tonpar-do

或fori=1tondoinparallel......endforendforforall語(yǔ)句

forallPi,where0≤i≤kdo...endfor2023/7/311.3并行算法的一般概念:并行算法的表2023/9/51.3并行算法的一般概念:并行算法的復(fù)雜度串行算法的度量一些記號(hào)平均情形復(fù)雜度、最壞情形復(fù)雜度2023/7/311.3并行算法的一般概念:并行算法的復(fù)2023/9/51.3并行算法的一般概念:并行算法的復(fù)雜度并行算法復(fù)雜性的度量運(yùn)行時(shí)間t(n)：計(jì)算時(shí)間tc和選路(路由)時(shí)間tr處理器數(shù)目p(n)成本c(n)：c(n)=t(n)×p(n)成本最優(yōu)性：若c(n)等于在最壞情形下串行算法所需要的時(shí)間，則并行算法是成本最優(yōu)的。加速比Sp(n)：Sp(n)=ts(n)/tp(n)，其中ts(n)為求解問(wèn)題的最快的串行算法在最壞情形下所需的運(yùn)行時(shí)間，tp(n)為求解同一問(wèn)題的并行算法在最壞情形下的運(yùn)行時(shí)間。注：(1)加速比Sp(n)反映算法的并行性對(duì)運(yùn)行時(shí)間的改進(jìn)程度。

(2)若Sp(n)=p(n)，則達(dá)到線性加速；若Sp(n)>p(n)，則為超線性加速(一般出現(xiàn)在某些特殊的應(yīng)用中，如并行搜索等)。并行效率Ep(n)：Ep(n)=Sp(n)/p(n)，0<Ep(n)<=1注：反映了并行系統(tǒng)中處理器的利用程度。工作量(或運(yùn)算量)W(n)：并行算法所執(zhí)行的總操作步數(shù)。(與處理器的數(shù)目無(wú)關(guān))2023/7/311.3并行算法的一般概念:并行算法的復(fù)2023/9/51.3并行算法的一般概念:并行算法的WT表示Brent定理(1974JACM)

令W(n)是一并行算法A在運(yùn)行時(shí)間T(n)內(nèi)執(zhí)行的運(yùn)算量，則A使用p臺(tái)處理器可在時(shí)間t(n)=O(W(n)/p+T(n))內(nèi)執(zhí)行完成。證明：設(shè)時(shí)刻并行算法A做的工作量為Wi(即在(i-1,i]時(shí)段內(nèi)的工作量)==>用p臺(tái)處理器去完成并行算法A的第i時(shí)刻工作量，需時(shí)間

==>用p臺(tái)處理器模擬并行算法A的總時(shí)間為2023/7/311.3并行算法的一般概念:并行算法的W2023/9/51.3并行算法的一般概念:并行算法的WT表示Brent定理注：(1)揭示了并行算法工作量和運(yùn)行時(shí)間的關(guān)系；

(2)提供了并行算法的WT(Work-Time)表示方法；(3)告訴我們：設(shè)計(jì)并行算法時(shí)應(yīng)盡可能將每個(gè)時(shí)間步的工作量均勻地分?jǐn)偨op臺(tái)處理器，使各處理器處于活躍狀態(tài)。2023/7/311.3并行算法的一般概念:并行算法的W2023/9/51.3并行算法的一般概念:并行算法的WT表示例1令n=2k(k>=0)，求n個(gè)數(shù)和的并行算法。算法運(yùn)行時(shí)間：t(n)=O(logn)總運(yùn)算量:由Brent定理知:t(n)=O(n/p+logn)

2023/7/311.3并行算法的一般概念:并行算法的W2023/9/51.3并行算法的一般概念:并行算法的WT表示2023/7/311.3并行算法的一般概念:并行算法的W2023/9/51.3并行算法的一般概念:加速比性能定律Amdahl’sLaw:BaseonFixedProblemSize適用于實(shí)時(shí)應(yīng)用問(wèn)題。當(dāng)問(wèn)題的計(jì)算負(fù)載或規(guī)模固定時(shí)，我們必須通過(guò)增加處理器數(shù)目來(lái)降低計(jì)算時(shí)間；設(shè)f是算法中不能并行的串行部分比例，Ws和Wp分別是串行和并行部分的工作量，則總工作量W=fW+(1-f)W=Ws+Wp；Amdahl’slaw表明：加速比受到算法中串行工作量的限制。公式推導(dǎo)2023/7/311.3并行算法的一般概念:加速比性能定2023/9/51.3并行算法的一般概念:加速比性能定律Gustafson’sLaw:BaseonFixedExecutionTime適用于要求精度高的應(yīng)用，通過(guò)加大計(jì)算量來(lái)提高計(jì)算精度。Gustafson’sLaw表明：隨著處理器數(shù)目的增加，串行執(zhí)行部分f不再是并行算法的瓶頸。放大問(wèn)題工作量或規(guī)模的加速公式推導(dǎo)：

與p成線性關(guān)系。2023/7/311.3并行算法的一般概念:加速比性能定2023/9/51.3并行算法的一般概念:加速比性能定律Sun&Ni’sLaw:BaseonMemoryBounding充分利用存儲(chǔ)空間等計(jì)算資源，盡量增大問(wèn)題規(guī)模以產(chǎn)生更好/更精確的解。是Amdahl定律和Gustafson定律的推廣。公式推導(dǎo)：設(shè)單機(jī)上的存儲(chǔ)器容量為M，其工作負(fù)載W=fW+(1-f)W當(dāng)并行系統(tǒng)有p個(gè)結(jié)點(diǎn)時(shí)，存儲(chǔ)容量擴(kuò)大了pM，用G(p)表示系統(tǒng)的存儲(chǔ)容量增加p倍時(shí)工作負(fù)載的增加量。則存儲(chǔ)容量擴(kuò)大后的工作負(fù)載為W=fW+(1-f)G(p)W，所以，存儲(chǔ)受限的加速為特別地：當(dāng)G(p)=1時(shí)，為Amdahl定律；當(dāng)G(p)=p時(shí)，為Gustafson定律；2023/7/311.3并行算法的一般概念:加速比性能定2023/9/51.3并行算法的一般概念:并行算法的同步同步概念同步是在時(shí)間上強(qiáng)使各執(zhí)行進(jìn)程在某一點(diǎn)必須互相等待，確保各進(jìn)程的正常順序和對(duì)共享可寫數(shù)據(jù)的正確訪問(wèn)；可用軟件、硬件和固件的辦法來(lái)實(shí)現(xiàn)。同步語(yǔ)句示例算法1.3APRAM上的求和算法輸入：A=(a0,…,an-1),處理器數(shù)p

輸出：S=ΣaiBegin(1)S=0(2.3)lock(S)(2)forallPiwhere0≤i≤p-1doS=S+L(2.1)L=0(2.4)unlock(S)(2.2)forj=itonsteppdoendfor