并行程序設(shè)計(jì)

1、并行程序設(shè)計(jì)Parallel Programming什么是并行計(jì)算?通過計(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í)將多條普通指令組裝成“超級(jí)指令”，比如

2、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í)行并行程序中無(wú)關(guān)數(shù)據(jù)運(yùn)算的計(jì)算機(jī)采用向量處理器一條指

3、令完成多個(gè)數(shù)據(jù)單元的處理提供多個(gè)互相獨(dú)立的處理執(zhí)行核:每個(gè)執(zhí)行核分別執(zhí)行自己的指令流多處理器系統(tǒng): Multi-core/SMP/CPU + Coprocessor多計(jì)算機(jī)系統(tǒng): MPP/Cluster/Grid/Cloud并行程序的開發(fā)與并行計(jì)算串行程序程序員串行編譯串行程序串行處理器串行執(zhí)行超標(biāo)量處理器并行執(zhí)行 并行編譯SIMD并行程序SIMD處理器并行執(zhí)行VLIW并行程序VLIW處理器并行執(zhí)行線程并行程序多處理器系統(tǒng)并行執(zhí)行進(jìn)程并行程序多計(jì)算機(jī)系統(tǒng)并行執(zhí)行線程并行程序進(jìn)程并行程序編譯編譯我們一直在不自覺的使用并行計(jì)算技術(shù)來(lái)提升計(jì)算效能當(dāng)前幾乎所有的計(jì)算機(jī)都是并行計(jì)算機(jī)：多核/微處理器內(nèi)多

4、個(gè)執(zhí)行單元/SIMD指令幾乎每個(gè)程序運(yùn)行時(shí)都在執(zhí)行并行計(jì)算：專家們(體系結(jié)構(gòu)/編譯/操作系統(tǒng))一直在替我們做并行技術(shù)的開發(fā)和運(yùn)用指令級(jí)并行: 提高同時(shí)執(zhí)行的指令數(shù)縮短指令流的執(zhí)行時(shí)間程序執(zhí)行效率的提升指令的基本執(zhí)行過程: instruction fetch decode execute memory access write back每個(gè)過程分別是由不同的部件執(zhí)行通過流水, 使得多條指令同時(shí)執(zhí)行, 每條指令分別處于不同的執(zhí)行階段: 依靠pre-fetch/re-order等技術(shù)提供多個(gè)執(zhí)行單元，支持多條指令流水同時(shí)執(zhí)行數(shù)據(jù)級(jí)并行(data-level parallelism)和任務(wù)級(jí)并行(ta

5、sk-level parallelism) : 提高同時(shí)執(zhí)行的線程數(shù)用戶工作效率的提升(同時(shí)做多件事情, 互不耽擱)基本技術(shù)支撐: interrupt/lock/hyper-threading/Cache/virtual memory/disk file: 執(zhí)行一個(gè)線程,總會(huì)發(fā)生數(shù)據(jù)訪問失效為什么要程序員編寫并行程序?并行計(jì)算機(jī): 提升計(jì)算系統(tǒng)計(jì)算潛力的必然趨勢(shì)Frequency wall: 物理上限指令流的執(zhí)行時(shí)間下限Memory wall: CPU與Memory的速度鴻溝指令級(jí)并行的流水深度限制Power wall: P = C (電容/晶體管的數(shù)量) V2 (電壓) F (頻率)單個(gè)芯片

6、的計(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寄存器, 一個(gè)指令周期可處理4個(gè)float數(shù)數(shù)據(jù)級(jí)并行(data-level parallelism)和任務(wù)級(jí)并行(task-level paralleli

7、sm) : 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指令集包括近300條指令, 科學(xué)計(jì)算只需要其中的約80條指令)提高用于數(shù)據(jù)處理的晶體管的比率提高晶體管的利用率可重構(gòu)計(jì)算技術(shù)(FPGA): 由應(yīng)用程序動(dòng)態(tài)將芯片定制成專用協(xié)處理器單個(gè)數(shù)據(jù)處理部件

