基于多核处理器的星空背景弥散效果实现算法

程小华，郑昌文，吴佳泽

（1.中国科学院软件研究所 天基综合信息系统重点实验室，北京100190；2.中国科学院研究生院，北京100190）

0 引 言

模拟生成星空背景图像是空间探测系统仿真的主要内容，其中弥散效果仿真占有重要的一席之地。文献［1－2］描述了白光产生弥散效果的原理，并以此为基础给出了星空背境图像的白光弥散仿真算法；文献［3］给出了一种不同波长的光在星敏感器成像系统上产生的彩色弥散斑实现算法；文献［4］在研究英仙座星团成员星Li丰度弥散的基础上，提出了不均匀红化和恒星活动是引起大部分Li丰度弥散的原因，并在此基础上给出了Li丰度弥散效果实现算法。

现有的星空背景图像主要采用基于单核处理器的星空背景图像实现算法。随着仿真应用范围的不断扩展，星空背景图像实现算法的实时性要求越来越强，同时图像分辨率等指标也不断提升，传统基于单核处理器的星空背景弥散效果实现算法的处理速度已经不能满足实际应用的要求。为了解决这一问题，本文提出一种基于多核处理器的星空背景图像弥散效果实现算法。

1 星空背景弥散效果原理与建模

1.1 星空背景弥散效果原理

本文研究星空背景的弥散效果增加仿真成像效果的真实性。在有限口径透镜成像中，物体上每点射出的光线经过透镜聚焦后在透镜像平面上形成该点清晰的像点。但是如果像平面距离清晰像点一定距离，该点所成的像将会是一个中间亮边缘模糊的光斑，这个光斑称为弥散圈（如图1所示）。

图1 弥散圈形成原理

文献［2］指出弥散圈直径d随着物距u的增大而增大，当u∞时，dv／（f×F）－f／F，其中v是点目标成像的像距，f是相机的焦距，F是光圈系数。在本文中，由于恒星距离遥远，可以认为物距是无穷大。根据光学系统参数计算出弥散圈直径约取值20个像素点，即弥散圆的半径RADIUS值为10。

1.2 星空背景弥散效果仿真建模

恒星亮度利用视星等和绝对星等来度量。视星等是人们从地球上观察星体亮度的度量，每级亮度之间像差2.512倍。因为不同恒星与地球的距离不同，所以视星等并不是反映恒星本身的发光亮度。绝对星等是假定把恒星放在距离地球10s差距（32.6光年）的地方测得的恒星亮度，它反映恒星真实发光本领。两者转换公式

式中：M——绝对星等等级，m——视星等等级，d——恒星的距离化为秒差距数。在星空背景图像仿真中，仿真图像是灰度级数字图像，需要将不同等级的星等转换为不同灰度级的像素。根据星等定义，星等等级越低，该恒星的亮度越大，表现在灰度级图像中的像素灰度值则越大；反之，星等等级越高，该恒星的亮度越小，对应像素灰度值越小。故星等与亮度的转换公式可以建模成以下公式

式中：A——比例因子，g——亮度值，m——视星等等级。弥散效果的建模主要采用二维Gauss模型和二维Laplace模型。它们都是中心对称衰减函数，但是Gauss模型使用范围更广，故采用Gauss模型建模。Gauss模型计算公式

式中：μ（x，y）——位于CCD像平面中坐标为（X，Y）处的恒星对该坐标系下坐标为（x，y）的像素点的单位亮度贡献值，δ表示弥散程度系数。在本实验中，遵循上述公式只需计算在CCD像平面中（X，Y）处的恒星，对位于以（X，Y）为圆心以及半径为RADIUS个像素的圆之内的像素点产生亮度贡献。当（x，y）和（X，Y）之间的距离超过RADIUS个像素点时，则认为位于（X，Y）的恒星对位于（x，y）的像素的亮度贡献值为0。最终，位于（X，Y）等级为m恒星对弥散圆形区域的任意一个像素点（x，y）的弥散权值由以下公式计算得来

2 星空背景弥散效果算法实现

2.1 基于单核的星空背景弥散效果实现算法

仿真图像是灰度级数字图像，利用浮点型二维矩阵Pic存储CCD像平面仿真图像的像素值。每次计算亮度贡献值时都需要计算式（4）会影响算法的执行效率。在程序设计中，利用内存空间耗费换取较高时间效率是一种很常用的设计思想。在本算法的设计中，可以利用这种思想将弥散权值在预处理时计算出来并存储在弥散权值查询表中。弥散权值查询表是一个三维数组，第一维度表征恒星亮度等级，第二维度和第三维度分别表征正方形区域U的长和宽，正方形区域U是弥散圆的外接正方形。经过恒星检索后，位于视场内的恒星结构体存储在一个容器V中，恒星结构描述如下所示。

struct SStar

｛ int mag；

／／恒星的亮度等级

int posW；

／／恒星在CCD像平面水平向的坐标

int posH；

