Как в вашей последовательной, так и в параллельной версии вы обновляете игровое поле по мере его прохождения. Это ошибка с обеими версиями. Допустим, вы вычислили новое состояние для gameField[0][0], а затем обновили его. Теперь вы переходите на gameField[0][1] --- как часть вычисления его нового состояния, вы смотрите налево на gameField[0][0], которое уже содержит недавно обновленное состояние этой ячейки, но правила Игры Жизни должны применяться к первой ячейке previous state.
Другими словами, вы должны иметь только для чтения (const) oldGameField и затем заполнять новые состояния в newGameField. После того как вы вычислили все ячейки, вы можете использовать новое поле в качестве старого поля для следующей итерации игры.
Исправление этой ошибки на самом деле является важной частью решения вашей проблемы с производительностью.
Многопоточность
Вместо того, чтобы думать, что 4 процессора делают эти обновления, представьте, что 4 человека делают это карандашом и бумагой. Поскольку теперь вы будете обрабатывать oldGameField только для чтения, можно безопасно скопировать старую страницу и дать копию каждому человеку. Каждый человек знает, что никто другой не собирается менять старую страницу, поэтому ему не нужно беспокоиться о том, что его копия станет устаревшей.
Но у вас все равно есть только одна страница для newGameField. В вашем последовательном подходе есть только один человек, который имеет страницу и карандаш исключительно для себя. Теперь у вас есть четыре человека, которые пытаются рисовать на одной странице одновременно. Они тратят больше времени на передачу карандаша и страницы между собой, чем на расчеты! Буквально на выполнение работы уходит четыре человека дольше, чем один мог бы выполнить ее в одиночку.
Это не означает точное представление о том, что происходит внутри аппаратного обеспечения, но когда мы рассматриваем любую блокировку и / или Возможно, используется OpenMP и такие вещи, как кеши памяти в ядрах вашего процессора - это довольно близко.
Итак, как нам это исправить?
Вы и ваши трое друзей могли бы решить, что каждый из вас обновит одну четверть поля. Может быть, вы берете всю верхнюю четверть доски. Следующий человек занимает вторую четверть и так далее. И вместо того, чтобы сражаться за один лист бумаги, чтобы нарисовать новое игровое поле, у каждого из вас есть свой собственный лист бумаги, чтобы нарисовать только четверть новых состояний.
Как только вы все закончите, вы быстро вставите свой четыре листка бумаги вместе, чтобы создать новую страницу игрового поля.
Суть в том, чтобы убедиться, что каждый поток читает из памяти, что никто не меняется, и что каждый поток записывает только в память, которая не другой поток получает доступ. Это означает, что ядра не блокируют друг друга с помощью записи в память, и им не нужно очищать свои кэши sh, когда они видят, что другие ядра записывают данные в общую память.
Убедитесь, что память нового игрового поля каждого потока не установлена. не достаточно близко, чтобы вызвать помехи в памяти, используемой другим потоком, сложно. Как правило, вам нужно знать некоторую информацию о размере строк кэша в ваших ядрах, независимо от того, использует ли ваша платформа что-то, называемое «NUMA», et c et c.
Я не знаю OpenMP - но, возможно, он имеет некоторую встроенную поддержку, чтобы помочь с этим.
В итоге
- Отделить старое состояние от нового состояния
- Ваши потоки могут все с удовольствием делятся старым состоянием (потому что никто не меняет его во время итерации)
- Разбейте работу на куски - по одному для каждого потока
- Дайте каждому потоку свой собственный фрагмент памяти для хранения его результаты.
- Как только все потоки закончатся, основной поток соберет все их результаты в одно новое игровое поле.