并行計算1并行計算介紹

什么是并行計算基本概念并行計算機的發展我國并行計算機的發展情況當前最快的超級計算機并行計算機體系結構并行算法2并行計算傳統的軟件是為串行計算機而編寫的:在只有一個處理器的單臺計算機上運行

把一個問題分解成離散的指令序列

指令被一條條的順序執行任何時候只有一條指令在執行3并行計算的應用需求

數值天氣預報全球氣象中期天氣預報要求在24

小時內完成48

小時天氣預測數值模擬，至少需635

萬個網格點，內存需求大于1T，計算性能高達25

萬億次/秒.

核武器數值模擬美國1996年實施的ASCI計劃，分四個階段實現萬億次、十萬億次、30萬億次和100萬億次大規模并行數值模擬，實現全三維、全物理過程、高分辨率的核武器數值模擬.并行計算能力已成為衡量一個國家綜合實力的重要標志之一！4并行計算機系統的應用領域數學基因信息氣象預報生物物理石油勘探信息服務汽車制造船舶制造5并行計算并行計算（高性能計算、超級計算）大任務分解多個子任務不同處理單元分

給快速求解協同合作基本條件：

硬件（并行機）、并行算法設計、并行編程環境主要目標：提高求解速度，擴大問題規模6串行計算與并行計算78組成并行計算機的各個部分：節點（node）互聯網絡（interconnectnetwork）內存（memory）內存模塊與節點分離內存模塊位于節點內部并行計算8并行計算介紹什么是并行計算基本概念并行計算機的發展我國并行計算機的發展情況當前最快的超級計算機弗林經典分類并行計算機體系結構并行算法9弗林根據指令和數據這兩個獨立維度的情況，對多處理器計算機結構進行了如下分類SISD單指令流單數據流SIMD單指令流多數據流MISD多指令流單數據流MIMD多指令流多數據流基本概念10單指令流單數據流(SISD)一個串行(非并行)計算機

單指令流:在任何一個時鐘周期，CPU中只有一個指令流在活動。單數據流:在任何一個時鐘周期，只有一個數據流作為輸入在被使用。執行結果是確定的。從很早一直到現在，這都是計算機的最主要的形式。基本概念11單指令流多數據流(SIMD)并行計算機的一種

。單指令流:在任何一個時鐘周期，CPU中只有一個指令流在活動。多數據流:每個處理單元能在不同的數據元素上進行操作。最適合具有高度規律性的特殊的問題，比如圖像處理。同步（步調一致）和確定的執行兩種類型:處理器陣列和向量流水線基本概念12多指令流單數據流(MISD)單一的數據流流入多個處理器單元去處理每個處理器單元通過獨立的指令流對數據進行處理這種類型的并行計算機很少有存在的例子，有一個實驗室的產品是卡內基梅隴大學的C.mmp計算機(1971)。

一些想象中的可能應用：

多種頻率的濾波器處理同一個信號流用多個密碼算法嘗試解開一個編碼信息。基本概念13多指令流多數據流(MIMD)目前最常用的并行計算機。大多數現代計算機屬于這一類多指令流:每個處理器可以執行不同的指令流多數據流:每個處理器可以工作在不同的數據流上執行可以是同步的或者異步的，確定的或者不確定的舉例:很多目前的巨型計算機、網絡并行計算機“網格”、多處理器SMP計算機以及多核處理器。基本概念14基本概念15并行計算機存儲結構多級存儲體系結構為了解決存儲墻（memorywall）性能瓶頸問題。在節點內部的cache稱為二級cache（L2cache）。在處理器內部更小的cache成為一級cache(L1cache)L1cache連接CPU寄存器和L2cache，負責緩存L2cache中的數據到寄存器中。1616微處理器的多級存儲結構

微機機群的一次消息傳遞延遲相當于

50000次峰值浮點運算17微處理器的多級存儲結構

微處理器主頻越來越高，內存容量越來越大，

但內存訪問速度的增長較慢

緩解內存墻性能瓶頸：Cache高速緩存18并行計算機體系結構并行計算機體系

結構示意圖

內存模塊與結點分離并行計算機體系

結構示意圖

內存模塊位于

