并行算法與并行程序設(shè)計 第01章 概論(新)

第一章概論《并行算法與并行程序設(shè)計》三、并行與并發(fā)并行(Parallel)并發(fā)(Concurrence)四、相關(guān)領(lǐng)域與概念高性能計算(HighPerformanceComputing)分布式計算(DistributedComputing)物聯(lián)網(wǎng)(TheInternetofThings)網(wǎng)格計算(GridComputing)云計算(CloudComputing)智慧的地球(SmarterPlanet)……二、并行計算的需求和現(xiàn)狀計算機系統(tǒng)性能的提高僅僅依靠硬件性能的提高是不夠的。很多重大技術(shù)問題和應(yīng)用都需要高性能的并行計算才能解決。并行計算的復(fù)雜程度遠高于串行計算的復(fù)雜程度。并行計算相比串行計算的研究還遠不夠成熟和完善。一、并行計算應(yīng)用實例SETI@home計劃，1999年5月~2004年6月，共計500萬人參加計算，197萬年計算機工作時間，5.2*1021次浮點運算，處理超過13億個數(shù)據(jù)單元。一、并行計算應(yīng)用實例Manyhandsmakelightwork.一、并行計算應(yīng)用實例10000m2的機房，HP刀片式服務(wù)器，總計4萬多個處理器，104TB

