Многопоточное заливное заполнение

Я пытаюсь преобразовать существующие однопоточные алгоритмы заливки в многопоточные.

Вход: - 2-битный массив и его размеры - координаты xy, где должно начинаться заливка

Выход: - тот же двумерный битовый массив с обновленными битами

Проблема: - только 1 поток одновременно может писать в заданные 64 бита (8x8 пикселей) в массиве, также ни один другой поток не может читать этот 64-битный фрагмент во время записи

Я начал с подхода к очереди и пула потоков, поэтому, как только поток завершит свою работу, он может взять другую задачу из очереди.

Как бы вы организовали синхронизацию потоков в соответствии с «проблемой»?

Основная проблема в том, как назначить блокировку чтения / записи данному фрагменту памяти?


multithreading algorithm flood-fill
person Anonymous    schedule 30.12.2014    source источник
comment
Мне никогда не казалось, что заливка флудом поддается многопоточности. Следующее действие слишком зависит от предыдущих результатов. Удачи.   -  person Mark Ransom    schedule 30.12.2014
comment
Должен ли он начинаться с нескольких координат или с одной (x, y)?   -  person didierc    schedule 30.12.2014
comment
@didierc, только одиночные x, y. Он должен быстро заполнить множество точек, требующих рекурсии заполнения.   -  person Anonymous    schedule 30.12.2014
comment
Вы можете разделить область на квадранты от начальной точки и иметь 4 работающих потока, по одному для каждого из них.   -  person didierc    schedule 30.12.2014
comment
Фактически, вам, вероятно, следует переосмыслить порядок, в котором новые координаты должны помещаться в очередь, чтобы группировать координаты таким образом, чтобы потоки не наступали друг другу на пятки.   -  person didierc    schedule 30.12.2014
comment
Если у вас есть один поток, последовательно идущий в одном направлении, он будет перемещать координаты по сторонам линии, которую он рисует, в очередь. Теперь каждая новая нить может взять хорду и следовать в ортогональном направлении от исходной линии и никогда не попадать в другую линию нитки. Следуйте этому процессу, начиная с обоих направлений, скажем, оси X начальной позиции, и вставьте допустимые координаты выше и ниже этих линий, которые новые потоки будут отслеживать вертикально вверх и вниз.   -  person didierc    schedule 30.12.2014
comment
Однако с заливкой в ​​8 направлениях все становится немного сложнее.   -  person didierc    schedule 30.12.2014
comment
Что касается ограничения на битовые блоки, просто группируйте работу по блокам, то есть заставляйте потоки работать с блоками, а не с пикселями.   -  person didierc    schedule 31.12.2014
comment
@didierc, поднимающие 4-х направленные специализированные потоки довольно хорошо справляются со своей задачей (одновременно допускается ограничение не более 4 запущенных потоков). Действительно, потоки с ограничением блока - это то, на что я хотел бы переключиться, но он включает в себя несколько точек на границе соседнего блока, которые необходимо заполнить. Это усложняет ввод блочного потока, поскольку он должен принимать несколько начальных точек.   -  person Anonymous    schedule 31.12.2014

Ответы (1)


arrow_upward
2
arrow_downward

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

Вышеупомянутая общая «грубая» политика позволяет избежать распространенных ошибок (например, ложное совместное использование), которые предотвращают масштабирование.

Что касается вашей конкретной проблемы, я должен признаться, я не разбираюсь в алгоритмах заливки, поэтому я не могу сразу набросать грубый подход.

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

Еще одна возможность - реализация без блокировки. Возможно, для записи можно использовать операцию сравнения и замены (InterlockedCompareExchange64 в VS) в сочетании с логикой повтора, если другой поток записал в том же 64-битном блоке 8x8 пикселей.

Можно было бы полностью ослабить блокировку чтения. Если 2 потока заканчивают рисовать одни и те же пиксели, это может только напрасно тратить несколько циклов, но не повредить результаты.

Реализация без блокировки могла быть несколько раз быстрее.

Если вы работаете в Java, Java Concurrency на практике от Goetz - отличная книга о таких вещах, как разделение замков.

person Peter Lamberg    schedule 30.12.2014
comment
Спасибо за отзыв. Так, по вашему мнению, это убьет параллельную обработку из-за архитектуры кеша, или вы даете мне подсказку, как не попасть в проблемы с ограничением строки кеша? - person Anonymous; 30.12.2014
comment
Я постараюсь продолжить свой ответ. Одновременно смотрю годовалую: D - person Peter Lamberg; 30.12.2014
comment
Я просто пытался предупредить о неприятных проблемах, которые трудно увидеть, которые могут разрушить иначе умные стратегии распараллеливания. Может, попробую перепечатать свой пост ... - person Peter Lamberg; 30.12.2014
comment
Спасибо, я рисую эту штуку в объектах синхронизации c ++ и win32 + взаимосвязанные операции для управления потоками. Я занимаюсь полосой замков, чтобы посмотреть, подходит ли мне. PS: берегитесь подгузников, овл :) - person Anonymous; 30.12.2014
comment
Пожалуйста, разместите здесь свои результаты. Может быть отдельный ответ. - person Peter Lamberg; 30.12.2014
comment
Конечно, ты можешь выйти на свободу. Выполняйте каждую запись с внутренним сравнением и заменой в сочетании с логикой повтора. Это на несколько порядков быстрее, поскольку не требует операций по управлению потоками. - person Peter Lamberg; 30.12.2014
comment
Постараюсь завтра выложить, с результатами скамейки. Теперь у меня проблема с доступом к массиву :) - person Anonymous; 31.12.2014