并行算法的設(shè)計(jì)與(1)

1、并行算法設(shè)計(jì)與分析并行算法設(shè)計(jì)與分析 鐘誠(chéng)鐘誠(chéng)3236396， 教材陳國(guó)良.并行算法的設(shè)計(jì)與分析，第3版.北京:高等教育出版社,2009參考書1 陳國(guó)良. 并行計(jì)算結(jié)構(gòu)算法 編程, 第3版. 北京：高等 教育出版社,20112 陳國(guó)良等. 并行算法實(shí)踐.北京：高等教育出版社,20043 蘇德富,鐘誠(chéng). 計(jì)算機(jī)算法設(shè)計(jì)與分析,第2版. 北京：電子 工業(yè)出版社, 20054 C. Xavier, S. S. Iyenger著, 張?jiān)迫茸g. 并行算法導(dǎo)論.北京： 機(jī)械工業(yè)出版社, 19985 Ananth Grama. 并行計(jì)算導(dǎo)論, 第2版,英文版. 北京:機(jī)械 工業(yè)出版社,2003為什么需要學(xué)

2、習(xí)研究并行算法？v 計(jì)算機(jī)算法+數(shù)據(jù)結(jié)構(gòu)=計(jì)算機(jī)程序。v 計(jì)算機(jī)程序計(jì)算機(jī)程序+文檔文檔+控制數(shù)據(jù)控制數(shù)據(jù)=計(jì)算機(jī)軟件。計(jì)算機(jī)軟件。v 計(jì)算機(jī)軟件+市場(chǎng)=（精神與物質(zhì)的）財(cái)富。v 并行計(jì)算機(jī)并行計(jì)算機(jī)、并行算法可以顯著加速大規(guī)模、復(fù)并行算法可以顯著加速大規(guī)模、復(fù)雜問題的處理（求解）速度，可以獲得問題的更雜問題的處理（求解）速度，可以獲得問題的更精確（更好）的解。精確（更好）的解。v 客觀世界的一切事物（對(duì)象）及其活動(dòng)都是并發(fā)（并行）進(jìn)行的，將事物（對(duì)象）及其活動(dòng)映射 成計(jì)算機(jī)軟件解時(shí)，設(shè)計(jì)開發(fā)的計(jì)算機(jī)軟件（計(jì)算機(jī)程序、計(jì)算機(jī)算法）自然也應(yīng)當(dāng)是并行的！版權(quán)聲明 本教學(xué)PPT僅供課堂教學(xué)教師使用第

3、一章 緒論1.1 引言引言 1. 并行處理并行處理 (Parallel Processing) 挖掘計(jì)算挖掘計(jì)算(Computing)過程的并發(fā)事件的信息處理過程的并發(fā)事件的信息處理. 2. 并發(fā)性并發(fā)性 (Concurrency) 并行性并行性(Parallelism) 同時(shí)性同時(shí)性(Simultaneity) 流水線流水線(Pipelining) 3. 并行處理的級(jí)別并行處理的級(jí)別(Parallel Processing Level) 指令級(jí)并行指令級(jí)并行(Instruction Level Parallelism-ILP, 指令內(nèi)部并行指令內(nèi)部并行,指令之間并行指令之間并行) 細(xì)粒度并行

4、細(xì)粒度并行 (fine grain parallelism/ tiny granularity parallelism ) 線程級(jí)并行線程級(jí)并行(Thread Level Parallelism-TLP) 中細(xì)粒度并行中細(xì)粒度并行 (fine- medium grain parallelism) 進(jìn)程級(jí)進(jìn)程級(jí)(Process Level Parallelism-PLP)/過程級(jí)過程級(jí)/算法級(jí)并行算法級(jí)并行 中粒度并行中粒度并行 (medium grain parallelism) 任務(wù)級(jí)并行任務(wù)級(jí)并行(Task Level Parallel) 粗粒度并行粗粒度并行 (coarse grain

5、parallelism) 4. 并行計(jì)算并行計(jì)算(Parallel Computing)學(xué)科學(xué)科 并行計(jì)算機(jī)體系結(jié)構(gòu)并行計(jì)算機(jī)體系結(jié)構(gòu) (Parallel Computer Architectures) 并行算法并行算法 (Parallel Algorithms) 并行程序設(shè)計(jì)并行程序設(shè)計(jì) (Parallel Programming)5. 多核處理器（多核處理器（Multi-core Processors，又稱片上多處理器，又稱片上多處理器-Chip Multi-Processor, CMP） 、眾核處理器、眾核處理器(Many-core Processors, 如如GPU)、多線程并行技術(shù)、

6、多線程并行技術(shù)(Multi-thread Parallel Techniques) 的出現(xiàn)與應(yīng)用，使得并行算法的研究與開發(fā)顯得極其的出現(xiàn)與應(yīng)用，使得并行算法的研究與開發(fā)顯得極其迫切且富有挑戰(zhàn)性。迫切且富有挑戰(zhàn)性。第一章 緒論1.2 并行算法的硬件基礎(chǔ)并行算法的硬件基礎(chǔ)1.2.1 并行計(jì)算機(jī)的體系結(jié)構(gòu)并行計(jì)算機(jī)的體系結(jié)構(gòu): 并行計(jì)算機(jī)分類并行計(jì)算機(jī)分類v Flynn分類（分類（1966年）年） (1) 單指令流單數(shù)據(jù)流機(jī)器單指令流單數(shù)據(jù)流機(jī)器SISD，即傳統(tǒng)的單處理機(jī)，即傳統(tǒng)的單處理機(jī) (2) 單指令流多數(shù)據(jù)流機(jī)器單指令流多數(shù)據(jù)流機(jī)器SIMD-Single Instruction Stream

