1、并行程序設(shè)計(jì) Parallel Programming,余華山,什么是并行計(jì)算?,通過(guò)計(jì)算機(jī)硬件和軟件協(xié)作，同時(shí)執(zhí)行多個(gè)數(shù)據(jù)運(yùn)算的一種計(jì)算模式 提高計(jì)算效率，包括提高計(jì)算速度、以及降低數(shù)據(jù)處理的成本 四種不同粒度/層次的并行計(jì)算 微指令級(jí)(SSE: streaming SIMD extensions)：向量處理指令 指令級(jí)(ILP: instruction-level parallelism): 一顆core微處理器，有3個(gè)ALU、2個(gè)FPU、3個(gè)SSE 超標(biāo)量技術(shù)：依靠微處理器體系結(jié)構(gòu)技術(shù)，動(dòng)態(tài)調(diào)整指令流的順序，一次發(fā)射多條指令，主流處理器幾乎都采用的技術(shù) 超長(zhǎng)指令字技術(shù)：編譯時(shí)將多條普通指

2、令組裝成“超級(jí)指令”，比如IA微處理器 線程級(jí)(TLP: thread-level parallelism)：由程序?qū)⒂?jì)算任務(wù)劃分成可以同時(shí)執(zhí)行的操作序列，每個(gè)操作序列分別由不同的處理器執(zhí)行內(nèi)核來(lái)處理 進(jìn)程級(jí)：由程序?qū)⒂?jì)算任務(wù)劃分成可以獨(dú)立分配計(jì)算資源的子任務(wù)，每個(gè)子任務(wù)分別由不同的計(jì)算機(jī)系統(tǒng)來(lái)處理,并行程序與并行計(jì)算機(jī),串行程序: 將計(jì)算任務(wù)分解成標(biāo)量操作的序列的程序。串行程序是可以并行執(zhí)行的 被編譯器編譯成面向SIMD的指令 被編譯器編譯成面向VLIW 指令 由支持superscalar技術(shù)的處理器執(zhí)行 并行程序: 顯式表達(dá)計(jì)算任務(wù)中各數(shù)據(jù)運(yùn)算無(wú)關(guān)性的程序 并行計(jì)算機(jī): 能夠同時(shí)執(zhí)行并行程

3、序中無(wú)關(guān)數(shù)據(jù)運(yùn)算的計(jì)算機(jī) 采用向量處理器 一條指令完成多個(gè)數(shù)據(jù)單元的處理 提供多個(gè)互相獨(dú)立的處理執(zhí)行核:每個(gè)執(zhí)行核分別執(zhí)行自己的指令流 多處理器系統(tǒng): Multi-core/SMP/CPU + Coprocessor 多計(jì)算機(jī)系統(tǒng): MPP/Cluster/Grid/Cloud,并行程序的開(kāi)發(fā)與并行計(jì)算,串行程序,程序員,串行編譯,串行程序,串行處理器,串行執(zhí)行,超標(biāo)量處理器,并行執(zhí)行,并行編譯,SIMD并行程序,SIMD處理器,并行執(zhí)行,VLIW并行程序,VLIW處理器,并行執(zhí)行,線程并行程序,多處理器系統(tǒng),并行執(zhí)行,進(jìn)程并行程序,多計(jì)算機(jī)系統(tǒng),并行執(zhí)行,線程并行程序,進(jìn)程并行程序,編譯,編

4、譯,我們一直在不自覺(jué)的使用并行計(jì)算技術(shù)來(lái)提升計(jì)算效能,當(dāng)前幾乎所有的計(jì)算機(jī)都是并行計(jì)算機(jī)：多核/微處理器內(nèi)多個(gè)執(zhí)行單元/SIMD指令 幾乎每個(gè)程序運(yùn)行時(shí)都在執(zhí)行并行計(jì)算：專家們(體系結(jié)構(gòu)/編譯/操作系統(tǒng))一直在替我們做并行技術(shù)的開(kāi)發(fā)和運(yùn)用 指令級(jí)并行: 提高同時(shí)執(zhí)行的指令數(shù)縮短指令流的執(zhí)行時(shí)間程序執(zhí)行效率的提升 指令的基本執(zhí)行過(guò)程: instruction fetch decode execute memory access write back 每個(gè)過(guò)程分別是由不同的部件執(zhí)行 通過(guò)流水, 使得多條指令同時(shí)執(zhí)行, 每條指令分別處于不同的執(zhí)行階段: 依靠pre-fetch/re-order等技術(shù)

5、 提供多個(gè)執(zhí)行單元，支持多條指令流水同時(shí)執(zhí)行 數(shù)據(jù)級(jí)并行(data-level parallelism)和任務(wù)級(jí)并行(task-level parallelism) : 提高同時(shí)執(zhí)行的線程數(shù)用戶工作效率的提升(同時(shí)做多件事情, 互不耽擱) 基本技術(shù)支撐: interrupt/lock/hyper-threading/ Cache/virtual memory/disk file: 執(zhí)行一個(gè)線程,總會(huì)發(fā)生數(shù)據(jù)訪問(wèn)失效,為什么要程序員編寫并行程序?,并行計(jì)算機(jī): 提升計(jì)算系統(tǒng)計(jì)算潛力的必然趨勢(shì) Frequency wall: 物理上限 指令流的執(zhí)行時(shí)間下限 Memory wall: CPU與Mem

6、ory的速度鴻溝 指令級(jí)并行的流水深度限制 Power wall: P = C (電容/晶體管的數(shù)量) V2 (電壓) F (頻率) 單個(gè)芯片的計(jì)算潛力上限 Multi-core: 提升單個(gè)芯片計(jì)算潛力的必然選擇, 保持Moores law: 增加執(zhí)行核(用于數(shù)據(jù)運(yùn)算的晶體管的數(shù)量),降低主頻 提高用于數(shù)據(jù)運(yùn)算的晶體管的比率: 降低指令級(jí)并行的流水深度 提高晶體管的利用率: 執(zhí)行核之間按需共享cache/FBI 挖掘處理器的計(jì)算潛力: 提高芯片內(nèi)用于數(shù)據(jù)處理的晶體管的比率 微指令級(jí)并行(SIMD): 提高計(jì)算機(jī)的字長(zhǎng) 一次解碼, 處理更多的數(shù)據(jù) 例如core微處理器的SSE指令采用128bit

