張薇薇，楊懌菲

（西安郵電大學電子工程學院，西安　710121）

?

多光源并行化算法的實現*

張薇薇，楊懌菲

（西安郵電大學電子工程學院，西安710121）

摘要：針對在繪制具有真實感的圖形中光照處理模塊串行處理速度慢的問題，提出多光源光照算法的并行化，采用負載均衡的并行策略，重新優(yōu)化計算模型，單獨計算環(huán)境光、散射光、鏡面光及衰減因子后疊加在一起。計算不同的PE（處理單元）個數使用了不同的分配方案來提高處理速度。實驗結果表明，將多光源光照算法并行化，可充分利用資源，發(fā)揮多核處理器的處理能力，提高了資源利用率。

關鍵詞：多光源，并行化，真實感

0　引言

在計算機圖形學和虛擬現實中，真實感圖形的繪制技術是研究的熱點之一［1-2］，廣泛應用于電子游戲開發(fā)、醫(yī)學、飛行模擬等眾多領域，而光照處理對于繪制具有真實感的圖形來說至關重要，如果沒有光照，很多物體沒有真實效果，通過合理地使用光源、定義物體表面的材料特征，可以模擬真實場景，產生多種不同的視覺效果。光照渲染是真實場景繪制的一個重要組成部分，在眾多行業(yè)中都有廣泛的應用，是目前研究的熱點之一［3-5］。并行算法是適合于并行操作的一類算法總稱，它通常由一些可同時執(zhí)行的進程來表示，這些進程在執(zhí)行過程中相互作用與協調工作，以完成對給定問題的求解［6-9］。我國自20世紀80年代起開始對真實感圖形繪制進行研究，對光照技術的研究也有所發(fā)展［10］。文獻［10］對一類具有復雜非直接光照的場景提出了一種稱作Ercuts的全局光照算法。算法不僅考慮了直接光照，也考慮了物體之間的相互作用。

現有的研究中，對光照算法或并行算法單獨進行研究得居多，將二者結合在一起的很少，本文重點研究多光源光照算法的并行化，將并行算法應用于光照算法中，通過PAAG（Polymorphous Array Architecture Graphic），一種適用于圖形圖像處理的高效陣列機結構，為多光源光照并行算法的實現和仿真驗證提供依據。根據負載均衡的原則，將環(huán)境光、散射光和鏡面光的計算映射到多個處理器上，多個處理器協同工作同時求解，降低了問題的復雜度并提高了運算速度，另外還對并行算法的效果進行了比較和分析，通過加速比來分析并行計算效果，從而實現算法的并行化。

1　 Phong模型

Phong光照模型是真實圖形學中提出的第一個有影響的光照明模型，該模型只考慮物體對直接光照的反射作用，認為環(huán)境光是常量，沒有考慮物體之間相互的反射光，物體間的反射光只用環(huán)境光表示。Phong光照模型屬于簡單光照模型。簡單光照模型僅考慮光源直接照射在景物表面所產生的光照效果，并且景物表面通常被假定為不透明，且具有均勻反射率。

Phong光照模型是一種典型的簡單光照模型。Phong模型的計算公式如下［3］：

其中，Ipa為環(huán)境光亮度，ka為環(huán)境反射系數（0≤ka≤1），Ipd為光源垂直入射時反射光的光亮度，i為光源入射角，kd為漫反射系數，Ips為入射光的光亮度，ks為鏡面反射系數，θ為鏡面反射方向和視線方向的夾角，n為鏡面反射光的會聚指數（與物體表面光滑度有關）。由上式看出，一旦反射光中3種分量的顏色以及它們的系數ka、kd和ks確定以后，從景物表面上某點達到觀察者的反射光顏色就僅僅和光源入射角和視角有關。

2光照算法

對光照算法的并行處理則將需要工作分離成離散部分，這有助于同時解決，隨時并及時地執(zhí)行多個程序指令，將計算時間縮短。并行算法根據公式中的相加部分將算法分解為多個部分，分別計算環(huán)境光、散射光、鏡面光和衰減因子這4種成分，單獨計算后疊加在一起。

2.1環(huán)境光成分

環(huán)境光沒有源頭，方向不能確定，但卻存在亮度。環(huán)境光成分就是光源的環(huán)境顏色根據材料的環(huán)境屬性進行縮放后的值［4］。