8、的運(yùn)算速度有上限: frequency wall多核時(shí)代, 計(jì)算平臺(tái)的關(guān)鍵特征: 不是單個(gè)執(zhí)行核的性能提升了, 而是可利用的執(zhí)行核的數(shù)量提升了如何處理更大規(guī)模的問題, 即: 如何在可接受的時(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ì)算能力（處理器的數(shù)量、處理器內(nèi)執(zhí)行核的數(shù)量）內(nèi)存: 容量/訪問速度和帶寬磁盤及IO:容量/訪問速度和帶寬數(shù)據(jù)級(jí)并行(data-level parallelism)和任務(wù)級(jí)并行(task-level paral

9、lelism) 多臺(tái)計(jì)算機(jī)協(xié)作面向領(lǐng)域/應(yīng)用的并行計(jì)算機(jī)/協(xié)處理器(如GPU)/可重構(gòu)計(jì)算(FPGA)編譯技術(shù)/微處理器體系結(jié)構(gòu)技術(shù)不足以開發(fā)并行計(jì)算機(jī)的計(jì)算能力VLIW/superscalar：適合開發(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)性分析問題的數(shù)學(xué)/物理模型設(shè)計(jì)串行算法用串行語(yǔ)言編碼算法例如：尋找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 ) bre

10、ak;primep = i;p+;并行程序設(shè)計(jì)以問題分解為基礎(chǔ), 開發(fā)面向并行計(jì)算機(jī)的程序: 通過多顆處理器協(xié)作、以及挖掘處理器的計(jì)算潛力, 達(dá)到加速數(shù)據(jù)處理的效率和提高問題求解的規(guī)模的目標(biāo)手段挖掘每個(gè)處理器的計(jì)算潛力提供更多的并行線程，避免由于內(nèi)存壁壘等因素導(dǎo)致執(zhí)行單元處于空等待狀態(tài)微指令級(jí)并行(向量計(jì)算), 提高單條指令的數(shù)據(jù)處理量多個(gè)處理器協(xié)作, 分?jǐn)傆?jì)算任務(wù): 縮短每個(gè)指令流的長(zhǎng)度多計(jì)算機(jī)間數(shù)據(jù)劃分: 增加存儲(chǔ)容量目標(biāo)加速數(shù)據(jù)處理的效率提高問題求解的規(guī)模并行程序設(shè)計(jì)(本門課程)關(guān)注: 發(fā)現(xiàn)計(jì)算任務(wù)中無(wú)關(guān)的數(shù)據(jù)運(yùn)算，并利用數(shù)據(jù)運(yùn)算的無(wú)關(guān)性開發(fā)并行計(jì)算機(jī)的計(jì)算能力向量處理器/陣列處理器系統(tǒng)

