并行程序設(shè)計

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

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

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

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

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

6、的計算潛力上限Multi-core: 提升單個芯片計算潛力的必然選擇, 保持Moores law: 增加執(zhí)行核(用于數(shù)據(jù)運算的晶體管的數(shù)量),降低主頻提高用于數(shù)據(jù)運算的晶體管的比率: 降低指令級并行的流水深度提高晶體管的利用率: 執(zhí)行核之間按需共享cache/FBI挖掘處理器的計算潛力: 提高芯片內(nèi)用于數(shù)據(jù)處理的晶體管的比率微指令級并行(SIMD): 提高計算機的字長一次解碼, 處理更多的數(shù)據(jù)例如core微處理器的SSE指令采用128bit寄存器, 一個指令周期可處理4個float數(shù)數(shù)據(jù)級并行(data-level parallelism)和任務(wù)級并行(task-level paralleli

7、sm) : multi-core, 支持多個指令流同時處于數(shù)據(jù)運算階段如何提高數(shù)據(jù)處理的效率: 利用多個執(zhí)行核分?jǐn)倲?shù)據(jù)處理任務(wù)指令級并行/提高主頻: 縮短指令流的執(zhí)行時間并行程序:縮短指令流的長度數(shù)據(jù)級并行/任務(wù)級并行: 同時執(zhí)行多個短的指令流向量計算: 提高單條指令的數(shù)據(jù)處理量處理器的主導(dǎo)技術(shù)已由提高處理器主頻轉(zhuǎn)向多核技術(shù)多核技術(shù)指令流的執(zhí)行時間延長了同時執(zhí)行的指令流數(shù)量增加了專用協(xié)處理器技術(shù)(X86指令集包括近300條指令, 科學(xué)計算只需要其中的約80條指令)提高用于數(shù)據(jù)處理的晶體管的比率提高晶體管的利用率可重構(gòu)計算技術(shù)(FPGA): 由應(yīng)用程序動態(tài)將芯片定制成專用協(xié)處理器單個數(shù)據(jù)處理部件

8、的運算速度有上限: frequency wall多核時代, 計算平臺的關(guān)鍵特征: 不是單個執(zhí)行核的性能提升了, 而是可利用的執(zhí)行核的數(shù)量提升了如何處理更大規(guī)模的問題, 即: 如何在可接受的時間里完成更大規(guī)模數(shù)據(jù)的處理? 例如電信計費網(wǎng)絡(luò)搜索視頻點播地震現(xiàn)象反演: 有限元法, 地震區(qū)域的10m10m10m作為一個粒子, 模擬這些粒子在地震前后的運動軌跡一臺計算機的服務(wù)能力有上限：處理器: 計算能力（處理器的數(shù)量、處理器內(nèi)執(zhí)行核的數(shù)量）內(nèi)存: 容量/訪問速度和帶寬磁盤及IO:容量/訪問速度和帶寬數(shù)據(jù)級并行(data-level parallelism)和任務(wù)級并行(task-level paral

9、lelism) 多臺計算機協(xié)作面向領(lǐng)域/應(yīng)用的并行計算機/協(xié)處理器(如GPU)/可重構(gòu)計算(FPGA)編譯技術(shù)/微處理器體系結(jié)構(gòu)技術(shù)不足以開發(fā)并行計算機的計算能力VLIW/superscalar：適合開發(fā)微處理器內(nèi)部各個執(zhí)行單元的并行能力編譯技術(shù)：發(fā)現(xiàn)串行程序中無關(guān)的數(shù)據(jù)運算串行程序：隱藏了計算任務(wù)的數(shù)據(jù)運算無關(guān)性分析問題的數(shù)學(xué)/物理模型設(shè)計串行算法用串行語言編碼算法例如：尋找N以內(nè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è)計以問題分解為基礎(chǔ), 開發(fā)面向并行計算機的程序: 通過多顆處理器協(xié)作、以及挖掘處理器的計算潛力, 達到加速數(shù)據(jù)處理的效率和提高問題求解的規(guī)模的目標(biāo)手段挖掘每個處理器的計算潛力提供更多的并行線程，避免由于內(nèi)存壁壘等因素導(dǎo)致執(zhí)行單元處于空等待狀態(tài)微指令級并行(向量計算), 提高單條指令的數(shù)據(jù)處理量多個處理器協(xié)作, 分?jǐn)傆嬎闳蝿?wù): 縮短每個指令流的長度多計算機間數(shù)據(jù)劃分: 增加存儲容量目標(biāo)加速數(shù)據(jù)處理的效率提高問題求解的規(guī)模并行程序設(shè)計(本門課程)關(guān)注: 發(fā)現(xiàn)計算任務(wù)中無關(guān)的數(shù)據(jù)運算，并利用數(shù)據(jù)運算的無關(guān)性開發(fā)并行計算機的計算能力向量處理器/陣列處理器系統(tǒng)

