第1章并行計(jì)算與并行計(jì)算機(jī)結(jié)構(gòu)模型(3)

1、第一章 并行計(jì)算與并行計(jì)算機(jī)結(jié)構(gòu)模型計(jì)算機(jī)與軟件學(xué)院 陸克中1課程介紹2n問(wèn)題與建議Email：辦公室：科技樓701辦公室電話：26732030Office Hour：每周五下午1:30-3:30n成績(jī)?cè)u(píng)定25%實(shí)驗(yàn)報(bào)告 南區(qū)計(jì)算機(jī)大樓D22715%課后作業(yè)60%期末考試(閉卷)課程介紹3n教材陳國(guó)良. 并行計(jì)算結(jié)構(gòu).算法.編程(第3版). 北京: 高等教育出版社, 2011n主要參考書(shū)陳國(guó)良等. 并行算法實(shí)踐. 北京:高等教育出版社, 20044第一章 并行計(jì)算與并行計(jì)算機(jī)結(jié)構(gòu)模型n1.1 計(jì)算與計(jì)算機(jī)科學(xué)n1.2 單處理機(jī)與指令級(jí)并行n1.3 多核處理器與線程級(jí)并行n1.4 并行計(jì)算體系結(jié)

2、構(gòu)n1.5 并行計(jì)算概述51.1.1 科學(xué)發(fā)現(xiàn)的第三支柱：計(jì)算科學(xué)n科學(xué)發(fā)現(xiàn)三大支柱理論科學(xué)以數(shù)學(xué)學(xué)科為基礎(chǔ)實(shí)驗(yàn)科學(xué)以物理學(xué)科為基礎(chǔ)計(jì)算科學(xué)以計(jì)算機(jī)學(xué)科為基礎(chǔ)在許多情況下，計(jì)算手段是解決問(wèn)題的唯一或主要方法理論基礎(chǔ)尚未建立理論方法過(guò)于復(fù)雜試驗(yàn)費(fèi)用過(guò)于昂貴實(shí)驗(yàn)環(huán)境條件苛刻61.1.1 科學(xué)發(fā)現(xiàn)的第三支柱：計(jì)算科學(xué)n計(jì)算學(xué)科的興起計(jì)算科學(xué)與工程計(jì)算物理學(xué)、計(jì)算化學(xué)、計(jì)算生物學(xué)、計(jì)算地質(zhì)學(xué)、計(jì)算氣象學(xué)、計(jì)算材料學(xué)和計(jì)算電磁學(xué)等學(xué)科n計(jì)算科學(xué)的作用科學(xué)發(fā)現(xiàn)和人類文明進(jìn)步的第三支柱促進(jìn)其它學(xué)科發(fā)展的基礎(chǔ)作用解決21世紀(jì)重大科學(xué)問(wèn)題的綜合作用21世紀(jì)科學(xué)與工程發(fā)現(xiàn)的普遍模式n名人名言美國(guó)總統(tǒng)信息技術(shù)咨詢委

3、員會(huì)的報(bào)告雖然計(jì)算本身也是一門學(xué)科，但其具有促進(jìn)其他學(xué)科發(fā)展的作用。21世紀(jì)科學(xué)上最重要的和經(jīng)濟(jì)上最有前途的研究前沿，有可能通過(guò)熟練地掌握先進(jìn)的計(jì)算技術(shù)和運(yùn)用計(jì)算科學(xué)而得到解71.1.2 計(jì)算科學(xué)與計(jì)算機(jī)科學(xué)n計(jì)算科學(xué)應(yīng)用計(jì)算能力與方法解決實(shí)際問(wèn)題的一門學(xué)科特點(diǎn)知識(shí)強(qiáng)度高應(yīng)用面廣有益于其他研究領(lǐng)域的公益性學(xué)科n計(jì)算機(jī)科學(xué)計(jì)算科學(xué)的核心和重要組成部分同時(shí)強(qiáng)調(diào)工程實(shí)現(xiàn)和應(yīng)用n計(jì)算思維運(yùn)用計(jì)算機(jī)科學(xué)的基礎(chǔ)概念進(jìn)行問(wèn)題求解、系統(tǒng)設(shè)計(jì)以及人類行為的理解一種基本技能，如同閱讀、寫(xiě)作和算術(shù)(3R)技能8第一章 并行計(jì)算與并行計(jì)算機(jī)結(jié)構(gòu)模型n1.1 計(jì)算與計(jì)算機(jī)科學(xué)n1.2 單處理機(jī)與指令級(jí)并行n1.3 多核