11、多處理器系統(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/MPPGrid/Cloud大多數(shù)人并沒有多個(gè)執(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): 多

12、線程支持/早先的超線程技術(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í)代的特點(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ì)算性能的提

13、升效果數(shù)據(jù)處理的速度更快可處理的數(shù)據(jù)規(guī)模更大挑戰(zhàn)性問題: 并行程序的可移植性(衡量程序算法/代碼與目標(biāo)平臺(tái)體系結(jié)構(gòu)的緊密程度), 來(lái)自并行計(jì)算平臺(tái)的異構(gòu)性Intel/AMD處理器：CPU + CPUIBM CELL處理器: CPU + Coprocessor多處理器系統(tǒng): SMP / (CPU + Coprocessor) / (CPU + FGPA) 多計(jì)算機(jī)系統(tǒng): Cluster/MPP/Grid/Cloud編程人員：“傻瓜”還是“精英”“傻瓜”：知道語(yǔ)法就夠了，其他事情交給編譯、運(yùn)行支持去做吧“精英”：我能，但只有我能；我能，但我只會(huì)這一點(diǎn)盡管都是面向流媒體計(jì)算CPU中的SSE：SIMD

14、，向量指令GPU：陣列處理器，線程并行編程(CUDA)新軟件危機(jī)硬件上多核、軟件上串行大量的晶體管閑置、使用效率不高主頻的降低，導(dǎo)致性能體驗(yàn)的下降性能，再次成為編程技術(shù)的焦點(diǎn)：線程級(jí)并行對(duì)開發(fā)多核處理器的計(jì)算能力至關(guān)重要性能，依賴“精英”們實(shí)現(xiàn)體系結(jié)構(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è)問題很簡(jiǎn)單時(shí)不能：并行算法設(shè)計(jì)是“藝術(shù)性”、而非“技術(shù)性

15、”的工作。請(qǐng)將一個(gè)求素?cái)?shù)的串行程序并行化吧。并行程序設(shè)計(jì)：少數(shù)人的專利、編程人員的基本要求？?jī)?nèi)容提要課程基本信息對(duì)并行計(jì)算的認(rèn)識(shí)并行計(jì)算的概念并行計(jì)算平臺(tái)并行計(jì)算技術(shù)的使用問題是什么？課程目標(biāo)與定位教學(xué)安排課程相關(guān)信息成績(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ù)問題，結(jié)合課程學(xué)習(xí)，提出并行處理技術(shù)對(duì)該問題的促進(jìn)高性能/高效能/云計(jì)算領(lǐng)域中感興趣的前沿研究方向，結(jié)合課程學(xué)習(xí)，開展調(diào)研，給出該方向

16、的研究進(jìn)展、趨勢(shì)和評(píng)價(jià)期末考試：50分課程網(wǎng)頁(yè)課程歷史與內(nèi)容沿革1999-2002年，李曉明MPI、HPF、OpenMP、并行編譯集群、MPP、SMP2003年開始，余華山2005年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ò)的并行

17、處理(網(wǎng)格)多核、 SMP、集群、MPP、網(wǎng)格2011年：北京大學(xué)研究生課程建設(shè)以出版為目標(biāo)的講義完成一章，在課程網(wǎng)站發(fā)布一章并行程序設(shè)計(jì)的基本概念“并行程序”：支持多個(gè)操作、或者任務(wù)同時(shí)執(zhí)行的一種規(guī)劃做事情，總要規(guī)劃動(dòng)作的順序：確定房子的地址、設(shè)計(jì)結(jié)構(gòu)圖、作預(yù)算、選擇施工者、規(guī)劃施工進(jìn)度、買建筑材料和施工。規(guī)劃的關(guān)鍵是分析問題各個(gè)部分之間的內(nèi)在聯(lián)系，任何規(guī)劃都不能破壞這個(gè)聯(lián)系總有一些部分之間是沒有內(nèi)在聯(lián)系的，可以同時(shí)執(zhí)行：房屋建筑的第一階段施工、購(gòu)買第二階段建筑材料什么是并行程序設(shè)計(jì)：以任務(wù)分解為基礎(chǔ), 開發(fā)面向并行計(jì)算機(jī)的應(yīng)用程序, 以提高數(shù)據(jù)處理的效率、或者提高可解問題的規(guī)模.計(jì)算平臺(tái)：

18、支持同時(shí)執(zhí)行多個(gè)數(shù)據(jù)處理運(yùn)算(提供多個(gè)執(zhí)行核/向量處理器)操作系統(tǒng)：支持多指令流調(diào)度(多核處理器計(jì)算平臺(tái))、或者多數(shù)據(jù)流訪問(向量處理器平臺(tái))編程語(yǔ)言(以及編譯運(yùn)行系統(tǒng))：支持計(jì)算并行性的表達(dá)并行計(jì)算有什么用途并非所有問題都需要使用并行計(jì)算技術(shù)寫WORD文檔、寫C/C+程序代碼一個(gè)字符、一個(gè)字符地從鍵盤輸入即使用最低端的機(jī)器，沒有人感覺到不能及時(shí)得到響應(yīng)(你同時(shí)打開了很多文檔、再邊聽MP3除外)使用Google、Baidu搜索網(wǎng)頁(yè)時(shí)刻都有成千上萬(wàn)的用戶在搜索有興趣嗎？對(duì)比一下從Google、Baidu得到的響應(yīng)速度、在一臺(tái)高端服務(wù)器上模擬100個(gè)用戶搜索1,000,000條記錄的響應(yīng)速度汶川地

