автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Клеточно-автоматное моделирование физико-химических процессов на вычислителях с параллельной архитектурой

На правах рукописи

00504^'"

КАЛГИН Константин Викторович

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

Специальность 05.13.18 - математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

2 4 М.4 5 2012

Новосибирск - 2012

005044974

Работа выполнена в Федеральном государственном бюджетном учреждении науки Институте вычислительной математики н математической геофизики Сибирских) отделения Российской академии наук (ИВМнМГ СО РАН).

Научный руководитель: доктор технических наук,

профессор

Бандман Ольга Леонидовна

Официальные оппоненты: доктор физико-математических наук,

профессор

Войтпшек Антон Вацлавович (Федеральное государственное бюджетное .учреждение науки Институт вычислительной математики и математической геофизики Сибирского отделения Российской академии наук);

кандидат физико-математических наук, доцент

Шилов Николай Вячеславович (Федеральное государственное бюджетное учреждение науки Институт систем информатики имени А.П. Ершова Сибирского отделения Российской академии наук);

Ведущая организация: Федеральное государственное бюджетное учре-

ждение науки Институт динамики систем и теории управления Сибирского отделения Российской академии наук, Иркутск

Защита состоится 19 нюня 2012 г. в 15.00 на заседании диссертационного совета Д 003.061.02 на базе Федерального государствепиого бюджетного учреждения науки Института вычислительной математики и математической геофизики Сибирского отделения Российской академии наук по адресу: 630090, г. Новосибирск, пр. академика Лаврентьева, 6, тел. (383)330-71-59.

С диссертацией можно ознакомиться в библиотеке Федерального государственного бюджетного учреждения науки Института вычислительной математики и математической геофизики Сибирского отделения Российской академии наук.

Автореферат разослан 4 мая 2012 г.

Ученый секретарь

диссертационного совета Д 003.061.02 на базе ИВМиМГ СО РАН, д.ф.-м.н.

С.Б. Сорокин

Общая характеристика работы

Актуальность работы. В настоящее время существует большое количество асинхронных клеточно-автоматных (АКА) моделей микроуровневых физико-химических процессов таких, как диффузия, разделение фаз, эпи-таксиальный рост кристаллов, реакционно-диффузионные процессы, в том числе на, поверхности катализатора. Например, в терминах асинхронного клеточного автомата представляется большое число моделей, в основе которых лежат кинетические методы Монте-Карло. При этом асинхронное клеточно-автоматное моделирование реальных процессов требует больших вычислительных мощностей, поскольку для выявления каких-либо свойств моделируемых процессов необходимо оперировать большими количествами частиц (1010-Ю12) в течение длительного времени (103-105 итераций). Естественным образом возникает потребность использовать параллельные вычислители для ускорения вычислений.

Однако, асинхронные клеточные автоматы не поддаются столь же легкому распараллеливанию, как синхронные клеточные автоматы (КА). Это связано с тем, что при распараллеливании необходимо соблюдать следующие условия: корректность и эффективность распараллеливания, а также равноправие в выборе клеток. Первые два. условия типичны для большинства параллельных программ. Последнее условие возникает из определения асинхронного режима работы клеточного автомата и заключается в следующем: вероятность выбора некоторой клетки на некотором шаге должна быть равна вероятности выбора любой другой клетки на любом другом шаге. Подробнее проблемы параллельного исполнения асинхронных клеточно-автоматных моделей рассматриваются в Главе 2.

Существующие параллельные алгоритмы можно разделить на два класса: не нарушающие условия равноправия в выборе клеток [1,2] (сохраняющие асинхронпзм), и нарушающие его [3,4] (нарушающие асинхронизм). Алгоритм Ь [2] разрабатывался и тестировался на компьютере с общей памятью в 1987 году, его эффективность на современных мультипроцессорах мала. В основе алгоритма Б [1] лежит алгоритм параллельного моделирования дискретно-событийных систем. Из результатов работы [1] следует, что эффективность параллельного исполнения авторской реализации этого алгоритма слишком мала для асинхронных клеточно-автоматных моделей физико-химических процессов. В работах [3,4,5] на трёх моделях показано, что применение алгоритмов, нарушающих асинхронизм, не вносит существенных изменений в моделируемый процесс. Вопрос о том, для каких моделей использование алго-

ритмов, нарушающих асинхронизм, допустимо, то есть не вносит изменения в моделируемый процесс, остаётся открытым.

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

Целью настоящей работы является создание методов и алгоритмов параллельного моделирования микроуровневых физико-химических процессов, описываемых асинхронными вероятностными клеточными автоматами, для современных вычислителей с различной архитектурой (мультипроцессор, мультикомпьютер и графический ускоритель).

Для достижения поставленной цели следует решить следующие задачи:

1. Разработать формализм для описания АКА моделей микроуровневых физико-химических процессов.

2. Проанализировать существующие методы и алгоритмы параллельного исполнения АКА моделей физико-химических процессов.

3. Разработать и реализовать новые алгоритмы исполнения АКА моделей физико-химических процессов для мультипроцессоров, мультикомпью-теров и графических ускорителей.

4. Провести вычислительные эксперименты по определению эффективности реализаций существующих и разработанных параллельных алгоритмов на вычислителях с различной архитектурой.

5. Провести вычислительные эксперименты по определению статистического смещения моделируемого процесса для существующих и разработанных алгоритмов, нарушающих асинхронизм.

