20100428 并行計(jì)算模型和任務(wù)分解策略

1、第三章 并行計(jì)算模型和任務(wù)分解策略首先，我們將研究不同類型的并行計(jì)算機(jī)，為了不嚴(yán)格限定于某個(gè)指定機(jī)型，我們通過(guò)模型把并行計(jì)算機(jī)抽象為幾個(gè)特定屬性。為了說(shuō)明并行程序中處理器之間的通信概念模型我們討論了不同的程序模型，另外為了分析和評(píng)估我們算法的性能，我們討論了多計(jì)算機(jī)架構(gòu)下評(píng)估并行算法復(fù)雜度的代價(jià)模型。在介紹并分析的各種代價(jià)模型的基礎(chǔ)上給出了改進(jìn)型的代價(jià)模型。其次我們定義這樣幾個(gè)指標(biāo)如負(fù)載均衡和網(wǎng)絡(luò)半徑等用來(lái)研究圖分解問(wèn)題的主要特性。并把圖分解問(wèn)題歸納為一般類型和空間映射圖類型。我們重點(diǎn)研究的是后者，因?yàn)槎喑叨扰渲谜鎸?shí)感光照渲染算法可以很方便的描述成空間映射圖形式。3.1 并行計(jì)算機(jī)模型以下給出

2、并行計(jì)算機(jī)的模型的概述，根據(jù)其結(jié)構(gòu)并行計(jì)算機(jī)大致可分為以下幾類。多計(jì)算機(jī)(Multicomputer)：一個(gè)von Neumann計(jì)算機(jī)由一個(gè)中央處理器(CPU)和一個(gè)存儲(chǔ)單元組成。一個(gè)多計(jì)算機(jī)則由很多von Neumann計(jì)算機(jī)通過(guò)互聯(lián)網(wǎng)絡(luò)連接而成的計(jì)算機(jī)系統(tǒng)。見圖3.1。每個(gè)計(jì)算機(jī)(節(jié)點(diǎn))執(zhí)行自己的計(jì)算并只能訪問(wèn)本地的存儲(chǔ)。通過(guò)消息實(shí)現(xiàn)各計(jì)算機(jī)之間的互相通訊。在理想的網(wǎng)絡(luò)中，兩個(gè)計(jì)算節(jié)點(diǎn)之間的信息傳送代價(jià)與本地的計(jì)算節(jié)點(diǎn)和它的網(wǎng)絡(luò)阻塞無(wú)關(guān)，只和消息的長(zhǎng)度相關(guān)。以上多計(jì)算機(jī)和分布式存儲(chǔ)的MIMD機(jī)器之間的主要區(qū)別在于后者的兩個(gè)節(jié)點(diǎn)間的信息傳輸不依賴于本地計(jì)算和其它網(wǎng)絡(luò)阻塞。分布式存儲(chǔ)的MIM

3、D類型的機(jī)器主要有IBM的SP, Intel的Paragon, 曙光4000系列, Cray的T3E, Meiko的CS-2, NEC的Cenju 3, 和nCUBE等。通過(guò)本地網(wǎng)絡(luò)的連接的集群系統(tǒng)可以認(rèn)為是分布式存儲(chǔ)的MIMD型計(jì)算機(jī)。多處理器(Multiprocessor)：一個(gè)多處理器型并行計(jì)算機(jī)(共享存儲(chǔ)的MIMD計(jì)算機(jī))由大量處理器組成，所有的處理器都訪問(wèn)一個(gè)共同的存儲(chǔ)。理論上理想的模型就是PRAM模型(并行的隨機(jī)訪問(wèn)系統(tǒng))，即任何一個(gè)處理器訪問(wèn)任一存儲(chǔ)單元都是等效的(見圖3.2)。并發(fā)存儲(chǔ)訪問(wèn)是否允許取決于所使用的真正的模型【34】?；旌夏Ｐ停悍植际焦蚕泶鎯?chǔ)(DMS)計(jì)算機(jī)，提供了

4、一個(gè)統(tǒng)一的存儲(chǔ)訪問(wèn)地址空間但是分布式物理存儲(chǔ)模塊。編譯器和運(yùn)行時(shí)系統(tǒng)負(fù)責(zé)具體的并行化應(yīng)用。這種系統(tǒng)軟件比較復(fù)雜。 圖3.1 多計(jì)算機(jī)模型 圖3.2 PRAM 模型SIMD計(jì)算機(jī)：在一個(gè)SIMD(單指令流多數(shù)據(jù)流)計(jì)算機(jī)中在不同數(shù)據(jù)流階段所有的處理器執(zhí)行同樣的指令流。典型的機(jī)型有MasPar的MP, 和聯(lián)想機(jī)器CM2。多計(jì)算機(jī)系統(tǒng)具有良好的可擴(kuò)展性，價(jià)格低廉的集群式并行計(jì)算機(jī)就屬于這種模型，本文中的算法主要基于多計(jì)算機(jī)體系結(jié)構(gòu)。3.2 程序模型并行程序的編程語(yǔ)言如C或Fortan。并行結(jié)構(gòu)以某種類庫(kù)的形式直接整合進(jìn)這些編程語(yǔ)言中。編程模型確定了并行程序的風(fēng)格。一般可分為數(shù)據(jù)并行、共享存儲(chǔ)和消息傳

