《并行處理與體系結(jié)構(gòu)1》

《并行處理與體系結(jié)構(gòu)》計(jì)算機(jī)學(xué)院計(jì)算機(jī)體系結(jié)構(gòu)教研室嵌入式系統(tǒng)研究中心

張老師引言

SuperComputer超級(jí)計(jì)算機(jī)2011.11.8“天河一號(hào)”超級(jí)計(jì)算機(jī)“天河一號(hào)”超級(jí)計(jì)算機(jī)“天河一號(hào)”計(jì)算機(jī)排名世界第五天河一號(hào)”計(jì)算機(jī)排名“亞洲第一”基本信息數(shù)字1：速度1“天河一號(hào)”計(jì)算一天１６０年全系統(tǒng)峰值性能為每秒１２０６萬(wàn)億次實(shí)測(cè)性能為每秒５６３．１萬(wàn)億次相當(dāng)于SPEED基本信息數(shù)字2：共享存儲(chǔ)總?cè)萘?“天河一號(hào)”共享存儲(chǔ)總?cè)萘?個(gè)國(guó)家圖書館共享存儲(chǔ)總?cè)萘繛椋保校孪喈?dāng)于存儲(chǔ)容量基本信息數(shù)字3：大小與重量119個(gè)神舟飛船相當(dāng)于占地重量…“天河一號(hào)”重量基本信息數(shù)字4：處理器1“天河一號(hào)”處理器處理器包括6144個(gè)IntelXeonE5540/E5450處理器5120個(gè)AMDRadeonHD4870X2顯卡基本信息數(shù)字5：互聯(lián)通信速率1“天河一號(hào)”互聯(lián)結(jié)構(gòu)一條信息高速公路互聯(lián)通信網(wǎng)絡(luò)的單根線傳輸速率為１０Ｇｂｐｓ相當(dāng)于內(nèi)部修建Interaction目前國(guó)際上最快的速率基本信息數(shù)字6：速度1“天河一號(hào)”造價(jià)“天河一號(hào)”目前投資為６億人民幣使用壽命預(yù)計(jì)為１０年價(jià)值MONEY６億人民幣863“高效能計(jì)算機(jī)及網(wǎng)格服務(wù)環(huán)境”重大項(xiàng)目“千萬(wàn)億次高效能計(jì)算機(jī)系統(tǒng)研制”課題成果國(guó)家超級(jí)計(jì)算天津中心的業(yè)務(wù)主機(jī)，部署于天津市濱海新區(qū)中國(guó)國(guó)家網(wǎng)格計(jì)算主結(jié)點(diǎn)基本信息結(jié)構(gòu)特點(diǎn)1√√√研制背景6144個(gè)通用處理器5120個(gè)加速處理器內(nèi)存總?cè)萘?8TB√√√天河一號(hào)典型系統(tǒng)配置點(diǎn)點(diǎn)通信帶寬40Gbps共享磁盤總?cè)萘繛?PB.√√①計(jì)算陣列2560個(gè)計(jì)算結(jié)點(diǎn)；每個(gè)計(jì)算結(jié)點(diǎn)集成2個(gè)IntelCPU，配32GB內(nèi)存；②加速陣列2560個(gè)加速結(jié)點(diǎn)；每個(gè)加速結(jié)點(diǎn)含2個(gè)AMDGPU、2GB顯存；③服務(wù)陣列512個(gè)服務(wù)結(jié)點(diǎn)每個(gè)服務(wù)結(jié)點(diǎn)含2個(gè)IntelEPCPU、32GB內(nèi)存④互聯(lián)通信子系統(tǒng)采用兩級(jí)InfinibandQDR互聯(lián)；單個(gè)通信鏈路的通信帶寬為40Gbps，延遲1.2微妙；⑤I/O存儲(chǔ)子系統(tǒng)采用全局分布共享并行I/O系統(tǒng)結(jié)構(gòu)；磁盤總?cè)萘?PB⑥監(jiān)控子系統(tǒng)采用分布式集中管理結(jié)構(gòu)，實(shí)現(xiàn)全系統(tǒng)的實(shí)時(shí)安全檢測(cè)、系統(tǒng)控制和調(diào)試診斷功能H硬件系統(tǒng) 由計(jì)算陣列、加速陣列、服務(wù)陣列，以及互聯(lián)通信子系統(tǒng)、I/o存儲(chǔ)子系統(tǒng)和

監(jiān)控診斷子系統(tǒng)等構(gòu)成。S軟件系統(tǒng) 由操作系統(tǒng)、編譯系統(tǒng)、資源管理系統(tǒng)和并行程序開發(fā)環(huán)境等四部分組成。①操作系統(tǒng)操作系統(tǒng)采用64位Linux；面向高性能并行環(huán)境、支持能耗管理、虛擬化和安全隔離等進(jìn)行了針對(duì)性設(shè)計(jì)。②編譯系統(tǒng)支持C、C++、Fortran77/90/95、JAVA語(yǔ)言支持OpenMP、MPI并行編程；提供異構(gòu)協(xié)同編程框架，高效發(fā)揮CPU和GPU的協(xié)同計(jì)算能力；③資源管理提供全系統(tǒng)資源統(tǒng)一視圖，實(shí)現(xiàn)多策略資源分配與作業(yè)調(diào)度，有效提高資源利用率和系統(tǒng)吞吐率；④并行程序開發(fā)環(huán)境并行程序開發(fā)環(huán)境提供一體化圖形用戶界面，支持應(yīng)用程序的調(diào)試和性能分析。②操作系統(tǒng)符合B2級(jí)安全標(biāo)準(zhǔn)，提供基于隔離的用戶安全工作環(huán)境，提供統(tǒng)一的全系統(tǒng)資源管理視圖、友好的系統(tǒng)管理使用界面、一體化的并行應(yīng)用集成開發(fā)環(huán)境和虛擬化的網(wǎng)絡(luò)計(jì)算環(huán)境。T技術(shù)特點(diǎn)

①“天河一號(hào)”的峰值性能可以達(dá)到1.206PFlops，LINPACK測(cè)試性能563.1TFlops，超過(guò)2009年6月TOP500第四位；系統(tǒng)能效為431.7MFlops/W，超過(guò)2009年6月

Green500第五位。AT應(yīng)用領(lǐng)域

