Многопоточная Программа Java для игры Conway жизни - конкуренция в краевых ячейках
Я изучаю параллельное программирование в Java и запись моделирования для Игры Жизни.
Вот то, что я думаю:
- Используйте интервал [] [] для хранения состояний ячеек
- разделите интервал [] [] в t сегменты и используйте t рабочие потоки
- Потоки t будут читать из своего сегмента, вычислять новые значения для всех ячеек в их сегменте и обновлять ячейки.
- После того как они закончили вычисление, которое они ожидают в барьере других рабочих для окончания
- когда барьер будет пересечен, основной поток обновит UI.
- рабочие продолжают вычислять следующее состояние.
Теперь там будет конкуренцией на общих границах сегментов. Если поток перезаписал состояние краевой ячейки, прежде чем ее сосед считал предыдущее значение, вычисление соседа будет неправильным.
Каковы мои опции?
- Используйте вызываемый вместо выполнимого и имейте рабочие потоки, возвращают новое значение (вместо того, чтобы обновить сами сегменты). Основной поток может обновить матрицу после того, как барьер будет пересечен. Эта опция включает копирование результатов, возвращенных рабочими потоками в матрицу.
- Используйте два барьера. Поток рабочих делает копию краевых ячеек от сегментов их соседей и ожидает в первом барьере. После того как этот барьер передается, они продолжают вычислять следующие состояния и обновлять сегменты на месте. Затем они ожидают в 2-м барьере. основной поток обновляет UI.
Мой вопрос, там какой-либо другой способ иметь дело с конкуренцией в краевых ячейках, которая не включает копирование данных или более эффективна что вышеупомянутые две опции? Может использовать ReaderWriterLock, энергозависимую переменную или другой механизм синхронизации?
ОБНОВЛЕНИЕ: До сих пор решением для двойной буферизации Peter является самое чистое. Но у меня есть вопрос. Так как два массива обменяны данными, и мы не используем синхронизации (синхронизировал доступ или энергозависимую переменную), разве это не создаст проблему видимости? Действительно ли несколько центральных процессоров могли кэшировать значения массива и обновить только часть массива с каждым повторением? Затем потоки получат устаревшие значения для краевых ячеек. Действительно ли это возможно? В противном случае, почему. Если да, как я решаю его? Это кажется объявлением, что два энергозависимые массива не сделают свои отдельные элементы энергозависимыми.
5 ответов
Это не отвечает на ваш вопрос, но моя рекомендация будет вашим первым вариантом ... возврат новых значений вместо обновления рабочих потоков их. Я бы пошел дальше и попросил «агрегатор» объединить результаты рабочих потоков в новый массив состояний платы, а затем отбросить первый. Я считаю, что это улучшит общую читаемость логики, поскольку практически не будет «глобальных взаимодействий», о которых вам нужно беспокоиться.
При этом я немного предвзят, потому что предпочитаю программировать функционально, за исключением случаев, когда есть веская причина не делать этого.
Я предлагаю иметь 2 массива int [] []. Назовем их A и B. A будет содержать значения всех «тиков» с нечетными номерами, а B будет содержать тики с четными номерами.
Инициализируйте A в соответствии с вашим начальным состоянием. Затем позвольте вашим потокам расслабиться, чтобы вычислить следующее состояние каждой ячейки, и поместите результаты в соответствующую ячейку в B. Как только все ваши потоки будут выполнены, вы получите новое состояние в B. Теперь используйте B для вычислить следующее состояние каждой ячейки и сохранить результаты в A. В любой момент времени один массив будет доступен только для чтения, а другой - только для записи, поэтому конфликтов не будет.
Преимущества:
- Отсутствие копирования данных по сравнению с тем, что вы делаете сейчас. На каждую ячейку выполняется только одна запись.
- Не нужно беспокоиться о краях / углах, так как алгоритм прост.
- Нет постоянного выделения памяти. Просто выделите два массива при запуске.
Недостатки:
- Вам нужно выделить вдвое больше памяти.
Я бы попробовал следующий подход:
- Пусть рабочие выполняют вычисления, но только записывают значения во внутренние ячейки.
- Для пограничных ячеек сохраните результаты.
- Когда вычисления будут завершены, подождите у барьера.
- Когда все рабочие окажутся у первого барьера, отпустите их и позвольте каждому записать пограничные ячейки.
- Подождите у второго барьера, пока пользовательский интерфейс обновится.
Объем памяти, необходимый для плитки nxm , составляет 2 * (n + m - 1) , поэтому обычно плитки большего размера (8x8) или больше) требуют пропорционально меньше памяти для кэшированных значений.
Я только что наткнулся на java.util.concurrent.Exchanger . Он действует как точка обмена. Я, вероятно, смогу использовать его для обмена списками состояний ячеек между соседними потоками. Это было бы лучше, чем барьер, потому что мне нужно синхронизировать только между соседними рабочими.
Чтобы ответить на ваше обновление о проблеме кеширования с двойной буферизацией, это не проблема. У ЦП есть согласованный кеш, и они знают, когда данные были изменены в другом кэше ЦП.