4、處理器與線程級(jí)并行n1.4 并行計(jì)算體系結(jié)構(gòu)n1.5 并行計(jì)算概述91.2.1 加快CPU執(zhí)行速度n 流水線與超標(biāo)量流水線技術(shù)重疊指令執(zhí)行中的不同階段超標(biāo)量處理器可在同一時(shí)鐘周期內(nèi)發(fā)射多條指令功能指令級(jí)并行執(zhí)行相關(guān)n超長(zhǎng)指令字將能夠并行執(zhí)行的指令合在一起分配給處理器，在多個(gè)功能單元上同時(shí)執(zhí)行n向量指令同一條指令同時(shí)對(duì)一組數(shù)據(jù)施行相同的操作101.2.2 減少存儲(chǔ)延遲n存儲(chǔ)器性能的局限CPU與存儲(chǔ)器之間的性能差距每年平均增長(zhǎng)約50%存儲(chǔ)容量存儲(chǔ)帶寬訪存延遲n使用高速緩存平滑CPU與DRAM之間的性能差距快速、小容量和高帶寬高速緩存命中率問(wèn)題高速緩存一致性問(wèn)題111.2.3 改善輸入和輸出以及網(wǎng)絡(luò)

5、性能n輸入和輸出設(shè)備磁盤(pán)高速緩存n網(wǎng)絡(luò)系統(tǒng)用戶模式12第一章 并行計(jì)算與并行計(jì)算機(jī)結(jié)構(gòu)模型n1.1 計(jì)算與計(jì)算機(jī)科學(xué)n1.2 單處理機(jī)與指令級(jí)并行n1.3 多核處理器與線程級(jí)并行n1.4 并行計(jì)算體系結(jié)構(gòu)n1.5 并行計(jì)算概述131.3.1 單核處理器結(jié)構(gòu)設(shè)計(jì)n處理器性能與摩爾定律集成電路上可容納的晶體管數(shù)目，約每隔18個(gè)月增加一倍計(jì)算機(jī)系統(tǒng)的性能，每隔18個(gè)月會(huì)提高一倍n傳統(tǒng)單核處理器存在的問(wèn)題如何有效地利用巨量的晶體管資源晶體管門延遲時(shí)間將小于互連的線延遲處理器性能的提升與電路復(fù)雜度的平方根成正比芯片發(fā)熱現(xiàn)象日益突出設(shè)計(jì)和人力成本均急劇上升給軟件(編譯器)設(shè)計(jì)增加了額外的負(fù)擔(dān)141.3.2

6、 多核處理器的結(jié)構(gòu)設(shè)計(jì)n多核處理器最初稱單芯片多處理器與傳統(tǒng)的對(duì)稱多處理器系統(tǒng)具有很多相似之處將所有多核處理器封裝在單個(gè)基片內(nèi)n多核處理器的技術(shù)特點(diǎn)便于優(yōu)化設(shè)計(jì)降低功耗較容易地實(shí)現(xiàn)設(shè)計(jì)要求的主頻線程級(jí)的應(yīng)用軟件易于移植到多核環(huán)境中151.3.3 多核處理器實(shí)例n學(xué)術(shù)界多核處理器實(shí)例16Hydra多核處理器總體結(jié)構(gòu)1.3.3 多核處理器實(shí)例n工業(yè)界多核處理器實(shí)例Intel Core Duo共享二級(jí)Cache更多的緩存空間更低的片上通信延遲適用于僅使用單一雙核處理器的系統(tǒng)AMD Dual Core Opteron私有二級(jí)Cache更多的私有緩存空間易于融合多個(gè)芯片之間的一致性信息適用于將多個(gè)雙核處

7、理器組織起來(lái)的系統(tǒng)17第一章 并行計(jì)算與并行計(jì)算機(jī)結(jié)構(gòu)模型n1.1 計(jì)算與計(jì)算機(jī)科學(xué)n1.2 單處理機(jī)與指令級(jí)并行n1.3 多核處理器與線程級(jí)并行n1.4 并行計(jì)算體系結(jié)構(gòu)n1.5 并行計(jì)算概述181.4.1 并行計(jì)算機(jī)結(jié)構(gòu)模型n大型并行機(jī)系統(tǒng)單指令流多數(shù)據(jù)流(SIMD)并行向量處理機(jī)(PVP)對(duì)稱多處理機(jī)(SMP)大規(guī)模并行處理機(jī)(MPP)分布共享存儲(chǔ)多處理機(jī)(DSM)工作站機(jī)群(COW)191.4.1 并行計(jì)算機(jī)結(jié)構(gòu)模型n并行向量處理機(jī)(PVP)少量的高性能的定制向量處理器VP專門設(shè)計(jì)的交叉開(kāi)關(guān)互連共享存儲(chǔ)通常不使用高速緩存，配有大量的向量寄存器201.4.1 并行計(jì)算機(jī)結(jié)構(gòu)模型n對(duì)稱多處

