Уменьшить мьютекс в алгоритмах многопоточности вокселей
В настоящее время я внедряю многопоточный воксельный игровой движок. Когда я работаю с многопоточностью, я быстро сталкиваюсь с узкими местами производительности с мьютексами.
Для выяснения моей проблемы давайте возьмем 2D случай:
+-+-+-+
|A|B|C|
+-+-+-+
|D|E|F|
+-+-+-+
|G|H|I|
+-+-+-+
Все эти ячейки являются кусками вокселей (16×16 вокселей).
Я делаю все воксельные алгоритмы по частям, используя несколько потоков. У меня есть очередь заданий, состоящая из чанков, над которыми нужно работать, и каждый рабочий поток просто непрерывно выбирает чанки из очереди и работает над ней.
Теперь представьте, что одному потоку необходимо выполнить некоторые расчеты освещения в порции E. Поскольку в углу E может быть источник света, который будет распространяться на соседние порции, он должен заблокировать все девять соседних порций вокруг, чтобы избежать потенциальной гонки данных с использованием мьютексов. ,
Однако, как я экспериментировал, производительность с мьютексами не очень хорошая. В настоящее время я использую простой for цикл, чтобы добавить работу. Поэтому, когда игра запускается, начальная очередь заданий будет выглядеть примерно так:
A, B, C, D, E, F, G, H, I, ...
Это действительно плохо, так как первое задание A блокирует A, B, D, E и выполняет все последующие восемь заданий в ожидании мьютексов, убивая производительность.
В настоящее время единственное смягчение, о котором я могу подумать, — это попытаться добавлять рабочие места по-разному, надеясь, что мы сможем избежать большинства срывов. Но мне не нравится этот подход, так как он выглядит скорее как обходной путь и не очень гибкий, если меняется схема блокировки.
Я также думал об использовании «асинхронных мьютексов». Но я не очень уверен, как это сделать.
РЕДАКТИРОВАТЬ:
Просто чтобы уточнить, задания освещения добавляются во время выполнения, а не в фиксированном порядке. Например, представьте, что игрок перемещается из обрабатываемых в настоящий момент чанков, тогда в очередь должны быть добавлены только внешние чанки, которые могут находиться в нерегулярной границе.
Поэтому я думаю, что использование приличного планировщика недостаточно для решения этой проблемы.
Решение
Это слишком долго, чтобы поместиться в разделах комментариев.
Как насчет использования атомарного bool, чтобы увидеть, обрабатывается ли чанк в данный момент? Таким образом, вы получите более высокое использование потоков вместо потоков, ожидающих обработки. Также, если вы начнете каждый поток в одинаково распределенных точках, вы получите меньше столкновений. Затем этот алгоритм просто решает проблему, когда потоки должны работать с одинаковыми блоками.
- Поток 1 получает блок A (влияет на фрагменты B и C) и устанавливает флаг обработки A.
- Поток 2 одновременно получает блок B и устанавливает флаг обработки B.
- Поток 1 завершает блок A и сбрасывает флаг A и проверяет, доступен ли блок B.
- Поток 2 занят B, поэтому поток 1 оставляет B необработанным, а пока перемещается на C и устанавливает флаг C.
- Поток 2 заканчивается буквой B, сбрасывает флаг B.
- Поток 1 завершает C и сбрасывает флаг C, а затем перемещается к B. B уже имеет результаты потока 2, поэтому поток 1 делает последний проход на B и завершается.
Другие решения
как насчет планирования с некоторым смещением между потоками, как это:
- разные цвета означают разные рабочие нити
- изображение представляет одну строку на вашей карте
- больше в тексте ниже
У вас есть 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 пробела
- при достижении конца строки потоки должны ждать завершения всех перед планированием следующей строки
- Кроме того, вы можете полностью избежать конфликтов, когда вы будете сначала планировать край пропуска, а затем остальные
- вместо 0000,0001,0002 будет 0002,0000,0001
Этот подход может создавать артефакты распространения данных !!!
- потому что данные не распространяются непрерывно между соседями
- так что могут появиться некоторые сетчатые артефакты …