探討平行與優化技術於熱輻射法 (下)

contents

  1. 1. 平行設計 Parallel Design
    1. 1.1. Single-Source Parallel Algorithm
    2. 1.2. Multi-Source Parallel Algorithm
  2. 2. 展示結果 Demo
    1. 2.1. 平行效能比較
  3. 3. 參考論文 Reference
  4. 4. 後記 Note
  5. 5. 致謝 Thanks

接續上一篇

平行設計 Parallel Design

回顧原始算法,為了加快收斂速度,每一次會挑選單位面積能量最多的三角形 $f$ ,之後便拿所有三角形 $t$ 進行傳導,直到傳導能量小於閥值,迭代將停止。算法如下所述:

1
2
3
4
5
6
while (not converge) {
f = PickMaxRadiosityTriangle()
foreach triangle t in model
shader(f, t);

clearRadiosity(f)
}

在嘗試傳遞的過程中,若三角形 $f$ 的三頂點的能量差異大,則選擇自適應切割三角形,直到三頂點能量差異小,這麼計算 Form-Factor 才會正確。在自適應部份,切割方法如下圖所示:

當偵測到綠色三角形 $A$ 頂點之間的 Form-Factor 差異過大時,使用最長邊的中點切割,這麼做是盡可能產生銳角三角形,為了圖形完整,必然也要對鄰居切割。為減少計算量,只算新增中心點 $P$ 的 Form-Factor。對於下方的三角形 $B$ 而言,分成兩種情況,已在這一輪完成計算,則重新計算 Form-Factor;相反地,不做任何事。

Single-Source Parallel Algorithm

我們發現計算 Form-Factor 相當獨立的,但自適應處理需要遞迴切割,因此選用多核心平台,而非通用圖形處理器平台,因為目前的 GPU 實作遞迴所需的 stack 使用 global memory 作為存取位址,所以一般多核心平台效果會更好。在這一次報告中,我們選用 OpenMP 這套跨平台多執行緒 API 進行實驗。

著手將多個三角形平行處理,意即每一個執行緒負責多個三角形的 Form-Factor 計算。

1
2
3
4
5
6
// Single-Source Parallel Algorithm
while (not converage) {
f = PickMaxRadiosityTriangle()
parallel foreach triangle t in model
shader(s, t);

clearRadiosity(f)

Multi-Source Parallel Algorithm

從原始算法中,我們發現到每一次迭代將只有一個熱源輻射到場景中,當場景有多個高能量熱源時,場景必須經過好幾次迭代才能近似最終結果。藉由平行處理的效能,我們可以一次迭代多熱源,便可將低執行緒之間分配工作不均的情況,不僅僅前幾次迭代就能近似最終結果,同時也能加速運算。

1
2
3
4
5
6
7
8
9
10
// Multi-Source Parallel Algorithm
while (not converge) {
set<Triangle> f = RadiosityTriangleCandiateCandidate();
parallel foreach triangle t in model
if (f.find(t))
continue;
foreach s in f
shader(s, t);
clearRadiosity(f);
}

我們所用的平行方無法搭配上述自適應的切割方案,其原因在於分裂過程中,同時也要對鄰居三角形分裂,整個圖形產生的節點與邊的關係才會正確,無法保證鄰居在同一執行緒內處理,若沒有做好空間切割,我們便無法處理這部份。若模型格式會是數個獨立的物體,而非單純的三角形資訊,可分配每一個執行緒處理多個獨立物體,我們預期可以達到更好的效果。

平行過程中每一個執行緒共享和衝突的區段越少越好,這意味著我們必須在運行輻射前就必須將模型切得相當細緻。特別注意到,切得細緻與否對於光線投射 (Ray Casting) 複雜度不變,因為邏輯上他們處理同一平面。

一旦切得細緻,傳遞的效果就不是這麼好,在邊界的陰影更加顯著。根據理論和實作層面推測,其一原因是能傳遞的總能量隨著迭代減少,那麼從分裂過程中傳遞能量採用較多的加法完成,相較於多個 32-bit floating point 誤差就少了許多。

我們也試著使用獨立的切割方案─重心切割,切割的結果不依賴鄰居,只需要在加入三角形清單部份使用 critical section 即可,效能影響並不大。

根據重心切割,下述實驗中,從 156 個三角形,自動分裂到 30000 個三角形後進行輻射的結果如下圖所示:

明顯地,根據重心的切割方法容易產生鈍角三角形,看起來就會像很多紡錘體。在眾多數學性質中,只使用重心也許不是好的解決方案,這是値得探討的一部份,由於製作上的時間限制,我們並沒有去探討各個不同切割方案,所對應的自適應的效果如何。

Longest Edge Center

展示結果 Demo

只使用優化技術渲染結果

blocks room
hall church

平行效能比較

在 Intel Xeon E5-2620 v3 上,我們測試不同平行度帶來的影響,由於只有兩個實體 CPU,每一個 CPU 有 6 個核心,每個核心皆有 Hyper-threading 技術,故可產生 24 個執行緒。

Single-Source Parallel Algorithm - Scalability

我們對模型 room.tri 以預先切割 14977 個三角形後,根據先前提到的平行算法 Single-Source Parallel Algorithm,即是迭代一次只取一個熱源,平行計算所有三角形到此熱源的 Form-Factor 値,針對不同的執行緒個數和運行時間記錄,結果如上圖。在由於過多的執行緒可能會帶來更多的 false sharing,造成資料在不同的 CPU 之間運行 data transmission,所以效果就逐漸不明顯。

Multi-Source Parallel Algorithm - Scalability

接著,我們測試 Multi-Source Parallel Algorithm,以 room.tri 預先切割 50017 個三角形後,每次迭代皆取數個熱源,平行計算所有三角形到所有被選取熱源的 Form-Factor 的總和。同樣地,因為查找的資料重複存取的模式造成不好的影響,類似上述所提到的 false sharing 影響,故會呈現一種陡坡。

參考論文 Reference

後記 Note

當我們進行平行效能比較時,要特別小心編譯器行為的差異,意即平行處理 $P$ 控制時,當 $P=1$ 時,使用平行版本比較合適。因為有時候,平行部分的函數被編譯器偵測到,由於分享記憶體的關係,部分代碼無法優化,導致效能瞬間慢個四到五倍都是有可能的,再加上 false sharing 的關係,更有可能在發生密集計算時,效能更加低落。

在不同平台上的情況也有所不同,例如在一般 server 上運行時,CPU 頻率通常都會比一般 PC 慢上許多,又因為很多個 CPU 導致總共的快取大小遠比一般 PC 多,所以平行效能將會受限於運行的應用行為,是否需要時常存取大量的資料。

致謝 Thanks

一開始在挑選主題相當困惑,畢竟使用 Unity 可以做出更生動的作品,但作品的元素和創意相當重要,相當迷惘於要選哪一種類型才好。如果要兩人以上一起做,那麼主題又不能太過狹隘。百般思慮下,還是由我拉選了這個主題下來做。

「我可能會扯你後腿,還是我們各別做?」組員擔心地說道

不用擔心,我自己也沒信心將所有程序都看完且修改更好更快,每天都焦頭爛額地煩惱整份程序的運作,深怕來不及在時限內完成足夠的報告份量。

「快來幫幫我啊,在身邊一起 trace 程序也好,咱的記憶體不足啊。」內心如此吶喊

一起修課的博班學長給了我們一些意見與鼓勵,而學弟們只會在一旁扯後腿問「學姊今天會來嗎?」最後,我們完成了整份程序的理解與討論。