8、理機(jī)(SMP)結(jié)構(gòu)對(duì)稱性共享存儲(chǔ)，處理器通過(guò)讀/寫(xiě)共享變量通信單地址空間高速緩存及其一致性211.4.1 并行計(jì)算機(jī)結(jié)構(gòu)模型n大規(guī)模并行處理機(jī)(MPP)大量的商用處理器，可擴(kuò)放性好物理上分布的分布式存儲(chǔ)器高帶寬低延遲的定制互連網(wǎng)絡(luò)消息傳遞方式通信221.4.1 并行計(jì)算機(jī)結(jié)構(gòu)模型n分布共享存儲(chǔ)處理機(jī)(DSM)由各個(gè)局存構(gòu)成全局地址空間定制互連網(wǎng)絡(luò)基于目錄DIR的高速緩存一致性系統(tǒng)軟/硬件提供單一地址編程空間231.4.1 并行計(jì)算機(jī)結(jié)構(gòu)模型n工作站機(jī)群(COW)每個(gè)節(jié)點(diǎn)都是一臺(tái)完整的PC機(jī)或工作站(無(wú)頭工作站)低成本標(biāo)準(zhǔn)商用互連網(wǎng)絡(luò)分布存儲(chǔ)，松散耦合結(jié)構(gòu)易搭建，投資風(fēng)險(xiǎn)小241.4.1 并行計(jì)

9、算機(jī)結(jié)構(gòu)模型n公用結(jié)構(gòu)SMP、MPP、DSM和COW并行結(jié)構(gòu)漸趨一致大量的節(jié)點(diǎn)通過(guò)高速網(wǎng)絡(luò)互連起來(lái)節(jié)點(diǎn)遵循Shell結(jié)構(gòu)用定制的Shell電路將商用微處理器和節(jié)點(diǎn)的其他部分連接起來(lái)CPU升級(jí)只需要更換Shell251.4.1 并行計(jì)算機(jī)結(jié)構(gòu)模型n5種結(jié)構(gòu)特性一覽表26屬性PVPSMPMPPDSMCOW結(jié)構(gòu)類型MIMDMIMDMIMDMIMDMIMD處理器類型專用定制商用商用商用商用互連網(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ǔ)器集中共享集中共享分布非共享

10、分布共享分布非共享訪存模型UMAUMANORMANUMANORMA代表機(jī)器Cray C - 9 0 , Cray T-90，銀河1號(hào)IBM R50, SGI Power Challenge，曙光1號(hào)Intel Paragon， IBM Option White，曙光1000/2000S t a n f o r d DASH, Cray T3DBerkeley NOW, Alpha Farm1.4.2 并行計(jì)算機(jī)訪存模型n均勻存儲(chǔ)訪問(wèn) (UMA)物理存儲(chǔ)器被所有處理器均勻共享所有處理器訪問(wèn)任何存儲(chǔ)字取相同的時(shí)間每臺(tái)處理器可帶私有高速緩存外圍設(shè)備也可以一定形式共享271.4.2 并行計(jì)算機(jī)訪存模型

11、n非均勻存儲(chǔ)訪問(wèn)(NUMA)共享存儲(chǔ)器在物理上分布在所有處理器中，所有本地存儲(chǔ)器的集合組成了全局地址空間處理器訪問(wèn)存儲(chǔ)器的時(shí)間是不一樣的訪問(wèn)本地存儲(chǔ)器或群內(nèi)共享存儲(chǔ)器較快訪問(wèn)外地存儲(chǔ)器或全局共享存儲(chǔ)器較慢每臺(tái)處理器可帶私有高速緩存，外設(shè)也可以某種形式共享 281.4.2 并行計(jì)算機(jī)訪存模型n全高速緩存存儲(chǔ)訪問(wèn)(COMA)各處理器節(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ì)被遷移到要用到它們的地方 291.4.2 并行計(jì)算機(jī)訪存模型

12、n高速緩存一致性非均勻存儲(chǔ)訪問(wèn)(CC-NUMA)大多數(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ù)遷移至要用到它的地方301.4.2 并行計(jì)算機(jī)訪存模型n遠(yuǎn)程存儲(chǔ)訪問(wèn)(NORMA)所有存儲(chǔ)器是私有的絕大數(shù)NORMA都不支持遠(yuǎn)程存儲(chǔ)器的訪問(wèn)在DSM中，NORMA就消失了311.4.2 并行計(jì)算機(jī)訪存模型n構(gòu)筑并行機(jī)系統(tǒng)的不同存儲(chǔ)結(jié)構(gòu)321.4.3 并行計(jì)算機(jī)存儲(chǔ)組織