7、寄存器, 一個(gè)指令周期可處理4個(gè)float數(shù) 數(shù)據(jù)級(jí)并行(data-level parallelism)和任務(wù)級(jí)并行(task-level parallelism) : multi-core, 支持多個(gè)指令流同時(shí)處于數(shù)據(jù)運(yùn)算階段,如何提高數(shù)據(jù)處理的效率: 利用多個(gè)執(zhí)行核分?jǐn)倲?shù)據(jù)處理任務(wù) 指令級(jí)并行/提高主頻: 縮短指令流的執(zhí)行時(shí)間 并行程序:縮短指令流的長(zhǎng)度 數(shù)據(jù)級(jí)并行/任務(wù)級(jí)并行: 同時(shí)執(zhí)行多個(gè)短的指令流 向量計(jì)算: 提高單條指令的數(shù)據(jù)處理量 處理器的主導(dǎo)技術(shù)已由提高處理器主頻轉(zhuǎn)向 多核技術(shù)多核技術(shù) 指令流的執(zhí)行時(shí)間延長(zhǎng)了 同時(shí)執(zhí)行的指令流數(shù)量增加了 專用協(xié)處理器技術(shù)(X86指令集包括近30

8、0條指令, 科學(xué)計(jì)算只需要其中的約80條指令) 提高用于數(shù)據(jù)處理的晶體管的比率 提高晶體管的利用率 可重構(gòu)計(jì)算技術(shù)(FPGA): 由應(yīng)用程序動(dòng)態(tài)將芯片定制成專用協(xié)處理器 單個(gè)數(shù)據(jù)處理部件的運(yùn)算速度有上限: frequency wall 多核時(shí)代, 計(jì)算平臺(tái)的關(guān)鍵特征: 不是單個(gè)執(zhí)行核的性能提升了, 而是可利用的執(zhí)行核的數(shù)量提升了,如何處理更大規(guī)模的問(wèn)題, 即: 如何在可接受的時(shí)間里完成更大規(guī)模數(shù)據(jù)的處理? 例如 電信計(jì)費(fèi) 網(wǎng)絡(luò)搜索 視頻點(diǎn)播 地震現(xiàn)象反演: 有限元法, 地震區(qū)域的10m10m10m作為一個(gè)粒子, 模擬這些粒子在地震前后的運(yùn)動(dòng)軌跡 一臺(tái)計(jì)算機(jī)的服務(wù)能力有上限： 處理器: 計(jì)算能力

9、（處理器的數(shù)量、處理器內(nèi)執(zhí)行核的數(shù)量） 內(nèi)存: 容量/訪問(wèn)速度和帶寬 磁盤及IO:容量/訪問(wèn)速度和帶寬 數(shù)據(jù)級(jí)并行(data-level parallelism)和任務(wù)級(jí)并行(task-level parallelism) 多臺(tái)計(jì)算機(jī)協(xié)作 面向領(lǐng)域/應(yīng)用的并行計(jì)算機(jī)/協(xié)處理器(如GPU)/可重構(gòu)計(jì)算(FPGA),編譯技術(shù)/微處理器體系結(jié)構(gòu)技術(shù)不足以開(kāi)發(fā)并行計(jì)算機(jī)的計(jì)算能力,VLIW/superscalar：適合開(kāi)發(fā)微處理器內(nèi)部各個(gè)執(zhí)行單元的并行能力 編譯技術(shù)：發(fā)現(xiàn)串行程序中無(wú)關(guān)的數(shù)據(jù)運(yùn)算 串行程序：隱藏了計(jì)算任務(wù)的數(shù)據(jù)運(yùn)算無(wú)關(guān)性 分析問(wèn)題的數(shù)學(xué)/物理模型 設(shè)計(jì)串行算法 用串行語(yǔ)言編碼算法 例如

10、：尋找N以內(nèi)的素?cái)?shù), 該如何并行？ prime0=2; prime1=3; p=2; for(i=5;iN;i=i+2) for(j=1; jp; j+) if ( i%primej=0 ) break; if ( jp ) break; primep = i; p+; ,并行程序設(shè)計(jì),以問(wèn)題分解為基礎(chǔ), 開(kāi)發(fā)面向并行計(jì)算機(jī)的程序: 通過(guò)多顆處理器協(xié)作、以及挖掘處理器的計(jì)算潛力, 達(dá)到加速數(shù)據(jù)處理的效率和提高問(wèn)題求解的規(guī)模的目標(biāo) 手段 挖掘每個(gè)處理器的計(jì)算潛力 提供更多的并行線程，避免由于內(nèi)存壁壘等因素導(dǎo)致執(zhí)行單元處于空等待狀態(tài) 微指令級(jí)并行(向量計(jì)算), 提高單條指令的數(shù)據(jù)處理量 多個(gè)處理器

11、協(xié)作, 分?jǐn)傆?jì)算任務(wù): 縮短每個(gè)指令流的長(zhǎng)度 多計(jì)算機(jī)間數(shù)據(jù)劃分: 增加存儲(chǔ)容量 目標(biāo) 加速數(shù)據(jù)處理的效率 提高問(wèn)題求解的規(guī)模 并行程序設(shè)計(jì)(本門課程)關(guān)注: 發(fā)現(xiàn)計(jì)算任務(wù)中無(wú)關(guān)的數(shù)據(jù)運(yùn)算，并利用數(shù)據(jù)運(yùn)算的無(wú)關(guān)性開(kāi)發(fā)并行計(jì)算機(jī)的計(jì)算能力 向量處理器/陣列處理器系統(tǒng) 多處理器系統(tǒng) 多計(jì)算機(jī)系統(tǒng),多核時(shí)代：當(dāng)多核處理器給用戶相應(yīng)提高的性能體驗(yàn)時(shí)，才真正到了多核時(shí)代,計(jì)算平臺(tái)可為程序的運(yùn)行提供多個(gè)執(zhí)行核 多核時(shí)代不等于多核處理器時(shí)代 如何獲得多個(gè)執(zhí)行核? 多核處理器 SMP/CPU + Coprocessor(專用協(xié)處理器/FPGA) Cluster/MPP Grid/Cloud 大多數(shù)人并沒(méi)有多個(gè)

