并行算法的設(shè)計與(1)全解課件

1、并行算法設(shè)計與分析 鐘誠3236396， 第1頁，共50頁。教材陳國良.并行算法的設(shè)計與分析，第3版.北京:高等教育出版社,2009參考書1 陳國良. 并行計算結(jié)構(gòu)算法 編程, 第3版. 北京：高等 教育出版社,20112 陳國良等. 并行算法實踐.北京：高等教育出版社,20043 蘇德富,鐘誠. 計算機算法設(shè)計與分析,第2版. 北京：電子 工業(yè)出版社, 20054 C. Xavier, S. S. Iyenger著, 張云泉等譯. 并行算法導(dǎo)論.北京： 機械工業(yè)出版社, 19985 Ananth Grama. 并行計算導(dǎo)論, 第2版,英文版. 北京:機械 工業(yè)出版社,2003第2頁，共50頁

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

3、Computing)過程的并發(fā)事件的信息處理. 2. 并發(fā)性 (Concurrency) 并行性(Parallelism) 同時性(Simultaneity) 流水線(Pipelining) 3. 并行處理的級別(Parallel Processing Level) 指令級并行(Instruction Level Parallelism-ILP, 指令內(nèi)部并行,指令之間并行) 細粒度并行 (fine grain parallelism/ tiny granularity parallelism ) 線程級并行(Thread Level Parallelism-TLP) 中細粒度并行 (fine

4、- medium grain parallelism) 進程級(Process Level Parallelism-PLP)/過程級/算法級并行 中粒度并行 (medium grain parallelism) 任務(wù)級并行(Task Level Parallel) 粗粒度并行 (coarse grain parallelism) 4. 并行計算(Parallel Computing)學(xué)科 并行計算機體系結(jié)構(gòu) (Parallel Computer Architectures) 并行算法 (Parallel Algorithms) 并行程序設(shè)計 (Parallel Programming)5. 多

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

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

7、rs ( 工作站機群Workstation-Cluster, PC機群PC-Cluster, SMP機群 SMP-Cluster等)；目前大部分“超級并行計算機”均采用Clusters結(jié)構(gòu) DSM (Distributed Shared Memory, 分布共享存儲多處理機) 第6頁，共50頁。第一章 緒論1.2.1 并行計算機的體系結(jié)構(gòu): 并行計算機分類 結(jié)構(gòu)模型物理機模型VPVPVP交叉開關(guān)SM(a) PVPP/CP/CP/C總線或交叉開關(guān)SM(b) SMP, 物理上單一地址空間P/CP/CP/C定制網(wǎng)絡(luò)LMLMLM虛擬分布共享存儲(DSM) (d) DSM (MPP/Cluster),邏

8、輯上單一地址空間P/CP/CP/C定制網(wǎng)絡(luò)LMLMLM(c) MPP, 物理/邏輯上多地址空間P/CP/CP/C定制/標(biāo)準(zhǔn)網(wǎng)絡(luò)LMLMLM(e) Cluster/COW, 物理/邏輯上多地址空間第7頁，共50頁。第一章 緒論1.2.1 并行計算機的體系結(jié)構(gòu): 并行計算機分類 結(jié)構(gòu)模型物理機模型SMPSMPSMPSAN/LANSMSMSMMPPMPPMPPSAN/LANDSMDSMDSM(f) SMP-Cluster(g) DSM-ClusterSMPMPPMPPWANLMDSMSM(h) Grid (Cluster of Clusters)第8頁，共50頁。1.2.1 并行計算機的互連網(wǎng)絡(luò) 靜

