中科大-并行計算講義-并行計算機系統(tǒng)與結構模型

并行算法實踐上篇并行程序設計導論2023/2/31現代密碼學理論與實踐之五并行算法實踐

上篇并行程序設計導論單元I并行程序設計基礎單元II并行程序編程指南單元III并行程序開發(fā)方法2023/2/32現代密碼學理論與實踐之五單元I并行程序設計基礎第一章并行計算機系統(tǒng)與結構模型第二章PC機群的搭建第三章并行程序設計簡介2023/2/33現代密碼學理論與實踐之五第一章并行計算機系統(tǒng)與結構模型1.1典型并行計算機系統(tǒng)簡介1.1.1陣列處理機1.1.2向量處理機1.1.3共享存儲多處理機1.1.4分布存儲多計算機1.1.5分布共享存儲多處理機1.2當代并行計算機體系結構1.2.1并行計算機體系結構模型1.2.2并行計算機存儲結構模型1.2.3分布式高速緩存與主存體系結構1.3小結2023/2/34現代密碼學理論與實踐之五陣列處理機向量處理機共享存儲多處理機分布存儲多計算機典型并行計算機系統(tǒng)分布存儲共享存儲流水線并行向量機緊耦合多機系統(tǒng)同構對稱對機系統(tǒng)DSM/SVM2023/2/35現代密碼學理論與實踐之五陣列處理機的兩種基本結構

(a)分布存儲陣列機(b)共享存儲陣列機2023/2/36現代密碼學理論與實踐之五陣列處理機的特點SIMD－單指令多數據流機利用資源重復開拓計算空間的并行同步計算－－所有PE執(zhí)行相同操作適于特定問題（如有限差分、矩陣運算等）求解2023/2/37現代密碼學理論與實踐之五Cray-1的向量處理2023/2/38現代密碼學理論與實踐之五共享存儲的多處理機MIMD－多指令多數據流機單一的共享地址空間易于編程、難于擴展存儲訪問可成為性能瓶頸緊耦合與同構對稱方式2023/2/39現代密碼學理論與實踐之五典型的緊耦合多處理機系統(tǒng)2023/2/310現代密碼學理論與實踐之五Balance同構對稱多處理機系統(tǒng)2023/2/311現代密碼學理論與實踐之五分布存儲多計算機松散耦合多機系統(tǒng)節(jié)點獨立（可有局存、IO設備等）易于擴展多地址空間消息傳遞通信界面難于編程2023/2/312現代密碼學理論與實踐之五IntelParagon系統(tǒng)框圖2023/2/313現代密碼學理論與實踐之五分布共享存儲多處理機分布共享存儲DSM－DistributedSharedMemory

將物理上分布的存儲系統(tǒng)，通過硬件和軟件的辦法，向用戶提供一個單一的全局地址空間易于編程易于擴展2023/2/314現代密碼學理論與實踐之五并行計算機體系結構單指令多數據流機SIMD（Single-InstructionMultiple-Data）；并行向量處理機PVP（ParallelVectorProcessor）；對稱多處理機SMP（SymmetricMultiprocessor）；大規(guī)模并行處理機MPP(MassivelyParallelProcessor)；工作站機群COW(ClusterofWorkstation)分布式共享存儲DSM(DistributedSharedMemory)多處理機。

2023/2/315現代密碼學理論與實踐之五并行計算機體系結構模型2023/2/316現代密碼學理論與實踐之五對稱多處理機SMP(1)SMP:采用商用微處理器，通常有片上和片外Cache，基于總線連接，集中式共享存儲，UMA結構例子：SGIPowerChallenge,DECAlphaServer,Dawning12023/2/317現代密碼學理論與實踐之五對稱多處理機SMP(2)優(yōu)點對稱性單地址空間，易編程性，動態(tài)負載平衡，無需顯示數據分配高速緩存及其一致性，數據局部性，硬件維持一致性低通信延遲，Load/Store完成問題欠可靠，BUS,OS,SM通信延遲（相對于CPU），競爭加劇慢速增加的帶寬（MBdouble/3年,IOB更慢）不可擴放性---〉CC-NUMA2023/2/318現代密碼學理論與實踐之五大規(guī)模并行機MPP成百上千個處理器組成的大規(guī)模計算機系統(tǒng)，規(guī)模是變化的。NORMA結構，高帶寬低延遲定制互連?？蓴U放性：Mem,I/O,平衡設計系統(tǒng)成本：商用處理器，相對穩(wěn)定的結構，SMP,分布通用性和可用性：不同的應用，PVM,MPI,交互，批處理，互連對用戶透明，單一系統(tǒng)映象，故障通信要求存儲器和I/O能力例子：IntelOptionRed