7、Multiple Data Stream (3) 多指令流單數(shù)據(jù)流機(jī)器多指令流單數(shù)據(jù)流機(jī)器MISD （目前無實(shí)際的商用機(jī)器目前無實(shí)際的商用機(jī)器） (4) 多指令流多數(shù)據(jù)流機(jī)器多指令流多數(shù)據(jù)流機(jī)器MIMD-Multiple Instruction Stream Multiple Data Streamv 并行機(jī)的結(jié)構(gòu)模型并行機(jī)的結(jié)構(gòu)模型實(shí)際的機(jī)器體系結(jié)構(gòu)實(shí)際的機(jī)器體系結(jié)構(gòu) PVP (Parallel Vector Processor, 并行向量機(jī)并行向量機(jī)) SIMD 陣列處理器（陣列處理器（SIMD PE） SMP (Symmetric Multiprocessor, 對(duì)稱多處理機(jī)對(duì)稱多處理機(jī)

8、) MPP (Massively Parallel Processor, 大規(guī)模并行處理機(jī)大規(guī)模并行處理機(jī)) Clusters ( 工作站機(jī)群工作站機(jī)群Workstation-Cluster, PC機(jī)群機(jī)群PC-Cluster, SMP機(jī)群機(jī)群 SMP-Cluster等等)；目前大部分目前大部分“超級(jí)并行計(jì)算機(jī)超級(jí)并行計(jì)算機(jī)”均采用均采用Clusters結(jié)構(gòu)結(jié)構(gòu) DSM (Distributed Shared Memory, 分布共享存儲(chǔ)多處理機(jī)分布共享存儲(chǔ)多處理機(jī)) 第一章 緒論1.2.1 并行計(jì)算機(jī)的體系結(jié)構(gòu)并行計(jì)算機(jī)的體系結(jié)構(gòu): 并行計(jì)算機(jī)分類并行計(jì)算機(jī)分類 結(jié)構(gòu)模型物理機(jī)模型VPVPV

9、P交叉開關(guān)交叉開關(guān)SM(a) PVPP/CP/CP/C總線或交叉開關(guān)總線或交叉開關(guān)SM(b) SMP, 物理上單一地址空間物理上單一地址空間P/CP/CP/C定制網(wǎng)絡(luò)定制網(wǎng)絡(luò)LMLMLM虛擬分布共享存儲(chǔ)虛擬分布共享存儲(chǔ)(DSM) (d) DSM (MPP/Cluster),邏輯上單一地址空間邏輯上單一地址空間P/CP/CP/C定制網(wǎng)絡(luò)定制網(wǎng)絡(luò)LMLMLM(c) MPP, 物理物理/邏輯上多地址空間邏輯上多地址空間P/CP/CP/C定制定制/標(biāo)準(zhǔn)網(wǎng)絡(luò)標(biāo)準(zhǔn)網(wǎng)絡(luò)LMLMLM(e) Cluster/COW, 物理物理/邏輯上多地址空間邏輯上多地址空間第一章 緒論1.2.1 并行計(jì)算機(jī)的體系結(jié)構(gòu)并行計(jì)算

10、機(jī)的體系結(jié)構(gòu): 并行計(jì)算機(jī)分類并行計(jì)算機(jī)分類 結(jié)構(gòu)模型物理機(jī)模型SMPSMPSMPSAN/LANSMSMSMMPPMPPMPPSAN/LANDSMDSMDSM(f) SMP-Cluster(g) DSM-ClusterSMPMPPMPPWANLMDSMSM(h) Grid (Cluster of Clusters)1.2.1 并行計(jì)算機(jī)的互連網(wǎng)絡(luò)并行計(jì)算機(jī)的互連網(wǎng)絡(luò)v 靜態(tài)互連網(wǎng)絡(luò)靜態(tài)互連網(wǎng)絡(luò)(固定連接固定連接) connected graph: vertices = processing nodes, edges = communication links(1) 一維線性連接一維線性連接LA

11、(1-D Linear Array): 一維陣列一維陣列 不帶環(huán)繞的1-D LA，帶環(huán)繞的1-D LA, 通信直徑n-1, n處理器數(shù)(2) 網(wǎng)孔連接網(wǎng)孔連接MC (Mesh Connected): 二維陣列二維陣列 互連函數(shù): MC2+1(p)=(p+1) mod n, MC2-1(p)=(p-1) mod n MC2+n 1/2(p)=(p+n1/2) mod n, MC2-n 1/2(p)=(p-n1/2) mod n, p處理器編號(hào) 不帶環(huán)繞的MC，帶環(huán)繞的MC , 通信直徑n1/2-1,1.2.1 并行計(jì)算機(jī)的互連網(wǎng)絡(luò)并行計(jì)算機(jī)的互連網(wǎng)絡(luò)v 網(wǎng)孔結(jié)構(gòu)的擴(kuò)展網(wǎng)孔結(jié)構(gòu)的擴(kuò)展: 可重構(gòu)網(wǎng)孔

12、可重構(gòu)網(wǎng)孔 RMESH (Reconfigurable Mesh) 網(wǎng)孔+可重構(gòu)總線 動(dòng)態(tài)重新設(shè)置并行計(jì)算機(jī)的互連結(jié)構(gòu)，例如可動(dòng)態(tài)設(shè)置成多條行總線、列總線或者對(duì)角線總線處理機(jī)陣列結(jié)構(gòu)，也可動(dòng)態(tài)將規(guī)模n n的二維RMESH結(jié)構(gòu)設(shè)置成n個(gè)規(guī)模n1/2 n1/2的子MESH結(jié)構(gòu)。每個(gè)處理器通過四個(gè)端口（N,E,S,W）與總線相連，在處理器內(nèi)部有6個(gè)開關(guān)控制這四個(gè)端口之間的連接關(guān)系，如圖a所示。這四個(gè)端口之間共有15種連接方式，如圖b所示。 123123iijP(2,3)NESW: 開關(guān)NSEWNSEWNSEWNSEWNEWEWSNE,W,SNEW,S,NE,W,S,NEW,SNNSEWNSEWEWN

