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 algorithm on the GPU using CUDAから Dijkstra の Shortest Path Algorithm を並列化できます。

彼らは、マスク、コスト、および更新配列のアイデアと同期するために配列を複製することを提案しています。

Mask は、このサイズのキューを表す一意のブール配列です。この配列の要素iが true の場合、要素iはキューにあります。

同期を保証する 2 つのカーネルがあります。

  • 最初のカーネルは、Cost 配列から値を読み取るだけで、Update 配列に書き込むだけです。
  • 2 番目のカーネルは、Cost 値が Update と異なる場合にのみ、Cost 値を更新します。その場合、アップグレードされた要素は 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][ソース コード][トーク スライド (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 に答える