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

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

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

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

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

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

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

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

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

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

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