opencl - opencl中的优先级队列

Question

我正在尝试在 OpenCL 上实现 A-Star 搜索算法，但无法找到实现优先级队列的方法。这是我在 .cl 文件中尝试执行的操作的总体思路

//HOW TO IMPLEMENT THESE??
void extractFromPriorityQueue();
void insertIntoPriorityQueue();
//HOW TO IMPLEMENT THESE??

__kernel void startAStar(//necessary inputs) {
 int id = get_global_id(0);
 int currentNode = extractFromPriorityQueue(priorityQueueArray,id);
  if(currentNode==0){
    return;
  }
 int earliest_edge = vertexArray[currentNode-1];
 int next_vertex_edge = vertexArray[currentNode];
 for(int i=earliest_edge;i<next_vertex_edge;i++){
    int child = edgeArray[i];
    float weight = weightArray[i];
    gCostArray[child-1] = gCostArray[currentNode] + weight;
    hCostArray[child-1] = computeHeuristic(currentNode,child,coordinateArray);
    fCostArray[child-1] = gCostArray[child-1] + hCostArray[child-1];
    insertIntoPriorityQueue(priorityQueueArray,child);
 }
}

另外，在这种情况下优先级队列是否必须同步？

Answer 1

下面是各种无锁 GPU 数据结构(包括跳过列表和优先级队列)的论文、pptx 和源代码的链接。然而源代码是CUDA。 CUDA 代码与 OpenCL 足够接近，您可以了解如何在 OpenCL 中实现此代码的要点。

优先级队列使用原子操作进行同步。队列节点在主机上分配并作为全局节点数组传递给函数。通过使用数组计数器的原子增量来获得新节点。

使用原子比较和交换(交换)调用将节点插入队列。纸张和ppx 解释工作原理和并发问题。

http://www.cse.iitk.ac.in/users/mainakc/projects.html

查看上页条目

并行编程/运行时支持 [ICPADS 2012][PDF][源代码][演讲幻灯片 (PPTX)] 普拉巴卡尔·米斯拉和迈纳克·乔杜里。 GPU 上并发无锁数据结构的性能评估。第 18 届 IEEE 国际并行和分布式系统 session 论文集，第 53-60 页，2012 年 12 月。

源代码链接为http://www.cse.iitk.ac.in/users/mainakc/lockfree.html