／／恒星在CCD像平面垂直方向的坐标

｝；

基于单核单核的星空背景弥散效实现算法具体所述如下：

（1）初始化矩阵Pic；

（2）遍历容器V中所有恒星，如果遍历完恒星就退出；否则继续向下执行；

（3）对于每颗恒星，遍历以（posW，posH）为中心的正方形区域U′，该正方形的边长为2RADIUS；

（4）针对位于区域U’内每个坐标点为（x，y）的像素：当（x，y）与（posW，posH）之间的距离小于或者等于RADIUS，利用式（4）计算恒星对该像素点的亮度贡献值，并累和到Pic（x，y），转到（2）；否则不对该像素做任何操作，转到（2）。

假设在一次成像过程中，恒星数目是N，基于单核处理器星空背景弥散效果算法的时间复杂度是O（N×（2×RADIUS）（2×RADIUS））。对于串行程序设计，该算法是一种比较高效的算法。但是鉴于恒星背景成像实时性要求：生成每幅图像耗费50ms以内。该算法的成像效率满足不了需求，因而需要利用并行算法来加速成像。

2.2 基于多核处理器的星空背景弥散效果实现算法

依靠提高CPU主频的方式来提升CPU运算速度已经越来越受到电子工艺和器件功耗的制约，因而在同一个芯片上集成多个处理器核是现在提升CPU处理速度的一种大趋势。多核CPU体系结构可以在底层机器指令级上实现并行，但是多核优势并没有得到充分利用。设计多核并发程序时，创建多个线程并让它们并发执行更能提高多核CPU利用率。为了将多核处理器并行编程性能发挥到极致，需要从以下3个方面来提升多核CPU并行程序执行的效率：①存储带宽；②片上缓存一致性；③负载均衡［5］。存储带宽由机器硬件配置所决定；文献［6］提出一种面向多线程多道程序的加权共享Cache划分框架：包括面向应用的效率监控器和加权Cache划分算法以提高系统的整体性能；另外，如何管理线程调度也是影响多线程运行性能的一个重要因素。在本文中，利用操作系统提供的API函数SetThreadAffinityMask（）将每一个线程硬关联到一个核上［7］，可以避免线程在不同核间切换带来时间开销，并保证每个核的负载均衡。

多核处理器的星空背景图像实现算法主要分为两个过程：计算子图像和合成结果图像。计算子图像过程中恒星集合被均匀分配给每个核进行处理以期望每个核负载均衡［8］；合成结果图像过程中整幅图像被划分为N个子图像，每个线程负责合成一个子图像（CPU核数目为N）。基于多核处理器的星空背景弥散效果具体算法如下所示：

（1）主线程根据系统API函数GetSystemInfo（）得到CPU核数目N；

（2）主线程在创建N个线程并设置线程参数后开始等待；

（3）每个子线程初始化各自生成的子图像SubPic（x，y）＝0；

（4）遍历该子线程处理的恒星子集合，如果遍历完恒星子集合就等待；否则继续执行；

（5）对于每颗恒星，遍历以（posW，posH）为中心的正方形区域U’，该正方形的边长为2RADIUS＋1；

（6）针对位于区域U’内每个坐标点为（x，y）的像素：当（x，y）与（posW，posH）的距离小于或者等于RADIUS，利用式（4）计算恒星对该像素点的亮度贡献值，并累和到SubPic（x，y）；否则不对该像素做任何操作；

（7）转到（4）；

（8）当所有子线程完成子图像计算就停止等待继续执行，到此计算子图像过程完成，开始进入合成结果图像过程；

（9）每个子线程遍历分配给该线程的结果图像块的每个像素点，将N个子图像的对应像素点值累和赋给结果图像像素点；

（10）当N个子线程都完成图像合成时，主线程停止等待处理其它事务。

计算子图像过程耗费的时间随着恒星数目的增多而增加；合成结果图像过程耗费的时间则随着图像尺寸的增大而增加。基于多核处理器的星空背景弥散效果实现算法在一定情况下可以满足实时性要求，比如图像尺寸是1024×1024以及恒星数目少于10 000颗，但是对于图像尺寸是2048×2048恒星数目多于5 000颗就达不到实时性要求。

3 实验结果对比

3.1 生成星空背景图像所耗时间对比

实验采用4种不同型号的机器计算生成星空背景弥散效果仿真图像所耗时间和加速比，它们的硬件配置和软件环境见表1。

表1 单核和多核算法运行环境

表2列出恒星数目分别为5000颗、10000颗和50000颗以及1024×1024像素的图像在上述4种机器上生成的星空背景图像所消耗的时间，并计算在多核算法下相对单核算法的加速比，所耗的时间单位是ms。

表2 多核算法生成1024×1024图像时间与加速比

3.2 星空背景图像效果对比

图2是星空背景图像仿真系统在模拟SKYNET 5c卫星上的相机于31Oct 2009 01－48－09.000拍摄的星空背景图像。该图像包含1974颗恒星，其中星等大于或等于10的恒星占97.7%。从图中可以看出，单核和多核算法生成的星空背景仿真图像效果完全一样。

