Многопоточная Java-программа для игры жизни Конвея - раздоры в пограничных ячейках

Question

Я изучаю параллельное программирование на Java и пишу симулятор для Game of Life.

Вот что я думаю:

• Используйте int [] [] для хранения состояний ячеек
• разбить int [] [] на t сегментов и использовать t рабочих потоков
• Потоки t будут читать из своего сегмента, вычислять новые значения для всех ячеек в своем сегменте и обновлять ячейки.
• Как только они закончили расчет, они ждут у барьера, чтобы другие работники закончили
• при пересечении барьера основной поток обновит интерфейс.
• рабочие приступают к расчету следующего состояния.

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

Какие у меня варианты?

• Используйте callable вместо runnable и пусть рабочие потоки возвращают новое значение (вместо обновления самих сегментов). Основной поток может обновить матрицу после того, как барьер пройден. Эта опция включает в себя копирование результатов, возвращаемых рабочими потоками, в матрицу.
• Используйте два барьера. Рабочий поток делает копию пограничных ячеек из сегментов своих соседей и ждет у первого барьера. Как только этот барьер пройден, они продолжают вычислять следующие состояния и обновляют сегменты на месте. Затем они ждут у 2-го барьера. основной поток обновляет пользовательский интерфейс.

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

ОБНОВЛЕНИЕ: Пока что решение для двойной буферизации Питера является самым чистым. Но у меня есть вопрос. Поскольку эти два массива являются общими данными, и мы не используем синхронизацию (синхронизированный доступ или переменная переменная), не создаст ли это проблему видимости ? Могут ли несколько процессоров кэшировать значения массива и обновлять только часть массива с каждой итерацией? Тогда потоки получат устаревшие значения для граничных ячеек. Это возможно? Если нет, то почему. Если да, как мне это решить? Кажется, объявление двух массивов volatile не сделает их отдельные элементы volatile .

Answer 1

Я предлагаю иметь 2 массива int [] []. Назовем их A и B. A будет содержать значения всех нечетных «тиков», а B будет содержать четные тики.

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

Преимущества:

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

Недостатки:

• Вам нужно выделить вдвое больше памяти.

Answer 2

Я бы попробовал следующий подход:

• Пусть рабочие выполняют расчеты, но записывают только значения во внутренние ячейки.
• Для граничных ячеек сохраните результаты.
• Когда расчеты будут завершены, подождите у барьера.
• Когда все рабочие окажутся у первого барьера, отпустите затем и дайте каждому возможность написать ячейки границы.
• Ожидание второго барьера, пока обновляется пользовательский интерфейс

Требуется объем памяти для плитки n x m 2 * (n + m - 1), поэтому, как правило, для больших плиток (8x8 или более) требуется пропорционально меньше памяти для кэшированных значений.

Answer 3

Это не отвечает на ваш фактический вопрос, но моя рекомендация будет вашим первым вариантом ... возвращать новые значения вместо того, чтобы рабочие потоки обновляли их. Я бы сделал еще один шаг, и «агрегатор» объединил результаты рабочих потоков в новый массив состояний платы, а затем отбросил первый. Я полагаю, что это улучшит общую читабельность логики, поскольку вам не придется беспокоиться о «глобальных взаимодействиях».

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

Answer 4

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

Answer 5

Я только что наткнулся на java.util.concurrent.Exchanger<V>. Это действует как точка обмена. Я, вероятно, могу использовать его для обмена списками состояний ячеек между соседними потоками. Это было бы лучше, чем барьер, потому что мне нужно синхронизировать только между соседними работниками.