6. Разработать язык для описания АКА моделей физико-химических процессов и транслятор, переводящий это описание в программы для выше перечисленных вычислителей.

Достоверность полученных результатов. Все основные положения и выводы, сформулированные в диссертации, подтверждаются строгими математическими выводами и доказательствами, а также тестированием отдельных процедур программного комплекса на тестовых моделях, разработанных ранее другими авторами.

Основные положения, выносимые на защиту:

1. Формализм для описания АКА моделей микроуровневых физико-химических процессов.

2. Новый метод параллельного исполнения АКА моделей, основанный на

расширенных блочно-синхронных режимах работы КА и обеспечивающий меньшее статистическое смещение при моделировании.

3. Параллельные алгоритмы исполнения АКА моделей фпзико-химиче-ских процессов для вычислителей с различной параллельной архитектурой (мультипроцессоры, мультикомньютеры и графические ускорители).

4. Язык описания АКА моделей микроуровневых физико-химических процессов и транслятор, переводящий описание АКА модели па этом языке в программу на языке C++/Proccssing.

Научная новизна заключается в том. что в работе впервые:

1. Предложен формализм для описания АКА моделей физико-химических процессов, основанный на алгоритме параллельных подстановок.

2. Предложен новый .метод параллельного исполнения АКА моделей, основанный на расширенных блочно-синхронных режимах работы КА и обеспечивающий меньшее статистическое смещение при моделировании.

3. Обоснована необходимость использования сохраняющих асинхронизм параллельных алгоритмов исполнения АКА моделей физико-химических процессов в общем случае.

4. Разработаны и реализованы эффективные алгоритмы исполнения АКА моделей физико-химических процессов на следующих вычислителях с параллельной архитектурой: мультипроцессоры, мультикомпьютеры и графические ускорители.

5. Разработан язык описания и транслятор, позволяющие автоматизировать разработку АКА моделей физико-химических процессов.

Личный вклад автора. Все выносимые на защиту результаты получены автором лично.

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

Апробация. Результаты диссертационной работы были представлены на семи Российских и международных конференциях:

1. V Всероссийская конференция молодых ученых, Санкт-Петербург, 2008;

2. Международная научная студенческая конференция ''Студент и научно-технический прогресс", Новосибирск, 2008;

3. Parallel computing technologies. РаСТ-2009, Novosibirsk;

4. Cellular Automata for Research and Industry, ACRI-2010, Italy, Ascoli Piceno, 2010;

5. XIX International Conference on Chemical Reactors "CHEMREACTOR-19", Austria, Vienna, 2010;

6. VIII International Conference Mechanisms of Catalytic Reactions. Novosibirsk, 2011;

7. Parallel computing technologies, PaCT-2011, Kazan, 2011;

8. Конференция молодых ученых по вычислительной математике и информатике, ИВМиМГ СО РАН, 2011.

Результаты докладывались на семинарах:

1. "Математическое и архитектурное обеспечение параллельных вычислений" под руководством д.т.н. В.Э. Малышкина;

2. "Архитектура, системное и прикладное программное обеспечение кластерных суперЭВМ" под руководством д.т.н. Б.М. Глинского;

3. "Методы Монте-Карло" под руководством чл.-корр. Г.А. Михайлова;

4. "Семинар ИДСТУ СО РАН по вычислительным технологиям" под руководством д.т.н. Г.А. Опарина (г. Иркутск).

Публикации. Основные результаты опубликованы в изданиях, рекомендованных ВАК (3 публикации), в трудах конференций (G публикаций), и местных изданиях (2 публикации).

Структура и объем диссертации. Диссертация состоит из введения, трёх глав, заключения, библиографии и трёх приложений. Общий объём диссертации 82 страницы, включая 14 рисунков. Библиография включает 34 наименования.

Основное содержание работы

В первой главе предлагается формализм для описания АКА моделей физико-химических процессов, основанный на алгоритме параллельных подстановок, а также новые блочно-синхроиные режимы работы КА, обеспечивающие меньшее статистическое смещение при моделировании.

Выделяемый в данной работе класс моделей - модели микроуровневых физико-химических процессов, представляемых в виде АКА, в которых для

записи локального оператора перехода используется адаптированный формализм алгоритма параллельных подстановок. Выделение именно такого класса моделей обусловлено следующими факторами: большая часть моделей мик-роуровневых физико-химических процессов, в основе которых лежат кинетические методы Монте-Карло, обладает структурой АКА; в форме элементарных подстановок удобно записывать элементарные действия в моделях физико-химических процессов, которые ранее записывались частично неформальным, словесным, образом, а частично в виде списка химических формул; с помощью предлагаемых в работе правил композиции удобно записывать порядок применения имеющихся элементарных подстановок, который ранее описывался неформальным, словесным, образом.

В разделе 1.1 приводится общепринятое определение АКА модели, которая описывается четвёркой

АКА = {X, А, ©, Т),

где X - множество координат клеток, А - множество возможных состояний клеток, В - локальный оператор перехода (далее оператор), а Т - режим работы. Клеткой называется пара с = (х, а), где х € X - координата клетки, а € А - состояние клетки.

В разделе 1.2 предлагается определение оператора © как вероятностного отображения вида

В : ,1х ' А АМ, (1)

где базовый В и контекстный С шаблоны суть списки именующих функций, ф : X ->■ X, В = С Эти шаблоны

определяют базовые и контекстные соседства клетки х следующим образом:

£(х) = {0?(х),...,^|(х)}, С7(х) = ... ,^,(х)}.

