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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

17、程操作，我們將實(shí)現(xiàn)更完美的加速和并行效率。如何將PVM機(jī)制整合入CSCW系統(tǒng)，是更進(jìn)一步的應(yīng)用，也將被繼續(xù)研究下去。參考文獻(xiàn) 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