換一個(gè)角度思考-并行計(jì)算

1、換一個(gè)角度思考：并行計(jì)算一、前言工作中，我們總是希望我們自己工作得更有效率，用更少的吋間解決更多的問題。在計(jì)算機(jī)里，這 就是并行計(jì)算的基木初衷。全世界第一臺(tái)計(jì)算機(jī)eniac中就己經(jīng)出現(xiàn)了并行計(jì)算的概念。它有20個(gè)累 加器，可以并發(fā)執(zhí)行多個(gè)加減運(yùn)算，可謂開并行計(jì)算的先河。在隨后的上世紀(jì)五六丁年代，由于晶體管 和集成電器的發(fā)明，出現(xiàn)了了更多更快的計(jì)算機(jī)。ibm是這一時(shí)期的主角，同期計(jì)算機(jī)編程語言的出現(xiàn), 由軟件完成處理并行計(jì)算的思想進(jìn)一步深化。但這一時(shí)期的計(jì)算還是大型機(jī)時(shí)代，沒有兒個(gè)平民能用得 起這些昂貴的大家伙。計(jì)算機(jī)和軟件技術(shù)述鎖在研究院和大學(xué)校園里。七i年代，隨著微電子技術(shù)的發(fā)展，出現(xiàn)了微型

2、處理器（cpu）。接著，1974年，全世界第一臺(tái)個(gè) 人電腦：牛郎星順利出爐。緊隨其后，看到市場前景的蘋果和ibm推波助瀾，計(jì)算機(jī)開始進(jìn)入個(gè)人時(shí)代。 個(gè)人計(jì)算機(jī)同時(shí)乂催生了軟件業(yè)的窩速發(fā)展，軟件乂帶動(dòng)cpu不斷升級(jí)換代。這為并行計(jì)算擺脫高端路 線，進(jìn)入平民化時(shí)代打下了基礎(chǔ)。龐大的eniac,運(yùn)算速度只相當(dāng)于現(xiàn)在的一只計(jì)算器。全世界第一臺(tái)個(gè)人計(jì)算機(jī)(pc)： 丫郎星。使川intel8080處理器，配4k內(nèi)存。為什么需要并行討ci在個(gè)人計(jì)算機(jī)誕生后的兒十年甲，程序員們編寫了大量的應(yīng)川軟件，這些軟件決大部分了采用串行 計(jì)算方法。所謂串行，是指軟件在pc±執(zhí)行，在進(jìn)入cpu前被分解為一個(gè)個(gè)指令

3、，指令在cpu中一 條條順序執(zhí)行。任一時(shí)間內(nèi)，cpu只能夠運(yùn)行一條指令。這種方式很符合我們對(duì)現(xiàn)實(shí)此界的思考習(xí)慣。 至于軟件的運(yùn)行速度，則依賴硬件的處理能力，尤其cpu的處理速度。這種思維方式到了 2005年遇到 了挑戰(zhàn)。在那一年，受限于制造cpu的半導(dǎo)體材料限制，左右cpu發(fā)展的摩爾定律開始失效了。但芯 片業(yè)很快找到了一個(gè)變通的辦法：在一塊芯片中植入多個(gè)處理核心，通過多核的共同運(yùn)算，捉高運(yùn)行速 度。不幸的是，采用串行方法編寫的軟件血臨著一個(gè)尷尬的局面：如果仍采用串行編程方式，運(yùn)行速度 將停滯不前。這樣，原來需要cpu完成的提速工作，被迫需要軟件口已來完成。在另一個(gè)領(lǐng)域：互聯(lián) 網(wǎng)，由于網(wǎng)絡(luò)數(shù)據(jù)極

4、速膨脹，數(shù)據(jù)量已經(jīng)遠(yuǎn)遠(yuǎn)超過一臺(tái)或者兒臺(tái)人型計(jì)算機(jī)的處理能力，需要更大數(shù)量 的計(jì)算機(jī)協(xié)同完成。而對(duì)這些問題，主要的解決方案就是：并行計(jì)算。probleminstructionsiiiuuni 111tnt3t2串行計(jì)算示例全球第一款雙核處理器：ibm power4 （64位，2001年誕生），主要川于ibm服務(wù)器和蘋果的macintosh 上。當(dāng)年的mac機(jī)it于運(yùn)算速度太快了，被禁止銷往中國、朝鮮等“敵對(duì)國家”。amd第一款雙核處理器：opteron （皓龍）。用于服務(wù)器領(lǐng)域，64位，2005年4月22日發(fā)布。amd第一款針對(duì)桌而的雙核處理器：athlon （速龍）。同樣是64位，只比服務(wù)器版