13、n層次存儲(chǔ)技術(shù)寄存器高速緩存主存儲(chǔ)器磁盤(pán)存儲(chǔ)器磁帶機(jī)331.4.3 并行計(jì)算機(jī)存儲(chǔ)組織n高速緩存一致性各個(gè)處理器的高速緩存中的數(shù)據(jù)副本保持一致高速緩存寫(xiě)策略寫(xiě)直達(dá)寫(xiě)回高速緩存不一致性的原因共存可寫(xiě)數(shù)據(jù)進(jìn)程遷移繞過(guò)高速緩存的I/O操作341.4.3 并行計(jì)算機(jī)存儲(chǔ)組織n監(jiān)聽(tīng)總線協(xié)議適用于基于總線連接的多處理機(jī)系統(tǒng)由總線監(jiān)聽(tīng)高速緩存中數(shù)據(jù)的一致性狀態(tài)是否被破壞寫(xiě)無(wú)效和寫(xiě)更新351.4.3 并行計(jì)算機(jī)存儲(chǔ)組織n基于目錄的協(xié)議適用于多級(jí)互連網(wǎng)絡(luò)連接的多處理機(jī)系統(tǒng)使用一個(gè)目錄來(lái)記錄共享數(shù)據(jù)的所有高速緩存行的位置和狀態(tài)36第一章 并行計(jì)算與并行計(jì)算機(jī)結(jié)構(gòu)模型n1.1 計(jì)算與計(jì)算機(jī)科學(xué)n1.2 單處理機(jī)與指

14、令級(jí)并行n1.3 多核處理器與線程級(jí)并行n1.4 并行計(jì)算體系結(jié)構(gòu)n1.5 并行計(jì)算概述371.5.1 關(guān)于并行計(jì)算n并行計(jì)算的含義簡(jiǎn)單地講，并行計(jì)算就是在并行計(jì)算機(jī)上所做的計(jì)算普通意義上講，它和常說(shuō)的高性能計(jì)算、超級(jí)計(jì)算等是同義詞n并行計(jì)算求解問(wèn)題將計(jì)算任務(wù)分解成多個(gè)子任務(wù)，有助于同時(shí)解決在同一時(shí)間，由不同的執(zhí)行部件可同時(shí)執(zhí)行多個(gè)子任務(wù)多計(jì)算資源下解決問(wèn)題的耗時(shí)要少于單個(gè)計(jì)算資源下的耗時(shí)n并行計(jì)算的類型計(jì)算密集型：如大型科學(xué)工程計(jì)算與數(shù)值模擬等數(shù)據(jù)密集型：如數(shù)字圖書(shū)館、數(shù)據(jù)倉(cāng)庫(kù)、數(shù)據(jù)挖掘和計(jì)算可視化等網(wǎng)絡(luò)密集型：如協(xié)同計(jì)算和遠(yuǎn)程診斷等381.5.1 關(guān)于并行計(jì)算n并行計(jì)算與摩爾定律計(jì)算機(jī)性能

15、的發(fā)展遵循了著名的摩爾定律，即性能(Flop/s)每12年提高兩個(gè)數(shù)量級(jí)391.5.1 關(guān)于并行計(jì)算n并行計(jì)算的戰(zhàn)略地位國(guó)家綜合國(guó)力的體現(xiàn)支撐國(guó)家實(shí)力持續(xù)發(fā)展的關(guān)鍵技術(shù)之一在國(guó)防安全、高科技發(fā)展和國(guó)民經(jīng)濟(jì)建設(shè)中占有重要的地位HPCC計(jì)劃1993年，美國(guó)科學(xué)工程技術(shù)聯(lián)邦協(xié)調(diào)理事會(huì)提出的HPCC計(jì)劃，該計(jì)劃提出了某些重大挑戰(zhàn)性課題的計(jì)算需求，并提出了發(fā)展萬(wàn)億次(1012)計(jì)算機(jī)的研制計(jì)劃ASCI計(jì)劃1996年，由美國(guó)能源部聯(lián)合美國(guó)三大核武器實(shí)驗(yàn)室共同提出ASCI計(jì)劃，提出了發(fā)展千萬(wàn)億次(1015)計(jì)算機(jī)的目標(biāo)HPCS計(jì)劃2002年，美國(guó)DARPA啟動(dòng)了HPCS計(jì)劃，希望確定未來(lái)10年甚至20年通過(guò)平衡裁剪并行向量機(jī)、對(duì)稱多處理機(jī)、大規(guī)模并行處理機(jī)等體系結(jié)構(gòu)來(lái)構(gòu)成異構(gòu)超級(jí)計(jì)算機(jī)體系結(jié)構(gòu)，并且確定使用高產(chǎn)能而非峰值計(jì)算能力作為評(píng)估超級(jí)計(jì)算機(jī)的性能指標(biāo)401.5.1 關(guān)于并行計(jì)算n并行計(jì)算的研究?jī)?nèi)容并行計(jì)算機(jī)并行計(jì)算的硬件平臺(tái)并行算法