13、,SEWS,NNWS,EW,NESNW,SENSEWNSEWNSEWNSEWNE,W,SN,W,ESWS,N,ENW,S,ENE,SWNSEWNSEWNSEWNSEW(a)(b) 2D-RMESH結(jié)構(gòu)1.2.1 并行計(jì)算機(jī)的互連網(wǎng)絡(luò)并行計(jì)算機(jī)的互連網(wǎng)絡(luò)v 靜態(tài)互連網(wǎng)絡(luò)靜態(tài)互連網(wǎng)絡(luò) (3) 樹形連接樹形連接TC(Tree Connected) 二叉樹，通信直徑2(logn-1) 胖樹(X樹） 根結(jié)點(diǎn)處理器負(fù)載過重，瓶頸結(jié)點(diǎn)要求根結(jié)點(diǎn)處理和容錯(cuò)能力強(qiáng)千萬億次神威藍(lán)光超級(jí)并行計(jì)算機(jī)群采用千萬億次神威藍(lán)光超級(jí)并行計(jì)算機(jī)群采用胖樹結(jié)構(gòu)胖樹結(jié)構(gòu)連接機(jī)群中的處理器結(jié)點(diǎn)連接機(jī)群中的處理器結(jié)點(diǎn) 曙光曙光5000

14、A超級(jí)并行計(jì)算機(jī)群系統(tǒng)機(jī)采用超級(jí)并行計(jì)算機(jī)群系統(tǒng)機(jī)采用樹結(jié)構(gòu)樹結(jié)構(gòu)連接機(jī)群中的處理器結(jié)點(diǎn)連接機(jī)群中的處理器結(jié)點(diǎn)1.2.1 并行計(jì)算機(jī)的互連網(wǎng)絡(luò)并行計(jì)算機(jī)的互連網(wǎng)絡(luò)v 靜態(tài)互連網(wǎng)絡(luò)靜態(tài)互連網(wǎng)絡(luò) (4) 樹網(wǎng)連接樹網(wǎng)連接MT(Mesh of tree) 1.2.1 并行計(jì)算機(jī)的互連網(wǎng)絡(luò)并行計(jì)算機(jī)的互連網(wǎng)絡(luò)v 靜態(tài)互連網(wǎng)絡(luò)靜態(tài)互連網(wǎng)絡(luò)(5) 金字塔連接金字塔連接 (Pyramid)(6) 超立方連接超立方連接HC (Hypercube Connected)互連函數(shù): CCi(pm-1 pm-2 pi+1 pi pi-1 p1 p0 )= pm-1 pm-2 pi+1 pi pi-1 p1 p0 其中

15、pm-1 pm-2 pi+1 pi pi-1 p1 p0為處理器編號(hào)的二進(jìn)制表示, pi 為對(duì)pi 求反, i=0m-1, m=log2n, n=2m ; 通信直徑log2n. 不易擴(kuò)展. 例例: n=16, CC0(0000 )= 0001, CC0(0001 )= 0000, CC0(0010 )= 0011, CC0(0011 )= 0010, CC0(0100 )= 0101, CC0(0101 )= 0100, CC0(0110 )= 0111, CC0(0111 )= 0110, CC0(1000 )= 1001, CC0(1001 )= 1000, 3立方立方 4立方立方1.2.

16、1 并行計(jì)算機(jī)的互連網(wǎng)絡(luò)并行計(jì)算機(jī)的互連網(wǎng)絡(luò)v 擴(kuò)展的超立方結(jié)構(gòu)擴(kuò)展的超立方結(jié)構(gòu)-光電超立方機(jī)器光電超立方機(jī)器 立方體內(nèi)的結(jié)點(diǎn)(處理器)由電信號(hào)連接, 超立方體之間用光信號(hào)(光波)連接. 機(jī)器規(guī)模擴(kuò)展容易. 電信號(hào)連接 光信號(hào)連接1.2.1 并行計(jì)算機(jī)的互連網(wǎng)絡(luò)并行計(jì)算機(jī)的互連網(wǎng)絡(luò)v 靜態(tài)互連網(wǎng)絡(luò)靜態(tài)互連網(wǎng)絡(luò)(7)立方環(huán)連接CCC (Cube Connected-Cycles)(8)洗牌交換連接SE(Shuffle Exchange)物理上是SIMD-SM機(jī)器互連函數(shù): SH(pm-1 pm-2 p1 p0 )= pm-2 pm-3 p1 p0 pm-1 ,循環(huán)左移1位, m=logn EX(

17、pm-1 pm-2 p1 p0 )= pm-1 pm-2 p1 p0 , 奇偶相鄰處理器交換數(shù)據(jù) 例: n=8個(gè)處理器的洗牌和交換函數(shù): SH(p)=(0) (1,2,4) (3,6,5 ) (7); EX(p)=(0,1) (2,3) (4,5) (6,7) P0 - P1 (y) P2 - P3 P4 - P5(x) P6-P7特點(diǎn)：位于某個(gè)處理器中的數(shù)據(jù)，連續(xù)洗牌m次之后，數(shù)據(jù)又回到該處理器1.2.1 并行計(jì)算機(jī)的互連網(wǎng)絡(luò)并行計(jì)算機(jī)的互連網(wǎng)絡(luò)v 靜態(tài)互連網(wǎng)絡(luò)靜態(tài)互連網(wǎng)絡(luò)(9) 蝶形連接蝶形連接(Butterfly Connected) 對(duì)于k n的蝶形網(wǎng)絡(luò), k=log2n, 設(shè)Pr,i

18、 (0 r k, 0 i n)表示第r 行第i 列上的處理器,其中第k 行視同第0行. 蝶形網(wǎng)絡(luò)互連函數(shù): Butterfly(Pr,i )= Pr-1,j , r 0, j= i ,或者 j和 i的二進(jìn)制表示從左邊數(shù)起僅在第r 位不同.蝶形網(wǎng)絡(luò)以2j增長(zhǎng)方式展開翅膀, j=0k-1蝶形網(wǎng)絡(luò)通信直徑: k=log2n蝶形網(wǎng)絡(luò)特別適用于離散富立頁變換FFT的并行處理(做成專用的并行處理器).1.2.1 并行計(jì)算機(jī)的互連網(wǎng)絡(luò)并行計(jì)算機(jī)的互連網(wǎng)絡(luò)v 動(dòng)態(tài)互連網(wǎng)絡(luò)(非固定連接)總線Bus, 主要用于構(gòu)造規(guī)模不大的SMP機(jī)器. P.21(2) 交叉開關(guān)Crossbar Switcher：一種高帶寬網(wǎng)絡(luò)

19、P.21(3) 多級(jí)互連網(wǎng)絡(luò)Multistage Interconnection Network P.21 一種大型開關(guān)網(wǎng)絡(luò). 根據(jù)算法(應(yīng)用)的需要, 動(dòng)態(tài)動(dòng)態(tài)地設(shè)置多級(jí)網(wǎng)絡(luò)中各端口連通狀各端口連通狀態(tài)態(tài), 從而使得在任一處理器與某個(gè)共享存儲(chǔ)器模塊之間構(gòu)成一條路由(鏈路,通路), 該處理器可以訪問此共享存儲(chǔ)器模塊單元中的內(nèi)容(數(shù)據(jù)). 對(duì)于對(duì)于n個(gè)處理器、個(gè)處理器、n個(gè)共享存儲(chǔ)模塊的多級(jí)互連網(wǎng)絡(luò)，其互連個(gè)共享存儲(chǔ)模塊的多級(jí)互連網(wǎng)絡(luò)，其互連級(jí)數(shù)級(jí)數(shù)m=logn1.2.2 并行計(jì)算機(jī)的存儲(chǔ)組織并行計(jì)算機(jī)的存儲(chǔ)組織v存儲(chǔ)器的層次結(jié)構(gòu) 寄存器 容 量 高速緩沖存儲(chǔ)器(SRAM) 每 和 一級(jí)緩存一級(jí)

20、緩存L1Cache 位 存 二級(jí)緩存二級(jí)緩存L2Cache (處理核共享處理核共享) 成成 取 三級(jí)緩存三級(jí)緩存L3Cache（CMP共享）共享） 本 時(shí) 增 間 主存儲(chǔ)器DRAM 加 增 加 硬盤存儲(chǔ)器 磁帶機(jī)1.2.2 并行計(jì)算機(jī)的存儲(chǔ)組織并行計(jì)算機(jī)的存儲(chǔ)組織v存儲(chǔ)器層次之間的數(shù)據(jù)傳輸（P.23 圖 1.21）v各層存儲(chǔ)器的性能參數(shù) 容量C：字節(jié)數(shù) 延遲L：讀取一個(gè)字（Word, 32/64位）所需的時(shí)間 帶寬B：1秒鐘內(nèi)各存儲(chǔ)層傳送的字節(jié)數(shù) （P.24 圖 1.22）v高速緩存一致性問題 當(dāng)某個(gè)處理器第一次訪問主存某一存儲(chǔ)單元時(shí)，系統(tǒng)會(huì)將其副本同時(shí)傳給與該處理器相連的高速緩存。以后當(dāng)此處

21、理器再此訪問此數(shù)據(jù)時(shí)，即可直接訪問其高速緩存中的副本（數(shù)據(jù)）。 若另一個(gè)處理器也訪問主存中同一存儲(chǔ)單元，則此數(shù)據(jù)之副本也被傳到其高速緩存中。 在上述情形下，若一個(gè)處理器改寫了其高速緩存中（副本）的內(nèi)容，但另一個(gè)處理器的高速緩存中（副本）的內(nèi)容仍是原來的值，則產(chǎn)生了高速緩存中不一致性的問題。1.3 并行計(jì)算模型并行計(jì)算模型1.3.1 引言引言v設(shè)計(jì)并行算法時(shí)，用戶可以不關(guān)心具體的并行計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)的細(xì)節(jié)。設(shè)計(jì)并行算法時(shí)，用戶可以不關(guān)心具體的并行計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)的細(xì)節(jié)。v將各種并行計(jì)算機(jī)系統(tǒng)的一些共同屬性抽象起來形成將各種并行計(jì)算機(jī)系統(tǒng)的一些共同屬性抽象起來形成“并行計(jì)算模并行計(jì)算模型型”。v并行算

