多光源并行化算法的实现*

张薇薇，杨怿菲

（西安邮电大学电子工程学院，西安　710121）



多光源并行化算法的实现*

张薇薇，杨怿菲

（西安邮电大学电子工程学院，西安710121）

摘要：针对在绘制具有真实感的图形中光照处理模块串行处理速度慢的问题，提出多光源光照算法的并行化，采用负载均衡的并行策略，重新优化计算模型，单独计算环境光、散射光、镜面光及衰减因子后叠加在一起。计算不同的PE（处理单元）个数使用了不同的分配方案来提高处理速度。实验结果表明，将多光源光照算法并行化，可充分利用资源，发挥多核处理器的处理能力，提高了资源利用率。

关键词：多光源，并行化，真实感

0　引言

在计算机图形学和虚拟现实中，真实感图形的绘制技术是研究的热点之一［1-2］，广泛应用于电子游戏开发、医学、飞行模拟等众多领域，而光照处理对于绘制具有真实感的图形来说至关重要，如果没有光照，很多物体没有真实效果，通过合理地使用光源、定义物体表面的材料特征，可以模拟真实场景，产生多种不同的视觉效果。光照渲染是真实场景绘制的一个重要组成部分，在众多行业中都有广泛的应用，是目前研究的热点之一［3-5］。并行算法是适合于并行操作的一类算法总称，它通常由一些可同时执行的进程来表示，这些进程在执行过程中相互作用与协调工作，以完成对给定问题的求解［6-9］。我国自20世纪80年代起开始对真实感图形绘制进行研究，对光照技术的研究也有所发展［10］。文献［10］对一类具有复杂非直接光照的场景提出了一种称作Ercuts的全局光照算法。算法不仅考虑了直接光照，也考虑了物体之间的相互作用。

现有的研究中，对光照算法或并行算法单独进行研究得居多，将二者结合在一起的很少，本文重点研究多光源光照算法的并行化，将并行算法应用于光照算法中，通过PAAG（Polymorphous Array Architecture Graphic），一种适用于图形图像处理的高效阵列机结构，为多光源光照并行算法的实现和仿真验证提供依据。根据负载均衡的原则，将环境光、散射光和镜面光的计算映射到多个处理器上，多个处理器协同工作同时求解，降低了问题的复杂度并提高了运算速度，另外还对并行算法的效果进行了比较和分析，通过加速比来分析并行计算效果，从而实现算法的并行化。

1　 Phong模型

Phong光照模型是真实图形学中提出的第一个有影响的光照明模型，该模型只考虑物体对直接光照的反射作用，认为环境光是常量，没有考虑物体之间相互的反射光，物体间的反射光只用环境光表示。Phong光照模型属于简单光照模型。简单光照模型仅考虑光源直接照射在景物表面所产生的光照效果，并且景物表面通常被假定为不透明，且具有均匀反射率。

Phong光照模型是一种典型的简单光照模型。Phong模型的计算公式如下［3］：

其中，Ipa为环境光亮度，ka为环境反射系数（0≤ka≤1），Ipd为光源垂直入射时反射光的光亮度，i为光源入射角，kd为漫反射系数，Ips为入射光的光亮度，ks为镜面反射系数，θ为镜面反射方向和视线方向的夹角，n为镜面反射光的会聚指数（与物体表面光滑度有关）。由上式看出，一旦反射光中3种分量的颜色以及它们的系数ka、kd和ks确定以后，从景物表面上某点达到观察者的反射光颜色就仅仅和光源入射角和视角有关。

2光照算法

对光照算法的并行处理则将需要工作分离成离散部分，这有助于同时解决，随时并及时地执行多个程序指令，将计算时间缩短。并行算法根据公式中的相加部分将算法分解为多个部分，分别计算环境光、散射光、镜面光和衰减因子这4种成分，单独计算后叠加在一起。

2.1环境光成分

