基于sor-andn的三维城市场景并行绘制性能分析

基于sor-andn的三维城市场景并行绘制性能分析

1并行绘制系统三维数字城市系统的构建是数字地球的重要组成部分。随着城市的快速扩张和空间数据获取手段的不断进步,三维城市模型的数据量呈现出指数级增加的趋势,使得单台消费级PC的实时绘制能力和内存管理能力愈来愈难以满足三维数字城市的需求。鉴此,一是从数据本身入手,建立三维城市模型的多级分辨率表达,减少实时绘制系统的负载;二是通过软硬件方法,直接对渲染过程进行加速,而并行绘制因为可扩展性高、相对易实现,是研究重点之一。Molnar根据并行绘制系统中,图元判断在渲染流水线中的时机,将其分为3类:Sort-First、SortMiddle和Sort-Last。其中,Sort-First特别适合多机分布式实现,以及超高分辨率的显示,并且在理论上能以类线性的代价实现规模扩展,因而获得了广泛的关注和大量的应用。也有一些研究者设计了混合体系结构的并行绘制系统,如文献,其本质是一个分层的复合系统,上层采用Sort-First结构,对Sort-First中每个子任务再采用Sort-Last进行分解。而大规模复杂城市场景多应用在超大屏幕展览,且场景深度复杂度高,若采用Sort-Last系统可能造成图像合成时间长,网络传输量大等问题,因此,多采用Sort-First方式进行并行绘制。当前对Sort-First系统的研究多集中在任务划分及负载平衡方面,鲜见一些对并行绘制系统性能的定量分析研究工作,并且多针对某一特殊架构,缺少对Sort-First系统中各系统参数对性能的影响和加速比的定量分析,难以从节点配置和任务划分两个方面达到对系统性能的最优化。2首先，并行块系统及其性能分析2.1并行结构及模型构建为了获得更高性能的计算能力,并行系统对数据或者功能进行分解,充分发挥多个节点的计算能力,分别称为数据并行和时间并行。Sort-First并行绘制系统在图像空间对任务进行划分,属于一种数据并行系统,其图元归属判断发生在进入渲染管线之前。如图1,图像空间被划分成若干个不重叠的2D子区域,每一个或多个子区域对应一个绘制节点,分布在子区域内的所有图元会被送入相应节点的渲染管线,在管线末端,各节点将绘制结果以图像的形式发送到最终绘制通道所在节点完成一帧的显示。基于Sort-First的并行绘制系统对渲染管线的介入较浅,相对于其他两种并行结构,其主要优点有:网络传输量低;每个节点执行完整的渲染管线,利于分布式实现;合成方法简单;良好的可扩展性。由于图元在屏幕空间的分布具有随机性,节点之间的负载均衡是Sort-First需要解决的主要问题之一。本文采用一种时间反馈的动态负载平衡技术,利用帧间图元分布的相似性,参考前一帧的绘制时间,作为当前帧中绘制任务划分的依据。针对PC集群中网络传输较慢的特点,本文对文献中方法做了一定优化,将绘制时间与传输时间的和作为任务划分依据。在城市场景中,场景的深度复杂性高,图元在屏幕上分布密度大,对2D子区域进行的动态扩张或收缩调整,能带来图元负载数量显著的变化,使各节点的绘制时间趋于一致,所以,此方法在复杂城市场景绘制中能取得较好效果。2.2性能分析：sort-1行系统2.2.1并行加速比sn对于一个并行计算系统来说,加速比和并行效率都是非常重要的性能指标,其中最常用的性能评价指标就是加速比。假设一个串行系统完成一帧的绘制所用时间为T(1),而N个节点构成并行绘制系统绘制同样一帧所用时间为T(N),则加速比S(N)定义为:阿姆达尔(Amdahl)定律将并行系统中执行任务的时间T(N)分为2个部分,T(P)为系统中可并行部分所花费的时间,T(1)-T(P)为串行部分所花费的时间,将式(1)改写为:当参与并行的节点数不断增加,可并行部分所花费的时间越来越少:可见,并行系统中,能达到的最高理论加速比取决于可并行部分在整个任务中的比例。2.2.2绘制时间的约束对于三维城市场景的绘制,每秒的绘制帧数(FPS)是衡量一个可视化系统的通用性能指标,在绘制场景内容不变的情况下,对FPS的衡量可以转换为绘制一帧所需要的时间,在单节点的串行绘制系统中,绘制一帧所需时间为:式(4)中,TG和TR分别表示几何变换和光栅化2个阶段所用时间。式(3)是阿姆达尔定律所表达的一种理想情况,在Sort-First并行绘制系统中,几何变换和光栅化都具有数据可并行性,然而对数据的分解,必然会带来其他额外的执行时间,主要有网络传输时间(Tw)、从显存到内存的回读时间(TB)、图像合成时间(TA)。因此,在有N个节点参与绘制的SortFirst并行绘制系统中,一帧的绘制时间T(N)可约束为:由于Sort-First系统在每个绘制节点保留了比较完整的渲染管线,可以记TEi=TGi+TRi+TBi,在以下的讨论中以TEi代替绘制时间。而Sort-First架构有着合成方法简单的优点,图像的合成是一个简单的拼接过程,所以,TA系统性能的影响可忽略不计,式(5)可改写为:从式(1)可得出,加速比S(N)由每个节点的绘制时间和图像传输时间决定,从而影响Sort-First并行绘制系统性能的主要因素有:节点绘制性能、绘制任务划分方式、网络传输速度,以及目标显示颜色深度和分辨率。3绘制节点的总负载平衡各个节点负载的均衡是Sort-First系统性能达到最优的必要条件,文献中采用了一种基于绘制时间反馈的动态负载平衡方法。由于每个节点的计算性能可能存在差异,即使建立一个每个节点硬件配置都是均等的计算集群,也会因多任务操作系统分配资源的不确定性,导致每个节点的绘制性能会上下波动,绘制时间难以事先计算,因此,我们通过计算前一帧的绘制时间作为当前帧的参考绘制时间,并以此预测屏幕空间中图元的分布情况。由直观判断可知,节点中TEi>Twi是该节点能提高系统加速比的必要条件,该方法使用TUi作为任务划分的权值依据,用有N个叶节点的二叉树将屏幕划分成N个不重叠的二维区域,将TUi以ms为单位,加权换算成屏幕空间中以像元无单位二维区域。本文考虑到PC集群所在的局域网传输速度较慢,以及三维城市场景的绘制负载量较大,使用绘制时间与传输时间的和TOi作为衡量该绘制节点负载的指标。用TOi作为负载平衡中时空转换的依据,在理想的均衡状态下,每个节点的TOi相等,记为,由于在一帧绘制中,系统中各节点的总负载量是一定的,所以,每个节点的TOi达到均衡也是整个并行绘制系统达到理论最高加速比的必要条件,此时,从而,Sort-First并行绘制系统的加速比可以描述为:同绘制时间TEi相比,从绘制节点至目标显示节点的网络传输时间Twi受到传输数据量及网络传输速度(记为Li字节/秒)影响,记显示总像元为P,颜色深度为D字节,其中,节点i对应视口的像元数为Pi,则传输数据量由Pi及D决定:从上节可知,欲实现负载平衡,使系统加速比达到最高值的条件是每个节点的TEi+Twi相等。在实际系统构建中,为了提高性能,应用程序所在计算机往往也是绘制节点之一,与其他绘制节点不同的是,该节点的绘制结果图像可直接用来拼接显示,而不需要网络传输。为了方便讨论,不失一般性记该节点的绘制时间为TE1,传输时间Tw1=0。场景中三角面片在屏幕均匀分布的理想情况下,TE1主要受P1,即主节点绘制区域占屏幕像元的比重影响。为了获得最高理论加速比,本文考虑并行系统中最理想的情况,除第一个绘制节点(即应用程序所在节点)外,每个节点的绘制时间TEi和传输Twi在每个节点的值相等,据式(7)可限定每个节点的Pi和Li也相等(i≠1)。因为对节点的绘制时间TEi中包含了从显存到内存的回读时间,所以,在任务均等划分的理想情况下,记目标显示分辨率为P,网络总带宽为L字节/秒,则在负载平衡的情况下:由此得到N个节点构成的集群系统中,并行绘制的加速比理论最高值为式(15)右端部分,对于一个可视化系统而言,决定T(1)的影响因素较多,且随着场景复杂度及可视部分数据量而波动,但是,式(15)中显示分辨率和颜色深度往往是不变的常数,而网络带宽在网络环境建设好之后也相对固定,所以,我们记常数C=DL,得到加速比S(N)理论最大值为:由式(16)可看出,在绘制场景不变的情况下,如果TE1增大,意味着P1在增大,即T(1)N+(P-P1)*C在减小,反之亦然,因此,我们得到系统加速比S(N)达到最大值的一个必要条件:从式(17)可看出,如果T(1)或者N很小,都可能导致等式不成立,由此可见,基于Sort-First的并行绘制系统不同于普通计算密集型的并行计算,在节点数较少,以及单台计算机绘制负载较小的情况下,并行绘制的加速比可能会小于1,同样从式(16)可看出,当绘制节点数不断增加时,其带来的收益并非线性增长,因此,合理配置并行资源对并行绘制系统的性能有着重要的影响。4实验结果及分析本节通过南京市总统府地区的三维场景并行绘制实验来验证上文的分析,并对比分析文献中的负载平衡策略与本文方法的性能差异。实验采用4台硬件配置如表1的PC机,网络环境为百兆交换机局域网,软件环境为Windows764位旗舰版,VisualStudio2010,以OSG为渲染引擎,模型中共含有8438340个顶点,2812780个三角面片。本实验实现的是一个动态漫游系统,而在漫游过程中由于磁盘I/O可能会引起FPS的抖动,对I/O相关的性能影响分析超出了本文的研究范围,因此,为避免屏幕内图元数量,以及景深的不同和磁盘I/O对测量结果的影响,同次实验中采用相同的位置及视角。显然当视点和视角变化时,实验结论依然成立。在自适应的负载平衡实验中,由于任务划分和分配处于一个动态平衡的状态,性能及反馈参数会不断波动,因此,本文采用连续绘制2000帧的平均值作为测量结果。使用不同节点数,采用单台PC绘制、以及本文优化的动态负载均衡方法,分别对实验场景进行绘制(图2)。实验中绘制窗口分辨率设置为720×480,颜色深度为24bit(3Byte)(FPS统计值结果如表2),因此,一帧图像的像元数P为345600,百兆局域网的理论传输速度为12MB/s,实测中传输速度值大约为10.16MB/s,从而上节中的常数C大约为2.82×10-7,统计式(16)中各项的值,结果如表3所示。从表2可看出,本文以传输时间和绘制时间之和,作为性能反馈的依据,相对文献中的方法,更加全面地考虑了对系统总体性能产生影响的因素,使性能有一定程度的提高。在实际场景中,三角面片在屏幕的分布可能发生严重倾斜。据表3的数据,式(17)所描述的等式并不能完全成立,而会因任务分配的波动导致主节点的绘制时间稍长。当节点数增加,系统整体性能提高时,主节点所绘制的结果占屏幕的百分比越来越低,这与式(16)所反映的规律一致。5并行绘制系统配置优化本文分析了基于Sort-First的绘制系统的并行机制,研究了系统中各项参数对系统性能的影响,改进了文献提出的负载平衡策略,尝试量化分析系统加速比的最高理论值,并给出其成立的一个必要条件。通过一个复杂城市场景的并行绘制实验分析,结果表明,并行绘制系统的配置对性能的提高有着重要的影响,当系统负载较小时,增加节点甚至可能降低性能,而当节点数不断增加,其带来的收益也并非呈线性增长。本研究为基于SortFirst的并行绘制系统的配