Введение к работе
Актуальность работы. В настоящее время существует большое количество асинхронных клеточно-автоматных (АКА) моделей микроуровневых физико-химических процессов таких, как диффузия, разделение фаз, эпи-таксиальный рост кристаллов, реакционно-диффузионные процессы, в том числе на поверхности катализатора. Например, в терминах асинхронного клеточного автомата представляется большое число моделей, в основе которых лежат кинетические методы Монте-Карло. При этом асинхронное клеточно-автоматное моделирование реальных процессов требует больших вычислительных мощностей, поскольку для выявления каких-либо свойств моделируемых процессов необходимо оперировать большими количествами частиц (10 -10 ) в течение длительного времени (10 -105 итераций). Естественным образом возникает потребность использовать параллельные вычислители для ускорения вычислений.
Однако, асинхронные клеточные автоматы не поддаются столь же легкому распараллеливанию, как синхронные клеточные автоматы (КА). Это связано с тем, что при распараллеливании необходимо соблюдать следующие условия: корректность и эффективность распараллеливания, а также равноправие в выборе клеток. Первые два условия типичны для большинства параллельных программ. Последнее условие возникает из определения асинхронного режима работы клеточного автомата и заключается в следующем: вероятность выбора некоторой клетки на некотором шаге должна быть равна вероятности выбора любой другой клетки на любом другом шаге. Подробнее проблемы параллельного исполнения асинхронных клеточно-автоматных моделей рассматриваются в Главе 2.
Существующие параллельные алгоритмы можно разделить на два класса: не нарушающие условия равноправия в выборе клеток [1,2] (сохраняющие асинхронизм), и нарушающие его [3,4] (нарушающие асинхронизм). Алгоритм L [2] разрабатывался и тестировался на компьютере с общей памятью в 1987 году, его эффективность на современных мультипроцессорах мала. В основе алгоритма S [1] лежит алгоритм параллельного моделирования дискретно-событийных систем. Из результатов работы [1] следует, что эффективность параллельного исполнения авторской реализации этого алгоритма слишком мала для асинхронных клеточно-автоматных моделей физико-химических процессов. В работах [3,4,5] на трёх моделях показано, что применение алгоритмов, нарушающих асинхронизм, не вносит существенных изменений в моделируемый процесс. Вопрос о том, для каких моделей использование алго-
ритмов, нарушающих асинхронизм, допустимо, то есть не вносит изменения в моделируемый процесс, остаётся открытым.
Следовательно, создание новых методов и алгоритмов параллельного исполнения асинхронных клеточных автоматов для современных вычислителей является своевременной и актуальной работой.
Целью настоящей работы является создание методов и алгоритмов параллельного моделирования микроуровневых физико-химических процессов, описываемых асинхронными вероятностными клеточными автоматами, для современных вычислителей с различной архитектурой (мультипроцессор, мультикомпьютер и графический ускоритель).
Для достижения поставленной цели следует решить следующие задачи:
Разработать формализм для описания АКА моделей микроуровневых физико-химических процессов.
Проанализировать существующие методы и алгоритмы параллельного исполнения АКА моделей физико-химических процессов.
Разработать и реализовать новые алгоритмы исполнения АКА моделей физико-химических процессов для мультипроцессоров, мультикомпью-теров и графических ускорителей.
Провести вычислительные эксперименты по определению эффективности реализаций существующих и разработанных параллельных алгоритмов на вычислителях с различной архитектурой.
Провести вычислительные эксперименты по определению статистического смещения моделируемого процесса для существующих и разработанных алгоритмов, нарушающих асинхронизм.
Разработать язык для описания АКА моделей физико-химических процессов и транслятор, переводящий это описание в программы для выше перечисленных вычислителей.
Достоверность полученных результатов. Все основные положения и выводы, сформулированные в диссертации, подтверждаются строгими математическими выводами и доказательствами, а также тестированием отдельных процедур программного комплекса на тестовых моделях, разработанных ранее другими авторами.
Основные положения, выносимые на защиту:
Формализм для описания АКА моделей микроуровневых физико-химических процессов.
Новый метод параллельного исполнения АКА моделей, основанный на
расширенных блочно-синхронных режимах работы КА и обеспечивающий меньшее статистическое смещение при моделировании.
Параллельные алгоритмы исполнения АКА моделей физико-химических процессов для вычислителей с различной параллельной архитектурой (мультипроцессоры, мультикомпьютеры и графические ускорители).
Язык описания АКА моделей микроуровневых физико-химических процессов и транслятор, переводящий описание АКА модели на этом языке в программу на языке C++/Processing.
Научная новизна заключается в том, что в работе впервые:
Предложен формализм для описания АКА моделей физико-химических процессов, основанный на алгоритме параллельных подстановок.
Предложен новый метод параллельного исполнения АКА моделей, основанный на расширенных блочно-синхронных режимах работы КА и обеспечивающий меньшее статистическое смещение при моделировании.
Обоснована необходимость использования сохраняющих асинхронизм параллельных алгоритмов исполнения АКА моделей физико-химических процессов в общем случае.
Разработаны и реализованы эффективные алгоритмы исполнения АКА моделей физико-химических процессов на следующих вычислителях с параллельной архитектурой: мультипроцессоры, мультикомпьютеры и графические ускорители.
Разработан язык описания и транслятор, позволяющие автоматизировать разработку АКА моделей физико-химических процессов.
Личный вклад автора. Все выносимые на защиту результаты получены автором лично.
Научная и практическая ценность. Предложенные методы и алгоритмы позволяют за приемлемое время моделировать микроуровневые физико-химические процессы, протекающие на поверхностях катализаторов, в масштабе необходимом исследователям для сравнения с реальными экспериментами. Созданные язык и транслятор позволяют автоматизировать процесс разработки подобных моделей.
Апробация. Результаты диссертационной работы были представлены на семи Российских и международных конференциях:
1. V Всероссийская конференция молодых ученых, Санкт-Петербург, 2008;
Международная научная студенческая конференция "Студент и научно-технический прогресс", Новосибирск, 2008;
Parallel computing technologies, РаСТ-2009, Novosibirsk;
Cellular Automata for Research and Industry, ACRI-2010, Italy, Ascoli Piceno, 2010;
XIX International Conference on Chemical Reactors "CHEMREACTOR-19", Austria, Vienna, 2010;
VIII International Conference Mechanisms of Catalytic Reactions, Novosibirsk, 2011;
Parallel computing technologies, PaCT-2011, Kazan, 2011;
Конференция молодых ученых по вычислительной математике и информатике, ИВМиМГ СО РАН, 2011.
Результаты докладывались на семинарах:
"Математическое и архитектурное обеспечение параллельных вычислений" под руководством д.т.н. В.Э. Малышкина;
"Архитектура, системное и прикладное программное обеспечение кластерных суперЭВМ" под руководством д.т.н. Б.М. Глинского;
"Методы Монте-Карло" под руководством чл.-корр. Г.А. Михайлова;
"Семинар ИДСТУ СО РАН по вычислительным технологиям" под руководством д.т.н. Г.А. Опарина (г. Иркутск).
Публикации. Основные результаты опубликованы в изданиях, рекомендованных ВАК (3 публикации), в трудах конференций (6 публикаций), и местных изданиях (2 публикации).
Структура и объем диссертации. Диссертация состоит из введения, трёх глав, заключения, библиографии и трёх приложений. Общий объём диссертации 82 страницы, включая 14 рисунков. Библиография включает 34 наименования.
