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

并行算法實踐上篇并行程序設(shè)計導(dǎo)論2023/2/31現(xiàn)代密碼學(xué)理論與實踐之五并行算法實踐

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

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

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

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

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

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

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

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

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