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