“天河一號(hào)”可廣泛應(yīng)用于：石油勘探數(shù)據(jù)處理、生物醫(yī)藥研究、航空航天裝備研制、資源勘測(cè)和衛(wèi)星遙感數(shù)據(jù)處理、金融工程數(shù)據(jù)分析、氣象預(yù)報(bào)和氣候預(yù)測(cè)、海洋環(huán)境數(shù)值模擬、短臨地震預(yù)報(bào)、新材料開發(fā)和設(shè)計(jì)、土木工程設(shè)計(jì)、基礎(chǔ)科學(xué)理論計(jì)算等?！疤旌右惶?hào)”的具體硬件配置配置硬件25120個(gè)通用處理器5120個(gè)加速處理器1024個(gè)通用處理器采用兩級(jí)InfinibandQDR互連全局分布共享并行I/O系統(tǒng)結(jié)構(gòu)分布式集中管理結(jié)構(gòu)天河一號(hào)硬件配置配置硬件2配置軟件2“天河一號(hào)”超級(jí)計(jì)算機(jī)技術(shù)關(guān)鍵技術(shù)3技術(shù)關(guān)鍵技術(shù)1/7:多陣列可配置協(xié)同并行體系結(jié)構(gòu)31/7:多陣列可配置協(xié)同并行體系結(jié)構(gòu)融合了計(jì)算陣列、加速陣列和服務(wù)陣列，結(jié)合資源管理的異構(gòu)協(xié)同技術(shù)和編譯的混合編程支撐技術(shù)，實(shí)現(xiàn)資源的動(dòng)態(tài)配置和異構(gòu)計(jì)算能力的協(xié)同工作。滿足各類應(yīng)用對(duì)計(jì)算資源的不同需求。在超大規(guī)模高性能計(jì)算機(jī)體系結(jié)構(gòu)方面有所突破。天河一號(hào)具有數(shù)據(jù)級(jí)并行處理能力和指令級(jí)并行處理能力等在內(nèi)的多種計(jì)算能力，可針對(duì)不同應(yīng)用的計(jì)算需求，通過(guò)計(jì)算能力的動(dòng)態(tài)組合，實(shí)現(xiàn)高效能計(jì)算。系統(tǒng)峰值性能1.206萬(wàn)億次，LINKPACK測(cè)試性能560.3萬(wàn)億次。①高可靠異構(gòu)計(jì)算結(jié)點(diǎn)平衡設(shè)計(jì)技術(shù)；②高層任務(wù)抽象和管理技術(shù)；③多陣列可配置高速互聯(lián)技術(shù)；④動(dòng)態(tài)任務(wù)分布和調(diào)度技術(shù)；⑤全局共享并行I/O技術(shù)；⑥動(dòng)態(tài)計(jì)算域構(gòu)建技術(shù)；⑦異構(gòu)協(xié)同的資源管理技術(shù)。技術(shù)關(guān)鍵技術(shù)2/7:高速率可擴(kuò)展互聯(lián)通信技術(shù)32/7：高速率擴(kuò)展互聯(lián)通信技術(shù)互聯(lián)通信網(wǎng)絡(luò)基于高速率InfinibandQDR技術(shù)，采用可擴(kuò)展的互聯(lián)網(wǎng)絡(luò)結(jié)構(gòu)和單線速率10Gps,鏈路帶寬40Gbps高帶寬互聯(lián)。突破了高速率與高密度互聯(lián)網(wǎng)絡(luò)的關(guān)鍵技術(shù)，提高了系統(tǒng)效率，簡(jiǎn)化系統(tǒng)維護(hù)。統(tǒng)一實(shí)現(xiàn)了計(jì)算處理、I/O存儲(chǔ)、系統(tǒng)管理等不同類型任務(wù)的同步與通信，系統(tǒng)管理與維護(hù)簡(jiǎn)潔，取得了40Gbps通信帶寬，1.2us延遲的高效通信性能。②用戶級(jí)低延遲通信協(xié)議；③鏈路自檢測(cè)和自管理；④單線速率10Gbps的互聯(lián)；⑤高吞吐高密度背板互聯(lián)結(jié)構(gòu)⑥光電混合傳輸。①高帶寬可擴(kuò)展互聯(lián)網(wǎng)絡(luò)技術(shù)；高效發(fā)揮CPU與GPU的協(xié)同計(jì)算能力，把GPU的計(jì)算效率從優(yōu)化前的20%提高到70%。技術(shù)關(guān)鍵技術(shù)3/7:高效異構(gòu)協(xié)同計(jì)算技術(shù)33/7:高效異構(gòu)協(xié)同計(jì)算技術(shù)使用CPU+GPU的體系結(jié)構(gòu)，GPU扮演加速器的作用，它加快了計(jì)算機(jī)的運(yùn)行速度，卻降低了功耗和成本。針對(duì)多陣列可配置協(xié)同并行體系結(jié)構(gòu)中的異構(gòu)混合計(jì)算資源，采用混合語(yǔ)言編程技術(shù)，突破了傳統(tǒng)混合計(jì)算模式效率低的問(wèn)題，為提高系統(tǒng)的整體性能起到關(guān)鍵作用。①自使用動(dòng)態(tài)任務(wù)劃分，自動(dòng)平衡CPU和GPU的工作負(fù)載；②流式數(shù)據(jù)存儲(chǔ)，減少GPU數(shù)據(jù)傳輸對(duì)CPU計(jì)算的干擾；③軟件流水，重疊GPU計(jì)算與主存和GPU之間的數(shù)據(jù)傳輸；④親和調(diào)度，優(yōu)化計(jì)算結(jié)點(diǎn)間的進(jìn)程調(diào)度和計(jì)算結(jié)點(diǎn)內(nèi)的線程調(diào)度，減少數(shù)據(jù)、指令遷移和通信開銷；⑤多層緩沖區(qū)雙向異步數(shù)據(jù)傳輸，通過(guò)PCI-E數(shù)據(jù)緩沖區(qū)優(yōu)化CPU與GPU之間的數(shù)據(jù)傳輸，減少帶寬壓力；⑥高級(jí)循環(huán)優(yōu)化，通過(guò)編譯器自動(dòng)進(jìn)行數(shù)據(jù)交換、循環(huán)變換和循環(huán)分塊，增大⑦OpenMP與MPI混合并行支持，針對(duì)并行粒度的不同分別進(jìn)行優(yōu)化。Cache重用，改善多線程運(yùn)行時(shí)的帶寬受限問(wèn)題；技術(shù)關(guān)鍵技術(shù)4/7:基于隔離的安全控制技術(shù)34/7:基于隔離的安全控制技術(shù)面向虛擬域的作用管理服務(wù)結(jié)點(diǎn)虛擬計(jì)算域計(jì)算結(jié)點(diǎn)高性能計(jì)算域安全控制系統(tǒng)的結(jié)構(gòu)圖資源管理分配模塊環(huán)境監(jiān)測(cè)設(shè)置模塊虛擬計(jì)算域管理工具包面向虛擬域的服務(wù)質(zhì)量保證模塊虛擬計(jì)算域構(gòu)建模塊防止客體重用模塊面向任務(wù)的服務(wù)質(zhì)量保證模塊高性能計(jì)算域構(gòu)建模塊針對(duì)超級(jí)計(jì)算中心的高信息安全需求，系統(tǒng)創(chuàng)新地采用了基于隔離的安全控制技術(shù)，在不增加系統(tǒng)開銷的前提下，有效提高了用戶運(yùn)行信息和數(shù)據(jù)的安全性。充分發(fā)揮了系統(tǒng)的各項(xiàng)性能，在保證系統(tǒng)數(shù)據(jù)、用戶數(shù)據(jù)安全的前提下，最大限度地提升了系統(tǒng)的服務(wù)能力，為每個(gè)用戶提供了安全、高效、靈活、符合用戶習(xí)慣的計(jì)算環(huán)境。①低開銷的用戶容器技術(shù)；②高效的虛擬文件系統(tǒng)隔離技術(shù)；③定制的用戶運(yùn)行環(huán)境技術(shù)；④靈活安全的文件穿透訪問(wèn)技術(shù)；⑤細(xì)粒度的高效資源和服務(wù)質(zhì)量保證技術(shù)；⑥相互隔離的用戶獨(dú)立工作環(huán)境構(gòu)建技術(shù)；⑦高效、簡(jiǎn)便的用戶定制環(huán)境管理技術(shù)；⑧快速模板構(gòu)建技術(shù)。技術(shù)關(guān)鍵技術(shù)5/7:虛擬化的網(wǎng)絡(luò)計(jì)算支撐技術(shù)35/7:虛擬化的網(wǎng)絡(luò)計(jì)算支撐技術(shù)針對(duì)網(wǎng)絡(luò)化計(jì)算需求，通過(guò)高性能虛擬域技術(shù)，支持根據(jù)用戶需求動(dòng)態(tài)構(gòu)造虛擬化的用戶運(yùn)行環(huán)境，并結(jié)合遠(yuǎn)程虛擬終端技術(shù)，屏蔽系統(tǒng)細(xì)節(jié)，高效支撐網(wǎng)絡(luò)化使用和云計(jì)算。虛擬化網(wǎng)絡(luò)計(jì)算支撐技術(shù)有效屏蔽了系統(tǒng)細(xì)節(jié)，簡(jiǎn)化了用戶使用，提高應(yīng)用開發(fā)效率，提供了有別于傳統(tǒng)高性能計(jì)算機(jī)的使用方式，可以進(jìn)一步擴(kuò)展并滿足未來(lái)云計(jì)算的需求。①面向?qū)ο蟮慕M件化系統(tǒng)結(jié)構(gòu)；②動(dòng)態(tài)服務(wù)發(fā)現(xiàn)技術(shù)；③友好的人機(jī)界面設(shè)計(jì)技術(shù)；④一體化圖形集成開發(fā)框架；⑤高效能、低開銷的虛擬域技術(shù)；⑥用戶環(huán)境的動(dòng)態(tài)構(gòu)建遷移技術(shù)；⑦系統(tǒng)資源遠(yuǎn)程探測(cè)技術(shù)。技術(shù)關(guān)鍵技術(shù)6/7:多層次的大規(guī)模系統(tǒng)容錯(cuò)技術(shù)36/7:多層次的大規(guī)模系統(tǒng)容錯(cuò)技術(shù)多層次容錯(cuò)框架自動(dòng)作業(yè)容錯(cuò)流程作業(yè)進(jìn)程檢查點(diǎn)庫(kù)并行存儲(chǔ)系統(tǒng)容錯(cuò)并行算法與斷點(diǎn)續(xù)傳應(yīng)用程序檢查點(diǎn)管理與與作業(yè)自動(dòng)恢復(fù)資源管理并行任務(wù)協(xié)同通道重建MPI運(yùn)行庫(kù)用戶透明的進(jìn)程檢查點(diǎn)技術(shù)OS內(nèi)核用戶界面統(tǒng)籌作業(yè)管理檢查點(diǎn)插件故障檢測(cè)模塊資源管理系統(tǒng)采用多層容錯(cuò)技術(shù)，通過(guò)操作系統(tǒng)級(jí)的檢查點(diǎn)功能、資源管理級(jí)的任務(wù)和作業(yè)的自動(dòng)容錯(cuò)技術(shù)，以及并行應(yīng)用級(jí)的容錯(cuò)并行算法和斷點(diǎn)續(xù)傳功能，有效提高了系統(tǒng)的可靠性。緩解了大規(guī)模系統(tǒng)固有可靠性低對(duì)用戶應(yīng)用運(yùn)行的影響，使用戶作業(yè)的運(yùn)行成功率得到很大提高，提升了系統(tǒng)可用性與吞吐率。①操作系統(tǒng)內(nèi)核實(shí)現(xiàn)用戶透明的進(jìn)程檢查點(diǎn)支持；②MPI運(yùn)行庫(kù)進(jìn)行并行任務(wù)檢查點(diǎn)的協(xié)同與通信通道重建；③資源管理提供作業(yè)檢查點(diǎn)的管理與自動(dòng)故障恢復(fù)；④應(yīng)用容錯(cuò)并行算法和斷點(diǎn)續(xù)傳；⑤資源管理控制進(jìn)程的雙機(jī)備份技術(shù)；⑥并行存儲(chǔ)的Failover技術(shù)；技術(shù)關(guān)鍵技術(shù)7/7:系統(tǒng)能耗綜合控制技術(shù)37/7:系統(tǒng)能耗綜合控制技術(shù)操作系統(tǒng)、資源管理系統(tǒng)和編譯系統(tǒng)相結(jié)合，通過(guò)系統(tǒng)動(dòng)態(tài)重構(gòu)技術(shù)，結(jié)點(diǎn)ACP能耗狀態(tài)動(dòng)態(tài)管理技術(shù)和動(dòng)態(tài)調(diào)頻技術(shù)，根據(jù)用戶資源需求和系統(tǒng)工作狀態(tài)，動(dòng)態(tài)調(diào)整系統(tǒng)資源配置，調(diào)節(jié)結(jié)點(diǎn)功耗狀態(tài)和CPU、GPU、內(nèi)存的工作頻率，實(shí)現(xiàn)最佳的系統(tǒng)能效，并有效提高系統(tǒng)的可靠性。通過(guò)一體化的能耗控制技術(shù)，使系統(tǒng)的空閑結(jié)點(diǎn)能耗降低比例大于80%；并行計(jì)算系統(tǒng)綜合能耗降低比例大于20%；能耗管理系統(tǒng)對(duì)應(yīng)用運(yùn)行時(shí)間影響低于5%。

①應(yīng)用能耗特征識(shí)別；②基于PMU事件和QoS的能耗狀態(tài)監(jiān)控；③能耗感知的資源分配；④能耗感知的作業(yè)調(diào)度；⑤能耗感知的分布式設(shè)備狀態(tài)管理；⑥面向能效優(yōu)化的編譯。用數(shù)值方法預(yù)報(bào)臺(tái)風(fēng)應(yīng)用典型應(yīng)用1/N:用數(shù)值方法預(yù)報(bào)臺(tái)風(fēng)4通過(guò)天河一號(hào)輔助設(shè)計(jì)飛機(jī)氣動(dòng)外形應(yīng)用典型應(yīng)用2/N:輔助設(shè)計(jì)飛機(jī)氣動(dòng)外形4美洲豹（2009年的世界第一名美國(guó)“美洲豹”

）

同比超級(jí)計(jì)算機(jī)排名1/5:美洲豹5“走鵑”（2008年排名世界第一的美國(guó)“走鵑”超級(jí)計(jì)算機(jī)）同比超級(jí)計(jì)算機(jī)排名2/5走鵲5“走鵑”（2008年排名世界第一的美國(guó)“走鵑”超級(jí)計(jì)算機(jī)）“海妖”超級(jí)計(jì)算機(jī)同比超級(jí)計(jì)算機(jī)排名3/5海妖5“尤金”同比超級(jí)計(jì)算機(jī)排名4/5尤金52004年-2007年，美國(guó)“藍(lán)色基因”曾多年雄踞世界第一位，速度為500萬(wàn)億次，但耗電量高達(dá)6兆瓦“天河一號(hào)”同比超級(jí)計(jì)算機(jī)排名5/5天河一號(hào)5國(guó)家超級(jí)計(jì)算天津中心大樓落戶國(guó)家超級(jí)計(jì)算天津中心天津?yàn)I海新區(qū)5爭(zhēng)鋒“超越只是一瞬間”不進(jìn)則退92011年6月20日，國(guó)際TOP500組織對(duì)外公布了世界超級(jí)計(jì)算機(jī)最新排行榜：日本“京”超級(jí)計(jì)算機(jī)超越了我國(guó)“天河一號(hào)”，排名世界第一。日本理化學(xué)研究所20日宣布，與富士通共同研發(fā)中的超級(jí)計(jì)算機(jī)“京”以每秒8612萬(wàn)億次的運(yùn)算速度在最新全球超級(jí)計(jì)算機(jī)500強(qiáng)排名中位列第一。爭(zhēng)鋒“超越只是一瞬間”不進(jìn)則退9今年，日本超級(jí)計(jì)算機(jī)“京”奪走Top500榜首之位，中國(guó)的“天河一號(hào)”僅保持半年的優(yōu)勢(shì)爭(zhēng)鋒“超越只是一瞬間”不進(jìn)則退9日本超級(jí)計(jì)算機(jī)“京”單機(jī)柜圖（2004年-2007年，美國(guó)“藍(lán)色基因”曾多年雄踞世界第一位，速度為500萬(wàn)億次，但耗電量高達(dá)6兆瓦）美國(guó)“藍(lán)色基因”單機(jī)柜圖中國(guó)超級(jí)計(jì)算機(jī)發(fā)展年譜節(jié)點(diǎn)機(jī)采用了曙光自主研發(fā)的TC3600刀片服務(wù)器，應(yīng)用了大規(guī)模系統(tǒng)管理和調(diào)度系統(tǒng)、高性能計(jì)算機(jī)安全系統(tǒng)等自主技術(shù)，具有“四高二低”技術(shù)亮點(diǎn)，即高性能、高效能、高可靠、高密度、低功耗、低成本。簡(jiǎn)單來(lái)說(shuō)，星云”的優(yōu)勢(shì)在于采用了我國(guó)自主研發(fā)的模塊化服務(wù)器，能夠按計(jì)算需求自行選擇主要計(jì)算組件，同時(shí)它在每個(gè)節(jié)點(diǎn)容納了10塊GPU計(jì)算卡，因而在較重要的節(jié)點(diǎn)通過(guò)互相比對(duì)的計(jì)算模式，保證了數(shù)據(jù)的可靠性。驕傲“星云”超級(jí)計(jì)算機(jī)世界No.32010年6月1日，曙光公司在京宣布：我國(guó)首臺(tái)達(dá)到每秒3000萬(wàn)億次峰值運(yùn)算速度的超級(jí)計(jì)算機(jī)“星云”，近日由中科院計(jì)算所、曙光公司、國(guó)家超算深圳中心共同研制成功。其實(shí)測(cè)性能超過(guò)每秒1271萬(wàn)億次，在5月31日德國(guó)發(fā)布的第35屆全球超級(jí)計(jì)算機(jī)前500強(qiáng)(TOP500)排行榜上居第二位（現(xiàn)在位居第三）