环境光没有源头，方向不能确定，但却存在亮度。环境光成分就是光源的环境颜色根据材料的环境属性进行缩放后的值［4］。

其中ambient表示环境光，ambientlight指光源的环境颜色，ambientmaterial指材料的环境属性。

2.2散射光成分

散射光来自一个方向，光的强度不仅取决于材料还取决于光源的位置。散射光成分需要考虑光线是否照射在顶点上、光源的散射颜色以及材料的散射属性［4］：

其中L=（Lx，Ly，Lz）是从顶点到光源位置的单位向量，n=（nx，ny，nz）是顶点的单位法向向量，diffuselight为光源的散射颜色，diffusematerial为材料的散射属性。

2.3镜面光成分

如果不考虑镜面光，尽管场景图像有明暗和三维效果，但表面看起来缺少高亮区域，高亮区域是由光泽对象反射形成的。表面越光滑，反射效果越像一面镜子。镜面光成分还取决于光线是否直接落在顶点上。如果L·n小于等于0，顶点上就不存在镜面光（如果这个值小于0，表示光线位于表面的另一面）。如果存在镜面光成分，它的值取决于如下因素［4］：

其中，shininess为镜面指数，specularlight为镜面颜色，specularmaterial为材料的镜面属性。

2.4衰减因子

考虑到距离因素，光从光源发射到表面，光强会随着距离d增大而逐渐衰减，取决于光源位置和顶点间的距离d，常量衰减因子kc，线性衰减因子kl，二次衰减因子kq因素，而考虑到光源是否为聚光灯光源，需要判断光源是否为聚光灯以及顶点是否位于聚光灯的光锥范围之内，如果是范围之内则还要考虑顶点指向聚光灯的单位向量、聚光灯的方向和聚光灯的切角因素。

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

综上，将以上结果进行叠加，顶点的颜色=顶点处的材料发射颜色+全局环境光（在顶点处根据材料环境颜色属性进行缩放）+经过适当衰减的来自所有光源的环境、散射和镜面光成分［12］。在执行光照计算之后，颜色值将在［0，1］的范围之内。

总公式如下［4］：

顶点颜色=emissionmaterial+ambientlightmodel×ambientmaterial+

3并行实现

3.1并行算法

并行算法根据不同类别的问题和并行机体系结构而有不同的特征。一个好的并行算法不仅要适应并行计算机硬件结构，而且要反映所要解决的问题的内在并行性。对于并行计算，有一个非常重要的原则，那就是尽可能地增加运行时间的比例，同时降低通信频率。如果多个处理单元之间的通信可以同时发生，程序的执行效率将大大提升。

染色算法的并行性可以体现在两个方面：数据并行和任务并行。本文采用了两者相结合的策略，提出了一种并行染色算法，提高了硬件利用率的同时减少数据通信量，该算法适于处理数据密集型任务，如图像处理、顶点染色。使系统吞吐量提升到一个较高的水平。

要完成上述的光照计算，计算量很大，传统的GPU中用多个顶点染色器进行计算，本文采用的是多态阵列的体系结构处理器（PAAG）［8］来实现并行染色。

图1　PAAG阵列处理器结构

PAAG阵列处理器如图1所示，这是一种适用于图形图像处理的高效并行阵列及结构。该结构的处理单元阵列机系统是由多个处理器簇组成，每个簇是由16个处理单元组成的4*4阵列，处理单元由近邻互联组成（PE）组成的一个二维阵列。每一行有行控制器，每一列也有列控制器用来实现行列的运算。这些使得此种阵列机能够实现效率很高的线乘级并行运算、数据级并行运算和操作级并行运算。

为了程序的验证，采用PAAG处理器的仿真系统、编译系统及调试环境，分析时则使用了其性能分析参数提取工具。这一套完整的软件开发工具为程序的执行以及性能的分析提供了可靠的保证。

