并行計算第一講

并行計算介紹Outline234IBM2000年它的速度高達每秒12.3萬億次浮點運算，就是說，它一秒鐘內(nèi)完成的工作量，相當于一個人使用計算器用1000萬年時間完成的工作量。并行計算研究內(nèi)容5并行計算機的體系結(jié)構(gòu)并行算法設(shè)計與分析并行實現(xiàn)技術(shù)：編程實現(xiàn)，優(yōu)化性能并行應(yīng)用：開發(fā)并行應(yīng)用軟件并行計算機的發(fā)展始于70年代1946年第一臺計算機ENIAC（ElectronicNumericalIntegratorAndComputer）占地170平方重約30噸5000次加法/秒或500次乘法/秒15分鐘換一個零件主要用于彈道計算和氫彈研制6ElectronicNumericalIntegratorAndCalculator，即電子數(shù)字積分計算機并行計算機的發(fā)展始于70年代1972年第一臺并行計算機ILLIAC-IV（伊利諾依大學(xué)）----------------------------------------------------60年代末開始建造72年建成,74年運行第一個完整程序,76年運行第一個應(yīng)用程序64個處理器，是當時性能最高的CDC7600機器的2-6倍公認的1981年前最快1982年退役可擴展性好，但可編程性差78并行計算機的發(fā)展9并行計算機的發(fā)展10并行計算機的發(fā)展11并行計算機的發(fā)展90年代：體系結(jié)構(gòu)框架趨于統(tǒng)一(DSM、MPP、NOW)DSM（DistributedSharedMemory）分布式共享存儲以結(jié)點為單位，每個結(jié)點有一個或多個CPU專用的高性能互聯(lián)網(wǎng)絡(luò)連接（Myrinet,Infiniband,…）分布式存儲：內(nèi)存模塊局部在每個結(jié)點中單一的操作系統(tǒng)單一的內(nèi)存地址空間：所有內(nèi)存模塊都由硬件進行了統(tǒng)一的編址，各個結(jié)點既可以直接訪問局部內(nèi)存單元，又可以直接訪問其他結(jié)點的局部內(nèi)存單元可擴展到上百個結(jié)點支持消息傳遞、共享存儲并行程序設(shè)計12并行計算機的發(fā)展13并行計算機的發(fā)展90年代：體系結(jié)構(gòu)框架趨于統(tǒng)一MPP（MassivelyParallelProcessing）大規(guī)模并行處理結(jié)構(gòu)每個結(jié)點相對獨立，有一個或多個微處理器每個結(jié)點均有自己的操作系統(tǒng)各個結(jié)點自己獨立的內(nèi)存，避免內(nèi)存訪問瓶頸各個結(jié)點只能訪問自己的內(nèi)存模塊擴展性較好DM-MPP分布式存儲MPP：每個結(jié)點僅包含一個微處理器SMP-MPP：每個結(jié)點是一臺SMP并行機DSM-MPP：每個結(jié)點是一臺DSM并行機14并行計算機的發(fā)展15并行計算機的發(fā)展90年代：體系結(jié)構(gòu)框架趨于統(tǒng)一NOW（NetworkofWorkstations）工作站機群

投資風險小、結(jié)構(gòu)靈活、可擴展性強、通用性好、異構(gòu)能力強，被大量中小型計算用戶和科研院校所采用

每個結(jié)點安裝消息傳遞并行程序設(shè)計軟件，實現(xiàn)通信、負載平衡等每個結(jié)點都是一個完整的工作站，有獨立的硬盤與UNIX系統(tǒng)結(jié)點間通過低成本的網(wǎng)絡(luò)（如千兆以太網(wǎng)）連接也稱為COW（ClusterofWorkstations）NOW（COW）與MPP之間的界線越來越模糊16并行計算機的發(fā)展17并行計算機的發(fā)展第一臺Beowulf機群18并行計算機的發(fā)展2000年至今：前所未有大踏步發(fā)展Cluster機群每個結(jié)點含多個商用處理器，結(jié)點內(nèi)部共享存儲采用商用機群交換機通過前端總線連接結(jié)點，結(jié)點分布存儲各個結(jié)點采用Linux操作系統(tǒng)、GNU編譯系統(tǒng)和作業(yè)管理系統(tǒng)Constellation星群每個結(jié)點是一臺子并行機采用商用機群交換機通過前端總線連接結(jié)點，結(jié)點分布存儲各個結(jié)點運行專用的結(jié)點操作系統(tǒng)、編譯系統(tǒng)和作業(yè)管理系統(tǒng)MPP專用高性能網(wǎng)絡(luò)，大多為政府直接支持19并行計算機的發(fā)展并行計算機發(fā)展趨勢由于向量機和MPP受研制費用高、售價高等因素的影響，其市場受到一定的限制SMP由于共享結(jié)構(gòu)的限制，系統(tǒng)的規(guī)模不可能很大