12、執(zhí)行核協(xié)同計(jì)算(并行計(jì)算)的體會(huì) 計(jì)算機(jī)專業(yè)的整個(gè)本科教學(xué)，都是基于Von Neumann， 僅在操作系統(tǒng)、體系結(jié)構(gòu)里提到一點(diǎn)并行和并發(fā)的概念 使用的應(yīng)用軟件也基本是基于串行技術(shù): 對(duì)計(jì)算性能的體驗(yàn)并未改進(jìn), 甚至有所下降 串行程序+降低了主頻和指令流水深度的多核處理器 更復(fù)雜的操作系統(tǒng): 多線程支持/早先的超線程技術(shù) 操作系統(tǒng)程序與用戶程序同時(shí)運(yùn)行: Cache、FBI的瓶頸效應(yīng) 可以在一臺(tái)機(jī)器上同時(shí)運(yùn)行幾個(gè)程序: 多核處理器之前已經(jīng)如此 操作系統(tǒng)的多進(jìn)程/多線程/超線程支持技術(shù) 用于超級(jí)計(jì)算機(jī)(Cluster/MPP)的HTC (high-throughput computing),多核時(shí)

13、代的特點(diǎn),已經(jīng)具備的特點(diǎn): 并行計(jì)算機(jī)不再與“昂貴”、“高性能”有必然聯(lián)系，從體系結(jié)構(gòu)上看，我們所使用的都是并行計(jì)算機(jī) 支持SSE的多核CPU+GPU(每個(gè)GPU是一個(gè)微處理器陣列) CPU的微處理器內(nèi)核包括多個(gè)執(zhí)行單元，采用了superscalar/VLIW技術(shù) 尚不具備的特點(diǎn): 體驗(yàn)并行計(jì)算機(jī)對(duì)計(jì)算性能的提升效果 數(shù)據(jù)處理的速度更快 可處理的數(shù)據(jù)規(guī)模更大 挑戰(zhàn)性問(wèn)題: 并行程序的可移植性(衡量程序算法/代碼與目標(biāo)平臺(tái)體系結(jié)構(gòu)的緊密程度), 來(lái)自并行計(jì)算平臺(tái)的異構(gòu)性 Intel/AMD處理器：CPU + CPU IBM CELL處理器: CPU + Coprocessor 多處理器系統(tǒng): S

14、MP / (CPU + Coprocessor) / (CPU + FGPA) 多計(jì)算機(jī)系統(tǒng): Cluster/MPP/Grid/Cloud 編程人員：“傻瓜”還是“精英” “傻瓜”：知道語(yǔ)法就夠了，其他事情交給編譯、運(yùn)行支持去做吧 “精英”：我能，但只有我能；我能，但我只會(huì)這一點(diǎn) 盡管都是面向流媒體計(jì)算 CPU中的SSE：SIMD，向量指令 GPU：陣列處理器，線程并行編程(CUDA),新軟件危機(jī),硬件上多核、軟件上串行 大量的晶體管閑置、使用效率不高 主頻的降低，導(dǎo)致性能體驗(yàn)的下降 性能，再次成為編程技術(shù)的焦點(diǎn)：線程級(jí)并行對(duì)開(kāi)發(fā)多核處理器的計(jì)算能力至關(guān)重要 性能，依賴“精英”們實(shí)現(xiàn) 體系結(jié)

15、構(gòu)的特征 數(shù)學(xué)/物理模型中的計(jì)算并行性特征并行算法 編寫程序：既要做“經(jīng)理”，又要做“業(yè)務(wù)員” “業(yè)務(wù)員”：完成數(shù)據(jù)處理 “經(jīng)理”：“業(yè)務(wù)員”的分工、協(xié)調(diào)(在單核處理器時(shí)代，可以由編譯技術(shù)/微處理器體系結(jié)構(gòu)技術(shù)自動(dòng)解決) 能以來(lái)自動(dòng)機(jī)理論(運(yùn)行時(shí)支持) 、形式化理論(編譯技術(shù))代替“精英”嗎？ 能：當(dāng)這個(gè)問(wèn)題很簡(jiǎn)單時(shí) 不能：并行算法設(shè)計(jì)是“藝術(shù)性”、而非“技術(shù)性”的工作。請(qǐng)將一個(gè)求素?cái)?shù)的串行程序并行化吧。 并行程序設(shè)計(jì)：少數(shù)人的專利、編程人員的基本要求？,內(nèi)容提要,課程基本信息 對(duì)并行計(jì)算的認(rèn)識(shí) 并行計(jì)算的概念 并行計(jì)算平臺(tái) 并行計(jì)算技術(shù)的使用 問(wèn)題是什么？ 課程目標(biāo)與定位 教學(xué)安排,課程相關(guān)

16、信息,成績(jī)?cè)u(píng)定：平時(shí)成績(jī)(50%)+ max興趣研究報(bào)告，期末筆試 平時(shí)練習(xí)、編程實(shí)驗(yàn): 50分 興趣研究報(bào)告：50分。1-3人一組，自選題目，題目來(lái)源： 所在研究組面臨的計(jì)算性能需求，結(jié)合課程學(xué)習(xí)，提出解決方案 所在課題組正在解決的計(jì)算性能/計(jì)算效能方面的技術(shù)問(wèn)題，結(jié)合課程學(xué)習(xí)，提出并行處理技術(shù)對(duì)該問(wèn)題的促進(jìn) 高性能/高效能/云計(jì)算領(lǐng)域中感興趣的前沿研究方向，結(jié)合課程學(xué)習(xí)，開(kāi)展調(diào)研，給出該方向的研究進(jìn)展、趨勢(shì)和評(píng)價(jià) 期末考試：50分 課程網(wǎng)頁(yè) ,課程歷史與內(nèi)容沿革,1999-2002年，李曉明 MPI、HPF、OpenMP、并行編譯 集群、MPP、SMP 2003年開(kāi)始，余華山 2005年