，創(chuàng)造了中國(guó)高性能計(jì)算的最高性能。國(guó)家超級(jí)計(jì)算天津中心招聘啟事科研人員在對(duì)“天河一號(hào)”超級(jí)計(jì)算機(jī)進(jìn)行系統(tǒng)性能測(cè)試國(guó)家超級(jí)計(jì)算天津中心大樓國(guó)家超級(jí)計(jì)算天津中心（NSCC-TJ）是由國(guó)家科技部、天津市和國(guó)防科學(xué)技術(shù)大學(xué)三方共同建設(shè)的國(guó)家級(jí)超級(jí)計(jì)算中心。中心采用我國(guó)首臺(tái)千萬(wàn)億次計(jì)算機(jī)“天河一號(hào)”作為業(yè)務(wù)主計(jì)算機(jī)，是我國(guó)第一個(gè)具有千萬(wàn)億次計(jì)算能力的超級(jí)計(jì)算中心，也是世界上少數(shù)幾個(gè)具有千萬(wàn)億次計(jì)算機(jī)的超級(jí)計(jì)算機(jī)。中心立足天津，面向全國(guó)，以應(yīng)用需求為牽引，按照“高科技公共服務(wù)、信息產(chǎn)業(yè)發(fā)展、信息專業(yè)人才聚集培養(yǎng)”三位一體的思路開展建設(shè)和進(jìn)行運(yùn)營(yíng)，為提高國(guó)家科技創(chuàng)新能力和促進(jìn)產(chǎn)業(yè)技術(shù)創(chuàng)新提供高性能計(jì)算服務(wù)。因中心工作需要，在全國(guó)范圍內(nèi)招聘如下職位：并行程序設(shè)計(jì)與開發(fā)工程師1、計(jì)算機(jī)及相關(guān)專業(yè)碩士，熟悉并行算法設(shè)計(jì)，精通MPI、OpenMP、CUDA等編程；2、熟悉linux/windows系統(tǒng)下的C/C++、Fortran編程，熟悉gnu、intel等編譯器；3、2年以上軟件開發(fā)經(jīng)歷或分布計(jì)算、并行計(jì)算相關(guān)經(jīng)歷優(yōu)先；4、熟悉GPU、FPGA、DSP等優(yōu)先；5、英語(yǔ)良好，有較強(qiáng)的溝通能力和團(tuán)隊(duì)合作精神。爭(zhēng)鋒中國(guó)全國(guó)產(chǎn)化的超級(jí)計(jì)算機(jī)“神威藍(lán)光”問(wèn)世《2011年中國(guó)高性能計(jì)算機(jī)TOP100排行榜》中，排名第二的神威藍(lán)光(SunwayBlueLightMPP)2011年10月27日消息，2011年全國(guó)高性能計(jì)算學(xué)術(shù)年會(huì)(HPCChina2011)于10月26至29日在山東濟(jì)南山東大廈召開申威1600微處理器“神威藍(lán)光”超級(jí)計(jì)算機(jī)爭(zhēng)鋒中國(guó)全國(guó)產(chǎn)化的超級(jí)計(jì)算機(jī)“神威藍(lán)光”問(wèn)世“神威藍(lán)光”超級(jí)計(jì)算機(jī)（爭(zhēng)鋒中國(guó)全國(guó)產(chǎn)化的超級(jí)計(jì)算機(jī)“神威藍(lán)光”問(wèn)世“神威藍(lán)光”超級(jí)計(jì)算機(jī)申威1600微處理器及電路板等爭(zhēng)鋒中國(guó)全國(guó)產(chǎn)化的超級(jí)計(jì)算機(jī)“神威藍(lán)光”問(wèn)世全部采用自主設(shè)計(jì)生產(chǎn)的CPU(ShenWeiprocessorSW1600)，系統(tǒng)共8704個(gè)CPU

峰值1.07016PFlops，持續(xù)性能795.9TFlops

Linpack效率74.37%，總功耗1074KW

由山東省科學(xué)院計(jì)算中心負(fù)責(zé)建設(shè)、管理和運(yùn)營(yíng)《2011年中國(guó)高性能計(jì)算機(jī)TOP100排行榜》中，排名第二的神威藍(lán)光(SunwayBlueLightMPP)該機(jī)器獲得科技部863計(jì)劃支持，由國(guó)家并行計(jì)算機(jī)工程技術(shù)研究中心制造，于2011年9月安裝于國(guó)家超算濟(jì)南中心

《并行處理與體系結(jié)構(gòu)》并行主要研究先行方式、流水方式、向量化并發(fā)性、同時(shí)性數(shù)據(jù)并行性、劃分交叉、重疊、多重性、重復(fù)時(shí)間共享、空間共享多任務(wù)處理、多道程序、多線程方式和分布式計(jì)算本章內(nèi)容學(xué)習(xí)目標(biāo)1.1計(jì)算技術(shù)的現(xiàn)狀1.2多處理機(jī)和多計(jì)算機(jī)1.3多向量機(jī)和SIMD計(jì)算機(jī)第1章并行計(jì)算機(jī)模型掌握基本概念1.4并行計(jì)算機(jī)的抽象模型1.5可擴(kuò)展的范圍和設(shè)計(jì)

1計(jì)算技術(shù)的現(xiàn)狀一、并行技術(shù)的出現(xiàn)二、現(xiàn)代并行計(jì)算機(jī)的組成涉及6個(gè)問(wèn)題：1.計(jì)算問(wèn)題現(xiàn)實(shí)生活中對(duì)問(wèn)題要求快速而精確地求解推動(dòng)了計(jì)算機(jī)的廣泛使用。科學(xué)技術(shù)中的數(shù)值計(jì)算問(wèn)題人工智能(AI)問(wèn)題事務(wù)處理2.算法和數(shù)據(jù)結(jié)構(gòu)并行計(jì)算問(wèn)題中的運(yùn)算和通信，需要各種專門的算法和數(shù)據(jù)結(jié)構(gòu)。符號(hào)處理科學(xué)計(jì)算存在的問(wèn)題3.硬件資源處理機(jī)、存儲(chǔ)器和外圍設(shè)備組成了計(jì)算機(jī)系統(tǒng)的硬件核心外圍設(shè)備可以直接或通過(guò)局域網(wǎng)和廣域網(wǎng)與主機(jī)相連Transaction4.操作系統(tǒng)管理用戶程序執(zhí)行過(guò)程中的資源分配和再分配映射是一種算法結(jié)構(gòu)與硬件結(jié)構(gòu)相匹配的雙向過(guò)程。并行操作系統(tǒng)的映射算法和數(shù)據(jù)結(jié)構(gòu)到機(jī)器結(jié)構(gòu)的映射包括處理機(jī)調(diào)度、存儲(chǔ)器映象、處理器間的通信等。這些問(wèn)題通常都與系統(tǒng)結(jié)構(gòu)有關(guān)。5.系統(tǒng)軟件支持存在的問(wèn)題：不能以通用和可移植方式進(jìn)行并行程序設(shè)計(jì)開發(fā)并行編程環(huán)境：一種與系統(tǒng)結(jié)構(gòu)無(wú)關(guān)的語(yǔ)言、編譯器和軟件工具。兩個(gè)方向：對(duì)于開發(fā)并行語(yǔ)言:將著眼點(diǎn)放在語(yǔ)言執(zhí)行的效率、對(duì)不同機(jī)器的可移植性、與現(xiàn)有的順序語(yǔ)言的兼容性、并行性的表達(dá)和編程的簡(jiǎn)便性等上面。可以設(shè)計(jì)一種新的語(yǔ)言，逐步擴(kuò)展現(xiàn)有的順序語(yǔ)言。新語(yǔ)言有用顯式高級(jí)結(jié)構(gòu)描述并行性的優(yōu)點(diǎn)，但是新語(yǔ)言往往與現(xiàn)有語(yǔ)言不兼容，而需要新的編譯器或者通過(guò)新的步驟才能利用現(xiàn)有的編譯器。大部分系統(tǒng)選用的是語(yǔ)言擴(kuò)展方式。6.編譯器支持改進(jìn)編譯器有三種途徑：預(yù)處理程序預(yù)編譯器并行化編譯器預(yù)處理程序采用順序編譯器和目標(biāo)計(jì)算機(jī)的低層程序庫(kù)實(shí)現(xiàn)高級(jí)并行結(jié)構(gòu)。預(yù)編譯器需要程序流分析、相關(guān)性檢查和有限的優(yōu)化來(lái)檢測(cè)并行性。聯(lián)接過(guò)程的效果取決于預(yù)處理程序、預(yù)編譯器、并行化編譯器、加載程序和操作系統(tǒng)支持的功效。由于程序行為的不可預(yù)測(cè)，現(xiàn)有的編譯器在檢測(cè)所有類型的并行性時(shí)都不是完全自動(dòng)或完全智能進(jìn)行的。存在一些有效的方法：7.并行程序的設(shè)計(jì)環(huán)境隱式并行性顯式并行性伊利諾依大學(xué)的DavidKuck和Rice大學(xué)的KenKennedy以及他們的合作者都已采用這種隱式并行性方法。加州理工學(xué)院的CharlesSeitz和麻省理工學(xué)院的WilliamDaily在開發(fā)多計(jì)算機(jī)時(shí)采用了這種顯式方法弱強(qiáng)將編譯器命令插入源代碼，幫助編譯器做出較好的結(jié)果。這樣，用戶可與編譯器進(jìn)行交互重構(gòu)，這已被證明對(duì)提高并行計(jì)算機(jī)性能是十分有用的。總結(jié)要使一個(gè)環(huán)境對(duì)用戶更加友好，必須要有專用軟件工具一些工具是傳統(tǒng)高級(jí)語(yǔ)言的并行擴(kuò)展一些則是集成環(huán)境其中包括提供不同級(jí)別的程序抽象、驗(yàn)證、測(cè)試、查錯(cuò)和調(diào)試等各種工具；性能預(yù)測(cè)和監(jiān)控；輔助程序開發(fā)的可視化支持、性能測(cè)量以及計(jì)算結(jié)果的圖形顯示及動(dòng)畫表示三、計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)向高性能發(fā)展歷程主要探討順序到并行的過(guò)程SP集成傳統(tǒng)工作環(huán)境+性能監(jiān)控分析與預(yù)測(cè)+可視化技術(shù)超標(biāo)量技術(shù)微型機(jī)采用的技術(shù)1.先行、并行性和流水線技術(shù)用先行技術(shù)預(yù)取指令可使I／E(指令讀取／譯碼和執(zhí)行)支持功能并行性的方法有兩種①一種是同時(shí)使用多個(gè)功能部件②另一種是在不同處理級(jí)分別實(shí)施流水線技術(shù)流水線指令執(zhí)行、流水線算術(shù)計(jì)算和存儲(chǔ)器存取操作。2.Flynn分類法MkhealFlynn(1972)根據(jù)指令和數(shù)據(jù)流概念提出了不同計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)的分類法。1234多數(shù)據(jù)流(MD)一定是多個(gè)執(zhí)行部件多指令流(MI)一定是多個(gè)控制部件單指令流(SI)一定是單個(gè)控制部件C-->P-->M傳統(tǒng)的順序機(jī)被稱為SISD(單指令流單數(shù)據(jù)流)計(jì)算機(jī)。向量計(jì)算機(jī)--標(biāo)量和向量硬件裝備，或以SIMD(單指令流多數(shù)據(jù)流)機(jī)的形式出現(xiàn)。并行計(jì)算機(jī)則屬M(fèi)IMD(多指令流多數(shù)據(jù)流)機(jī)MISD(多指令流單數(shù)據(jù)流)機(jī)在執(zhí)行不同的指令流時(shí)，同一數(shù)據(jù)流通過(guò)處理機(jī)線性陣列。這種系統(tǒng)結(jié)構(gòu)也就是所謂流水線執(zhí)行特定算法的脈動(dòng)陣列(Systolicarrays)。由卡內(nèi)基—梅隆大學(xué)的美籍華人學(xué)者H．T．Kung于1978年提出的。這一結(jié)構(gòu)是隨著VLSI技術(shù)的發(fā)展和各種大運(yùn)算量的信號(hào)/圖象處理及科學(xué)計(jì)算的運(yùn)算要求而建立起來(lái)的MPMD：控制并行程序（待續(xù)）SPMD：數(shù)據(jù)并行程序（待續(xù)）共享存儲(chǔ)型多處理機(jī)（待續(xù)）消息傳遞型多計(jì)算機(jī)（待續(xù)）圖示含義這是一類為實(shí)現(xiàn)確定算法而設(shè)計(jì)的多維流水線陣列結(jié)構(gòu)；如上圖所示就是為完成矩陣--矩陣相乘而專門設(shè)計(jì)的搏動(dòng)式陣列。此例的內(nèi)部結(jié)點(diǎn)度為6。靜態(tài)搏動(dòng)式陣列可在多個(gè)方向上使數(shù)據(jù)流變成以流水線方式工作；商用IntelWarp系統(tǒng)(Anaratone等，1986)就是用搏動(dòng)式結(jié)構(gòu)設(shè)計(jì)而成的。自從1978年Kung和Leiserson提出搏動(dòng)式陣列后，它已成為廣泛研究的領(lǐng)域。多方向性處理單元簡(jiǎn)單;含義流水；算法專業(yè)。3.并行／向量計(jì)算機(jī)真正的并行計(jì)算機(jī)是那些以MIMD模式執(zhí)行程序的計(jì)算機(jī)。并行計(jì)算機(jī)有兩大類，即共享存儲(chǔ)型多處理機(jī)和消息傳遞型多計(jì)算機(jī)。多處理機(jī)和多計(jì)算機(jī)之間的主要差別就在于存儲(chǔ)器共享和處理機(jī)間通信機(jī)制的不同。多處理機(jī)系統(tǒng)中的處理機(jī)通過(guò)公用存儲(chǔ)器的共享變量實(shí)現(xiàn)互相通信。多計(jì)算機(jī)系統(tǒng)的每個(gè)計(jì)算機(jī)結(jié)點(diǎn)有一個(gè)與其它結(jié)點(diǎn)不共享的本地存儲(chǔ)器。處理機(jī)之間的通信通過(guò)結(jié)點(diǎn)間的消息傳遞來(lái)實(shí)現(xiàn)。顯式向量計(jì)算機(jī)指令是隨向量處理機(jī)的問(wèn)世而出現(xiàn)的一臺(tái)向量處理機(jī)可以裝備有用硬件或固件并發(fā)控制的多條向量流水線4.開發(fā)層次LionelNi的最新分類法(1990)，并行計(jì)算機(jī)的分層開發(fā)可表示于下圖2.性能因子設(shè)Ic為已知程序的指令條數(shù)。執(zhí)行程序所需的CPU時(shí)間(T，以秒/程序表示)可用三個(gè)主要因素的乘積來(lái)計(jì)算：四、性能的系統(tǒng)屬性1