5、木晩1個(gè)月面市。intel是頂極芯片制造商中最晚推出的雙核處理器:intel pentiunid, 2005年5月26日發(fā)布。三、并行計(jì)算介紹核心提示：程序二數(shù)據(jù)+算法，并行計(jì)算程序二線程+分片+算法。3.1概述并行計(jì)算目前還是一門發(fā)展中的學(xué)科。并行計(jì)算是相對(duì)串行計(jì)算而言的，并行計(jì)算可以分為吋間上 的并行計(jì)算和空間上的并行計(jì)算。吋間上的并行計(jì)算就是流水線技術(shù)，即釆用指令預(yù)取技術(shù)，將每個(gè)指令分成多步，各步間疊加操作, 當(dāng)前指令完成前，后一指令準(zhǔn)備就緒，縮小指令執(zhí)行的時(shí)鐘周期。典型的以時(shí)間換空間。流水線技術(shù)rh 處理器(cpu)提供，不屬于我們討論的范疇?？臻g上的并行計(jì)算是指rh多個(gè)處理單元(不僅

6、是cpu)執(zhí)行的計(jì)算，是以空間換時(shí)間。空間上的并 行計(jì)算分為兩類：單指令多數(shù)據(jù)流(simd)和多指令多數(shù)據(jù)流(mimd)osimd是流水技術(shù)的擴(kuò)展，可以在一個(gè)時(shí)鐘周期處理多個(gè)指令，我們目前使川的pc大多屬于此列, 例如amd3dnow和intel mmxo因?yàn)槭怯布峁┑募夹g(shù)，也不屬于我們討論的內(nèi)容。mimd大致又分為五類：工作站集群(cow)、對(duì)稱多處理機(jī)(smp)、大規(guī)模并行處理機(jī)(mpp)、 分布共享存儲(chǔ)處理機(jī)(dsm)、并行向量機(jī)(pvp)o是我們討論的重點(diǎn)。在這一章節(jié)，我們將從程序員和算法的角度，著重討論空間上的并行計(jì)算。空間并行計(jì)算技術(shù)包括 數(shù)據(jù)并行計(jì)算利任務(wù)并行計(jì)算。數(shù)據(jù)并行計(jì)算

7、是指將一個(gè)大的數(shù)據(jù)分解為多個(gè)小的數(shù)據(jù)，分散到多個(gè)處 理單元執(zhí)行。任務(wù)并行是將大的任務(wù)分解為小的任務(wù)，分散到多個(gè)處理單元執(zhí)行，任務(wù)并行同時(shí)還要避 免任務(wù)車復(fù)執(zhí)行，協(xié)調(diào)數(shù)據(jù)的上下文關(guān)系，避免沖突發(fā)牛。任務(wù)并行計(jì)算與實(shí)際應(yīng)用需求緊密相關(guān)。所 以，任務(wù)并行計(jì)算要比數(shù)據(jù)并行計(jì)算復(fù)雜得多。并行計(jì)算與串行計(jì)算的最大不同在于，并行計(jì)算不僅要 考慮計(jì)算本身，還要考慮并行處理模型、網(wǎng)絡(luò)通信、計(jì)算協(xié)作諸多問題。3.2主要的并行計(jì)算體系類型3.2.1工作站集群(cow cluster of workstation)o工作站集群可以理解為：pc+網(wǎng)絡(luò)。它可以市少數(shù)幾臺(tái) pc擴(kuò)展到數(shù)t個(gè)節(jié)點(diǎn)的大規(guī)模并行系統(tǒng)，既可以是廉價(jià)