17、MPI、OpenMP、并行算法設(shè)計(jì)與應(yīng)用實(shí)例、基于網(wǎng)絡(luò)的并行處理 集群、MPP、SMP、網(wǎng)格 2007年：教育部-Intel精品課程建設(shè)項(xiàng)目 MPI、pthread與Intel多核技術(shù)、并行算法設(shè)計(jì)與應(yīng)用實(shí)例、 OpenMP、基于網(wǎng)絡(luò)的并行處理 多核、 SMP、集群、MPP、網(wǎng)格 2008年：教育部-IBM精品課程建設(shè)項(xiàng)目 pthread與Intel多核技術(shù)、CELL BE技術(shù)、 MPI、并行算法設(shè)計(jì)與應(yīng)用實(shí)例、基于網(wǎng)絡(luò)的并行處理(網(wǎng)格) 多核、 SMP、集群、MPP、網(wǎng)格,2011年：北京大學(xué)研究生課程建設(shè) 以出版為目標(biāo)的講義 完成一章，在課程網(wǎng)站發(fā)布一章,并行程序設(shè)計(jì)的基本概念,“并行程序

18、”：支持多個(gè)操作、或者任務(wù)同時(shí)執(zhí)行的一種規(guī)劃 做事情，總要規(guī)劃動(dòng)作的順序：確定房子的地址、設(shè)計(jì)結(jié)構(gòu)圖、作預(yù)算、選擇施工者、規(guī)劃施工進(jìn)度、買建筑材料和施工。 規(guī)劃的關(guān)鍵是分析問(wèn)題各個(gè)部分之間的內(nèi)在聯(lián)系，任何規(guī)劃都不能破壞這個(gè)聯(lián)系 總有一些部分之間是沒(méi)有內(nèi)在聯(lián)系的，可以同時(shí)執(zhí)行：房屋建筑的第一階段施工、購(gòu)買第二階段建筑材料 什么是并行程序設(shè)計(jì)：以任務(wù)分解為基礎(chǔ), 開(kāi)發(fā)面向并行計(jì)算機(jī)的應(yīng)用程序, 以提高數(shù)據(jù)處理的效率、或者提高可解問(wèn)題的規(guī)模. 計(jì)算平臺(tái)：支持同時(shí)執(zhí)行多個(gè)數(shù)據(jù)處理運(yùn)算(提供多個(gè)執(zhí)行核/向量處理器) 操作系統(tǒng)：支持多指令流調(diào)度(多核處理器計(jì)算平臺(tái))、或者多數(shù)據(jù)流訪問(wèn)(向量處理器平臺(tái)) 編

19、程語(yǔ)言(以及編譯運(yùn)行系統(tǒng))：支持計(jì)算并行性的表達(dá),并行計(jì)算有什么用途,并非所有問(wèn)題都需要使用并行計(jì)算技術(shù) 寫WORD文檔、寫C/C+程序代碼 一個(gè)字符、一個(gè)字符地從鍵盤輸入 即使用最低端的機(jī)器，沒(méi)有人感覺(jué)到不能及時(shí)得到響應(yīng)(你同時(shí)打開(kāi)了很多文檔、再邊聽(tīng)MP3除外) 使用Google、Baidu搜索網(wǎng)頁(yè) 時(shí)刻都有成千上萬(wàn)的用戶在搜索 有興趣嗎？對(duì)比一下從Google、Baidu得到的響應(yīng)速度、在一臺(tái)高端服務(wù)器上模擬100個(gè)用戶搜索1,000,000條記錄的響應(yīng)速度 汶川地震研究：反演地震過(guò)程，整個(gè)中國(guó)幾乎都有震感 震區(qū)離散化，每10個(gè)立方米作為一個(gè)粒子 使用當(dāng)今運(yùn)算速度最快的處理器，對(duì)這個(gè)三維數(shù)

20、組做一次最簡(jiǎn)單的運(yùn)算，比如對(duì)每個(gè)元素做一次加法，需要多久？,并行程序的時(shí)代已經(jīng)到了？,并行計(jì)算：在計(jì)算平臺(tái)上同時(shí)執(zhí)行多個(gè)數(shù)據(jù)運(yùn)算 提高計(jì)算的效能 提高處理器的計(jì)算潛力 提高處理器的利用率 提高數(shù)據(jù)處理的速度 提高可解問(wèn)題的規(guī)模 并行計(jì)算平臺(tái)隨處可見(jiàn) 多核處理器：PC機(jī)、筆記本 SMP：服務(wù)器 Cluster：大型計(jì)算中心服務(wù)器 網(wǎng)絡(luò)計(jì)算環(huán)境：CN Grid、China Grid、TeraGrid、Google？ 并行程序的需求來(lái)自各個(gè)領(lǐng)域 我們的生活已經(jīng)離不開(kāi)網(wǎng)絡(luò)：成千上萬(wàn)的并發(fā)用戶訪問(wèn)搜索引擎、新聞網(wǎng)站、通信聊天網(wǎng)站、娛樂(lè)視頻網(wǎng)站、多人網(wǎng)絡(luò)游戲、公共服務(wù)網(wǎng)站(圖書(shū)館、電子文獻(xiàn)數(shù)據(jù)庫(kù))、電子銀

21、行、電子政務(wù) 工程、科研、生活服務(wù)越來(lái)越依賴于大規(guī)模數(shù)據(jù)的高效計(jì)算：飛機(jī)設(shè)計(jì)、汽車碰撞模擬、武器設(shè)計(jì)、油氣勘探、神州飛船跟蹤、基因數(shù)據(jù)分析、地震運(yùn)動(dòng)過(guò)程模擬、太陽(yáng)風(fēng)磁場(chǎng)重聯(lián)模擬、三峽大壩選址、氣象預(yù)報(bào)、,并行計(jì)算的現(xiàn)狀,CPU執(zhí)行程序時(shí)，使用了superscalar/VLIW CPU早就提供了SIMD支持，從MMX到現(xiàn)在的SSE4。 一些商業(yè)軟件使用了SIMD 一些函數(shù)包使用了SIMD 一些編譯器在對(duì)循環(huán)優(yōu)化時(shí)使用了SIMD 程序員使用了嗎？ 誰(shuí)在用桌面機(jī)的多核處理器計(jì)算能力？ 桌面機(jī)上的應(yīng)用以串行程序?yàn)橹?自己會(huì)寫并行程序的人不多 一邊寫程序、一邊聽(tīng)MP3時(shí)，可以用上，但影響編程、不用多核處