5、遞等模型35。數(shù)據(jù)并行編程：數(shù)據(jù)并行模型開始于編寫同步SIMD并行計(jì)算機(jī)程序。程序員需要在每個(gè)處理器上獨(dú)立執(zhí)行一個(gè)程序，每個(gè)處理器均有其自己的存儲(chǔ)器。程序員需要定義數(shù)據(jù)如何分配到每個(gè)局部存儲(chǔ)中。實(shí)際應(yīng)用中大量的條件分支的需要使得其很難高效的運(yùn)行在SIMD型的機(jī)器上。共享存儲(chǔ)編程：共享存儲(chǔ)模型是一個(gè)簡(jiǎn)單的模型，因?yàn)槌绦騿T寫并行程序就像寫串行程序一樣。一個(gè)程序的執(zhí)行與幾個(gè)處理器獨(dú)立，也不需要同步。一個(gè)處理器的執(zhí)行狀態(tài)獨(dú)立于其它處理器的運(yùn)行狀態(tài)。由于所有運(yùn)行程序均訪問(wèn)統(tǒng)一的全局存儲(chǔ)器，這就需要小心處理任何一個(gè)處理器需要訪問(wèn)的數(shù)據(jù)都必須和其它處理器的訪問(wèn)之間沒有任何沖突。消息傳遞模型：我們把消息傳遞模

6、型和SPMD(單一程序多數(shù)據(jù))應(yīng)用技術(shù)結(jié)合使用。每個(gè)程序獨(dú)立在幾個(gè)處理器上執(zhí)行，不需要同步(MIMD系統(tǒng))。每個(gè)程序均立即訪問(wèn)本地存儲(chǔ)，通過(guò)消息傳遞實(shí)現(xiàn)遠(yuǎn)程的存儲(chǔ)訪問(wèn)。通信方式主要有一下幾個(gè)不同類型：點(diǎn)對(duì)點(diǎn)通信(point-to-point communication)：一個(gè)處理器發(fā)送一個(gè)數(shù)據(jù)包到另一個(gè)處理器，使用發(fā)送操作，目標(biāo)處理器必須調(diào)用一個(gè)接受操作獲得這些數(shù)據(jù)。我們假定一個(gè)處理器可以同時(shí)和其它處理器通信，我們還假定一個(gè)處理器在同一時(shí)間只能和一個(gè)處理器通信。且通信為異步，也就是說(shuō)接收處理器可以在發(fā)送操作完成后的任意時(shí)間調(diào)用接收命令。集合通信(collective communication

7、)：集合通信涉及到多處理器之間的通信。投射(cast)：一個(gè)處理器同時(shí)拷貝同樣的信息到其它多個(gè)處理器的過(guò)程。聚合(combine)：組內(nèi)每個(gè)處理器只負(fù)責(zé)發(fā)送整個(gè)數(shù)據(jù)段的一部分，由一個(gè)主處理器接受所有結(jié)果，這個(gè)過(guò)程需要一個(gè)額外的數(shù)據(jù)統(tǒng)計(jì)數(shù)據(jù)項(xiàng)的個(gè)數(shù)。M個(gè)處理器之間的集合通信可以通過(guò)大量的點(diǎn)對(duì)點(diǎn)通信以樹形方式在時(shí)間內(nèi)完成，這里假定每個(gè)處理器之間的通信物理鏈路均是獨(dú)立的。對(duì)于并行語(yǔ)言的實(shí)現(xiàn)方面，很多的研究工作在對(duì)現(xiàn)有的串行程序語(yǔ)言的基礎(chǔ)上進(jìn)行擴(kuò)展以實(shí)現(xiàn)并行化計(jì)算方面作出了大量有益的嘗試，如HPC+36或HPF 37等試圖在C+或Fortran語(yǔ)言中應(yīng)用不同的程序模型?，F(xiàn)在把并行性能整合到現(xiàn)有的編成語(yǔ)

8、言中的一個(gè)可行方案就是給對(duì)語(yǔ)言提供能實(shí)現(xiàn)并行處理和通信的運(yùn)行庫(kù)。這其中關(guān)鍵的挑戰(zhàn)在于擴(kuò)展已有語(yǔ)言中新的語(yǔ)言元素和關(guān)鍵字。目前對(duì)現(xiàn)有語(yǔ)言進(jìn)行并行化擴(kuò)展的工作還處于比較初級(jí)的階段。建立一個(gè)標(biāo)準(zhǔn)去規(guī)范這方面的應(yīng)用是必要的，基于這樣標(biāo)準(zhǔn)可以整合大量不同的計(jì)算模型，因此，使用消息傳遞作為編程模型可以使得程序保持一定的靈活性，隨著將來(lái)并行語(yǔ)言的不斷擴(kuò)充和發(fā)展而已有的并行應(yīng)用方案在不需要修改。本文采用的編程模型是消息傳遞模型。這在過(guò)去的若干年里業(yè)界已形成了消息傳遞模型的一個(gè)標(biāo)準(zhǔn)MPI【38，39】。當(dāng)前很多超級(jí)計(jì)算機(jī)實(shí)現(xiàn)了大量高效的MPI應(yīng)用。采用免費(fèi)、高效、可移植性好的稱之為MPICH的并行編程語(yǔ)言構(gòu)建適

9、用于集群系統(tǒng)的并行計(jì)算的應(yīng)用，可以使得我們基于MPI的應(yīng)用可以很容易的移植到其它很多并行計(jì)算環(huán)境中。3.3 代價(jià)模型確定了基于消息傳遞模型進(jìn)行并行算法的設(shè)計(jì)，接著就需要分析該算法的算法復(fù)雜度。對(duì)于算法復(fù)雜度問(wèn)題，由于大量不同類型的超級(jí)計(jì)算機(jī)的存在使得統(tǒng)一且能準(zhǔn)確預(yù)測(cè)一個(gè)算法的特性幾乎不可能。因此我們必須指定一個(gè)代價(jià)模型作為我們的分析依據(jù)。顯然這個(gè)模型應(yīng)該盡可能模擬當(dāng)前的超級(jí)計(jì)算機(jī)的性能結(jié)構(gòu)。前人已在該領(lǐng)域做了大量的工作來(lái)定義一般的代價(jià)模型，使得我們可以通過(guò)該模型準(zhǔn)確預(yù)測(cè)并行算法的復(fù)雜性，而不用考慮編程模型或使用哪種硬件。首先介紹目前比較常見的幾種并行計(jì)算代價(jià)模型，接著在同步性、通信方式和參數(shù)等