串行计算可以先进行向量的标准化和衰减因子及聚光灯效果的计算，之后进行散射光、镜面光和环境光成分的运算，也可以改变它们的顺序，本文列出了其中的一种算法顺序如图2所示：

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

由于各个部分计算量不同，简单的划分会导致负载不均衡影响算法效率，图3为初步并行算法流程图，本文采用了一种负载较为均衡的并行策略，重新优化任务如图4所示，将镜面光的所需向量S1，S2的计算放到另一个处理单元（PE）中，并将发射光与全局光的计算与合并放在同一个PE里，此种方法同时保证了数据的相关性。

图4　并行算法流程图

3.2实验分析和结果

通过Amdahl定律［13］可以以数值的方式直观地反映出系统在性能上的提升。它定义了采用某种加速措施所取得的加速比［14-15］。

加速比反映了使用增强措施后完成一个任务比不使用增强措施完成同一个任务加快的比率。具体公式如下：

理想的加速比是随着处理器核数的增加，并行执行倍数也相应地倍增。在实际应用中，并行的加速比很难符合理论的数值。

3.3单灯并行算法

对于单灯，运用不同的PE个数和不同的任务分配得到的加速比是不同的。提高PE的个数就能提高加速比，经过仿真可知，在PE个数增加到8个后，再多增加PE个数，对加速比的提升并没有明显的效果，本文对单灯采用8个PE，如图5所示：

图5　8 PE并行结构

PE0：将顶点值、光源位置的值赋给PE4。

PE4：进行向量标准化的计算。将所需向量顶点指向聚光灯的单位向量标准化，后将结果送入PE5。

PE5：将顶点到光源位置的单位向量，顶点指向观察点的向量标准化，并将这两个向量的和规范化，将结果送入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可以看出，并行程序的执行时间有明显变化。当计算规模相对较小只有一盏灯的时候，并行程序的加速比最高只能到2.88，表明对小规模的计算并行化不占优势，而变成8盏灯的时候，加速比最大达到了23.43，可以看出，随着规模的增大并行程序和串行程序的时间差有了明显的变化，这表明相对大规模的计算并行化效果显著。

在实际的工作生产中，当有大量的顶点数据存在时，一个簇可同时运行两个顶点，按照单盏灯单个顶点的速度处理，如果同时送入两个顶点的数据时，运行速度则可翻倍，而当同时送入多个顶点的数据时，速度则可大大增加，小规模计算并行化并不占优势，而大规模的计算并行化效果显著。

表3　4簇8盏灯运行加速比

4　结论

本文详细叙述了光照算法在多核处理器上的并行实现，具体描述并行算法的分配方案以及每个处理器的执行过程和具体步骤，介绍了评价并行化效果的指标加速比。对于多盏灯来讲，不同的并行结构，会得到不同的加速比，本文提出的并行方案，可使加速比达到23.43，相对于原有的并行结构加速比为7.46，提高了很多。加速了原本运算，提高了资源利用率。对于光照算法来说，小规模的并行化不占优势，大规模的计算并行效果会更显著。

参考文献：

［1］李继芳.实用计算机图形学［M］.北京：清华大学出版社，2012.

［2］陆玲.计算图形学［M］.北京：电子工业出版社，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］林宇晗，孔繁鑫，徐惠婷，等.线性加速比并行实时任务的节能研究［J］.计算机学报，2013，36（2）:384-391.

［10］朱振兴，徐晓旸，潘金贵.一种复杂非直接光照场景的渲染算法［J］.计算机科学，2010，37（12）:227- 229.

［11］张建强.基于任务并行策略的多核程序优化研究［D］.大连：辽宁师范大学，2011.

［12］李涛，肖灵芝.面向图形和图像处理的轻核阵列机结构［J］.西安邮电学院学报，2012，17（3）:41-47.

［13］唐思敏，党杰，钟升.基于SIMD PE阵列的图像同态滤波并行算法［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