利用PVM 實現(xiàn)整體光照的并行計算

1、利用PVM 實現(xiàn)整體光照的并行計算 學生學院 計算機學院 專業(yè)班級 11級網(wǎng)絡工程3班 學 號 3111006372 學生姓名 陳俊豪 指導教師 王卓薇 2014年 12 月 27 日利用PVM 實現(xiàn)整體光照的并行計算孫濟洲 1 , Nicolas D Georganas 2(1 .天津大學電子信息工程學院, 天津 ;2 .渥太華大學信息技術(shù)與工程學院, 加拿大)摘要:對利用網(wǎng)絡資源解決復雜且耗時的計算問題做了嘗試.選擇典型的粒子跟蹤整體光照計算問題作為研究對象,提出一種改進的且充分發(fā)掘其內(nèi)在相關(guān)特性的密度估計算法.在以太網(wǎng)連接的多臺微機上, 以PVM(并行虛擬機)機制實現(xiàn)了該算法的并行計算.

2、通過對各項運算性能指標的測試與分析, 結(jié)果顯示可獲得良好的加速比,并且PVM 在分布式網(wǎng)絡并行計算上將有很好的應用前景. 關(guān)鍵詞:并行計算;PVM ;整體光照;分布式網(wǎng)絡盡管硬件的計算速度極大的提高了，但仍有很多尚不能解決的應用問題。這些是復雜的、實時性很高的過程，例如實際圖像生成虛擬或模擬，醫(yī)學上使用的圖像識別和處理，在復雜的表格、結(jié)構(gòu)的設計上的有限元分析。隨著計算機體系結(jié)構(gòu)和V LSI技術(shù)演化，人們能夠通過大型的多處理器并行計算機解決大量問題，不過，想要廣泛應用這門技術(shù)還需很長時間。近年來，對分布式網(wǎng)絡和互聯(lián)網(wǎng)的使用在各種應用領域迅速發(fā)展。基于此，計算機支持的協(xié)同工作（CSCW）系統(tǒng)完成一

3、個大項目，為資源共享、多個用戶之間的信息交流和協(xié)調(diào)提供了一個很好的環(huán)境。除了支持協(xié)同工作，人們還可以在分布式環(huán)境中任何方面進行開發(fā)或借整個網(wǎng)絡資源，以解決上述復雜和耗時的問題，這一點已經(jīng)受到越來越多的關(guān)注。PVM（并行虛擬機）應發(fā)展趨勢而生，它不僅支持一個完整的消息傳遞模型，還能讓分布式工作站和PC結(jié)合成為一臺高性能并行計算機。在本文中，研究目標是整體光照計算問題，它是一個現(xiàn)實的圖像生成的核心，也是一個非常復雜和費時的過程。由于光的現(xiàn)象，如不同的光學特性的表面之間的漫反射，鏡面反射，折射和透射，實驗目標必須模擬全局光照1，它可能需要幾個小時甚至幾天的計算機時間來營造呈現(xiàn)復雜的場景以獲得高質(zhì)量的

4、合成圖像。在這里嘗試利用PVM進行整體光照的并行計算。首先，根據(jù)粒子跟蹤和康奈爾大學2提出密度估計（DE）方法，通過對它固有的并行性進行了探索，改進了DE算法（IDE），可以更方便和更有效的實現(xiàn)并行計算。然后對實驗進行了討論，如任務分配策略和子任務粒度的選擇，其中PVM環(huán)境的建立是為了支持算法及其并行實現(xiàn)。得到的試驗結(jié)果及并行加速性能的分析用來為PVM應用積累經(jīng)驗。試驗結(jié)果表明，該算法是適用的，PVM具有很好的應用前景。它們還為將集成PVM模型整合到分布式協(xié)同虛擬環(huán)境的研究的可行性的奠定了基礎。1 改進的DE算法整體光照算法主要包括有限元法和應用隨機技術(shù)方法，后者分別是獨立視圖和視圖依賴技術(shù)。