10、3個(gè)方面對(duì)它們作一簡(jiǎn)單分析比較。詳細(xì)的概述文章見【40】。本文采用的機(jī)器模型是多計(jì)算機(jī)，該模型包括了p個(gè)獨(dú)立的處理器，每個(gè)只能訪問(wèn)其本地的存儲(chǔ)。處理器間異步工作且通過(guò)一個(gè)由處理器對(duì)之間的雙向通信鏈路連接而成的網(wǎng)絡(luò)進(jìn)行通信。以點(diǎn)對(duì)點(diǎn)方式通信，例如，一個(gè)處理器發(fā)送數(shù)據(jù)包到另一個(gè)處理器，就是用send操作。目標(biāo)處理器調(diào)用receive操作接收數(shù)據(jù)。衡量點(diǎn)對(duì)點(diǎn)通信的代價(jià)的方法很多，下面介紹一些主要方法。真正具有大規(guī)模處理器的超級(jí)計(jì)算機(jī)不會(huì)給每對(duì)處理器之間提供獨(dú)立的物理的通信鏈路。而是采用處理器之間的通道共享方式。如果兩處理器對(duì)之間需要同時(shí)占用該通道進(jìn)行通信時(shí)就會(huì)發(fā)生消息阻塞。由于這種阻塞和特定的網(wǎng)絡(luò)拓

11、撲結(jié)構(gòu)有關(guān)，所以以下一般代價(jià)模型沒有考慮這些問(wèn)題。但我們將在第3.4.3中討論如何避免或減少阻塞的一般方法。這還考慮了在分布式存儲(chǔ)模型上整合其它的作為原子操作的通信類如涉及到群組處理器之間的集合通信。顯然這些通信可以通過(guò)大量的點(diǎn)對(duì)點(diǎn)通信方式得到。我們只使用點(diǎn)對(duì)點(diǎn)的通信模式，使得我們的算法不需要依賴那些需要更高效的專門的硬件支持集合通信。3.3.1 Postal模型Postal【67】模型主要用來(lái)描述具有下面3個(gè)方面特點(diǎn)的消息傳遞的通信系統(tǒng)：完全連通、同時(shí)IO和通信延遲。一個(gè)帶有n個(gè)處理機(jī)和通信延遲的消息傳遞系統(tǒng)有下面3個(gè)屬性：(1)完全的連通性。系統(tǒng)中的每一個(gè)處理機(jī)能夠向系統(tǒng)中的任何其他處理機(jī)

12、發(fā)送點(diǎn)對(duì)點(diǎn)消息；(2)同時(shí)的IO。一個(gè)處理機(jī)p可以在給處理機(jī)q發(fā)送消息的同時(shí)接收處理機(jī)r發(fā)送來(lái)的消息；(3)通信延遲。如果在t時(shí)刻處理機(jī)P向處理機(jī)q發(fā)送我消息M則P在時(shí)間間隔內(nèi)忙于發(fā)送消息M，而且q在時(shí)間間隔內(nèi)忙于接收消息M。上面是從處理機(jī)的觀點(diǎn)來(lái)分析一個(gè)消息傳遞系統(tǒng)。在這樣的一個(gè)系統(tǒng)中，處理機(jī)之間靠通過(guò)一個(gè)通信網(wǎng)絡(luò)互相發(fā)送和接收消息來(lái)通信，這樣就產(chǎn)生了一個(gè)抽象的全連通的系統(tǒng)。而在很多系統(tǒng)中，通過(guò)不同的輸人輸出端口，處理機(jī)確實(shí)可以同時(shí)發(fā)送和接收消息。在Postal模型中，message被用來(lái)表示一個(gè)在處理機(jī)之間進(jìn)行通信的不可分割的數(shù)據(jù)單元，一個(gè)message在發(fā)送的時(shí)候、傳輸?shù)臅r(shí)候和接收的時(shí)候

13、都不能被分成更小的快。一個(gè)原子message被定義為一個(gè)數(shù)據(jù)大小的單元，而發(fā)送或者接收一個(gè)message的時(shí)間被定義為一個(gè)時(shí)間單元。發(fā)送大塊數(shù)據(jù)的時(shí)候，這些數(shù)據(jù)會(huì)首先被分成多個(gè)message，每個(gè)message都被單獨(dú)地發(fā)送和接收，這在許多報(bào)文交換系統(tǒng)(packet switching)中都是一種標(biāo)準(zhǔn)的實(shí)現(xiàn)。上面所說(shuō)的通信延遲中包括各方面的系統(tǒng)開銷，具體來(lái)說(shuō)包括消息準(zhǔn)備時(shí)間、輸出緩沖拷貝時(shí)間、輸出端口提交延遲、網(wǎng)絡(luò)傳輸延遲、輸人端口延遲、輸人緩沖拷貝時(shí)間和消息中斷時(shí)間。這里的通信延遲還包括所有的軟件開銷和硬件開銷。從形式上來(lái)說(shuō)，的值為消息M的發(fā)送方開始發(fā)送消息到接收方完全接收完消息所用的時(shí)間。