由于機群系統(tǒng)具有投資風險小、可擴展性好、可繼承現(xiàn)有軟硬件資源和開發(fā)周期短、可編程性好等特點，目前已成為并行處理的熱點和主流20我國并行計算機的發(fā)展情況第一臺計算機1958年第一臺國產(chǎn)計算機－－103型計算機運行速度每秒1500次21我國高性能計算機的發(fā)展22我國高性能計算機的發(fā)展1999年9月，由國家并行計算機工程技術(shù)研究中心牽頭研制成功的“神威”計算機系統(tǒng)投入運行。2000年，“神威I”面向社會開放使用?！吧裢蘒”的峰值速度為每秒3840億次浮點運算23我國高性能計算機的發(fā)展情況241993年10月研制成功“曙光一號”SMP多處理機2000年推出每秒3000億次的曙光3000超級服務(wù)器2004年6月，推出11萬億次的曙光4000A超級計算機，落戶上海超算中心，進入全球前十名，從而使中國成為繼美國和日本之后，第三個能研制10萬億次高性能計算機的國家2008年6月，曙光5000A發(fā)布，實際運算速度超過每秒160萬億次，排名世界第十，曙光5000A我國高性能計算機的發(fā)展情況252002年，聯(lián)想發(fā)布深騰1800計算機，排名全球第43位，成為首家正式進入排行榜前100的中國企業(yè)2003年，深騰6800計算機發(fā)布，列全世界TOP500第14位，其78.5%的整機效率列世界通用高端計算機第一名2008年12月，聯(lián)想發(fā)布百萬億次超級計算機深騰7000深騰7000當前高性能計算機26當前高性能計算機27當前高性能計算機28當前高性能計算機29當前高性能計算機30當前高性能計算機31當前高性能計算機32并行計算機發(fā)展趨勢33國內(nèi)超級計算中心國家高性能計算中心國家高性能計算中心（北京）1995年5月成立，第一個高性能計算中心國家高性能計算中心（合肥）：1995年9月，中科大國家高性能計算中心（成都）：1997年11月，西南交大國家高性能計算中心（武漢）：1997年12月，華中科技國家高性能計算中心（上海）：1998年4月，復(fù)旦大學(xué)國家高性能計算中心（杭州）：2001年4月，浙江大學(xué)國家高性能計算中心（西安）：2002年4月，西安交大國內(nèi)超級計算中心34并行計算機體系結(jié)構(gòu)35操作系統(tǒng)與編程語言并行計算機主流操作系統(tǒng)：UNIX/LinuxAIX（IBM）HPUX（HP）Solaris（SUN）IRIX（SGI）Linux編程語言Fortran77/90/95C/C++36進程與線程進程（process）運行中的程序各個進程擁有獨立的執(zhí)行環(huán)境進程間通信同一臺處理機或不同處理機的多個進程之間交流信息通信（消息傳遞）、同步、聚集線程（threads）降低系統(tǒng)管理開銷一個進程可以含一個或多個線程37并行編程環(huán)境38并行算法39并行算法適合在并行機上實現(xiàn)的算法好的并行算法應(yīng)充分發(fā)揮并行機計算機的潛在性能并行算法分類按運算對象：數(shù)值并行算法、非數(shù)值并行算法按并行進程執(zhí)行順序：同步并行算法、異步并行算法、獨立并行算法按計算任務(wù)：細粒度并行算法（基于向量和循環(huán)級并行）中粒度并行算法（基于較大的循環(huán)級并行）大粒度并行算法（基于子任務(wù)級并行）并行算法設(shè)計40并行算法設(shè)計以MIMD為主(MultipleInstructionStreamMultipleDataStream)可擴展、可移植大粒度任務(wù)級并行每個進程發(fā)揮單機性能（數(shù)據(jù)結(jié)構(gòu)、程序設(shè)計、通信方式）并行計算--高性能計算并行計算(ParallelComputing）

高端計算(High-endParallelComputing)

高性能計算(HighPerformanceComputing)

超級計算(SuperComputing)

任何高性能計算和超級計算都離不開使用并行技術(shù)計算科學(xué)與傳統(tǒng)的兩種科學(xué)，即理論科學(xué)和實驗科學(xué)，并立被認為是人類認識自然的三大支柱，他們彼此相輔相成地推動科學(xué)發(fā)展與社會進步。在許多情況下，或者是理論模型復(fù)雜甚至理論尚未建立，或者實驗費用昂貴甚至無法進行時，計算就成了求解問題的唯一或主要的手段。并行:古老的思想!“...并行計算并不是什么新的思想,只是將它擴展應(yīng)用于計算機而已”.作者也不認為這種擴展應(yīng)用會存在什么無法克服的困難.但也不要期待有效的并行編程方法與技術(shù)能夠在一夜之間誕生.期間還需要有許多的工作和實驗要做.畢竟,今天的編程技術(shù)(串行)是若干年來艱苦的探索才取得的.現(xiàn)在編程工作似乎成了一種令人單調(diào)乏味的工作,事實上,并行編程的出現(xiàn)將會使重新恢復(fù)編程工作者們的探索精神...”(Gill,S.(1958),“ParallelProgramming”

TheComputerJournal,vol.1,April,pp.2-10.)ParallelProgrammingwithMPIbyPeterPacheco(2000)什么是并行計算?并行計算:

由運行在多個部件上的小任務(wù)合作來求解一個規(guī)模很大的計算問題的一種方法例:在曙光2000上用8個節(jié)點計算的Mandelbrot集結(jié)果(Mandelbrot為分形理論創(chuàng)始人)44/149現(xiàn)代計算機的共同特點：

并行性45/149現(xiàn)代計算機的共同特點：

并行性46/149為什么要做并行計算？

－－應(yīng)用需求為什么要做并行計算？人類對計算及性能的要求是無止境的從系統(tǒng)的角度：集成系統(tǒng)資源，以滿足不斷增長的對性能和功能的要求

從應(yīng)用的角度：適當分解應(yīng)用，以實現(xiàn)更大規(guī)?；蚋氈碌挠嬎銥槭裁匆霾⑿杏嬎?？問題:科學(xué)和工程問題的數(shù)值模擬與仿真計算密集數(shù)據(jù)密集網(wǎng)絡(luò)密集三種混合要求:在合理的時限內(nèi)完成計算任務(wù)秒級 制造業(yè)分鐘級 短時天氣預(yù)報(當天)小時級 中期天氣預(yù)報(3~10日)盡可能快 長期天氣預(yù)報(氣候)可計算 湍流模擬2004年4月49/149并行計算的功能降低單個問題求解的時間增加問題求解規(guī)模、提高問題求解精度(多機同時執(zhí)行多個串行程序)容錯、更高的可用性、提高吞吐率如何實現(xiàn)并行計算?分而治之!2004年4月52/149分而治之并行化的主要方法:分而治之根據(jù)問題的求解過程，把任務(wù)分成若干子任務(wù)(任務(wù)級并行或功能并行)根據(jù)處理數(shù)據(jù)的方式，形成多個相對獨立的數(shù)據(jù)區(qū)，由不同的處理器分別處理(數(shù)據(jù)并行)并行計算軟件環(huán)境及現(xiàn)狀操作系統(tǒng)：UNIX、LINUX、WindowsNT在SMP,DSM并行機上編譯系統(tǒng)通常具有一定的對用戶程序(C/Fortran)進程自動并行化的能力,但經(jīng)常需要人工干預(yù)(通過編譯制導(dǎo),命令行選項等)以達到理想的并行效率.且并行主要針對循環(huán)進行(屬于細粒度并行);在分布式內(nèi)存并行機上尚無通過高效的自動并行工具,主要依靠人工編寫并行程序;并行算法的設(shè)計及并行程序的編制已成為目前特約大規(guī)模并行計算機應(yīng)用的主要障礙.并行編程現(xiàn)狀:并行軟件開發(fā)遠遠落后于并行系統(tǒng)體系結(jié)構(gòu)的發(fā)展。缺少合適的并行軟件是阻礙主流用戶社會接納并行計算的原因。:與串行軟件相比，并行軟件數(shù)量少，功能原始。??編程環(huán)境落后的并行編譯器、調(diào)試器vs.通用先進的串行編程環(huán)境.自動并行編譯器遠遠滿足不了程序并行化的要求.3算法并行模型的多樣化(并行計算機系統(tǒng)結(jié)構(gòu)的多樣性)vs.串行編程中的唯一模型:馮.諾依曼模型問題的并行求解的困難在于問題的多樣性和求解過程中所需的創(chuàng)造性勞動，使得這一過程難以進行自動化對串行機而言,解法=唯一串行算法+計算程序(通用)對并行機而言,解法=某種并行算法+有針對性的計算程序(很難通用)J人稀少而初級的并行編程人員vs.成熟而經(jīng)驗豐富的串行程序員一些途徑充分利用順序程序開發(fā)的經(jīng)驗、方法和工具，特別是順序領(lǐng)域中的問題求解、算法設(shè)計方法，這是簡化并行程序開發(fā)的重要手段。并行程序開發(fā)的困難主要在于問題的并行求解，而不是并行程序設(shè)計語言?！皬氖虏⑿谐绦蛟O(shè)計實踐的人往往把精力耗費在為變量分配內(nèi)存、為循環(huán)體尋求并行上，卻忽略對問題本身的分析。其實能否并行的決定因素是應(yīng)用問題本身?！痹诓⑿兴惴ǖ脑O(shè)計階段最大限度地開發(fā)出問題本身固有的并行性才是提高計算效率的根本手段。只有粗粒度的并行，才能具有高的計算通信比，而粗粒度的并行只能在算法設(shè)計階段開發(fā)出來并行軟件程序員的工作指令層，非常細的粒度數(shù)據(jù)層，細粒度控制層，中粒度任務(wù)層，大粒度

前兩層大都由硬件和編譯器負責處理，程序員通常處理后兩層的并行

并行程序設(shè)計方法隱式并行程序設(shè)計：常用傳統(tǒng)的語言編程成順序源編碼，把“并行”交給編譯器實現(xiàn)自動并行程序的自動并行化是一個理想目標，存在難以克服的困難語言容易，編譯器難顯式并行程序設(shè)計：在用戶程序中出現(xiàn)“并行”的調(diào)度語句顯式的并行程序開發(fā)則是解決并行程序開發(fā)困難的切實可行的語言難，編譯器容易并行程序設(shè)計模型隱式并行（ImplicitParallel）數(shù)據(jù)并行（DataParallel）共享變量（SharedVariable）消息傳遞（MessagePassing）隱式并行(ImplicitParallel)概況：程序員用熟悉的串行語言編程(未作明確的制定并行性)編譯器和運行支持系統(tǒng)自動轉(zhuǎn)化為并行代碼特點：語義簡單可移植性好單線程，易于調(diào)試和驗證正確性細粒度并行效率很低數(shù)據(jù)并行（DataParallel）概況：SIMD的自然模型局部計算和數(shù)據(jù)選路操作特點：單線程并行操作于聚合數(shù)據(jù)結(jié)構(gòu)（數(shù)組）松散同步單一地址空間隱式交互作用顯式數(shù)據(jù)分布優(yōu)點:編程相對簡單,串并行程序一致.缺點:程序的性能在很大程度上依賴于所用的編譯系統(tǒng)及用戶對編譯系統(tǒng)的了解.并行粒度局限于數(shù)據(jù)級并行,粒度較小.共享變量(SharedVariable)概況：PVP,SMP,DSM的自然模型特點：多線程：SPMD,MPMD異步單一地址空間顯式同步隱式數(shù)據(jù)分布隱式通信典型代表：OpenMP消息傳遞(MessagePassing)概況：MPP、COW的自然模型特點：多線程異步多地址空間顯式同步顯式數(shù)據(jù)映射和負載分配顯式通信典型代表MPI、PVM并行編程標準數(shù)據(jù)并行語言標準Fortran90,HPF(1992),Fortran95/2001:顯式數(shù)據(jù)分布描述,并行DO循環(huán).線程庫標準(ThreadLibrary)–Win32API.–POSIXthreads線程模型.編譯制導(dǎo)