其中ambient表示環(huán)境光，ambientlight指光源的環(huán)境顏色，ambientmaterial指材料的環(huán)境屬性。

2.2散射光成分

散射光來自一個方向，光的強度不僅取決于材料還取決于光源的位置。散射光成分需要考慮光線是否照射在頂點上、光源的散射顏色以及材料的散射屬性［4］：

其中L=（Lx，Ly，Lz）是從頂點到光源位置的單位向量，n=（nx，ny，nz）是頂點的單位法向向量，diffuselight為光源的散射顏色，diffusematerial為材料的散射屬性。

2.3鏡面光成分

如果不考慮鏡面光，盡管場景圖像有明暗和三維效果，但表面看起來缺少高亮區(qū)域，高亮區(qū)域是由光澤對象反射形成的。表面越光滑，反射效果越像一面鏡子。鏡面光成分還取決于光線是否直接落在頂點上。如果L·n小于等于0，頂點上就不存在鏡面光（如果這個值小于0，表示光線位于表面的另一面）。如果存在鏡面光成分，它的值取決于如下因素［4］：

其中，shininess為鏡面指數，specularlight為鏡面顏色，specularmaterial為材料的鏡面屬性。

2.4衰減因子

考慮到距離因素，光從光源發(fā)射到表面，光強會隨著距離d增大而逐漸衰減，取決于光源位置和頂點間的距離d，常量衰減因子kc，線性衰減因子kl，二次衰減因子kq因素，而考慮到光源是否為聚光燈光源，需要判斷光源是否為聚光燈以及頂點是否位于聚光燈的光錐范圍之內，如果是范圍之內則還要考慮頂點指向聚光燈的單位向量、聚光燈的方向和聚光燈的切角因素。

衰減因子和聚光燈效果公式如下［4］：

綜上，將以上結果進行疊加，頂點的顏色=頂點處的材料發(fā)射顏色+全局環(huán)境光（在頂點處根據材料環(huán)境顏色屬性進行縮放）+經過適當衰減的來自所有光源的環(huán)境、散射和鏡面光成分［12］。在執(zhí)行光照計算之后，顏色值將在［0，1］的范圍之內。

總公式如下［4］：

頂點顏色=emissionmaterial+ambientlightmodel×ambientmaterial+

3并行實現

3.1并行算法

并行算法根據不同類別的問題和并行機體系結構而有不同的特征。一個好的并行算法不僅要適應并行計算機硬件結構，而且要反映所要解決的問題的內在并行性。對于并行計算，有一個非常重要的原則，那就是盡可能地增加運行時間的比例，同時降低通信頻率。如果多個處理單元之間的通信可以同時發(fā)生，程序的執(zhí)行效率將大大提升。

染色算法的并行性可以體現在兩個方面：數據并行和任務并行。本文采用了兩者相結合的策略，提出了一種并行染色算法，提高了硬件利用率的同時減少數據通信量，該算法適于處理數據密集型任務，如圖像處理、頂點染色。使系統吞吐量提升到一個較高的水平。

要完成上述的光照計算，計算量很大，傳統的GPU中用多個頂點染色器進行計算，本文采用的是多態(tài)陣列的體系結構處理器（PAAG）［8］來實現并行染色。

圖1　PAAG陣列處理器結構

PAAG陣列處理器如圖1所示，這是一種適用于圖形圖像處理的高效并行陣列及結構。該結構的處理單元陣列機系統是由多個處理器簇組成，每個簇是由16個處理單元組成的4*4陣列，處理單元由近鄰互聯組成（PE）組成的一個二維陣列。每一行有行控制器，每一列也有列控制器用來實現行列的運算。這些使得此種陣列機能夠實現效率很高的線乘級并行運算、數據級并行運算和操作級并行運算。

為了程序的驗證，采用PAAG處理器的仿真系統、編譯系統及調試環(huán)境，分析時則使用了其性能分析參數提取工具。這一套完整的軟件開發(fā)工具為程序的執(zhí)行以及性能的分析提供了可靠的保證。

串行計算可以先進行向量的標準化和衰減因子及聚光燈效果的計算，之后進行散射光、鏡面光和環(huán)境光成分的運算，也可以改變它們的順序，本文列出了其中的一種算法順序如圖2所示：

圖2　串行算法流程圖　圖3　初步并行算法流程圖

