一、并行模型的設計

PBRT是由Matt Pharr 和Greg Humphreys完成的一個經(jīng)典的光線追蹤程序，它十分注重于光線追蹤算法的效率。而光線追蹤算法的一個最大的難點就是其性 能問題，算法中需要對每個像素點進行光線的反向追蹤，并且反向追蹤時每碰到一個物體，就要考慮其表面的反射、折射等現(xiàn)象。其中存在大量的并行機會，因此 并行化一直是光線追蹤算法的一個研究熱點問題。光線追蹤算法的并行化，有兩種基本思路：一是依次對每個像素點的光線追蹤進行并行，同時執(zhí)行多個相鄰像素點的光線追蹤，這種方法并行粒度較細，并行 時負載平衡性較好，但只能串行的獲取每個像素點；二是將要生成的圖片分塊，同時執(zhí)行多個塊中的不同像素點的光線追蹤，這種方法并行粒度較大，可以并行獲 取每個像素點，但是負載可能不夠平衡。針對以上情況，PBRT設計并實現(xiàn)了一種集中上面兩種方法的優(yōu)點的并行模型。假定計算是在提供一致性共享內(nèi)存的處理器 上運行的，選用Linux下的pthread線程作為共享內(nèi)存并行程序的實現(xiàn)方法。一致性共享內(nèi)存的主要思想是所有線程都可以讀寫一組公共的內(nèi)存位置，并且一個線 程對內(nèi)存的更改最終將由其他線程看到。如下圖1所示，在所設計的模型中，光線追蹤要生成的圖片被劃分成幾個子塊，每個子塊對應一個子任務，所有的子任務組成n個子任務隊列，每個子任務隊列 分別含有m個子任務，n個線程分別從n個子任務隊列中依次獲取自己的子任務執(zhí)行。初始時，每個子任務隊列均含m個子塊，作為m個子任務，當線程執(zhí)行完自己子 任務隊列中的所有子任務時，向子任務管理器申請從別的子任務隊列中調(diào)撥新的子任務，如失敗，則結(jié)束執(zhí)行。圖1 線程并行執(zhí)行模型