14、盡管從形式上來(lái)說(shuō)是這樣，可實(shí)際的精確值可能取決于實(shí)際的發(fā)送接收組和宴際通信網(wǎng)絡(luò)的負(fù)載；通常，的值應(yīng)該是相對(duì)固定不變的，不同的處理機(jī)之間不能有很大的浮動(dòng)。3.3.2 BSP 模型根據(jù)BSP (bulk synchronous parallel)66模型，一個(gè)并行計(jì)算機(jī)由下面3部分組成：第一，若干個(gè)存儲(chǔ)器或者處理機(jī)組件;第二,這些組件之間的點(diǎn)對(duì)點(diǎn)通信；第三，這些組件之間的同步機(jī)制。為簡(jiǎn)單起見，可以認(rèn)為每個(gè)組件中包含一個(gè)處理機(jī)和本地存儲(chǔ)器；在模型中，不要求關(guān)于通信系統(tǒng)、互連網(wǎng)絡(luò)和同步系統(tǒng)的額外信息。在BSP模型中，一個(gè)并行系統(tǒng)由下面3個(gè)參數(shù)來(lái)表示：(1)P，系統(tǒng)中處理機(jī)的數(shù)目；(2)g，把通信開銷轉(zhuǎn)

15、換為計(jì)算開銷的因子；(3)L，兩個(gè)同步之間的最短時(shí)間。連續(xù)的兩個(gè)同步之間的周期被定義為超步(superstep)。在一個(gè)超步中一個(gè)處理機(jī)可以進(jìn)行3個(gè)操作：首先各處理機(jī)處理本地存儲(chǔ)器中的數(shù)據(jù)，可以是本地計(jì)算；然后各處理機(jī)向別的處理機(jī)提出遠(yuǎn)程內(nèi)存讀寫請(qǐng)求，而通信實(shí)際發(fā)生在超步中的時(shí)間是不可預(yù)知的；最后，所有處理機(jī)進(jìn)行障柵同步，本次超步的數(shù)據(jù)通信僅當(dāng)同步以后有效。在BSP模型中，計(jì)算操作的總量用處理機(jī)在計(jì)算過(guò)程中所做的基本操作的數(shù)目來(lái)表示，通信量則用字?jǐn)?shù)來(lái)表示。假設(shè)在同一次計(jì)算和通信中數(shù)據(jù)項(xiàng)的大小是一樣的，而且假設(shè)在一個(gè)超步中的通信總量是被發(fā)送或者接受的最大字?jǐn)?shù)。通過(guò)因子g，通信開銷被轉(zhuǎn)換成計(jì)算開銷

16、，其中g(shù)是系統(tǒng)中計(jì)算帶寬與通信帶寬的比值。具體地說(shuō)，就是每個(gè)處理機(jī)發(fā)送或者接收至多h個(gè)字的開銷與在相同的時(shí)間內(nèi)進(jìn)行加次計(jì)算操作。L表示連續(xù)的兩次同步之間所能執(zhí)行的操作的次數(shù)，它的具體值由同步操作的實(shí)現(xiàn)和上層算法來(lái)決定。同步操作使得超步之間相互無(wú)關(guān)，根據(jù)BSP模型實(shí)現(xiàn)的算法的總開銷就是所有超步開銷的總和，而每一個(gè)超步的開銷由該超步中計(jì)算開銷和通信開銷所決定。BSP模型的一個(gè)不足之處在于處理器的同步只在superstep之間。一個(gè)消息在一個(gè)superstep開始時(shí)發(fā)送只能被用于下一個(gè)superstep，即使superstep的長(zhǎng)度比網(wǎng)絡(luò)延時(shí)還要長(zhǎng)；另一個(gè)缺點(diǎn)就是這個(gè)模型不能統(tǒng)計(jì)消息注入網(wǎng)絡(luò)的時(shí)間。

17、這些不足可由以下模型彌補(bǔ)。3.3.3 LogP 模型LogP【68】是一個(gè)能很好地符合并行計(jì)算機(jī)系統(tǒng)中這種分布式存儲(chǔ)、多處理器網(wǎng)絡(luò)通信機(jī)制的計(jì)算模型。利用LogP模型，通過(guò)4個(gè)重要參數(shù)就可以設(shè)計(jì)良好的適應(yīng)不同處理器的算法。這4個(gè)參數(shù)及含義如下：(1)P(處理器存儲(chǔ)模塊的個(gè)數(shù))設(shè)處理器進(jìn)行本地操作的單位時(shí)間為一個(gè)周期；(2)L(最大通信延遲) 即從源模塊到目的模塊傳輸包含一個(gè)字或幾個(gè)字的信息所用的時(shí)間；(3)o(通信開銷)即一個(gè)處理器發(fā)送一個(gè)信息所用的時(shí)間長(zhǎng)度，在此時(shí)間段中處理器不能執(zhí)行其它操作；(4)g(通信間距) 即一個(gè)處理器連續(xù)進(jìn)行信息收發(fā)的最小時(shí)間間隔，g的倒數(shù)對(duì)應(yīng)于通信帶寬。在LogP

18、模型中，通信網(wǎng)絡(luò)被認(rèn)為有有限的能力，因此在某一個(gè)時(shí)刻至多只有Lg消息從任何處理機(jī)到任何別的處理機(jī)。如果某個(gè)處理機(jī)嘗試傳輸消息時(shí)超過(guò)這個(gè)限制，這個(gè)超出的消息將被延遲，直到網(wǎng)絡(luò)中別的消息已經(jīng)傳送完畢后再傳輸。性能參數(shù)L、o和g都用處理機(jī)操作的周期數(shù)來(lái)表示。LogP模型是異步的，延遲也只有一個(gè)上限，按一定的順序發(fā)出的消息到達(dá)時(shí)的順序可能不一致。并且假設(shè)所有的消息都是短消息。這些參數(shù)的選擇是在忠實(shí)地獲得實(shí)際機(jī)器的執(zhí)行特點(diǎn)、提供一個(gè)有效的算法設(shè)計(jì)和分析的框架之問(wèn)取一個(gè)折衷。參數(shù)取得太少，不能很好地描述系統(tǒng)的特點(diǎn)；但參數(shù)取得太多，又會(huì)使算法的設(shè)計(jì)變得異常困難。在不同的情況下，LogP模型中的各個(gè)參數(shù)也可以