22、理器時(shí)計(jì)算能力也夠了 SMP (Symmetric Multi Processing )服務(wù)器 商業(yè)軟件：開(kāi)發(fā)了并行能力 自己開(kāi)發(fā)的軟件：以串行程序?yàn)橹?主要是依靠操作系統(tǒng)支持多個(gè)進(jìn)程/線程的同時(shí)執(zhí)行,能同時(shí)使用成百上千顆處理器的應(yīng)用有多少?,集群上的并行計(jì)算情況：以CCSE128節(jié)點(diǎn)使用情況為例(2006年3月) 3309個(gè)計(jì)算任務(wù) 平均使用1.85個(gè)計(jì)算節(jié)點(diǎn) 節(jié)點(diǎn)資源利用率94.7% IBM RoadRunner 哪個(gè)應(yīng)用能同時(shí)使用12960顆CELL CELL處理器執(zhí)行標(biāo)量計(jì)算程序?qū)⒎浅Ｂ?6912顆AMD Opteron似乎只是為了讓每個(gè)節(jié)點(diǎn)也能夠正常執(zhí)行原來(lái)的標(biāo)量計(jì)算進(jìn)程) 天河計(jì)算

23、機(jī)：主要計(jì)算能力來(lái)自GPU 2048顆飛騰FT-1000八核心處理器 14336顆Intel Xeon X5670 2.93GHz六核心處理器 7168塊NVIDIA Tesla M2050高性能計(jì)算卡(GPU),如何看待我國(guó)的天河一號(hào)A？,這是一個(gè)了不起的成就：2萬(wàn)多顆處理器放在一起，并讓它們一起協(xié)作，采用LU分解的方法求解一個(gè)密集矩陣的方程 通信問(wèn)題 穩(wěn)定性問(wèn)題：一個(gè)部件的出錯(cuò)/故障率是百萬(wàn)分之一，這么多通信、存儲(chǔ)、計(jì)算、及其他輔助部件放在一起，怎么能夠穩(wěn)定運(yùn)行？ 功耗和散熱問(wèn)題 這臺(tái)機(jī)器本身也許并不是一個(gè)特別值得炫耀的成就 有多少支持GPU的軟件？ 支持GPU的軟件能夠在哪些領(lǐng)域使用？G

24、PU的基本數(shù)據(jù)類型是float，這樣一個(gè)精度下如何進(jìn)行迭代模擬類計(jì)算、高精度場(chǎng)計(jì)算？ 有多少應(yīng)用能夠有效開(kāi)發(fā)1024顆處理器執(zhí)行核的計(jì)算能力？比如速度能夠提高600倍 有多少人在開(kāi)發(fā)面向這個(gè)機(jī)器的軟件？軟件的開(kāi)發(fā)周期5-10年。,誰(shuí)依靠網(wǎng)絡(luò)環(huán)境進(jìn)行并行計(jì)算?,TeraGrid:主要用戶是SSH 沒(méi)有網(wǎng)格對(duì)這類用戶沒(méi)有影響 其實(shí)就是使用超級(jí)計(jì)算機(jī) EGEE:主要工作是提供一個(gè)統(tǒng)一的用戶接口 支持并發(fā)用戶，避免相互惡性競(jìng)爭(zhēng)：把計(jì)算任務(wù)動(dòng)態(tài)綁定到具體的超級(jí)計(jì)算機(jī)上 沒(méi)有支持一個(gè)問(wèn)題同時(shí)使用多臺(tái)超級(jí)計(jì)算機(jī) CN Grid、ChinaGrid上是否有跨超級(jí)計(jì)算機(jī)求解問(wèn)題的應(yīng)用？ Google searc

25、h engine：依靠網(wǎng)絡(luò)計(jì)算環(huán)境支持大規(guī)模并發(fā)用戶 云計(jì)算的概念 以數(shù)據(jù)為中心，根據(jù)數(shù)據(jù)需求選擇計(jì)算資源,并行技術(shù)的應(yīng)用為何不如人意？,并行計(jì)算平臺(tái)有其適用范圍 并行處理技術(shù)的使用離不開(kāi)人的參與 并行求解算法的設(shè)計(jì)不是簡(jiǎn)單的串行算法并行化：按照體系結(jié)構(gòu)設(shè)計(jì)算法 向量處理器：標(biāo)量數(shù)據(jù)要向量化 多顆標(biāo)量處理器：設(shè)計(jì)多個(gè)指令流,你的筆記本、桌面機(jī)需要提高性能嗎？,需要性能提高的理由 系統(tǒng)啟動(dòng)慢 啟動(dòng)一個(gè)應(yīng)用程序慢：打開(kāi)一個(gè)PDF、WORD、VC編程環(huán)境、DVD視頻文件、 打開(kāi)很多個(gè)應(yīng)用程序時(shí)，系統(tǒng)響應(yīng)很慢 打開(kāi)一個(gè)大的PDF文件、WORD文件，翻頁(yè)瀏覽時(shí)響應(yīng)慢 如何提高性能:CPU的計(jì)算能力按照m

26、oore定律成長(zhǎng)，你體驗(yàn)的性能成長(zhǎng)多少了？ 微軟的應(yīng)用程序都很大，載入系統(tǒng)慢 同時(shí)運(yùn)行的應(yīng)用越多，系統(tǒng)切換需要的存儲(chǔ)交換越大 如果你覺(jué)得翻頁(yè)瀏覽時(shí)響應(yīng)慢，請(qǐng)你看看被打開(kāi)的PDF文件、WORD文件有多大 你使用的CPU性能早就遠(yuǎn)超過(guò)你的需求：軟件的質(zhì)量、存儲(chǔ)的速度？ 把VISTA還原成XP，把XP替換成WIN98，速度的體驗(yàn)會(huì)如何？ 把CPU從INTEL CORE i5換成Pentium IV 1.8/3.2，速度的體驗(yàn)會(huì)如何？,多核處理器： CELL,DMA (Direct Memory Access )數(shù)據(jù)存?。壕幊倘藛T需要知道一切細(xì)節(jié)，內(nèi)存的大小、被訪問(wèn)數(shù)據(jù)的大小、計(jì)算和數(shù)據(jù)的劃分方法、