9、態(tài)互連網(wǎng)絡(luò)(固定連接) connected graph: vertices = processing nodes, edges = communication links(1) 一維線性連接LA(1-D Linear Array): 一維陣列 不帶環(huán)繞的1-D LA，帶環(huán)繞的1-D LA, 通信直徑n-1, n處理器數(shù)(2) 網(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,

10、 p處理器編號 不帶環(huán)繞的MC，帶環(huán)繞的MC , 通信直徑n1/2-1,第9頁，共50頁。1.2.1 并行計算機的互連網(wǎng)絡(luò)網(wǎng)孔結(jié)構(gòu)的擴展: 可重構(gòu)網(wǎng)孔 RMESH (Reconfigurable Mesh) 網(wǎng)孔+可重構(gòu)總線 動態(tài)重新設(shè)置并行計算機的互連結(jié)構(gòu)，例如可動態(tài)設(shè)置成多條行總線、列總線或者對角線總線處理機陣列結(jié)構(gòu)，也可動態(tài)將規(guī)模n n的二維RMESH結(jié)構(gòu)設(shè)置成n個規(guī)模n1/2 n1/2的子MESH結(jié)構(gòu)。每個處理器通過四個端口（N,E,S,W）與總線相連，在處理器內(nèi)部有6個開關(guān)控制這四個端口之間的連接關(guān)系，如圖a所示。這四個端口之間共有15種連接方式，如圖b所示。 123123iijP(

11、2,3)NESW: 開關(guān)NSEWNSEWNSEWNSEWNEWEWSNE,W,SNEW,S,NE,W,S,NEW,SNNSEWNSEWEWN,SEWS,NNWS,EW,NESNW,SENSEWNSEWNSEWNSEWNE,W,SN,W,ESWS,N,ENW,S,ENE,SWNSEWNSEWNSEWNSEW(a)(b) 2D-RMESH結(jié)構(gòu)第10頁，共50頁。1.2.1 并行計算機的互連網(wǎng)絡(luò) 靜態(tài)互連網(wǎng)絡(luò) (3) 樹形連接TC(Tree Connected) 二叉樹，通信直徑2(logn-1) 胖樹(X樹） 根結(jié)點處理器負載過重，瓶頸結(jié)點要求根結(jié)點處理和容錯能力強千萬億次神威藍光超級并行計算機群

12、采用胖樹結(jié)構(gòu)連接機群中的處理器結(jié)點 曙光5000A超級并行計算機群系統(tǒng)機采用樹結(jié)構(gòu)連接機群中的處理器結(jié)點第11頁，共50頁。1.2.1 并行計算機的互連網(wǎng)絡(luò) 靜態(tài)互連網(wǎng)絡(luò) (4) 樹網(wǎng)連接MT(Mesh of tree) 第12頁，共50頁。1.2.1 并行計算機的互連網(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 其中pm-1 pm-2 pi+1 pi pi-1 p1 p0為處理

13、器編號的二進制表示, pi 為對pi 求反, i=0m-1, m=log2n, n=2m ; 通信直徑log2n. 不易擴展. 例: 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立方第13頁，共50頁。1.2.1 并行計算機的互連網(wǎng)絡(luò) 擴展的超立方結(jié)構(gòu)-光電超立

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

15、的洗牌和交換函數(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特點：位于某個處理器中的數(shù)據(jù)，連續(xù)洗牌m次之后，數(shù)據(jù)又回到該處理器第15頁，共50頁。1.2.1 并行計算機的互連網(wǎng)絡(luò) 靜態(tài)互連網(wǎng)絡(luò)(9) 蝶形連接(Butterfly Connected) 對于k n的蝶形網(wǎng)絡(luò), k=log2n, 設(shè)Pr,i (0 r k, 0 i n)表示第r 行第i 列上的處理器,其中第k 行視同第0行. 蝶形網(wǎng)絡(luò)互連函數(shù): Butterfly(Pr,i )

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

17、)的需要, 動態(tài)地設(shè)置多級網(wǎng)絡(luò)中各端口連通狀態(tài), 從而使得在任一處理器與某個共享存儲器模塊之間構(gòu)成一條路由(鏈路,通路), 該處理器可以訪問此共享存儲器模塊單元中的內(nèi)容(數(shù)據(jù)). 對于n個處理器、n個共享存儲模塊的多級互連網(wǎng)絡(luò)，其互連級數(shù)m=logn第17頁，共50頁。1.2.2 并行計算機的存儲組織存儲器的層次結(jié)構(gòu) 寄存器 容 量 高速緩沖存儲器(SRAM) 每 和 一級緩存L1Cache 位 存 二級緩存L2Cache (處理核共享) 成 取 三級緩存L3Cache（CMP共享） 本 時 增 間 主存儲器DRAM 加 增 加 硬盤存儲器 磁帶機第18頁，共50頁。1.2.2 并行計算機的存

18、儲組織存儲器層次之間的數(shù)據(jù)傳輸（P.23 圖 1.21）各層存儲器的性能參數(shù) 容量C：字節(jié)數(shù) 延遲L：讀取一個字（Word, 32/64位）所需的時間 帶寬B：1秒鐘內(nèi)各存儲層傳送的字節(jié)數(shù) （P.24 圖 1.22）高速緩存一致性問題 當(dāng)某個處理器第一次訪問主存某一存儲單元時，系統(tǒng)會將其副本同時傳給與該處理器相連的高速緩存。以后當(dāng)此處理器再此訪問此數(shù)據(jù)時，即可直接訪問其高速緩存中的副本（數(shù)據(jù)）。 若另一個處理器也訪問主存中同一存儲單元，則此數(shù)據(jù)之副本也被傳到其高速緩存中。 在上述情形下，若一個處理器改寫了其高速緩存中（副本）的內(nèi)容，但另一個處理器的高速緩存中（副本）的內(nèi)容仍是原來的值，則產(chǎn)生了

19、高速緩存中不一致性的問題。第19頁，共50頁。1.3 并行計算模型1.3.1 引言設(shè)計并行算法時，用戶可以不關(guān)心具體的并行計算機系統(tǒng)結(jié)構(gòu)的細節(jié)。將各種并行計算機系統(tǒng)的一些共同屬性抽象起來形成“并行計算模型”。并行算法的設(shè)計與分析依賴于并行計算模型。傳統(tǒng)的順序（串行）算法的設(shè)計與分析依賴于經(jīng)典計算模型隨機存?。ㄔL問）機器模型RAM（Random Access Machine）。1.3.2 共享存儲的并行計算模型PRAM模型 PRAM模型(Parallel Random Access Machine, 并行隨機存取機器模型) 1、同步PRAM模型（SIMD-SM模型） SM：Shared Memo

20、ry 共享存儲器的SIMD機器模型：容量無限的共享存儲器；有限/無限個功能相同的處理器；任何時刻各個處理器均可通過共享存儲器的存儲單元進行數(shù)據(jù)交換（通信）。特點：硬件同步各并行進程；時間復(fù)雜度分析：計算時間（通信時間轉(zhuǎn)化成計算時間）；算法設(shè)計策略（方法）是串行算法設(shè)計思想的擴展；隱藏了并行機的通訊、同步等細節(jié)（設(shè)計并行算法直觀、容易）；忽略了SM的競爭、通訊延遲等因素。第20頁，共50頁。1.3 并行計算模型同步PRAM（SIMD-SM）模型結(jié)構(gòu)圖Control UnitInterconnection NetworkPLMPLMPLMPLMShared Memory第21頁，共50頁。1.3

21、并行計算模型同步PRAM（SIMD-SM）分類PRAM-EREW模型 互斥讀互斥寫 不支持多個處理器同時讀/寫共享存儲器同一單元。PRAM-CREW模型 并發(fā)讀互斥寫 允許多個處理器同時讀共享存儲器同一單元，但不支持多個處理器同時寫共享存儲器同一單元。PRAM-CRCW模型 并發(fā)讀并發(fā)寫 （理想化的模型） 支持多個處理器同時讀/寫共享存儲器同一單元。 PRAM-CRCW模型的變形：CPRAM-CRCW (Common PRAM-CRCW)模型：僅允許寫入相同數(shù)據(jù)PPRAM-CRCW(Priority PRAM-CRCW)模型：僅允許優(yōu)先級最高（比如：處理器編號最?。┑奶幚砥鞒晒懭?。APRAM

22、-CRCW(Arbitrary PRAM-CRCW)：允許任意處理器自由寫入。 第22頁，共50頁。1.3 并行計算模型同步PRAM（SIMD-SM）分類PRAM-EREW模型 互斥讀互斥寫 不支持多個處理器同時讀/寫共享存儲器同一單元。PRAM-CREW模型 并發(fā)讀互斥寫 允許多個處理器同時讀共享存儲器同一單元，但不支持多個處理器同時寫共享存儲器同一單元。PRAM-CRCW模型 并發(fā)讀并發(fā)寫 （理想化的模型） 支持多個處理器同時讀/寫共享存儲器同一單元。 PRAM-CRCW模型的變形：CPRAM-CRCW (Common PRAM-CRCW)模型：僅允許寫入相同數(shù)據(jù)PPRAM-CRCW(Pr

23、iority PRAM-CRCW)模型：僅允許優(yōu)先級最高（比如：處理器編號最?。┑奶幚砥鞒晒懭?。APRAM-CRCW(Arbitrary PRAM-CRCW)：允許任意處理器自由寫入。 第23頁，共50頁。1.3 并行計算模型PRAM-EREW、PRAM-CREW、PRAM-CRCW計算能力比較 設(shè)TM表示某個并行算法在并行計算模型M上運行所需的時間，則：PRAM-EREW模型上解決并發(fā)讀沖突方法 將p 個處理器組織成一棵邏輯二叉樹，采取自頂向下（從樹根到樹葉）、逐層并行播送數(shù)據(jù)的方法，樹中第i 層上2i (i=1-log2p) 個處理器并行地從SM讀出數(shù)據(jù)，然后這些數(shù)據(jù)副本并行寫入SM中其

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

25、，第25頁，共50頁。1.3 并行計算模型2. 異步APRAM（MIMD-SM）模型 P.28模型特性每個處理器有其局部存儲器、局部時鐘、局部程序；無全局時鐘，各處理器異步執(zhí)行；處理器通過SM進行通訊、交換數(shù)據(jù)；處理器之間的依賴關(guān)系，需在并行算法（程序）中顯式地加入同步路障語句來指定同步，即軟件同步。算法（程序）設(shè)計難度比APRAM模型稍難些。時間復(fù)雜度分析：并行（并發(fā)）進程生成時間、并行計算時間、并行（并發(fā)）進程計算（處理）過程中的同步時間、并行（并發(fā)）進程結(jié)束的同步時間。指令類型：全局讀、全局寫、局部操作、同步計算時間 設(shè)局部操作為單位時間；全局讀/寫平均時間為d，d隨著處理器數(shù)目的增加而

26、增加；同步路障時間為B=B(p)非降函數(shù)。 令 為全局相內(nèi)各處理器執(zhí)行時間最長者，則APRAM上的計算時間為： 注：多核處理結(jié)構(gòu)的多核計算模型就是異步APRAM（MIMD-SM）模型。第26頁，共50頁。1.3 并行計算模型2. 異步APRAM（MIMD-SM）模型計算過程 異步APRAM（MIMD-SM）模型的計算過程由同步障分開的全局相組成。第27頁，共50頁。1.3 并行計算模型1.3.3 分布存儲的并行計算模型1. SIMD-IN（ SIMD-DM）模型分布存儲SIMD模型模型特性每個處理器均自己的存儲器（分布式存儲）；處理器之間通過互連網(wǎng)絡(luò)相連，采用傳遞數(shù)據(jù)方式實現(xiàn)通訊；運行在各處理

27、器的算法（進程）同步并行執(zhí)行，處理器之間同步由硬件實現(xiàn)；算法時間復(fù)雜度分析：計算時間和選路(路由，通信)時間。有些應(yīng)用所需的選路(路由，通信)時間比其計算時間還要多。模型的結(jié)構(gòu)圖第28頁，共50頁。1.3 并行計算模型1.3.3 分布存儲的并行計算模型1. SIMD-IN（ SIMD-DM）模型分布存儲SIMD模型SIMD-IN（SIMD-DM）模型的常見模型 SIMD-LC 一維線性連接 SIMD-MC 網(wǎng)孔連接 SIMD-TC 樹形連接 SIMD-MT 樹網(wǎng)連接 SIMD-HC 超立方連接 SIMD-CCC 立方環(huán)連接 SIMD-SE 洗牌交換連接 SIMD-BF 蝶形網(wǎng)絡(luò) SIMD-MI

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

29、andwidth第30頁，共50頁。1.3 并行計算模型1.3.3 分布存儲的并行計算模型2. BSP模型計算過程 BSP模型的計算過程由若干超級步組成 強調(diào)計算過程與通信過程的分離 限制至多h條消息的傳遞等第31頁，共50頁。1.3 并行計算模型1.3.3 分布存儲的并行計算模型3. LogP模型模型特性分布存儲的MIMD模型點到點通訊的多處理機模型，其中通訊由一組參數(shù)描述隱藏了并行機的網(wǎng)絡(luò)拓撲、路由、協(xié)議，可以應(yīng)用到共享存儲、消息傳遞、數(shù)據(jù)并行的編程模型中處理機之間實行隱式同步，即硬件同步算法描述、設(shè)計和分析困難模型參數(shù)L：network latencyo：communication ov

30、erheadg：gap=1/bandwidthP：#processors注：L和g反映了通訊網(wǎng)絡(luò)的容量第32頁，共50頁。1.3 并行計算模型1.3.4 層次存儲的并行計算模型1. 串行計算系統(tǒng)的層次存儲模型 （P.34-35）HMM（層次存儲）模型和HMM-BT（塊傳輸?shù)膶哟未鎯Γ┠Ｐ蚒MH （均勻存儲層次）模型RAM(h)模型h層隨機存儲模型2. 并行計算系統(tǒng)的層次存儲模型 （P.36-37）Memory-LogP模型 （ 共享存儲-分布存儲模型）DRAM（h）模型分布式h層隨機存儲模型本地結(jié)點模型為RAM(h)模型h層隨機存儲模型。 p個本地處理機結(jié)點通過互連網(wǎng)絡(luò)連接起來。處理機結(jié)點之間

31、采用點到點消息傳遞方式交換信息。將消息傳遞看成是另一層的存儲層次訪問；集合消息傳遞看成是另一層并發(fā)存儲訪問 方便分析并行算法復(fù)雜度DRAM(h)模型=RAM(h)模型+LogP遠程存儲訪問模型。 SMP-Cluster，多核處理器機群系統(tǒng)就屬于DRAM（h）模型的實例。HPM模型層次并行和存儲模型第33頁，共50頁。1.3 并行計算模型1.3.5 其他并行計算模型MIMD-AC模型異步通信分布式計算模型比較器網(wǎng)絡(luò)心動陣列和波前陣列判定樹有向五環(huán)圖 量子計算模型 量子物理，量子信息，量子位（Qubit），量子寄存器，n位的量子寄存器可表述 2n種狀態(tài)，可并行地對量子寄存器中 2n種狀態(tài)進行操作。

32、量子計算機具有海量存儲和天然并行性的特征。分子計算模型 用分子表示“處理（計算）單元”，分子狀態(tài)表示數(shù)據(jù)（信息）值，并行地對分子操作，所有分子同時產(chǎn)生反應(yīng)、改變分子狀態(tài)（改變數(shù)據(jù)值）。空間并行性。第34頁，共50頁。1.4 并行算法的基礎(chǔ)知識1.4.1 并行算法的定義與分類 1. 定義 并行算法： 一組可同時執(zhí)行且可互相協(xié)作的諸進程的集合。 2. 分類 VLSI并行算法：在VLSI計算模型上開發(fā)的并行算法 第35頁，共50頁。1.4 并行算法的基礎(chǔ)知識1.4.2 并行算法的表述1. do stepi to stepj in parallel 強調(diào)stepi , stepj 要并行執(zhí)行 step

33、i stepj enddo2. for all par-do 語句強調(diào)n 個進程（線程）并行執(zhí)行，每個進程（線程）均執(zhí)行語句S1,S2,.Sk,，但每個進程計算處理的數(shù)據(jù)對象不同 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 語句強調(diào)p個處理器并行執(zhí)行，每個處理器均執(zhí)行語句S1,S2,.Sk,，但每個處理器計算處理的數(shù)據(jù)對象不同 for all Pi, where 0ip-1 par-do 或 for all Pi, where 0i p-1

34、do in parallel S1 S1 . . Sk Sk end for endfor 第36頁，共50頁。1.4 并行算法的基礎(chǔ)知識1.4.3 并行算法復(fù)雜性的度量1、串行算法復(fù)雜性的度量 算法復(fù)雜性用關(guān)于輸入數(shù)據(jù)規(guī)模n的函數(shù)f(n)來度量，特別是用當(dāng)n充分大時f(n)的漸近度增長函數(shù)來度量一些記號f(n)=O(g(n) 當(dāng)n充分大時，f(n) cg(n), c常數(shù) f(n)=Omega(g(n) 當(dāng)n充分大時，f(n)cg(n), c常數(shù)f(n)=Qita(g(n) 當(dāng)n充分大時，c1 g(n) f(n) c2 g(n), c1 ， c2常數(shù)平均情形復(fù)雜度、最壞情形復(fù)雜度第37頁，共5

35、0頁。1.4 并行算法的基礎(chǔ)知識1.4.3 并行算法復(fù)雜性的度量 2. 并行算法復(fù)雜性的度量運行時間t(n): t(n)= tc (n) + tr (n) 計算時間tc (n)和選路(路由，通信)時間tr (n)處理器數(shù)目p(n)， p(n) =n1-e, 0ep(n)，則為超線性加速(一般出現(xiàn)在某些特殊的應(yīng)用中，如人工智能中的并行搜索等)并行效率Ep(n)：Ep(n)=Sp(n)/p(n)， 0用p臺處理器去完成并行算法A的第i時刻工作量，需時間 =用p臺處理器模擬并行算法A的總時間為 Brent定理揭示了并行算法工作量和運行時間的關(guān)系；提供了并行算法的WT(Work-Time)表示方法；指

36、明了設(shè)計并行算法時應(yīng)盡可能將每個時間步的工作量均勻地分攤給p臺處理器，使各處理器處于活躍狀態(tài)。第42頁，共50頁。算法1.1 SIMD-SM模型上并行求和算法（高層描述不考慮處理器數(shù)目及其分配） / 數(shù)據(jù)A1.n, n=2k Begin(1) for i=1 to n do in parallel /時間O(1 ), 工作量n Bi=Ai; / A為原始數(shù)組 endfor(2) for h=1 to log2n do / h為邏輯二叉樹的層號 / h層上n/2h個結(jié)點（進程） 并行執(zhí)行 for i = 1 to n/2h do in parallel / 時間 O(1 ), 工作量n/2h B

37、i=B2i-1+B2i; endfor endif(3) S=B1; / 時間O(1), 工作量1 endfor End.時間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)第43頁，共50頁。算法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

38、An-1 An第44頁，共50頁。算法1.2 SIMD-SM模型上并行求和算法（低層描述考慮處理器數(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 /時間O(n/p ) Bm(s-1)+j=Am(s-1)+j; / O(1)時間，A為原始數(shù)組 endfor(1.2)for h=1 to log2n do / h為邏輯二叉樹的層號 (1.2.1) if (k-q-h)=

39、0 then / h層上并行工作量（結(jié)點數(shù)）大于等于處理器數(shù) for i= 2k-h-q (s-1)+1 to 2k-h-q *s do / 時間 O(2k-h-q )=O(n/(p*2h) Bi=B2i-1+B2i; endfor endif (1.2.2) if s= 2k-h then / 時間O(1),當(dāng)前第s個子樹的和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 ) )+

40、O(1)+O(n/(p2logn )+O(1)+O(1)=O(n/p+log2n)第45頁，共50頁。1.5 并行算法的同步與通信1、并行算法的同步同步是在時間上強使各執(zhí)行進程在某一點必須互相等待，確保各進程的正常順序和對共享可寫數(shù)據(jù)的正確訪問?？捎密浖?、硬件和固件的辦法來實現(xiàn)同步：SIMD-SM(PRAM)/SIMD-IN上并行算法由硬件實現(xiàn)同步。MIMD-SM (APRAM) 上并行算法由軟件（算法）實現(xiàn)同步：例如，使用lock和unlock等同步語句顯式設(shè)置臨界區(qū)實現(xiàn)多個并發(fā)進程（線程）對共享變量的互斥訪問。算法復(fù)雜度還包括進程生成時間、進程結(jié)束同步時間。同步示例 MIMD-SM (AP

41、RAM)上的異步并行求和算法輸入：A=(a0,an-1), 處理器數(shù)p輸出：S=ai Begin (1) S=0； / S共享全局變量（總和） (2.3) lock(S) / 同步 (2) for all Pi where 0ip-1 para-do /異步并行/ 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第46頁，共50頁。 | | P0 P1 P p-2 Pp-1(主）進程0 進程1 進程p-2 進程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+