19、適當(dāng)?shù)鼗?jiǎn)來(lái)降低系統(tǒng)的復(fù)雜性。這是因?yàn)樵诓煌那闆r下，各個(gè)參數(shù)的重要性也是不一樣的，在某些情況下可以忽略一個(gè)或者更多參數(shù)，使模型變得更簡(jiǎn)單。比如說(shuō)，在不常進(jìn)行通信的算法中，可以忽略帶寬和網(wǎng)絡(luò)能力有限帶來(lái)的影響；在某些算法中，消息是由長(zhǎng)的數(shù)據(jù)流以流水線的方式通過(guò)網(wǎng)絡(luò)，這可以認(rèn)為消息的傳輸時(shí)間主要受g的限制，而不用考慮通信延遲L；而在某些機(jī)器中，系統(tǒng)的瓶頸是o，則可以認(rèn)為g=o，這樣就可以不考慮g對(duì)算法的影響。LogP模型通過(guò)抽象出來(lái)的4個(gè)參數(shù)來(lái)評(píng)價(jià)一個(gè)互連通信網(wǎng)絡(luò)的性能，使得算法設(shè)計(jì)者不需要關(guān)心具體的網(wǎng)絡(luò)信息，可以更容易地設(shè)計(jì)符合這種模型的算法。3.3.4 LogGP69模型LogGP模型是Lo

20、gP模型的擴(kuò)展，它發(fā)送長(zhǎng)消息的理想模型65。長(zhǎng)消息由一個(gè)新參數(shù)gap表示：對(duì)于長(zhǎng)消息每個(gè)字的間隔，對(duì)于長(zhǎng)消息來(lái)說(shuō)定義為每個(gè)字所需要的時(shí)間。對(duì)于長(zhǎng)消息來(lái)說(shuō)標(biāo)識(shí)每個(gè)處理器的有效通信帶寬。：消息的間隔，定義為在一個(gè)處理器消息的連續(xù)發(fā)送或接收之間的最小時(shí)間間隔，表示每個(gè)處理器處理短消息的有效通信帶寬。在LogP模型中，并不對(duì)長(zhǎng)消息做特別的處理，但是現(xiàn)在許多并行計(jì)算機(jī)對(duì)長(zhǎng)消息都提供了特別的支持，比如IBM的SP2等。與發(fā)送短消息相比，許多并行機(jī)采用處理長(zhǎng)消息的方法來(lái)達(dá)到更高的帶寬。因此，在LogGP模型中引入了對(duì)長(zhǎng)消息的支持，它比LogP多一個(gè)參數(shù)G，代表長(zhǎng)消息每字節(jié)間距，即發(fā)送長(zhǎng)消息每字節(jié)所需要的時(shí)間

21、，它的倒數(shù)對(duì)應(yīng)于處理機(jī)發(fā)送長(zhǎng)消息時(shí)的帶寬。在新的LogGP模型中發(fā)送一具有個(gè)字的消息需要花費(fèi)周期。發(fā)送和接收的處理器僅在第o個(gè)周期比較忙，其它時(shí)間周期它們都能把通信和計(jì)算重疊進(jìn)行。如果一個(gè)處理器需要在一行中發(fā)送兩個(gè)長(zhǎng)消息，那么在第一個(gè)消息發(fā)出之后和在第二個(gè)消息的首個(gè)字節(jié)傳送到網(wǎng)絡(luò)之前它必須等待周期。3.3.5 改進(jìn)的模型LogP模型是一個(gè)應(yīng)用廣泛的模型，但不太適合發(fā)送長(zhǎng)消息。LogGP模型又比較復(fù)雜，因?yàn)樗雰蓚€(gè)通信間距參數(shù)。我們的目標(biāo)在于定性而不是定量的估計(jì)動(dòng)態(tài)負(fù)載平衡算法的開銷。例如我們將部分使用O標(biāo)記說(shuō)明結(jié)果負(fù)載，對(duì)于這個(gè)結(jié)果如果只關(guān)注短消息和長(zhǎng)消息之間的差別就太學(xué)究味了。為了簡(jiǎn)化計(jì)算

22、我們假定長(zhǎng)消息和短消息之間的間隔相等，即有。這時(shí)發(fā)送具有k個(gè)字的消息的花費(fèi)為。和LogGP模型相比我們假定發(fā)送和接收處理器在周期都很忙。這是合理的，因?yàn)樵O(shè)置一個(gè)長(zhǎng)消息的花費(fèi)要比短消息長(zhǎng)。LogGP模型不包括發(fā)送消息的開始時(shí)間，因?yàn)樗哪康膬H測(cè)量通信開銷，后續(xù)部分我們將以此分析一個(gè)并行算法的整個(gè)開銷，當(dāng)采用長(zhǎng)消息通信時(shí)整個(gè)開銷的確很大。本文中的計(jì)算程序均設(shè)計(jì)為異步通信SPMD風(fēng)格的程序。僅有少量的全局通信的同步點(diǎn)，在這些點(diǎn)之間所有處理器都處于動(dòng)態(tài)平衡負(fù)載的處理狀態(tài)。該程序的延遲幾乎被計(jì)算過(guò)程重疊或略掉。這樣我們將忽略這個(gè)延遲，這樣我們的理論的開銷為：3.4 任務(wù)分解策略我們定義一些指標(biāo)如負(fù)載均衡