19、震研究：反演地震過程，整個(gè)中國(guó)幾乎都有震感震區(qū)離散化，每10個(gè)立方米作為一個(gè)粒子使用當(dāng)今運(yùn)算速度最快的處理器，對(duì)這個(gè)三維數(shù)組做一次最簡(jiǎn)單的運(yùn)算，比如對(duì)每個(gè)元素做一次加法，需要多久？并行程序的時(shí)代已經(jīng)到了？并行計(jì)算：在計(jì)算平臺(tái)上同時(shí)執(zhí)行多個(gè)數(shù)據(jù)運(yùn)算提高計(jì)算的效能提高處理器的計(jì)算潛力提高處理器的利用率提高數(shù)據(jù)處理的速度提高可解問題的規(guī)模并行計(jì)算平臺(tái)隨處可見多核處理器：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)離不開網(wǎng)絡(luò)：成千上萬(wàn)的并發(fā)用戶訪問搜索引擎、新聞

20、網(wǎng)站、通信聊天網(wǎng)站、娛樂視頻網(wǎng)站、多人網(wǎng)絡(luò)游戲、公共服務(wù)網(wǎng)站(圖書館、電子文獻(xiàn)數(shù)據(jù)庫(kù))、電子銀行、電子政務(wù)工程、科研、生活服務(wù)越來(lái)越依賴于大規(guī)模數(shù)據(jù)的高效計(jì)算：飛機(jī)設(shè)計(jì)、汽車碰撞模擬、武器設(shè)計(jì)、油氣勘探、神州飛船跟蹤、基因數(shù)據(jù)分析、地震運(yùn)動(dòng)過程模擬、太陽(yáng)風(fēng)磁場(chǎng)重聯(lián)模擬、三峽大壩選址、氣象預(yù)報(bào)、并行計(jì)算的現(xiàn)狀CPU執(zhí)行程序時(shí)，使用了superscalar/VLIWCPU早就提供了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ì)寫并行程

21、序的人不多一邊寫程序、一邊聽MP3時(shí)，可以用上，但影響編程、不用多核處理器時(shí)計(jì)算能力也夠了SMP (Symmetric Multi Processing )服務(wù)器商業(yè)軟件：開發(fā)了并行能力自己開發(fā)的軟件：以串行程序?yàn)橹髦饕且揽坎僮飨到y(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顆CELLCELL處理器執(zhí)行標(biāo)量計(jì)算程序?qū)⒎浅Ｂ?6912顆AMD Opteron似乎只是為了讓每個(gè)節(jié)

22、點(diǎn)也能夠正常執(zhí)行原來(lái)的標(biāo)量計(jì)算進(jìn)程)天河計(jì)算機(jī)：主要計(jì)算能力來(lái)自GPU2048顆飛騰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)定性問題：一個(gè)部件的出錯(cuò)/故障率是百萬(wàn)分之一，這么多通信、存儲(chǔ)、計(jì)算、及其他輔助部件放在一起，怎么能夠穩(wěn)定運(yùn)行？功耗和散熱問題這臺(tái)機(jī)器本身也許并不是一個(gè)特別值得炫耀的成就有多少支持GPU的軟件？支持GPU的

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

