我用 C 代码实现了二叉搜索树。我的每个树节点如下所示:
typedef struct treeNode {
int key;
struct treeNode *right;
struct treeNode *left;
} treeNode_t;
宿主建造的树。设备对树进行的查询。
现在,假设我已经在主机内存中构建了树。
我想将树的根复制到设备的内存中。
复制树的根本身是不够的。因为右\左子节点不在设备内存中。这是个问题。
所以,我的问题是将整个树复制到设备内存的最简单方法是什么?
最简单(也可能也是最好)的方法是更改结构以使用节点索引而不是指针。指针的问题在于设备具有不同的指针,即使您单独复制所有节点,它仍然无法工作,因为指针还需要更新为设备指针。不幸的是,OpenCL 1.2 甚至不能保证设备指针的有效时间长于单个内核调用的时间。因此,至少在设备上您必须使用索引而不是指针。
像这样修改你的结构:
typedef struct treeNode {
int key;
int left;
int right;
} treeNode_t;
在构建树之前,您需要分配一大树节点数组,该数组足够大以容纳所有节点。
treeNode_t nodes[MAX_NODES]; // or dynamic allocation
int first_free_node=0;
每次通常分配一个新节点时,现在都使用节点[first_free_node]来存储数据并递增first_free_node计数器。完成树的构建后,您只需使用单个 clEnqueueCopyBuffer 调用即可将所有节点复制到设备。您只需将 first_free_node*sizeof(treeNode_t) 字节从节点数组的开头复制到设备。如果您无法更改主机树构建代码,则可以使用树的简单递归深度优先遍历来计算节点数,并将节点从基于指针的格式转换为基于索引的格式。
在某些设备上,如果将树的结构从结构数组转换为数组结构,您可能会获得更高的性能。将结构填充到每个节点 16 字节也可能有所帮助。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)