Применением оператора © к клетке х называется обновление состояний клеток из базового соседства 5(х) состояниями 8(Я(х)), где Я(х) есть список состояний клеток из объединённого соседства В(х) и С(х).

Оператор © представляется в форме композиционной подстановки, которая состоит из элементарных подстановок.

Элементарная подстановка - это вероятностное отображение вида (1) со своими базовым и контекстным шаблонами, которая записывается в следующем виде:

Вть : {я.1,.... ят', ят'+1,..., ат} {о^, а2,..., а'т,}, (2)

сстЛ

где т! = |Дэ,и6|, т — т' — |Се,„ь|, Щ £ А, р - вероятность изменения, р = p(«i,...am), a cond - условие изменения базовых клеток, cond = cond(ai,..., ат). В результате применения элементарной подстановки esub к клеткам х1; х2,..., x¡ состояния базовых клеток Bc->rl¡b(хх, х2,..., х/) становятся равными а[,..., а'т, с вероятностю р и только при выполнении условия cond.

Композиционная подстановка - это вероятностное отображение вида (1) со своими базовым и контекстным шаблонами. Композиционная подстановка записывается в виде композиции других композиционных или элементарных подстановок. Наиболее часто используются следующие правила композиции: случайный выбор (R), последовательное исполнение (S), последовательное исполнение в случайном порядке (RS) и последовательное исполнение до первой действительно применившейся элементарной подстановки (F).

В разделе 1.3 приводятся определения как классических, так и предлагаемых режимов работы Т клеточного автомата, Т е {a, Процесс моделирования разбивается на итерации. Режим работы Т определяет порядок применения оператора В в рамках одной итерации. В синхронном режиме (сг) оператор © за одну итерацию применяется ко всем клеткам клеточного массива. В асинхронном режиме (а) итерация разбивается на |Х| шагов, на каждом шаге оператор © применяется к случайно выбранной клетке. Асинхронный режим является типичным для большинства К А моделей физико-химических процессов.

Блочно-синхронный режим (3) был введён в работах [3,4] для получения параллельных реализаций. В блочно-синхронном режиме итерация состоит из и стадий, на каждой стадии случайно и равновероятно выбирается подмножество Si С X из семейства S = {¿ц, S-¿,..., 5,,}, причем Ук = \X\/ui, после чего ко всем клеткам х 6 Si применяется оператор ©. Для обеспечения свойства корректности синхронного применения, равноправности выбора клеток и эффективного параллельного исполнения на семейство S накладываются дополнительные условия [3]. В разделе 1.4 предлагается использовать другие условия, которые не нарушают перечисленных свойств, но увеличивают размер семейства S, иногда на порядки, тем самым приближаясь к асинхронному режиму. Такой режим будем называть расширенным блочно-синхронным режимом (7).

В разделе 1.5 подробно рассматривается запись модели реакции СО + О = СО2 на поверхности палладия в предложенном выше формализме. Модель описывается 15-ю элементарными подстановками и 5-ю правилами ком-

позиции.

В разделе 1.6 сравниваются эволюции клеточных автоматов с различными режимами (а, ß, 7) на примере простой модели реакции СО + О = С02 на поверхности катализатора (ZGB, Ziff-Gulari-Barshad). Обычно для анализа эволюции клеточного автомата используется характеристика fa¡t - количество клеток с состоянием а в клеточном массиве после исполнения t итераций. В работе показывается, что используя эту характеристику мы не можем статистически отличить друг от друга большую часть эволюций клеточных автоматов при различных режимах. Для сравнения эволюций предлагается использовать новую болте информативную характеристику /Дх,4 - количество пар клеток в клеточном массиве после исполнения t итераций с координатами х и х + Ах и с. одинаковыми состояниями. С помощью вычислительных экспериментов показывается существенное преимущество, с точки зрения величины статистического смещения относительно асинхронного режима, предложенных расширенных блочно-синхронных режимов перед ранее существовавшими блочно-синхронными. С помощью вычислительных экспериментов также показывается, что введение диффузии в модель приводит к тому, что эволюции клеточного автомата при различных режимах становятся статистически неотличимыми друг от друга.

Во второй главе анализируются существующие и предлагаются новые алгоритмы параллельного исполнения АКА моделей физико-химических процессов, а также приводятся результаты тестирования рассматриваемых алгоритмов на современных вычислителях с параллельной архитектурой.

При распараллеливании на р процессов (потоков) клеточная область X делится между ними на непересекающиеся домены Dornь Dom2, ..., Domp. Клетках € Dorrik называется граничной, если существует домен к' такой, что (С(х) U В(х))пОопц.. ф 0, где С и В являются контекстным и базовым шаблонами оператора 9 соответственно. Каждый процесс (поток) р вычисляет функцию, реализующую применение оператора©, только для клеток своего домена Domp. Для синхронизации между процессами (потоками) вводится понятие локального времени процесса (потока).

Основная сложность построения эффективных параллельных алгоритмов функционирования АКА для систем с общей памятью состоит в следующем: во время применения оператора 6 к граничной клетке х одним потоком необходимо исключить использование клеток изС(х) U Bíx) другими потоками, иначе может возникнуть ситуация гонки (racing, race condition); необходимо сохранять равноправие всех клеток, то есть вероятность примсне-

ния 9 к некоторой клетке на некотором шаге должна быть равна вероятности применения 9 к любой другой клетке на любом другом шаге.

Основная сложность построения эффективных параллельных алгоритмов функционирования АКА для систем с распределённой памятью состоит в следующем: после изменения состояния любой граничной клетки необходимо мгновенно обновить это состояние в соседнем домене; количество передач новых состояний на одной итерации имеет порядок л/Щогщ] и они равномерно по ней разнесены; передача сообщений по сети занимает большое время (на два-три порядка больше, чем время вычисления функции, реализующей локальный оператор перехода); необходимо сохранять равноправие всех клеток, то есть вероятность применения 9 к некоторой клетке на некотором шаге должна быть равна вероятности применения 9 к любой другой клетке на любом другом шаге.

