并行程序設計

并行程序設計第一頁，共四十七頁，2022年，8月28日什么是并行計算?通過計算機硬件和軟件協(xié)作，同時執(zhí)行多個數據運算的一種計算模式提高計算效率，包括提高計算速度、以及降低數據處理的成本四種不同粒度/層次的并行計算微指令級(SSE:streamingSIMDextensions)：向量處理指令指令級(ILP:instruction-levelparallelism):一顆core微處理器，有3個ALU、2個FPU、3個SSE超標量技術：依靠微處理器體系結構技術，動態(tài)調整指令流的順序，一次發(fā)射多條指令，主流處理器幾乎都采用的技術超長指令字技術：編譯時將多條普通指令組裝成“超級指令”，比如IA微處理器線程級(TLP:thread-levelparallelism)：由程序將計算任務劃分成可以同時執(zhí)行的操作序列，每個操作序列分別由不同的處理器執(zhí)行內核來處理進程級：由程序將計算任務劃分成可以獨立分配計算資源的子任務，每個子任務分別由不同的計算機系統(tǒng)來處理第二頁，共四十七頁，2022年，8月28日并行程序與并行計算機串行程序:將計算任務分解成標量操作的序列的程序。串行程序是可以并行執(zhí)行的被編譯器編譯成面向SIMD的指令被編譯器編譯成面向VLIW指令由支持superscalar技術的處理器執(zhí)行并行程序:顯式表達計算任務中各數據運算無關性的程序并行計算機:能夠同時執(zhí)行并行程序中無關數據運算的計算機采用向量處理器一條指令完成多個數據單元的處理提供多個互相獨立的處理執(zhí)行核:每個執(zhí)行核分別執(zhí)行自己的指令流多處理器系統(tǒng):Multi-core/SMP/CPU+Coprocessor多計算機系統(tǒng):MPP/Cluster/Grid/Cloud第三頁，共四十七頁，2022年，8月28日并行程序的開發(fā)與并行計算串行程序程序員串行編譯串行程序串行處理器串行執(zhí)行超標量處理器并行執(zhí)行并行編譯SIMD并行程序SIMD處理器并行執(zhí)行VLIW并行程序VLIW處理器并行執(zhí)行線程并行程序多處理器系統(tǒng)并行執(zhí)行進程并行程序多計算機系統(tǒng)并行執(zhí)行線程并行程序進程并行程序編譯編譯第四頁，共四十七頁，2022年，8月28日我們一直在不自覺的使用并行計算技術來提升計算效能當前幾乎所有的計算機都是并行計算機：多核/微處理器內多個執(zhí)行單元/SIMD指令幾乎每個程序運行時都在執(zhí)行并行計算：專家們(體系結構/編譯/操作系統(tǒng))一直在替我們做并行技術的開發(fā)和運用指令級并行:提高同時執(zhí)行的指令數縮短指令流的執(zhí)行時間程序執(zhí)行效率的提升指令的基本執(zhí)行過程:instructionfetchdecodeexecutememoryaccesswriteback每個過程分別是由不同的部件執(zhí)行通過流水,使得多條指令同時執(zhí)行,每條指令分別處于不同的執(zhí)行階段:依靠pre-fetch/re-order等技術提供多個執(zhí)行單元，支持多條指令流水同時執(zhí)行數據級并行(data-levelparallelism)和任務級并行(task-levelparallelism):提高同時執(zhí)行的線程數用戶工作效率的提升(同時做多件事情,互不耽擱)基本技術支撐:interrupt/lock/hyper-threading/……Cache/virtualmemory/diskfile:執(zhí)行一個線程,總會發(fā)生數據訪問失效第五頁，共四十七頁，2022年，8月28日為什么要程序員編寫并行程序?并行計算機:提升計算系統(tǒng)計算潛力的必然趨勢Frequencywall:物理上限指令流的執(zhí)行時間下限Memorywall:CPU與Memory的速度鴻溝指令級并行的流水深度限制Powerwall:P=C(電容/晶體管的數量)×V2(電壓)×F(頻率)單個芯片的計算潛力上限Multi-core:提升單個芯片計算潛力的必然選擇,保持Moore’slaw:增加執(zhí)行核(用于數據運算的晶體管的數量),降低主頻提高用于數據運算的晶體管的比率:降低指令級并行的流水深度提高晶體管的利用率:執(zhí)行核之間按需共享cache/FBI挖掘處理器的計算潛力:提高芯片內用于數據處理的晶體管的比率微指令級并行(SIMD):提高計算機的字長一次解碼,處理更多的數據例如core微處理器的SSE指令采用128bit寄存器,一個指令周期可處理4個float數數據級并行(data-levelparallelism)和任務級并行(task-levelparallelism):multi-core,支持多個指令流同時處于數據運算階段第六頁，共四十七頁，2022年，8月28日如何提高數據處理的效率:利用多個執(zhí)行核分攤數據處理任務指令級并行/提高主頻:縮短指令流的執(zhí)行時間并行程序:縮短指令流的長度數據級并行/任務級并行:同時執(zhí)行多個短的指令流向量計算:提高單條指令的數據處理量處理器的主導技術已由提高處理器主頻轉向多核技術多核技術指令流的執(zhí)行時間延長了同時執(zhí)行的指令流數量增加了專用協(xié)處理器技術(X86指令集包括近300條指令,科學計算只需要其中的約80條指令)提高用于數據處理的晶體管的比率提高晶體管的利用率可重構計算技術(FPGA):由應用程序動態(tài)將芯片定制成專用協(xié)處理器單個數據處理部件的運算速度有上限:frequencywall多核時代,計算平臺的關鍵特征:不是單個執(zhí)行核的性能提升了,而是可利用的執(zhí)行核的數量提升了第七頁，共四十七頁，2022年，8月28日如何處理更大規(guī)模的問題,即:如何在可接受的時間里完成更大規(guī)模數據的處理?例如電信計費網絡搜索視頻點播地震現象反演:有限元法,地震區(qū)域的10m10m10m作為一個粒子,模擬這些粒子在地震前后的運動軌跡一臺計算機的服務能力有上限：處理器:計算能力（處理器的數量、處理器內執(zhí)行核的數量）內存:容量/訪問速度和帶寬磁盤及IO:容量/訪問速度和帶寬數據級并行(data-levelparallelism)和任務級并行(task-levelparallelism)多臺計算機協(xié)作面向領域/應用的并行計算機/協(xié)處理器(如GPU)/可重構計算(FPGA)第八頁，共四十七頁，2022年，8月28日編譯技術/微處理器體系結構技術不足以開發(fā)并行計算機的計算能力VLIW/superscalar：適合開發(fā)微處理器內部各個執(zhí)行單元的并行能力編譯技術：發(fā)現串行程序中無關的數據運算串行程序：隱藏了計算任務的數據運算無關性分析問題的數學/物理模型設計串行算法用串行語言編碼算法例如：尋找N以內的素數,該如何并行？prime[0]=2;prime[1]=3;p=2;for(i=5;i<N;i=i+2){for(j=1;j<p;j++)if(i%prime[j]==0)break;if(j<p)break;prime[p]=i;p++;}第九頁，共四十七頁，2022年，8月28日并行程序設計以問題分解為基礎,開發(fā)面向并行計算機的程序:通過多顆處理器協(xié)作、以及挖掘處理器的計算潛力,達到加速數據處理的效率和提高問題求解的規(guī)模的目標手段挖掘每個處理器的計算潛力提供更多的并行線程，避免由于內存壁壘等因素導致執(zhí)行單元處于空等待狀態(tài)微指令級并行(向量計算),提高單條指令的數據處理量多個處理器協(xié)作,分攤計算任務:縮短每個指令流的長度多計算機間數據劃分:增加存儲容量目標加速數據處理的效率提高問題求解的規(guī)模并行程序設計(本門課程)關注:發(fā)現計算任務中無關的數據運算，并利用數據運算的無關性開發(fā)并行計算機的計算能力向量處理器/陣列處理器系統(tǒng)多處理器系統(tǒng)多計算機系統(tǒng)第十頁，共四十七頁，2022年，8月28日多核時代：當多核處理器給用戶相應提高的性能體驗時，才真正到了多核時代計算平臺可為程序的運行提供多個執(zhí)行核多核時代不等于多核處理器時代如何獲得多個執(zhí)行核?多核處理器SMP/CPU+Coprocessor(專用協(xié)處理器/FPGA)Cluster/MPPGrid/Cloud大多數人并沒有多個執(zhí)行核協(xié)同計算(并行計算)的體會計算機專業(yè)的整個本科教學，都是基于VonNeumann，僅在操作系統(tǒng)、體系結構里提到一點并行和并發(fā)的概念使用的應用軟件也基本是基于串行技術:對計算性能的體驗并未改進,甚至有所下降串行程序+降低了主頻和指令流水深度的多核處理器更復雜的操作系統(tǒng):多線程支持/早先的超線程技術操作系統(tǒng)程序與用戶程序同時運行:Cache、FBI的瓶頸效應……可以在一臺機器上同時運行幾個程序:多核處理器之前已經如此操作系統(tǒng)的多進程/多線程/超線程支持技術用于超級計算機(Cluster/MPP)的HTC(high-throughputcomputing)第十一頁，共四十七頁，2022年，8月28日多核時代的特點已經具備的特點:并行計算機不再與“昂貴”、“高性能”有必然聯系，從體系結構上看，我們所使用的都是并行計算機支持SSE的多核CPU+GPU(每個GPU是一個微處理器陣列)CPU的微處理器內核包括多個執(zhí)行單元，采用了superscalar/VLIW技術尚不具備的特點:體驗并行計算機對計算性能的提升效果數據處理的速度更快可處理的數據規(guī)模更大挑戰(zhàn)性問題:并行程序的可移植性(衡量程序算法/代碼與目標平臺體系結構的緊密程度),來自并行計算平臺的異構性Intel/AMD處理器：CPU+CPUIBMCELL處理器:CPU+Coprocessor多處理器系統(tǒng):SMP/(CPU+Coprocessor)/(CPU+FGPA)多計算機系統(tǒng):Cluster/MPP/Grid/Cloud編程人員：“傻瓜”還是“精英”“傻瓜”：知道語法就夠了，其他事情交給編譯、運行支持去做吧“精英”：我能，但只有我能；我能，但我只會這一點盡管都是面向流媒體計算CPU中的SSE：SIMD，向量指令GPU：陣列處理器，線程并行編程(CUDA)第十二頁，共四十七頁，2022年，8月28日新軟件危機硬件上多核、軟件上串行大量的晶體管閑置、使用效率不高主頻的降低，導致性能體驗的下降性能，再次成為編程技術的焦點：線程級并行對開發(fā)多核處理器的計算能力至關重要性能，依賴“精英”們實現體系結構的特征數學/物理模型中的計算并行性特征→并行算法編寫程序：既要做“經理”，又要做“業(yè)務員”“業(yè)務員”：完成數據處理“經理”：“業(yè)務員”的分工、協(xié)調(在單核處理器時代，可以由編譯技術/微處理器體系結構技術自動解決)能以來自動機理論(運行時支持)、形式化理論(編譯技術)代替“精英”嗎？能：當這個問題很簡單時不能：并行算法設計是“藝術性”、而非“技術性”的工作。請將一個求素數的串行程序并行化吧。并行程序設計：少數人的專利、編程人員的基本要求？第十三頁，共四十七頁，2022年，8月28日內容提要課程基本信息對并行計算的認識并行計算的概念并行計算平臺并行計算技術的使用問題是什么？課程目標與定位教學安排第十四頁，共四十七頁，2022年，8月28日課程相關信息成績評定：平時成績(50%)+max{興趣研究報告，期末筆試}平時練習、編程實驗:50分興趣研究報告：50分。1-3人一組，自選題目，題目來源：所在研究組面臨的計算性能需求，結合課程學習，提出解決方案所在課題組正在解決的計算性能/計算效能方面的技術問題，結合課程學習，提出并行處理技術對該問題的促進高性能/高效能/云計算領域中感興趣的前沿研究方向，結合課程學習，開展調研，給出該方向的研究進展、趨勢和評價期末考試：50分課程網頁第十五頁，共四十七頁，2022年，8月28日課程歷史與內容沿革1999-2002年，李曉明MPI、HPF、OpenMP、并行編譯集群、MPP、SMP2003年開始，余華山2005年MPI、OpenMP、并行算法設計與應用實例、基于網絡的并行處理集群、MPP、SMP、網格2007年：教育部-Intel精品課程建設項目MPI、pthread與Intel多核技術、并行算法設計與應用實例、OpenMP、基于網絡的并行處理多核、SMP、集群、MPP、網格2008年：教育部-IBM精品課程建設項目pthread與Intel多核技術、CELLBE技術、MPI、并行算法設計與應用實例、基于網絡的并行處理(網格)多核、SMP、集群、MPP、網格第十六頁，共四十七頁，2022年，8月28日2011年：北京大學研究生課程建設以出版為目標的講義完成一章，在課程網站發(fā)布一章第十七頁，共四十七頁，2022年，8月28日并行程序設計的基本概念“并行程序”：支持多個操作、或者任務同時執(zhí)行的一種規(guī)劃做事情，總要規(guī)劃動作的順序：確定房子的地址、設計結構圖、作預算、選擇施工者、規(guī)劃施工進度、買建筑材料和施工。規(guī)劃的關鍵是分析問題各個部分之間的內在聯系，任何規(guī)劃都不能破壞這個聯系總有一些部分之間是沒有內在聯系的，可以同時執(zhí)行：房屋建筑的第一階段施工、購買第二階段建筑材料什么是并行程序設計：以任務分解為基礎,開發(fā)面向并行計算機的應用程序,以提高數據處理的效率、或者提高可解問題的規(guī)模.計算平臺：支持同時執(zhí)行多個數據處理運算(提供多個執(zhí)行核/向量處理器)操作系統(tǒng)：支持多指令流調度(多核處理器計算平臺)、或者多數據流訪問(向量處理器平臺)編程語言(以及編譯運行系統(tǒng))：支持計算并行性的表達第十八頁，共四十七頁，2022年，8月28日并行計算有什么用途并非所有問題都需要使用并行計算技術寫WORD文檔、寫C/C++程序代碼一個字符、一個字符地從鍵盤輸入即使用最低端的機器，沒有人感覺到不能及時得到響應(你同時打開了很多文檔、再邊聽MP3除外)使用Google、Baidu搜索網頁時刻都有成千上萬的用戶在搜索有興趣嗎？對比一下從Google、Baidu得到的響應速度、在一臺高端服務器上模擬100個用戶搜索1,000,000條記錄的響應速度汶川地震研究：反演地震過程，整個中國幾乎都有震感震區(qū)離散化，每10個立方米作為一個粒子使用當今運算速度最快的處理器，對這個三維數組做一次最簡單的運算，比如對每個元素做一次加法，需要多久？第十九頁，共四十七頁，2022年，8月28日并行程序的時代已經到了？并行計算：在計算平臺上同時執(zhí)行多個數據運算提高計算的效能提高處理器的計算潛力提高處理器的利用率提高數據處理的速度提高可解問題的規(guī)模并行計算平臺隨處可見多核處理器：PC機、筆記本SMP：服務器Cluster：大型計算中心服務器網絡計算環(huán)境：CNGrid、ChinaGrid、TeraGrid、Google？并行程序的需求來自各個領域我們的生活已經離不開網絡：成千上萬的并發(fā)用戶訪問搜索引擎、新聞網站、通信聊天網站、娛樂視頻網站、多人網絡游戲、公共服務網站(圖書館、電子文獻數據庫)、電子銀行、電子政務……工程、科研、生活服務越來越依賴于大規(guī)模數據的高效計算：飛機設計、汽車碰撞模擬、武器設計、油氣勘探、神州飛船跟蹤、基因數據分析、地震運動過程模擬、太陽風磁場重聯模擬、三峽大壩選址、氣象預報、……第二十頁，共四十七頁，2022年，8月28日并行計算的現狀CPU執(zhí)行程序時，使用了superscalar/VLIWCPU早就提供了SIMD支持，從MMX到現在的SSE4。一些商業(yè)軟件使用了SIMD一些函數包使用了SIMD一些編譯器在對循環(huán)優(yōu)化時使用了SIMD程序員使用了嗎？誰在用桌面機的多核處理器計算能力？桌面機上的應用以串行程序為主自己會寫并行程序的人不多一邊寫程序、一邊聽MP3時，可以用上，但影響編程、不用多核處理器時計算能力也夠了SMP(SymmetricMultiProcessing)服務器商業(yè)軟件：開發(fā)了并行能力自己開發(fā)的軟件：以串行程序為主主要是依靠操作系統(tǒng)支持多個進程/線程的同時執(zhí)行第二十一頁，共四十七頁，2022年，8月28日能同時使用成百上千顆處理器的應用有多少?集群上的并行計算情況：以CCSE128節(jié)點使用情況為例(2006年3月)3309個計算任務平均使用1.85個計算節(jié)點節(jié)點資源利用率94.7%IBMRoadRunner哪個應用能同時使用12960顆CELLCELL處理器執(zhí)行標量計算程序將非常慢(6912顆AMDOpteron似乎只是為了讓每個節(jié)點也能夠正常執(zhí)行原來的標量計算進程)天河計算機：主要計算能力來自GPU2048顆飛騰FT-1000八核心處理器14336顆IntelXeonX56702.93GHz六核心處理器7168塊NVIDIATeslaM2050高性能計算卡(GPU)第二十二頁，共四十七頁，2022年，8月28日如何看待我國的天河一號A？這是一個了不起的成就：2萬多顆處理器放在一起，并讓它們一起協(xié)作，采用LU分解的方法求解一個密集矩陣的方程通信問題穩(wěn)定性問題：一個部件的出錯/故障率是百萬分之一，這么多通信、存儲、計算、及其他輔助部件放在一起，怎么能夠穩(wěn)定運行？功耗和散熱問題……這臺機器本身也許并不是一個特別值得炫耀的成就有多少支持GPU的軟件？支持GPU的軟件能夠在哪些領域使用？GPU的基本數據類型是float，這樣一個精度下如何進行迭代模擬類計算、高精度場計算？有多少應用能夠有效開發(fā)1024顆處理器執(zhí)行核的計算能力？比如速度能夠提高600倍有多少人在開發(fā)面向這個機器的軟件？軟件的開發(fā)周期5-10年。第二十三頁，共四十七頁，2022年，8月28日誰依靠網絡環(huán)境進行并行計算?TeraGrid:主要用戶是SSH沒有網格對這類用戶沒有影響其實就是使用超級計算機EGEE:主要工作是提供一個統(tǒng)一的用戶接口支持并發(fā)用戶，避免相互惡性競爭：把計算任務動態(tài)綁定到具體的超級計算機上沒有支持一個問題同時使用多臺超級計算機CNGrid、ChinaGrid上是否有跨超級計算機求解問題的應用？Googlesearchengine：依靠網絡計算環(huán)境支持大規(guī)模并發(fā)用戶云計算的概念以數據為中心，根據數據需求選擇計算資源第二十四頁，共四十七頁，2022年，8月28日并行技術的應用為何不如人意？并行計算平臺有其適用范圍并行處理技術的使用離不開人的參與并行求解算法的設計不是簡單的串行算法并行化：按照體系結構設計算法向量處理器：標量數據要向量化多顆標量處理器：設計多個指令流第二十五頁，共四十七頁，2022年，8月28日你的筆記本、桌面機需要提高性能嗎？需要性能提高的理由系統(tǒng)啟動慢啟動一個應用程序慢：打開一個PDF、WORD、VC編程環(huán)境、DVD視頻文件、……打開很多個應用程序時，系統(tǒng)響應很慢打開一個大的PDF文件、WORD文件，翻頁瀏覽時響應慢如何提高性能:CPU的計算能力按照moore定律成長，你體驗的性能成長多少了？微軟的應用程序都很大，載入系統(tǒng)慢同時運行的應用越多，系統(tǒng)切換需要的存儲交換越大如果你覺得翻頁瀏覽時響應慢，請你看看被打開的PDF文件、WORD文件有多大你使用的CPU性能早就遠超過你的需求：軟件的質量、存儲的速度？？把VISTA還原成XP，把XP替換成WIN98，速度的體驗會如何？把CPU從INTELCOREi5換成PentiumIV1.8/3.2，速度的體驗會如何？第二十六頁，共四十七頁，2022年，8月28日多核處理器：CELLDMA(DirectMemoryAccess)數據存?。壕幊倘藛T需要知道一切細節(jié)，內存的大小、被訪問數據的大小、計算和數據的劃分方法、……標量計算速度慢：沒有數據預取、亂序執(zhí)行等。我猜想這是在RoadRunner中需要AMD處理器的根本原因：支持已有的MPI并行程序如何編程N-body問題？(IBM開發(fā)的方法：按照空間對粒子排序，一個空間的交給一個處理器，不考慮空間之間的互相作用。如此一來，粒子排序成為性能瓶頸)除了MPEG這類計算，CELL還能在哪地方用？GPGPU能走多遠？現在急需回答這個問題IBM已經放棄CELL，GPU會面臨同樣的困境嗎？第二十七頁，共四十七頁，2022年，8月28日多核處理器：IntelCore2CACHE數據存?。和耆帘螖祿L問細節(jié)，CACHE的命中率成為關鍵運行兩個無關的進程涉及的數據都?。夯ハ鄾]有影響兩個進程分別對一棵大的樹進行搜索，串行執(zhí)行兩個進程與并發(fā)執(zhí)行兩個進程：哪個更快？要協(xié)商對cache與系統(tǒng)內存之間系統(tǒng)總線的占用已經遇到一個應用：對一個大的數組進行變換確定數組A的元素值A[I，J]：產生兩個隨機數X，Y，將B[X，Y]賦值給A[I，J]使用串行程序要比并行程序更快執(zhí)行核cache系統(tǒng)內存第二十八頁，共四十七頁，2022年，8月28日SMP存儲一致性問題我在本課程的實驗中，對N-body問題測試計算任務直接更新全局空間的數據，并行程序更慢：同步開銷更適合計算松耦合問題。耦合：進程/線程運行過程中，互相交換數據、同步的頻率(通信)求素數問題：判斷I是否為素數，需要用到I之前的素數(同步)a=f(i)求和：任何時刻，只能有一個進程/線程在閱讀、修改變量a程序員要設法避免頻繁的同步第二十九頁，共四十七頁，2022年，8月28日cluster適合計算松耦合問題、問題要有一定的復雜度程序員劃分計算任務、數據確定數據的交換和同步當前最主要的超級計算機結構，其成功與MPI(messagepassinginterface)這一并行編程模式分不開能夠占用一臺超級計算機全部CPU的應用很少第三十頁，共四十七頁，2022年，8月28日網絡計算環(huán)境(Grid/Cloud)訪問網絡中的某臺超級計算機：當前主要的模式EGEE希望幫助用戶選擇需要訪問的超級計算機不適合計算松耦合問題：計算無耦合問題不錯，我們做了這方面的工作網格剛興起的時候，很多人嘗試在網絡環(huán)境運行MPI程序，效果很不理想計算的問題要足夠復雜：通信-計算比第三十一頁，共四十七頁，2022年，8月28日并行技術的使用離不開人的參與需要人根據問題特征發(fā)現并行性、選擇計算平臺需要人根據計算平臺劃分計算任務、優(yōu)化數據存取效率在基于Cache的多核處理器上，計算任務的粒度要考慮Cache的命中率在網絡計算環(huán)境上，計算任務的粒度要到批作業(yè)級才合適看幾個問題求素數問題：如何并行N-body問題：如何減少同步、維護數據一致性物體間的萬有引力定律，促使粒子的運動規(guī)則的大數組計算：C語言中以行優(yōu)先訪問、Fortran語言中以列優(yōu)先訪問可以提高數據的存取效率，在基于Cache的多核處理器平臺上，這個將更重要第三十二頁，共四十七頁，2022年，8月28日并行算法的設計問題從串行算法出發(fā)，尋找能夠并行的循環(huán)串型程序自動并行化的思路，實踐表明不理想串行算法本身常常沒有體現問題的并行性、或者隱藏了數學/物理模型中的并行性求素數問題并行算法的設計實現要考慮計算平臺：以我們做的大規(guī)模基因組可變剪接問題為例問題域中有幾萬個互相獨立的批作業(yè)在SMP/(有NFS、PFS支持的)cluster環(huán)境上：每個批作業(yè)作為一個任務在網絡計算環(huán)境上，要把幾百個、甚至幾千個批作業(yè)合并成一個子任務才會有效：這方面國際上已經有些類似的工作第三十三頁，共四十七頁，2022年，8月28日新的軟件危機？軟件危機：與軟件消耗的計算能力相比，硬件提供的計算能力過剩20世紀60、70年代，計算機的能力已經比50年代有巨大進步計算機的應用領域已經不只是在核武器計算人們使用匯編語言編寫程序：程序員少、生產效率低難題：如何開發(fā)更多的軟件解決高級語言和編譯技術，屏蔽計算任務到硬件設備的映射：Fortran、C操作系統(tǒng)技術，屏蔽硬件的實現和操作細節(jié)：軟件移植、應用軟件分時共享系統(tǒng)資源編程方法(軟件復用、可維護、可擴充)：結構化、面向對象第三十四頁，共四十七頁，2022年，8月28日今天的情形計算能力過剩Intel、AMD、IBM都在力推多核處理器網絡已經不只是交流信息，在P2P方面事實上已經成為計算平臺應用程序主要是串行的編寫并行程序是少數人的專利、效率低需求在擴展網絡計算已經深入社會生活的方方面面：支持大量的并發(fā)用戶科學工程領域更加依賴高性能計算技術研究工作的深度擴展：高精度、大規(guī)模研究工作的廣度擴展：軟件的協(xié)同、數據的綜合第三十五頁，共四十七頁，2022年，8月28日匯編語言寫串行程序C語言寫CELL處理器程序CPU操作寄存器數據，編程人員負責寄存器與內存數據的交換SPU操作局部內存數據，編程人員負責局部內存與全局內存的數據交換編程人員將計算任務分解到指令，規(guī)劃指令的執(zhí)行次序編程人員將計算任務分解到SPU的粒度(代碼和數據的規(guī)模不超過256KB)，規(guī)劃子任務的并發(fā)關系以BYTE為數據存取的基本單位以128BTYE(SPU寄存器大小)為數據存取的基本單位在Intel和AMD的多核處理器上：如何開發(fā)多個執(zhí)行核的并行計算能力使用C語言：只使用了一個處理器執(zhí)行核的計算能力使用C+pthread：并行算法設計、cache的命中率分別執(zhí)行不同的進程：進程之間的Cache競爭更進一步：如何開發(fā)SMP服務器、CLUSTER、網絡計算環(huán)境的并行能力？第三十六頁，共四十七頁，2022年，8月28日多核的硬件時代已經到來采用的多核技術，CPU的運算速度繼續(xù)按照Moore定律增長18個月，運算速度增長一倍一塊芯片上通用微處理器執(zhí)行核的數量真的會很多(比如超過32)嗎？制造工藝也許允許廠商這么做，但真能從軟件方面發(fā)揮其計算性能嗎？矛盾：最終用戶體驗到的性能改進極其有限多核的存儲模型是什么？存儲設備的性能早已成為性能的瓶頸，(我認為)也成為決定多核處理器時代存續(xù)的關鍵基于cache？(我認為)至少不能對程序員完全透明基于DMA？(我認為)至少不能完全將細節(jié)交給程序員一種全新的技術？我們拭目以待適合多核時代的軟件技術是什么？操作系統(tǒng)的理論和技術需要創(chuàng)新編譯理論和技術需要創(chuàng)新編程語言和模式需要創(chuàng)新第三十七頁，共四十七頁，2022年，8月28日網絡計算的時代已經到來曾經，網絡對我們而言快速、廉價的數據交換：FTP有限的資源共享：TELNET/SSH快速、廉價的通信：EMAIL用低端設備實現高性能的計算：分布式計算、CLUSTER今天的網絡是信息存儲、交流、聚合的平臺網頁搜索、瀏覽BBS/微博電子商務電子政務但我們還希望網絡是計算資源、軟件資源、數據資源的聚集和共享平臺：人們象使用今天的大型計算機一樣使用網絡環(huán)境、人人都可以隨時訪問網格計算技術、云計算技術、還是其他計算技術？第三十八頁，共四十七頁，2022年，8月28日網絡計算環(huán)境與超級計算機今天人們對網絡計算環(huán)境的需求，用現有的超級計算機都能夠滿足，但難度要大、成本要高Google搜索：把所有的服務器聚集在一起，做一個集群出口帶寬要很高散熱問題很大所有數據維護人員要集中在一起……還未有一個高性能應用，能夠占用RoadRunner/天河一號A的全部處理器資源當北大CCSE的集群有大量用戶排隊的時候，科學院計算中心的超級計算機沒有人使用北大CCSE集群和科學院計算中心的超級計算機都有大量用戶排隊，但都有一個處理器空閑，因為每個用戶的計算都需要至少兩顆處理器處于維護成本等方面因素的考慮，每個應用軟件、數據庫都只會安裝在數量有限的幾臺機器上第三十九頁，共四十七頁，2022年，8月28日課程目標與定位并行計算環(huán)境的時代已經到來多核處理器、SMP、集群、網絡計算環(huán)境程序開發(fā)的目的：提高處理器運算單元的利用率，達到計算性能提高的目的未來的程序開發(fā)，是并行程序的開發(fā)：我們假定多核是處理器發(fā)展的必然網絡是社會生活、工程設計制造、科學研究的基本工具通過這門課程的學習，你成為合格的程序員：開發(fā)程序，最大限度發(fā)揮計算平臺中處理器運算單元的利用率并行計算的基本原理：程序運行過程中，除了執(zhí)行數據處理語句外，還有哪些事情是必須做的并行程序開發(fā)的基本方法：計算并行性的挖掘、算法設計、實現優(yōu)化并行計算機的體系結構：工作原理、數據存儲與訪問第四十頁，共四十七頁，2022年，8月28日教什么？近10年并行處理技術研究、推廣應用的體會和認識把其中積累的應用實例拿來講，拋棄“教科書”上的示例請學生講他科研工作中面臨的問題，幫助他提出解決方案請同學們“照貓畫虎”準備幾只“貓”：求素數、N-Body、Laplace等準備幾個“動作”：MPI、pthread、CELL上的實現觀摩“貓”的表演：樣例并行程序請同學們體會“不要與虎謀皮”：沒有并行技術是不行的，但任何技術都有其局限性油氣勘探地震數據處理，一個三維數組的規(guī)模在15GB，雖然現在的處理器速度已經很快，在每個數組元素上加1，要多久？分子化學運動過程模擬，做一個大分子(幾千個原子)，一個時間步上，有多少次浮點計算、一個數據要被訪問多少次？N顆共享存儲的處理器，數據訪問的平均排隊時間是多長N顆分布存儲的處理器，數據交換的規(guī)模是多少第四十一頁，共四十七頁，2022年，8月28日教學方法結合具體的并行計算平臺CELL處理器、IntelCore2處理器SMP服務器集群結合教員在大規(guī)?？茖W工程計算積累的實例生物信息計算、流體力學、地質運動過程模擬、油氣勘探計算、天體物理、……教員講授PPT習題電子版參考資料自編講義：完成一章，在網站發(fā)布一章同學們的興趣研究科研工作中的問題感興趣的高性能/高效能研究前沿第四十二頁，共四十七頁，2022年，8月28日如何教？以實例和實踐為牽引Intel多核處理器/SMP服務器：pthread并行技術集群：MPI并行技術CELL處理器：數據存儲和訪問的原理、實現機制，向量并行計算N-body：加速比上限求素數：計算并行性的發(fā)現“不求甚解”：“藝術家”需要“天賦”并行計算涉及的計算機技術：操作系統(tǒng)、體系結構、、編譯技術、網絡通信有大量的trade-off：負載均衡與同步通信、重復計算與同步通信等實際問題基本是“一事一議”：沒有通用的并行算法和模式“知其然”，然后“知其所以然”從并行基礎理論出發(fā)，認識并行技術、分析應用需求運用并行基礎理論，解釋并行計算的現象“經典”也要“與時俱進”基礎理論：加速比上限、BSP/MPI、計算-通信比、SPMD/MPMD教研相長及時取舍:取新技術(多核技術/線程技術),舍未通過實踐檢驗的技術(HPF/OpenMP技術)第四十三頁，共四十七頁，2022年，8月28日教學內容并行計算的基本概念與基礎理論并行計算機與Fl