22、法的設(shè)計(jì)與分析依賴于并行計(jì)算模型。并行算法的設(shè)計(jì)與分析依賴于并行計(jì)算模型。v傳統(tǒng)的順序（串行）算法的設(shè)計(jì)與分析依賴于經(jīng)典計(jì)算模型傳統(tǒng)的順序（串行）算法的設(shè)計(jì)與分析依賴于經(jīng)典計(jì)算模型隨機(jī)隨機(jī)存?。ㄔL問）機(jī)器模型存?。ㄔL問）機(jī)器模型RAM（Random Access Machine）。）。1.3.2 共享存儲(chǔ)的并行計(jì)算模型共享存儲(chǔ)的并行計(jì)算模型PRAM模型模型 PRAM模型模型(Parallel Random Access Machine, 并行隨機(jī)存取機(jī)器模型并行隨機(jī)存取機(jī)器模型) 1、同步、同步PRAM模型（模型（SIMD-SM模型）模型） SM：Shared Memory v共享存儲(chǔ)器的共享

23、存儲(chǔ)器的SIMD機(jī)器模型機(jī)器模型：容量無限的共享存儲(chǔ)器；有限：容量無限的共享存儲(chǔ)器；有限/無限個(gè)無限個(gè)功能相同的處理器；任何時(shí)刻各個(gè)處理器均可通過共享存儲(chǔ)器的存儲(chǔ)功能相同的處理器；任何時(shí)刻各個(gè)處理器均可通過共享存儲(chǔ)器的存儲(chǔ)單元進(jìn)行數(shù)據(jù)交換（通信）。單元進(jìn)行數(shù)據(jù)交換（通信）。v特點(diǎn)：特點(diǎn)：硬件同步硬件同步各并行進(jìn)程；時(shí)間復(fù)雜度分析：各并行進(jìn)程；時(shí)間復(fù)雜度分析：計(jì)算時(shí)間（計(jì)算時(shí)間（通信時(shí)間通信時(shí)間轉(zhuǎn)化成計(jì)算時(shí)間）轉(zhuǎn)化成計(jì)算時(shí)間）；算法設(shè)計(jì)策略（方法）是串行算法設(shè)計(jì)思想的擴(kuò)；算法設(shè)計(jì)策略（方法）是串行算法設(shè)計(jì)思想的擴(kuò)展；展；隱藏了并行機(jī)的通訊、同步等細(xì)節(jié)隱藏了并行機(jī)的通訊、同步等細(xì)節(jié)（設(shè)計(jì)并行算法直

24、觀、容易）（設(shè)計(jì)并行算法直觀、容易）；忽略了忽略了SMSM的競(jìng)爭(zhēng)、通訊延遲的競(jìng)爭(zhēng)、通訊延遲等因素。等因素。1.3 并行計(jì)算模型并行計(jì)算模型v同步PRAM（SIMD-SM）模型結(jié)構(gòu)圖Control UnitInterconnection NetworkPLMPLMPLMPLMShared Memory1.3 并行計(jì)算模型并行計(jì)算模型v同步PRAM（SIMD-SM）分類PRAM-EREW模型模型 互斥讀互斥寫互斥讀互斥寫 不支持多個(gè)處理器同時(shí)讀/寫共享存儲(chǔ)器同一單元。PRAM-CREW模型模型 并發(fā)讀互斥寫并發(fā)讀互斥寫 允許多個(gè)處理器同時(shí)讀允許多個(gè)處理器同時(shí)讀共享存儲(chǔ)器同一單元，但不支持多個(gè)處理但