IBMSP2Dawning10002023/2/319現代密碼學理論與實踐之五典型MPP系統(tǒng)特性比較MPP模型Intel/SandiaASCIOptionRedIBMSP2SGI/CrayOrigin2000一個大型樣機的配置9072個處理器，1.8Tflop/s(NSL)400個處理器，100Gflop/s(MHPCC)128個處理器，51Gflop/s(NCSA)問世日期1996年12月1994年9月1996年10月處理器類型200MHz,200Mflop/sPentiumPro67MHz，267Mflop/sPOWER2200MHz，400Mflop/sMIPSR10000節(jié)點體系結構和數據存儲器2個處理器，32到256MB主存，共享磁盤1個處理器，64MB到2GB本地主存，1GB到14.5GB本地磁盤2個處理器，64MB到256MB分布共享主存和共享磁盤互連網絡和主存模型分離兩維網孔，NORMA多級網絡，NORMA胖超立方體網絡，CC-NUMA節(jié)點操作系統(tǒng)輕量級內核（LWK）完全AIX（IBMUNIX）微內核CellularIRIX自然編程機制基于PUMAPortals的MPIMPI和PVMPowerC，PowerFortran其他編程模型Nx，PVM，HPFHPF，LindaMPI，PVM2023/2/320現代密碼學理論與實踐之五機群型大規(guī)模并行機SP2設計策略：機群體系結構標準環(huán)境標準編程模型系統(tǒng)可用性精選的單一系統(tǒng)映像系統(tǒng)結構：高性能開關HPS多級Ω網絡寬節(jié)點、窄節(jié)點和窄節(jié)點22023/2/321現代密碼學理論與實踐之五工作站機群COW分布式存儲，MIMD，工作站+商用互連網絡，每個節(jié)點是一個完整的計算機，有自己的磁盤和操作系統(tǒng)，而MPP中只有微內核優(yōu)點：投資風險小系統(tǒng)結構靈活性能/價格比高能充分利用分散的計算資源可擴放性好問題通信性能并行編程環(huán)境例子：BerkeleyNOW，AlphaFarm,FXCOWP/CMMIOMIOMP/CNICNICDDLAN2023/2/322現代密碼學理論與實踐之五典型的機群系統(tǒng)典型的機群系統(tǒng)特點一覽表名稱系統(tǒng)特點Princeton:SHRIMPPC商用組件，通過專用網絡接口達到共享虛擬存儲，支持有效通信Karsruhe:Parastation用于分布并行處理的有效通信網絡和軟件開發(fā)Rice:TreadMarks軟件實現分布共享存儲的工作站機群Wisconsin:WindTunnel在經由商用網絡互連的工作站機群上實現分布共享存儲Chica、Maryl、Penns:NSCP國家可擴放機群計劃：在通過因特網互連的3個本地機群系統(tǒng)上進行元計算Argonne:Globus在由ATM連接的北美17個站點的WAN上開發(fā)元計算平臺和軟件Syracuse:WWVM使用因特網和HPCC技術，在世界范圍的虛擬機上進行高性能計算HKU:PearlCluster研究機群在分布式多媒體和金融數字庫方面的應用Virgina:Legion在國家虛擬計算機設施上開發(fā)元計算軟件2023/2/323現代密碼學理論與實踐之五SMP\MPP\機群比較系統(tǒng)特征SMPMPP機群節(jié)點數量(N)O(10)O(100)-O(1000)O(100)節(jié)點復雜度中粒度或細粒度細粒度或中粒度中粒度或粗粒度節(jié)點間通信