23、和網(wǎng)絡(luò)半徑等以此來(lái)研究圖分解問(wèn)題的主要特性。首先概述文獻(xiàn)中對(duì)解決圖分解問(wèn)題所提到的策略，并將之歸納為一般類型和空間映射圖類型。本文主要側(cè)重于后者，因?yàn)檎鎸?shí)感光照渲染算法可以很方便的描述成空間映射圖形式。3.4.1圖嵌入問(wèn)題在并行處理器上部署一個(gè)并行算法，首先要解決圖嵌入問(wèn)題42。假定H代表計(jì)算節(jié)點(diǎn)間通信網(wǎng)絡(luò)拓?fù)鋱D，以此描述處理器的節(jié)點(diǎn)和通信鏈路。一個(gè)任務(wù)圖G表示應(yīng)用的各子進(jìn)程之間的通信需求。把圖G嵌入到并行體系結(jié)構(gòu)H中就產(chǎn)生一個(gè)并行算法，使得應(yīng)用的各子進(jìn)程能較均勻的分配到每個(gè)處理節(jié)點(diǎn)上。衡量把G嵌入到H中后等到的并行算法的性能主要有負(fù)載均衡性，可擴(kuò)展性和阻塞等。下面介紹幾個(gè)關(guān)鍵概念：負(fù)載（lo

24、ad）：每個(gè)處理器具有相同的負(fù)載是圖嵌入問(wèn)題的最重要的目標(biāo)，一個(gè)應(yīng)用的總的運(yùn)行時(shí)間取決于具有最大負(fù)載的處理器的運(yùn)行時(shí)間。膨脹(dilation)：描述了一個(gè)時(shí)間周期(或稱之為路徑長(zhǎng)度)即G中兩個(gè)直連節(jié)點(diǎn)之間的通信消息在H中遍歷所需要的時(shí)間。阻塞(congestion): 測(cè)量路由通過(guò)H中任一條鏈路的G中邊的最大數(shù)量。阻塞從實(shí)踐的觀點(diǎn)看很重要，目前的映射技術(shù)的研究工作很少考慮到阻塞這個(gè)因素。3.4.2 圖分解問(wèn)題圖分解法是圖嵌入問(wèn)題的一個(gè)可能的近似解決方案，分解就是把計(jì)算任務(wù)均衡的分配到各子進(jìn)程中，并得到最小網(wǎng)絡(luò)半徑的過(guò)程。這里沒有考慮任務(wù)簇映射到處理器的過(guò)程，擴(kuò)展的開銷比較小，完全或略阻塞的影

25、響。Bokhari曾把圖分解問(wèn)題（他稱之為映射問(wèn)題43）簡(jiǎn)化為圖的同構(gòu)問(wèn)題，他定義的G的進(jìn)程數(shù)量小于H的節(jié)點(diǎn)數(shù)量，盡管很多研究人員都研究過(guò)這個(gè)問(wèn)題，但其多項(xiàng)式時(shí)間還是未知的。實(shí)踐中經(jīng)常使用啟發(fā)式方法計(jì)算一個(gè)網(wǎng)絡(luò)半徑盡可能低的已經(jīng)非常平衡的任務(wù)分解問(wèn)題。如果G是動(dòng)態(tài)變化的則問(wèn)題變得較復(fù)雜，這樣我們必須動(dòng)態(tài)產(chǎn)生一個(gè)初始的分解方法。圖分解問(wèn)題的一個(gè)完整定義如下。設(shè)G=(V，E)，它代表一個(gè)由頂點(diǎn)V= 和間接邊組成的圖。每個(gè)頂點(diǎn)v的頂點(diǎn)權(quán)重為 。每個(gè)邊有一個(gè)獨(dú)一無(wú)二的邊權(quán)重，頂點(diǎn)/邊的M的權(quán)重 定義為所包含的邊/頂點(diǎn)的權(quán)重之和。圖G被分解為p個(gè)部分，定義為：。衡量分解算法的主要性能指標(biāo)即該圖的平衡性和

26、網(wǎng)絡(luò)半徑。分解的負(fù)載均衡性是一個(gè)關(guān)于 h的元組：如果則這個(gè)分解結(jié)果稱之為負(fù)載均衡。分解的網(wǎng)絡(luò)半徑即橫截面所包括的所有邊的權(quán)重，例如：任務(wù)分解的過(guò)程就是找到一個(gè)具有最小網(wǎng)絡(luò)半徑且負(fù)載均衡的分解方法。一般情況下一個(gè)完美的任務(wù)分解是不會(huì)存在的，我們要做的就是尋找一個(gè)盡可能平衡的分解方案。3.4.3 通信和阻塞一旦一個(gè)應(yīng)用被分解，根據(jù)3.3部分的代價(jià)模型可以找到兩個(gè)處理器之間的高效的通信方法，主要遵循以下幾個(gè)原則：（a）盡可能的使用本地存儲(chǔ)（b）盡可能使得計(jì)算和通信重疊（延遲隱藏）（c）盡量使用長(zhǎng)消息而避免使用較多的短消息。網(wǎng)絡(luò)帶寬參數(shù)對(duì)于一個(gè)處理器由于本地帶寬有限而很少發(fā)消息的情況下影響很有限。如果