25、不支持多個(gè)處理器同時(shí)寫器同時(shí)寫共享存儲(chǔ)器同一單元。PRAM-CRCW模型模型 并發(fā)讀并發(fā)寫并發(fā)讀并發(fā)寫 （理想化的模型） 支持多個(gè)處理器同時(shí)讀/寫共享存儲(chǔ)器同一單元。 PRAM-CRCW模型的變形：模型的變形：CPRAM-CRCW (Common PRAM-CRCW)模型：僅允許寫入相同數(shù)據(jù)PPRAM-CRCW(Priority PRAM-CRCW)模型：僅允許優(yōu)先級(jí)最高（比（比如：處理器編號(hào)最小）如：處理器編號(hào)最?。┑奶幚砥鞒晒懭?。APRAM-CRCW(Arbitrary PRAM-CRCW)：允許任意處理器自由寫入。 1.3 并行計(jì)算模型并行計(jì)算模型v同步PRAM（SIMD-SM）分類P

26、RAM-EREW模型模型 互斥讀互斥寫互斥讀互斥寫 不支持多個(gè)處理器同時(shí)讀/寫共享存儲(chǔ)器同一單元。PRAM-CREW模型模型 并發(fā)讀互斥寫并發(fā)讀互斥寫 允許多個(gè)處理器同時(shí)讀允許多個(gè)處理器同時(shí)讀共享存儲(chǔ)器同一單元，但不支持多個(gè)處理但不支持多個(gè)處理器同時(shí)寫器同時(shí)寫共享存儲(chǔ)器同一單元。PRAM-CRCW模型模型 并發(fā)讀并發(fā)寫并發(fā)讀并發(fā)寫 （理想化的模型） 支持多個(gè)處理器同時(shí)讀/寫共享存儲(chǔ)器同一單元。 PRAM-CRCW模型的變形：模型的變形：CPRAM-CRCW (Common PRAM-CRCW)模型：僅允許寫入相同數(shù)據(jù)PPRAM-CRCW(Priority PRAM-CRCW)模型：僅允許優(yōu)先級(jí)

27、最高（比（比如：處理器編號(hào)最?。┤纾禾幚砥骶幪?hào)最小）的處理器成功寫入。APRAM-CRCW(Arbitrary PRAM-CRCW)：允許任意處理器自由寫入。 1.3 并行計(jì)算模型并行計(jì)算模型vPRAM-EREW、PRAM-CREW、PRAM-CRCW計(jì)算能力比較計(jì)算能力比較 設(shè)TM表示某個(gè)并行算法在并行計(jì)算模型M上運(yùn)行所需的時(shí)間，則：qPRAM-EREW模型上模型上解決解決并發(fā)讀沖突并發(fā)讀沖突方法方法 將p 個(gè)處理器組織成一棵邏輯二叉樹，采取自頂向下自頂向下（從樹根到樹葉）、逐層并行播送數(shù)據(jù)逐層并行播送數(shù)據(jù)的方法，樹中第i 層上2i (i=1-log2p) 個(gè)處理器并行地從SM讀出數(shù)據(jù)，然后

28、這些數(shù)據(jù)副本并行寫入SM中其他單元： SM: x P0 P1 P2 P3 P4 P5 P6 P7 P8 P9 P10 P11 P12 P13 P14CRCWCREWEREWTTT1.3 并行計(jì)算模型并行計(jì)算模型qPRAM-EREW模型上模型上解決解決并發(fā)寫沖突并發(fā)寫沖突方法方法 將p 個(gè)處理器組織成一棵邏輯二叉競(jìng)賽樹的樹葉結(jié)點(diǎn)，采取由底由底向上、逐層并行比較淘汰數(shù)據(jù)向上、逐層并行比較淘汰數(shù)據(jù)的方法，樹中第i 層上2i (i= log2(p-1) - 0) 個(gè)處理器并行比較其左右孩子結(jié)點(diǎn)（處理器）的數(shù)據(jù)，勝者晉升到上一層繼續(xù)比較，敗者被淘汰，最后能夠到達(dá)根結(jié)點(diǎn)的處理器成功將數(shù)據(jù)寫入SM單元中：