11、多處理器系統(tǒng)多計算機系統(tǒng)多核時代：當(dāng)多核處理器給用戶相應(yīng)提高的性能體驗時，才真正到了多核時代計算平臺可為程序的運行提供多個執(zhí)行核多核時代不等于多核處理器時代如何獲得多個執(zhí)行核?多核處理器SMP/CPU + Coprocessor(專用協(xié)處理器/FPGA)Cluster/MPPGrid/Cloud大多數(shù)人并沒有多個執(zhí)行核協(xié)同計算(并行計算)的體會計算機專業(yè)的整個本科教學(xué)，都是基于Von Neumann， 僅在操作系統(tǒng)、體系結(jié)構(gòu)里提到一點并行和并發(fā)的概念使用的應(yīng)用軟件也基本是基于串行技術(shù): 對計算性能的體驗并未改進, 甚至有所下降串行程序+降低了主頻和指令流水深度的多核處理器更復(fù)雜的操作系統(tǒng): 多

12、線程支持/早先的超線程技術(shù)操作系統(tǒng)程序與用戶程序同時運行: Cache、FBI的瓶頸效應(yīng)可以在一臺機器上同時運行幾個程序: 多核處理器之前已經(jīng)如此操作系統(tǒng)的多進程/多線程/超線程支持技術(shù)用于超級計算機(Cluster/MPP)的HTC (high-throughput computing)多核時代的特點已經(jīng)具備的特點: 并行計算機不再與“昂貴”、“高性能”有必然聯(lián)系，從體系結(jié)構(gòu)上看，我們所使用的都是并行計算機支持SSE的多核CPU+GPU(每個GPU是一個微處理器陣列)CPU的微處理器內(nèi)核包括多個執(zhí)行單元，采用了superscalar/VLIW技術(shù)尚不具備的特點: 體驗并行計算機對計算性能的提

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

14、，向量指令GPU：陣列處理器，線程并行編程(CUDA)新軟件危機硬件上多核、軟件上串行大量的晶體管閑置、使用效率不高主頻的降低，導(dǎo)致性能體驗的下降性能，再次成為編程技術(shù)的焦點：線程級并行對開發(fā)多核處理器的計算能力至關(guān)重要性能，依賴“精英”們實現(xiàn)體系結(jié)構(gòu)的特征數(shù)學(xué)/物理模型中的計算并行性特征并行算法編寫程序：既要做“經(jīng)理”，又要做“業(yè)務(wù)員”“業(yè)務(wù)員”：完成數(shù)據(jù)處理“經(jīng)理”：“業(yè)務(wù)員”的分工、協(xié)調(diào)(在單核處理器時代，可以由編譯技術(shù)/微處理器體系結(jié)構(gòu)技術(shù)自動解決)能以來自動機理論(運行時支持) 、形式化理論(編譯技術(shù))代替“精英”嗎？能：當(dāng)這個問題很簡單時不能：并行算法設(shè)計是“藝術(shù)性”、而非“技術(shù)性