Таким образом, трудности при параллельном исполнении АКА возникают в момент применения оператора 9 к граничной клетке. В этот момент у процесса (потока) есть три варианта поведения:

1. процесс (поток) ждёт и ничего не делает пока локальное время всех соседних процессов (потоков) меньше его локального времени;

2. процесс (поток) не ждёт никакой другой процесс (поток) и применяет оператор 9 сразу же;

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

На этих трёх вариантах поведения основаны три алгоритма параллельного исполнения: Э [1]. Ь [2] и собственный алгоритм К соответственно. Эти алгоритмы сохраняют асинхронизм (независимость выбора клеток). Кроме того существуют алгоритмы [3,4] нарушающие асинхронизм. Они основаны на определении блочно-синхронного режима работы клеточного автомата.

В разделе 2.1 приводятся и анализируются существующие алгоритмы параллельного исполнения АКА моделей физико-химических процессов: Ь [2], Б [1] и В [3,4].

Недостатком алгоритма Ь является его избыточная синхронизация при применении оператора 9 к граничной клетке: поток, применяющий оператор к граничной клетке, ждёт пока его локальное время станет меньше локального времени потока с граничащим доменом для того, чтобы быть уверенным, что не произойдёт какого-либо информационно зависимого граничного шага.

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

Алгоритм S, напротив, является оптимистичным.: процесс (поток), применяющий оператор к граничной клетке, "надеется", что в ближайшем будущем не произойдёт какого-либо информационно зависимого граничного шага. Если же такой шаг происходит, то соответствующий процесс (поток) извещает об этом соседние процессы (потоки). Если же во время исполнения процессу (потоку) приходит сообщение с информацией о том, что в его "прошлом" был исполнен граничный шаг, то процесс (поток) обязан "откатить" все изменённые за это время состояния клеток. Для этого процесс (ноток) должен сохранять все изменения клеток во время работы. Это приводит к тому, что этот алгоритм не является эффективным на большинстве клсточно-автомат-ных моделей микроуровневых физико-химических процессов, поскольку для таких моделей время применения оператора 9 соразмерно с временем сохранения изменённых состояний.

Алгоритм В очень прост, поскольку в основе cm лежит блочно-синхрон-ный режим работы клеточного автомата. Благодаря синхронным стадиям данный алгоритм возможно эффективно реализовать на графическом ускорителе.

В разделе 2.2 предлагается новый сохраняющий асинхронизм алгоритм параллельного исполнения АКА моделей физико-химических процессов. Основная идея алгоритма состоит в следующем. Каждый процесс (поток) создаёт план своих будущих применений оператора В к клеткам в соответствии с вероятностными свойствами асинхронного режима. Имея план будущих применений оператора соседними процессами (потоками), во время исполнения граничного шага процесс (поток) может определить, будет ли в ближайшем будущем у какого-либо процесса (потока) информационно зависимый шаг. Из чего станет ясно - необходимо ждать или можно без опаски применять оператор к граничной клетке. Засчет планирования будущего сокращается количество ненужных ожиданий, и отпадает необходимость сохранять изменения состояний клеток.

В разделе 2.3 приводятся основные данные по архитектуре используемых для тестирования вычислителей: мультипроцессор Intel Xeon Х7560 с 32 ядрами (4 процессора с 8 ядрами каждый); кластер MBC-lOOk, в каждом

узле по 8 ядер (два процессора Intel Xeon с 4 ядрами каждый); графический ускоритель Nvidia GTX 280 с 240 ядрами.

В разделе 2.4 приводятся результаты тестирования реализаций алгоритмов L, К и В. Для тестирования использовалась модель, онисанпая в разделе 1.5. Был проведен ряд вычислительных экспериментов, получены следующие результаты:

1. алгоритм К примерно в два раза быстрее алгоритма L на современном мультипроцессоре;

2. алгоритм В примерно в два раза быстрее алгоритма К на современном мультипроцессоре:

3. алгоритм К имеет достаточно хорошую производительность даже при использовании нескольких узлов кластера MVS-100k;

4. алгоритм В примерно в десять раз быстрее алгоритма К на кластере MVS-100k;

5. один рядовой графический ускоритель на тестируемой модели заменяет современный мощный мультипроцессор с 32 ядрами.

В третьей главе описываются разработанный язык описания АКА моделей микроуровневых физико-химических процессов и транслятор, переводящий описание модели в язык C++/Processing.

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

Для автоматизации процесса разработки АКА моделей физико-химических процессов были созданы предметно-ориентированный язык CACHE (Cellular Automata for physico-CHEinical models) и транслятор.

Транслятор на основе описания АКА модели на языке CACHE генерирует текст программы на языке С++ или Processing. В зависимости от нужд пользователя генерируется одна из нижеперечисленных программ;

1. последовательная программа на языке С++;