由于各個部分計算量不同，簡單的劃分會導致負載不均衡影響算法效率，圖3為初步并行算法流程圖，本文采用了一種負載較為均衡的并行策略，重新優(yōu)化任務如圖4所示，將鏡面光的所需向量S1，S2的計算放到另一個處理單元（PE）中，并將發(fā)射光與全局光的計算與合并放在同一個PE里，此種方法同時保證了數據的相關性。

圖4　并行算法流程圖

3.2實驗分析和結果

通過Amdahl定律［13］可以以數值的方式直觀地反映出系統在性能上的提升。它定義了采用某種加速措施所取得的加速比［14-15］。

加速比反映了使用增強措施后完成一個任務比不使用增強措施完成同一個任務加快的比率。具體公式如下：

理想的加速比是隨著處理器核數的增加，并行執(zhí)行倍數也相應地倍增。在實際應用中，并行的加速比很難符合理論的數值。

3.3單燈并行算法

對于單燈，運用不同的PE個數和不同的任務分配得到的加速比是不同的。提高PE的個數就能提高加速比，經過仿真可知，在PE個數增加到8個后，再多增加PE個數，對加速比的提升并沒有明顯的效果，本文對單燈采用8個PE，如圖5所示：

圖5　8 PE并行結構

PE0：將頂點值、光源位置的值賦給PE4。

PE4：進行向量標準化的計算。將所需向量頂點指向聚光燈的單位向量標準化，后將結果送入PE5。

PE5：將頂點到光源位置的單位向量，頂點指向觀察點的向量標準化，并將這兩個向量的和規(guī)范化，將結果送入PE6。

PE6：根據傳送過來的計算鏡面光的所需向量值，根據鏡面光的計算公式算出鏡面光，將結果送入PE10中。

PE9：算出散射光所用向量，并根據公式和所需值計算出散射光并傳入PE10中。

PE10：綜合PE6、PE9、PE11、PE14中的值，計算出來最終光照結果即RGB值。

PE11：進行衰減因子的運算。根據衰減因子的計算公式及所給的具體量值，將衰減因子求出，并則將結果送入PE10。

PE14：根據所給條件，聚光燈方向、聚光燈切角等算出聚光燈效果，之后將計算結果送入PE10。

表1　8PE并行結果

經過仿真，對單燈采用1個PE時，需要的時間是1 368個工作單位。運用8個PE時，由表1可知，PE10運行的總時間較長，需要475個工作單位，由此可以算出單燈并行的加速比為2.88。

3.4 8盞燈并行算法

按照1PE運行1單盞燈的并行算法：

圖6　8PE并行結構

如圖6所示，每個PE計算一盞燈，將最終結果相加，按照8盞燈來算，如果按照一個PE運行一盞燈，即PE0計算第1盞燈、PE1第2盞燈、PE2第3盞燈、PE3第4盞燈、PE4第5盞燈、PE5第6盞燈、PE6第7盞燈、PE7第8盞燈，8個PE同時運行，最終結果相加即可。

表2　8盞燈并行結果

按照圖2所示對8盞燈的串聯進行仿真，得到的運行時間為11 128個工作單位。8盞燈并聯時，由表1可知，PE7運行時間最長為1 491個工作單位，故得到8盞燈并行的加速比為7.46。

3.5本文提出的并行處理方法

由PAAG處理器可知，PAAG處理器是可以進行擴展的，能夠組成高層的簇結構。目前可達1 024個處理單元。每個行控制器和列控制器帶有自己的程序存儲，具體的擴展方式如圖7所示。

圖7　基本簇的擴展方式

一個簇可以運行兩盞燈，這樣4個簇則可以同時運行8盞燈，8盞燈串聯時運行時間為11 128個工作單位，由表1可知一盞燈最長運行時間為475個工作單位，可以得到加速比為23.43。

由下頁表3可以看出，并行程序的執(zhí)行時間有明顯變化。當計算規(guī)模相對較小只有一盞燈的時候，并行程序的加速比最高只能到2.88，表明對小規(guī)模的計算并行化不占優(yōu)勢，而變成8盞燈的時候，加速比最大達到了23.43，可以看出，隨著規(guī)模的增大并行程序和串行程序的時間差有了明顯的變化，這表明相對大規(guī)模的計算并行化效果顯著。