8、的并行程序調(diào)試環(huán)境，也可以成為的高性能計(jì)算 平臺(tái)。集群山于低成本，動(dòng)態(tài)可擴(kuò)充的特點(diǎn)，已經(jīng)成為高性能計(jì)算平臺(tái)的主流。目前google搜索和云計(jì) 算業(yè)務(wù)即采用這一方式。我國的聯(lián)想深騰xxxx、曙光xxxx系列均屬此類322稱多處理系統(tǒng)(smp symmetric multi processing),它由多個(gè)緊耦合多處理器組成，最人特點(diǎn)就是共 享全部資源。3.2.3人規(guī)模并行處理系統(tǒng)(mpp massively parallel processing)山許多松耦合處理單元(不是處理器)組 成的。這種結(jié)構(gòu)與smp對(duì)立，每個(gè)單-元自成體系，包括cpu、內(nèi)存、硬盤、操作系統(tǒng)，最大特點(diǎn)是不 共享資源。刀片服

9、務(wù)器屬于此列。3.2.4分布式共享存儲(chǔ)多處理(dsm)o它可以視為對(duì)smp的可擴(kuò)充，將共享數(shù)據(jù)映射到不同的物理位置。 數(shù)據(jù)的同步由硬件或者軟件來完成。是ei渝高性能計(jì)算機(jī)的主流發(fā)展方向之一。3.2.5并行向量機(jī)(pvp, parallel vector processor)o pvp使用專用的向量處理器，提供數(shù)據(jù)共亨，通過高 速交叉開關(guān)實(shí)現(xiàn)通信。向量運(yùn)算是一種較簡單的并行計(jì)算，適用血很廣，機(jī)器比較容易實(shí)現(xiàn)，使用也方 便，因此向量處理機(jī)(向量機(jī))在七十年代獲得了迅速發(fā)展。3.3并行計(jì)算的處理模式3.3.1主從模型(ms, master-slave),即有一個(gè)主進(jìn)程，其它是從進(jìn)程。主進(jìn)程負(fù)責(zé)整個(gè)系

10、統(tǒng)的控制(包 括任務(wù)調(diào)度、負(fù)載平衡)，從進(jìn)程負(fù)責(zé)對(duì)數(shù)據(jù)的處理和計(jì)算任務(wù)。google搜索業(yè)務(wù)目前就是采用的這種 編程模型。3.3.2對(duì)稱處理模型(spm)o這種架構(gòu)沒有主從概念之分，所仃進(jìn)程的地位都是平等的。在并行執(zhí)行過程中，我們可以任意選擇其中一個(gè)進(jìn)程執(zhí)行輸入輸出操作，其它進(jìn)程扮演同樣的角色。3.3.3多程序處理模型（mppm）：在計(jì)算機(jī)集群中，每臺(tái)計(jì)算機(jī)節(jié)點(diǎn)執(zhí)行不同的程序和相同的程序。3.4并行計(jì)算設(shè)計(jì)原則3.4.1適應(yīng)性。并行算法是并行計(jì)算的基礎(chǔ)，是為解決實(shí)際問題而出現(xiàn)，必須與實(shí)際應(yīng)用相結(jié)合。3.4.2可擴(kuò)展。并行算法是否能夠隨計(jì)算節(jié)點(diǎn)增加或減少而同步的線性變化，是評(píng)價(jià)一個(gè)并行算法是否

11、有效的重要標(biāo)志z。3.4.3粗粒度通常情況下，粒度越人越好。這是因?yàn)樵诿總€(gè)處理機(jī)中有很多需要計(jì)算的工作任務(wù)，如此 可以充分發(fā)揮多處理機(jī)的作用。并行加速比對(duì)細(xì)粒度問題一般情況下是不會(huì)很高的，這也是為什么并行 計(jì)算需耍求解大規(guī)模問題的原因所在。3.4.5減少通信一個(gè)高效的并行算法，通信是至關(guān)。提高性能的一個(gè)關(guān)鍵是減少數(shù)據(jù)通信量和通信次數(shù)。 3.4.6優(yōu)化性能。評(píng)價(jià)性能的優(yōu)缺，主要是看單節(jié)點(diǎn)計(jì)算的處理能力，和并行執(zhí)行效率。這與實(shí)際采川 的技術(shù)息息相關(guān)。3.5并行計(jì)算設(shè)計(jì)方法3.5.1分片3.5.1.1數(shù)據(jù)分片數(shù)據(jù)分片包括兩類：數(shù)值分片和哈希分片。數(shù)值分片適用丁已知數(shù)據(jù)范圍的分解，如果int、long