結點內部19并行計算機存儲結構多級存儲體系結構Cache的映射策略指的是內存塊和cache行之間如何建立相互映射關系。直接映射策略（directmappingstrategy）每個內存塊只能被唯一的映射到一條cache行中K－路組相聯映射策略（K-waysetassociationmappingstrategy）Cache被分解為V個組，每個組由K個cache行組成，內存塊按直接映射策略映射到某個組，但在該組中，內存塊可以被映射到任意一個cache行。全相聯映射策略（fullassociationmappingstrategy）內存塊可以被映射到cache中的任意一個cache行。20并行計算機存儲結構分布式存儲MEMORYNODEMEMORYNODEMEMORYNODEMEMORYNODEnetworkNODE（節點）=單處理器或多處理器21并行計算機存儲結構分布式存儲-NORMA(No-RemoteMemoryAccess)節點有它們自己的局部存儲器。一個節點內的存儲器地址不會映射到其他節點上，所以在全部節點中沒有全局地址空間的概念。因為每一個節點有它自己局部存儲器它們獨立地操作。因此Cache一致性的概念不存在。當一個節點需要存取另一個節點的數據（很少見），通常要程序員明確提供如何以及何時數據被傳送的信息。22并行計算機存儲結構分布式存儲優點增加節點數，就自然成比例地增加了存儲容量.每個節點能快速地存取它自己的存儲器而無需干涉也沒有試圖保持Cache一致性的開銷。成本效率:可以用商業化的，現成的處理器和網絡。缺點

如果數據在兩個節點間傳送，就要求程序員提供很多有關數據傳送的細節。很難將現在基于全局存儲的已有數據結構映射到這種存儲組織中。非均勻內存訪問(NUMA)時間

23并行計算機存儲結構共享存儲NODEMEMORYNODE（節點）=單處理器或多處理器NODENODENODE24并行計算機存儲結構共享存儲共享存儲的并行計算機千差萬別，但都能夠使所有的節點以全局地址空間的形式訪問全部的存儲器空間。多個節點可以獨立操作但又可共享相同的存儲資源。在一個節點上改變一個存儲位置的值對其他節點來說也是可見和可用的。25并行計算機存儲結構共享存儲均勻存儲訪問(UMA):存儲器和節點分離物理存儲器能夠通過互聯網絡被所有節點共享。發生訪存競爭時，仲裁策略平等對待每個節點，即每個節點機會均等；外圍I/O設備也可以共享，且每個節點有平等的訪問權利。最常見的代表是當前的對稱多處理器機器(SMP)26并行計算機存儲結構共享存儲均勻存儲訪問(UMA):所有節點訪問任意存儲單元的時間相同；各節點的CPU可帶有局部私有高速緩存；互聯網絡可以是單總線、多總線或者交叉開關。

有時候稱為CC-UMA–Cache一致性UMA.Cache一致性意味著如果一個處理器修改了共享存儲器中的某個位置的數，其他的所有處理器都知道這個改變。Cache的一致性在硬件一級完成。27network并行計算機存儲結構分布式共享存儲器(DSM)NODENODEMEMORYNODENODENODENODEMEMORYNODENODENODENODEMEMORYNODENODENODENODEMEMORYNODENODENODE（節點）=單處理器或多處理器28并行計算機存儲結構分布式共享存儲器(DSM)共享存儲器部分通常是一個Cache一致性的SMP機器。在給定的SMP中的處理器，能夠以全局方式尋址這個機器的存儲器。分布式存儲部分是多個SMP聯網。SMP只知道它們自己的存儲器-不是在其他SMP上的存儲器。因此，需要網絡通信來將數據從一個SMP移動到另一個。目前的趨勢似乎表明這種類型的存儲結構將繼續盛行，并將在高端計算機上得到增強。29并行計算機存儲結構分布式共享存儲器(DSM)非均勻存儲訪問(NUMA)每個節點都有共享存儲的一部分（局部存儲器）存儲器只有一個地址空間任何節點都可以實際地址直接訪問任何存儲器每個節點都可以有局部Cache不是所有的節點能夠以相同的時間訪問所有的存儲器，訪問時間與該存儲器到該節點的距離有關。跨鏈接的存儲訪問比較慢如果保持Cache一致性，它也可以稱為CC-NUMA–Cache一致性NUMA3031并行計算機存儲結構分布式共享存儲器全高速緩存存儲訪問(COMA):每個節點擁有共享存儲的一部分。然而，這次共享存儲器是由Cache組成的。沒有層次性存儲，地址空間是針對Cache的。有一個Cache目錄來幫助遠程Cache訪問。需要將數據轉移到需要它的節點上。3132并行計算機存儲結構分布式共享存儲器優點全局地址空間提供一個用戶友好的訪存編程方式。由于節點與內存接近，任務間的數據共享快速統一缺點