在實際的工作生產中，當有大量的頂點數據存在時，一個簇可同時運行兩個頂點，按照單盞燈單個頂點的速度處理，如果同時送入兩個頂點的數據時，運行速度則可翻倍，而當同時送入多個頂點的數據時，速度則可大大增加，小規(guī)模計算并行化并不占優(yōu)勢，而大規(guī)模的計算并行化效果顯著。

表3　4簇8盞燈運行加速比

4　結論

本文詳細敘述了光照算法在多核處理器上的并行實現，具體描述并行算法的分配方案以及每個處理器的執(zhí)行過程和具體步驟，介紹了評價并行化效果的指標加速比。對于多盞燈來講，不同的并行結構，會得到不同的加速比，本文提出的并行方案，可使加速比達到23.43，相對于原有的并行結構加速比為7.46，提高了很多。加速了原本運算，提高了資源利用率。對于光照算法來說，小規(guī)模的并行化不占優(yōu)勢，大規(guī)模的計算并行效果會更顯著。

參考文獻：

［1］李繼芳.實用計算機圖形學［M］.北京：清華大學出版社，2012.

［2］陸玲.計算圖形學［M］.北京：電子工業(yè)出版社，2012.

［3］杜璽倫，譚家萬.真實感圖形學中的光照模型研究綜述［J］.電子技術與軟件工程，2014（1）:111-113.

［4］李偉偉，董杰，李海霞，等.多光源實時全局光照算法的實現［J］.吉林大學學報，2011，29（2）：135-140

［5］劉艷麗，楊美燕，邢冠宇，等，一種魯棒的實時室外光照估計算法［J］.計算機輔助設計圖形學學報，2013，25（6）:767-773.

［6］王蕾，崔慧敏，陳莉，等.任務并行編程模型研究與進展［J］.軟件學報，2013，24（1）:77-90.

［7］徐曉東，趙建亭，徐春雷.實時多任務并行計算系統的容錯技術［J］.計算機工程與應用，2013，49（9）:33-36.

［8］牟少敏，杜海洋，蘇平，等.一種改進的快速并行細化算法［J］.微電子學與計算，2013，30（1）:53-55.

［9］林宇晗，孔繁鑫，徐惠婷，等.線性加速比并行實時任務的節(jié)能研究［J］.計算機學報，2013，36（2）:384-391.

［10］朱振興，徐曉旸，潘金貴.一種復雜非直接光照場景的渲染算法［J］.計算機科學，2010，37（12）:227- 229.

［11］張建強.基于任務并行策略的多核程序優(yōu)化研究［D］.大連：遼寧師范大學，2011.

［12］李濤，肖靈芝.面向圖形和圖像處理的輕核陣列機結構［J］.西安郵電學院學報，2012，17（3）:41-47.

［13］唐思敏，黨杰，鐘升.基于SIMD PE陣列的圖像同態(tài)濾波并行算法［J］.西安工程大學學報，2010，24（3）:302-305.

［14］LI T.A polymorphic array architecture for graphics and image processing［C］//2012 5th Int.Symp.Parallel Architectures，Algorithms and Programming，Dec.2013，Taipei，IEEE Computer Society CPS，2013.

［15］LI H，WANG L.Parallel programming languages on multi-core and many-core architectures［J］.Information Technology Letter，2012，10（1）:23-30.

Study and Implementation of Lighting Parallelization Algorithm

ZHANG Wei-wei，YANG Yi-fei
（School of Electronic Engineering，Xi’an University of Posts and Telecommunications，Xi’an 710121，China）

Abstract：According to slowly serial processing speed in the photorealistic rendering technology，the paper proposes many lights processing.Using parallel strategy of load balancing and optimizing calculation mode，ambient light、diffuse light and specular light are added when they are calculated separately.Different number of PE（processing unit）with different schemes is to improve the processing speed .The experimental results show that the parallelization of many lights can make a better use of resources and the processing power of multicore processors.The optimizing of the processing from serial computing into parallel computing accelerate the original operation，as well as resource utilization.

Key words：many lights，parallelization，sense of reality

作者簡介：張薇薇（1978-），女，陜西戶縣人，碩士，講師。研究方向：計算機圖形學。

*基金項目：國家自然科學基金（61301196）；陜西省教育廳科研基金（11KJ0932，14KJ1672）；西安郵電大學中青年基金資助項目（ZL2014-14）

收稿日期：2015-02-21修回日期：2015-04-26

文章編號：1002-0640（2016）03-0111-05

中圖分類號：TP391

文獻標識碼：A