【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尺寸,因此实现确定最大存储空间而不是计算中重新分配将更有效率)
伪代码可以表示如下:
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 );
}
}
}