Я хочу реализовать структуры данных Disjoint set и алгоритм Крускала в OpenCL. Я реализовал некоторые коды в OpenCL, но не знаю, как начать работу со структурами данных в OpenCL. Алгоритм Джкстры, приведенный в книге Афтаба Мунши, сложен для понимания. Может ли кто-нибудь предложить другой источник...?
Реализация непересекающихся множеств и алгоритма Крускала (и других структур данных) в OpenCL
Ответы (1)
Я предлагаю вам начать с простой версии C алгоритма, например:
http://prabhakargouda.hubpages.com/hub/Kruskal-algorithm-implementation-in-C
Оцените, что можно сделать параллельно. В приведенном выше коде есть несколько вложенных циклов for, которые могут выполняться параллельно. Матрица смежности является хорошей параллельной структурой по сравнению с указателями в дереве. Так что постарайтесь использовать это.
Помните, что не все этапы алгоритма можно выполнять параллельно. Поэтому начните с самых внутренних циклов for и выполняйте реализацию поэтапно.
Также обратите внимание, что указанный выше код не связан авторскими правами или лицензиями. Так осторожно, как вы его используете. Не забудьте указать авторские права там, где это необходимо.
person
Tim Child
schedule
04.02.2013
Я реализовал алгоритм kruskal в C, используя непересекающиеся наборы (Quick Union)... Но я не знаю, как структуры данных представлены в OpenCl. Чтобы быть более конкретным, я не знаю, как выполняется динамическое выделение памяти в коде хоста. OpenCL, а затем то, как эти переменные передаются в ядре. Я знаю, что динамическое выделение памяти не может быть выполнено в ядре OpenCL, так как же программируются структуры данных в OpenCL.
- person shunya; 05.02.2013