29、SM: y P P0 0 P0 P1 P P0 0 P P1 1 P P2 2 P P3 3 P0 P1 P2 P3 P4 P5 P6 P7 因此，)log()log(pTOpTOTCRCWCREWEREW1.3 并行計(jì)算模型并行計(jì)算模型2. 異步APRAM（MIMD-SM）模型 P.28v模型特性每個(gè)處理器有其局部存儲(chǔ)器、局部時(shí)鐘、局部程序；無全局時(shí)鐘，各處理器異步執(zhí)行無全局時(shí)鐘，各處理器異步執(zhí)行；處理器通過SM進(jìn)行通訊、交換數(shù)據(jù)；處理器之間的依賴關(guān)系，需在并行算法（程序）中顯式地加入同步路障語句來需在并行算法（程序）中顯式地加入同步路障語句來指定同步指定同步，即軟件同步軟件同步。算法（程序

30、）設(shè)計(jì)難度比APRAM模型稍難些。時(shí)間復(fù)雜度分析：并行（并發(fā)）進(jìn)程生成時(shí)間并行（并發(fā)）進(jìn)程生成時(shí)間、并行計(jì)算時(shí)間、并行計(jì)算時(shí)間、并行（并發(fā)）進(jìn)程計(jì)算（處理）過程中的同步時(shí)間計(jì)算（處理）過程中的同步時(shí)間、并行（并發(fā)）進(jìn)程結(jié)束的同步時(shí)間結(jié)束的同步時(shí)間。v指令類型：全局讀、全局寫、局部操作、同步v計(jì)算時(shí)間 設(shè)局部操作為單位時(shí)間；全局讀/寫平均時(shí)間為d，d隨著處理器數(shù)目的增加而增加；同步路障時(shí)間為B=B(p)非降函數(shù)。 令 為全局相內(nèi)各處理器執(zhí)行時(shí)間最長(zhǎng)者，則APRAM上的計(jì)算時(shí)間為： 注：多核處理結(jié)構(gòu)的多核計(jì)算模型就是異步注：多核處理結(jié)構(gòu)的多核計(jì)算模型就是異步APRAM（MIMD-SM）模型）模型。

31、pht同步障次數(shù)BtTph1.3 并行計(jì)算模型并行計(jì)算模型2. 異步APRAM（MIMD-SM）模型v計(jì)算過程 異步APRAM（MIMD-SM）模型的計(jì)算過程由同步障分開的全局相組成。1.3 并行計(jì)算模型并行計(jì)算模型1.3.3 分布存儲(chǔ)的并行計(jì)算模型1. SIMD-IN（ SIMD-DM）模型分布存儲(chǔ)SIMD模型v模型特性q每個(gè)處理器均自己的存儲(chǔ)器（分布式存儲(chǔ)）每個(gè)處理器均自己的存儲(chǔ)器（分布式存儲(chǔ)）；q處理器之間通過互連網(wǎng)絡(luò)相連，采用傳遞數(shù)據(jù)方式實(shí)現(xiàn)通訊傳遞數(shù)據(jù)方式實(shí)現(xiàn)通訊；q運(yùn)行在各處理器的算法（進(jìn)程）同步并行執(zhí)行同步并行執(zhí)行，處理器之間同步由硬件同步由硬件實(shí)現(xiàn)實(shí)現(xiàn)；q算法時(shí)間復(fù)雜度分析：計(jì)

32、算時(shí)間和選路選路( (路由，通信路由，通信) )時(shí)間時(shí)間。有些應(yīng)用所需的選路(路由，通信)時(shí)間比其計(jì)算時(shí)間還要多。v模型的結(jié)構(gòu)圖1.3 并行計(jì)算模型并行計(jì)算模型1.3.3 分布存儲(chǔ)的并行計(jì)算模型1. SIMD-IN（ SIMD-DM）模型分布存儲(chǔ)SIMD模型vSIMD-IN（SIMD-DM）模型的常見模型模型的常見模型q SIMD-LC 一維線性連接q SIMD-MC 網(wǎng)孔連接q SIMD-TC 樹形連接q SIMD-MT 樹網(wǎng)連接q SIMD-HC 超立方連接q SIMD-CCC 立方環(huán)連接q SIMD-SE 洗牌交換連接q SIMD-BF 蝶形網(wǎng)絡(luò)q SIMD-MIN 多級(jí)互連網(wǎng)絡(luò)1.3

33、并行計(jì)算模型并行計(jì)算模型1.3.3 分布存儲(chǔ)的并行計(jì)算模型2. BSP模型v模型特性q它是MIMD-DM模型模型中的一種；q每個(gè)處理器均自己的存儲(chǔ)器（分布式存儲(chǔ)）；q處理器之間通過互連網(wǎng)絡(luò)相連，采用傳遞消息方式實(shí)現(xiàn)通訊傳遞消息方式實(shí)現(xiàn)通訊；q運(yùn)行在各處理器上的算法（進(jìn)程）異步并行執(zhí)行異步并行執(zhí)行q處理器之間的同步由算法（程序處理器之間的同步由算法（程序/軟件）實(shí)現(xiàn)軟件）實(shí)現(xiàn)；q算法時(shí)間復(fù)雜度分析：計(jì)算時(shí)間和選路（路由，通信）時(shí)間。有些應(yīng)用所需的選路（路由，通信）時(shí)間比其計(jì)算時(shí)間還要多。v模型參數(shù)p：處理器數(shù)（帶有存儲(chǔ)器）L：同步障時(shí)間（Barrier synchronization time）

34、g：帶寬因子（time steps/packet）=1/bandwidth1.3 并行計(jì)算模型并行計(jì)算模型1.3.3 分布存儲(chǔ)的并行計(jì)算模型2. BSP模型v計(jì)算過程 BSP模型的計(jì)算過程由若干超級(jí)步組成 強(qiáng)調(diào)計(jì)算過程與通信過程的分離 限制至多h條消息的傳遞等1.3 并行計(jì)算模型并行計(jì)算模型1.3.3 分布存儲(chǔ)的并行計(jì)算模型3. LogP模型v模型特性q分布存儲(chǔ)的MIMD模型q點(diǎn)到點(diǎn)通訊的多處理機(jī)模型，其中通訊由一組參數(shù)描述q隱藏了并行機(jī)的網(wǎng)絡(luò)拓?fù)?、路由、協(xié)議，可以應(yīng)用到共享存儲(chǔ)、消息傳遞、數(shù)據(jù)并行的編程模型中q處理機(jī)之間實(shí)行隱式同步，即硬件同步q算法描述、設(shè)計(jì)和分析困難v模型參數(shù)qL：net

35、work latencyqo：communication overheadqg：gap=1/bandwidthqP：#processors注：L和g反映了通訊網(wǎng)絡(luò)的容量1.3 并行計(jì)算模型并行計(jì)算模型1.3.4 層次層次存儲(chǔ)的并行計(jì)算模型1. 串行計(jì)算系統(tǒng)的層次存儲(chǔ)模型 （P.34-35）vHMM（層次存儲(chǔ)）模型和HMM-BT（塊傳輸?shù)膶哟未鎯?chǔ)）模型vUMH （均勻存儲(chǔ)層次）模型vRAM(h)模型h層隨機(jī)存儲(chǔ)模型2. 并行計(jì)算系統(tǒng)的層次存儲(chǔ)模型 （P.36-37）vMemory-LogP模型模型 （ 共享存儲(chǔ)共享存儲(chǔ)-分布存儲(chǔ)模型分布存儲(chǔ)模型）vDRAM（h）模型）模型分布式分布式h層隨機(jī)存儲(chǔ)

36、模型層隨機(jī)存儲(chǔ)模型q本地結(jié)點(diǎn)模型為RAM(h)模型h層隨機(jī)存儲(chǔ)模型。q p個(gè)本地處理機(jī)結(jié)點(diǎn)通過互連網(wǎng)絡(luò)連接起來。q處理機(jī)結(jié)點(diǎn)之間采用點(diǎn)到點(diǎn)消息傳遞方式交換信息。q將消息傳遞看成是另一層的存儲(chǔ)層次訪問；集合消息傳遞看成是另一將消息傳遞看成是另一層的存儲(chǔ)層次訪問；集合消息傳遞看成是另一層并發(fā)存儲(chǔ)訪問層并發(fā)存儲(chǔ)訪問 方便分析并行算法復(fù)雜度方便分析并行算法復(fù)雜度qDRAM(h)模型=RAM(h)模型+LogP遠(yuǎn)程存儲(chǔ)訪問模型。 SMP-Cluster，多核處理器機(jī)群系統(tǒng)就屬于，多核處理器機(jī)群系統(tǒng)就屬于DRAM（h）模型的實(shí)例）模型的實(shí)例。vHPM模型模型層次并行和存儲(chǔ)模型層次并行和存儲(chǔ)模型1.3 并行

