計算機并行計算的基本問題及現(xiàn)狀

計算機并行計算的基本問題及現(xiàn)狀引言工作中，我們總是希望我們自己工作得更有效率，用更少的時間解決更多的問題。在計算機里，這就是并行計算的基本初衷。全世界第一臺計算機ENIAC中就己經(jīng)出現(xiàn)了并行計算的概念。它有20個累加器，可以并發(fā)執(zhí)行多個加減運算，可謂開并行計算的先河。在隨后的20世紀五六十年代，由于晶體管和集成電器的發(fā)明，出現(xiàn)了更多更快的計算機。IBM是這一時期的主角，同期計算機編程語言的出現(xiàn)，由軟件完成處理并行計算的思想進一步深化。但這一時期的計算還是大型機時代，沒有幾個平民能用得起這些昂貴的東西。計算機和軟件技術(shù)還鎖在研究院和大學校園里。20世紀70年代，隨著微電子技術(shù)的發(fā)展，出現(xiàn)了微型處理器(CPU)接著，1974年，全世界第一臺個人電腦牛郎星順利出爐。緊隨其后，看到市場前景的蘋果和IBM推波助瀾，計算機開始進入個人時代。個人計算機同時又催生了軟件業(yè)的高速發(fā)展，軟件又帶動CPU不斷升級換代。這為并行計算擺脫高端路線，進入平民化時代打下了基礎(chǔ)。1并行計算的基本問題1.1為什么需要并行計算在個人計算機誕生后的幾十年里，程序員們編寫了大量的應(yīng)用軟件，這些軟件決大部分了采用串行計算方法。所謂串行，是指軟件在PC上執(zhí)行，在進入CPU前被分解為一個個指令，指令在CPU中一條條順序執(zhí)行。任一時間內(nèi)，CPU只能夠運行一條指令。這種方式很符合我們對現(xiàn)實世界的思考習慣。至于軟件的運行速度，則依賴硬件的處理能力，尤其CPU的處理速度。這種思維方式到了2005年遇到了挑戰(zhàn)。在那一年，受限于制造CPU的半導體材料限制，左右CPU發(fā)展的摩爾定律開始失效了。但芯片業(yè)很快找到了一個變通的辦法:在一塊芯片中植入多個處理核心，通過多核的共同運算，提高運行速度。不幸的是，采用串行方法編寫的軟件面臨著一個尷尬的局面:如果仍采用串行編程方式，運行速度將停滯不前。這樣，原來需要CPU完成的提速工作，被迫需要軟件自己來完成。在另一個領(lǐng)域：互聯(lián)網(wǎng)，由于網(wǎng)絡(luò)數(shù)據(jù)極速膨脹，數(shù)據(jù)量己經(jīng)遠遠超過一臺或者幾臺大型計算機的處理能力，需要更大數(shù)量的計算機協(xié)同完成。面對這些問題，主要的解決方案就是:并行計算。1.2并行計算的涵義并行計算目前還是一門發(fā)展中的學科。并行計算是相對串行計算而言的，并行計算可以分為時間上的并行計算和空間上的并行計算。時間上的并行計算就是流水線技術(shù)，即采用指令預(yù)取技術(shù)，將每個指令分成多步，各步間疊加操作，當前指令完成前，后一指令準備就緒，縮小指令執(zhí)行的時鐘周期。典型的以時間換空間。空間上的并行計算是指由多個處理單元(不僅是CPU)執(zhí)行的計算，是以空間換時間。空間上的并行計算分為兩類:單指令多數(shù)據(jù)流(SIMD)和多指令多數(shù)據(jù)流(MIMD)SIMD是流水技術(shù)的擴展，可以在一個時鐘周期處理多個指令，我們目前使用的PC大多屬于此列，例如AMD3DNOW和IntelMMX。MIMD大致又分為5類:工作站集群(COW)。對稱多處理機(SMP)。大規(guī)模并行處理機(MPP)。分布共享存儲處理機(DSM),并行向量機(PVP)?？臻g并行計算技術(shù)包括數(shù)據(jù)并行計算和任務(wù)并行計算。數(shù)據(jù)并行計算是指將一個大的數(shù)據(jù)分解為多個小的數(shù)據(jù)，分散到多個處理單元執(zhí)行。任務(wù)并行是將大的任務(wù)分解為小的任務(wù)，分散到多個處理單元執(zhí)行，任務(wù)并行同時還要避免任務(wù)重復(fù)執(zhí)行，協(xié)調(diào)數(shù)據(jù)的上下文關(guān)系，避免沖突發(fā)生。任務(wù)并行計算與實際應(yīng)用需求緊密相關(guān)。所以，任務(wù)并行計算要比數(shù)據(jù)并行計算復(fù)雜得多。并行計算與串行計算的最大不同在于，并行計算不僅要考慮計算本身，還要考慮并行處理模型。網(wǎng)絡(luò)通信。計算協(xié)作諸多問題。1.3主要的并行計算體系類型工作站集群(COWClusterofWorkstation)工作站集群可以理解為:PC+網(wǎng)絡(luò)。它可以由少數(shù)幾臺PC擴展到數(shù)千個節(jié)點的大規(guī)模并行系統(tǒng)，既可以是廉價的并行程序調(diào)試環(huán)境，也可以成為的高性能計算平臺。集群由于低成本，動態(tài)可擴充的特點，己經(jīng)成為高性能計算平臺的主流。目前Google搜索和云計算業(yè)務(wù)即采用這一方式。我國的聯(lián)想深騰XXXX,曙光XXXX系列均屬此類。多處理系統(tǒng)(SMPSymmetricMultiProcessing)它由多個緊耦合多處理器組成，最大特點就是共享全部資源。大規(guī)模并行處理系統(tǒng)(MPPMassivelyParallelProcessing)由許多松禍合處理單元(不是處理器)組成的。這種結(jié)構(gòu)與SMP對立，每個單元自成體系，包括CPU。內(nèi)存。硬盤。操作系統(tǒng)，最大特點是不共享資源。刀片服務(wù)器屬于此列。1.3.4分布式共享存儲多處理(DSM)它可以視為對SMP的可擴充，將共享數(shù)據(jù)映射到不同的物理位置。數(shù)據(jù)的同步由硬件或者軟件來完成。是目前高性能計算機的主流發(fā)展方向之一。1.3.5并行向量機(PVP,ParallelVectorProcessor)PVP使用專用的向量處理器，提供數(shù)據(jù)共享，通過高速交叉開關(guān)實現(xiàn)通信。向量運算是一種較簡單的并行計算，適用面很廣，機器比較容易實現(xiàn)，使用也方便，因此向量處理機(向量機)在20世紀70年代獲得了迅速發(fā)展。1.4并行計算的處理模式1.4.1主從模型(MS,Master-slave)即有一個主進程，其他是從進程。主進程負責整個系統(tǒng)的控制(包括任務(wù)調(diào)度。負載平衡)，從進程負責對數(shù)據(jù)的處理和計算任務(wù)。Google搜索業(yè)務(wù)目前就是采用的這種編程模型。1.4.2對稱處理模型(SPM)這種架構(gòu)沒有主從概念之分，所有進程的地位都是平等的。在并行執(zhí)行過程中，我們可以任意選擇其中一個進程執(zhí)行輸入輸出操作，其他進程扮演同樣的角色。1.4.3多程序處理模型(MPPM)在計算機集群中，每臺計算機節(jié)點執(zhí)行不同的程序和相同的程序。1.5并行計算設(shè)計原則適應(yīng)性。并行算法是并行計算的基礎(chǔ)，是為解決實際問題而出現(xiàn)，必須與實際應(yīng)用相結(jié)合?？蓴U展。并行算法是否能夠隨計算節(jié)點增加或減少而同步的線性變化，是評價一個并行算法是否有效的重要標志之一。粗粒度。通常情況下，粒度越大越好。這是因為在每個處理機中有很多需要計算的工作任務(wù)，如此可以充分發(fā)揮多處理機的作用。并行加速比對細粒度問題一般情況下是不會很高的，這也是為什么并行計算需要求解大規(guī)模問題的原因所在。減少通信。一個高效的并行算法，通信是至關(guān)。提高性能的一個關(guān)鍵是減少數(shù)據(jù)通信量和通信次數(shù)。優(yōu)化性能。評價性能的優(yōu)缺，主要是看單節(jié)點計算的處理能力，和并行執(zhí)行效率。這與實際采用的技術(shù)息息相關(guān)。1.6并行計算設(shè)計方法1.6.1分片數(shù)據(jù)分片。數(shù)據(jù)分片包括兩類:數(shù)值分片和哈希分片。數(shù)值分片適用于己知數(shù)據(jù)范圍的分解，如果Int,Long類型處理。哈希分片適用于未知數(shù)據(jù)范圍的數(shù)據(jù)分解，包括字符串，字節(jié)數(shù)組類型。數(shù)據(jù)分片是把相同的操作作用于不同的數(shù)據(jù)，達到提到快速求解的目的。數(shù)據(jù)分片模型是一種較高層次的并行計算模型，編程卻相對簡單。數(shù)據(jù)分片的并行計算最早應(yīng)用于并行向量計算機(PVP))經(jīng)過長期實踐表明，該技術(shù)可以高效地求解大部分的科學和工程計算問題。數(shù)據(jù)并行處理對象是數(shù)值，對應(yīng)非數(shù)值類問題，則需要其他并行計算模型來解決。Google的搜索業(yè)務(wù)是采用數(shù)據(jù)分片的并行計算模式。（2）任務(wù)分片。任務(wù)分片的并行計算主要針對非數(shù)值類的并行處理。它通常的消息傳遞機制（目前主流是PMI是各并行計算執(zhí)行單元之間通過傳遞消息來交換數(shù)據(jù)，協(xié)調(diào)步伐，執(zhí)行控制操作。消息傳遞一般是針對分布節(jié)點內(nèi)存，也可以適用于共享內(nèi)存的并行節(jié)點。消息傳遞模型為程序員提供了更加靈活的控制手段和表現(xiàn)形式。消息傳遞模型很容易實現(xiàn)，控制變化手段靈活多樣，但是需要程序員有豐富的并行編程經(jīng)驗。是一種較低層次，編程相對復(fù)雜的模型，適用于業(yè)務(wù)流程的并行化處理。1.6.2通信協(xié)調(diào)計算過程中的數(shù)據(jù)共享。通信工作目前主要由TCP/IP協(xié)議完成。1.6.3組織組織各任務(wù)并發(fā)執(zhí)行，提高性能。在主線程的控制下，子線程在此承擔具體的并發(fā)操作任務(wù)。1.6.4映射分配任務(wù)（分布處理。共享處理）。線程和通信共同完成。1.7并行計算應(yīng)注意的事項⑴任務(wù)分解:這是所有并行計算的核心問題，優(yōu)秀的任務(wù)分解需要保證平均和處理負載的平衡，同時，隨著處理器能力的動態(tài)伸縮動態(tài)調(diào)節(jié)。通信:并發(fā)處理離不開網(wǎng)絡(luò)通信聯(lián)系。相較與CPU運算，數(shù)據(jù)在網(wǎng)絡(luò)間傳遞延遲是并發(fā)處理的瓶頸之一。光纖網(wǎng)絡(luò)是目前最好的選擇。并行協(xié)調(diào):是并行運算過程中控制流程。并行沖突:并行沖突來源主要是任務(wù)分解和并行協(xié)調(diào)。數(shù)據(jù)歸并:這是數(shù)據(jù)計算完成后，必不可少的一步操作。數(shù)據(jù)歸并需要注意:過濾重復(fù)數(shù)據(jù)，合并相關(guān)性數(shù)據(jù)等。死鎖。死鎖是在編程過程中，由于人為的原因造成。死鎖表示為：對象間在不放棄自己資源下互相調(diào)用。請程序員注意。2并行計算的發(fā)展現(xiàn)狀2.1多核為主流的體系結(jié)構(gòu)多核處理器代表了計算技術(shù)的一次創(chuàng)新。由于數(shù)字數(shù)據(jù)和互聯(lián)網(wǎng)的全球化，商業(yè)和消費者開始要求多核處理器帶來性能改進，這個重要創(chuàng)新就開始了，因為多核處理器比單核處理器具有性能和效率優(yōu)勢，多核處理器將會成為被廣泛采用的計算模型。在驅(qū)動PC安全性和虛擬化技術(shù)的重大進程過程中，多核處理器扮演著中心作用，這些安全性和虛擬化技術(shù)的開發(fā)用于為商業(yè)計算市場提供更大的安全性。更好的資源利用率。創(chuàng)造更大價值。普通消費者用戶也期望得到前所未有的性能，這將極大地擴展其家庭PC和數(shù)字媒體計算系統(tǒng)的使用。多核處理器具有不增加功耗而提高性能的好處，實現(xiàn)更大的性能/能耗比。在一個處理器中放入兩個或多個功能強大的計算核產(chǎn)生了一個重大的可能性。由于多核處理器能提供比單核處理器更好的性能和效率，下一代的軟件應(yīng)用程序很有可能是基于多核處理器而開發(fā)的。不管這些應(yīng)用是幫助專業(yè)的電影公司以更少的投入和更少的時間完成更真實的電影，還是以更徹底的方法使得PC更自然和直觀，多核處理器技術(shù)將永遠改變計算世界。多核處理器表達了AMD了解顧客需求并且開發(fā)最能滿足客戶要求產(chǎn)品的意愿。微軟多核計算的主管DanReed稱，整個世界上很缺乏那些并行計算的研究人員，而一個間接的原因就是學院里對于并行計算的關(guān)注度不夠，而這些學院正是下一代軟件開發(fā)人員誕生的地方。越來越高的時鐘頻率導致應(yīng)用程序的代碼運行得越來越快，而對于當前多核處理器來講這一規(guī)則雖然成立，但卻有所不同。而這種不同可以做一個形象的比喻，那就是一部跑車和一輛學校的巴士。當跑車能夠以很快的速度飛奔時，巴士雖然比較慢，但它可以載著更多的人前行。問題就是，簡單地在計算機CPU上增加多個核并不能增加傳統(tǒng)應(yīng)用程序代碼的運行速度，這一結(jié)果是根據(jù)一項來自于Forrester研究公司的報告得出的。換句話說，復(fù)雜的工作需要拆分來填充這輛巴士上的空座位。Forrester的報告還談到：當前四核處理器會激發(fā)更多的多處理器設(shè)計的思想，2009年x86的服務(wù)器使用64個處理器核，并且2012年臺式機也己實現(xiàn)了這一夢想。2.2以數(shù)據(jù)為中心的云計算云計算可以被解釋為虛擬主機的租賃服務(wù)，也可以被解釋為企業(yè)軟件的SaaS化，又或者是一個云機箱之上跑許多個虛擬桌面。但不管怎么說筆者認為云計算要解決3個實質(zhì)問題：大規(guī)模。這里提到的大規(guī)模不僅是超過單臺PC服務(wù)器的能力，更指的是能夠支撐互聯(lián)網(wǎng)級別的數(shù)據(jù)和應(yīng)用，例如個人郵箱。搜索等。低成本。低成本的一個標志在于用系統(tǒng)軟件來解決廉價硬件在復(fù)雜條件下不可靠的問題。服務(wù)運營。這里所指的服務(wù)運營是能夠通過無差別的存儲計算能力來提供公共的基礎(chǔ)服務(wù)。當各式各樣的應(yīng)用可以共同運行在一個統(tǒng)一平臺之上，才能達到真正的大規(guī)模，而由此得到的規(guī)模效益才能夠獲得低成本，于是這3個本質(zhì)的問題是云計算的有機整體。傳統(tǒng)的軟件以功能為主體，而云計算則徹底推動了數(shù)據(jù)為土。數(shù)據(jù)將成為一家企業(yè)乃至是一個國家極其重要的戰(zhàn)略資源。而數(shù)據(jù)的搜集。存儲。分享。處理和應(yīng)用是需要大量的計算資源的，從這個意義上說，云計算可以稱為以數(shù)據(jù)為中心的分布式大規(guī)模計算。而一個企業(yè)乃至一個國家瞬間能夠調(diào)用的計算資源則成為了能否利用和發(fā)揮好數(shù)據(jù)這個戰(zhàn)略資源的核心競爭力。提供公共計算服務(wù)的云計算平臺將大大促進企業(yè)之間。社會各行業(yè)間的數(shù)據(jù)收集。分享和實時處理，在這基礎(chǔ)之上必將孕育出大量的數(shù)據(jù)運營的新商業(yè)模式，數(shù)據(jù)也將最終成為一切商業(yè)行為的決策基礎(chǔ)，從而大大提高社會的整體效率，促進人類從大工業(yè)化時代走向信息化時代。2.3以普及應(yīng)用為宗旨的個人高性能計算機作為三大科學研究手段之一的高性能計算機，其發(fā)展的根本動力來自于各類科學技術(shù)對計算機性能永無止境的需求和生產(chǎn)的實際需要。在1996年的SuperComputing96大會上，美國政府HPCC計劃全國協(xié)調(diào)委員會主席JohnToole在題為危機。創(chuàng)新與機會:HPCC將向何處去的報告中指出：高性能計算與通信對美國的國家安全及保持美國在未來的優(yōu)勢至關(guān)重要。美國政府將在高端計算機與通信。大規(guī)模網(wǎng)絡(luò)。高可信系統(tǒng)等5個方面制定10~15年的長期計劃，保持長期持續(xù)性投資。過去的10年是超級計算機。特別是并行機飛速發(fā)展。走向成熟的10年。10年中CPU芯片的性能翻了幾番，計算機工作者發(fā)明了Wormhole（蟲蝕尋徑）技術(shù)，找到了更符合實際的LogP并行計算模型，創(chuàng)造了成百的不同規(guī)模。不同拓撲結(jié)構(gòu)的并行平臺。特別是，由于多種軟硬件技術(shù)的進步，使既具有可擴展性。又具有可編程性的。分布式共享存貯結(jié)構(gòu)的并行機成為可能。并行計算機是當今超級計算機的主流。并行計算機的發(fā)展史就是可擴展性與可編程性這一對矛盾相互作用直至統(tǒng)一的歷史?？蓴U展性是并行計算機最大的優(yōu)勢，可簡單定義為在確定的應(yīng)用背景下，計算機系統(tǒng)的性能要隨處理機數(shù)的增加而線性增長（美籍并行處理專家黃愷教授語）?？蓴U展性包括規(guī)?？蓴U展。時間可擴展和問題可擴展幾個方面。規(guī)?？蓴U展的要點是均衡，均衡的目的是防止瓶頸的發(fā)生，三T表達了當今均衡的指標。時間可擴展也稱換代可擴展，主要指體系不受限于芯片。器件。工藝等。問題可擴展指格點增加時，系統(tǒng)能適應(yīng)問題規(guī)模的擴大，而當問題的粒度加大時，效率能相應(yīng)提高?，F(xiàn)有的MPP，如Inetl的Paragon,IBM的SP/2。國內(nèi)的曙光1000,一般認為是可以擴展的?？删幊绦允窃诓⑿袡C發(fā)展的過程中，伴隨可擴展性而產(chǎn)生的新概念。并行計算機有共享與分布式兩種存儲結(jié)構(gòu)，所以操作系統(tǒng)進程間的通信(IPC)也有兩種不同的機制:共享變量和信息傳遞。機器結(jié)構(gòu)和操作系統(tǒng)的這些區(qū)別又影響到支撐軟件和應(yīng)用軟件的編程模式。SMP的程序設(shè)計仍以傳統(tǒng)的高級語言為基礎(chǔ)，系統(tǒng)提供自動并行識別或增加并行語言成分。而MPP必須建立另一種編程環(huán)境(如PVM,MPI等)，在程序中顯式地寫出信息的發(fā)送和接收。這不僅導致應(yīng)用軟件編寫困難，還給廣大用戶增加了很多負擔。為此，創(chuàng)建了一個新的單詞Programmability，用以描述并行計算機的這一重要特點。高性能計算機己走過了整整20年，這是一段可擴展性與可編程性這一對矛盾相互作用直至統(tǒng)一的歷史。市場需求是發(fā)展的動力，技術(shù)進步是發(fā)展的條件。有專家估計，從現(xiàn)在起直到21世紀若干年，DSM結(jié)構(gòu)將是超級計算機的主流，將穩(wěn)固地占領(lǐng)超級計算機的主要市場。3并行計算的發(fā)展機群系統(tǒng)機群系統(tǒng)是利用高