Уменьшение накладных расходов на мьютекс в многопоточных воксельных алгоритмах

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

Чтобы прояснить мою проблему, возьмем 2D-случай:

+-+-+-+
|A|B|C|
+-+-+-+
|D|E|F|
+-+-+-+
|G|H|I|
+-+-+-+

Все эти ячейки представляют собой воксельные блоки (16x16 вокселей).

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

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

Однако, как я экспериментировал, накладные расходы на производительность с мьютексами невысоки. В настоящее время я использую простой цикл for для добавления заданий. Итак, когда игра запускается, начальная очередь заданий будет выглядеть примерно так:

A, B, C, D, E, F, G, H, I, ...

Это действительно плохо, поскольку первое задание A блокирует A, B, D, E и выполняет все следующие восемь заданий в ожидании мьютексов, что снижает производительность.

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

Я также подумал об использовании «асинхронных мьютексов». Но я не совсем уверен, как это сделать.

РЕДАКТИРОВАТЬ: Чтобы уточнить, задания освещения добавляются во время выполнения, а не в фиксированном порядке. Например, представьте, что игрок выходит из обрабатываемых в данный момент фрагментов, тогда в очередь должны быть добавлены только внешние фрагменты, которые могут находиться на нерегулярной границе.

Поэтому я считаю, что для решения этой проблемы недостаточно использовать только достойный планировщик.


c++ multithreading algorithm mutex voxel
person Xiangyan Sun    schedule 23.04.2014    source источник
comment
Предполагая, что ваши воксельные фрагменты не слишком велики, можно ли скопировать затронутые фрагменты, обработать их и объединить результаты в конце? например. Поток 1 извлекает блок A, видит, что ему нужно осветить блоки C и F. Затем он копирует C и F и приступает к работе с ними. Поток 2 извлекает блок B и видит, что он также должен работать с C. Он также копирует C и работает с ним. После того, как все фрагменты обработаны, основной поток получает результаты от каждого потока и выполняет аддитивное смешивание, чтобы получить окончательную карту освещения.   -  person Wes    schedule 23.04.2014
comment
@Wes Умная идея. Но большинство используемых мной алгоритмов вокселей (включая освещение) должны иметь производительность, близкую к уровню O (N) (N - размер блока). Дополнительный этап посещения всех фрагментов в основном потоке делает многопоточность бесполезной.   -  person Xiangyan Sun    schedule 23.04.2014
comment
Являются ли все блоки кода взаимоисключающими? То есть, если вы не можете ничего сделать для B во время A, просто переместите B в конец очереди и выберите следующий элемент. Конечно, это может не сработать, если вы уже поработали для B. Думаю, вы не хотите откатывать работу.   -  person Vincent van der Weele    schedule 23.04.2014
comment
@Heuster: Это взаимоисключающие. Или, по крайней мере, мне нужно выполнить дополнительные шаги по смешиванию, как сказал @Wes. Ваш подход должен работать теоретически. Но как сохранить и получить информацию о том, кто над какими блоками работает? На приведенном выше рисунке я последовательно блокирую мьютексы (например, для E, блокировка A, B, C, ..., I, один за другим). Потому что мы не можем атомарно заблокировать все девять мьютексов одновременно, и эта схема может избежать тупиковых блокировок. Если он без мьютексов или, возможно, с использованием mutex.tryLock (), как избежать взаимоблокировок (и, возможно, живых блокировок)?   -  person Xiangyan Sun    schedule 23.04.2014
comment
Хорошо, как часто такое столкновение происходит? Я понимаю, что такие события не должны происходить, но если они относительно нечасты, должна быть возможность разработать лучшую стратегию защиты от коллизий, которая позволяет избежать девяти блокировок мьютексов в случае отсутствия коллизий, но требует дополнительных действий, когда коллизия действительно обнаружена. . Это улучшило бы производительность в целом.   -  person Martin James    schedule 23.04.2014

Ответы (2)


arrow_upward
1
arrow_downward

Это слишком долго, чтобы поместиться в разделах комментариев.

Как насчет использования атомарного логического значения, чтобы узнать, обрабатывается ли кусок в данный момент? Таким образом вы получите более высокое использование потоков вместо потоков, ожидающих обработки. Кроме того, если вы запустите каждый поток в одинаково распределенных точках, вы получите меньше столкновений. Затем этот алгоритм просто решает проблему, когда потокам необходимо работать с одними и теми же фрагментами.

  1. Поток 1 получает фрагмент A (влияет на фрагменты B и C) и устанавливает флаг обработки A.
  2. Поток 2 одновременно получает фрагмент B и устанавливает флаг обработки B.
  3. Поток 1 завершает блок A, сбрасывает флаг A и проверяет, доступен ли блок B.
  4. Поток 2 занят B, поэтому поток 1 оставляет B необработанным пока переходит на C и устанавливает флаг C.
  5. Поток 2 заканчивается на B сбрасывает флаг B.
  6. Поток 1 завершает C и сбрасывает флаг C, а затем переходит к B. B уже имеет результаты потока 2, поэтому поток 1 выполняет последний проход на B и готов.
person Wes    schedule 23.04.2014
comment
Проблема в том, что мой текущий алгоритм освещения требует, чтобы были доступны все 9 блоков, и обрабатывает их все сразу. Это не может быть частичным и возобновляемым. Это поведение требуется не только для алгоритма освещения, но и для некоторых алгоритмов процедурной генерации, которые я использую (необходимо, чтобы все соседние фрагменты работали). Использование этого подхода значительно усложнит кодирование. - person Xiangyan Sun; 23.04.2014

arrow_upward
0
arrow_downward

как насчет планирования с некоторым смещением между потоками, например:

offset-ed sheduling

  • разные цвета означают разные рабочие потоки
  • изображение представляет одну строку на вашей карте
  • больше в тексте ниже

У вас есть 4 или 8 соседей и, например, 4 рабочих потока

  • для ясности ячейка 0102 означает строку = 01 столбец - 02 (все отсчитываются от 0)

    thread 0000 00001 0002 0003
-------------------------
       cell cell cell cell
-------------------------
       0000 0003 0006 0009
       0001 0004 0007 0010
       0002 0005 0008 0011

       0012 0015 0018 0021
       0013 0016 0019 0022
       0014 0017 0020 0023

       0024 0027 0030 0033
       0025 0028 0030 0034
       0026 0029 0030 0035

       ... till end of row

       0100 0103 0106 0109
       0101 0104 0107 0110
       0102 0105 0108 0111

       0112 0115 0118 0121
       0113 0116 0119 0122
       0114 0117 0120 0123

       0124 0127 0130 0133
       0125 0128 0130 0134
       0126 0129 0130 0135

       ... till end of row
       ... till end map

  • чем больше зазор между нитками, тем лучше

  • 2 пробела минимум
  • при достижении конца строки потоки должны дождаться завершения, прежде чем планировать следующую строку
  • also you can completely avoid conflicts when you shedule the gap edge first and then the rest
    • instead of 0000,0001,0002 would be 0002,0000,0001

Такой подход может создавать артефакты распространения данных !!!

  • потому что данные не передаются непрерывно между соседями
  • поэтому может появиться какая-то сетка, похожая на артефакты ...
person Spektre    schedule 23.04.2014