分布式并行绘制系统中几何指令流压缩

分布式并行绘制系统中几何指令流压缩分布式并行绘制系统中几何指令流压缩的研究与实现*金哲凡 杨建石教英(浙江大学CAD&CG国家重点实验室,杭州,310027){jinzf,jyang,jyshi}@摘要对分布式并行绘制系统的几何指令流进行压缩能缓解网络带宽瓶颈 .对操作码使用LZW算法,对法向量使用球面对称网格剖分算法,对颜色和位置数据使用DPCM型预测编码算法,根据位置数据的特殊性,使用了4类预测器和自适应量化算法 .对几何指令流组合使用多种压缩算法取得了良好的效果,在几,指令平均长度压缩到原来的1/3左右,执行何模型质量基本没有损失的情况下速度达到了400指令/ms.关键字:分布式并行绘制,sort-first,几何压缩,LZW,DPCM,预测,量化中图分类号:TP391(StateKeyLaboratoryofCAD&CG,ZhejiangUniversity,Hangzhou310027)AbstractCompressionofgeometryinstructionstreamindistributedparallelrenderingsystemscanalleviatenetworkbandwidthbottleneck.LZWmethodisusedinop-codescompression.Aspheresymmetric-gridmethodisusedfornormalcompression.PredictiondeltacodingwithDPCMmodelisusedinpositionandcolorcompression.4kindsofpredictionsandadaptivequantizationareusedinpositioncompression.Multipleapproachesworkswellingeometryinstructionstreamcompression.Theaveragelengthofinstructionsiscompressedto1/3oftheoriginalonewithalmostnolossofqualityandtheexecutingspeedisbetterthan400instructions/msKeyWords:distributedparallelrendering,sort-first,geometrycompression,LZW,DPCM,prediction,quantization收稿日期:2001-00-00;修改日期:2001-00-00论文得到国家自然科学基金重点项目(No.60033010)和创新群体项目(No.60021201)支持.作者简介:金哲凡,男,1974年出生,博士研究生,主要研究方向:分布式图形计算,并行计算,email:jinzf@.杨建,男,1973年生,博士研究生,主要研究方向为分布式图形计算,虚拟现实.石教英,男,1937年出生,浙江大学CAD&CG国家重点实验室教授,博士生导师,主要研究领域为并行计算 ,计算机图形和 CAD,可视化,虚拟环境.email:jyshi@一,引言随着技术的进步,图形系统的能力越来越强大.目前微机高端显卡的三角形处理能力超过了30Mtriangles/s, 一些显卡带有16个硬件光源,4～8条纹理通道,低端显卡的性能几乎每6个月就翻一倍,发展速度突破了Moor定律[1]. 同时用户需求的增长也很迅速 ,一些应用领域,如大数据集的科学计算可视化 ,高分辨率超大屏幕显示,10M以上数量级三角形的巨型几何场景交互式绘制 ,大纹理数据量的绘制等,仍是孤立的(standalone) 图形处理系统难以应付的 .这些系统的性能在以下一些方面受到限制:[2] 产生几何数据的能力(compute-limited), 图形计算能力(graphics-limited), 几何指令发射能力(interface-limited), 显示分辨率(resolution-limited). 分布式并行绘制技术通过构建高性能的分布式图形处理系统,为以上问题提供了解决办法.并行绘制系统基于图形流水线的概念构造.图形流水线可分为几何处理和光栅化两个阶段.前者包括几何变换和光照处理;后者包括扫描转换,纹理贴图和图象合成.按照图形处理任务的重新分配发生在图形流水线的哪个阶段,并行绘制系统可分为 3类:sort-first,sort-middle 和sort-last[3].sort-first 系统在几何处理之前将模型空间的几何元素进行重新分配;sort-middle系统在几何处理和光栅化之间将屏幕空间的几何元素进行重新分配;而sort-last 系统在光栅化的最后将象素进行重新分配.Priceton的多投影系统是一个sort-first 系统,它实现了一个 2×4的高分辨率投影墙[4];WireGL 是第一个基于sort-first 体系结构并且独立于硬件的集群图形处理系统 [3].SGI 的RealityEngine 和InfiniteReality 是典型的sort-middle 系统[5].PixelFlow[6]和ParallelMesa[7] 是sort-last 系统.随着研究的深入,一些系统混合使用了一种以上的方式,如Pomegranete[8]和AnyGL[1].AnyGL是sort-first 和sort-last 混合的大规模分布式并行绘制系统.在分布式并行绘制系统中,网络带宽容易成为瓶颈,影响系统的性能和可扩展性.如何应用压缩技术减少数据的传输量,缓解网络带宽的瓶颈,是分布式并行绘制系统研究的一个重要问题.对sort-last 系统,通过提取"活跃象素"的办法可以大大压缩数据量 [3].sort-first 系统中,WireGL尝试了用一阶线性预测和量化编码对几何数据进行压缩 ,但它仅仅处理了部分几何数据 ,而sort-first 系统中网络上传输的是包含多条几何指令的一定格式的指令流.指令流由指令操作码和参数组成,参数主要为几何数据,包括顶点位置,向量,颜色,纹理等,数据类型多样,只有根据各种数据的特点,组合使用多种压缩方法才能达到较好的效果.二,AnyGL系统AnyGL是一个