27、標(biāo)量計(jì)算速度慢：沒(méi)有數(shù)據(jù)預(yù)取、亂序執(zhí)行等。我猜想這是在RoadRunner中需要AMD處理器的根本原因：支持已有的MPI并行程序 如何編程N(yùn)-body問(wèn)題？(IBM開(kāi)發(fā)的方法：按照空間對(duì)粒子排序，一個(gè)空間的交給一個(gè)處理器，不考慮空間之間的互相作用。如此一來(lái)，粒子排序成為性能瓶頸) 除了MPEG這類計(jì)算，CELL還能在哪地方用？GPGPU能走多遠(yuǎn)？ 現(xiàn)在急需回答這個(gè)問(wèn)題 IBM已經(jīng)放棄CELL，GPU會(huì)面臨同樣的困境嗎？,多核處理器： Intel Core 2,CACHE數(shù)據(jù)存取：完全屏蔽數(shù)據(jù)訪問(wèn)細(xì)節(jié)，CACHE的命中率成為關(guān)鍵 運(yùn)行兩個(gè)無(wú)關(guān)的進(jìn)程 涉及的數(shù)據(jù)都?。夯ハ鄾](méi)有影響 兩個(gè)進(jìn)程分別對(duì)一

28、棵大的樹(shù)進(jìn)行搜索，串行執(zhí)行兩個(gè)進(jìn)程與并發(fā)執(zhí)行兩個(gè)進(jìn)程：哪個(gè)更快？要協(xié)商對(duì)cache與系統(tǒng)內(nèi)存之間系統(tǒng)總線的占用 已經(jīng)遇到一個(gè)應(yīng)用：對(duì)一個(gè)大的數(shù)組進(jìn)行變換 確定數(shù)組A的元素值A(chǔ)I，J：產(chǎn)生兩個(gè)隨機(jī)數(shù)X，Y，將BX，Y賦值給AI，J 使用串行程序要比并行程序更快,執(zhí)行核,cache,系統(tǒng)內(nèi)存,SMP,存儲(chǔ)一致性問(wèn)題 我在本課程的實(shí)驗(yàn)中，對(duì)N-body問(wèn)題測(cè)試 計(jì)算任務(wù)直接更新全局空間的數(shù)據(jù)，并行程序更慢：同步開(kāi)銷 更適合計(jì)算松耦合問(wèn)題。耦合：進(jìn)程/線程運(yùn)行過(guò)程中，互相交換數(shù)據(jù)、同步的頻率 (通信)求素?cái)?shù)問(wèn)題：判斷I是否為素?cái)?shù)，需要用到I之前的素?cái)?shù) (同步)a=f(i)求和：任何時(shí)刻，只能有一個(gè)進(jìn)程

29、/線程在閱讀、修改變量a 程序員要設(shè)法避免頻繁的同步,cluster,適合計(jì)算松耦合問(wèn)題、問(wèn)題要有一定的復(fù)雜度 程序員劃分計(jì)算任務(wù)、數(shù)據(jù) 確定數(shù)據(jù)的交換和同步 當(dāng)前最主要的超級(jí)計(jì)算機(jī)結(jié)構(gòu)，其成功與MPI (message passing interface)這一并行編程模式分不開(kāi) 能夠占用一臺(tái)超級(jí)計(jì)算機(jī)全部CPU的應(yīng)用很少,網(wǎng)絡(luò)計(jì)算環(huán)境(Grid/Cloud),訪問(wèn)網(wǎng)絡(luò)中的某臺(tái)超級(jí)計(jì)算機(jī)：當(dāng)前主要的模式 EGEE希望幫助用戶選擇需要訪問(wèn)的超級(jí)計(jì)算機(jī) 不適合計(jì)算松耦合問(wèn)題：計(jì)算無(wú)耦合問(wèn)題不錯(cuò)，我們做了這方面的工作 網(wǎng)格剛興起的時(shí)候，很多人嘗試在網(wǎng)絡(luò)環(huán)境運(yùn)行MPI程序，效果很不理想 計(jì)算的問(wèn)題要足

30、夠復(fù)雜：通信-計(jì)算比,并行技術(shù)的使用離不開(kāi)人的參與,需要人根據(jù)問(wèn)題特征發(fā)現(xiàn)并行性、選擇計(jì)算平臺(tái) 需要人根據(jù)計(jì)算平臺(tái)劃分計(jì)算任務(wù)、優(yōu)化數(shù)據(jù)存取效率 在基于Cache的多核處理器上，計(jì)算任務(wù)的粒度要考慮Cache的命中率 在網(wǎng)絡(luò)計(jì)算環(huán)境上，計(jì)算任務(wù)的粒度要到批作業(yè)級(jí)才合適 看幾個(gè)問(wèn)題 求素?cái)?shù)問(wèn)題：如何并行 N-body問(wèn)題：如何減少同步、維護(hù)數(shù)據(jù)一致性 物體間的萬(wàn)有引力定律，促使粒子的運(yùn)動(dòng) 規(guī)則的大數(shù)組計(jì)算：C語(yǔ)言中以行優(yōu)先訪問(wèn)、Fortran語(yǔ)言中以列優(yōu)先訪問(wèn)可以提高數(shù)據(jù)的存取效率，在基于Cache的多核處理器平臺(tái)上，這個(gè)將更重要,并行算法的設(shè)計(jì)問(wèn)題,從串行算法出發(fā)，尋找能夠并行的循環(huán) 串型程序

