Безопасное обновление матрицы больших данных: теперь используются миллионы мьютексов?

Question

Я пересматривал некоторый код, который написал много лет назад, и решил переписать его, чтобы лучше использовать потоки (и лучше использовать программирование в целом ..).

Он находится здесь: https://github.com/buddhabrot/buddhabrot/blob/master/basic.c:

Это приложение, которое отображает фрактал buddhabrot.По причинам, выходящим за рамки этого вопроса, трудно использовать запоминание, чтобы оптимизировать это, и в основном, если вы профилируете это, более 99% времени тратится в самом внутреннем цикле, который в конечном итоге делает:

buddhabrot[col][row]++;

Несколько потоков выполнят этот код.Поскольку приращение не является поточно-ориентированным, я использовал специальную блокировку мьютекса вокруг этой части памяти.Итак, каждое адресуемое место в памяти buddhabrot имеет отдельный мьютекс.

Теперь это более эффективно, чем использование одной блокировки, конечно (которая определенно заставит все потоки ждать друг друга), но это меньшеэффективная память;кажется, что мьютексы также принимают некоторые данные.Мне также интересно узнать о других последствиях реализации pthreads с миллионами мьютексов?

Теперь у меня есть две другие стратегии для рассмотрения:

• Использовать менее плотный набор мьютексовзамки, для каждого "региона" на карте.Так, например, блокировка для [col / 16] [row / 16] блокирует поток, только если он посещает ту же область 16 пикселей, что и другая.Плотность замков можно динамически регулировать.Но когда я моделировал это, мне было интересно, не решаю ли я существующую проблему, которая может даже быть реализована ядрами, и я также не могу найти способ сделать это, не замедляя процесс.Я также подумал о «деревьях мьютексов», но все это слишком медленно внутри этого цикла (чтобы дать представление, после оптимизации порядка некоторых математических операций за спиной компилятора, я мог бы выжать на 30% больше процессорного времени),Есть ли тема для этого, как мне найти более подробную информацию о «планировании плотности мьютексов» ..?

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

Итак, есть ли что-нибудь еще, что-нибудь лучшее, что я мог бы сделать?

Answer 1

Вы можете использовать атомарные функции приращения, такие как InterlockedIncrement из intrin.h на платформах Windows.

#include <intrin.h>

#pragma intrinsic(_InterlockedExchangeAdd, _InterlockedIncrement, _InterlockedDecrement, _InterlockedCompareExchange, _InterlockedExchange)
#define InterlockedExchangeAdd _InterlockedExchangeAdd
#define InterlockedIncrement _InterlockedIncrement
#define InterlockedDecrement _InterlockedDecrement
#define InterlockedCompareExchange _InterlockedCompareExchange
#define InterlockedExchange _InterlockedExchange

#pragma intrinsic(abs, fabs, labs, memcmp, memcpy, memset, strcat, strcmp, strcpy, strlen)
#pragma intrinsic(acos, cosh, pow, tanh, asin, fmod, sinh)
#pragma intrinsic(atan, exp, log10, sqrt, atan2, log, sin, tan, cos) 

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

Answer 2

Ваш второй дизайн - лучший выбор именно по тем причинам, которые вы указали. Для рендеринга Буддхаброта вы хотите построить большую матрицу сумм. Вы можете избежать конфликта памяти, если вы позволите каждому процессору вычислять свой собственный массив, а затем добавлять свои результаты в мастер-массив каждую минуту или около того. Это единственная часть, которая требует блокировки памяти, и даже этого можно избежать, если каждый поток записывает в свой файл. У вас есть несколько процессоров, верно? Если нет, то добавление тем не принесет никакой пользы.

Answer 3

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

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

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

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

С уважением GJ