24、rch engine：依靠網(wǎng)絡(luò)計(jì)算環(huán)境支持大規(guī)模并發(fā)用戶云計(jì)算的概念以數(shù)據(jù)為中心，根據(jù)數(shù)據(jù)需求選擇計(jì)算資源并行技術(shù)的應(yīng)用為何不如人意？并行計(jì)算平臺(tái)有其適用范圍并行處理技術(shù)的使用離不開人的參與并行求解算法的設(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)用程序慢：打開一個(gè)PDF、WORD、VC編程環(huán)境、DVD視頻文件、打開很多個(gè)應(yīng)用程序時(shí)，系統(tǒng)響應(yīng)很慢打開一個(gè)大的PDF文件、WORD文件，翻頁(yè)瀏覽時(shí)響應(yīng)慢如何提高性能:CPU的計(jì)算能力按照moore定律成長(zhǎng)，你體驗(yàn)的

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

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

27、個(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ǔ)一致性問題我在本課程的實(shí)驗(yàn)中，對(duì)N-body問題測(cè)試計(jì)算任務(wù)直接更新全局空間的數(shù)據(jù)，并行程序更慢：同步開銷更適合計(jì)算松耦合問題。耦合：進(jìn)程/線程運(yùn)行過程中，互相交換數(shù)據(jù)、同步的頻率(通信)求素?cái)?shù)問題：判斷I是否為素?cái)?shù)，需要用到I之前的素?cái)?shù)(同步)a=f(i)求和：任何時(shí)刻，只能有一個(gè)進(jìn)程/線程在閱讀、修改變量a程序員要設(shè)法避免頻繁的同步cluster適合計(jì)算松耦合問題

28、、問題要有一定的復(fù)雜度程序員劃分計(jì)算任務(wù)、數(shù)據(jù)確定數(shù)據(jù)的交換和同步當(dāng)前最主要的超級(jí)計(jì)算機(jī)結(jié)構(gòu)，其成功與MPI (message passing interface)這一并行編程模式分不開能夠占用一臺(tái)超級(jí)計(jì)算機(jī)全部CPU的應(yīng)用很少網(wǎng)絡(luò)計(jì)算環(huán)境(Grid/Cloud)訪問網(wǎng)絡(luò)中的某臺(tái)超級(jí)計(jì)算機(jī)：當(dāng)前主要的模式EGEE希望幫助用戶選擇需要訪問的超級(jí)計(jì)算機(jī)不適合計(jì)算松耦合問題：計(jì)算無(wú)耦合問題不錯(cuò)，我們做了這方面的工作網(wǎng)格剛興起的時(shí)候，很多人嘗試在網(wǎng)絡(luò)環(huán)境運(yùn)行MPI程序，效果很不理想計(jì)算的問題要足夠復(fù)雜：通信-計(jì)算比并行技術(shù)的使用離不開人的參與需要人根據(jù)問題特征發(fā)現(xiàn)并行性、選擇計(jì)算平臺(tái)需要人根據(jù)計(jì)算平臺(tái)

29、劃分計(jì)算任務(wù)、優(yōu)化數(shù)據(jù)存取效率在基于Cache的多核處理器上，計(jì)算任務(wù)的粒度要考慮Cache的命中率在網(wǎng)絡(luò)計(jì)算環(huán)境上，計(jì)算任務(wù)的粒度要到批作業(yè)級(jí)才合適看幾個(gè)問題求素?cái)?shù)問題：如何并行N-body問題：如何減少同步、維護(hù)數(shù)據(jù)一致性物體間的萬(wàn)有引力定律，促使粒子的運(yùn)動(dòng)規(guī)則的大數(shù)組計(jì)算：C語(yǔ)言中以行優(yōu)先訪問、Fortran語(yǔ)言中以列優(yōu)先訪問可以提高數(shù)據(jù)的存取效率，在基于Cache的多核處理器平臺(tái)上，這個(gè)將更重要并行算法的設(shè)計(jì)問題從串行算法出發(fā)，尋找能夠并行的循環(huán)串型程序自動(dòng)并行化的思路，實(shí)踐表明不理想串行算法本身常常沒有體現(xiàn)問題的并行性、或者隱藏了數(shù)學(xué)/物理模型中的并行性求素?cái)?shù)問題并行算法的設(shè)計(jì)實(shí)現(xiàn)要