5、雖然有限元算法已被完全開發(fā)了很長一段時間，但它不適合用于需要復雜光照來渲染的場景。同時，內(nèi)存和計算帶來的巨大成本，以及曲面細分所帶來的附加誤差，都是有限元法的致命缺點。相比之下,應用隨機技術(shù)如Monte Carlo 方法，優(yōu)點是廣泛的適應性,實現(xiàn)的簡單性,應用隨機技術(shù)正在成為整體光照研究的重點3。DE算法的核心部分就是來自Monte Carlo 方法的密度估計計算。1.1 DE算法DE算法分為三步：粒子跟蹤，密度估計和網(wǎng)格優(yōu)化。2 粒子跟蹤描述能量粒子發(fā)射的整個過程，包括了粒子的反射，折射或吸收。事實上，粒子跟蹤應用Monte Carlo 方法求解位勢方程4,5和獲得對應區(qū)域的通量。在粒子跟蹤

6、后，包含命中點數(shù)據(jù)的文件就建立了。密度估計是用來計算小網(wǎng)格頂點光照和利用核函數(shù)創(chuàng)建包括網(wǎng)格頂點光照數(shù)據(jù)的文件的方法，核函數(shù)認為一個命中點只影響這一周圍地區(qū)的光照。這個方法的關(guān)鍵是選擇合適的核函數(shù)，它代表了受命中點光照影響的任何點，例如Silverman的K 2函數(shù)6.過密的網(wǎng)格必須減少，只保留周圍光強的變化較大的網(wǎng)格頂點，從而提高渲染速度。對此許多網(wǎng)格優(yōu)化的算法已經(jīng)被開發(fā)出來了7。最后，包含緊湊的渲染網(wǎng)格頂點的數(shù)據(jù)的文件就建立了。該文件可以以高氏陰影網(wǎng)狀1的形式存儲，或者可以以圖形工作站上交互顯示，或者可以用于一個附加的射線追蹤通以創(chuàng)建更逼真的、視圖依賴的圖像。1.2改進DE算法DE算法具有強

7、大的并行性。首先，DE算法的三個階段是獨立的、不相關(guān)的，它們可以在同一個管道模式下運行。事實上，這是大型并行粒度的開發(fā)。其次，該算法的每一階段都有很強的并發(fā)性，可以進行加工處理，跟蹤每個粒子就是一個典型的并行子任務。像記錄一定的表面的命中點的密度估計和為場景中的每個表面做網(wǎng)格優(yōu)化這兩個任務就可以同時執(zhí)行。由于密度估計在整個過程中起著重要作用，在改善算法的研究中密度估計將集中在以下的討論。 密度估計，是利用場景中一個表面所有點的數(shù)據(jù)，根據(jù)核函數(shù)方法計算網(wǎng)格頂點的光照。見圖1。本程序有兩個主要的短處，源于利用了表面上所有點的數(shù)據(jù)，這些數(shù)據(jù)數(shù)量是非常龐大的，甚至可以是數(shù)以百萬計的。一方面，由于內(nèi)部存

8、儲器的容量是有限的，點的數(shù)據(jù)必須從內(nèi)部存儲和外部存儲之間的反復轉(zhuǎn)換，導致較低的效率。另一方面，對網(wǎng)格頂點和所有點之間的距離比較的一小部分操作是有用的，因為事實上只有幾點可以影響的網(wǎng)格的頂點光照。此外，當以這種方式計算出的一個表面上的密度估計被分配為并行計算的子任務，效率不會因不同表面上的非常不同的命中點數(shù)量造成的負載不平衡而變高。圖1 基于網(wǎng)格點的密度估計方法因此，我們改變密度估計的模式，從考慮網(wǎng)格的頂點是怎么受所有點的影響，到考慮每個點是怎么影響其附近的網(wǎng)格頂點。就是說，將網(wǎng)格頂點的密度估計過程轉(zhuǎn)變?yōu)橐砸粋€點為基礎的計算程序。在這里，命中點的數(shù)據(jù)將被使用一次，以獲得其周圍的網(wǎng)格頂點部分光照。