15、”的工作。請將一個求素數(shù)的串行程序并行化吧。并行程序設(shè)計：少數(shù)人的專利、編程人員的基本要求？內(nèi)容提要課程基本信息對并行計算的認(rèn)識并行計算的概念并行計算平臺并行計算技術(shù)的使用問題是什么？課程目標(biāo)與定位教學(xué)安排課程相關(guān)信息成績評定：平時成績(50%)+ max興趣研究報告，期末筆試平時練習(xí)、編程實驗: 50分興趣研究報告：50分。1-3人一組，自選題目，題目來源：所在研究組面臨的計算性能需求，結(jié)合課程學(xué)習(xí)，提出解決方案所在課題組正在解決的計算性能/計算效能方面的技術(shù)問題，結(jié)合課程學(xué)習(xí)，提出并行處理技術(shù)對該問題的促進高性能/高效能/云計算領(lǐng)域中感興趣的前沿研究方向，結(jié)合課程學(xué)習(xí)，開展調(diào)研，給出該方向

16、的研究進展、趨勢和評價期末考試：50分課程網(wǎng)頁課程歷史與內(nèi)容沿革1999-2002年，李曉明MPI、HPF、OpenMP、并行編譯集群、MPP、SMP2003年開始，余華山2005年MPI、OpenMP、并行算法設(shè)計與應(yīng)用實例、基于網(wǎng)絡(luò)的并行處理集群、MPP、SMP、網(wǎng)格2007年：教育部-Intel精品課程建設(shè)項目MPI、pthread與Intel多核技術(shù)、并行算法設(shè)計與應(yīng)用實例、 OpenMP、基于網(wǎng)絡(luò)的并行處理多核、 SMP、集群、MPP、網(wǎng)格2008年：教育部-IBM精品課程建設(shè)項目pthread與Intel多核技術(shù)、CELL BE技術(shù)、 MPI、并行算法設(shè)計與應(yīng)用實例、基于網(wǎng)絡(luò)的并行

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

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

19、震研究：反演地震過程，整個中國幾乎都有震感震區(qū)離散化，每10個立方米作為一個粒子使用當(dāng)今運算速度最快的處理器，對這個三維數(shù)組做一次最簡單的運算，比如對每個元素做一次加法，需要多久？并行程序的時代已經(jīng)到了？并行計算：在計算平臺上同時執(zhí)行多個數(shù)據(jù)運算提高計算的效能提高處理器的計算潛力提高處理器的利用率提高數(shù)據(jù)處理的速度提高可解問題的規(guī)模并行計算平臺隨處可見多核處理器：PC機、筆記本SMP：服務(wù)器Cluster：大型計算中心服務(wù)器網(wǎng)絡(luò)計算環(huán)境：CN Grid、China Grid、TeraGrid、Google？并行程序的需求來自各個領(lǐng)域我們的生活已經(jīng)離不開網(wǎng)絡(luò)：成千上萬的并發(fā)用戶訪問搜索引擎、新聞

20、網(wǎng)站、通信聊天網(wǎng)站、娛樂視頻網(wǎng)站、多人網(wǎng)絡(luò)游戲、公共服務(wù)網(wǎng)站(圖書館、電子文獻數(shù)據(jù)庫)、電子銀行、電子政務(wù)工程、科研、生活服務(wù)越來越依賴于大規(guī)模數(shù)據(jù)的高效計算：飛機設(shè)計、汽車碰撞模擬、武器設(shè)計、油氣勘探、神州飛船跟蹤、基因數(shù)據(jù)分析、地震運動過程模擬、太陽風(fēng)磁場重聯(lián)模擬、三峽大壩選址、氣象預(yù)報、并行計算的現(xiàn)狀CPU執(zhí)行程序時，使用了superscalar/VLIWCPU早就提供了SIMD支持，從MMX到現(xiàn)在的SSE4。一些商業(yè)軟件使用了SIMD一些函數(shù)包使用了SIMD一些編譯器在對循環(huán)優(yōu)化時使用了SIMD程序員使用了嗎？誰在用桌面機的多核處理器計算能力？桌面機上的應(yīng)用以串行程序為主自己會寫并行程

