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

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

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