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

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

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, не имеет значения, в каком порядке мы обрабатываем записи массива, хотя технически существует состояние гонки, если мы делаем это параллельно (поскольку мы одновременно читаем/записываем один и тот же объект) . Как я могу сказать компилятору, что он не должен заботиться о состоянии гонки, не жертвуя при этом производительностью?