21、序的人不多一邊寫程序、一邊聽MP3時，可以用上，但影響編程、不用多核處理器時計算能力也夠了SMP (Symmetric Multi Processing )服務(wù)器商業(yè)軟件：開發(fā)了并行能力自己開發(fā)的軟件：以串行程序為主主要是依靠操作系統(tǒng)支持多個進程/線程的同時執(zhí)行能同時使用成百上千顆處理器的應(yīng)用有多少?集群上的并行計算情況：以CCSE128節(jié)點使用情況為例(2006年3月)3309個計算任務(wù)平均使用1.85個計算節(jié)點節(jié)點資源利用率94.7%IBM RoadRunner哪個應(yīng)用能同時使用12960顆CELLCELL處理器執(zhí)行標(biāo)量計算程序?qū)⒎浅Ｂ?6912顆AMD Opteron似乎只是為了讓每個節(jié)

22、點也能夠正常執(zhí)行原來的標(biāo)量計算進程)天河計算機：主要計算能力來自GPU2048顆飛騰FT-1000八核心處理器 14336顆Intel Xeon X5670 2.93GHz六核心處理器 7168塊NVIDIA Tesla M2050高性能計算卡(GPU)如何看待我國的天河一號A？這是一個了不起的成就：2萬多顆處理器放在一起，并讓它們一起協(xié)作，采用LU分解的方法求解一個密集矩陣的方程通信問題穩(wěn)定性問題：一個部件的出錯/故障率是百萬分之一，這么多通信、存儲、計算、及其他輔助部件放在一起，怎么能夠穩(wěn)定運行？功耗和散熱問題這臺機器本身也許并不是一個特別值得炫耀的成就有多少支持GPU的軟件？支持GPU的

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

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

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

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

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

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

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

30、考慮計算平臺：以我們做的大規(guī)?；蚪M可變剪接問題為例問題域中有幾萬個互相獨立的批作業(yè)在SMP/(有NFS、PFS支持的)cluster環(huán)境上：每個批作業(yè)作為一個任務(wù)在網(wǎng)絡(luò)計算環(huán)境上，要把幾百個、甚至幾千個批作業(yè)合并成一個子任務(wù)才會有效：這方面國際上已經(jīng)有些類似的工作新的軟件危機？軟件危機：與軟件消耗的計算能力相比，硬件提供的計算能力過剩20世紀(jì)60、70年代，計算機的能力已經(jīng)比50年代有巨大進步計算機的應(yīng)用領(lǐng)域已經(jīng)不只是在核武器計算人們使用匯編語言編寫程序：程序員少、生產(chǎn)效率低難題：如何開發(fā)更多的軟件解決高級語言和編譯技術(shù)，屏蔽計算任務(wù)到硬件設(shè)備的映射：Fortran、C操作系統(tǒng)技術(shù)，屏蔽硬件

31、的實現(xiàn)和操作細節(jié)：軟件移植、應(yīng)用軟件分時共享系統(tǒng)資源編程方法(軟件復(fù)用、可維護、可擴充)：結(jié)構(gòu)化、面向?qū)ο蠼裉斓那樾斡嬎隳芰^剩Intel、AMD、IBM都在力推多核處理器網(wǎng)絡(luò)已經(jīng)不只是交流信息，在P2P方面事實上已經(jīng)成為計算平臺應(yīng)用程序主要是串行的編寫并行程序是少數(shù)人的專利、效率低需求在擴展網(wǎng)絡(luò)計算已經(jīng)深入社會生活的方方面面：支持大量的并發(fā)用戶科學(xué)工程領(lǐng)域更加依賴高性能計算技術(shù)研究工作的深度擴展：高精度、大規(guī)模研究工作的廣度擴展：軟件的協(xié)同、數(shù)據(jù)的綜合匯編語言寫串行程序C語言寫CELL處理器程序CPU操作寄存器數(shù)據(jù)，編程人員負(fù)責(zé)寄存器與內(nèi)存數(shù)據(jù)的交換SPU操作局部內(nèi)存數(shù)據(jù)，編程人員負(fù)責(zé)局部內(nèi)