9、只有網(wǎng)格頂點坐標和網(wǎng)格的間隔需要保存，其成本非常小的。這樣，命中點的數(shù)據(jù)不應該被頻繁地交換于內(nèi)部和外部存儲器之間。命中點和無關(guān)的網(wǎng)格頂點之間的距離比較如果不影響這個獨特的點的話就不用保存。圖2顯示修改后的密度估計過程。修改后的算法稱為改進的密度估計全局光照算法或IDE短算法。IDE算法適用于并行模式運行，方便而有效。圖2 基于命中點的密度分析步驟2. PVM中IDE算法的并行實現(xiàn)2.1PVM并行計算架構(gòu) PVM是一個有效的機制，使得用戶可以利用分布式網(wǎng)絡中現(xiàn)有的計算資源來支持并行計算來用最小的額外成本解決大問題。在PVM所有的電腦都是工作在動態(tài)的主/從模式。在PVM的任何節(jié)點，當它正在運行一個

10、程序，希望借助網(wǎng)絡中的其他節(jié)點的計算資源，解決一個巨大的問題，可以作為主機，分配任務給其他節(jié)點和從機，來獲取一個快速的解決方案。主機將管理和監(jiān)控他們交換的消息，而從機同時完成子任務分配。節(jié)點之間的通信是基于消息傳遞，也可以通過PVM實現(xiàn)8。 IDE算法其內(nèi)在的并行性和考慮的任務分配的優(yōu)化和負載平衡決定了它非常適合在PVM環(huán)境下實現(xiàn)，在這里，一個子任務是指一定量的命中點的數(shù)據(jù)密度估計的計算，其中所有的子任務應按照自己的計算量排序，以防止降低效率。該算法的并行程序已被精心組織過，其數(shù)據(jù)結(jié)構(gòu)及其參數(shù)，如緩沖和訪問時間的大小，也被仔細選擇過以降低計算成本。2.2任務分配策略 靜態(tài)和動態(tài)策略用于并行計算

11、的任務分配。 在靜態(tài)戰(zhàn)略的實施，主進程根據(jù)命中點和可用的計算元素的總數(shù)讀取命中點和派生從機，給每個從屬進程分配任務。從機完成密度估計計算并將結(jié)果返回給主機，然后終止。上述過程被重復，直到所有的子任務完成。最后，主機收集所有的結(jié)果，并創(chuàng)建一個結(jié)果文件。 申請子任務的機制用于在動態(tài)任務分配的方案。主進程派生一個固定數(shù)目的從屬進程的，為它們分配的子任務與進入的循環(huán)等待狀態(tài)。完成當前子任務之后，從機返回其ID并請求一個新的子任務，然后進入一個閑狀態(tài)，等待下一個子任務。當主機沒有更多的子任務時，從機結(jié)束進程并提交結(jié)果到主機。2.3子任務粒度的選擇 子任務粒度的選擇直接影響并聯(lián)系統(tǒng)的負載均衡。這里，平行粒

12、度是一個子任務的計算量。由于該運算程序?qū)γ總€命中點是相同的，并需要類似的計算量，并行粒度可以根據(jù)命中點和可用的計算資源的數(shù)量來選擇。 為了實現(xiàn)在IDE算法，子任務粒度不會選擇像傳統(tǒng)的那樣為表面上所有擊中點的作密度估計作為一個子任務9。這是因為，只有當場景中每個表面上擊中點的數(shù)字是近似值，這樣的子任務的分區(qū)才是有效的。但是，為不同表面計算的復雜度的巨大差異會導致加載失衡并降低效率。舉例來說，恰好朝向光源的表面的命中點的數(shù)量必然比其他的大。這種表面比其他表面必須花費更長的時間來運算，使得每個處理單元上的負載將是不平衡的，并行計算的效率會較低。另一方面，粒度不能選擇過小，因為對PVM不支持具有非常小

13、的粒度的并行處理8。這樣由于每個處理單元經(jīng)常需要調(diào)度命中點的數(shù)據(jù)，會極大地增加溝通成本。 為降低通信成本并使每一處理器負載平衡，應選擇一個適當?shù)牟⑿辛６?、命中點的數(shù)量有限的子任務。由并行算法的高速化效應，幾個不同大小的粒度都已經(jīng)經(jīng)過測試并且它們的分析將在下面的章節(jié)中給出。在并行算法的執(zhí)行中，粒度的大小還將由任務分配的策略決定，以實現(xiàn)較高并行加速。為靜態(tài)任務分配的并行粒度可以是有點大的，因為從屬進程的數(shù)量是固定的，并且它的靈活性決定了它應該是小的動態(tài)策略。3 實驗和結(jié)果分析 用于場景的IDE算法的并行密度估計的實驗已經(jīng)分別完成了靜態(tài)和動態(tài)任務分配的策略。見圖3。整個測試經(jīng)由以太網(wǎng)使用8個相連的P