31、自動(dòng)并行化的思路，實(shí)踐表明不理想 串行算法本身常常沒(méi)有體現(xiàn)問(wèn)題的并行性、或者隱藏了數(shù)學(xué)/物理模型中的并行性 求素?cái)?shù)問(wèn)題 并行算法的設(shè)計(jì)實(shí)現(xiàn)要考慮計(jì)算平臺(tái)：以我們做的大規(guī)?；蚪M可變剪接問(wèn)題為例 問(wèn)題域中有幾萬(wàn)個(gè)互相獨(dú)立的批作業(yè) 在SMP/(有NFS、PFS支持的)cluster環(huán)境上：每個(gè)批作業(yè)作為一個(gè)任務(wù) 在網(wǎng)絡(luò)計(jì)算環(huán)境上，要把幾百個(gè)、甚至幾千個(gè)批作業(yè)合并成一個(gè)子任務(wù)才會(huì)有效：這方面國(guó)際上已經(jīng)有些類似的工作,新的軟件危機(jī)？,軟件危機(jī)：與軟件消耗的計(jì)算能力相比，硬件提供的計(jì)算能力過(guò)剩 20世紀(jì)60、70年代，計(jì)算機(jī)的能力已經(jīng)比50年代有巨大進(jìn)步 計(jì)算機(jī)的應(yīng)用領(lǐng)域已經(jīng)不只是在核武器計(jì)算 人們使用

32、匯編語(yǔ)言編寫程序：程序員少、生產(chǎn)效率低 難題：如何開(kāi)發(fā)更多的軟件 解決 高級(jí)語(yǔ)言和編譯技術(shù)，屏蔽計(jì)算任務(wù)到硬件設(shè)備的映射：Fortran、C 操作系統(tǒng)技術(shù)，屏蔽硬件的實(shí)現(xiàn)和操作細(xì)節(jié)：軟件移植、應(yīng)用軟件分時(shí)共享系統(tǒng)資源 編程方法(軟件復(fù)用、可維護(hù)、可擴(kuò)充)：結(jié)構(gòu)化、面向?qū)ο?今天的情形,計(jì)算能力過(guò)剩 Intel、AMD、IBM都在力推多核處理器 網(wǎng)絡(luò)已經(jīng)不只是交流信息，在P2P方面事實(shí)上已經(jīng)成為計(jì)算平臺(tái) 應(yīng)用程序主要是串行的 編寫并行程序是少數(shù)人的專利、效率低 需求在擴(kuò)展 網(wǎng)絡(luò)計(jì)算已經(jīng)深入社會(huì)生活的方方面面：支持大量的并發(fā)用戶 科學(xué)工程領(lǐng)域更加依賴高性能計(jì)算技術(shù) 研究工作的深度擴(kuò)展：高精度、大規(guī)

33、模 研究工作的廣度擴(kuò)展：軟件的協(xié)同、數(shù)據(jù)的綜合,在Intel和AMD的多核處理器上：如何開(kāi)發(fā)多個(gè)執(zhí)行核的并行計(jì)算能力 使用C語(yǔ)言：只使用了一個(gè)處理器執(zhí)行核的計(jì)算能力 使用C+pthread：并行算法設(shè)計(jì)、cache的命中率 分別執(zhí)行不同的進(jìn)程：進(jìn)程之間的Cache競(jìng)爭(zhēng) 更進(jìn)一步：如何開(kāi)發(fā)SMP服務(wù)器、CLUSTER、網(wǎng)絡(luò)計(jì)算環(huán)境的并行能力？,多核的硬件時(shí)代已經(jīng)到來(lái),采用的多核技術(shù)，CPU的運(yùn)算速度繼續(xù)按照Moore定律增長(zhǎng) 18個(gè)月，運(yùn)算速度增長(zhǎng)一倍 一塊芯片上通用微處理器執(zhí)行核的數(shù)量真的會(huì)很多(比如超過(guò)32)嗎？制造工藝也許允許廠商這么做，但真能從軟件方面發(fā)揮其計(jì)算性能嗎？ 矛盾：最終用戶體

34、驗(yàn)到的性能改進(jìn)極其有限 多核的存儲(chǔ)模型是什么？存儲(chǔ)設(shè)備的性能早已成為性能的瓶頸，(我認(rèn)為)也成為決定多核處理器時(shí)代存續(xù)的關(guān)鍵 基于cache？ (我認(rèn)為)至少不能對(duì)程序員完全透明 基于DMA？ (我認(rèn)為)至少不能完全將細(xì)節(jié)交給程序員 一種全新的技術(shù)？我們拭目以待 適合多核時(shí)代的軟件技術(shù)是什么？ 操作系統(tǒng)的理論和技術(shù)需要?jiǎng)?chuàng)新 編譯理論和技術(shù)需要?jiǎng)?chuàng)新 編程語(yǔ)言和模式需要?jiǎng)?chuàng)新,網(wǎng)絡(luò)計(jì)算的時(shí)代已經(jīng)到來(lái),曾經(jīng)，網(wǎng)絡(luò)對(duì)我們而言 快速、廉價(jià)的數(shù)據(jù)交換：FTP 有限的資源共享：TELNET/SSH 快速、廉價(jià)的通信：EMAIL 用低端設(shè)備實(shí)現(xiàn)高性能的計(jì)算：分布式計(jì)算、CLUSTER 今天的網(wǎng)絡(luò)是信息存儲(chǔ)、交流

35、、聚合的平臺(tái) 網(wǎng)頁(yè)搜索、瀏覽 BBS/微博 電子商務(wù) 電子政務(wù) 但我們還希望網(wǎng)絡(luò)是計(jì)算資源、軟件資源、數(shù)據(jù)資源的聚集和共享平臺(tái)：人們象使用今天的大型計(jì)算機(jī)一樣使用網(wǎng)絡(luò)環(huán)境、人人都可以隨時(shí)訪問(wèn) 網(wǎng)格計(jì)算技術(shù)、云計(jì)算技術(shù)、還是其他計(jì)算技術(shù)？,網(wǎng)絡(luò)計(jì)算環(huán)境與超級(jí)計(jì)算機(jī),今天人們對(duì)網(wǎng)絡(luò)計(jì)算環(huán)境的需求，用現(xiàn)有的超級(jí)計(jì)算機(jī)都能夠滿足，但難度要大、成本要高 Google搜索：把所有的服務(wù)器聚集在一起，做一個(gè)集群 出口帶寬要很高 散熱問(wèn)題很大 所有數(shù)據(jù)維護(hù)人員要集中在一起 還未有一個(gè)高性能應(yīng)用，能夠占用RoadRunner/天河一號(hào)A的全部處理器資源 當(dāng)北大CCSE的集群有大量用戶排隊(duì)的時(shí)候，科學(xué)院計(jì)算中心的