2. последовательная программа на языке Processing с возможностью визуализации и генерации видеофайлов;

3. параллельная программа для мультипроцессоров на языке С++ с использованием библиотеки управления потоками POSIX Threads;

4. параллельная программа для мультикомпыотеров на языке С++ с использованием библиотеки межпроцессных коммуникаций MPI;

5. параллельная программа для графических ускорителей, поддерживающих технологию CUDA.

Проведённое тестирование на АКА модели из раздела 1.5 показало, что скорость работы сгенерированной программы на 10-20% меньше скорости вручную написанной и оптимизированной программы, что является вполне приемлемой платой за автоматизацию процесса разработки.

В Заключении диссертационной работы сформулированы основные результаты работы, которые заключаются в следующем:

1. Предложен формализм для описания АКА моделей физико-химических процессов, основанный на теории параллельных подстановок.

2. Проанализированы существующие методы и алгоритмы параллельного исполнения АКА моделей физико-химических процессов. Обоснована необходимость создания новых методов и алгоритмов.

3. Предложен новый метод параллельного исполнения АКА моделей, основанный на расширенных блочно-синхронных режимах работы КА, обеспечивающих меньшею статистическое смещение при моделировании.

4. Обоснована, необходимость использования сохраняющих асинхронизм параллельных алгоритмов исполнения АКА моделей физико-химических процессов в общем случае.

5. Разработаны н реализованы эффективные алгоритмы исполнения АКА моделей физико-химических процессов на следующих вычислителях с параллельной архитектурой: мультипроцессоры, мультикомпьютеры и графические ускорители.

6. Разработаны язык описания АКА моделей физико-химических процессов и транслятор, переводящий это описание в программы для различных вычислителей с параллельной архитектурой.

В Приложении А приводится полная контекстно-свободная грамматика предметно ориентированного языка CACHE. В Приложении Б приводится полное описание АКА модели из раздела 1.5 на языке CACHE. В Приложении В приводится список публикаций автора.

Список литературы

1. Overeindcr B. J., Sloot P. M. A. Extensions to Time Warp Parallel Simulation for Spatial Decomposed Applications // Proceedings of the Fourth United Kingdom Simulation Society Conference (UKSim 99) /' Ed. by D. Al-Dabass, R. Cheng. Cambridge, UK: 1999. P. 67-73.

2. Lubachevsky B. Efficient parallel simulation of asynchronous cellular arrays // Complex Systems. 1987. Vol. 1. P. 1099-1123.

3. Bandman 0. Parallel Simulation of Asynchronous Cellular Automata Evolution // Proceedings of 7th International Conference on Cellular Automata, for Research and Industry, ACRI 200G / Ed. by S. Yacoubi, B. Chopard, S. Bandini. Vol. 4173 of LNCS. Springer, 200G. P. 41-47.

4. Nedea S., Lukkien J., Hilbers P., Jansen A. Methods for Parallel Simulations of Surface Reactions // Proceedings of the 17th International Symposium on Parallel and Distributed Processing / Ed. by B. Werner. IEEE Computer Society, 2003. P. 25G.

5. Sharifulina A., Elokhin V. Simulation of Heterogeneous Catalytic Reaction by Asynchronous Cellular Automata on Multicomputer // Proceedings of Parallel Computing Technologies, 6th International Conference, PaCT-2011 / Ed. by V. Malyshkin. LNCS. Springer, 2011. P. 204-209.

Публикации автора по теме диссертации

Статьи в рецензируемых журналах из перечня ВАК:

1. К. В. Калгин. Пар&члельная реализация асинхронных клеточных автоматов па 32-ядсрпой вычислительной системе. // Сиб. жури, вычисл. матем., 15:1 (2012), С. 55-05

2. К. В. Калгин. Реализация алгоритмов с мелкозернистым параллелизмом на графических ускорителях. /7 Сиб. журн. вычисл. матем., 14:1 (2011), С. 59-70

3. К.В. Калгин. Параллельная реализация асинхронных клеточно-авто-матных алгоритмов // Науч.-тех. вестник СПбГУ инф.тех., мех. и опт. 54, 2008, С.108-113

Другие статьи, тезисы и труды конференций:

4. K.V. Kalgin. Domain Specific Language and Translator for Cellular Automata Models of Physico-Chemical Processes // Proc. of PaCT-2011, P.1G6-174

5. K.V. Kalgin. Comparative Study of Parallel Algorithms for Asynchronous Cellular Automata Simulation on Different Computer Architectures //' Proc. of ACRI-2010, LNCS 6350, Springer, 2010, P. 399-408.

6. E.V. Kovalev, A.V. Matveev, K.V. Kalgin, V.I. Elokhin, V.V. Gorodetsky. Stoch. Model of CO Oxidation Reaction over Pd Supported Nanoparticles: Boudart Reverse Spillover. // Proc. VIII International Conference "Mechanisms of Catalytic Reactions "dedicated to the 70th anniversary of Professor Kirill I. Zamaracv, June 28-July 2, Novosibirsk, Russia. 2009. Vol. 1, P. 127.

7. K.V. Kalgin. Implementation of Fine-Grained Algorithms on Graphical Processing Unit .// Proc. of PaCT-2009, LNCS 5698, Springer, 2009, P.207-215.

8. K.V. Kalgin. Parallel simulation of asynchronous Cellular Automata evolution. // Bull. Nov. Сотр. Center, Сотр. Science 27, 2008, P.55-62.