sort-first

和

sort-last

混合型的大规模分布式图形系统

,它包含四类节点:几何数据分配节点(GeometryDataDistributionNode, 以下简称G-Node),几何图形渲染节点(RenderingNode,以下简称R-Node),深度图像合成节点(ImageCompositeNodewithDepthBuffer, 简称C-Node),输出图像显示节点(OutputImageDisplayNode,简称D-Node),彼此之间以网络连接.应用程序发射的OpenGL指令,被G-Node截获,G-Node将指令打包,并根据一定的负载平衡策略将其发往多个R-Node.R-Node接收指令包,根据状态命令设置相应的GLContext状态,执行OpenGL指令,将结果图像和深度缓冲区输出到C-Node.C-Node根据深度缓冲区和图像合成状态合成最终图像,并将最终图像发送到D-Node,D-Node利用显示器或者投影仪等设备输出最终图像 ,如图1.应用程序G-NodeR-NodeC-NodeD-Node应用程序G-NodeR-Node应用程序G-NodeR-Node应用程序G-NodeR-NodeC-NodeD-Node网络网络网络图1AnyGL系统结构设某应用程序运行于一个G-Node,多个R-Node的状态下,V为顶点发射速度,R为同一顶点被发送到多个R-Node的概率,B为每一顶点字节数,则G-Node需要的输出带宽为:W=V(1+R)B(1)AnyGL工作于立即模式(immediatemode)下,每绘制一帧都要发射整个场景的所有点,所以V=FS(2)S为场景顶点总数,F为帧速.设一个顶点由一个位置命令和一个法向量命令定义 ,参数各为3个IEEE浮点数,命令码1个字节,则B=26.忽略重发率,令R=0,帧速满足一般真实感要求

,F=30

帧/s,

由式(1),(2),1M

顶点需要的带宽WM=780Mbps如.果使用N个G-Node,不失一般性,可认为工作负载均匀分配,则每个G-Node需要带宽WNM=WM/N,当N=8时,WNM=97.5Mbps.当AnyGL运行于普通的100M网络时带宽是非常紧张的.AnyGL的设计目标是用中等性能的网络实现低成本规模扩展,为此必须引入压缩技术以减少对网络带宽的需求,压缩是AnyGL和其他分布式并行绘制系统 "平民化"的关键.,压缩算法3.1总述指令I为二进制字符串,运算符"+"表示串的顺序连接,则几何指令流S为:S=I1+I2+ ⋯+Ii+ ⋯.+In指令IiIi ∈

属于一指令有限集合Ins={Ik|k=1,2,

Ins,每条指令都包含操作码⋯.M}

op-code

和参数

para:Ii=op-codei+parai在AnyGL中,M=244,op-codeii决定,"||" 操作

可以用

8bit

表示,而

parai

