алгоритм параллельной выпуклой оболочки в графическом процессоре

Question

Я реализую подход «разделяй и властвуй» для выпуклой оболочки в CUDA. Это мой подход: Вверху:

• Создать список списков для хранения выпуклых оболочек;

• curSize = размер ввода (все точки);

• для i: 1 для входа N

• начать
• curSize = curSize / 2;
• Взять каждые 2 соседних выпуклых корпуса в список списков и объединить их в больший корпус (используя стандартный верхний и нижний общий тангенс подход для разделения и завоевания выпуклой оболочки) в потоках curSize
• // Сначала он объединяет каждые 2 соседние точки в списке в оболочку, затем в следующей итерации он объединяет выпуклые корпуса размером 2 в более крупные выпуклые оболочки и т. д., наконец, список списков будет иметь единый список точек на корпусе
• конец

Но это становится слишком сложным, и я чувствую, что не использую параллельную мощь CUDA, так как на каждом уровне дерева я создаю N / 2 ^ i потоков, сложность которых O (N) при объединении всех смежных оболочек на этом уровне , Следовательно, сложность сети по-прежнему равна O (N logN).

Можете ли вы сказать мне, как его улучшить, или дать альтернативный параллельный алгоритм для выпуклой оболочки (было бы здорово, если бы я мог получить алгоритм для параллельной версии сканирования Грэма)?

Answer 1

Сложность вашего алгоритма все еще O (N) (не изменилась по сравнению с однопоточной версией), потому что вы делаете 3 вещи:

1. Управление потоками: O (N)
2. Удалить некоторые вершины из списков: амортизированный O (N), поскольку существует только N точек.
3. Посмотрите на точки, смежные с удаленными, но не удаленные во время текущего шага: O (N), так как для каждого слияния не более 2 таких точек.

Но если ваши точки не отсортированы, вам лучше распараллелить сортировку.