27、一個(gè)處理器能了解整個(gè)網(wǎng)絡(luò)情況那么在全局網(wǎng)絡(luò)阻塞嚴(yán)重的情況下就可以決定不發(fā)送消息，既然處理器不了解全局的通信情況，可以執(zhí)行這樣一個(gè)策略即消息被異步且獨(dú)立發(fā)送的地方發(fā)生消息阻塞的概率比較低。然而，一個(gè)同步通信策略在不同階段可以使用高效的集合通信方法如廣播或聚合等操作。哪種策略最好取決于特定問(wèn)題的通信量，以及使用集合通信的潛力。圖 3.3 任務(wù)的空間簇如果通信量需求比較大時(shí)即使使用異步消息傳遞也會(huì)發(fā)生阻塞。顯然，在一個(gè)每對(duì)處理器間直接相連的通信網(wǎng)絡(luò)中，任何兩個(gè)消息和可以相互獨(dú)立發(fā)送且沒有相互干擾。然而，在一個(gè)稀疏網(wǎng)絡(luò)中也存在真實(shí)的相互干擾可能。由于我們關(guān)注與可移植性算法，所以并不打算專注于特定的網(wǎng)絡(luò)

28、拓?fù)?。而且我們希望這個(gè)算法在整個(gè)網(wǎng)絡(luò)上同時(shí)只有很小一部分的鏈接。為此，我們還要增加一個(gè)原則：（d）在同一時(shí)刻僅使用少量的網(wǎng)絡(luò)連接對(duì)于一般的應(yīng)用很難滿足這個(gè)要求，幸運(yùn)的是很多應(yīng)用并不是總體上都是非規(guī)則通信要求。例如，區(qū)域分解計(jì)算如計(jì)算流體動(dòng)力學(xué)或有限元定義位于空間的各任務(wù)間的局部依賴。多尺度配置真實(shí)感光照渲染算法可以被定義成只需要局部通信的并行計(jì)算(參考4.3)。3.5 一般解決方案首先介紹一些圖分解問(wèn)題的一半解決方案。3.5.1 易并行最簡(jiǎn)單的類型即易并行計(jì)算應(yīng)用，在子問(wèn)題之間很少或幾乎沒有相互的依賴45，46，44。這種情況下過(guò)載處理器的任務(wù)就被隨機(jī)發(fā)送到其它未過(guò)載的處理器。目標(biāo)處理器的選擇

29、不會(huì)影響任何子任務(wù)間的獨(dú)立關(guān)系。但基于物理的真實(shí)感渲染顯然不是易并行計(jì)算應(yīng)用，各子問(wèn)題之間存在大量的依存關(guān)系。3.5.2 多用途的圖分解已有很多的文獻(xiàn)在闡述圖分解問(wèn)題的研究成果，這些涵蓋了從基礎(chǔ)性的理論工作53，54到包括快速多層方法的軟件包47，48，52，50，49，51。但這些方法大多只適合靜態(tài)的負(fù)載均衡問(wèn)題，由于負(fù)載是靜態(tài)的，因此任務(wù)只需要在計(jì)算前作一次分解。如果負(fù)載情況經(jīng)常隨著時(shí)間變化而波動(dòng)，經(jīng)過(guò)初始的分解后隨著個(gè)節(jié)點(diǎn)間任務(wù)的平衡性改變后還需要重新平衡各節(jié)點(diǎn)間的計(jì)算任務(wù)55，56，57。過(guò)去，研究人員采用一般圖分解方法去解決真實(shí)感光照渲染算法58，59，60。結(jié)果卻并不理想，一個(gè)可能

30、的原因就是圖分解策略沒有考慮阻塞造成的額外計(jì)算和通信開銷。而空間簇方法則可以有效減少這種阻塞的可能。3.5.3 空間映射圖很多科學(xué)應(yīng)用所定義的應(yīng)用圖，圖的頂點(diǎn)可以自然映射到多維空間中。如果只有所有對(duì)象的一小部分子集時(shí)應(yīng)用就調(diào)用局部通信，而只需要通過(guò)對(duì)象簇的邊緣對(duì)象和其它簇進(jìn)行通信。這種情況下，構(gòu)建空間簇是個(gè)很好的策略（圖3.3）。Figure 3.4：二維的局部任務(wù)通信為了最小化通信量使用能最大限度地減少了表面體積比的簇的形狀。理想的形狀就是一個(gè)超球體，但是，它不可能通過(guò)非重疊的超球體覆蓋整個(gè)空間的表面。如果應(yīng)用需要執(zhí)行較長(zhǎng)距離的遠(yuǎn)程數(shù)據(jù)訪問(wèn)，那么一個(gè)的目錄列表就可以告訴需要那個(gè)處理器那個(gè)任務(wù)

31、，該列表可以被復(fù)制到每個(gè)處理器的局部存儲(chǔ)器中。遠(yuǎn)程數(shù)據(jù)訪問(wèn)和應(yīng)用的局部通信不相互沖突。例如一個(gè)把任務(wù)映射到2D空間的應(yīng)用和每個(gè)任務(wù)和其它共享頂點(diǎn)坐標(biāo)的任務(wù)(圖3.4上半部分)就是局部通信，因?yàn)槿魏稳蝿?wù)只取決于所有任務(wù)中的某個(gè)簇的子任務(wù)。圖3.4的下面顯示規(guī)則的任務(wù)分解，每個(gè)處理器索引都保存著能被簡(jiǎn)單計(jì)算的特定任務(wù)。在一個(gè)不規(guī)則的分解中，一個(gè)目錄列表非常有用，它可以說(shuō)明每個(gè)給定任務(wù)的處理器索引。不幸的是，一般情況下我們只能通過(guò)不規(guī)則的分解獲取良好的負(fù)載平衡性能。膨脹方法61，62在相鄰處理器上保持任務(wù)的連接時(shí)重新映射任務(wù)。相鄰處理器根據(jù)本地負(fù)載的不同而交換負(fù)載。正交遞歸二分法12，17有一個(gè)緊湊