12、 類型處理。哈希分片適用于未知數(shù)據(jù)范圍的數(shù)據(jù)分解，包括字符串，字節(jié)數(shù)組類型。數(shù)據(jù)分片是把相同的操作作用于不同的數(shù)據(jù)，達(dá)到提到快速求解的h的。數(shù)據(jù)分片模型是一種較高 層次的并行計(jì)算模型，編程卻相對(duì)簡單。數(shù)據(jù)分片的并行計(jì)算最早應(yīng)用于并行向量計(jì)算機(jī)（pvp）。經(jīng)過 長期實(shí)踐表明，該技術(shù)可以高效地求解大部分的科學(xué)和工程計(jì)算問題。數(shù)據(jù)并行處理對(duì)象是數(shù)值，對(duì)應(yīng) 非數(shù)值類問題，則需要其它并行計(jì)算模型來解決。google的搜索業(yè)務(wù)是釆用數(shù)據(jù)分片的并行計(jì)算模式。 3.5.1.2任務(wù)分片任務(wù)分片的并行計(jì)算主要針對(duì)非數(shù)值類的并行處理。它通常消息傳遞機(jī)制（目前主流是pmi）,各并 行計(jì)算執(zhí)行單元z間通過傳遞消息來交換

13、數(shù)據(jù)，協(xié)調(diào)步伐，執(zhí)行控制操作。消息傳遞一般是針對(duì)分布節(jié) 點(diǎn)內(nèi)存，也口j以適用于共享內(nèi)存的并行節(jié)點(diǎn)。消息傳遞模型為程序員提供了更加靈活的控制手段和表現(xiàn) 形式。消息傳遞模型很容易實(shí)現(xiàn)，控制變化手段靈活多樣，但是需要程序員有豐富的并行編程經(jīng)驗(yàn)。是 一種較低層次，編程相對(duì)復(fù)雜的模型，適用于業(yè)務(wù)流程的并行化處理。3.5.2通信協(xié)調(diào)計(jì)算過程中的數(shù)據(jù)共享。通信工作目詢主要山tcp/ip協(xié)議完成。3.5.3組織組織各任務(wù)并發(fā)執(zhí)行，提高性能。在主線程的控制下，子線程在此承擬具體的并發(fā)操作任務(wù)。3.5.4映射分配任務(wù)（分布處理、共享處理）。線程和通信共同完成。3.6并行計(jì)算評(píng)價(jià)指標(biāo)3.6.1粒度。多處理機(jī)單獨(dú)執(zhí)行

14、任務(wù)大小的度量。3.6.2加速比。串行執(zhí)行時(shí)間為t,使川n個(gè)處理機(jī)并行執(zhí)行執(zhí)行的時(shí)間為q,則加速比為：s=t/q （越 大越好）3.6.3效率。若n個(gè)處理器的加速比為s,則并行算法的效率是：e=s/n3.6.4性能。求解一個(gè)問題的計(jì)算量為w,執(zhí)行時(shí)間為t,則性能為f=w/t （越大越好）3.7并行計(jì)算注意事項(xiàng)probleminstructionsiiiii 11 卜丄3.7.1任務(wù)分解：這是所有并行計(jì)算的核心問題，優(yōu)秀的任務(wù)分解需要保證平均和處理負(fù)載的平衡，同 吋，隨著處理器能力的動(dòng)態(tài)伸縮動(dòng)態(tài)調(diào)節(jié)3.7.2通信：并發(fā)處理離不開網(wǎng)絡(luò)通信聯(lián)系。相較與cpu運(yùn)算，數(shù)據(jù)在網(wǎng)絡(luò)間傳遞延遲是并發(fā)處理的瓶