增加一些節點會使得存儲器到節點的路徑的擁擠程度成幾何增大。對于cache一致性系統，增加更多的節點會使得與cache/存儲器管理相關聯的沖突成幾何增長。程序員的責任就是能確保全局存儲的正確訪問的同步結構。32并行計算機系統架構33以動物的食物鏈為例并行計算機系統架構34并行計算機系統架構35對稱多處理機系統(SMP)SMP對稱式共享存儲:任意處理器可直接訪問任意內存地址,且訪問延遲、帶寬、機率都是等價的;系統是對稱的；微處理器:一般少于64個;處理器不能太多,總線和交叉開關的一旦作成難于擴展；例子:IBMR50,SGIPowerChallenge,SUNEnterprise,36分布式共享存儲系統(DSM)DSM分布共享存儲:內存模塊物理上局部于各個處理器內部,但邏輯上(用戶)是共享存儲的;這種結構也稱為基于Cache目錄的非一致內存訪問(CC-NUMA)結構;局部與遠程內存訪問的延遲和帶寬不一致;與SMP的主要區別：DSM在物理上有分布在各個節點的局部內存從而形成一個共享的存儲器；微處理器:16-128個;代表:SGIOrigin2000,CrayT3D;37大規模并行計算機系統(MPP)MPP物理和邏輯上均是分布內存能擴展至成百上千個處理器(微處理器或向量處理器)采用高通信帶寬和低延遲的互聯網絡(專門設計和定制的)一種異步的MIMD機器；程序系由多個進程組成，每個都有其私有地址空間，進程間采用傳遞消息相互作用；代表:CRAYT3E(2048),ASCIRed(3072),IBMSP238機群系統(Cluster)Cluster每個節點都是一個完整的計算機各個節點通過高性能網絡相互連接網絡接口和I/O總線松耦合連接每個節點有完整的操作系統曙光2000、3000、4000,ASCIBlueMountain39并行計算機的發展始于70年代

1946年第一臺計算機ENIAC

（ElectronicNumericalIntegratorAndComputer）占地170平方重約30噸

5000次加法/秒

或500次乘法/秒

15分鐘換一個零件主要用于彈道計算

和氫彈研制40并行計算機的發展始于70年代

1972年第一臺并行計算機ILLIACIV（伊利諾依大學）60年代末開始建造

72年建成,74年運行

第一個完整程序,

76年

運行第一個應用程序

64個處理器，是當時

性能最高的CDC7600

機器的2-6倍公認的1981年前最快1982年退役可擴展性好，

但可編程性差41并行計算機的發展始于70年代向量機Cray-1

一般將Cray-1投入

運行的1976年稱為

“超級計算元年”編程方便，

但可擴展性差以Cray為代表的

向量機稱雄超級

計算機界十幾載收藏于DeutschesMuseum德意志

博物館的Cray-1原型42并行計算機的發展

80年代百家爭鳴早期：以MIMD并行計算機的研制為主

DenelcorHEP

（1982年）第一臺商用MIMD并行計算機

CrayX-MP

Cray研究公司第一臺MIMD并行計算機

IBM309080

年代普遍為銀行所采用西摩?克雷SeymourCray(1925-1996)，

電子工程學學士，應用數學碩士，

超級計算機之父，Cray研究公司的創始人，

親手設計了Cray機型的全部硬件與操作系統，

作業系統由他用機器碼編寫完成。1984年時，

公司占據了超級計算機市場70%的份額。

1996年Cray研究公司被SGI收購，2000年被

出售給Tera計算機公司，成立Cray公司。43并行計算機的發展

80年代百家爭鳴中期：共享存儲多處理機Shared-MemoryMultiProcessor

