并行計(jì)算中的通信性能研究

并行計(jì)算通信性能研究摘要：在基于網(wǎng)絡(luò)環(huán)境的分布式并行計(jì)算中，因?yàn)橐话闱闆r下，局域網(wǎng)的底層通信協(xié)議多為以太網(wǎng)協(xié)議，而以太網(wǎng)采用的是總線通信和信道競爭兩種技術(shù)，因此基于網(wǎng)絡(luò)環(huán)境的分布式并行計(jì)算中最大的問題可能就是要解決好通信開銷的問題。本文研究了一種子任務(wù)計(jì)算和通信錯開的解決方案，從理論上分析該方案的加速比和并行效率等。關(guān)鍵詞：分布式并行計(jì)算；以太網(wǎng)；信道競爭；并行效率；加速比Abstract：Generallyspeakinginthelowerlayeroflocalnetwork，theprotocolisEthernet，andEthernetisbasedonbustopologyandChannelCompetition.Sothemostimportantproblemfordistributedparallelcomputing,maybetoolargerforcommunicationspending.Inthispaperwestudiedaschemetosolvethisproblem,andgivetheanalysisofthisparallelefficiencyandaccelerateproportion。Keywords：distributedparallelcomputing，Ethernetchannelcompetition，parallelefficiency,accelerateproportion前言并行計(jì)算是目前解決大規(guī)模計(jì)算問題的一種有效方法，利用普通局域網(wǎng)中的計(jì)算機(jī)可以有效實(shí)現(xiàn)并行計(jì)算，其最大意義在于能夠充分利用網(wǎng)絡(luò)中大量閑散的CPU，提供的計(jì)算能力遠(yuǎn)遠(yuǎn)的超過同等的串行計(jì)算機(jī);性價比遠(yuǎn)遠(yuǎn)高于同等的小型機(jī)，而且可以很容易進(jìn)行擴(kuò)展。如果運(yùn)用的恰當(dāng)，可以獲得非常好的效果。在進(jìn)行并行計(jì)算時，各個節(jié)點(diǎn)之間的負(fù)載平衡，數(shù)據(jù)傳遞問題至關(guān)重要！并行計(jì)算機(jī)是由一組處理單元組成的。這組處理單元通過相互之間的通信與協(xié)作，以更快的速度共同完成一項(xiàng)大規(guī)模的計(jì)算任務(wù)。因此，并行計(jì)算機(jī)的兩個最主要的組成部分是計(jì)算節(jié)點(diǎn)和節(jié)點(diǎn)間的通信與協(xié)作機(jī)制。并行計(jì)算機(jī)體系結(jié)構(gòu)的發(fā)展也主要體現(xiàn)在計(jì)算節(jié)點(diǎn)性能的提高以及節(jié)點(diǎn)間通信技術(shù)的改進(jìn)兩方面。多處理機(jī)并行計(jì)算一般由計(jì)算和通信兩部分組成。根據(jù)多處理機(jī)并行計(jì)算過程對處理機(jī)間信息交換的依賴方式的不同可分為同步并行計(jì)算和異步并行計(jì)算。同步并行計(jì)算通常是指并行計(jì)算機(jī)系統(tǒng)中每一處理器，無論它的計(jì)算速度與其它處理器相差多大，也不論它所處理的任務(wù)量如何與眾不同，都必須等待所有的處理器都到達(dá)同一個珊后才能做進(jìn)一步的工作，這個珊常被稱為同步點(diǎn)。而異步并行計(jì)算則是指在通常用于等待同步操作的時間內(nèi)并行計(jì)算機(jī)系統(tǒng)內(nèi)每一處理器各自完成自己的有用工作。與同步計(jì)算相比，當(dāng)某處理器等待其它處理器到達(dá)某一柵時，異步并行計(jì)算提供該處理器有用的計(jì)算供其執(zhí)行。1并行通信機(jī)制的發(fā)展20世紀(jì)80年代中期，加州理工學(xué)院成功地將64個i8086/i8087處理器通過超立方體互連結(jié)構(gòu)連結(jié)起來。此后，便先后出現(xiàn)了InteliPSC系列、INMOSTransputer系列，IntelParagon以及IBMSP的前身Vulcan等基于消息傳遞機(jī)制的并行計(jì)算機(jī)。20世紀(jì)80年代末到90年代初，共享存儲器方式的大規(guī)模并行計(jì)算機(jī)又獲得了新的發(fā)展。IBM將大量早期RISC微處理器通過蝶形互連網(wǎng)絡(luò)連結(jié)起來。人們開始考慮如何才能在實(shí)現(xiàn)共享存儲器緩存一致的同時，使系統(tǒng)具有一定的可擴(kuò)展性。20世紀(jì)90年代初期，斯坦福大學(xué)提出了DASH計(jì)劃，它通過維護(hù)一個保存有每一緩存塊位置信息的目錄結(jié)構(gòu)來實(shí)現(xiàn)分布式共享存儲器的緩存一致性。后來，IEEE在此基礎(chǔ)上提出了緩存一致性協(xié)議的標(biāo)準(zhǔn)。20世紀(jì)90年代至今，主要的幾種體系結(jié)構(gòu)開始走向融合。屬于數(shù)據(jù)并行類型的CM-5除大量采用商品化的微處理器以外，也允許用戶層的程序傳遞一些簡單的消息。CrayT3D是一臺NUMA結(jié)構(gòu)的共享存儲型并行計(jì)算機(jī)，但是它也提供了全局同步機(jī)制、消息隊(duì)列機(jī)制，并采取了一些減少消息傳遞延遲的技術(shù)。隨著微處理器商品化、網(wǎng)絡(luò)設(shè)備的發(fā)展以及MPI/PVM等并行編程標(biāo)準(zhǔn)的發(fā)布，集群架構(gòu)的并行計(jì)算機(jī)出現(xiàn)開始。IBMSP2系列集群系統(tǒng)就是其中的典型代表。在這些系統(tǒng)中，各個節(jié)點(diǎn)采用的都是標(biāo)準(zhǔn)的商品化計(jì)算機(jī)，它們之間通過高速網(wǎng)絡(luò)連接起來。2影響通信性能的因素2.1網(wǎng)絡(luò)帶寬低工作站機(jī)群系統(tǒng)使用的網(wǎng)絡(luò)是普通的局域網(wǎng),而局域網(wǎng)的帶寬通常都比較低,如以太網(wǎng)的帶寬只有10MB/S。局域網(wǎng)的帶寬之所以低,原因主要是局域網(wǎng)是為長距離的數(shù)據(jù)通信而設(shè)計(jì)的,由于通信距離較長,限制了通信速度的提高,因?yàn)樾盘柕念l率越高,它能夠傳輸?shù)木嚯x也越短。另外一個原因是出于價格上的考慮。為了降低網(wǎng)絡(luò)系統(tǒng)布線所需的成本,大多數(shù)是LAN共享一根信號總線進(jìn)行數(shù)據(jù)傳輸,因此這也在很大程度上影響了網(wǎng)絡(luò)系統(tǒng)的性能,特別是在網(wǎng)絡(luò)負(fù)載較重時,由于各結(jié)點(diǎn)都要搶占信號總線,很容易造成通信阻塞,使得實(shí)際通信帶寬比其最大帶寬要小得多。2.2傳統(tǒng)TCP/IP協(xié)議的多層次結(jié)構(gòu)帶來了很大的處理開銷TCP/IP協(xié)議是面向低速率、高差錯和大數(shù)據(jù)包傳輸而設(shè)計(jì)的,它是一個多層次的軟件結(jié)構(gòu),按自底向上的順序可劃分為四層:網(wǎng)絡(luò)接口層、網(wǎng)間網(wǎng)層、傳輸層和應(yīng)用層。由于協(xié)議層次多,在進(jìn)行數(shù)據(jù)傳輸時,數(shù)據(jù)需要經(jīng)過多次拷貝才能從應(yīng)用層傳遞到網(wǎng)絡(luò)接口或從網(wǎng)絡(luò)接口傳送到應(yīng)用層,而多次拷貝帶來了很大的網(wǎng)絡(luò)延遲時間。另外,在多層協(xié)議的實(shí)現(xiàn)中,各層還重復(fù)實(shí)現(xiàn)了很多相同的功能,比如:·從IP層到傳輸層都要進(jìn)行差錯控制·從網(wǎng)絡(luò)接口層到應(yīng)用層都要進(jìn)行協(xié)議的處理機(jī)調(diào)度·從IP層到應(yīng)用層都要進(jìn)行流量控制·從IP層到應(yīng)用層都要進(jìn)行數(shù)據(jù)包組裝和定序的緩沖這些冗余的功能雖然可確保數(shù)據(jù)的無差錯傳送,但隨著鏈路傳輸出錯率降低,這種冗余處理反而限制了數(shù)據(jù)及時提交給應(yīng)用程序處理?？梢?多層次的協(xié)議結(jié)構(gòu)是造成通信瓶頸的主要原因之一,合并某些層次,刪除冗余的處理,設(shè)計(jì)一種輕型通信協(xié)議,是提高通信性能的重要方法。2.3協(xié)議復(fù)雜的緩沖管理增加了網(wǎng)絡(luò)延遲網(wǎng)絡(luò)協(xié)議處理包括很多功能,如流量控制、差錯控制、出錯重發(fā)機(jī)制、擁塞控制等,而這些功能的實(shí)現(xiàn)都與緩沖管理密切相關(guān)。緩沖管理的作用是完成數(shù)據(jù)的分組和組裝,緩沖區(qū)可看成一種網(wǎng)絡(luò)資源,這種資源是有限的,對它的管理很重要。不過通常的緩沖管理機(jī)制都比較復(fù)雜,例如,采用一種BerkeleyUNIX叫mbufs的結(jié)構(gòu)對協(xié)議的數(shù)據(jù)包進(jìn)行緩沖管理,但mbufs算法很復(fù)雜,開銷很大。在DECsta5000上,對單字節(jié)消息緩沖管理,需要100微秒,而對512字節(jié)數(shù)據(jù)包需要300微秒,可見緩沖管理帶來的網(wǎng)絡(luò)延遲也很大,如何簡化協(xié)議復(fù)雜的緩沖管理也是通信技術(shù)研究的主要內(nèi)容。2.4操作系統(tǒng)額外開銷不可忽視操作系統(tǒng)提供的系統(tǒng)調(diào)用和原語是網(wǎng)絡(luò)協(xié)議實(shí)現(xiàn)的底層軟件支持。在網(wǎng)絡(luò)協(xié)議實(shí)現(xiàn)中涉及到上下文切換、調(diào)入調(diào)出頁面、啟動I/O設(shè)備、中斷響應(yīng)等操作系統(tǒng)處理,有時這些開銷可能比協(xié)議本身的處理開銷還大。比如,在360系統(tǒng)上對一個數(shù)據(jù)包的協(xié)議處理SunTCPIP時間為100微秒,而操作系統(tǒng)的額外開銷卻高達(dá)240微秒,這就造成了通信性能對操作系統(tǒng)一定程度上的依賴。因此,要提高通信系統(tǒng)的性能,降低網(wǎng)絡(luò)延遲,應(yīng)當(dāng)盡量減少網(wǎng)絡(luò)協(xié)議對主機(jī)操作系統(tǒng)的服務(wù)請求,最大限度地使通信與計(jì)算重疊[4]。3異步分布式并行算法異步并行計(jì)算相對于同步并行計(jì)算會帶來一些計(jì)算過程的“混亂”，并使計(jì)算的收斂性分析復(fù)雜化。但是，在基于網(wǎng)絡(luò)環(huán)境的分布式并行計(jì)算中，最大的問題可能就是要解決好通信開銷的問題。因?yàn)樗褂玫木钟蚓W(wǎng)環(huán)境，其底層協(xié)議大多是基于以太網(wǎng)的，其上為協(xié)議。而以太網(wǎng)是一種總線型局域網(wǎng)，它采用的是CSMA（載波偵聽多路訪問沖突檢測）技術(shù)。如果采用同步并行計(jì)算，強(qiáng)調(diào)的是負(fù)載均衡，各處理到達(dá)同一個珊后才能做進(jìn)一步的工作：交換信息、評估交換后的信息、進(jìn)行下一步的計(jì)算工作，這樣做的一個必然結(jié)果是通信相對集中、形成一個“交通瓶頸”、造成待交換信息的堵塞。而異步并行算法，在分布式多處理機(jī)系統(tǒng)中，可使計(jì)算過程和通信過程重疊成為可能，從而可以運(yùn)用性能優(yōu)越的通信和計(jì)算錯開的方式進(jìn)行消息傳遞。因此，設(shè)計(jì)高效正確的異步并行算法一直是并行處理領(lǐng)域中的主要研究方向之一。異步并行計(jì)算的概念已在共享存貯多處理器系統(tǒng)和少量基于消息傳遞的MIMD系統(tǒng)中成功地用于大型線性方程組問題的求解。與傳統(tǒng)的異步并行算法的策略不同的是，該基于分布式網(wǎng)絡(luò)的算法策略，兼有負(fù)載均衡、同時又可以有效地錯異步并行SRM開計(jì)算和通信的雙重優(yōu)點(diǎn)。應(yīng)用異步并行算法的思想，采用通信和計(jì)算錯開的策略。此處，著重對效果從理論上分析[2]。3.1異步分布式并行算法描述通常，將一個大型計(jì)算任務(wù)，劃分為基于計(jì)算量近似相同的子計(jì)算任務(wù)時，通信相對集中，造成信息交換的堵塞。記一個算法的串行實(shí)現(xiàn)時間為Ts;同樣算法的并行實(shí)現(xiàn)總時間為Tp；那么加速比Sp定義為：而Tp可作如下分解：其中,表示各子任務(wù)作串行計(jì)算的時間的最大值（在該方案中，因?yàn)槭遣捎秘?fù)載基本均衡的分配方法，此處各處理機(jī)的Ts基本相同，它近似為Ts/N,N為處理機(jī)數(shù)量）[3]：TPA表示由于算法并行化過程中額外增加的計(jì)算量，如一個依賴于區(qū)域邊界條件的微分方程求解[7]。進(jìn)行邊界交換信息，修正子域邊界條件，并重新計(jì)算、整合，逐步逼近精確解。迭代步數(shù)取決于區(qū)域的劃分、邊界條件修正的方法等。這種迭代過程便產(chǎn)生了由于并行化而額外增加的計(jì)算量TPA。Tpc表示交換邊界信息時，產(chǎn)生的通信開銷時間。這就是在很多情況下，處理不當(dāng)就會導(dǎo)致并行不如并行的結(jié)果。在現(xiàn)有的有關(guān)基于網(wǎng)絡(luò)的分布并行計(jì)算文章中，多數(shù)研究者的精力主要集中在“如何減少TPA”上，而忽略了Tpc的存在。在基于網(wǎng)絡(luò)環(huán)境的分布式并行計(jì)算實(shí)驗(yàn)中，發(fā)現(xiàn)是影響并行加速比的一個很重要的因素。在充分分析了以太網(wǎng)協(xié)議的基本特征之后，該文提出了一種適用于基于網(wǎng)絡(luò)環(huán)境的分布式并行計(jì)算的異步通信算法模型，并以SRM作為算例加以實(shí)現(xiàn)，取得了很好的效果。在算法的并行化過程中，為了提高并行計(jì)算效率，現(xiàn)在普遍采用的一個措施就是要求任務(wù)劃分負(fù)載均衡，不致于部分理機(jī)處于閑置狀態(tài)。這種思路主要是考慮到減少，如果確實(shí)做到了負(fù)載絕對均衡，至少從直觀上來看，每個處理機(jī)都在滿負(fù)荷工作，肯定比有部分處理機(jī)處于閑置狀態(tài)工作效率高。但是人們在追求負(fù)載均衡的時候，卻忽略了Tpc的負(fù)作用。當(dāng)各負(fù)載均衡性能相似的處理機(jī)作分布式網(wǎng)絡(luò)并行計(jì)算時，幾乎是同時完成了各子任務(wù)的計(jì)算，等待邊界信息的交換。而基于以太網(wǎng)的局域網(wǎng)是總線結(jié)構(gòu)，也就是說在同一時間，只允許一個信號在信道上傳輸，當(dāng)所有處理機(jī)同時要求交換信息時，結(jié)果是誰都不能通信，按CSMA技術(shù)原則，只有等待一個隨機(jī)的時間之后再去競爭信道。這種沖突和競爭，將會使Tpc成為影響Tp的一個極重要的因素。而在通信完成之后，每臺處理機(jī)執(zhí)行自己的計(jì)算時間，信道處于空閑。異步分布式并行計(jì)算方法，其實(shí)質(zhì)是在保證負(fù)載均衡的前提下，有效地錯開通信時間。它既可以保證系統(tǒng)負(fù)載均衡，又可以充分利用傳輸信道資源，解決好信道“沖突-競爭-空閑的問題。可用如下的示意圖表示兩不種情況下的解決方案。在方案2中，通信和計(jì)算是異步進(jìn)行的。在同一時間內(nèi)，在沒有局域網(wǎng)上其它主機(jī)參與信道競爭的情況下，只有兩臺主機(jī)參與通信，線路暢通、效率極高，而其它計(jì)算機(jī)可以執(zhí)行獨(dú)立的計(jì)算子任務(wù)。理論分析和實(shí)驗(yàn)均表明，以上方案將分布式并行中通信開銷時間降到了最低限度[1]。3.2加速比及并行效率分析理想狀態(tài)，也即無通信開銷的狀態(tài)，在分布式并行計(jì)算情況下實(shí)際上是不存在的。為了模擬此環(huán)境，假定算法并行化時，各處理機(jī)均利用固定的虛擬邊界條件進(jìn)行計(jì)算。即不進(jìn)行邊界交換，只做獨(dú)立的并行計(jì)算。此處，給出理想狀態(tài)下的理論分析。在理想狀態(tài)下，SRM算法的加速比、并行效率分別為：假設(shè)求解區(qū)域劃分為N*N個網(wǎng)格，在一臺處理機(jī)作串行計(jì)算時，其計(jì)算量近似為：N*N*a，其中a為每個結(jié)點(diǎn)所需要的計(jì)算量。當(dāng)使用P臺處理機(jī)作并行計(jì)算時，如圖5所示，從水平方P個子域，每個子域內(nèi)包含有(N/P+1)*N個結(jié)點(diǎn)，從而計(jì)算量為(N/P+1)*N*a；可得理想狀態(tài)下，其加速比理論值為：由上式，可得并行效率為：3.3異步分布式并行SRM算法的加速比及并行效率異步分布式并行算法考慮到了通信量，但按前面所提的思路，盡量錯開通信時間，可使通信開銷降到最低限度。異步分布式并行算法的加速比、并行效率分別為：假設(shè)求解區(qū)域劃分為N*N個網(wǎng)格，在一臺處理機(jī)作串行計(jì)算時，其計(jì)算量近似為：N*N*a；其中a為每個結(jié)點(diǎn)所需要的計(jì)算量。當(dāng)使用P臺處理機(jī)作并行計(jì)算時，如圖5所示，從水平方向劃分為P個子域，每個子域內(nèi)包含有（N/P+1）*N個結(jié)點(diǎn)，而計(jì)算量為由于通信交換信息的過程是異步進(jìn)行的，基本上消除了信中的等待和沖突。當(dāng)P->∞時，異步分布式并行SRM算法的加速比、并行效率分別為：其中，表示邊界上重復(fù)的計(jì)算量，一般為O（N）,Tpc為邊界上交換信息的通信時間。由此不難看出，隨著處理機(jī)的增加，各處理機(jī)的子計(jì)算任務(wù)迅速減少，計(jì)算時間變小，而通信相應(yīng)頻繁，從而又出現(xiàn)了處理機(jī)花大量的時間在等待通信。此處要強(qiáng)調(diào)的是等待通信，因?yàn)椴捎卯惒酵ㄐ偶夹g(shù)，使得沒有沖突存在。但不管怎樣，Tpc是變大了（用于等待）。4提高并行效率的方法