Приоритетная очередь в opencl

Question

Я пытаюсь реализовать алгоритм поиска A-Star в OpenCL и не могу найти способ реализовать приоритетную очередь для него. Вот общее представление о том, что я пытаюсь сделать в моем файле.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

Есть другой способ, если атомарные операции не поддерживаются. Вы можете использовать эту идею для распараллеливания алгоритма кратчайшего пути Дейкстры из статьи Хариша и Нарайанана. Ускорение алгоритмов с большими графами на графическом процессоре с использованием CUDA.

Они предлагают продублировать массивы для синхронизации с идеями массивов Mask, Cost и Update.

Маска - это уникальный логический массив, представляющий очередь с таким размером. Если элемент i в этом массиве равен true, элемент i находится в очереди.

Есть два ядра, которые гарантируют синхронизацию:

• Первое ядро ​​читает только значения из массивов Cost и записывает только в массивы Update.
• Второе ядро ​​обновляет только значения Cost, если они отличаются от Update. В этом случае обновленный элемент будет установлен в значение true.

Идея работает, и в книге "Руководство по программированию OpenCL" реализована реализация кейса: https://code.google.com/p/opencl-book-samples/source/browse/trunk/src/Chapter_16.

Answer 2

Ниже приведены ссылки на документ, pptx и исходные тексты для различных структур данных GPU без блокировки, включая список пропусков и приоритетную очередь. Однако исходный код CUDA. Код CUDA достаточно близок к OpenCL, чтобы вы могли понять суть того, как реализовать это в OpenCL.

Очередь приоритетов синхронизируется с помощью атомарных операций. Узлы очереди размещаются на хосте и передаются в функции как глобальный массив узлов. Новый узел получается с помощью атомарного приращения счетчика массива.

Узлы вставляются в очередь с помощью атомарных вызовов сравнения и обмена. Бумага и ppx объясняют работу и проблемы параллелизма.

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

Смотрите запись на странице выше

Параллельное программирование / Поддержка времени выполнения [ICPADS 2012][PDF][Исходный код] [Разговорные слайды (PPTX)] Прабхакар Мисра и Майнак Чаудхури. Оценка производительности параллельных структур данных без блокировок на графических процессорах. В материалах 18-й Международной конференции IEEE по параллельным и распределенным системам, стр. 53-60, декабрь 2012 г.

Ссылка на исходный код: http://www.cse.iitk.ac.in/users/mainakc/lockfree.html