4

我正在尝试在 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);
 }
}

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

4

2 回答 2

0

如果不支持原子操作，还有另一种方法。您可以使用这个想法来并行化 Harish 和 Narayanan 的论文Accelerating large graph algorithms on GPU using CUDA中的 Dijkstra 的最短路径算法。

他们建议复制数组以与 Mask、Cost 和 Update 数组的想法同步。

Mask 是一个唯一的布尔数组，用于表示具有此大小的队列。如果此数组中的元素i为真，则元素i在队列中。

有两个内核可以保证同步：

  • 第一个内核只从 Cost 数组中读取值，并且只在 Update 数组中写入。
  • 第二个内核仅在成本值与更新不同时才更新成本值。在这种情况下，升级后的元素将设置为 true。

这个想法有效，并且在 OpenCL 编程指南的书中有一个案例研究的实现：https ://code.google.com/p/opencl-book-sa​​mples/source/browse/trunk/src/Chapter_16#Chapter_16% 2FDijkstra。

于 2014-01-05T16:51:09.580 回答
0

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

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

使用原子比较和交换（交换）调用将节点插入队列。论文和 ppx 解释了工作原理和并发问题。

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

请参阅上页中的条目

并行编程/运行时支持 [ICPADS 2012][PDF][Source code][Talk slides (PPTX)] Prabhakar Misra 和 Mainak Chaudhuri。GPU 上并发无锁数据结构的性能评估。在第 18 届 IEEE 并行和分布式系统国际会议论文集上，第 53-60 页，2012 年 12 月。

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

于 2013-06-29T20:48:18.310 回答