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

Question

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

Вот что я имею в виду:

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

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

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

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

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

ОБНОВЛЕНИЕ: Пока double buffering solution by Peter является самым чистым. Но у меня есть вопрос. Поскольку два массива являются общими данными, и мы не используем какую-либо синхронизацию (синхронизированный доступ или изменчивую переменную), не создаст ли она проблему видимости? Могут ли несколько ЦП кэшировать значения массива и обновлять только часть массива с каждой итерацией? Затем потоки получат устаревшие значения для пограничных ячеек. Это возможно? Если нет, то почему. Если да, то как мне его решить? Кажется declaring two arrays volatile will not make their individual elements volatile.

Answer 1

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

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

Answer 2

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

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

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

Answer 3

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

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

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

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

Недостатки:

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

Answer 4

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

Answer 5

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