9. K.V. Kalgin. Acceleration of linear congruential generators. // Bull. Nov. Сотр. Center, Сотр. Science 27, 2008, P.51-53.

10. V.I. Elokhin, K.V. Kalgin, E.V. Kovalyov, A.V. Matveev, V.V. Gorodetsky, Specificity of the Oscillations Performance over the Flexible Surfaces of the Metal Nanoparticles /'/ Proc. XIX International Conference on Chemical Reactors "CHEMREACTOR-19 September 5-9, Vienna, Austria. P. 45-46.

11. Калпга K.B. Эффективная параллельная реализация асинхронных клеточно-автоматных алгоритмов // Труды XLVI Международной научно студенческой конференции, 2008, С. 251.

Подписано в печагь 02.05.2012г. Формат 60x84 1\16 Усл. печ. л. 1 Объем 16 стр. Тираж 100 экз. Заказ № 64

Отпечатано ООО «Омега Принт» 630090, г. Новосибирск, пр. Ак.Лаврентьева,6

Введение

Глава 1. Формальное представление асинхронных вероятностных клеточно-автоматных моделей физико-химических процессов

1.1. Формальное представление клеточного автомата

1.2. Локальный оператор перехода.

1.3. Эволюция клеточного автомата.

1.4. Семейства подмножеств S для KÄß и КА

1.5. АКА модель реакции СО + О = СО2 на поверхности палладия

1.6. Сравнение поведений КАа, КА^ и КА7.

Клеточный автомат (КА) был предложен фон-Нейманом в середине прошлого века [1]. На основе этой модели подтверждалась мысль о том, что человек может создать устройство, обладающее присущими ему самому свойствами, в частности, возможностью воспроизводить себе подобного. Основные свойства клеточного автомата формулируются в следующем виде [2]: дискретность пространства, времени и состояний; однородность (все клетки организованы в регулярную пространственную структуру); синхронный режим изменения состояний; пространственная локальность; временная локальность.

Первое время клеточный автомат оставался объектом для игры ума. Сначала эта игра происходила на бумаге, затем она была перенесена на компьютер. Самым известным клеточным автоматом была и остается "Игра Жизнь" [3]. Интерес к этому клеточному автомату, как и вообще ко всем клеточным автоматам, постепенно перерос из игрового в научный. Когда начала бурно развиваться микроэлектроника (70-е годы) и появилась потребность в быстродействующих электронных схемах на многих элементарных автоматах, действующих параллельно, то клеточный автомат приобрёл важный практический смысл. Заложенные в его идее принципы параллельности и близкодей-ствия межклеточных взаимодействий как нельзя лучше соответствуют требованиям технологии больших интегральных схем.

Следующий всплеск интереса к клеточным автоматам был связан уже не с построением параллельных устройств, а с построением новых моделей вычислений [4, 5]. Это произошло в середине 80-х годов, когда были предложены клеточные автоматы, эволюция которых моделирует процесс диффузии [6-8], разделения фаз [2, 7], реакционно-диффузионные процессы [9-11], знаменитую реакцию Белоусова-Жаботинского [12], образование диссипативных структур [13].

На волне интереса к клеточно-автоматному моделированию стали развиваться асинхронные клеточные автоматы. Отчасти это связано с тем, что большое количество уже существующих кинетических методов Монте-Карло [14-16], в которых обычно используются регулярные решетки и локальные правила изменения характеристик частиц материала, представляются в форме клеточного автомата.

При этом, асинхронное клеточно-автоматное (АКА) моделирование реальных процессов требует больших вычислительных мощностей, поскольку для выявления каких-либо свойств моделируемых процессов необходимо оперировать большими количествами частиц (1010-Ю12) в течение длительного времени (103-105 итераций). Естественно возникает потребность использовать параллельные вычислители для ускорения вычислений, к этому также располагают основные свойства клеточного автомата - естественная мелкозернистая параллельность и локальность взаимодействий при функционировании. Однако, асинхронные клеточные автоматы не поддаются столь же легкому распараллеливанию, как и обычные, синхронные, клеточные автоматы.

Это связано с тем, что при распараллеливании необходимо соблюдать следующие свойства: корректность и эффективность распараллеливания, а также равноправие в выборе клеток. Первые два свойства типичны для большинства параллельных программ. Последнее свойство возникает из определения асинхронного режима работы клеточного автомата и заключается в следующем: вероятность выбора некоторой клетки на некотором шаге должна быть равна вероятности выбора любой другой клетки на любом другом шаге. Подробнее проблемы параллельного исполнения асинхронных клеточно-авто-матных моделей рассматриваются в Главе 2.

Существующие параллельные алгоритмы можно разделить на два класса: не нарушающие свойства равноправия в выборе клеток [16, 17] (сохраняющие асинхронизм), и нарушающие его [18, 19] (нарушающие асинхронизм). Алгоритм [17] разрабатывался и тестировался на компьютере с общей памятью в 1987 году, его эффективность на современных мультипроцессорах мала (Глава 2). В основе алгоритма [16] лежит алгоритм параллельного моделирования дискретно-событийных систем. Из результатов работы [16] следует, что эффективность параллельного исполнения авторской реализации этого алгоритма слишком мала для асинхронных клеточно-автоматных моделей физико-химических процессов. В работах [18-20] на трёх моделях показано, что применение алгоритмов, нарушающих асинхронизм, не вносит существенных изменений в моделируемый процесс. Вопрос о том, для каких моделей использование алгоритмов, нарушающих асинхронизм, допустимо, то есть не вносит изменения в моделируемый процесс, остаётся открытым.

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