3.3 实验结果分析

图2 相机在SKYNET 5c卫星上于31Oct 2009 01－48－09.000拍摄的图像

综合分析可以得出以下结论：①单核和多核算法生成的星空背景仿真图像没有区别；②程序中串行部分占有的比率非常小，而实验中的CPU主频也不完全相同，但多次实验的加速比围绕核数目波动，可以认为满足阿姆尔达定律阐述的多核加速比与程序中串行程序所占比例以及CPU核数目的等式关系；③基于单核处理器的星空背景图像实现算法是CPU密集型算法，在单核处理下速度很慢，但是耗用的内存空间不多；基于多核处理器的星空背景图像实现算法将计算压力分摊到多个核上并行计算，提高了生成图像的速度，但在每个线程中必须分配两幅图像的内存空间分别用于保存中间图像与合成图像，因而，几乎需要两倍于单核算法的内存空间。

4 结束语

本文基于一种单核处理器的星空背景弥散效果实现算法，提出了基于多核处理器的并行实现算法。仿真分析表明，在单核实现算法中，单核CPU承受大量计算任务导致生成图像效率不够理想，通过利用多核算法可以将密集的计算任务分摊到多核并行处理，能够实时生成仿真图像，加速比大致满足阿姆达尔定律［9］。在星空背景图像仿真中，星芒效果是重要的研究方向。今后，在更进一步提升以上两种算法效率的同时，将继续研究基于多核处理器的星芒［10］效果实现算法。

［1］YUAN Lin，LV Pin，ZHENG Changwen，et al.Research on simulation of imaging effects in star field［J］.Journal of System Simulation，2009，21（8）：2174－2178（in Chinese）.［袁麟，吕品，郑昌文，等.星空环境成像效果的仿真研究［J］.系统仿真学报，2009，21（8）：2174－2178.］

［2］WANG Bin，DAI Shuling.Simulation of lens system imaging in virtual reality system［J］.Journal of System Simulation，2007，19（6）：1312－1315（in Chinese）.［王槟，戴树岭.虚拟现实系统中的可见光成像仿真［J］.系统仿真学报，2007，19（6）：1312－1315.］

［3］ZHOU Yan，ZHAO Jianke，CHANG Ming，et al.Measurement of dispersed spot for star sensor optics［J］.Journal of Applied Optics，2009，30（3）：454－456（in Chinese）.［周艳，赵建科，昌明，等.星敏感器光学系统弥散斑测试方法［J］.应用光学，2009，30（3）：454－456.］

［4］XIONG Darun，DENG Licai.A revision on lithium abundance dispersin in pleiades stars［J］.ACTA Astronomica Sinica，2005，46（3）：258－271（in Chinese）.［熊大闰，邓李才.重新审查昴星团成员星锂丰度的弥散［J］.天文学报，2005，46（3）：258－271.］

［5］CAO Zhebo，LI Qing.Research and design of parallel programming model on multi－core［J］.Computer Engineering and Design，2010，31（13）：2999－3002（in Chinese）.［曹折波，李青.多核处理器并行编程模型的研究与设计［J］.计算机工程与设计，2010，31（13）：2999－3002.］

［6］SUO Guang，YANG Xuejun.A weighted dynamic shared cache partitioning mechanism for multi－threaded multi－programmed workloads［J］.Chinese Journal of Computers，2008，31（11）：1939－1947（in Chinese）.［所光，杨学军.面向多线程多道程序的加权共享Cache的划分［J］.计算机学报，2008，31（11）：1939－1947.］

［7］Jeffrey Richter，Christophe Nasarre.Windows Via C／C＋＋［M］.GE Zi’ang，ZHOU Jing，MIAO Min，transl.Beijing：Tsinghua University Press，2008（in Chinese）.［Jeffrey Richter，Christophe Nasarre.Windows核心编程［M］.葛子昂，周靖，廖敏，译.北京：清华大学出版社，2008.］

［8］LI Shi，LI Naiqi，GUO Jiandong.Multi＿threading wordload balance under multi－core architecture［J］.Computer Applications.2008，28（2）：138－140（in Chinese）.［李实，刘乃琦，郭建东.多核架构下的多线程负载均衡［J］.计算机应用，2008，28（2）：138－140.］

［9］GUO Naiwang，WU Chengrong.Network content parallel recovery system based on multi－core processor［J］.Com－puter Engineering，2011，37（12）：291－293（in Chinese）.［郭乃网，吴承荣.基于多核处理器的网络内容并行还原系统［J］.计算机工程，2011，37（12）：291－293.］

［10］YUAN Lin.Research on imaging effect simulation in space environment［D］.Beijing：Institute of Software of Chinese Academy of Sciences，2009（in Chinese）.［袁麟.空间环境下成像效果的仿真研究［D］.北京：中国科学院软件研究所，2009.］