32、存與全局內(nèi)存的數(shù)據(jù)交換編程人員將計算任務(wù)分解到指令，規(guī)劃指令的執(zhí)行次序編程人員將計算任務(wù)分解到SPU的粒度(代碼和數(shù)據(jù)的規(guī)模不超過256KB)，規(guī)劃子任務(wù)的并發(fā)關(guān)系以BYTE為數(shù)據(jù)存取的基本單位以128BTYE(SPU寄存器大小)為數(shù)據(jù)存取的基本單位在Intel和AMD的多核處理器上：如何開發(fā)多個執(zhí)行核的并行計算能力使用C語言：只使用了一個處理器執(zhí)行核的計算能力使用C+pthread：并行算法設(shè)計、cache的命中率分別執(zhí)行不同的進程：進程之間的Cache競爭更進一步：如何開發(fā)SMP服務(wù)器、CLUSTER、網(wǎng)絡(luò)計算環(huán)境的并行能力？多核的硬件時代已經(jīng)到來采用的多核技術(shù)，CPU的運算速度繼續(xù)按照M

33、oore定律增長18個月，運算速度增長一倍一塊芯片上通用微處理器執(zhí)行核的數(shù)量真的會很多(比如超過32)嗎？制造工藝也許允許廠商這么做，但真能從軟件方面發(fā)揮其計算性能嗎？矛盾：最終用戶體驗到的性能改進極其有限多核的存儲模型是什么？存儲設(shè)備的性能早已成為性能的瓶頸，(我認(rèn)為)也成為決定多核處理器時代存續(xù)的關(guān)鍵基于cache？ (我認(rèn)為)至少不能對程序員完全透明基于DMA？ (我認(rèn)為)至少不能完全將細節(jié)交給程序員一種全新的技術(shù)？我們拭目以待適合多核時代的軟件技術(shù)是什么？操作系統(tǒng)的理論和技術(shù)需要創(chuàng)新編譯理論和技術(shù)需要創(chuàng)新編程語言和模式需要創(chuàng)新網(wǎng)絡(luò)計算的時代已經(jīng)到來曾經(jīng)，網(wǎng)絡(luò)對我們而言快速、廉價的數(shù)據(jù)交

34、換：FTP有限的資源共享：TELNET/SSH快速、廉價的通信：EMAIL用低端設(shè)備實現(xiàn)高性能的計算：分布式計算、CLUSTER今天的網(wǎng)絡(luò)是信息存儲、交流、聚合的平臺網(wǎng)頁搜索、瀏覽BBS/微博電子商務(wù)電子政務(wù)但我們還希望網(wǎng)絡(luò)是計算資源、軟件資源、數(shù)據(jù)資源的聚集和共享平臺：人們象使用今天的大型計算機一樣使用網(wǎng)絡(luò)環(huán)境、人人都可以隨時訪問網(wǎng)格計算技術(shù)、云計算技術(shù)、還是其他計算技術(shù)？網(wǎng)絡(luò)計算環(huán)境與超級計算機今天人們對網(wǎng)絡(luò)計算環(huán)境的需求，用現(xiàn)有的超級計算機都能夠滿足，但難度要大、成本要高Google搜索：把所有的服務(wù)器聚集在一起，做一個集群出口帶寬要很高散熱問題很大所有數(shù)據(jù)維護人員要集中在一起還未有一個

35、高性能應(yīng)用，能夠占用RoadRunner/天河一號A的全部處理器資源當(dāng)北大CCSE的集群有大量用戶排隊的時候，科學(xué)院計算中心的超級計算機沒有人使用北大CCSE集群和科學(xué)院計算中心的超級計算機都有大量用戶排隊，但都有一個處理器空閑，因為每個用戶的計算都需要至少兩顆處理器處于維護成本等方面因素的考慮，每個應(yīng)用軟件、數(shù)據(jù)庫都只會安裝在數(shù)量有限的幾臺機器上課程目標(biāo)與定位并行計算環(huán)境的時代已經(jīng)到來多核處理器、SMP、集群、網(wǎng)絡(luò)計算環(huán)境程序開發(fā)的目的：提高處理器運算單元的利用率，達到計算性能提高的目的未來的程序開發(fā)，是并行程序的開發(fā)：我們假定多核是處理器發(fā)展的必然網(wǎng)絡(luò)是社會生活、工程設(shè)計制造、科學(xué)研究的基

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

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

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