36、超級(jí)計(jì)算機(jī)沒(méi)有人使用 北大CCSE集群和科學(xué)院計(jì)算中心的超級(jí)計(jì)算機(jī)都有大量用戶排隊(duì)，但都有一個(gè)處理器空閑，因?yàn)槊總€(gè)用戶的計(jì)算都需要至少兩顆處理器 處于維護(hù)成本等方面因素的考慮，每個(gè)應(yīng)用軟件、數(shù)據(jù)庫(kù)都只會(huì)安裝在數(shù)量有限的幾臺(tái)機(jī)器上,課程目標(biāo)與定位,并行計(jì)算環(huán)境的時(shí)代已經(jīng)到來(lái) 多核處理器、SMP、集群、網(wǎng)絡(luò)計(jì)算環(huán)境 程序開(kāi)發(fā)的目的：提高處理器運(yùn)算單元的利用率，達(dá)到計(jì)算性能提高的目的 未來(lái)的程序開(kāi)發(fā)，是并行程序的開(kāi)發(fā)：我們假定 多核是處理器發(fā)展的必然 網(wǎng)絡(luò)是社會(huì)生活、工程設(shè)計(jì)制造、科學(xué)研究的基本工具 通過(guò)這門課程的學(xué)習(xí)，你成為合格的程序員：開(kāi)發(fā)程序，最大限度發(fā)揮計(jì)算平臺(tái)中處理器運(yùn)算單元的利用率 并行

37、計(jì)算的基本原理：程序運(yùn)行過(guò)程中，除了執(zhí)行數(shù)據(jù)處理語(yǔ)句外，還有哪些事情是必須做的 并行程序開(kāi)發(fā)的基本方法：計(jì)算并行性的挖掘、算法設(shè)計(jì)、實(shí)現(xiàn)優(yōu)化 并行計(jì)算機(jī)的體系結(jié)構(gòu)：工作原理、數(shù)據(jù)存儲(chǔ)與訪問(wèn),教什么？,近10年并行處理技術(shù)研究、推廣應(yīng)用的體會(huì)和認(rèn)識(shí) 把其中積累的應(yīng)用實(shí)例拿來(lái)講，拋棄“教科書(shū)”上的示例 請(qǐng)學(xué)生講他科研工作中面臨的問(wèn)題，幫助他提出解決方案 請(qǐng)同學(xué)們“照貓畫虎” 準(zhǔn)備幾只“貓”：求素?cái)?shù)、N-Body、Laplace等 準(zhǔn)備幾個(gè)“動(dòng)作”：MPI、pthread、CELL上的實(shí)現(xiàn) 觀摩“貓”的表演：樣例并行程序 請(qǐng)同學(xué)們體會(huì)“不要與虎謀皮”：沒(méi)有并行技術(shù)是不行的，但任何技術(shù)都有其局限性 油

38、氣勘探地震數(shù)據(jù)處理，一個(gè)三維數(shù)組的規(guī)模在15GB，雖然現(xiàn)在的處理器速度已經(jīng)很快，在每個(gè)數(shù)組元素上加1，要多久？ 分子化學(xué)運(yùn)動(dòng)過(guò)程模擬，做一個(gè)大分子(幾千個(gè)原子)，一個(gè)時(shí)間步上，有多少次浮點(diǎn)計(jì)算、一個(gè)數(shù)據(jù)要被訪問(wèn)多少次？ N顆共享存儲(chǔ)的處理器，數(shù)據(jù)訪問(wèn)的平均排隊(duì)時(shí)間是多長(zhǎng) N顆分布存儲(chǔ)的處理器，數(shù)據(jù)交換的規(guī)模是多少,教學(xué)方法,結(jié)合具體的并行計(jì)算平臺(tái) CELL處理器、Intel Core 2處理器 SMP服務(wù)器 集群 結(jié)合教員在大規(guī)模科學(xué)工程計(jì)算積累的實(shí)例 生物信息計(jì)算、流體力學(xué)、地質(zhì)運(yùn)動(dòng)過(guò)程模擬、油氣勘探計(jì)算、天體物理、 教員講授 PPT 習(xí)題 電子版參考資料 自編講義：完成一章，在網(wǎng)站發(fā)布一章

39、 同學(xué)們的興趣研究 科研工作中的問(wèn)題 感興趣的高性能/高效能研究前沿,如何教？,以實(shí)例和實(shí)踐為牽引 Intel多核處理器/SMP服務(wù)器：pthread并行技術(shù) 集群：MPI并行技術(shù) CELL處理器：數(shù)據(jù)存儲(chǔ)和訪問(wèn)的原理、實(shí)現(xiàn)機(jī)制，向量并行計(jì)算 N-body：加速比上限 求素?cái)?shù)：計(jì)算并行性的發(fā)現(xiàn) “不求甚解”：“藝術(shù)家”需要“天賦” 并行計(jì)算涉及的計(jì)算機(jī)技術(shù)：操作系統(tǒng)、體系結(jié)構(gòu)、編譯技術(shù)、網(wǎng)絡(luò)通信 有大量的trade-off：負(fù)載均衡與同步通信、重復(fù)計(jì)算與同步通信等 實(shí)際問(wèn)題基本是“一事一議”：沒(méi)有通用的并行算法和模式 “知其然”，然后“知其所以然” 從并行基礎(chǔ)理論出發(fā)，認(rèn)識(shí)并行技術(shù)、分析應(yīng)用需求 運(yùn)用并行基礎(chǔ)理論，解釋并行計(jì)算的現(xiàn)象 “經(jīng)典”也要“與時(shí)俱進(jìn)” 基礎(chǔ)理論：加速比上限、BSP/MPI、計(jì)算-通信比、SPMD/MPMD 教研相長(zhǎng) 及時(shí)取舍:取新技術(shù)(多核技術(shù)/線程技術(shù)),舍未通過(guò)實(shí)踐檢驗(yàn)的技術(shù)(HPF/OpenMP技術(shù)),教學(xué)內(nèi)容,并行計(jì)算的基本概念與基礎(chǔ)理論 并行計(jì)算機(jī)與F