的长度则由指令类型表示取二进制字符串的长度 :|op-codei|=8.指令流压缩后仍为一二进制流 ,定义压缩函数F:F(S)==niiaiIF1)()(iaiIF表示对第i条类型为ai的指令的压缩.指令的操作码部分有相同的格式和语义上的关联,用函数g进行压缩.不同类型的指令参数类型或含意不同,同一类型的指令相互之间有关联,以一族函数fi进行压缩.对i类型的指令Ii:F(Ii)=g(op-codei)+fi(parai)(3)由式(3)可见,几何指令流压缩分为两个步骤:一,指令流和指令的分解和组合,二,g,fi的设计.几何指令的参数描述位置,向量,颜色,纹理等各种信息,其类型和含意十分丰富.设指令Ii出现的概率为pi,则压缩后的指令平均长度为 :==niiIFipIF1|)(|)(|)(|,而)(|)(||)(|ipIFIFi·=(4)式(4)表示,对指令Ii压缩能获得的好处与Ii出现的频率有关,应优先对出现频率高的指令进行压缩.,出现最多的指令是顶点几何场景绘制过程实际是通过描述大量的顶点来实现的属性定义命令,包括位置指令,法向量指令和颜色指令.设这些指令构成指令集合Ins'∈Ins,则指令流的压缩过程可表示为:+-∈+-=)'()()'()()()(InsIparacodeopgInsIparafcodeopgIFiiiiiiii实际系统如图2所示,压缩后的数据输出到一双向缓冲区d-buffer,d-buffer以O为原点,op-code数据向左增长,para数据向右增长.op-codeparad-bufferop-codesparametersOg(x)I∈Ins'(x)ifYN图2压缩指令到d-bufferAnyGL中分发的几何指令共有244条,op-code用一个字节表示.观察图形程序的运行规律可以发现,一些"短语"会在同一程序里大量重复出现 .如描述一个顶点属性的指令序列 :glVertex3f(x,y,z);//glNormal3f(a,b,c);//glColor3f(r,g,b)//

定义位置定义法向量定义颜色由于同一场景的大量顶点的属性定义往往会采用相同的方式,所以操作码形成的短语glVertex3f-glNormal3f-glColor3f 会多次重复出现.LZW算法可对字符串进行编码,同时定义特定的字符串表以及它们对应的编码.每当字符串表中没有的字符串出现时,它就被原样保存起来,并分配给它一个代码.当这个字符串再次出现时,将只保存上次分配的代码[9].LZW算法能有效消除字符串冗余,将它应用于操作码的压缩,可得到40%左右的压缩率.一个法向量一般由3个标准IEEE32位浮点数来表示.3个浮点数共可表示三维空间的296个点.这种表示方式有很大的冗余.首先,在同一空间取向上排列有多个点,如(1,1,1)的方向上共有216-1个点;其次,这些法向量在空间过于紧密,大大超出图形表达的需要.如果将296个法向量均匀分布在单位球面上,每2-46弧度就会有一个法向量,以这种精度从地球指向金星表面误差小于1厘米.而在单位球面上均匀分布的100,000个法向量,其精度已经超出了人眼的识别能力[10],所以理论上法向量只需17个bit来表示.对颜色和位置数据的压缩使用了DPCM(差分脉码调制)型预测编码.其过程为:由预测模块产生对下一个输入的预测值,对实际输入与预测值的差进行量化和编码,然后将量化输出与预测值的和反馈给预测模块,作为下一次预测的参考.提高DPCM型压缩的效果需要提高预测的准确性和减小量化误差.颜色数据使用一阶线性预测,对顶点的位置数据使用了4类预测算法.几何指令流压缩流程如下:while(thereisanIi){if(currentstringofparanotinLZW_dictionary){outputcode;addcurrentstringintoLZW_dictionary;}if(IiIns'){outputparai;continue;}if(Iiisnormaldefinition){outputfnormal(parai);continue;}if(Iiiscolororpositiondefinition){chooseappropriatepredicter;chooseappropriatequantizer;parai=parai-predicter.predict();outputquantizer.quantize( parai);predicter.feedback(quantizer.getvalue()+predicter.predict());continue;}}3.2 法向量压缩法向量压缩可归结为两个问题:一,将至少100,000个点比较均匀地分布到单位球面上;二,对这些点进行编码.问题一的解决方法是充分利用球面的对称性 ,将球面分割为多个子区域 ,再对子区域作网格剖分[10],这样可以尽量分散网格剖分不均匀的影响 ,并方便编码.如图3,球面被分为48个对称的子区域,子区域ABC上的点(x,y,z) 的球座标为:x=cosθcosφ,y=sin φ,z=sin θcosφ( θ∈(0,π/4),φ∈(0,0.615479709))(5)图3 单位球面剖分将等差数列(φ0,φ1,⋯⋯φn)带入式(5)所得的系列圆弧作为网格的纬线φi纬线与弧AB交于D(φi,θi), 将(θ0,θ1,⋯⋯θn)带入式(5)得到网格的经线.对网格上的点(i,j):x=cosθjcosφi,y=sin φi,z=sin θjcosφi

,若若i,j各用n位二进制数表示,则:-==)2)2(arcsin(2maxmaxnninjitgjφθφφ对于球面上点P的编码分三步进行:一,用3位二进制码表示P所属象限;二,用4个3位码和2个2位码表示P所在1/6象限子区域,三,以2个n位码字表示与P最近的网格点座标.如此一个向量的压缩后长度L=3+(3×2/3+2×1/3)+2n=2n+52/3.当n=6时,L=172/3.在程序实现上,使用了与网格形状相称的三角形检索表以加快速度.实验结果显示当n=6或n=5时,质量损失微小.3.3顶点位置预测要提高点的预测的准确性,需充分利用点之间的相关性.几何图形中点之间的相关性由点描述的图元决定.AnyGL中共有10种基本图元,其预测算法可分为 4类:1, 线性预测这类图元包括离散点,离散线段,离散三角形,离散四边形和不闭合折线.这些图元的共同特点是顶点间相关性较弱,没有一种明显的趋势能对下一个点的预测提供指导.对这些图元可使用线性预测器:1(,)kniiλ==n-1n-2n-kn-iPv,v,...vv

λ其中Pn为第n个点的预测值,vi(x,y,z)数,λi是vn-i 对Pn的影响力的度量如取λ=(0.5,0.3,0.2) 进行三阶预测2, 闭合原则

为第i个点.k为阶数,λ为预测系.,则Pn=0.5vn-1+0.3vn-2+0.2vn-3.对多边形和闭合折线,(v0,v1,⋯⋯vn)呈现一种闭合的趋势,若已知vn-1,vn-2,vn-3,可以推测Pn将继续闭合的趋势前进,方向与上一次相同,步长位前两次步长的均值 ,如图4(c):∠Pnvn-1vn-2=∠vn-1vn-2vn-3||||||2+=n-2n-1n-3n-2n-1nvvvvvP3, 平行四边形法则平行四边形法则[11]常用以进行三角形条带(trianglestrip) 的预测,如图4(a),其公式为:Pn=vn-2+vn-1-vn-3平行四边形法则隐含的假设是:随着顶点的发射,三角形条带趋向于模仿前一个三角形均匀地向前"生长".四边形条带也有此种特点,因此可对前一个四边形运用两次平行四边形法则,作为对下两个顶点的预测,如图4(b),其中:Pn=vn-2+vn-1-vn-3Pn+1=vn-1+vn-2-vn-44,三角形扇形与三角形条带一样,三角形扇(trianglefan)也常用于三维物体的表达.第i个三角形的顶点为(v1,vi+1,vi+2),v1为扇的中心,固定不变.观察可见,在以v1为圆心的极坐标下,Pn趋向于以一定的半径在扇"打开"的方向上继续转动一个角度,如图4(d):∠Pnv1vn-1=∠vn-1v1vn-2|v1Pn|=||||2+n-11n-21vvvvnP1nP+平行四边性法则nP1nv-2nv-3nv-1nv-2nv-3nv-4nv-四边形条带预测nP1nv-2nv-3nv-闭合原则nP1v1nv-2nv-三角形扇形预测图4顶点预测3.4顶点位置自适应量化量化是位置数据压缩的另一个重要环节.量化函数Q为:]),[(5.02))(1(),,(LLxLLxKLKxQ-∈++-=其中K为量化电平数,当编码长度为N时,K=2N,L限定了量化范围,L>0,Q(x,K,L)输出整数,用以进行编码.正常量化的条件是x∈[-L,L].一般的压缩方法需先对样本空间进行遍历以确定Max(|x|),并令L≥Max(|x|),以保证x∈[-L,L].而从AnyGL的工作原理可知,AnyGL无法进行样本的遍历,出于时间效率的考虑,也不允许进行遍历操作.几何数据来自应用程序,而后者的行为是无法预料的,所以量化溢出,即],[LLx- 是不可避免的.这要求量化算法:一,能处理量化溢出;二,动态确定并优化L,使得量化误差和溢出概率都较小.对问题一的解决办法是定义溢出标志数Coverflow,来标识溢出事件的发生.如取Cover