Параллельная реализация клеточно-автоматных алгоритмов моделирования пространственной динамики

Клеточный автомат (KA) является математической моделью пространственной динамики, которая используется, в основном, в тех случаях, когда моделируемое явление представлено нелинейными или разрывными функциями. Поскольку задачи КА-моделирования имеют большие размеры, для их решения необходимо иметь эффективные методы и алгоритмы распараллеливания. Укоренившееся мнение о том, что мелкозернистость КА-алгоритмов обеспечивает простое и эффективное крупноблочное распараллеливание не всегда верно. На самом деле проблема требует решения. В статье делается попытка обосновать общий подход к распараллеливанию КА-алгоритмов, основываясь на условиях поведенческой корректности КА-алгоритмов. Сначала дается формальная модель представления КА (алгоритм параллельных подстановок) и приводятся условия их корректности. Затем представлены методы распараллеливания и оценки их эффективности для синхронных и асинхронных КА. Для последних рассмотрен метод достижения высокой эффективности путем аппроксимации их блочно-синхронными КА. Все аналитические положения иллюстрируются результатами вычислительных экспериментов.