Я не совсем уверен, что это правильно, но я подумал, что выкину это для комментариев.Во-первых, позвольте мне ввести алгоритм непересекающегося множества без блокировки, который станет важной частью предложенного мной алгоритма.
Алгоритм непересекающегося множества без блокировки
Я предполагаю наличие сравнения размером с два указателя-и-своп операции на ваш выбор архитектуры процессора.Это доступно как минимум для архитектур x86 и x64.
Алгоритм в основном такой же, как описан на странице Википедии для однопоточного регистра , с некоторыми изменениями для безопасной работы без блокировки.Во-первых, мы требуем, чтобы элементы rank и родительские элементы имели размер указателя и были выровнены в 2 * sizeof (указатель) в памяти, для атомарного CAS позже.
Find () не нужно изменять;в худшем случае оптимизация сжатия пути не будет иметь полного эффекта в присутствии одновременно пишущих.
Union (), однако, должен измениться:
function Union(x, y)
redo:
x = Find(x)
y = Find(y)
if x == y
return
xSnap = AtomicRead(x) -- read both rank and pointer atomically
ySnap = AtomicRead(y) -- this operation may be done using a CAS
if (xSnap.parent != x || ySnap.parent != y)
goto redo
-- Ensure x has lower rank (meaning y will be the new root)
if (xSnap.rank > ySnap.rank)
swap(xSnap, ySnap)
swap(x, y)
-- if same rank, use pointer value as a fallback sort
else if (xSnap.rank == ySnap.rank && x > y)
swap(xSnap, ySnap)
swap(x, y)
yNew = ySnap
yNew.rank = max(yNew.rank, xSnap.rank + 1)
xNew = xSnap
xNew.parent = y
if (!CAS(y, ySnap, yNew))
goto redo
if (!CAS(x, xSnap, xNew))
goto redo
return
Это должно быть безопасно вчто он никогда не будет образовывать петли и всегда приведет к правильному объединению.Мы можем подтвердить это, наблюдая, что:
- Во-первых, до завершения один из двух корней всегда будет заканчиваться родительским указателем, указывающим на другого.Следовательно, до тех пор, пока петли нет, слияние будет успешным.
- Во-вторых, ранг всегда увеличивается.После сравнения порядка x и y мы знаем, что x имеет более низкий ранг, чем y во время моментального снимка.Для формирования цикла другой поток должен был бы сначала увеличить ранг x, а затем объединить x и y.Однако в CAS, который записывает родительский указатель x, мы проверяем, что ранг не изменился;следовательно, ранг y должен оставаться больше x.
В случае одновременной мутации возможно , что ранг y может быть увеличен, а затем вернуться к повтору из-за конфликта,Однако это означает, что либо y больше не является корнем (в этом случае ранг не имеет значения), либо что ранг y был увеличен другим процессом (в этом случае второе вращение не будет иметь никакого эффекта, а y будет иметь правильный ранг).
Следовательно, не должно быть никаких шансов на формирование петель, и этот алгоритм без блокировок дизъюнкт-множества должен быть безопасным.
А теперь перейдем к приложению к вашей проблеме...
Допущения
Я делаю предположение, что ребристые сегменты могут пересекаться только в своих конечных точках.Если это не так, вам нужно каким-то образом изменить фазу 1.
Я также делаю предположение, что совместное размещение одного целочисленного пиксельного местоположения является достаточным для соединения сегментов гребня.Если нет, вам нужно будет изменить массив в фазе 1, чтобы он содержал несколько потенциальных сегментов гребня + пары непересекающихся наборов, и отфильтруйте их, чтобы найти те, которые действительно связаны.
Структуры непересекающихся множеств, используемые в этом алгоритмедолжны иметь ссылку на отрезок в своих структурах.В случае слияния мы выбираем один из двух записанных сегментов произвольно для представления набора.
Этап 1: Идентификация локальной линии
Мы начинаем с разделения карты на сектора, каждый из которыхкоторый будет обрабатываться как отдельная работа.Несколько заданий могут обрабатываться в разных потоках, но каждое задание будет обрабатываться только одним потоком.Если ребристый сегмент пересекает сектор, он разделяется на два сегмента, по одному для каждого сектора.
Для каждого сектора устанавливается позиция пикселя отображения массива в структуру непересекающихся множеств.Большая часть этого массива будет отброшена позже, поэтому его требования к памяти не должны быть слишком обременительными.
Затем мы проходим по каждому отрезку в секторе. Сначала мы выбираем непересекающееся множество, представляющее всю линию, частью которой является сегмент. Сначала мы ищем каждую конечную точку в массиве позиций пикселей, чтобы увидеть, была ли уже назначена структура непересекающихся множеств. Если одна из конечных точек уже находится в этом массиве, мы используем назначенный непересекающийся набор. Если оба находятся в массиве, мы выполняем объединение непересекающихся множеств и используем новый корень в качестве нашего множества. В противном случае мы создаем новый дизъюнктный набор и связываем со структурой дизъюнктного набора ссылку на текущий сегмент линии. Затем мы записываем обратно в массив позиции пикселя корень нашего нового непересекающегося набора для каждой из наших конечных точек.
Этот процесс повторяется для каждого отрезка в секторе; к концу мы полностью идентифицируем все линии внутри сектора с помощью несвязного множества.
Обратите внимание, что поскольку непересекающиеся множества еще не разделены между потоками, нет необходимости использовать операции сравнения и замены; просто используйте обычный однопоточный алгоритм объединения-слияния. Поскольку мы не освобождаем ни одну из структур непересекающихся множеств до тех пор, пока алгоритм не завершится, выделение может быть также выполнено с помощью бампера-распределителя для каждого потока, что делает выделение памяти (практически) без блокировки и O (1).
Как только сектор полностью обработан, все данные в массиве позиций пикселей отбрасываются; однако данные, соответствующие пикселям на границе сектора, копируются в новый массив и сохраняются для следующего этапа.
Поскольку перебор всего изображения равен O (x * y), а disjoint-merge фактически равен O (1), эта операция - O (x * y) и требует рабочей памяти O (m + 2 * x * y). / k + k ^ 2) = O (x * y / k + k ^ 2), где t - количество секторов, k - ширина сектора, а m - количество частичных отрезков в секторе ( в зависимости от того, как часто линии пересекают границы, m может значительно отличаться, но оно никогда не будет превышать количество отрезков линии). Память перенесена на следующую операцию: O (m + 2 * x * y / k) = O (x * y / k)
Фаза 2: Межсекторное слияние
После обработки всех секторов мы переходим к объединению линий, которые пересекают сектора. Для каждой границы между секторами мы выполняем операции слияния без блокировки над линиями, которые пересекают границу (т. Е. Когда смежные пиксели на каждой стороне границы были назначены наборам линий).
Эта операция имеет время выполнения O (x + y) и использует O (1) памяти (однако мы должны сохранить память из фазы 1). По окончании краевые массивы могут быть отброшены.
Фаза 3: Сбор линий
Теперь мы выполняем операцию многопоточного отображения над всеми выделенными объектами структуры с непересекающимся множеством. Сначала мы пропускаем любой объект, который не является корнем (т. Е. Где obj.parent! = Obj). Затем, начиная с репрезентативного отрезка, мы оттуда выезжаем, собираем и записываем любую необходимую информацию о рассматриваемой линии. Мы уверены, что только один поток просматривает любую строку за раз, поскольку пересекающиеся линии оказались бы в одной структуре с непересекающимися множествами.
Это время выполнения O (m) и использование памяти в зависимости от того, какую информацию вам нужно собрать об этих отрезках.
Резюме
В целом, этот алгоритм должен иметь время работы O (x * y) и использование памяти O (x * y / k + k ^ 2). Регулировка k дает компромисс между использованием переходной памяти на процессах фазы 1 и долгосрочным использованием памяти для массивов смежности и структур с непересекающимся множеством, перенесенных на фазу 2.
Обратите внимание, что я на самом деле не тестировал производительность этого алгоритма в реальном мире; также возможно, что я упустил из виду проблемы параллелизма в алгоритме объединения-объединения без блокирования дизъюнкт-множества выше. Комментарии приветствуются:)