SMP

(SymmetricalMulti-Processing)：在一個計算機上匯集一組處理器，各處理器對稱共享內存及計算機的其他資源，由單一操作系統管理，極大提高整個系統的數據處理能力。

擴展性較差可靠性較差內存訪問瓶頸44并行計算機的發展

80年代百家爭鳴后期：具有強大計算能力的并行機

通過二維Mesh連接的Meiko（Sun）系統

超立方體連接的MIMD并行機：nCUBE-2、iPSC/80共享存儲向量多處理機CrayY-MP

······45并行計算機的發展

90年代：體系結構框架趨于統一(DSM、MPP、NOW)

DSM（DistributedSharedMemory）分布式共享存儲以結點為單位，每個結點有一個或多個CPU專用的高性能互聯網絡連接（Myrinet,Infiniband,…）分布式存儲：內存模塊局部在每個結點中單一的操作系統單一的內存地址空間：所有內存模塊都由硬件進行了統一的編址，各個結點既可以直接訪問局部內存單元，又可以直接訪問其他結點的局部內存單元可擴展到上百個結點支持消息傳遞、共享存儲并行程序設計46并行計算機的發展

90年代：體系結構框架趨于統一

DSM（DistributedSharedMemory）分布式共享存儲47并行計算機的發展

90年代：體系結構框架趨于統一

MPP（MassivelyParallelProcessing）大規模并行處理結構

每個結點相對獨立，有一個或多個微處理器每個結點均有自己的操作系統各個結點自己獨立的內存，避免內存訪問瓶頸各個結點只能訪問自己的內存模塊擴展性較好

DM-MPP分布式存儲MPP：每個結點僅包含一個微處理器

SMP-MPP：每個結點是一臺SMP并行機

DSM-MPP：每個結點是一臺DSM并行機48并行計算機的發展

MPP體系結構示意圖

90年代：體系結構框架趨于統一49并行計算機的發展

90年代：體系結構框架趨于統一

NOW（NetworkofWorkstations）工作站機群投資風險小、結構靈活、可擴展性強、通用性好、異構能力強，被大量中小型計算用戶和科研院校所采用每個結點安裝消息傳遞并行程序設計軟件，實現通信、負載平衡等每個結點都是一個完整的工作站，有獨立的硬盤與UNIX系統結點間通過低成本的網絡（如千兆以太網）連接也稱為COW（ClusterofWorkstations）

NOW（COW）與MPP之間的界線越來越模糊50并行計算機的發展

NOW的典型代表：Beowulfcluster微機機群性能價格比極高

90年代：體系結構框架趨于統一51并行計算機的發展第一臺Beowulf機群52并行計算機的發展

2000年至今：前所未有大踏步發展

Cluster機群

Constellation星群每個結點含多個商用處理器，結點內部共享存儲

采用商用機群交換機通過前端總線連接結點，結點分布存儲各個結點采用Linux操作系統、GNU編譯系統和作業管理系統每個結點是一臺子并行機采用商用機群交換機通過前端總線連接結點，結點分布存儲各個結點運行專用的結點操作系統、編譯系統和作業管理系統

MPP專用高性能網絡，大多為政府直接支持53并行計算機的發展并行計算機發展趨勢由于向量機和MPP

受研制費用高、售價高等因素的影響，其市場受到一定的限制

SMP

由于共享結構的限制，系統的規模不可能很大由于機群系統具有投資風險小、可擴展性好、可繼承現有軟硬件資源和開發周期短、可編程性好等特點，目前已成為并行處理的熱點和主流54并行計算介紹什么是并行計算并行計算機的發展我國并行計算機的發展情況當前最快的超級計算機并行計算機體系結構操作系統與并行計算編程環境并行算法55我國高性能計算機的發展

1958年第一臺國產計算機

－－103型計算機運行速度每秒1500次第一臺計算機56我國高性能計算機的發展

1983年12月，我國第一臺每秒鐘運算達1億次以上的計算機“銀河I”問世

1992年“銀河-II”問世，每秒運算達10億次

1997年成功研制百億次并行機“銀河-III”，由130多個處理結點組成超級計算機曙光（曙光信息產業有限公司