14、C（奔騰100和32M字節(jié)存儲器），它運行的是Linux操作系統(tǒng)（RedHat的60.2）和PVM（第3版0.4）的軟件包。使用一個容量為10兆字節(jié)的網(wǎng)卡。圖3測試現(xiàn)場在實驗中，計算速度和總運算速度有效性是怎么被PC的數(shù)目的影響，粒度的大小首先被研究。有效的運算速度是每單位時間為密度估計計算出的命中點的數(shù)量，總的計算速度是有效的運算速度和的總時間的比率。這里的總時間是指計算時間和交流時間。靜態(tài)策略的并行加速示于圖4，其中橫坐標表示所用的PC，在y軸的數(shù)量分別表示有效的計算速度和總運算速度。這里的粒度是1000命中點的密度估計。我們可以發(fā)現(xiàn)，在加速的有效計算速度大約是線性的，而總的計算速度顯顯示

15、緩慢增加。表格1給出了具有不同粒度的總計算時間（單位為秒）的比較;力度越大，總時間越短。圖4 并行加速靜態(tài)任務分配表1 靜態(tài)任務分配的整個計算時間圖5和圖6顯示了加速的動態(tài)任務分配圖5的坐標與圖4是相同的。圖6顯示了不同粒度如何影響加速。我們可以發(fā)現(xiàn)，有效的計算速度是接近線性的增加，總的計算速度緩慢增加。此外，在一定的范圍內(nèi)，子任務越小，加速越好。圖5 并行加速動態(tài)任務分配圖6 動態(tài)任務分配對加速影響任務分配兩種策略被認為是有用的，他們都達到近似線性的加速。在靜態(tài)任務分配的過程中，主機按組創(chuàng)建從機組，僅分配一個單一的子任務到每個從機。這需要大量的啟動和等待時間，將導致并行效率降低。為了避免額外

16、的時間成本，并行粒度為靜態(tài)策略不應太小。但這個策略應該是穩(wěn)健的，能夠簡單地控制和實現(xiàn)。從試驗結(jié)果中看，動態(tài)任務分配的加速比靜態(tài)策略的好得多，并到達了預期的目標。動態(tài)策略避免了過多的時間成本，主機無需等待所有從機完成任務就能發(fā)布新的任務。只要收到從機的人物請求就發(fā)布任務，極大提高效率。動態(tài)策略可引導計算和通信之間時間重疊，并適當降低了粒度，可以使計算和通信的花費更緊密，使效率得到提高。在未來，我們的工作是要設法消除目前并行計算的瓶頸，這意味著改善任務分配策略的。由于主按順序分配從機子任務，從機必須在現(xiàn)在進入循環(huán)等待，無論使用靜態(tài)或動態(tài)策略。如果PVM標準被擴展到支持用于分配用于并行計算任務的多線

17、程操作，我們將實現(xiàn)更完美的加速和并行效率。如何將PVM機制整合入CSCW系統(tǒng)，是更進一步的應用，也將被繼續(xù)研究下去。參考文獻 1 Hearn D,Baker M P .Computer Graphics M .C Version , 2nd Ed.NewYork:Prentice-Hall, 1997 . 2 Shirley P .Global illumination via density estimation A .Proceedings ofEurographics Rendering Workshop C .1995. 3 Veach E .Robust Monte Carlo Me

18、thods for Light Transport Simulation D .Stanford University , 1997 . 4 Kajiya J T .The rendering equation J .Computer Graphics, 1986 , 20(4):143 150 . 5 Pattanaik S N, Mudur S P.Eff icient potential equation solutions for globalillumination computation J .Computers and Graphics , 1993 , 17 (4):387 396 . 6 Silverman B W.Density Estimation for St atistics and Data Analysis M .London and New York :Chapman and Hall , 1986 . 7 Heckbert P S .Simulating Global Illumination Using Adaptive Meshing D .Berkeley :Universit y of Cali