.時(shí)鐘頻率和CPI主頻當(dāng)前數(shù)字計(jì)算機(jī)的CPU(或簡(jiǎn)稱處理機(jī))是由一個(gè)恒定周期(τ，以ns表示)的時(shí)鐘驅(qū)動(dòng)的。周期的倒數(shù)是時(shí)鐘頻率:(ｆ＝1/

τ）（以MHz表示）程序的規(guī)模是由其指令數(shù)(Ic)，也就是程序串要執(zhí)行的機(jī)器指令數(shù)來(lái)決定的。執(zhí)行不同的機(jī)器指令所需要的時(shí)鐘周期數(shù)也是不一樣的。一條指令的周期數(shù)(CPl)就成為衡量執(zhí)行每條指令所需時(shí)間的重要參數(shù)T＝Ic

×CPI×τ可將上式重寫成如下形式：T＝Ic

×(p+m×k)×τ

一種指令類型的CPI可分為完成指令所需的處理機(jī)周期數(shù)和存儲(chǔ)器周期數(shù)兩部分。完整的指令執(zhí)行過(guò)程可能包含一至四次存儲(chǔ)器訪問(wèn)(一次用于取指令，兩次用于取操作數(shù)，一次用于存儲(chǔ)結(jié)果)，這與指令的類型有關(guān)p為指令譯碼和執(zhí)行所需的處理機(jī)周期數(shù)m為所需的存儲(chǔ)器訪問(wèn)次數(shù)k為存儲(chǔ)周期與處理機(jī)周期之比Ic為指令條數(shù)因?yàn)榇鎯?chǔ)周期很大于處理機(jī)周期3.系統(tǒng)屬性計(jì)算機(jī)系統(tǒng)屬性可以由五元組表示：(Ic，p，m，k，τ)T＝Ic×(p+m×k)×τ五個(gè)量可以稱為性能因子與四種系統(tǒng)屬性有關(guān)：指令系統(tǒng)結(jié)構(gòu)、編譯技術(shù)、CPU實(shí)現(xiàn)和控制技術(shù)、高速緩存與存儲(chǔ)器層次結(jié)構(gòu)。X表示”有關(guān)”機(jī)器規(guī)模n—處理機(jī)個(gè)數(shù)時(shí)鐘速率f工作負(fù)載W--程序中的計(jì)算操作數(shù)順序執(zhí)行時(shí)間T1并行執(zhí)行時(shí)間Tn速度Pn=W/Tn加速比Sn=T1/Tn效率En=Sn/n

利用率Un=Pn/n(Ppeak)啟動(dòng)時(shí)間t0

漸進(jìn)帶寬r∞處理器的峰值速度推廣并行系統(tǒng)的性能屬性P11分母與分子上下同除以CPU時(shí)鐘周期：τCPI=——————CICC是執(zhí)行Ic條執(zhí)行所用總的處理機(jī)周期C=—————————TCPU時(shí)鐘周期：τT是總的執(zhí)行時(shí)間，以CPU時(shí)鐘周期為單位的4.Mips速率(其中C是總的周期數(shù))5.吞吐率系統(tǒng)在單位時(shí)間內(nèi)能執(zhí)行多少個(gè)程序，這稱為系統(tǒng)的吞吐率(單位為程序數(shù)／秒)Ws在多道程序系統(tǒng)中，系統(tǒng)吞吐率常低于CPU吞吐率Wp。Wp可用下式表示：CPI:每指令執(zhí)行所需周期數(shù)

f是“頻率”：1s鐘內(nèi)有多個(gè)處理機(jī)周期或：

Wp=(MIPS)×106／Ic

Wp的單位是程序數(shù)／秒。程序的指令條數(shù)(Ic)每秒鐘執(zhí)行的指令條數(shù)5.吞吐率CPU吞吐率是根據(jù)MIPS速率和程序的平均長(zhǎng)度(Ic)來(lái)衡量機(jī)器每秒鐘能執(zhí)行多少個(gè)程序的尺度。Ws<Wp用多道程序或分時(shí)操作在CPU上交叉執(zhí)行多個(gè)程序時(shí)，I／O、編譯器和操作系統(tǒng)產(chǎn)生的額外系統(tǒng)開銷所造成的。

2多處理機(jī)和多計(jì)算機(jī)一、共享存儲(chǔ)型多處理機(jī)1.UMA模型UMA--UniformMemoryAccess含義均勻存儲(chǔ)器訪問(wèn)/集中式存儲(chǔ)器訪問(wèn)結(jié)構(gòu)和特點(diǎn)緊耦合系統(tǒng)(tightlycoupledsystem)多處理機(jī)由于高度資源共享系統(tǒng)的互連采用總線、交叉開關(guān)、或多級(jí)網(wǎng)絡(luò)形式對(duì)稱(symmetric)多處理機(jī)當(dāng)所有處理機(jī)都能同樣訪問(wèn)所有外圍設(shè)備時(shí)。SMP在UMA結(jié)構(gòu)中，所有存儲(chǔ)單元與任何處理器之間都是等距的，所以所有的存儲(chǔ)器訪問(wèn)操作需要基本一致的時(shí)間。分類UMASMP:對(duì)稱(symmetric)多處理機(jī)PVP:并行向量處理器（parallelvectorprocessor）在此，可不叫做“本地共享存儲(chǔ)器”舉例Fortran程序可在單處理機(jī)上順序執(zhí)行，分析CPU的運(yùn)行時(shí)間，假設(shè)條件：所有數(shù)組A(I)，B(I)，C(I)都有N個(gè)元素；分析：求和Fortran程序L1:Do10I＝1，NL2:A(I)＝B(I)+C(I)L3:10ContinueL4:SUM＝0L5:Do20J＝1，NL6:SUM＝SUM+A(J)L7:20Continue假定取指令和加載數(shù)據(jù)的開銷可以忽略不計(jì)；所有數(shù)組已經(jīng)裝入主存儲(chǔ)器，并且短程序段已經(jīng)裝入高速緩沖存儲(chǔ)器。忽略總線爭(zhēng)用或存儲(chǔ)器存取沖突問(wèn)題。執(zhí)行代碼行L2，L4和L6，每行要用一個(gè)機(jī)器周期。執(zhí)行程序控制語(yǔ)句L1，L3，L5和L7所需的時(shí)間可以忽略。應(yīng)該是2N+1個(gè)周期（代碼L4也需要一個(gè)周期）CPU用________個(gè)周期2N+1串行程序并行化:在M—處理機(jī)系統(tǒng)上執(zhí)行程序?qū)⒀h(huán)操作劃分成M段，每段有L＝N／M個(gè)元素。假設(shè)經(jīng)過(guò)共享存儲(chǔ)器的處理機(jī)之間的每次通信操作需要：k個(gè)周期Doallk＝1，MDo10I＝L(k-1)+1，kL。