32、的樹形表達(dá)方法。重新平衡操作可以異步且獨(dú)立的在子樹中執(zhí)行70。為了最小化表面對(duì)體積的比率，一個(gè)多維二分策略要比一維簇要好，這因?yàn)橐痪S簇可能產(chǎn)生細(xì)長(zhǎng)條。矩形網(wǎng)格簇如圖3.4 (底部/左面)所示經(jīng)常被用于矩陣和矢量的乘法63。無(wú)法通過(guò)簡(jiǎn)單的移動(dòng)超平面而得到一個(gè)精確的負(fù)載均衡性能。而且任務(wù)必須被隨機(jī)置換為了得到具有高概率的平衡性能64。34 J. Jaja. An Introduction to Parallel Algorithms. Addison Wesley, 1992.35I. Foster. Designing and Building Parallel Programs. Addiso

33、n Wesley, 1995.36HPC+ Consortium. HPC+-homepage. /hpc+/.37 HPF-Forum. HPF-homepage. .38Message-Passing-Interface-Forum. . 39Message-Passing-Interface Forum. MPI: A message-passing interface standard. International Journal of Supercomputing Applications, 1994.40 B. M. Mag

34、gs, L. R. Matheson, and R. E. Tarjan. Models of parallel computation: A survey and synthesis. In Proc. 28th Hawaii Int. Conf. on System Sciences (HICSS-28), volume 2, pages 6170, 1995.41A. Barnoy and S. Kipnis. Designing algorithms in the postal model for message passing systems. In Proc. of the 4th

35、 Annual ACM Symposium on Parallel Algorithms and Architectures, pages 1322, 1992.42B. Monien, R. Diekmann, R. Feldmann, R. Klasing, R. L¨ uling, K. Menzel, T. R¨ omke, and U.-P. Schroeder. Efficient use of parallel & distributed systems: From theory to practice. In J. van Leeuwen, edit

36、or, Trends in Computer Science, Lecture Notes in Computer Science. Springer, Berlin, 1995.43S. H. Bokhari. On the mapping problem. IEEE Transactions on computers, C-30(3), 1981.44M. Adler, S. Chakrabarti, M. Mitzenbacher, and L. Rasmussen. Parallel randomized load balancing. In ACM-SIGACT Symposium

37、on the Theory of Computing (STOC), pages 238247, 1995.45W. Aiello, B. Awerbuch, B. Maggs, and S. Rao. Approximate load balancing on dynamic and asynchronous networks. In Proceedings of the 25th Annual ACM Symposium on Theory of Computing (STOC), pages 632641, May 1993.46R. L¨ uling and B. Monie

38、n. A dynamic distributed load balancing algorithm with provable good performance. In Proc. of the 5th ACM Symposium on Parallel Algorithms and Architectures (SPAA 93), pages 164173, 1993.47B. Hendrickson and R. Leland. Chaco. . 48B. Hendrickson and R. Leland. The Chaco Users Guide Version 2.0. Techn

39、ical Report SAND95-2344, Sandia National Laboratories, Albuquerque, NM 87185-1110, July 1995.49G. Karypis and V. Kumar. Metis multilevel partitioning. / karypis/metis.50G. Karypis and V. Kumar. METIS: Unstructured graph partitioning and sparse matrix ordering system, version 2.0.

40、 Technical report, University of Minnesota, Dept. of CS, Minneapolis, MN 55455, August 1995.51 R. Preis and R. Diekmann. Party partitioning library. . de/cs/robsy/party.html.52C. Walshaw. Jostle mesh partitioning software. 53B. W. Kernighan and S. Lin. An efficient heuristic procedure for partitioni

41、ng graphs. The Bell System Technical Journal, 49:291307, February 1970.54C. M. Fiduccia and R. M. Mattheyses. A linear-time heuristic for improving network partitions. In 19th IEEE Design Automation Conference, pages 175181, 1982.55R. Williams. Performance of dynamic load balancing algorithms for un

42、structured mesh calculations. Con-currency, 3:457481, 1991.56R. van Driessche and D. Roose. An improved spectral bisection algorithm and its application to dynamic load balancing. Parallel Computing, 21:2948, 1995.57P. Diniz, S. Plimpton, B. Hendrickson, and R. Leland. Parallel algorithms for dynami

43、cally partitioning unstructured grids. In Proc. 7th SIAM Conf. Parallel Proc. Sci. Comput., February 1995.58R. Garmann. Paralleles Hierarchisches Radiosity auf der CM-5. Diplomarbeit, Fachbereich Informatik, Universit¨ at Dortmund, Germany, D-44221 Dortmund, November 1994.59R. Garmann, C.-A. Bo

44、hn, and H. M¨ uller. Parallel Hierarchical Radiosity on the CM-5. Technical Report 557, Fachbereich Informatik, Universit¨ at Dortmund, Germany, D-44221 Dortmund, December 1994.60C.-A. Bohn and R. Garmann. A Parallel Approach to Hierarchical Radiosity. In V. Skala, editor, Proceedings of t

45、he Winter School of Computer Graphics and CAD Systems 95, pages 2635, Plzen, Czech Republic, February 1995. University of West Bohemia.61A. Heirich and S. Taylor. A parabolic load balancing method. In Proc. 24th Int. Conf. Par. Proc., volume III, pages 192202, New York, 1995. CRC Press.62C.-Z. Xu and F. C. M. Lau. The general