37、計(jì)算模型并行計(jì)算模型1.3.5 其他其他并行計(jì)算模型MIMD-AC模型異步通信分布式計(jì)算模型比較器網(wǎng)絡(luò)心動(dòng)陣列和波前陣列判定樹有向五環(huán)圖 量子計(jì)算模型量子計(jì)算模型 量子物理，量子信息，量子位（Qubit），量子寄存器，n位的量子寄存器可表述 2n種狀態(tài)，可并行地對(duì)量子寄存器中 2n種狀態(tài)進(jìn)行操作。量子計(jì)算機(jī)具有海量存儲(chǔ)和天然并行性海量存儲(chǔ)和天然并行性的特征。分子計(jì)算模型分子計(jì)算模型 用分子表示“處理（計(jì)算）單元”，分子狀態(tài)表示數(shù)據(jù)（信息）值，并行地對(duì)分子操作，所有分子同時(shí)產(chǎn)生反應(yīng)、改變分子狀態(tài)（改變數(shù)據(jù)值）。空間并行性?？臻g并行性。1.4 并行算法的基礎(chǔ)知識(shí)并行算法的基礎(chǔ)知識(shí)1.4.1 并行算

38、法的定義與分類 1. 定義 并行算法： 一組可同時(shí)執(zhí)行且可互相協(xié)作的諸進(jìn)程的集合。一組可同時(shí)執(zhí)行且可互相協(xié)作的諸進(jìn)程的集合。 2. 分類 VLSI并行算法：在VLSI計(jì)算模型上開發(fā)的并行算法 、匹配等符號(hào)處理基于排序、選擇、搜索非數(shù)值算法：基于代數(shù)等數(shù)學(xué)運(yùn)算數(shù)值算法：各進(jìn)程可以獨(dú)立執(zhí)行異步算法：進(jìn)程執(zhí)行需要相互等待同步算法：環(huán)境下網(wǎng)格計(jì)算：元計(jì)算網(wǎng)絡(luò)計(jì)算：工作站機(jī)群局網(wǎng)環(huán)境下分布算法InternetCOW/法等如：隨機(jī)算法、智能算非確定算法：時(shí)間復(fù)雜性確定的以及算法結(jié)果求解過程為確定的步驟確定算法：/1.4 并行算法的基礎(chǔ)知識(shí)并行算法的基礎(chǔ)知識(shí)1.4.2 并行算法的表述1. do stepi

39、to stepj in parallel 強(qiáng)調(diào)stepi , stepj 要并行執(zhí)行 stepi stepj enddo2. for all par-do 語句強(qiáng)調(diào)n 個(gè)進(jìn)程（線程）并行執(zhí)行，每個(gè)進(jìn)程（線程）均執(zhí)行語句S1,S2,.Sk,，但每個(gè)進(jìn)程計(jì)算處理的數(shù)據(jù)對(duì)象不同 for i=1 to n par-do 或 for i=1 to n do in parallel S1 S1 . . Sk Sk end for end for3. for all par-do 語句強(qiáng)調(diào)p個(gè)處理器并行執(zhí)行，每個(gè)處理器均執(zhí)行語句S1,S2,.Sk,，但每個(gè)處理器計(jì)算處理的數(shù)據(jù)對(duì)象不同 for all Pi,