并行模型充分利用前面提到的兩類并行模型的優(yōu)點：n和m足夠大時，可以保證子塊足夠小，相應的子任務粒度足夠細，且并行時所有線程的負載具有較好的平 衡性；同時各個線程各自獨立地獲取子任務，相互之間可以并行執(zhí)行。線程和子任務管理器的相應算法的偽代碼如下所示：線程i的執(zhí)行算法： void thread_unit_run(int i){ while(true){ pthread_mutex_lock(locki); if(get_subtask(i)){//獲取子任務進行光線追蹤 pthread_mutex_unlock(locki); Run_subtask(i); }else{ pthread_mutex_unlock(locki); If(sub_task_adjust(i)==false)break;//通過子任務管理器申請調(diào)撥新的子任務 } } } 子任務管理器執(zhí)行算法： Boolean sub_task_adjust(int i){ If(存在j){//子任務隊列j中有剩余的子任務 pthread_mutex_lock(locki); pthread_mutex_lock(lockj); 從j中取部分子任務到i中 pthread_mutex_unlock(lock); pthread_mutex_unlock(locki); Return true; }else Return false; }

二、并行模型的實現(xiàn)

更加具體一點，PBRT中的所有多核并行性都是通過使用ParallelFor()函數(shù)并行for循環(huán)表示的。在應用啟動的時候，由ParallelInit()函數(shù)創(chuàng)建n個線程， 所有線程初始化完成后就讓它進入等待狀態(tài)，直到有任務喚醒它為止。然后由ParallelFor()函數(shù)把任務放到工作列表中，并和線程池中的線程一起完成任務。因 為調(diào)用ParallelFor的線程也是資源，不能讓它空閑，和線程池中的線程一起工作，這樣也能加快速度。最后由workerThreadFunc()函數(shù)負責讓工作線程執(zhí)行任 務。取任務這個操作是被互斥體包圍的，取完之后，真正執(zhí)行任務的時候，互斥體就會被釋放。在任務執(zhí)行的過程中，其他線程可以從工作列表中獲取任務執(zhí)行 （即多線程）。完成任務后，繼續(xù)獲得互斥體繼續(xù)循環(huán)看看是否還有任務。ParallelInit函數(shù)代碼： void ParallelInit() {CHECK_EQ(threads.size(), 0);int nThreads = MaxThreadIndex();ThreadIndex = 0;/* 創(chuàng)建一個屏障，以便在我們從該函數(shù)返回之前，確保所有工作線程都通過了對 ProfilerWorkerThreadInit（）的調(diào)用。反過來，我們可以確保直到所有工作線 程 都完成了這一操作之后，才會啟動分析系統(tǒng)。 */std::shared_ptr<Barrier> barrier = std::make_shared<Barrier>(nThreads);//啟動的工作線程比我們要做的工作線程總數(shù)少一個，因為主線程也有幫助。 for (int i = 0; i < nThreads - 1; ++i)threads.push_back(std::thread(workerThreadFunc, i + 1, barrier));barrier->Wait(); } 圖2 ParallelFor()函數(shù)程序框圖

圖3 workerThreadFunc()函數(shù)程序框圖

三、并行化輸出問題

并行化能明顯提高性能，加快運行速度，但隨之而來的如何確保串行程序并行化后的正確性成為了一個難點問題。并行程序由于自身特點，會導致即使完全并 行化正確，其輸出結(jié)果也可能和串行程序不一致。影響程序并行化后的輸出的問題，主要包含下面三類：（1）數(shù)據(jù)沖突：指多個線程在沒有鎖保護的情況下讀寫同一內(nèi)存區(qū)域，導致某些線程不能得到正確的讀寫結(jié)果。PBRT通過采用互斥和原子內(nèi)存操作來解決多 個執(zhí)行線程正在訪問共享的已修改數(shù)據(jù)時的同步問題。互斥是在pbrt中用std:：mutex對象實現(xiàn)的。mutex可以用來保護對某些資源的訪問，確保一次只有一個線 程可以訪問它。而原子內(nèi)存操作是通過多個線程正確執(zhí)行這種類型的內(nèi)存更新的另一種選擇。原子是機器指令，可確保它們各自的內(nèi)存更新將在單個事務中執(zhí)行。（2）隨機數(shù)生成器：PBRT中采用了一種稱為Mersenne Twister的隨機數(shù)生成器。當進行并行化后，每個像素點進行光線追蹤時采用的隨機數(shù)會和原來串行 時不一致，這樣也就導致了并行前后輸出的結(jié)果不一致。為了消除隨機數(shù)生成器對輸出結(jié)果的影響，方便對數(shù)據(jù)沖突的消除，對串行PBRT中生成的隨機數(shù)進行了 profiling，并行后對每個像素點采用其串行時profiling的隨機數(shù)，這樣消除隨機數(shù)生成器導致的并行前后輸出結(jié)果的不一致，以使最后輸出完全一致。（3）浮點數(shù)運算：在PBRT中，為了充分實現(xiàn)反走樣技術(shù)，采用MSAA，對屏幕上每個像素點，計算其周圍4個像素點的平均值作為該像素點的值。并行執(zhí)行一 個像素點周圍的4個點的光線追蹤時，如果這4個點的值的計算速度不一致，則計算平均值時進行加運算的順序不一致，由于這些值都是浮點數(shù)，這樣會導致即使4 個點的值分別和串行時一致，其平均值也可能和串行時的不一致。因此，PBRT在并行化過程中，通過對每個像素周圍的4個點進行編號，根據(jù)編號計算其平均值， 這樣便消除了驗證時對輸出結(jié)果的影響。

四、性能優(yōu)化

在解決上述問題后，我們只是得到了一個初步認為正確的并行PBRT程序，但此時的并行并行PBRT程序性能并不高。偽共享是共享內(nèi)存編程中一種常見的性能 瓶頸。雖然變量共享在功能上是正確的，但是由于變量的共享會導致頻繁的Cache失效，也就成為了整個程序性能的瓶頸。在PBRT中的偽共享主要分為兩類：一類是共享的變量被多個線程反復修改，每個線程修改時，為了維護Cache數(shù)據(jù)的一致性，則需要更新運行其他線程的CPU 的Cache上擁有的該數(shù)據(jù)；另一類是在內(nèi)存中相鄰位置的多個變量如果在同一Cache塊中，當此Cache塊上的數(shù)據(jù)共享時，如果被不同的線程更改時，也會產(chǎn)生偽共 享現(xiàn)象。針對第一類問題，PBRT的解決思路是將線程中用到的這些變量進行線程私有化，每個線程有自己的統(tǒng)計變量，只有當這些線程結(jié)束后，才將該線程統(tǒng)計的結(jié)果 添加到全局統(tǒng)計變量中。針對第二類問題，PBRT采用數(shù)據(jù)填充解決，基本思想是將位于同一Cache塊上的變量分布到不同的內(nèi)存區(qū)域，不再出現(xiàn)位于Cache塊上的現(xiàn)象，以此來消除偽 共享。舉例說明，在并行PBRT中，有一些整數(shù)變量，如lastMailboxId和curMailboxId，用于保存光線追蹤的中間結(jié)果。并行時多個像素點的光線并發(fā)追蹤，需要 更多空間保存光線追蹤的中間結(jié)果，一個較為直觀的方法就是將其擴充為數(shù)組lastMailboxId[ThreadNum]和curMailboxId[ThreadNum]。不同的線程根據(jù)自己 的線程id訪問相鄰的數(shù)組元素，由于這些相鄰的元素很大可能會位于同一Cache塊，此時就會產(chǎn)生偽共享問題。PBRT利用C++中數(shù)組按行存儲的特性將這些保存中 間結(jié)果的數(shù)組分別填充為二維數(shù)組lastMailboxId[ThreadNum][N]和curMailboxId[ThreadNum][N]，但是只使用每行的第一個元素lastMailboxId [ThreadNum][0]，并且調(diào)整N的大小使每行元素各占一個Cache塊，這樣便不會再發(fā)生偽共享。

參考

[1]1.4 pbrt的并行化
[2]A.6并行性

總結(jié)

以上是生活随笔為你收集整理的PBRT并行化研究的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。