Целью настоящей работы является создание методов и алгоритмов параллельного моделирования микроуровневых физико-химических процессов, описываемых асинхронными вероятностными клеточными автоматами, для современных вычислителей с различной архитектурой (мультипроцессор, мультикомпьютер и графический ускоритель).

Для достижения поставленной цели следует решить следующие задачи:

1. Разработать формализм для описания КА моделей микроуровневых физико-химических процессов.

2. Проанализировать существующие методы и алгоритмы параллельного исполнения КА моделей физико-химических процессов.

3. Разработать и реализовать новые алгоритмы исполнения К А моделей физико-химических процессов для мультипроцессоров, мультикомпью-теров и графических ускорителей.

4. Провести вычислительные эксперименты по определению эффективности реализаций существующих и разработанных параллельных алгоритмов на вычислителях с различной архитектурой.

5. Провести вычислительные эксперименты по определению статистического смещения моделируемого процесса для существующих и разработанных алгоритмов, нарушающих асинхронизм.

6. Разработать язык для описания К А моделей физико-химических процессов и транслятор, переводящий это описание в программы для вышеперечисленных вычислителей.

Научная новизна заключается в том, что в работе впервые:

1. Предложен формализм для описания К А моделей физико-химических процессов, основанный на алгоритме параллельных подстановок.

2. Предложен новый метод параллельного исполнения АКА моделей, основанный на расширенных блочно-синхронных режимах работы КА и обеспечивающий меньшее статистическое смещение при моделировании.

3. Обоснована необходимость использования сохраняющих асинхронизм параллельных алгоритмов исполнения КА моделей физико-химических процессов в общем случае.

4. Разработаны и реализованы эффективные алгоритмы исполнения К А моделей физико-химических процессов на следующих вычислителях с параллельной архитектурой: мультипроцессоры, мультикомпьютеры и графические ускорители.

5. Разработан язык описания и транслятор, позволяющие автоматизировать разработку КА моделей физико-химических процессов.

Основные положения, выносимые на защиту:

1. Формализм для описания К А моделей микроуровневых физико-химических процессов.

2. Новый метод параллельного исполнения АКА моделей, основанный на расширенных блочно-синхронных режимах работы КА и обеспечивающий меньшее статистическое смещение при моделировании.

3. Параллельные алгоритмы исполнения КА моделей физико-химических процессов для вычислителей с различной параллельной архитектурой (мультипроцессоры, мультикомпьютеры и графические ускорители.).

4. Язык описания КА моделей микроуровневых физико-химических процессов и транслятор, переводящий описание К А модели на этом языке в программу на языке С++/Ргосеэ8^.

Научная и практическая ценность. Предложенные методы и алгоритмы позволяют за приемлемое время моделировать микроуровневые физико-химические процессы, протекающие на поверхностях катализаторов [14, 21], в масштабе необходимом исследователям для сравнения с реальными экспериментами. Созданные язык и транслятор позволяют автоматизировать процесс разработки подобных моделей.

Достоверность полученных результатов. Все основные положения и выводы, сформулированные в диссертации, подтверждаются строгими математическими выводами и доказательствами, а также тестированием отдельных процедур программного комплекса на тестовых моделях, разработанных ранее другими авторами [14, 21].

Личный вклад автора. Все выносимые на защите результаты получены автором лично.

Апробация. Результаты диссертационной работы были представлены на 7-и Российских и международных конференциях:

1. V Всеросийская конференция молодых ученых, Санкт-Петербург, 2008;

2. Международная научная студенческая конференция "Студент и научно-технический прогресс", Новосибирск, 2008;

3. Parallel computing technologies, РаСТ-2009, Novosibirsk;

4. Cellular Automata for Research and Industry, ACRI-2010, Italy, Ascoli Picheno, 2010;

5. XIX International Conference on Chemical Reactors "CHEMREACTOR-19", Austria, Vienna, 2010;

6. VIII International Conference Mechanisms of Catalytic Reactions, Novosibirsk, 2011;

7. Parallel computing technologies, PaCT-2011, Kazan, 2011;

8. Конференция молодых ученых по вычислительной математике и информатике, ИВМиМГ СО РАН, 2011.

Результаты докладывались на семинарах:

1. "Математическое и архитектурное обеспечение параллельных вычислений" под руководством д.т.н. В.Э. Малышкина;

2. "Архитектура, системное и прикладное программное обеспечение кластерных суперЭВМ" под руководством д.т.н. Б.М. Глинского;

3. "Методы Монте-Карло" под руководством чл.-корр. Г.А. Михайлова;

4. "Семинар ИДСТУ СО РАН по вычислительным технологиям" под руководством д.т.н. Г.А. Опарина (г. Иркутск).

Публикации. Основные результаты опубликованы в изданиях рекомендованных ВАК (3 публикации), в трудах конференций (6 публикаций), и местных изданиях (2 публикации).

Автор выражает искреннюю благодарность научному руководителю О.Л. Бандман за ценные обсуждения, постоянную поддержку и внимание к данной работе.

Заключение

В данной работе были получены следующие результаты.

1. Предложен формализм, основанный на теории параллельных подстановок, для описания КА моделей физико-химических процессов.

2. Проанализированы существующие методы и алгоритмы параллельного исполнения КА моделей физико-химических процессов. Обоснована необходимость создания новых методов и алгоритмов.