40、 where 0ip-1 par-do 或 for all Pi, where 0i p-1 do in parallel S1 S1 . . Sk Sk end for endfor 1.4 并行算法的基礎(chǔ)知識(shí)并行算法的基礎(chǔ)知識(shí)1.4.3 并行算法復(fù)雜性的度量1、串行算法復(fù)雜性的度量 算法復(fù)雜性用關(guān)于輸入數(shù)據(jù)規(guī)模n的函數(shù)f(n)來度量，特別是用當(dāng)n充分大時(shí)f(n)的漸近度增長(zhǎng)函數(shù)來度量v一些記號(hào)f(n)=O(g(n) 當(dāng)n充分大時(shí)，f(n) cg(n), c常數(shù) f(n)=Omega(g(n) 當(dāng)n充分大時(shí)，f(n)cg(n), c常數(shù)f(n)=Qita(g(n) 當(dāng)n充分大時(shí)，c1 g(n

41、) f(n) c2 g(n), c1 ， c2常數(shù)v平均情形復(fù)雜度、最壞情形復(fù)雜度1.4 并行算法的基礎(chǔ)知識(shí)并行算法的基礎(chǔ)知識(shí)1.4.3 并行算法復(fù)雜性的度量 2. 并行算法復(fù)雜性的度量v運(yùn)行時(shí)間t(n): t(n)= tc (n) + tr (n) 計(jì)算時(shí)間tc (n)和選路(路由，通信)時(shí)間tr (n)v處理器數(shù)目p(n)， p(n) =n1-e, 0ep(n)，則為超線性加速(一般出現(xiàn)在某些特殊的應(yīng)用中，如人工智能中的并行搜索等)v并行效率Ep(n)：Ep(n)=Sp(n)/p(n)， 0用用p臺(tái)處理器去完成并行算法臺(tái)處理器去完成并行算法A的第的第i時(shí)刻工作量，需時(shí)間時(shí)刻工作量，需時(shí)間

42、=用用p臺(tái)處理器模擬并行算法臺(tái)處理器模擬并行算法A的總時(shí)間為的總時(shí)間為 Brent定理揭示了定理揭示了并行算法工作量和運(yùn)行時(shí)間的關(guān)系；并行算法工作量和運(yùn)行時(shí)間的關(guān)系；提供了提供了并行算法并行算法的的WT(Work-Time)表示方法；表示方法；指明了指明了設(shè)計(jì)并行算法時(shí)應(yīng)盡可能將每個(gè)設(shè)計(jì)并行算法時(shí)應(yīng)盡可能將每個(gè)時(shí)間步的工作量均勻地分?jǐn)偨o時(shí)間步的工作量均勻地分?jǐn)偨op臺(tái)處理器，使各處理器處于活躍狀態(tài)。臺(tái)處理器，使各處理器處于活躍狀態(tài)。)()(11)(1)(1)(1nTpnWpWpWpWnTiinTiinTii算法算法1.1 SIMD-SM模型上并行求和算法模型上并行求和算法（高層描述（高層描述不考

43、慮處理器數(shù)目及其不考慮處理器數(shù)目及其分配）分配） / 數(shù)據(jù)數(shù)據(jù)A1.n, n=2k Begin(1) for i=1 to n do in parallel /時(shí)間時(shí)間O(1 ), 工作量工作量n Bi=Ai; / A為原始數(shù)組為原始數(shù)組 endfor(2) for h=1 to log2n do / h為邏輯二叉樹的層號(hào)為邏輯二叉樹的層號(hào) / h層上層上n/2h個(gè)結(jié)點(diǎn)（進(jìn)程）個(gè)結(jié)點(diǎn)（進(jìn)程） 并行執(zhí)行并行執(zhí)行 for i = 1 to n/2h do in parallel / 時(shí)間時(shí)間 O(1 ), 工作量工作量n/2h Bi=B2i-1+B2i; endfor endif(3) S=B1;

44、 / 時(shí)間時(shí)間O(1), 工作量工作量1 endfor End.時(shí)間時(shí)間T(n)=O(1)+ log2n*O(1)+O(1)=O(log2n)工作量工作量W(n) =n+(n/21 +n/22 +n/2log-1+n/2logn)+1=O(n)算法1.1 SIMD-SM模型上并行求和算法（高層描述）示意圖： B1 (S) B1 B2 B1 B2 B3 B4 逐層并行 由底向上 B1 B2 . Bn/2-1 Bn/2 B1 B2 B3 B4 . Bn-3 Bn-2 Bn-1 Bn A1 A2 A3 A4 . An-3 An-2 An-1 An算法1.2 SIMD-SM模型上并行求和算法（低層描述

45、考慮處理器數(shù)目及其分配） / 數(shù)據(jù)A1.n, n=2k, 處理器數(shù)p=2q； / 處理器Ps求Am(s-1)+1.m*s的子和,m=n/p=2k-q , s=1 p Begin(1) for s=1 to p do in parallel(1.1) for j=1 to m=n/p do /時(shí)間O(n/p ) Bm(s-1)+j=Am(s-1)+j; / O(1)時(shí)間，A為原始數(shù)組為原始數(shù)組 endfor(1.2)for h=1 to log2n do / h為邏輯二叉樹的層號(hào) (1.2.1) if (k-q-h)=0 then / h層上并行工作量（結(jié)點(diǎn)數(shù)）大于等于處理器數(shù) for i= 2

46、k-h-q (s-1)+1 to 2k-h-q *s do / 時(shí)間 O(2k-h-q )=O(n/(p*2h) Bi=B2i-1+B2i; endfor endif (1.2.2) if s= 2k-h then / 時(shí)間O(1),當(dāng)前第s個(gè)子樹的和Bs Bs=B2s-1+B2s; endif endfor(1.3) If s=1 the S=B1 endif endfor End.T(n)=O(n/p)+O(n/(p21 )+O(1)+ O(n/(p22 )+O(1) + +O( n/(p2log- 1 ) )+O(1)+O(n/(p2logn )+O(1)+O(1)=O(n/p+log2

47、n)1.5 并行算法的同步與通信1、并行算法的同步、并行算法的同步v 同步是在時(shí)間上強(qiáng)使各執(zhí)行進(jìn)程在某一點(diǎn)必須互相等待，確保各進(jìn)程的正同步是在時(shí)間上強(qiáng)使各執(zhí)行進(jìn)程在某一點(diǎn)必須互相等待，確保各進(jìn)程的正常順序和對(duì)共享可寫數(shù)據(jù)的正確訪問。常順序和對(duì)共享可寫數(shù)據(jù)的正確訪問。v 可用軟件、硬件和固件的辦法來實(shí)現(xiàn)同步：可用軟件、硬件和固件的辦法來實(shí)現(xiàn)同步： SIMD-SM(PRAM)/SIMD-IN上并行算法由硬件實(shí)現(xiàn)同步。上并行算法由硬件實(shí)現(xiàn)同步。 MIMD-SM (APRAM) 上并行算法由軟件（算法）實(shí)現(xiàn)同步上并行算法由軟件（算法）實(shí)現(xiàn)同步：例如，使用：例如，使用lock和和unlock等同步語句顯

48、式設(shè)置臨界區(qū)實(shí)現(xiàn)多個(gè)并發(fā)進(jìn)程（線程）對(duì)共等同步語句顯式設(shè)置臨界區(qū)實(shí)現(xiàn)多個(gè)并發(fā)進(jìn)程（線程）對(duì)共享變量的互斥訪問。享變量的互斥訪問。算法復(fù)雜度還包括進(jìn)程生成時(shí)間、進(jìn)程結(jié)束同步時(shí)間。算法復(fù)雜度還包括進(jìn)程生成時(shí)間、進(jìn)程結(jié)束同步時(shí)間。v 同步示例同步示例 MIMD-SM (APRAM)上的異步并行求和算法上的異步并行求和算法輸入：輸入：A=(a0,an-1), 處理器數(shù)處理器數(shù)p輸出：輸出：S=ai Begin (1) S=0； / S共享全局變量（總和）共享全局變量（總和） (2.3) lock(S) / 同步同步 (2) for all Pi where 0ip-1 para-do /異步并行異步并

49、行/ S=S+L； (2.1) L=0 ； / L局部變量（子和）局部變量（子和） (2.4) unlock(S) (2.2) for j=i to n step p do end for L=L+aj ； End end for | | P0 P1 P p-2 Pp-1(主）進(jìn)程主）進(jìn)程0 進(jìn)程進(jìn)程1 進(jìn)程進(jìn)程p-2 進(jìn)程進(jìn)程p-1 i=0 i=1 i= p-2 i= p-1 | | | | S=0 | | | | L=0 L=0 L=0 L=0 | | | |for j=i to n step p do for j=i to n step p do for j=i to n step p do for j=i to n step p doL=L+aj L=L+aj L=L+aj L=L+aj | | | |lock(S) lock(S) lock(S) lock(S) S=S+L S=S+L S=S+L S=S+Lunlock(S) unlock(S) unlock(S) unlock(S)2、并行算法的通信v SIMD-SM/MIMD-SM算法的通信算法的通信 通過讀通過讀/寫共享存儲(chǔ)器實(shí)現(xiàn)處理器（并行進(jìn)程）之間的通信：寫共享存儲(chǔ)器實(shí)現(xiàn)處理器（并行進(jìn)程）之間