30、考慮計(jì)算平臺(tái)：以我們做的大規(guī)模基因組可變剪接問題為例問題域中有幾萬(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ì)算能力過剩20世紀(jì)60、70年代，計(jì)算機(jī)的能力已經(jīng)比50年代有巨大進(jìn)步計(jì)算機(jī)的應(yīng)用領(lǐng)域已經(jīng)不只是在核武器計(jì)算人們使用匯編語(yǔ)言編寫程序：程序員少、生產(chǎn)效率低難題：如何開發(fā)更多的軟件解決高級(jí)語(yǔ)言和編譯技術(shù)，屏蔽計(jì)算任務(wù)到硬件設(shè)備的映射：Fortran、C操作系統(tǒng)技術(shù)，屏蔽硬件

31、的實(shí)現(xiàn)和操作細(xì)節(jié)：軟件移植、應(yīng)用軟件分時(shí)共享系統(tǒng)資源編程方法(軟件復(fù)用、可維護(hù)、可擴(kuò)充)：結(jié)構(gòu)化、面向?qū)ο蠼裉斓那樾斡?jì)算能力過剩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ī)模研究工作的廣度擴(kuò)展：軟件的協(xié)同、數(shù)據(jù)的綜合匯編語(yǔ)言寫串行程序C語(yǔ)言寫CELL處理器程序CPU操作寄存器數(shù)據(jù)，編程人員負(fù)責(zé)寄存器與內(nèi)存數(shù)據(jù)的交換SPU操作局部?jī)?nèi)存數(shù)據(jù)，編程人員負(fù)責(zé)局部?jī)?nèi)

32、存與全局內(nèi)存的數(shù)據(jù)交換編程人員將計(jì)算任務(wù)分解到指令，規(guī)劃指令的執(zhí)行次序編程人員將計(jì)算任務(wù)分解到SPU的粒度(代碼和數(shù)據(jù)的規(guī)模不超過256KB)，規(guī)劃子任務(wù)的并發(fā)關(guān)系以BYTE為數(shù)據(jù)存取的基本單位以128BTYE(SPU寄存器大小)為數(shù)據(jù)存取的基本單位在Intel和AMD的多核處理器上：如何開發(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)一步：如何開發(fā)SMP服務(wù)器、CLUSTER、網(wǎng)絡(luò)計(jì)算環(huán)境的并行能力？多核的硬件時(shí)代已經(jīng)到來(lái)采用的多核技術(shù)，CPU的運(yùn)算速度繼續(xù)按照M

33、oore定律增長(zhǎng)18個(gè)月，運(yùn)算速度增長(zhǎng)一倍一塊芯片上通用微處理器執(zhí)行核的數(shù)量真的會(huì)很多(比如超過32)嗎？制造工藝也許允許廠商這么做，但真能從軟件方面發(fā)揮其計(jì)算性能嗎？矛盾：最終用戶體驗(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ù)交

34、換：FTP有限的資源共享：TELNET/SSH快速、廉價(jià)的通信：EMAIL用低端設(shè)備實(shí)現(xiàn)高性能的計(jì)算：分布式計(jì)算、CLUSTER今天的網(wǎng)絡(luò)是信息存儲(chǔ)、交流、聚合的平臺(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ǎ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è)集群出口帶寬要很高散熱問題很大所有數(shù)據(jù)維護(hù)人員要集中在一起還未有一個(gè)

