代码之家 › 专栏 › 技术社区 › No1Lives4Ever

OpenCL-将树复制到设备内存

binary-tree opencl tree c

No1Lives4Ever · 技术社区 · 9 年前

我用C代码实现了一个二进制搜索树。我的每个树节点如下所示:

typedef struct treeNode {
    int key;
    struct treeNode *right;
    struct treeNode *left;
} treeNode_t;

主人建造的树。设备对树的查询。

现在,假设我已经完成了在主机内存中构建树。我想将树的根复制到设备的内存中。

复制树根本身是不够的。因为右\左子项不在设备内存中。这是一个问题。

所以,我的问题是,将整个树复制到设备内存的最简单方法是什么?

2 回复 | 直到 9 年前

Jan Lucas 9 年前

最简单(可能也是最好的)方法是更改结构,使用节点索引而不是指针。指针的问题是设备具有不同的指针,即使您单独复制所有节点,它仍然无法工作,因为指针也需要更新为设备指针。不幸的是,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字节也会有所帮助。

doqtor 9 年前

如果您的设备支持OpenCL 2.0,则可以使用 Shared Virtual Memory 。在主机上创建的指针也将在设备上有效。以下是描述和二进制搜索树示例: opencl-2-shared-virtual-memory .

推荐文章

Ash · 递归列表拆分和索引

2 年前

Tuna ArÄ±yÃ¼rek · “结构对象*对象”和“对象*对象”之间的区别

2 年前

Zevvysan · 为什么我的打印函数之一要删除节点?

7 年前

codingBoy · 使用python进行二叉树修剪[postorder方法不起作用]

7 年前

user9573040 · 递归二叉树高度

7 年前

Dipesh Desai · 在二叉树haskell中搜索值

7 年前

Yuki.kuroshita · 从二叉树中删除节点及其所有子节点,而不使用树数据结构

7 年前

MMelvin0581 · 为什么在我的LinkedBinaryTree实现中只添加根目录

7 年前

Shuklaswag · 为什么我们要通过堆而不是二进制搜索树进行排序?

7 年前

ibrahim · “main”已停止工作-C++[开发人员++]

7 年前