Как я могу сделать код, который одновременно читает и изменяет массив, четко определенный, без введения блокировки?

Question

Я пишу программу, которая вычисляет базу данных эндшпиля для шахматного варианта. Алгоритм заполнения табличной базы работает так:

1. Начните с огромного массива unsigned charкаждый участник представляет одну позицию (мы всегда предполагаем, что настала очередь белых). Член массива четный, если позиция потеряна, нечетная, если она выиграна, 0xff если это недействительно, 0xfe если это ничья.
2. Итерируйте по массиву, отмечая каждую недопустимую позицию 0xff, каждая позиция, где белый сочетается с 0x00 и все остальные позиции с 0x0fe,
3. Итерация по массиву с учетом только отмеченных позиций 0xfe, Проверьте, есть ли движение, которое приводит к позиции, чей элемент массива является четным, если он есть, запишите единицу плюс номер этой позиции в элемент, соответствующий текущей позиции. Если все ходы приводят к позициям, обозначенным нечетными числами (т. Е. Это проигрышная позиция), отметьте эту позицию как единицу плюс наибольшее из этих чисел, чтобы указать, сколько времени занимает самая сильная защита.
4. Повторяйте шаг три, пока массив больше не изменится.

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

• Разбейте массив на n частей, чтобы один поток работал с каждой частью. Пусть текущая итерация будет i.
• Если поток должен прочитать элемент из массива и он равен i, обработайте его так, как если бы он был установлен в 0xfe потому что это означает, что член был просто записан одновременно другим потоком.

Теперь очевидно, что в этой программе есть условие гонки, но это не имеет значения, поскольку мы всегда получаем правильный результат, если нет никаких розовых слонов (которые не могут существовать, если char написано атомарно). Однако, поскольку на бумаге есть условие гонки, компилятор C может объявить мою программу неопределенной и отформатировать мой жесткий диск.

Что я могу сделать, чтобы распараллелить этот алгоритм, не нарушая каких-либо ограничений модели памяти C и не вызывая значительного замедления (например, путем добавления блокировок)?

Упрощенное описание проблемы

Вот упрощенный алгоритм, который демонстрирует ту же концепцию, но лишен всего несущественного:

1. Начните с массива unsigned char a[n], Каждый элемент массива имеет значение 0 или 1.
2. Для каждого элемента массива, для которого установлено значение 0: если некоторые другие элементы массива равны 0 или 2, задайте для этого элемента массива значение 2. Проверенные элементы массива зависят от индекса элемента массива, который мы хотим обновить. Простых отношений между индексом и членами массива, которые мы должны проверять, не существует, по сути, это случайный характер

Поскольку мы когда-либо меняем только 0 на 2, не имеет значения, в каком порядке мы обрабатываем записи массива, хотя технически существует условие гонки, если мы делаем это параллельно (так как мы одновременно читаем / пишем один и тот же объект), Как я могу сказать компилятору, что он не должен заботиться о состоянии гонки, не жертвуя при этом производительностью?

Answer 1

Это то, что _Atomic квалификатор типа для C11. Вы бы объявили свой массив как

_Atomic unsigned char a[n];

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

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

---

Обратите внимание, что порядок памяти по умолчанию для C11 _Atomic доступ это memory_order_seq_cst (последовательная последовательность), и если вам это не нужно, вы можете использовать atomic_load_explicit а также atomic_store_explicit действия с более слабым упорядочением памяти (т.е. memory_order_relaxed в твоем примере)