3. Предложен новый метод параллельного исполнения АКА моделей, основанный на расширенных блочно-синхронных режимах работы КА, обеспечивающих меньшее статистическое смещение при моделировании.

4. Обоснована необходимость использования сохраняющих асинхронизм параллельных алгоритмов исполнения КА моделей физико-химических процессов в общем случае.

5. Разработаны и реализованы эффективные алгоритмы исполнения К А моделей физико-химических процессов на следующих вычислителях с параллельной архитектурой: мультипроцессоры, мультикомпьютеры и графические ускорители.

6. Разработаны язык описания К А моделей физико-химических процессов и транслятор, переводящий это описание в программы для различных вычислителей с параллельной архитектурой.

1. von Neumann J. Theory of self reproducing automata. USA: University of 1.linois Press, 1966. P. 388.

2. Wolfram S. A new kind of science. USA: Wolfram Media, 2002. P. 900. ISBN: 1579550088. URL: http://www.wolframscience.com.

3. Gardner M. Wheels, Life, and Other Mathematical Amusements. USA: W.H. Freeman, 1983. P. 261.

4. Vichniac G. Simulating physics with cellular automata // Physica D: Nonlinear Phenomena. 1984. Vol. 10. P. 96-116.

5. Wolfram S. Statistical Mechanics of Cellular Automata // Reviews of Modern Physics. 1983. Vol. 55. P. 601-644.

6. Toffoli T. Computation and construction universality of reversible cellular automata // Journal of Computer and System Sciences. 1977. Vol. 15. P. 213-231.

7. Margolus N., Toffoli T. Cellular Automata Machines: A New Environment for Modeling. USA: MIT Press, 1987. P. 259.

8. Bandman O. Comparative Study of Cellular Automata Diffusion Models // Proceedings of Parallel Computing Technologies, 5th International Conference, PaCT-99 / Ed. by V. Malyshkin. Vol. 1662 of LNCS. Springer, 1999. P. 395-409.

9. Weimar J. Cellular Automata for Reaction-Diffusion Systems // Parallel Computing. 1997. Vol. 23. P. 1699-1715.

10. Бандман О. Клеточно-автоматное моделирование диффузионно-реакционных процессов // Автометрия. 2003. Т. 3. С. 1-16.

11. Madore В., Ffreedman W. Computer simulation of Belousov-Zhabotinski reaction // Scinece. 1983. Vol. 222. P. 615-616.

12. Пригожин И. От существующего к возникающему. Время и сложность в физических науках. М.: Наука, Физматгиз, 1985. С. 328.

13. Elokhin V. е. a. Application of Statistical Lattice Models to the Analysis of Oscillatory and Autowave Processes in the Reaction of Carbon Monoxide Oxidation over Platinum and Palladium Surfaces // Kinetics and Catalysis. 2003. Vol. 44. P. 692-700.

14. Neizvestny I. 3D-model of epitaxial growth on porous 111 and 100 Si surfaces // Computer Physics Communications. 2002. Vol. 147. P. 272-275.

15. Lubachevsky B. Efficient parallel simulation of asynchronous cellular arrays // Complex Systems. 1987. Vol. 1. P. 1099-1123.

16. Nedea S., Lukkien J., Hilbers P., Jansen A. Methods for Parallel Simulations of Surface Reactions // Proceedings of the 17th International Symposium on Parallel and Distributed Processing / Ed. by B. Werner. IEEE Computer Society, 2003. P. 256.

17. Ziff R., Gulari E., Barshad Y. Kinetic phase transitions in an irreversible surface-reaction model // Phys Rev Lett. 1986. Vol. 56. P. 2553-2556.

18. Achasova S., Bandman O., Markova V., Piskunov S. Parallel Substitution Algorithm: Theory and Application. Singapore: World Scientic, 1994. P. 220.

19. Metropolis N., Rosenbluth A., Rosenbluth M. et al. Equation of State Calculations by Fast Computing Machines // Chem. Phys. 1953. Vol. 31. P. 1087-1092.

20. Chopard B., Droz M. Cellular Automata Modeling Of Physical Systems. USA: Cambridge University Press, 1998. P. 341.

21. Ачасова С., Бандман. О. Корректность параллельных вычислительных процессов. Новосибирск: Наука. Сиб. Отд., 1990. С. 253.

22. Калгин К. Параллельная реализация асинхронных клеточно-автоматных алгоритмов // Научно-технический вестник СПбГУ информационных технологий, механики и оптики. 2008. Т. 54. С. 108-113.

23. Михайлов Г., Войтишек А. Численное статистическое моделирование. Методы Монте-Карло. М.: Академия, 2006. С. 368.

24. Pseudo random number generators: uniform and non-uniform distributions. URL: http://www.agner.org/random/ (дата обращения: 01.04.2012).

25. Intel Many Core Testing Lab. URL: http://software.intel.com/en-us/ articles/intel-many-core-testing-lab (дата обращения: 01.04.2012).

26. Message Passing Interface. URL: http://ru.wikipedia.org/wiki/ MessagePassingInterf асе (дата обращения: 01.04.2012).

27. NVIDIA CUDA Programming Guide. URL: http://www.nvidia.com/cudaдата обращения: 01.04.2012).

28. Processing. URL: http://processing.org (дата обращения: 01.04.2012).

29. Eli project. URL: http://eli-project.sourceforge.net (дата обращения: 01.04.2012).