35、高性能應(yīng)用，能夠占用RoadRunner/天河一號(hào)A的全部處理器資源當(dāng)北大CCSE的集群有大量用戶排隊(duì)的時(shí)候，科學(xué)院計(jì)算中心的超級(jí)計(jì)算機(jī)沒有人使用北大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)境程序開發(fā)的目的：提高處理器運(yùn)算單元的利用率，達(dá)到計(jì)算性能提高的目的未來(lái)的程序開發(fā)，是并行程序的開發(fā)：我們假定多核是處理器發(fā)展的必然網(wǎng)絡(luò)是社會(huì)生活、工程設(shè)計(jì)制造、科學(xué)研究的基

36、本工具通過這門課程的學(xué)習(xí)，你成為合格的程序員：開發(fā)程序，最大限度發(fā)揮計(jì)算平臺(tái)中處理器運(yùn)算單元的利用率并行計(jì)算的基本原理：程序運(yùn)行過程中，除了執(zhí)行數(shù)據(jù)處理語(yǔ)句外，還有哪些事情是必須做的并行程序開發(fā)的基本方法：計(jì)算并行性的挖掘、算法設(shè)計(jì)、實(shí)現(xiàn)優(yōu)化并行計(jì)算機(jī)的體系結(jié)構(gòu)：工作原理、數(shù)據(jù)存儲(chǔ)與訪問教什么？近10年并行處理技術(shù)研究、推廣應(yīng)用的體會(huì)和認(rèn)識(shí)把其中積累的應(yīng)用實(shí)例拿來(lái)講，拋棄“教科書”上的示例請(qǐng)學(xué)生講他科研工作中面臨的問題，幫助他提出解決方案請(qǐng)同學(xué)們“照貓畫虎”準(zhǔn)備幾只“貓”：求素?cái)?shù)、N-Body、Laplace等準(zhǔn)備幾個(gè)“動(dòng)作”：MPI、pthread、CELL上的實(shí)現(xiàn)觀摩“貓”的表演：樣例并行

37、程序請(qǐng)同學(xué)們體會(huì)“不要與虎謀皮”：沒有并行技術(shù)是不行的，但任何技術(shù)都有其局限性油氣勘探地震數(shù)據(jù)處理，一個(gè)三維數(shù)組的規(guī)模在15GB，雖然現(xiàn)在的處理器速度已經(jīng)很快，在每個(gè)數(shù)組元素上加1，要多久？分子化學(xué)運(yùn)動(dòng)過程模擬，做一個(gè)大分子(幾千個(gè)原子)，一個(gè)時(shí)間步上，有多少次浮點(diǎn)計(jì)算、一個(gè)數(shù)據(jù)要被訪問多少次？N顆共享存儲(chǔ)的處理器，數(shù)據(jù)訪問的平均排隊(duì)時(shí)間是多長(zhǎng)N顆分布存儲(chǔ)的處理器，數(shù)據(jù)交換的規(guī)模是多少教學(xué)方法結(jié)合具體的并行計(jì)算平臺(tái)CELL處理器、Intel Core 2處理器SMP服務(wù)器集群結(jié)合教員在大規(guī)?？茖W(xué)工程計(jì)算積累的實(shí)例生物信息計(jì)算、流體力學(xué)、地質(zhì)運(yùn)動(dòng)過程模擬、油氣勘探計(jì)算、天體物理、 教員講授PPT

38、習(xí)題電子版參考資料自編講義：完成一章，在網(wǎng)站發(fā)布一章同學(xué)們的興趣研究科研工作中的問題感興趣的高性能/高效能研究前沿如何教？以實(shí)例和實(shí)踐為牽引Intel多核處理器/SMP服務(wù)器：pthread并行技術(shù)集群：MPI并行技術(shù)CELL處理器：數(shù)據(jù)存儲(chǔ)和訪問的原理、實(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í)際問題基本是“一事一議”：沒有通用的并行算法和模式“知其然”，然后“知其所以然”從并行基礎(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ù)),舍未通過實(shí)踐檢驗(yàn)的技術(shù)(HPF/OpenMP技術(shù))教學(xué)內(nèi)容 并行計(jì)算的基本概念與基礎(chǔ)理論并