A(I)＝B(I)+C(I)10ContinueSUM(k)＝0Do20J＝1，LSUM(k)=SUM(k)+A(L(k-1)+J)20ContinueENDall結(jié)論Doall表示所有M段在M臺(tái)處理機(jī)上并行執(zhí)行分析循環(huán)1是L個(gè)周期；循環(huán)2是L個(gè)周期總時(shí)間：_____________________________需要通信h次數(shù);h=log2Ma0a1a2a3a4a5a6a7+++++++遞歸折迭操作2L+h(k+1)=2N/M+log2M(k+1)123122.NUMA模型全局NUMA模型特點(diǎn)共享存儲(chǔ)器物理上分布在各個(gè)處理機(jī)的本地存儲(chǔ)器上，全部本地存儲(chǔ)器組成了全局地址空間,可被所有處理機(jī)訪問(wèn)。處理機(jī)訪問(wèn)共享存儲(chǔ)器的時(shí)間非均勻性共享存儲(chǔ)器(SM)不一定就是UMA,也可以是NUMA，無(wú)必然聯(lián)系!高度注意概念3.COMA模型只使用高速緩存的多處理機(jī)（cache-onlymemoryarchitecture）

只有高速緩存的多處理機(jī)全局瑞典計(jì)算機(jī)科學(xué)研究所的數(shù)據(jù)擴(kuò)散機(jī)(DDM，Hagersten等，1990)KendallSquareReserch公司的KSR—1機(jī)器(Burkhart等，1992)。實(shí)現(xiàn)的機(jī)器特點(diǎn)COMA模型是NUMA機(jī)的一種特例，將NUMA中分布主存儲(chǔ)器換成了高速緩存；全部高速緩沖存儲(chǔ)器組成了全局地址空間；遠(yuǎn)程高速緩存訪問(wèn)則借助于分布高速緩存目錄進(jìn)行，分級(jí)目錄往往可用來(lái)尋找高速緩存塊的副本，這與所用的互連網(wǎng)絡(luò)有關(guān)；數(shù)據(jù)的初始位置并不重要，因?yàn)樗罱K將會(huì)遷移到要用到它的地方。例如，高速緩存一致性非均勻存儲(chǔ)存取(CC—NUMA)模型。可以用分布共享存儲(chǔ)器和高速緩存目錄來(lái)描述。CC—NUMA模型的實(shí)例模型的演變斯坦福大學(xué)的Dash系統(tǒng)(Lenosh等，1990)和麻省理工學(xué)院的Alewife系統(tǒng)(Agarwal等，1990)4.典型的多處理機(jī)二、分布存儲(chǔ)型多計(jì)算機(jī)系統(tǒng)概念由多個(gè)計(jì)算機(jī)結(jié)點(diǎn)，通過(guò)消息傳遞網(wǎng)絡(luò)互相連接而成，每個(gè)結(jié)點(diǎn)是一臺(tái)由處理機(jī)、本地存儲(chǔ)器和有時(shí)接有磁盤或I／0外圍設(shè)備組成的自治的計(jì)算機(jī)。消息傳遞網(wǎng)絡(luò)提供結(jié)點(diǎn)之間的點(diǎn)到點(diǎn)靜態(tài)連接傳統(tǒng)的多計(jì)算機(jī)已被稱為近地存儲(chǔ)訪問(wèn)機(jī)(NORMA)私用存儲(chǔ)器逐漸在分布共享存儲(chǔ)器的多計(jì)算機(jī)中將被逐步取消。特點(diǎn)√√√本節(jié)共享存儲(chǔ)型多處理機(jī)系統(tǒng)分布存儲(chǔ)型多計(jì)算機(jī)系統(tǒng)軟件實(shí)現(xiàn)的DSM:為了在NORMA和NCC-NUMA上實(shí)現(xiàn)共享存儲(chǔ)器技術(shù)，研究人員提出了軟件一致性模型NUMA存儲(chǔ)器模型，也稱為分布式共享存儲(chǔ)器模型（DSM）UMANUMACOMANORMA第五章P156關(guān)聯(lián)與比較NORMA；近地存儲(chǔ)訪問(wèn)機(jī)，所有本地存儲(chǔ)器是私用的，而且只有本地處理機(jī)才能訪問(wèn)。所有本地存儲(chǔ)器是私用的，而且只有本地處理機(jī)才能訪問(wèn)；DSM:分布存儲(chǔ)器模型（distributedshared-memory）CC-NUMANCC-NUMA3.多計(jì)算機(jī)的換代現(xiàn)代多計(jì)算機(jī)用硬件尋徑器來(lái)傳送信息；計(jì)算機(jī)結(jié)點(diǎn)與尋徑器相連，邊界上的尋徑器與I／O和外圍設(shè)備連接；任何兩結(jié)點(diǎn)間的消息傳遞會(huì)涉及一連串的尋徑器和通道。在異構(gòu)多計(jì)算機(jī)系統(tǒng)中，可以有多種類型的結(jié)點(diǎn)，結(jié)點(diǎn)間的通信是通過(guò)可兼容的數(shù)據(jù)表示和消息傳遞協(xié)議來(lái)實(shí)現(xiàn)的。加州理工學(xué)院的Cosmic和InteliPSC／1是這一代研制的代表IntelParagon和ParsysSuperNodel000可作為代表性產(chǎn)品消息傳遞型多計(jì)算機(jī)的發(fā)展換代第一代(1983—1987)是基于處理機(jī)板技術(shù)，采用了超立方體結(jié)構(gòu)和軟件控制的消息交換方法。第二代(1988—1992)是用網(wǎng)格連接的系統(tǒng)結(jié)構(gòu)、硬件消息尋徑和中粒度分布計(jì)算的軟件環(huán)境實(shí)現(xiàn)的；現(xiàn)在面臨的第三代(1993—)預(yù)期是細(xì)粒度計(jì)算機(jī)麻省理工學(xué)院的J-Machine和加州工學(xué)院的Mosaic，VLSI片上實(shí)現(xiàn)處理機(jī)和通訊工具。示例IBMPOWER4體系結(jié)構(gòu)特點(diǎn)PowerPC64位體系結(jié)構(gòu)單芯片雙處理器，MCM八處理器集成多處理器互連接口集成I/O控制器集成L3Cache控制器集成存儲(chǔ)控制器IBMPOWER4(MCM結(jié)構(gòu))八處理器IBMPOWER4(32CPU)88884.典型多計(jì)算機(jī)多計(jì)算機(jī)的可編程性取決于:高效編譯器實(shí)用高效的分布式操作系統(tǒng)實(shí)用多計(jì)算機(jī)需要分布式操作系統(tǒng)!三.多處理機(jī)和多計(jì)算機(jī)之間的主要差別在于存儲(chǔ)器共享和處理機(jī)間通信機(jī)制的不同。多處理機(jī)系統(tǒng)中的處理機(jī)通過(guò)公用存儲(chǔ)器的共享變量實(shí)現(xiàn)互相通信。多計(jì)算機(jī)系統(tǒng)的每個(gè)計(jì)算機(jī)結(jié)點(diǎn)有一個(gè)與其它結(jié)點(diǎn)不共享的本地存儲(chǔ)器。處理機(jī)之間的通信通過(guò)結(jié)點(diǎn)間的消息傳遞來(lái)實(shí)現(xiàn)。多處理機(jī)系統(tǒng)多計(jì)算機(jī)系統(tǒng)共享變量消息傳遞

3多向量機(jī)和SIMD計(jì)算機(jī)一、向量超級(jí)計(jì)算機(jī)1.早期的超級(jí)計(jì)算機(jī)可分為：流水線向量機(jī)SIMD計(jì)算機(jī)強(qiáng)調(diào)開發(fā)大規(guī)模數(shù)據(jù)并行性用帶有少量帶有向量硬件，但性能很高的處理機(jī)來(lái)裝備.向量功能流水線向量數(shù)據(jù)流向量處理機(jī)：專門設(shè)計(jì)用來(lái)完成向量運(yùn)算的協(xié)處理機(jī)，是執(zhí)行向量操作的硬件資源，包括向量寄存器、流水線功能部件、處理部件和寄存器計(jì)數(shù)器。執(zhí)行過(guò)程：當(dāng)譯出的指令為向量操作；①它將被送至向量控制器，控制器將監(jiān)督主存儲(chǔ)器與向量功能流水線之間的向量數(shù)據(jù)流，向量數(shù)據(jù)流由控制器協(xié)調(diào)控制；②向量處理機(jī)則裝有若干條向量功能流水線。理解“向量運(yùn)算”流水線向量處理機(jī)有兩種類型：寄存器—寄存器結(jié)構(gòu)存儲(chǔ)器—存儲(chǔ)器結(jié)構(gòu)2.寄存器—寄存器的系統(tǒng)結(jié)構(gòu)如1976年推出的Cray1向量寄存器用來(lái)保存向量操作數(shù)、中間和最終的向量結(jié)果;向量功能流水線從向量寄存器檢索操作數(shù)，并將結(jié)果放入寄存器。說(shuō)明利用向量寄存器作為存儲(chǔ)器與功能流水線之間的接口重要特點(diǎn)

3.存儲(chǔ)器—存儲(chǔ)器結(jié)構(gòu)這種結(jié)構(gòu)比較早，與寄存器—寄存器結(jié)構(gòu)的區(qū)別就在于采用向量流水部件代替了向量寄存器。將向量操作流直接從存儲(chǔ)器取至流水線，然后再送回存儲(chǔ)器.重要特點(diǎn)

