利用PVM实现整体光照的并行计算

利用PVM实现整体光照的并行计算学生学院计算机学院专业班级11级网络工程3班学号3111006372学生姓名陈俊豪指导教师王卓薇2014年12月27日利用PVM实现整体光照的并行计算孙济洲1,NicolasDGeorganas2(1.天津大学电子信息工程学院,天津;2.渥太华大学信息技术与工程学院,加拿大)摘要:对利用网络资源解决复杂且耗时的计算问题做了尝试.选择典型的粒子跟踪整体光照计算问题作为研究对象,提出一种改进的且充分发掘其内在相关特性的密度估计算法.在以太网连接的多台微机上,以PVM(并行虚拟机)机制实现了该算法的并行计算.通过对各项运算性能指标的测试与分析,结果显示可获得良好的加速比,并且PVM在分布式网络并行计算上将有很好的应用前景.关键词:并行计算;PVM;整体光照;分布式网络尽管硬件的计算速度极大的提高了，但仍有很多尚不能解决的应用问题。这些是复杂的、实时性很高的过程，例如实际图像生成虚拟或模拟，医学上使用的图像识别和处理，在复杂的表格、结构的设计上的有限元分析。随着计算机体系结构和VLSI技术演化，人们能够通过大型的多处理器并行计算机解决大量问题，不过，想要广泛应用这门技术还需很长时间。近年来，对分布式网络和互联网的使用在各种应用领域迅速发展。基于此，计算机支持的协同工作（CSCW）系统完成一个大项目，为资源共享、多个用户之间的信息交流和协调提供了一个很好的环境。除了支持协同工作，人们还可以在分布式环境中任何方面进行开发或借整个网络资源，以解决上述复杂和耗时的问题，这一点已经受到越来越多的关注。PVM（并行虚拟机）应发展趋势而生，它不仅支持一个完整的消息传递模型，还能让分布式工作站和PC结合成为一台高性能并行计算机。在本文中，研究目标是整体光照计算问题，它是一个现实的图像生成的核心，也是一个非常复杂和费时的过程。由于光的现象，如不同的光学特性的表面之间的漫反射，镜面反射，折射和透射，实验目标必须模拟全局光照[1]，它可能需要几个小时甚至几天的计算机时间来营造呈现复杂的场景以获得高质量的合成图像。在这里尝试利用PVM进行整体光照的并行计算。首先，根据粒子跟踪和康奈尔大学[2]提出密度估计（DE）方法，通过对它固有的并行性进行了探索，改进了DE算法（IDE），可以更方便和更有效的实现并行计算。然后对实验进行了讨论，如任务分配策略和子任务粒度的选择，其中PVM环境的建立是为了支持算法及其并行实现。得到的试验结果及并行加速性能的分析用来为PVM应用积累经验。试验结果表明，该算法是适用的，PVM具有很好的应用前景。它们还为将集成PVM模型整合到分布式协同虚拟环境的研究的可行性的奠定了基础。1改进的DE算法整体光照算法主要包括有限元法和应用随机技术方法，后者分别是独立视图和视图依赖技术。虽然有限元算法已被完全开发了很长一段时间，但它不适合用于需要复杂光照来渲染的场景。同时，内存和计算带来的巨大成本，以及曲面细分所带来的附加误差，都是有限元法的致命缺点。相比之下,应用随机技术如MonteCarlo方法，优点是广泛的适应性,实现的简单性,应用随机技术正在成为整体光照研究的重点[3]。DE算法的核心部分就是来自MonteCarlo方法的密度估计计算。1.1DE算法DE算法分为三步：粒子跟踪，密度估计和网格优化。[2]粒子跟踪描述能量粒子发射的整个过程，包括了粒子的反射，折射或吸收。事实上，粒子跟踪应用MonteCarlo方法求解位势方程[4,5]和获得对应区域的通量。在粒子跟踪后，包含命中点数据的文件就建立了。密度估计是用来计算小网格顶点光照和利用核函数创建包括网格顶点光照数据的文件的方法，核函数认为一个命中点只影响这一周围地区的光照。这个方法的关键是选择合适的核函数，它代表了受命中点光照影响的任何点，例如Silverman的K2函数[6].过密的网格必须减少，只保留周围光强的变化较大的网格顶点，从而提高渲染速度。对此许多网格优化的算法已经被开发出来了[7]。最后，包含紧凑的渲染网格顶点的数据的文件就建立了。该文件可以以高氏阴影网状[1]的形式存储，或者可以以图形工作站上交互显示，或者可以用于一个附加的射线追踪通以创建更逼真的、视图依赖的图像。1.2改进DE算法DE算法具有强大的并行性。首先，DE算法的三个阶段是独立的、不相关的，它们可以在同一个管道模式下运行。事实上，这是大型并行粒度的开发。其次，该算法的每一阶段都有很强的并发性，可以进行加工处理，跟踪每个粒子就是一个典型的并行子任务。像记录一定的表面的命中点的密度估计和为场景中的每个表面做网格优化这两个任务就可以同时执行。由于密度估计在整个过程中起着重要作用，在改善算法的研究中密度估计将集中在以下的讨论。密度估计，是利用场景中一个表面所有点的数据，根据核函数方法计算网格顶点的光照。见图1。本程序有两个主要的短处，源于利用了表面上所有点的数据，这些数据数量是非常庞大的，甚至可以是数以百万计的。一方面，由于内部存储器的容量是有限的，点的数据必须从内部存储和外部存储之间的反复转换，导致较低的效率。另一方面，对网格顶点和所有点之间的距离比较的一小部分操作是有用的，因为事实上只有几点可以影响的网格的顶点光照。此外，当以这种方式计算出的一个表面上的密度估计被分配为并行计算的子任务，效率不会因不同表面上的非常不同的命中点数量造成的负载不平衡而变高。图1基于网格点的密度估计方法因此，我们改变密度估计的模式，从考虑网格的顶点是怎么受所有点的影响，到考虑每个点是怎么影响其附近的网格顶点。就是说，将网格顶点的密度估计过程转变为以一个点为基础的计算程序。在这里，命中点的数据将被使用一次，以获得其周围的网格顶点部分光照。只有网格顶点坐标和网格的间隔需要保存，其成本非常小的。这样，命中点的数据不应该被频繁地交换于内部和外部存储器之间。命中点和无关的网格顶点之间的距离比较如果不影响这个独特的点的话就不用保存。图2显示修改后的密度估计过程。修改后的算法称为改进的密度估计全局光照算法或IDE短算法。IDE算法适用于并行模式运行，方便而有效。图2基于命中点的密度分析步骤2.PVM中IDE算法的并行实现2.1PVM并行计算架构PVM是一个有效的机制，使得用户可以利用分布式网络中现有的计算资源来支持并行计算来用最小的额外成本解决大问题。在PVM所有的电脑都是工作在动态的主/从模式。在PVM的任何节点，当它正在运行一个程序，希望借助网络中的其他节点的计算资源，解决一个巨大的问题，可以作为主机，分配任务给其他节点和从机，来获取一个快速的解决方案。主机将管理和监控他们交换的消息，而从机同时完成子任务分配。节点之间的通信是基于消息传递，也可以通过PVM实现[8]。IDE算法其内在的并行性和考虑的任务分配的优化和负载平衡决定了它非常适合在PVM环境下实现，在这里，一个子任务是指一定量的命中点的数据密度估计的计算，其中所有的子任务应按照自己的计算量排序，以防止降低效率。该算法的并行程序已被精心组织过，其数据结构及其参数，如缓冲和访问时间的大小，也被仔细选择过以降低计算成本。2.2任务分配策略静态和动态策略用于并行计算的任务分配。在静态战略的实施，主进程根据命中点和可用的计算元素的总数读取命中点和派生从机，给每个从属进程分配任务。从机完成密度估计计算并将结果返回给主机，然后终止。上述过程被重复，直到所有的子任务完成。最后，主机收集所有的结果，并创建一个结果文件。申请子任务的机制用于在动态任务分配的方案。主进程派生一个固定数目的从属进程的，为它们分配的子任务与进入的循环等待状态。完成当前子任务之后，从机返回其ID并请求一个新的子任务，然后进入一个闲状态，等待下一个子任务。当主机没有更多的子任务时，从机结束进程并提交结果到主机。2.3子任务粒度的选择子任务粒度的选择直接影响并联系统的负载均衡。这里，平行粒度是一个子任务的计算量。由于该运算程序对每个命中点是相同的，并需要类似的计算量，并行粒度可以根据命中点和可用的计算资源的数量来选择。为了实现在IDE算法，子任务粒度不会选择像传统的那样为表面上所有击中点的作密度估计作为一个子任务[9]。这是因为，只有当场景中每个表面上击中点的数字是近似值，这样的子任务的分区才是有效的。但是，为不同表面计算的复杂度的巨大差异会导致加载失衡并降低效率。举例来说，恰好朝向光源的表面的命中点的数量必然比其他的大。这种表面比其他表面必须花费更长的时间来运算，使得每个处理单元上的负载将是不平衡的，并行计算的效率会较低。另一方面，粒度不能选择过小，因为对PVM不支持具有非常小的粒度的并行处理[8]。这样由于每个处理单元经常需要调度命中点的数据，会极大地增加沟通成本。为降低通信成本并使每一处理器负载平衡，应选择一个适当的并行粒度、命中点的数量有限的子任务。由并行算法的高速化效应，几个不同大小的粒度都已经经过测试并且它们的分析将在下面的章节中给出。在并行算法的执行中，粒度的大小还将由任务分配的策略决定，以实现较高并行加速。为静态任务分配的并行粒度可以是有点大的，因为从属进程的数量是固定的，并且它的灵活性决定了它应该是小的动态策略。3实验和结果分析用于场景的IDE算法的并行密度估计的实验已经分别完成了静态和动态任务分配的策略。见图3。整个测试经由以太网使用8个相连的PC（奔腾100和32M字节存储器），它运行的是Linux操作系统（RedHat的60.2）和PVM（第3版0.4）的软件包。使用一个容量为10兆字节的网卡。图3测试现场在实验中，计算速度和总运算速度有效性是怎么被PC的数目的影响，粒度的大小首先被研究。有效的运算速度是每单位时间为密度估计计算出的命中点的数量，总的计算速度是有效的运算速度和的总时间的比率。这里的总时间是指计算时间和交流时间。静态策略的并行加速示于图4，其中横坐标表示所用的PC，在y轴的数量分别表示有效的计算速度和总运算速度。这里的粒度是1000命中点的密度估计。我们可以发现，在加速的有效计算速度大约是线性的，而总的计算速度显显示缓慢增加。表格1给出了具有不同粒度的总计算时间（单位为秒）的比较;力度越大，总时间越短。图4并行加速静态任务分配表1静态任务分配的整个计算时间图5和图6显示了加速的动态任务分配图5的坐标与图4是相同的。图6显示了不同粒度如何影响加速。我们可以发现，有效的计算速度是接近线性的增加，总的计算速度缓慢增加。此外，在一定的范围内，子任务越小，加速越好。图5并行加速动态任务分配图6动态任务分配对加速影响任务分配两种策略被认为是有用的，他们都达到近似线性的加速。在静态任务分配的过程中，主机按组创建从机组，仅分配一个单一的子任务到每个从机。这需要大量的启动和等待时间，将导致并行效率降低。为了避免额外的时间成本，并行粒度为静态策略不应太小。但这个策略应该是稳健的，能够简单地控制和实现。从试验结果中看，动态任务分配的加速比静态策略的好得多，并到达了预期的目标。动态策略避免了过多的时间成本，主机无需等待所有从机完成任务就能发布新的任务。只要收到从机的人物请求就发布任务，极大提高效率。动态策略可引导计算和通信之间时间重叠，并适当降低了粒度，可以使计算和通信的花费更紧密，使效率得到提高。在未来，我们的工作是要设法消除目前并行计算的瓶颈，这意味着改善任务分配策略的。由于主按顺序分配从机子任务，从机必须在现在进入循环等待，无论使用静态或动态策略。如果PVM标准被扩展到支持用于分配用于并行计算任务的多线程操作，我们将实现更完美的加速和并行效率。如何将PVM机制整合入CSCW系统，是更进一步的应用，也将被继续研究下去。参考文献[1]HearnD,BakerMP.ComputerGraphics[M].CVersion,2ndEd.NewYork:Prentice-Hall,1997.[2]ShirleyP.Globalilluminationviadensityestimation[A].ProceedingsofEurographicsRenderingWorkshop[C]