技术开发 频道

基于点集的Balance kd-tree的并行构建

  【IT168 技术】

  注:本文为IT168&NVIDIA联合举办的“如何并行化我的应用”方案征集活动三等奖作品。本次方案征集活动详情见:http://cuda.itpub.net/thread-1299715-1-1.html。近期活动的大部分方案,将会逐步与大家分享,不可错过哦!

  CUDA ZONE专区:http://cuda.it168.com/

  CUDA技术论坛:http://cuda.itpub.net

        1、首先将点集的坐标数据转换成无符号整型。

  2、将数据按照X轴方向进行排序。

  3、将排序号的数据进行分割,如果slice中的元素个数是偶数则分成的2个slice正好相等,如果是奇数个数则中间的元素同时即属于左子slice又属于右子slice。

  4、对每一迭代层中的所有slice中的元素进行kdnode编码。

  5、然后在下一层迭代中对上面分成的2个slice分别独立的按照Y轴向排序,饼尽享如上不相同的操作步骤。

  6、这是一个递归(当然程序实现时时没有递归的,以为每个迭代层中的所有slice可以独立的并行计算。

  7、用户可以设置一个阀值,用来当每个slice中(kdnode)的元素数量小于该值时停止树的划分。

  8、及时对于相当大的数据规模,实际的迭代次数没有那么多,因为当每个slice的尺寸小于或等于最大可用的block尺寸时(为什么是最大尺寸的一半,因为要考虑slice尺寸为奇数划分时的长度扩展)对应于剩下的迭代中的划分,编码计算可以在内核中一次完成,这样最后的几步迭代实际上只调用一次内核就可以了。

  另外还需要注意的是,将浮点数转化成无符号整型后,还需要翻转符号位,因为负数的符号位是1,而正数的符号位是0,翻转后才能确保负数总是排在正数之前(假设按照从小到大的顺序)。

  还要记得,排序时XYZ坐标是关键字(每层的关键字coord[ level%3 ] ),而点ID是被排序的目标数组。

  还有一点需要注意,在准备数据前,要先根据阀值确定树最终将会构建都少层,然后再根据层数计算出扩展空间(如果当前slice中的元素是奇数个,那么当将其划分时程2个单独的slice后,这2个slice的长度将大于原来的slice尺寸,因此实现确定最大存储空间而不是计算中重新分配将更有效率)

  伪代码可以表示如下:

source_slice[];

  target_slice[];

  AXIS
=0;

  PROC Create_Point_Kdtree( target slice, source_slice, AXIS )

  {

  
while( slice_size

  {

  sort( source_slice, AXIS%
3 );

  split_slice( target_slice, source_slice );

  
++AXIS

  swap( target_slice, source_slice );

  
//这一步在用CUDA中实现时其实并不是在一个循环中计算,而是所有slice同事在一个grid上独立的进行计算

  
for slice_id= 0 to ( 2^level )-1

  {

  Create_Point_Kdtree( target_slice, source_slice, AXIS );

  }

  }

  }
0
相关文章