）深騰（聯想集團）銀河神威軍事部門57我國高性能計算機的發展

1999年9月，由國家并行計算機工程技術研究中心牽頭研制成功的“神威”計算機系統投入運行。2000年，“神威I”面向社會開放使用。“神威I”的峰值速度為每秒3840億次浮點運算神威

I58我國高性能計算機的發展

1993年10月研制成功“曙光一號”SMP多處理機

2000年推出每秒3000億次的曙光3000超級服務器

2004年6月，推出11萬億次的曙光4000A超級計算機，落戶上海超算中心，進入全球前十名，從而使中國成為繼美國和日本之后，第三個能研制10萬億次高性能計算機的國家

2008年6月，曙光5000A發布，實際運算速度超過每秒160萬億次，排名世界第十曙光5000A59我國高性能計算機的發展

2002年，聯想發布深騰1800計算機，排名全球第43位，成為首家正式進入排行榜前100的中國企業

2003年，深騰6800計算機發布，列全世界TOP500第14位，其78.5%的整機效率列世界通用高端計算機第一名

2008年12月，聯想發布百萬億次超級計算機深騰7000深騰700060并行計算介紹什么是并行計算并行計算機的發展我國并行計算機的發展情況當前最快的超級計算機并行計算機體系結構操作系統與并行計算編程環境并行算法61當前高性能計算機

Top500：2007年11月排名第一的

IBMBlueGene/L由212992

個處理器構成，內存為73728G

理論峰值為596378

GFlops測試峰值478200

GFlops

2008年06月排名第二62當前高性能計算機63當前高性能計算機64當前高性能計算機

并行機類型Architecturesharefor06/200965當前高性能計算機

并行機采用的操作系統OperatingsystemFamilysharefor06/200966當前高性能計算機

并行機采用的網絡鏈接67

并行計算機發展趨勢68國內高性能計算機

Top100inChina：http:///曙光公司中國科學院計算技術研究所國家智能計算機研究開發中心國家高性能計算中心

合作伙伴：AMD、上海超級計算中心最新產品：曙光5000A（百萬億次）聯想公司合作伙伴：Intel、中科院計算機網絡中心（超級計算中心）最新產品：深騰7000（百萬億次）69國內超級計算中心國家高性能計算中心

國家高性能計算中心（北京）

1995年5月成立，第一個高性能計算中心

國家高性能計算中心（合肥）：1995年9月，中科大

國家高性能計算中心（成都）：1997年11月，西南交大

國家高性能計算中心（武漢）：1997年12月，華中科技

國家高性能計算中心（上海）：1998年4月，復旦大學

國家高性能計算中心（杭州）：2001年4月，浙江大學

國家高性能計算中心（西安）：2002年4月，西安交大70并行計算介紹什么是并行計算并行計算機的發展我國并行計算機的發展情況當前的超級計算機并行計算機體系結構操作系統與并行計算編程環境并行算法71操作系統與編程語言并行計算機主流操作系統：UNIX/Linux

AIX（IBM）

HPUX（HP）

Solaris（SUN）

IRIX（SGI）

Linux編程語言

Fortran77/90/95

C/C++72進程與線程進程（process）運行中的程序各個進程擁有獨立的執行環境進程間通信同一臺處理機或不同處理機的多個進程之間交流信息通信（消息傳遞）、同步、聚集線程（threads）降低系統管理開銷一個進程可以含一個或多個線程73并行編程環境常見的并行編程環境消息傳遞、共享存儲、數據并行特征消息傳遞共享數據數據并行典型代表

可移植性

存儲方式

學習難度

可擴展性MPI，PVM

所有流行并行機

分布式存儲

較難

好OpenMP

SMP，DSM

共享存儲

容易

較差HPF

SMP，DSM，MPP

共享存儲

偏易

一般三種并行編程環境主要特征一覽74并行計算介紹什么是并行計算并行計算機的發展我國并行計算機的發展情況當前的超級計算機并行計算機體系結構操作系統與并行計算編程環境并行算法75并行算法適合在并行機上實現的算法

好的并行算法應充分發揮并行機計算機的潛在性能并行算法并行算法分類按運算對象：數值并行算法、非數值并行算法

按并行進程執行順序：

同步并行算法、異步并行