共享存儲器消息傳遞或共享變量（有DSM時）消息傳遞節(jié)點操作系統(tǒng)1N(微內核)和1個主機OS(單一)N(希望為同構)支持單一系統(tǒng)映像永遠部分希望地址空間單一多或單一（有DSM時）多個作業(yè)調度單一運行隊列主機上單一運行隊列協作多隊列網絡協議非標準非標準標準或非標準可用性通常較低低到中高可用或容錯性能/價格比一般一般高互連網絡總線/交叉開關定制商用2023/2/324現代密碼學理論與實踐之五五種結構特性一覽表屬性PVPSMPMPPDSMCOW結構類型MIMDMIMDMIMDMIMDMIMD處理器類型專用定制商用商用商用商用互連網絡定制交叉開關總線、交叉開關定制網絡定制網絡商用網絡以太,ATM通信機制共享變量共享變量消息傳遞共享變量消息傳遞地址空間單地址空間單地址空間多地址空間單地址空間多地址空間系統(tǒng)存儲器集中共享集中共享分布非共享分布共享分布非共享訪存模型UMAUMANORMANUMANORMA代表機器CrayC-90，CrayT-90，銀河1號IBMR50，SGIPowerChallenge，曙光1號IntelParagon，IBMSP2，曙光1000/2000StanfordDASH，CrayT3DBerkeleyNOW，AlphaFarm2023/2/325現代密碼學理論與實踐之五并行計算機訪存模型均勻存儲訪問模型－UMA非均勻存儲訪問模型－NUMA全高速緩存訪問模型－COMA高速緩存一致性非均勻存儲訪問模型－CC-NUMA非遠程存儲訪問模型－NORMA2023/2/326現代密碼學理論與實踐之五UMA訪存模型UMA（UniformMemoryAccess）模型是均勻存儲訪問模型的簡稱。其特點是：物理存儲器被所有處理器均勻共享；所有處理器訪問任何存儲字取相同的時間；每臺處理器可帶私有高速緩存；外圍設備也可以一定形式共享。2023/2/327現代密碼學理論與實踐之五NUMA訪存模型NUMA(NonuniformMemoryAccess)模型是非均勻存儲訪問模型的簡稱。特點是：被共享的存儲器在物理上是分布在所有的處理器中的，其所有本地存儲器的集合就組成了全局地址空間；處理器訪問存儲器的時間是不一樣的；訪問本地存儲器LM或群內共享存儲器CSM較快，而訪問外地的存儲器或全局共享存儲器GSM較慢(此即非均勻存儲訪問名稱的由來)；每臺處理器照例可帶私有高速緩存，外設也可以某種形式共享。

LM1P1LM2P2LMnPn互連網絡(a)共享本地存儲模型全局互連網絡(b)層次式機群模型GSMGSMGSM…………PCINCSMPPCSMCSM群1……PCINCSM群NPPCSMCSM……2023/2/328現代密碼學理論與實踐之五COMA訪存模型COMA(Cache-OnlyMemoryAccess)模型是全高速緩存存儲訪問的簡稱。其特點是：各處理器節(jié)點中沒有存儲層次結構，全部高速緩存組成了全局地址空間；利用分布的高速緩存目錄D進行遠程高速緩存的訪問;COMA中的高速緩存容量一般都大于2級高速緩存容量；使用COMA時，數據開始時可任意分配，因為在運行時它最終會被遷移到要用到它們的地方。

2023/2/329現代密碼學理論與實踐之五CC-NUMA訪存模型CC-NUMA（Coherent-CacheNonuniformMemoryAccess）模型是高速緩存一致性非均勻存儲訪問模型的簡稱。其特點是：大多數使用基于目錄的高速緩存一致性協議；保留SMP結構易于編程的優(yōu)點，也改善常規(guī)SMP的可擴放性；CC-NUMA實際上是一個分布共享存儲的DSM多處理機系統(tǒng)；它最顯著的優(yōu)點是程序員無需明確地在節(jié)點上分配數據，系統(tǒng)的硬件和軟件開始時自動在各節(jié)點分配數據，在運行期間，高速緩存一致性硬件會自動地將數據遷移至要用到它的地方。

2023/2/330現代密碼學理論與實踐之五NORMA訪存模型NORMA（No-RemoteMemoryAccess）模型是非遠程存儲訪問模型的簡稱。NORMA的特點是：所有存儲器是私有的；絕大數NUMA都不支持遠程存儲器的訪問；在DSM中，NORMA就消