15、頸z。光纖網(wǎng)絡(luò)是h前最好的選擇。3.7.3并行協(xié)調(diào)：是并行運(yùn)算過程中控制流程。3.7.4并行沖突：并行沖突來源主要是任務(wù)分解和并行協(xié)調(diào)。3.7.5數(shù)據(jù)歸并：這是數(shù)據(jù)計(jì)算完成后,必不可少的一步操作。數(shù)據(jù)歸并需要注意:過濾重復(fù)數(shù)據(jù),合 并相關(guān)性數(shù)據(jù)等。3.7.5死鎖。死鎖是在編程過程中，市于人為的原因造成。死鎖表示為：對(duì)彖間在不放棄口己資源下互 相調(diào)用。請(qǐng)程序員注意。3.8哪些任務(wù)不能使川并行計(jì)算3.8.1有著嚴(yán)格業(yè)務(wù)處理流程的計(jì)算。如在得到前一任務(wù)結(jié)果之前，不能進(jìn)行卞一步操作的處理。3.8.2 web作業(yè)，如php, jsp這類腳本編稈mu 11卜丄 iiiii 11 卜丄 iiiii 11 卜

16、丄并行計(jì)算示例ibm 360,共享存儲(chǔ)多處理器大型主機(jī)，使用cisc處理器。上世紀(jì)六i年代的代表機(jī)型。1976年面世的并行向量機(jī)：cray-1,是首次采用risc芯片的機(jī)型。從此，向量機(jī)牢牢控制住高端計(jì)算 帀場。我國的銀河系統(tǒng)也屬于向量機(jī)范疇。google案列可以說，google是十余年來，it界最成功的計(jì)算機(jī)公司。成功不僅來口于它為大眾捉供的及時(shí)準(zhǔn)確 的免費(fèi)信息，還有造就它成功的業(yè)務(wù)模式和技術(shù)。下面，我簡單介紹一下它的技術(shù)實(shí)現(xiàn)。4.1 google技術(shù)的優(yōu)秀z處google采用了 pc+linux的解決方案。google集群在存儲(chǔ)了海量的網(wǎng)絡(luò)數(shù)據(jù)同時(shí)，乂保證了捜索業(yè) 務(wù)的快速、穩(wěn)定和負(fù)載平衡

17、。是低成本、高效能的完美組合，這也是技術(shù)業(yè)界推崇google模式的主耍原 因。目前google技術(shù)已經(jīng)廣泛應(yīng)用到它的搜索、云計(jì)算等諸多領(lǐng)域，并且成為眾多開源社區(qū)模仿的對(duì)彖, 如 nutch, hadoopo4.2奠定google技術(shù)成功的三人基石4.2.1 gfs （google file system）gfs是一個(gè)基t linux平臺(tái)的分布式文件管理系統(tǒng)，是google最核心的技術(shù)。它實(shí)現(xiàn)了海量數(shù)據(jù)管 理，機(jī)器容錯(cuò)，數(shù)據(jù)容錯(cuò)，負(fù)載平衡等多項(xiàng)指標(biāo)。可以不夸張地說，山于gfs的穩(wěn)定，保證了 google 的成功。4.2.1 bigtablebigtable是google在2004年，為管理海量數(shù)

18、據(jù)研發(fā)的一個(gè)半結(jié)構(gòu)化數(shù)據(jù)存儲(chǔ)模型。它運(yùn)行在gfs z上，主要特點(diǎn)有：（1）數(shù)據(jù)以“塊”的形式保存在磁盤上，每個(gè)塊按照用戶的要求大小可調(diào)，通常是64m-塊。（2）存儲(chǔ)量極大。在gfs的管理下，可以分布到數(shù)千臺(tái)服務(wù)器上。（3）搜索速度快。bigtable是專為搜索而設(shè)計(jì)的，通過了優(yōu)化的搜索算法，提高搜索質(zhì)量。（4）“在多不在精”，通過將大量數(shù)據(jù)均勻分布多臺(tái)物理計(jì)算機(jī)節(jié)點(diǎn)上，實(shí)現(xiàn)高效的并行計(jì)算。4.2.3 mapreduce4.2.3.1 map就町以看做是把一個(gè)大塊數(shù)據(jù)分解成多個(gè)小塊數(shù)據(jù)的處理。是一個(gè)“分”的處理。4.2.3.2 reduce是map返回的數(shù)據(jù)后，對(duì)數(shù)據(jù)進(jìn)行的篩選、過濾，合并。可以看作是一個(gè)“合”的處理。423.3 mapreduce通常在gfs的控制下，并發(fā)到數(shù)百臺(tái)計(jì)算機(jī)節(jié)點(diǎn)上。mapreduce