可見:雖然起始模塊不定,但向量依起始模塊連續(xù)存放二、SIMD超級(jí)計(jì)算機(jī)特點(diǎn)一個(gè)控制部件;多個(gè)功能部件1.SIMD的操作模型可用五元組表示M＝<N，C，I，M，R>N為機(jī)器的處理單元(PE)數(shù)例如：SIMD機(jī)器MasParMP—1是一種SIMD機(jī)器，其PE數(shù)N＝1024至16384。PE數(shù)目與機(jī)器配置有關(guān)。C為由控制部件(CU)直接執(zhí)行的指令集包括標(biāo)量和程序流控制指令例如：MasParMP—1CU執(zhí)行標(biāo)量指令，將譯碼后的向量指令播送到PE陣列，并控制PE間的通信。大1.SIMD的操作模型可用五元組表示M＝<N，C，I，M，R>I為由CU廣播至所有PE進(jìn)行并行執(zhí)行的指令集；它包括算術(shù)運(yùn)算、邏輯運(yùn)算、數(shù)據(jù)尋徑、屏蔽以及其它由每個(gè)活動(dòng)的PE對(duì)它的數(shù)據(jù)所執(zhí)行的局部操作。例如：MasParMP—1每個(gè)PE都是基于寄存器的加載／存儲(chǔ)RISC處理機(jī)，能執(zhí)行不同數(shù)據(jù)量的整數(shù)運(yùn)算和標(biāo)準(zhǔn)浮點(diǎn)運(yùn)算。各PE從CU接受指令。小1.SIMD的操作模型可用五元組表示M＝<N，C，I，M，R>M為屏蔽方案集其中每種屏蔽將PE集劃分為允許操作和禁止操作兩種子集。例如：MasParMP—1屏蔽方案設(shè)在每個(gè)PE中，并由CU連續(xù)監(jiān)控，它能在運(yùn)行時(shí)動(dòng)態(tài)地使每個(gè)PE處于置位或復(fù)位狀態(tài)。精髓:由CU進(jìn)行動(dòng)態(tài)”編程”!1.SIMD的操作模型可用五元組表示M＝<N，C，I，M，R>R是數(shù)據(jù)尋徑功能集說(shuō)明互連網(wǎng)絡(luò)中PE間通信所需要的各種設(shè)置模式。例如：MasParMP—1MP—1有一個(gè)X—Net網(wǎng)格網(wǎng)絡(luò)和一個(gè)全局多級(jí)交叉開關(guān)尋徑器，以實(shí)現(xiàn)CU—PE之間、X—Net的8個(gè)近鄰之間和全局尋徑器的通信。2.SIMD的實(shí)施模型（1）分布式存儲(chǔ)器模型(DSM)（同一）陣列控制部件1.N（PE個(gè)數(shù)）向量操作2.CU3.I(PE并行執(zhí)行的指令)程序和數(shù)據(jù)通過(guò)主機(jī)裝入控制存儲(chǔ)器控制部件通過(guò)執(zhí)行程序來(lái)控制數(shù)據(jù)尋徑網(wǎng)絡(luò)存儲(chǔ)器分布的SIMD特點(diǎn)SIMD計(jì)算機(jī)開發(fā)的是PE之間的空間并行性存儲(chǔ)器分布的SIMD計(jì)算機(jī)由同一陣列控制部件控制的PE陣列組成程序和數(shù)據(jù)通過(guò)主機(jī)裝入控制存儲(chǔ)器指令是送到控制部件進(jìn)行譯碼標(biāo)量操作或控制操作，則將直接由與控制部件相連的標(biāo)量處理機(jī)執(zhí)行向量操作，則將它廣播到所有PE并行地執(zhí)行劃分后的數(shù)據(jù)集合通過(guò)向量數(shù)據(jù)總線廣播到所有PE的本地存儲(chǔ)器PE通過(guò)數(shù)據(jù)尋徑網(wǎng)絡(luò)互連。數(shù)據(jù)尋徑網(wǎng)絡(luò)執(zhí)行PE間的通信，如移數(shù)、置換和其它尋徑操作?？刂撇考ㄟ^(guò)執(zhí)行程序來(lái)控制數(shù)據(jù)尋徑網(wǎng)絡(luò)。PE的同步由控制部件的硬件實(shí)現(xiàn)所有PE在同一個(gè)周期執(zhí)行同一條指令可以用屏蔽邏輯來(lái)決定任何一個(gè)PE在給定的指令周期執(zhí)行或不執(zhí)行指令√√√√√√√√12345678（2）

共享存儲(chǔ)器模型是一種PE使用共享存儲(chǔ)器的SIMD計(jì)算機(jī)。PE和存儲(chǔ)器之間的通信網(wǎng)絡(luò)是一個(gè)對(duì)準(zhǔn)網(wǎng)絡(luò)，它也受控制部件控制?？偩€型對(duì)等網(wǎng)絡(luò)示意圖星型對(duì)等網(wǎng)絡(luò)示意圖對(duì)等型網(wǎng)絡(luò)是指在網(wǎng)絡(luò)中不需要專門的服務(wù)器，網(wǎng)絡(luò)中的各工作站之間是平等的關(guān)系，每臺(tái)接入網(wǎng)絡(luò)的計(jì)算機(jī)既可以是服務(wù)器，也可以是工作站。在工作過(guò)程中，既共享其他計(jì)算機(jī)上的資源，又要為其他計(jì)算機(jī)提供共享資源。在其他計(jì)算機(jī)訪問(wèn)其共享資源時(shí)，可將其視為服務(wù)器，在其訪問(wèn)其他計(jì)算機(jī)時(shí)又可將其視為工作站。在對(duì)等型網(wǎng)絡(luò)中又有總線型對(duì)等網(wǎng)絡(luò)和星型對(duì)等型網(wǎng)絡(luò)之分。對(duì)等網(wǎng)絡(luò)（PeertoPeer，簡(jiǎn)稱P2P）也稱為對(duì)等連接，是一種新的通信模式，每個(gè)參與者具有同等的能力，可以發(fā)起一個(gè)通信會(huì)話。

4并行計(jì)算機(jī)的抽象模型并行計(jì)算機(jī)的理論模型是從物理模型抽象的；為開發(fā)并行算法提供了一種方便的框架；用這些模型可求得并行計(jì)算機(jī)的理論性能界限；可在芯片制作前估算芯片區(qū)的VLSI復(fù)雜性和執(zhí)行時(shí)間。一、時(shí)間與空間復(fù)雜性執(zhí)行時(shí)間存儲(chǔ)空間計(jì)算機(jī)求解一個(gè)規(guī)模為s的問(wèn)題的算法復(fù)雜性取決于：時(shí)間復(fù)雜性時(shí)間復(fù)雜性g(s)為O(f(s))，可讀作“數(shù)量級(jí)為f(s)”，如存在正的常量c和s0，則對(duì)所有s>s0的非負(fù)值就有g(shù)(s)≤cf(s)

?？臻g復(fù)雜性為問(wèn)題規(guī)模s的函數(shù)。漸近空間復(fù)雜性(asymptoticspacecom—plexity)主要與大問(wèn)題的數(shù)據(jù)存儲(chǔ)有關(guān)，而程序(代碼)存儲(chǔ)的需求和輸入數(shù)據(jù)的存儲(chǔ)不考慮在內(nèi)。串行算法的時(shí)間復(fù)雜性簡(jiǎn)稱為串行復(fù)雜性;并行算法的時(shí)間復(fù)雜性就稱為并行復(fù)雜性;并行復(fù)雜性應(yīng)比串行復(fù)雜性低，至少是相近。常識(shí)只考慮確定性算法P類(即多項(xiàng)式類)具有多項(xiàng)式復(fù)雜性算法的問(wèn)題集，如果存在一多項(xiàng)式p(s)，對(duì)任何問(wèn)題規(guī)模s的時(shí)間復(fù)雜性為O(p(s))，則某算法即具有多項(xiàng)式復(fù)雜性。NP類(即不確定性多項(xiàng)式類)不能以多項(xiàng)式實(shí)現(xiàn)，用不確定性算法求解的問(wèn)題集。P

NP確定性算法是不確定算法的特殊情況。P類問(wèn)題是計(jì)算易解的，而NP-P類問(wèn)題是難解的?，F(xiàn)在不知道是否P＝NP或P≠NP難解的NP類問(wèn)題又稱為具有指數(shù)時(shí)間復(fù)雜性的問(wèn)題?！獭獭獭汤}多項(xiàng)式復(fù)雜性和指數(shù)復(fù)雜性算法：將幾個(gè)數(shù)排序的多項(xiàng)式時(shí)間復(fù)雜性分別為_________，屬于P類對(duì)兩個(gè)n×n矩陣相乘算法的多項(xiàng)式時(shí)間復(fù)雜性分別為_________

，屬于P類。旅行推銷員問(wèn)題復(fù)雜性為_________指數(shù)復(fù)雜性問(wèn)題是屬_________的：到目前為止還未發(fā)現(xiàn)這類問(wèn)題的確定性多項(xiàng)式算法。背包問(wèn)題的復(fù)雜性為_________P、NP和NPC（NP完全問(wèn)題）可見，P是NP的一種O(nlogn)O(n3)O(n22n)O(2n/2)NP類二、并行隨機(jī)存取機(jī)模型(ParallelRandom—AccessMachine，PRAM)可用來(lái)開發(fā)并行算法和分析可擴(kuò)展性及復(fù)雜性。MIMD細(xì)粒度嚴(yán)格同步零開銷共享變量在PRAM上的一個(gè)并行程序由n個(gè)進(jìn)程組成，其中第i個(gè)進(jìn)程留駐在第i個(gè)處理器上，且由一串指令所組成。在每個(gè)基本時(shí)間步(稱為周期)，每個(gè)處理器執(zhí)行一條指令。這些指令包括數(shù)據(jù)傳送、算/邏、控制流以及I/O指令，在典型的順序計(jì)算機(jī)中均有這些指令。說(shuō)明1.同構(gòu)性規(guī)模為1的PRAM退化為傳統(tǒng)的RAM。這種機(jī)器為SISD。當(dāng)處理器多于1個(gè)時(shí)，一個(gè)PRAM將訪問(wèn)多個(gè)數(shù)據(jù)流，且通?？蓤?zhí)行多個(gè)指令流。因此PRAM是一個(gè)MIMD機(jī)器。并行計(jì)算機(jī)則屬M(fèi)IMD(多指令流多數(shù)據(jù)流)機(jī)說(shuō)明在那里程序執(zhí)行單一指令流且訪問(wèn)單一數(shù)據(jù)流。這種機(jī)器被稱為“單指令（流）、單數(shù)據(jù)（流）機(jī)（SISD）”，它能模型化普通的順序計(jì)算機(jī)。MIMD的特例:如果在每一周期，所有處理器必須執(zhí)行相同指令，即只有一個(gè)指令流時(shí)，則PRAM就成為單指令(流)、多數(shù)據(jù)(流)(SIMD)機(jī)器。(SPMD)計(jì)算：?jiǎn)纬绦蚨鄶?shù)據(jù)，所有進(jìn)程執(zhí)行同一程序，而由進(jìn)程指標(biāo)加以參數(shù)化。SIMD和SPMD間的差別是，在SPMD計(jì)算中，同一周期可以執(zhí)行不同指令。2.同步性進(jìn)程同步是嚴(yán)格的。PRAM是在指令級(jí)同步的。SIMD是指令級(jí)別同步的MIMD并行機(jī)則是異步的,每個(gè)進(jìn)程按照自己速率執(zhí)行，與其他進(jìn)程的執(zhí)行速度無(wú)關(guān)。3.交互機(jī)制這一屬性描述了并行進(jìn)程間如何相互影響行為的特性;在PRAM模型中，進(jìn)程間通過(guò)共享變量(或共享存儲(chǔ)器)進(jìn)行交互。4.地址空間PRAM模型所有進(jìn)程對(duì)所有存儲(chǔ)單元均有相等的訪問(wèn)時(shí)間--均勻存儲(chǔ)器訪問(wèn)(UMA)模型。針對(duì)多計(jì)算機(jī)不合適在多計(jì)算機(jī)中，每個(gè)處理機(jī)有它自己的分離地址空間。這些機(jī)器被稱為具有多地址空間。多計(jì)算機(jī)的處理機(jī)間通信不是通過(guò)共享變量，而是借助消息傳遞?！?.存儲(chǔ)器模型各種方案的主要區(qū)別在于如何協(xié)調(diào)RW的沖突。四種PRAM模型方案都與存儲(chǔ)器讀寫如何處理有關(guān)。(1)EREW-PRAM模型——這種模型禁止一臺(tái)以上處理機(jī)同時(shí)讀、寫同一存儲(chǔ)單元.

這是限制最大的PRAM模型。(2)CREW-PRAM模型——用互斥使寫沖突避免。可以并行讀同一存儲(chǔ)單元。(3)ERCW-PRAM模型——允許互斥讀或并行寫同一存儲(chǔ)單元。(4)CRCW-PRAM模型——允許在同一時(shí)刻并行讀或者并行寫。寫沖突可用下述四種策略之一分解：①共用——所有同時(shí)進(jìn)行的寫操作將相同數(shù)據(jù)存入熱點(diǎn)存儲(chǔ)單元②任選——將任何一個(gè)要寫的數(shù)保存起來(lái)，而其它的忽略不計(jì)③最小值——將處理機(jī)要寫的下標(biāo)值最小的數(shù)保存起來(lái)④優(yōu)先——對(duì)要寫的數(shù)用求和或求最大值等聯(lián)想函數(shù)加以組合嚴(yán)松6.原子操作原子操作的定義：一個(gè)原子操作是指有如下特性的一種操作。不可分有限更嚴(yán)格的原子操作定義：需要滿足以下的4個(gè)性質(zhì)。稱這樣的原子操作為一個(gè)事務(wù)操作。