RAM。五、并行計算機模型并行模型的語義屬性同構(gòu)性在執(zhí)行并行程序時，并行計算機中處理器行為的相似程度。如SISD、SIMD、SPMD、MIMD。同步性進程同步的嚴格程度。指令同步、超步同步、松散同步、異步。交互機制并行進程間如何相互影響行為的特性。共享變量、消息傳遞。地址空間單地址空間、多地址空間。存儲器模型如何處理共享存儲器的訪問沖突。CRCW、CREW、ERCW、EREW五、并行計算機模型并行模型的性能屬性機器規(guī)模n可用處理器的個數(shù)。時鐘速率f MHz單一處理器的時鐘速率。工作負載W Mfloat程序的計算量，或計算操作數(shù)。串行執(zhí)行時間T1 s參考的串行程序執(zhí)行所需要的時間。并行執(zhí)行時間Tn s在機器規(guī)模為n的情況下，并行程序執(zhí)行所需要的時間。速度 Pn=W/Tn Mfloat/s在機器規(guī)模為n的情況下，并行計算的平均速度。五、并行計算機模型并行模型的性能屬性加速比Sn=T1/Tn在處理器規(guī)模為n的情況下，并行計算相對于串行計算的加速倍數(shù)。上限為n。效率En=Sn/n在處理器規(guī)模為n的情況下，并行計算相對于串行計算的有效率。上限為1。利用率Un=Pn/Ppeak在處理器規(guī)模為n的情況下，各處理器計算能力的平均利用比率。Ppeak是處理器的峰值處理速度。上限為1。通信啟動時間t0 μs0字節(jié)或短消息（如單字）的通信時間，也稱為通信時延。漸近帶寬r∞ MB/s通信長消息的速率。五、并行計算機模型抽象機模型PRAM模型機器規(guī)模n可任意大。指令同步，每一執(zhí)行周期每個處理器執(zhí)行一條指令。每一周期中，各處理器蘊式同步，同步開銷、通信開銷、并行性開銷忽略不計，只計負載不平衡開銷。通過讀寫共享變量進行通信。PRAM模型對零開銷和指令同步的假設(shè)是不現(xiàn)實的，而且現(xiàn)行機器規(guī)模n通常也比較小，復(fù)雜度并不能真實反映算法的性能。PRAM模型對現(xiàn)實機器模型的模擬很不精確，但因其簡單性，仍是開發(fā)高級并行算法的一個良好的模型。五、并行計算機模型抽象機模型BSP模型由哈佛大學(xué)LeslieValiant提出，以克服PRAM模型的缺點，但仍保留其簡單性。一個BSP計算機由n個[處理器/存儲器]對（結(jié)點）組成，通過通信網(wǎng)絡(luò)進行互連。一個BSP程序有n個進程，每個駐留在一個結(jié)點上，按嚴格超步序列執(zhí)行。BSP模型是MIMD系統(tǒng)，進程能同時執(zhí)行不同指令。在一個超步中，不同進程以不同的速率異步執(zhí)行。BSP模型有一個單地址空間，一個處理器不但能訪問它的局部存儲器，還能以通信方式訪問其他結(jié)點上的遠程存儲器。在一個超步內(nèi)，每個計算操作都只使用局部存儲器。采用路障同步，在一個超步內(nèi)，所有存儲操作和通信操作完成后，才能開始下一個超步。BSP模型考慮了除用于進程管理的并行性開銷外的所有其他開銷，更為現(xiàn)實。五、并行計算機模型抽象機模型階段并行模型一個并行程序以一系列階段加以執(zhí)行，在當(dāng)前階段的所有操作未完成之前，不能開始下一階段的操作。共有三類階段：并行化階段：涉及進程管理的開銷階段。計算階段：處理器執(zhí)行若干局部計算操作，結(jié)點所需的所有數(shù)據(jù)均可在局部存儲器中訪問到。交互階段：完成交互操作所需執(zhí)行的任務(wù)，如通信、同步或是聚集操作。五、并行計算機模型物理機模型SIMD單指令多數(shù)據(jù)流機–多為專用型計算機MIMD并行向量處理機(PVP)基本構(gòu)件多采用定制對稱多處理機(SMP)大規(guī)模并行處理機(MPP)工作站群/計算機機群(COW)分布共享存儲器多處理機(DSM)五、并行計算機模型物理機模型并行向量處理機(PVP)VP：定制向量處理器，數(shù)量不多，功能很強。SM：共享存儲器。PVP通常不使用高速緩存，而是使用大量向量寄存器以及指令緩存。VPVPSMSMSM…………定制高帶寬縱橫交叉開關(guān)網(wǎng)絡(luò)VP五、并行計算機模型物理機模型對稱多處理機(SMP)P/C：微處理器和高速緩存。SM：共享存儲器。與PVP不同，采用商品化微處理器，帶有片內(nèi)和片外高速緩存。對稱性指每個處理器平等地訪問共享存儲器、I/O部件以及操作系統(tǒng)服務(wù)。使用集中式共享存儲器和總線或交叉網(wǎng)絡(luò)的系統(tǒng)互連，一旦建成就難以擴展。P/CP/CP/CSMSMSM…………總線或縱橫交叉開關(guān)網(wǎng)絡(luò)五、并行計算機模型物理機模型分布共享存儲器多處理機(DSM)P/C：微處理器和高速緩存LM：本地存儲器DIR：高速緩存目錄，用來支持分布式一致高速緩存。NIC：網(wǎng)絡(luò)接口電路MB：存儲器總線DSM與SMP（對稱多處理機）的主要區(qū)別在于DSM的存儲器是分布在各結(jié)點中的，但系統(tǒng)通過硬件和軟件為用戶建立了一個單地址空間的幻覺。五、并行計算機模型物理機模型大規(guī)模并行處理機(MPP)P/C：微處理器和高速緩存LM：本地存儲器NIC：網(wǎng)絡(luò)接口電路MB：存儲器總線P/CLMNICMBP/CLMNICMB……定制網(wǎng)絡(luò)五、并行計算機模型物理機模型大規(guī)模并行處理機(MPP)在處理結(jié)點中使用商品化微處理器。在處理結(jié)點內(nèi)使用物理上分布的存儲器。使用具有高通信帶寬和低時速的互連。能擴展成具有成百甚至成千個處理器。類似于多處理機模型，是異步MIMD機，但進程同步采用鎖式消息傳遞操作，而不是用共享變量同步操作加以實現(xiàn)。程序由多個進程組成，每個進程有自己的私有地址空間。通過消息傳遞實現(xiàn)進程間互相作用。結(jié)點間用高速、專用通信網(wǎng)加以互連，稱這些結(jié)點為緊耦合的。五、并行計算機模型物理機模型工作站機群/計算機機群(COW)COW的每個結(jié)點可以是一個完整的工作站，不包含某些外設(shè)（如監(jiān)視器、鍵盤、鼠標等），也可以是一臺SMP或PC。結(jié)點間一般通過低廉的商品化網(wǎng)絡(luò)，如以太網(wǎng)、FDDI、光通道、ATM開關(guān)實現(xiàn)互連。不同于MPP，COW的網(wǎng)絡(luò)接口與結(jié)點中的I/O總線松耦合相連。通常都有一個局部磁盤，而MPP結(jié)點中可能沒有。每個結(jié)點上駐留著一個完整的操作系統(tǒng)，而在MPP的某些結(jié)點中可能只有操作系統(tǒng)的微核。六、并行程序設(shè)計并行處理的特點自治性：各處理器在工作時是相互獨立的。合作性：各處理器共同完成一個整體任務(wù)，相互之間有協(xié)作關(guān)系，有數(shù)據(jù)通信。同時性：各處理器同時都在執(zhí)行指令，而不是交錯執(zhí)行。六、并行程序設(shè)計并行計算舉例設(shè)有稠密矩陣A和B，計算C=A*B。假設(shè)，A2*2，B2*2，則：cij=ai1*b1j+ai2b2j i,j=1,2若動用4個處理器Pij，分別計算cij，則可以同時進行計算。在一個并行計算步中，就可以完成計算?？疾煜旅娴睦樱篖1:x←1L2:x←2*xL3:x←3*x該例不具備并行性。六、并行程序設(shè)計并行程序設(shè)計方法學(xué)并行程序設(shè)計方法學(xué)與順序程序設(shè)計方法學(xué)的主要區(qū)別在于對問題的看法。順序程序設(shè)計方法學(xué)將問題或事物的變化理解為單線程的，由一系列不可分割的有因果關(guān)系的統(tǒng)一事物；而并行程序設(shè)計方法學(xué)最基本的一個觀點，就是把行為看作是多個事物相互作用的結(jié)果，因此并行程序設(shè)計的第一工作就是對問題作并行劃分。并行程序設(shè)計方法學(xué)的核心就是并行劃分和算法映射，其理論基礎(chǔ)是并行計算模型。六、并行程序設(shè)計并行編程的困難所在并行編程比順序編程更為復(fù)雜。并行編程有許多不同的可參考模型。并行編程的工具軟件相對落后。并行編程的程序累積遠不如順序編程。六、并行程序設(shè)計并行編程模型指令式編程模型蘊式并行程序員不顯式地說明并行性，通過編譯器和運行支持系統(tǒng)自動加入并行性。常見的是利用專門的并行化編譯器，對順序程序?qū)嵭凶詣硬⑿谢删幾g器對源代碼進行相關(guān)性分析，通過一組變換技術(shù)將順序代碼轉(zhuǎn)換為并行代碼。這種編譯器也稱為并行化編譯器或重構(gòu)編譯器。其難點在于并行編譯器的有效性。數(shù)據(jù)并行適用于SIMD或SPMD方式，主要思想是在多個計算結(jié)點上對不同的數(shù)據(jù)集同時執(zhí)行相同的指令或程序段。消息傳遞各進程異步執(zhí)行，通過路障或鎖定通信實現(xiàn)同步，是一種粗粒度的MIMD。共享變量共享變量模型擁有單地址空間（與數(shù)據(jù)并行類似），是多線程化和異步的（與消息傳遞相似）。六、并行程序設(shè)計并行編程模型函數(shù)式編程函數(shù)式編程描述計算的輸入與輸出之間的函數(shù)關(guān)系，由編譯器和運行時間系統(tǒng)根據(jù)函數(shù)說明生成執(zhí)行代碼。邏輯編程邏輯編程不對控制流和函數(shù)進行說明，而是說明要計算的是什么，即輸入與輸出之間的邏輯關(guān)系，由編譯器和運行系統(tǒng)從邏輯說明中推導(dǎo)出一個算法。通過學(xué)習(xí)進行計算通過學(xué)習(xí)進行計算首先是構(gòu)造一個學(xué)習(xí)程序，然后將許多例子提供給學(xué)習(xí)算法，由它最終生成可完成該任務(wù)的算法。六、并行程序設(shè)計實現(xiàn)并行編程系統(tǒng)的方法庫子程序擴展新構(gòu)造的并行編程語言多是在Fortran或Ｃ的基礎(chǔ)擴展得到的。編譯器命令擴展方法實例優(yōu)點缺點庫例程MPI,PVM,CrayCraft易于實現(xiàn)，不需要新的編譯器無編譯器檢查、分析和優(yōu)化新構(gòu)造Fortran90,CrayCraft允許編譯器檢查、分析和優(yōu)化實現(xiàn)困難，需要新編譯器命令HPF,CrayCraft介于兩者之間，在串行平臺上不起作用for(i=0;i<N;i++)A[i]=b[i]*b[i+1];for(i=0;i<N;i++)c[i]=A[i]+A[i+1];串行代碼段id=my_process_id();p=number_of_processes();for(i=id;i<N;i=i+p)A[i]=b[i]*b[i+1];barrier();for(i=id;i<N;i=i+p)c[i]=A[i]+A[i+1];使用庫例程的并行代碼my_process_id(),nmber_of_processes(),andbarrier()A(0:N-1)=b(0:N-1)*b(1:N)c=A(0:N-1)+A(1:N)使用新構(gòu)造并行程序設(shè)計語言的并行代碼#pragmaparallel#pragmashared(A,b,c)#pragmalocal(i){#pragmapforiterate(i=0;N;1)for(i=0;i<N;i++)A[i]=b[i]*b[i+1];#pragmasynchronize#pragmapforiterate(i=0;N;1)for(i=0;i<N;i++)c[i]=A[i]+A[i+1];}使用編譯器命令的并行代碼六、并行程序設(shè)計并行算法范例并行算法范例并行算法范例是指構(gòu)造算法的方法以使其能在并行機系統(tǒng)上運行。階段并行分治法流水線進程農(nóng)莊工作池六、并行程序設(shè)計并行算法范例階段并行階段并行是一個廣泛使用的范例。程序由一些超步組成，每一超步分兩階段。在計算階段，多個進程中的每一個完成一個獨立計算。此后是交互階段，進程完成一個或多個同步交互操作，如一個路障或一個鎖定通信。然后再執(zhí)行下一超步。該范例也稱為松馳同步范例。其缺點是：交互與計算不相重迭；在進程間很難保持平衡的工作負載。CCC……CCC……同步交互同步交互六、并行程序設(shè)計并行算法范例分治法缺點是難以達到負載平衡。六、并行程序設(shè)計并行算法范例流水線有大量數(shù)據(jù)需要重復(fù)進行某一宏操作，該宏操作可以被分解為若干子操作順序執(zhí)行，這時就可以采用流水線操作方式使各子操作能夠同步執(zhí)行。PQR