实时碰撞检测算法中的数据缓存优化技术研究.pdf

《实时碰撞检测算法中的数据缓存优化技术研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、学术探讨∙算法研究实时碰撞检测算法中的数据缓存优化技术研究殷存举邵小兰（江苏联合职业技术学院常州刘国钧分院，江苏常州213000）[摘要]在实时碰撞系统中，数据缓存的利用率对性能有极大的影响，本文通过重新设计算法和数据结构，并以一种更具预测性、线性或部分线性的方式访问数据，有效地改善数据局域性特征。达到降低数据尺寸、提高空间和时间局域性特征进而提高数据缓存利用率的目的。[关键字]数据缓存；访问频率；优化；数据压缩中图分类号：TP333文献标识码：A文章编号：1008-6609(2016)05-0054-03int64e;1结构优化floatf;针对数据缓存

2、的改进措施，首先考查结构和类的优化方};案，包括以下三点：structY{（1）降低结构的整体尺寸。使用恰当的位数表示数字，int8a,pad_a[7];从而可降低缓存单元中匹配数据量以及结构中相关字段的int64b;内存读取次数。int8c,pad_c[1];（2）在结构内适当地重组字段。结构内的相应字段通常int16d,pad_d[2];按照其自身含义加以分类，但从本质上讲应以访问模式加以int64e;分组，以使字段的访问-存储过程相吻合。floatf,pad_f[1];（3）根据数据的使用频率划分结构。由于结构内部相关};字段的访问频率不同，可将那些

3、不经常访问的字段置入单一structZ{结构中，从而增加频繁受访数据缓存间的一致性，特别在该int64b;结构是数组或其他聚合型数据结构的某一部分时。int64e;许多平台上的对齐操作将会迫使编译器对相关结构实floatf;施填充操作，即N字节字段将实现N字节对齐。由于填充结int16d;构的对齐尺寸往往是该结构中最大N字节字段的某一倍数，int8a;因此会浪费一部分内存空间。考虑到填充操作，按降序排序int8c;成员变量将在一定程度上节省内存空间。另外，某些编译器};会提供相应的警告，以助于检测当前内存空间的消耗状态。则多数编译器将会生成如下结果：基于M

4、IPS平台的体系结构往往有相应的对齐限制。其Sizeof(X)==40，Sizeof(y)==40，Sizeof(z)==24（这里，假设中，若定义了下列数据结构：float类型为4字节）。与排序后的结构Z相比，结构X的填充structX{数据占据了全部内存空间的40%（如结构Y所示）。其他缩int8a;减结构尺寸的相关方法如下：int64b;（1）从已存储值可轻易计算得到的数据值则不要存储于int8c;结构中，以避免额外的缓存读取操作。int16d;（2）可能的话，尽量使用小尺寸的整型数据。——————————————作者简介：殷存举，男，山东费县人，硕

5、士，副教授，研究方向：智能信息处理。-54-学术探讨∙算法研究（3）采用位域表示法而非布尔值。尽量不采用Bool类值Value时，则增加该元素的count字段值。型的标志变量，可将全部标志封装至某一位域中。Bool变量structS{的尺寸是依赖于机器环境的，其范围从一个字节至长整型数int32value;据不等。将多个标志存储于位格式中，可将所需内存空间至int32count;少减少至1/8，通常为1/32甚至更少。...（4）采用偏移量而非用于索引数据结构的指针。指针通}elem[1000];常为4字节（或更多）固定尺寸变量，而偏移量的尺寸可根据//F

6、indtheindexoftheelementwithlargestvalue索引项的数量产生变化。例如，2字节偏移量可索引包含216intindex=0;个对象的数组。for(inti=0;int<1000;i++)由于缓存失效将导致计算开销急剧增加，因此必须谨慎if(elem[i].value>elem[index].value)index=i;处理压缩/非压缩数据。//Incrementthecountfieldofthatelement需要指出的是，在某些系统结构中，上述方案可能会带elem[index].count++;来额外的cpu计算开销。例

7、如，附加指令要求针对小尺寸整如果上述基于结构数组的搜索过程视为核心操作，则应型数据或位域中的某一位进行操作。随着指令运行数量的将结构S划分为高频受访字段结构（S1）和低频受访字段结增加，缓存压力也将会随之增长，进而会逐渐抵消缓存优构S2.上述代码可改写为：势。因此，对代码进行优化测试不失为一种较好的解决方案//HotfieldsofS——理想情况下，可对变化前后的代码分别进行测试，从而structS1{采取相应的改进方案。Int32value;对相关字段加以记录实现起来并非易事。在某些情况}elem1[100];下，多个字段将存储于同一缓存单元中，尤其是多

8、个字段被同时访问时。考查下列情况，位置、速度以及加速字段经常//C