原子性一致性隔離性持續(xù)性要么執(zhí)行事務(wù)操作的所有子操作，要么不執(zhí)行任何子操作一個(gè)事務(wù)操作總是將一個(gè)程序由一個(gè)一致性狀態(tài)轉(zhuǎn)換成另一個(gè)一致性狀態(tài)在一個(gè)事務(wù)操作完成之前，該事務(wù)操作的效果（結(jié)果）不會(huì)對(duì)其他事務(wù)操作產(chǎn)生影響一旦完成，當(dāng)系統(tǒng)失敗時(shí)，事務(wù)操作的效果仍會(huì)持續(xù)原一隔持例題PRAM步中的計(jì)算復(fù)雜性：假設(shè)有三個(gè)PRAM算法A，B和C，當(dāng)在一個(gè)有n個(gè)處理器的PRAM計(jì)算機(jī)上執(zhí)行時(shí)，各自的時(shí)間復(fù)雜性為:A--7nB--(nlogn)／4C--nloglogn根據(jù)大O標(biāo)志：算法A最快：(O(n))，C次之：O(nloglogn)，B為最慢：O(nlogn)。而實(shí)際上，假設(shè)當(dāng)機(jī)器的處理器數(shù)等于1024時(shí)：A=7X1024=7168B=1024X10/4=2558C=1024log210>3076結(jié)論：算法B最快，其次是C，而A則是最慢的。PRAM與物理模型的差異實(shí)際上，這種并行計(jì)算機(jī)是不存在的。共享存儲(chǔ)器SIMD機(jī)是與PRAM模型最接近的結(jié)構(gòu)。更確切地說(shuō)，以共享存儲(chǔ)的同步MIMD模式運(yùn)行。四種PRAM方案中，EREW和CRCW是應(yīng)用最普遍的模型每個(gè)CRCW算法可用一個(gè)EREW算法來(lái)模擬CRCW算法比一個(gè)等效的EREW要快，經(jīng)證明，最好的n—處理機(jī)EREW算法要比任一個(gè)n-處理機(jī)CRCW算法慢O(logn)倍對(duì)研究結(jié)構(gòu)規(guī)則的并行性來(lái)說(shuō)，用PRAM比用實(shí)際機(jī)器模型要好得多PRAM能指出實(shí)際并行計(jì)算機(jī)性能的上限研究PRAM模型目的三、異步PRAM模型—APRAM是一個(gè)異步的PRAM模型，簡(jiǎn)記為APRAM1.模型特點(diǎn)由p個(gè)處理器組成每個(gè)處理器都有其本地存儲(chǔ)器、局部時(shí)鐘和局部程序處理器間的通信經(jīng)過(guò)共享全局存儲(chǔ)器無(wú)全局時(shí)鐘各處理器異步地獨(dú)立執(zhí)行各自的指令處理器任何時(shí)間依賴關(guān)系需明確地在各處理器的程序中加入同步(路)障(SynchronizationBarrier)一條指令可在非確定但有限的時(shí)間內(nèi)完成√√√√√√2、APRAM模型中的指令類型有四類指令①全局讀將全局存儲(chǔ)單元中的內(nèi)容讀入局存單元中②局部操作對(duì)局存中的數(shù)執(zhí)行操作，其結(jié)果存入局存中③全局寫將局存單元中的內(nèi)容寫入全局存儲(chǔ)單元中④同步同步是計(jì)算中的一個(gè)邏輯點(diǎn)，在該點(diǎn)各處理器均需等待別的處理器到達(dá)后，才能執(zhí)行其局部程序3.APRAM模型中完成的計(jì)算計(jì)算是由一系列用同步障分開的全局相所組成在各全局相內(nèi)，每個(gè)處理器異步地運(yùn)行其局部程序每個(gè)局部程序中的最后一條指令是一條同步障指令各處理器均可異步地讀取和寫入全局存儲(chǔ)器在同一相內(nèi)不允許兩個(gè)處理器訪問(wèn)同一單元不同的處理器訪問(wèn)存儲(chǔ)單元總是由一同步障所分開，所以指令完成時(shí)間上的差異并不影響整個(gè)計(jì)算。√√√同步障指令局部程序…同步障指令局部程序…同步障指令局部程序…同步障指令局部程序…P1P2……4.APRAM模型中的時(shí)間計(jì)算使用APRAM模型計(jì)算算法的時(shí)間復(fù)雜度時(shí)，假定局部操作取單位時(shí)間全局讀／寫時(shí)間為d它定量化了通信延遲，代表讀/寫全局存儲(chǔ)器的平均時(shí)間，d隨機(jī)器中的處理器增加而增加同步障的時(shí)間為B它是處理器數(shù)P的非降函數(shù)B=B(P)在APRAM中假定上述參數(shù)服從如下關(guān)系：2≤d≤B≤P同時(shí)：B(P)∈O(dlogP)或B(P)∈O(dlogP/logd)令tph為全局相內(nèi)各處理器指令執(zhí)行時(shí)間中最長(zhǎng)者，則整個(gè)程序運(yùn)行時(shí)間T為各相的時(shí)間之和加上B乘以同步障次數(shù)，即:T=∑tph+B×同步障次數(shù)√√√四.BSP模型BSP-BulkSynchronizationParallel1.BSP模型的提出哈佛大學(xué)的LeslieValiant提出：塊同步并行(BSP)，用以克服PRAM模型的缺點(diǎn)，但保留其簡(jiǎn)單性。一個(gè)BSP計(jì)算機(jī)由n個(gè)結(jié)點(diǎn)(處理器和存儲(chǔ)器對(duì))所組成。2.特點(diǎn)一個(gè)BSP程序有n個(gè)進(jìn)程，每個(gè)駐留在一個(gè)結(jié)點(diǎn)上?；緯r(shí)間單位是周期(或時(shí)間步)程序按嚴(yán)格的超步序列執(zhí)行同步路障迫使進(jìn)程等待BSP計(jì)算機(jī)是MIMD系統(tǒng)BSP模型是超步級(jí)的松同步在一個(gè)超步中，不同進(jìn)程以不同速率異步執(zhí)行BSP模型交互機(jī)制是共享變量或是消息傳遞3.h關(guān)系的定義一個(gè)h關(guān)系是任何通信操作的抽象，在其中，每個(gè)結(jié)點(diǎn)最多發(fā)出h個(gè)字到各結(jié)點(diǎn)，并且每個(gè)結(jié)點(diǎn)最多接收h個(gè)字在一個(gè)BSP計(jì)算機(jī)中，實(shí)現(xiàn)任何h關(guān)系的時(shí)間不會(huì)超過(guò)gh個(gè)周期(g是由機(jī)器平臺(tái)決定的一個(gè)常數(shù))超步程序…4.一個(gè)超步執(zhí)行時(shí)間的確定計(jì)算時(shí)間w處理器中完成計(jì)算操作所需的最大周期數(shù)路障同步開銷為L(zhǎng)通信開銷為gh周期g是實(shí)現(xiàn)h關(guān)系的比例系數(shù)，常數(shù)w+gh+L執(zhí)行一個(gè)超步的時(shí)間為:結(jié)論在一個(gè)有n個(gè)處理器的EREWPRAM計(jì)算機(jī)上，對(duì)兩個(gè)N維向量A和B求內(nèi)積s，可指派每個(gè)處理器完成2N／n個(gè)加法和乘法;改用BSP機(jī)器模型實(shí)現(xiàn)一個(gè)并行執(zhí)行上述內(nèi)積求解。在一個(gè)有8個(gè)處理器的BSP計(jì)算機(jī)上，用4個(gè)超步完成問(wèn)題求解：例題①每個(gè)處理器在w=2N／8周期內(nèi)計(jì)算，求出局部和②通信1次：處理器0，2，4，6將其局部和→處理器1，3，5，7③路障同步計(jì)算時(shí)間通信開銷同步開銷超步１超步2①計(jì)算１、３、５、７各自完成一次加法②通訊1次：處理器１，５中間結(jié)果送處理器３和７③路障同步計(jì)算時(shí)間通信開銷同步開銷超步3①計(jì)算：處理器３和處理器７，各完成一次加②通訊：處理器３→處理器７，完成一次通訊③路障同步計(jì)算時(shí)間通信開銷同步開銷2N／8+3g+3Ｌ+3個(gè)周期超步4①處理器7完成一次加法(w＝１）產(chǎn)生最后和②不再需要任何通信或同步計(jì)算時(shí)間無(wú)同步通信開銷總執(zhí)行時(shí)間總共計(jì)算了3次（實(shí)際上每一次都發(fā)生了計(jì)算的“重疊”現(xiàn)象）比較點(diǎn)積在一個(gè)有n個(gè)處理器的BSP計(jì)算機(jī)上，執(zhí)行時(shí)間為：2N／n+logｎ(g+L+1)個(gè)周期PRAM計(jì)算機(jī)的執(zhí)行時(shí)間2N／n+logn個(gè)周期沒(méi)有考慮進(jìn)程管理的并行性開銷點(diǎn)積在一個(gè)有1個(gè)處理器的普通順序計(jì)算機(jī)上，執(zhí)行時(shí)間為：2N個(gè)周期關(guān)于BSP模型的實(shí)際優(yōu)點(diǎn)和評(píng)論：比起PRAM模型來(lái)，BSP模型更為現(xiàn)實(shí):除了用于進(jìn)程管理的并行性開銷外，它考慮了所有其他開銷。對(duì)兩個(gè)N維向量A和B求內(nèi)積s單機(jī)順序：2N個(gè)周期在n個(gè)處理器的EREWPRAM計(jì)算機(jī)上，指派每個(gè)的處理器完成2N/n個(gè)加法和乘法，在2N/n個(gè)周期內(nèi)產(chǎn)生一個(gè)局部結(jié)果，然后用樹歸約方法在logn周期中，將n個(gè)局部和相加，形成最后的總和s。則總的執(zhí)行時(shí)間為2N/n+logn在一個(gè)有n個(gè)處理器的BSP計(jì)算機(jī)上，執(zhí)行時(shí)間為：2N／n+logｎ(g+L+1)個(gè)周期。五.VLSI復(fù)雜性模型VLSI復(fù)雜性模型背景：以ClarkThompson(1980)的研究工作為基礎(chǔ)的二維VLSI芯片的AT2模型。AT2模型設(shè)A是用VLSI電路芯片完成給定運(yùn)算的芯片面積;T為執(zhí)行時(shí)間;又設(shè)s為運(yùn)算問(wèn)題的規(guī)模。Thompson在其博士論文中曾指出：對(duì)某些運(yùn)算存在一個(gè)下界f(s),有AT2≥O(

f(s))1、芯片面積A的存儲(chǔ)界限許多計(jì)算在需要處理大型數(shù)據(jù)集時(shí)常受到存儲(chǔ)器的限制。計(jì)算對(duì)存儲(chǔ)量的需求常常決定了芯片面積A的下限。2、AT體積的I/O界限可以用乘積AT來(lái)表示I／O的下限。3、等分通信界限A1/2Ｔ等分面積A1/2Ｔ，限定通信的下限。4、例題矩陣相乘算法的VLSI芯片的實(shí)現(xiàn)(VictorPrasanna，1992)要求：如何計(jì)算芯片面積A和計(jì)算時(shí)間T？一個(gè)每行和每列處理單元(PE)都有廣播總線的網(wǎng)格系統(tǒng)上做n×n矩陣乘法C＝A×B分析：二維網(wǎng)格結(jié)構(gòu)如下圖所示。PE間的通信通過(guò)廣播總線實(shí)現(xiàn)PE廣播總線每個(gè)PE占據(jù)一單位面積總芯片面積為O(n2)廣播總線需要O(n2)導(dǎo)線面積nXn矩陣相乘可在此網(wǎng)格芯片上完成的時(shí)間為T＝O(n)說(shuō)明：PE表示成PE(i，j)，0≤i，j≤n-1存儲(chǔ)器分布在所有的PE上，每個(gè)PE只能訪問(wèn)自己的本地存儲(chǔ)器。下面的并行算法，可完成C(i，j)＝∑A(i，k)XB(k，j)k=0n-1其中0≤i，j≤n-1的點(diǎn)積運(yùn)算，并產(chǎn)生全部輸出元素。40PE(i，j)computes

C(i，j)←C(i，j)+A(i，k)XB(k，j)50ContinueDoall10for0≤i，j≤n-110PE(i，j)setsC(i,j)to0／Initialization／Do50for0≤k≤n-1Doall20for0≤i≤n-120PE(i，k)broadcastA(i，k)alongitsrowbusDoall30for0≤j≤n-130PE(k，j)broadcastB(k，j)alongitscolumnbus／PE(i，j)nowhasA(i，k)andB(k，j)，0≤i，j≤n/Doall40for0≤i，j≤n-1

Doall表示所有M段在M臺(tái)處理機(jī)上并行執(zhí)行并行程序點(diǎn)積程序算法沿k方向有一順序循環(huán)，用了n個(gè)單位時(shí)間(迭代)。已知，T＝O(n)，所以AT2＝O(n2)×(O(n))2＝O(n4)

5可擴(kuò)展的范圍和設(shè)計(jì)一、可擴(kuò)展性范圍系統(tǒng)伸縮：增加或減少系統(tǒng)資源。這里假定并行處理計(jì)算機(jī)的體系中的結(jié)點(diǎn)均為單一處理器結(jié)點(diǎn)可擴(kuò)展性范圍包括：資源可擴(kuò)展性應(yīng)用可擴(kuò)展性技術(shù)可擴(kuò)展性1.資源可擴(kuò)展性資源可擴(kuò)展性是指通過(guò)增加處理器數(shù)、更多的存儲(chǔ)部件(高速緩存，主存，磁盤)以及增加軟件等方法，使系統(tǒng)具有更高性能或功能。涉及三方面：規(guī)?？缮炜s性資源擴(kuò)展軟件可擴(kuò)展性規(guī)模可伸縮性與處理器數(shù)相關(guān)聯(lián)擴(kuò)展一個(gè)計(jì)算機(jī)系統(tǒng)增加機(jī)器規(guī)模（處理器數(shù)）不同并行計(jì)算機(jī)規(guī)?？蓴U(kuò)展能力不同限制并行系統(tǒng)可擴(kuò)展性的兩個(gè)主要因素是：程序設(shè)計(jì)及通信（1）規(guī)模可伸縮性處理器數(shù)示例在1997年時(shí)：一個(gè)對(duì)稱多處理機(jī)(SMP)系統(tǒng)最多能擴(kuò)展到大約64個(gè)處理器；一個(gè)IBMSP2并行機(jī)能擴(kuò)展到最多具有512個(gè)處理器。當(dāng)前的并行計(jì)算機(jī)規(guī)模的擴(kuò)展：增加互連網(wǎng)絡(luò)、接口以及通信軟件在內(nèi)的子系統(tǒng)有效地利用更大并行性，即如何為擴(kuò)大的系統(tǒng)進(jìn)行編程。（2）資源擴(kuò)展增加處理器數(shù)不是唯一方式保持處理器數(shù)不變通過(guò)增加更多存儲(chǔ)容量、更大的芯片外高速緩存以及更大容量磁盤等方法來(lái)擴(kuò)展系統(tǒng)。存儲(chǔ)部件示例IBMSP2中的存儲(chǔ)器需求當(dāng)Maui高性能計(jì)算中心(MHPCC)決定升級(jí)它的具有400個(gè)結(jié)點(diǎn)的SP2系統(tǒng)時(shí)，它選擇了增加存儲(chǔ)器和磁盤容量方法，而不是增加更多結(jié)點(diǎn)數(shù)方法。加入更多處理器表概述了所擴(kuò)展的存儲(chǔ)容量要求：系統(tǒng)必須設(shè)計(jì)成能允許擴(kuò)展這么多的容量。實(shí)際系統(tǒng)總有一個(gè)最大存儲(chǔ)器容量的上限。例如：IBMSP2中的每個(gè)結(jié)點(diǎn)最多可容納2GB存儲(chǔ)器；CrayT3D為64MB（3）軟件可擴(kuò)展性包括：操作系統(tǒng)的一個(gè)新版本，它具有更多功能性，如多線程，從而可支持更多的用戶進(jìn)程，更大的地址空間以及更高效的內(nèi)核功能等。具有更有效優(yōu)化的編譯器更有效的數(shù)學(xué)和工程庫(kù)更有效和易于使用的應(yīng)用軟件對(duì)用戶更友好的編程環(huán)境2、應(yīng)用可擴(kuò)展性相同程序在一個(gè)可擴(kuò)展系統(tǒng)上運(yùn)行時(shí)，其性能隨規(guī)模擴(kuò)大成比例地改進(jìn)。兩個(gè)度量：機(jī)器規(guī)模可擴(kuò)展性問(wèn)題規(guī)模的可擴(kuò)展性應(yīng)用程序（1）機(jī)器規(guī)?？蓴U(kuò)展性隨著附加處理器的增多，系統(tǒng)性能會(huì)有多大改進(jìn)。示例假定一個(gè)有n個(gè)處理器的系統(tǒng)，作數(shù)據(jù)庫(kù)服務(wù)器用它擁有美國(guó)人口數(shù)據(jù)庫(kù)，通常有100位美國(guó)科學(xué)家查詢，其性能為每秒1000個(gè)事務(wù)處理(TPS)。現(xiàn)在如果我們將處理器數(shù)加倍成2n，能期望速度有多少改進(jìn)?期望是多少？所增加的資源中，處理器最為常見；也可能是存儲(chǔ)器容量和I／O容量（2）問(wèn)題規(guī)?？蓴U(kuò)展性是指系統(tǒng)在處理更大數(shù)據(jù)量和工作負(fù)載的更大求解問(wèn)題時(shí)其性能如何。示例例如：仍以上述的數(shù)據(jù)庫(kù)服務(wù)器為例，如果該服務(wù)器上裝有中國(guó)人口的數(shù)據(jù)庫(kù)，則此服務(wù)器的服務(wù)質(zhì)量將會(huì)如何?注意到此數(shù)據(jù)庫(kù)的大小已增至原來(lái)的5倍。如果用戶數(shù)增至200(100個(gè)美國(guó)和100中國(guó)科學(xué)家聯(lián)合參與研究)，將會(huì)發(fā)生什么情況?在研究應(yīng)用可擴(kuò)展性時(shí)，有以下3點(diǎn)值得注意：許多實(shí)際的并行應(yīng)用問(wèn)題對(duì)于機(jī)器和問(wèn)題規(guī)模已有內(nèi)在限制應(yīng)將“應(yīng)用／機(jī)器”一起視為一個(gè)系統(tǒng)它也依賴于資源規(guī)模3、技術(shù)可擴(kuò)展性是指該系統(tǒng)能適應(yīng)技術(shù)的改變。它可進(jìn)一步分為3類：代可擴(kuò)展性空間可擴(kuò)展性異構(gòu)可擴(kuò)展性技術(shù)創(chuàng)新（1）代(時(shí)間)可擴(kuò)展性一個(gè)系統(tǒng)擴(kuò)展可以通過(guò)使用：下一代的硬件部件更快的處理器更快存儲(chǔ)器新版本的操作系統(tǒng)更強(qiáng)功能的編譯器計(jì)算機(jī)系統(tǒng)中發(fā)展最快的部件是處理器進(jìn)展最慢的部分是程序設(shè)計(jì)語(yǔ)言(Fortran77仍被廣泛使用)單計(jì)算機(jī)每?jī)赡昕梢詫⑻幚砥魃?jí)一次并以慢得多的速度更新其他部件并行計(jì)算機(jī)中這種更新不活躍例題IBM個(gè)人計(jì)算機(jī)的代可擴(kuò)展性:最具有代可擴(kuò)展的計(jì)算機(jī)是IBMPC機(jī)PC系統(tǒng)(從處理器到母板、I／O卡和軟件)是設(shè)計(jì)成代可擴(kuò)展的?，F(xiàn)有系統(tǒng)中的二進(jìn)制代碼和應(yīng)用程序(DOS、Windows、數(shù)據(jù)庫(kù)、電子表格及字處理軟件等)不用作任何修改，就可在升級(jí)的系統(tǒng)中運(yùn)行得更快。（2）空間可擴(kuò)展性這一用語(yǔ)是由GordenBell發(fā)明的，用來(lái)表示一個(gè)系統(tǒng)可從一個(gè)盒子、一間房間或一幢大樓中的多處理器擴(kuò)展到多幢大樓和地理范圍(遠(yuǎn)距離范圍)中的多處理器的能力。因特網(wǎng)則具有最好的空間可擴(kuò)展性SMP和MMP只具有有限的空間可擴(kuò)展性（3）異構(gòu)可擴(kuò)展性一個(gè)系統(tǒng)擴(kuò)展不同設(shè)計(jì)者和廠商所提供的硬件和軟件部分的能力系統(tǒng)應(yīng)使用具有標(biāo)準(zhǔn)、開放系統(tǒng)結(jié)構(gòu)和接口的部件例題可擴(kuò)展并行計(jì)算機(jī)的”軟件可移植性”IBM并行操作環(huán)境(POE)在任何規(guī)模的RS6000系統(tǒng)上具有可擴(kuò)展性POE特點(diǎn)支持一個(gè)并行程序無(wú)需任何修改就能在由RS6000結(jié)點(diǎn)機(jī)構(gòu)成的任何網(wǎng)絡(luò)中運(yùn)行結(jié)點(diǎn)可以是一個(gè)低端PowerPC工作站，可以是一個(gè)高端SP2寬結(jié)點(diǎn)這些結(jié)點(diǎn)能由任何普通互聯(lián)網(wǎng)絡(luò)，從慢速以太網(wǎng)到SP2的高性能開關(guān)(HPS)，加以連接結(jié)點(diǎn)之間的距離不限例題并行虛擬機(jī)(PVM)，它也是異構(gòu)可擴(kuò)展的：它允許一個(gè)并行程序運(yùn)行在來(lái)自不同廠商的結(jié)點(diǎn)機(jī)所構(gòu)成的網(wǎng)絡(luò)上。二、可擴(kuò)展設(shè)計(jì)原理包括：獨(dú)立原理平衡設(shè)計(jì)原理可擴(kuò)展性設(shè)計(jì)原理時(shí)延隱藏原理(第5章介紹）1.獨(dú)立原理（1）定義應(yīng)努力使系統(tǒng)中的各個(gè)組成部分（硬、軟件）相互獨(dú)立。如果無(wú)法達(dá)到完全獨(dú)立，則應(yīng)盡力使相關(guān)程度減至最小并使相關(guān)性盡量清晰。（2）采用獨(dú)立原理的