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

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

¿ШладлА___

—»а *

Киреева Анастасия Евгеньевна

КЛЕТОЧНО-АВТОМАТНОЕ МОДЕЛИРОВАНИЕ САМООРГАНИЗУЮЩИХСЯ РЕАКЦИОННО-ДИФФУЗИОННЫХ ПРОЦЕССОВ

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

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

Новосибирск — 2013

- 8 АВГ 2013

005531948

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

руководитель: Бандман Ольга Леонидовна Официальные Сабельфельд Карл Карлович,

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

ральное государственное бюджетное учреждение науки Институт вычислительной математики и математической геофизики СО РАН, главный научный сотрудник Казунина Галина Алексеевна, доктор технических наук, доцент, Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Кузбасский государственный технический университет имени Т.Ф. Горбачёва» Ведущая Федеральное государственное бюджетное учреждение

организация: науки Институт физики прочности и материаловеде-

ния Сибирского отделения Российской академии наук Защита состоится 12 ноября 2013 года в 15.00 часов на заседании диссертационного совета Д 003.061.02 на базе Федерального государственного бюджетного учреждения науки Института вычислительной математики и математической геофизики Сибирского отделения Российской академии наук (ИВМиМГ СО РАН) по адресу: 630090, г. Новосибирск, проспект академика Лаврентьева, 6. С диссертацией можно ознакомиться в библиотеке Федерального государственного бюджетного учреждения науки Института вычислительной математики и математической геофизики СО РАН. Автореферат разослан 15 июля 2013 года. Учёный секретарь

диссертационного совета Д 003.061.02 П

на базе ИВМиМГ СО РАН, д.ф.-м.н. (/хЛх Сорокин Сергей Борисович

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

Актуальность работы

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

Эффективным методом изучения процессов самоорганизации в сложных нелинейных системах является теория клеточных автоматов (КА), в которой динамика сложных систем описывается простыми дискретными правилами переходов. КА-подходу к моделированию физико-химических, биологических и социальных явлений посвящены работы российских и зарубежных авторов: АладьеваВ.З., Бандман О.Л., ВанагаВ.К., Вольфрама С., Евреинова Э.В., Мар-голуса Н., Тоффоли Т., Чуа О., Янга Д. и многих других.

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

диффузионной модели А. Тьюринга1. Асинхронные тоталистические КА-

2

модели моделируют возникновение пятен на шкурах животных, позволяют формировать пористые среды с различной морфологией, описывают возникновение автоволн в реакции Белоусова-Жаботинского, имитируют простран-

1 Turing A.M. The Chemical Basis of Morphogenesis // Phil. Trans. Roy. Soc. Lond. B. 1952. Vol. 237. N. 641. P. 37-72.

2 Young D A. A local activator-inhibitor model of vertebrate skin patterns // Math. Biosciences. 1984. Vol. 72. P. 51-58.

ственно-временную динамику реакций гетерогенного катализа.

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

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

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

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

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

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

3. Разработка вероятностной асинхронной КА-модели (Ксо) реакции окисления монооксида углерода (СО) на поверхности платины (Р^оо), анализ про-

3 Bandman O.L. Parallel simulation of asynchronous cellular automata evolution // Proceedings of ACRI-2006. Berlin: Springer. 2007. LNCS 4173. P. 41-48.

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

Методы исследования.

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

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

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

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

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

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

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

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

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

2. Бифуркационная диаграмма реакции окисления СО на платине, построенная в результате анализа эволюции вероятностной КА-модели Ксо.

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

4. Научно-исследовательский программный комплекс для моделирования на суперкомпьютере процессов самоорганизации: формирования устойчивых структур С ПОМОЩЬЮ Ks И устойчивых колебаний С ПОМОЩЬЮ Ксо-

Апробация работы.

Основные результаты диссертации докладывались на Российских и международных конференциях: Международная конференция "Cellular Automata for Research and Industry", Греция, 2012; IX Российская конференция с международным участием "Новые информационные технологии в исследовании сложных структур", Томск, 2012; Международная научная конференция "Параллельные вычислительные технологии", Новосибирск, 2012; 11-th International Conference on Parallel Computing Technologies, Казань, 2011; XI Всероссийская конференция молодых учёных по математическому моделированию и информационным технологиям, Красноярск, 2010; V Сибирская конференция по параллельным и высокопроизводительным вычислениям, Томск, 2009; Конференция молодых учёных ИВМиМГ СО РАН, Новосибирск, 2009, 2011, 2012, 2013; XLVII Международная научная студенческая конференция,

6

Новосибирск, 2009. А также на семинарах ИВМиМГ: "Математическое и архитектурное обеспечение параллельных вычислений" и по междисциплинарному интеграционному проекту №47 под руководством Михайлова Г.А.

Работа выполнялась в рамках Проекта №7 ИВМиМГ, а также Проекта 15.9 Президиума РАН, междисциплинарного проекта №47 СО РАН, проекта № 12-03-00766-а, № 12-07-09289-моб_з и № 12-01-31455-мол_а.

Публикации. По результатам работы опубликовано 14 работ, среди которых 11 статей, в том числе две статьи в журналах, входящих в список ВАК.

Структура и объём диссертации.

Диссертация состоит из введения, трёх глав, заключения, списка литературы, содержащего 78 наименований. Общий объём диссертации — 112 страниц. Работа содержит 54 рисунка и 8 таблиц.

Содержание работы

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

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

Тоталистический КА (ТКА) определяется следующими понятиями:

= (A,Xd ,Q,ju), где А={0,\} — алфавит состояний клеток, X1 — конечное множество имён клеток, X1 = {х| (i,j) при d= 2, (i,j, к) при d= 3}, i,j, k e N, 0(jc) — локальный оператор, вычисляющий новые состояния клеток, а /«е{а, а, р} — режим функционирования, определяющий порядок применения 0(jc) к клеткам: а — синхронный, а — асинхронный, р — блочно-синхронный режим.

Каждой клетке соответствует пара (и, jc), где и е А, х е X. На множестве имён X определены именующие функции <р: Х—+Х, конечное множество имену-

7

ющих функций называется шаблоном соседства Тк(х). В качестве шаблона соседства КГк4 используется квадрат К* К клеток для й = 2 и куб КхКхК для с1 = 3.

Локальный оператор 0(х) вычисляет новое состояние клетки с именем д: в зависимости от взвешенной суммы состояний соседних клеток {ик, <Рк{х)),

где wk — весовые коэффициенты, которые являются элементами матрицы весов W,\W\ = |7>(.v")], wk > О называются активаторами (р), wk < 0 - ингибиторами (и). Константа 5еК- это порог функции s(uk), в экспериментах используется 5=0. Эволюция исследуется для матриц весов двух видов: IV, с двумя значениями элементов: п < 0 и р > 0, и W2 с тремя значениями элементов: п<0,/)|<0и р> 0, при К = 7, что является оптимальным для получения большого многообразия устойчивых структур. Множество состояний всех клеток JC е X в момент времени t является глобальным состоянием клеточного массива П(/).

Эволюция ~i\rKA моделирует процессы структурообразования. В результате проведения вычислительных экспериментов установлено, что эволюция сходится к устойчивым состояниям двух типов: 1) через /' итераций глобальное состояние клеточного массива не изменяется, т.е. 3 /': для V t > t' £2(i) = £2(0; 2) через t' итераций происходит чередование двух глобальных состояний, т.е. 3 t': Cî(t'+2-k) = П(С) и £2(У+2-Ш) = П(/'+1), к е N .

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

Теорема 1. Пусть определён тоталистический КА с матрицей весов вида IV,, начальным состоянием Q(0) и раз.мером клеточного массива \Х], тогда эволюция определяется только значением р/п и не зависит от конкретных значений активатора и ингибитора.

1, если s(uk ) = -uk>B,

О, иначе,

Теорема 2. Пусть определён тоталистический КА с матрицей весов вида W2, начальным состоянием Q(O) и размером клеточного массива \Х\, тогда эволюция N7K4 определяется только значениями двух отношений: п/р и П]/р и не зависит от конкретных значений активатора и ингибиторов.

На основании Теоремы 1 и Теоремы 2 проведена классификация устойчивых структур, и построены диаграммы устойчивых состояний для эволюции Х]КА с матрицей весов вида W, в зависимости от значений р!п, и для с матрицей весов вида W2 в зависимости от значений п/р и щ/р, при Г2(0), содержащем одну единичную клетку и остальные клетки с состоянием и = 0.

Для получения сложных неоднородных структур предложена двухслойная ТКА-модель, являющаяся однонаправленной параллельной композицией ТКА Кга и асинхронного КА второго слоя: Nv = Т(К7Г/),К2;). В качестве второго слоя выбран КА, моделирующий распространение огня в лесу: ^2/, =(AiL'XiL,®1L,cc), эволюция K2i имитирует неоднородное динамически изменяющееся распределение реагентов трёх типов: A2L = {0, 1, 2}, где 0 - это земля, 1 - дерево, 2 - огонь. Между X2L и ХТсл определяется взаимнооднозначное соответствие: Х'гсл = J Шаблон соседства T2L(y) - крест из пяти клеток при d= 2 и из семи клеток при d= 3. Локальный оператор:

0, если V = 2,

©2iOO:(v>jO->(v'.jO. v' = -2, если V = 1 & {(3 (vk,<pk(y)): vk = 2) & rand<Pf},

1, если v = 0 & rand < Pt,

где <pk(y) e T2L(y), rand e (0, 1) - случайное число, Pf и P, - вероятности самовозгорания и появления дерева, соответственно.

Композиция Ns предполагает, что новые состояния клеток основного КА Kj^ вычисляются не только в зависимости от состояний его соседних клеток, но и от состояний клеток КА второго слоя К2/:

il, еслиф4)= £ f(vk)-ut>B, 0 (*): О0,х) . {(uk,tpk(x)),(vk,<pk{x))} и' = j *=о,..й|

[О, иначе,

N(l)-N(2) /К) = /^<Л) = \тк\

■wk, если wt > 0 (активатор).

wk, если w^ <0 (ингибитор).

где - состояние к-ой клетки с именем у е Хц, А,г( 1) и N(2) - количество клеток с состоянием V = 1 и V = 2, принадлежащих шаблону соседства ТК(у) с131,

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

Рис. 1. Изменение морфологии пористой среды, формирующейся в течение эволюции К, при = 50x50x50, п = -0.5, и, = -0.1, р=2 для Pf= 0.5, Р, =0.00005 и начального распределения единичных клеток с вероятностью 0.005.

Вторая глава содержит результаты исследования асинхронной вероятностной КА-модели реакции окисления СО на поверхности Ptioo: Ксо = (А,Х,@,а), являющейся примером самоорганизации с возникновением устойчивых колебаний. Алфавит состояний определяется реагентами реакции: Л = {*,>.,,*hex,C(Zl,С&2,О^,(У^}, *1х] и *hex обозначают свободные активные центры поверхности с гексагональной и кубической структурой, CO^]s и СО*2 — это молекулы монооксида углерода, адсорбированные на 1x1 и hex поверхности, соответственно, O^l и Oaedxs - молекулы кислорода, адсорбированные на 1x1 и hex поверхности. Клеточный массив соответствует поверхности катализатора, множество имён X задано в виде двумерной решётки. В модели исполь-

итерация 2

итерация 5

зуются следующие шаблоны соседства: Т\ (х) - одна клетка, Т5(х) — крест, Т9(х) — квадрат 3x3 клетки и Т13(х) — ромб из 13 клеток.

Локальный оператор 0(х) определяется согласно механизму4 реакции окисления СО и является системой подстановок и их суперпозиций: ©(.к) = Ф/((0(|9),02,в},в4,в5,Ö(6 V),ö(79|,ö(8 9)), где Фк - оператор случайного выбора, вI - адсорбция СО, 02 - десорбция СО с hex поверхности, 03 - десорбция СО с 1x1 поверхности, в4 - реконструкция поверхности в гексагональную, 05 - реконструкция поверхности в кубическую, в6 - адсорбция 02 на hex поверхность, 07 - адсорбция Oi на 1x1 поверхность, 0S- диффузия COajs по поверхности катализатора, 09 — взаимодействие между молекулами CO„,i5 и Oads.

Взаимодействие между молекулами COuas и Oads, оказавшимися на соседних активных центрах, происходит мгновенно, поэтому сразу же после адсорбции СО, адсорбции 02 и диффузии проверяется возможность осуществления реакции с помощью суперпозиции подстановок #(/ 9) = 6,(0/), / = 1,6,7,8 , которая предполагает применение в9 к результату выполнения в] с шаблоном Гп(л:). Подстановки 0/ и суперпозиции 0()9) выбираются с вероятностью 8

р, = к, /^/с, 1 = 1,...,8, где константы скоростей стадий реакции.

1=1

В результате КА-моделирования получены устойчивые колебания концентраций реагентов, адсорбированных на поверхности катализатора, скорости образования С02 и доли поверхности с кубической и гексагональной структурой (Рис. 2а). Колебания соответствуют периодической смене покрытий поверхности реагентами COajs Oads, которая происходит в виде образования и распространения островков из COac/s и ()ujs по поверхности катализатора.

В результате КА-моделирования и анализа эволюции Хсо построена бифуркационная диаграмма реакции окисления в пространстве констант скорости адсорбции 02 и СО (Рис. 26). В зависимости от значений этих констант эволю-

4 Elokhin V.l., Latkin E.I., Matveev A.V, and Gorodetskii V.V. 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. N. 5. P. 692-700.

11

ция Хсо сходится к пяти устойчивым состояниям: 1) покрытие всей поверхности CO^x^; 2) покрытие всей поверхности 3) устойчивые колебания концентраций всех реагентов и скорости образования С02; 4) устойчивые колебания концентраций и *кех; 5) нерегулярные колебания реагентов при малых значениях констант к6 е[0;8) и Л, е[0;10).

+к6

0,8 0,6

я

§ 0,2

и и

0 50 100 150 200 250 количество итераций

-С02

-СОасЬ--Оа&

а)

20 40 60 80 100 120 140 160 180 200 б)

Рис. 2. Результаты КА-моделирования: а) колебания концентраций реагентов и скорости образования С02\ б) бифуркационная диаграмма реакции.

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

Преобразование асинхронного КА в блочно-синхронный выполняется следующим образом: 1) на множестве имён X определяется блок В(х), включающий в себя все шаблоны соседства: с В(х); 2) блок В(х) порождает на множестве имён X разбиение П = {Пх,П2,...,Пті^}, для V Пк, к= 1,...,|£(д:)|:

У В(х) = Х, В(х)[)В(у) = 0 \/х,у <а П, ,хфу 3) итерация разби-

I В(Х) I

I л»

вается на |б(*)1 этапов, и на каждом этапе 0(лс) синхронно применяется ко всем клеткам выбранного случайным образом подмножества П^

Для проверки применимости блочно-синхронного преобразования к Кл и

N0j проводится сравнительный анализ их эволюций при /; = а и /л = р. Для Ns вычисляются следующие численные характеристики: перколяция Per вдоль плоскостей XY, XZ и YZ, число компонент связности для m=1Z.(1)h« = 0 L( 0), площади компонент связности пористость Рог. Для Кго вычисляются концентрации адсорбированных реагентов: n(COhex), п(СО,УІ), n(Ohex), niO,,,), скорость образования С02: v(C02), доли поверхности с 1><1 и hex структурой: f f (hex) и периоды колебаний Т. Для численных характеристик, полученных при /л = а и // = р, рассчитываются следующие статистики: оценки математического ожидания (Ма, Мр) и дисперсии (DH, Dp), доверительные интервалы для математического ожидания (1_Ма, 1_Мр) и дисперсии (/_£>„, I_Dp) и среднеквадратичные разности (Е).

С помощью проведения сравнительного анализа значений статистик, вычисленных для численных характеристик эволюции Ns для различных размеров блока Щх), установлено, что при увеличении |Д(х)| разница между значениями статистик уменьшается, и эволюция блочно-синхронного Kv сходится к эволюции асинхронного. Причём критерий х2 — Пирсона с уровнем значимости 0.999 показал, что гипотеза об однородности распределений Srn), вычисленных с помощью Ks при /v=a и /у=Р, принимается и для \В{х)\=-\Т-,{х)\, и для |5(д-)|=21x21x21. Следовательно, при ¡л=а и ft=Р формируются похожие устойчивые структуры, различия между эволюциями являются допустимыми для вероятностных процессов.

Сравнительный анализ эволюций Ксо показал, что разница между статистиками, вычисленными для численных характеристик его эволюции при ju=a и /¿=Р, в среднем составляет 10"3. Причём распределения значений численных характеристик, полученных для /и=а и /<=Р, совпадают. Кроме того, для блочно-синхронного и асинхронного режимов асо построены одинаковые бифуркационные диаграммы. Следовательно, Ксо при ¡л = а и /л = /? демонстрирует одинаковый характер поведения реакции окисления.

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

13

сий обеих КА-моделей: К4. и Ксо.

Распараллеливание блочно-синхронных КА Ks и Кго выполняется с помощью гибридной модели MPI+OpenMP на суперкомпьютере «МВС-100К» МСЦ РАН. Клеточный массив разделяется на домены \Х' ЩХ | /рг , которые распределяются между рг mpi-процессами. В каждом процессе создаётся по два OpenMP-потока, которые на каждом к-ом этапе одновременно вычисляют состояния клеток своих доменов Av в соответствии с выбранным подмножеством Пк. В случае двухслойного ТКА Ns OpenMP-потоки одновременно вычисляют состояния клеток основного КА и КА-второго слоя: О-тка и П2г- Обмен граничными значениями выполняется в конце каждого к-ого этапа.

Для оценки эффективности параллельной реализации К5 вычисляется эффективность в слабом смысле (weak scaling efficiency): Qw(pr)=T\ITpr, где Tpr — время вычислений на рг процессах, причём размер домена на всех процессах остаётся фиксированным при изменении рг. В результате распараллеливания Кх получена Qw(pr) выше 70% для рг < 1024. В результате распараллеливания Ксо с [X'|=8000><8000 клеток получена эффективность (strong scaling efficiency) Q(pr)=T\l{Tpr-pr) выше 80% при использовании до 128 процессов, т.е. при размере домена | X' | > 2.04-10б клеток.

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

В заключении представлены основные результаты:

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

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

3. Разработана КА-модель К со реакции окисления СО на Ptjoo, на основании анализа её эволюции определены пять режимов протекания реакции и построена бифуркационная диаграмма в пространстве констант адсорбции СО и О2.

4. С ' помощью проведения сравнительного анализа результатов КА-моделирования для асинхронного и блочно-синхронного режимов показана применимость блочно-синхронного преобразования для Ns и Ксо-

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

Список публикаций по теме диссертации В журналах из списка ВАК:

1. Шарифулина (Киреева) А.Е. Параллельная реализация каталитической реакции (СО + 02 —► С02) с помощью асинхронного клеточного автомата // Вестник ЮУрГУ. 2012. № 47 (3 06). С. 112-126.

2. Маркова В.П., Шарифулина (Киреева) А.Е. Параллельная реализация асинхронного клеточного автомата, моделирующего реакцию окисления СО на палладии // Прикладная Дискретная Математика. 2011. № 1. С. 116-127.

В других изданиях:

3. Sharifulina (Kireeva) A. Investigation of Stable Patterns Formed by Totalistic Cellular Automata Evolution // Cellular Automata. LNCS 7495, Springer, 2012. P. 161-170.

4. Eiokhin V.I., Sharifulina (Kireeva) A.E. Simulation of Heterogeneous Catalytic Reaction by Asynchronous Cellular Automata on Multicomputer // Proc. of PaCT 2011, LNCS 6873, Springer, 2011. P. 204-209.

5. Markova V.P., Sharifulina (Kireeva) A.E. Parallel Implementation of Kinetic Cellular Automata for Modeling CO Oxidation over Pd(l 10) Surface // Proc. of MTPP 2010, LNCS 6083, Springer, 2010. P. 212-221.

6. Шарифулина (Киреева) A.E. Параллельная реализация каталитической реакции (СО + 02 —► С02) / Ptno с помощью асинхронного клеточного автомата // Параллельные вычислительные технологии: труды международной научной конференции. Челябинск: Изд-во ЮУрГУ, 2012. С. 325-335.

7. Sharifulina (Kireeva) A. Stable patterns formation by totalistic cellular automata //

15

Bull. Nov. Comp. Center, Comp. Science 33, 2012. P. 69-78.

8. Markova V., Sharifulina (Kireeva) A. Using kinetic cellular automata for modeling CO oxidation over Pduo surface // Bull. Nov. Comp. Center, Comp. Science 30, 2010. P. 27-41.

9. Шарифулина (Киреева) A.E. КА-моделирование гетерогенной каталитической реакции (СО + О «-* С02)/ Pt]0o с помощью специализированной системы программирования CACHE. // Труды конференции молодых учёных - Новосибирск: Изд-во ИВМиМГ СО РАН, 2011. С. 104-117.

10. Шарифулина (Киреева) А.Е. Исследование поведения каталитической реакции окисления монооксида углерода на поверхности палладия с помощью вероятностной клеточно-автоматной модели // Труды конференции молодых учёных. Новосибирск: ИВМиМГ СО РАН, 2009. С. 157-164.

11. Шарифулина (Киреева) А.Е. Параллельная реализация вероятностного асинхронного клеточного автомата, моделирующего каталитическую реакцию окисления монооксида углерода (СО) на поверхности палладия (Pdn0) // Пятая Сибирская конференция по параллельным и высокопроизводительным вычислениям /Под ред. проф. A.B. Старченко. Томск: Изд-во Том. ун-та, 2010. С. 99-104.

12. Шарифулина (Киреева) А.Е. Исследование устойчивых структур, формирующихся в результате эволюции синхронного и асинхронного клеточных автоматов // Новые информационные технологии в исследовании сложных структур. Тезисы докладов девятой Российской конференции с международным участием. Томск: Изд-во НТЛ, 2012. С. 27-28.

13. Шарифулина (Киреева) А.Е. Построение бифуркационной диаграммы реакции окисления СО на палладии с помощью асинхронного клеточного автомата // Тезисы докладов XI Всероссийской конференции молодых учёных по математическому моделированию и информационным технологиям. Новосибирск, 2010. С. 79-80.

14. Шарифулина (Киреева) А.Е. Кпеточно-автоматное моделирование реакции окисления монооксида углерода на поверхности палладия. // Материалы XLVII Международной научной студенческой конференции «Студент и научно-технический прогресс». Изд-во НГУ, 2009. С. 220.

Подписано в печать 01.07.2013 Формат 60x84 1\16 Усл. печ. л. 1 Объем 16 стр. Тираж 100 экз. Заказ № 182 Отпечатано Омега Принт 630090, г. Новосибирск, пр. Ак.Лаврентьева,6 email: omegap@yandex.ru

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

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

04201363389

^ абьСсцчЛ^

Киреева Анастасия Евгеньевна

КЛЕТОЧНО-АВТОМАТНОЕ МОДЕЛИРОВАНИЕ САМООРГАНИЗУЮЩИХСЯ РЕАКЦИОННО-ДИФФУЗИОННЫХ ПРОЦЕССОВ

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

ДИССЕРТАЦИЯ на соискание учёной степени кандидата физико-математических наук

Научный руководитель д.т.н., проф. Бандман Ольга Леонидовна

Новосибирск 2013

Оглавление

Оглавление...................................................................................................................2

Введение.......................................................................................................................4

Глава 1 Моделирование процессов структурообразования с помощью тоталистического клеточного автомата..................................................................18

1.1 Основные понятия теории клеточных автоматов.........................................18

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

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

1.4 Зависимость эволюции №ТКА с матрицей весов, содержащей одно значение ингибитора, от значений весовых коэффициентов.............................................26

1.4.1 Классификация устойчивых структур, формирующихся в результате эволюции ХГКА приа? = 2....................................................................................29

1.4.2 Классификация устойчивых структур, формирующихся в результате эволюции при ¿/= 3....................................................................................34

1.5 Зависимость эволюции КТКА с матрицей весов, содержащей два значения ингибитора, от значений весовых коэффициентов.............................................37

1.6 Двухслойный тоталистический клеточный автомат.....................................47

1.7 Выводы..............................................................................................................54

Глава 2. Клеточно-автоматная модель каталитической реакции окисления

монооксида углерода на металлах платиновой группы........................................55

2.1 Реакция окисления СО на поверхности металлов платиновой группы... 55

2.2 Механизм реакции окисления СО на поверхности платины Р^оо...............57

2.3 Клеточно-автоматная модель реакции окисления СО на Р1........................59

2.4 Результаты моделирования реакции окисления с помощью асинхронного

вероятностного КА К со.........................................................................................63

2

2.5 Влияние размера массива и интенсивности диффузии на динамику реакции окисления.................................................................................................67

2.6 Бифуркационная диаграмма реакции окисления, построенная с помощью К со...........................................................................................................................73

2.7 Выводы..............................................................................................................80

Глава 3. Параллельная реализация асинхронных клеточных автоматов на основе блочно-синхроннош преобразования.........................................................81

3.1 Преобразование асинхронного КА в блочно-синхронный..........................81

3.2 Проверка применимости бл очно-синхронного преобразования асинхронных КА.....................................................................................................82

3.2.1 Проверка применимости блочно-синхронного преобразования для асинхронного тоталистического КА КТКА........................................................84

3.2.2 Проверка применимости блочно-синхронного преобразования для асинхронного двухслойного тоталистического КА ..................................89

3.2.3 Проверка применимости блочно-синхронного преобразования для асинхронного КА , моделирующего реакцию окисления СО на Р1юо----92

3.3 Результаты распараллеливания блочно-синхронного КА...........................95

3.3.1 Результаты распараллеливания блочно-синхронного двухслойного тоталистического КА ....................................................................................96

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

3.4 Выводы..............................................................................................................99

Заключение...............................................................................................................101

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

Введение

Актуальность работы

Структурообразование лежит в основе многих природных явлений. Наиболее известными примерами возникновения устойчивых структур в живой и неживой природе являются конвективные и гидродинамические ячейки, вихри в атмосфере и океане, лазеры, концентрические круги и движущиеся спирали в реакции Белоусова-Жаботинского, поверхностные волны в реакциях гетерогенного катализа, раскраска животных и растений. Формирование различных пространственно-временных структур происходит в результате самоорганизации в сложных многокомпонентных нелинейных системах. Основная идея самоорганизации заключается в том, что в неравновесных условиях сложная система качественно изменяет свое макроскопическое поведение за счёт самопроизвольного упорядочивания составляющих её простых элементов [1, 2]. Изучение явлений самоорганизации имеет большое значение как с фундаментальной, так и с практической точки зрения. В системах самой различной природы могут возникать похожие устойчивые структуры. Следовательно, выявление общих принципов самоорганизации и структурообразования является ключевым в понимании основных механизмов физико-химических, биологических, социальных процессов и закономерностей их развития. С практической точки зрения, самоорганизация в наносистемах позволяет создавать наноструктуры с различной морфологией и формой, и как следствие, с различными свойствами.

Изучению устойчивых структур, возникающих в неравновесных открытых системах (диссипативных системах), посвящено большое число работ. Основы общей теории диссипативных структур сформулировал А. Тьюринг в 1952 г. [3], в этой работе он показал, что в гомогенной неперемешиваемой реакционной системе типа реакция-диффузия при определённых условиях может установиться периодическое в пространстве и стационарное во времени распределение концентраций. Экспериментально структуры Тьюринга были обна-

ружены в реакции Белоусова-Жаботинского и в реакции хлорит-иодид-малоновая кислота (ХИМ). Структуры Тьюринга представляют интерес не только для изучения кинетики химических реакций, аналогичные структуры возникают в биологии. На основе работ Тьюринга был разработан целый класс моделей реакционно-диффузионного типа. Классической моделью морфогенеза является реакционно-диффузионная модель активаторно-ингибиторного типа Гирера-Майнхардта [4, 5]. В этой модели клетки развивающегося организма могут продуцировать два морфогена: активатор и ингибитор, способные диффундировать в другие клетки. Разная скорость диффузии активаторов и ингибиторов приводит к неустойчивости и формированию пространственных структур. Математические модели генетического триггера Жакоба и Моно, Д.С. Чер-навского [6], описывающие процесс дифференциации клеток, основаны на ак-тиваторно-ингибиторном механизме. Основной характеристикой этих моделей является тригтерность - возможность переключения системы из одного состояния в другое, переключение происходит вследствие синтеза активных и неактивных ферментов. Дж. Марри предложил модель формирования структур на шкурах животных, основанную на активаторно-ингибиторном механизме [7], кроме того, Дж. Марри сделан большой обзор реакционно-диффузионных систем, использующихся для изучения нелинейных биологических процессов: возникновения биологических осцилляций, однородных колебаний и пространственных структур [8].

Большой вклад в исследование проблем самоорганизации внесли Г. Хакен, И. Пригожин [9], Г. Николис, A.M. Жаботинский, Б.П. Белоусов, Д.А. Янг, В.К. Ванаг и др. Существует несколько подходов к изучению самоорганизации сложных систем различной природы: синергетическая модель параметров порядка и принципа подчинения Г. Хакена, теория диссипативных структур И. Пригожина, концепция эволюции органических молекул М. Эйге-на, концепция эволюции открытых каталитических систем А.П. Руденко, модели формирования и эволюции нестационарных структур в режимах с обостре-

5

нием A.A. Самарского и С.П. Курдюмова и др.

Существенную роль в исследовании явлений самоорганизации играет теория нелинейных колебаний и волн, основоположниками которой являются Л.И. Мандельштам, A.A. Андронов, A.A. Витте, С.Э. Хайкин и др. [10, 11]. В рамках этой теории изучаются сложные, нерегулярные колебательные и волновые режимы, возникающие в открытых нелинейных динамических системах: автоколебания, бифуркации, стохастические колебания, хаос. Наиболее интересным и важным направлением теории нелинейных колебаний является исследование формирования и динамики автоколебаний и автоструктур. Термин «автоколебания» введён A.A. Андроновым и обозначает незатухающие устойчивые колебания в диссипативной динамической системе с нелинейной обратной связью, поддерживающиеся за счёт энергии постоянного внешнего воздействия, на фазовой плоскости автоколебаниям соответствует устойчивый предельный цикл. Автоструктуры определены в работе [12] A.B. Гапонова-Грехова и М.И. Рабиновича как пространственные образования, устойчиво существующие в диссипативных неравновесных системах и не зависящие от граничных и начальных условий, на фазовой плоскости автоструктурам соответствует устойчивый фокус.

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

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

стью определяется в терминах локальных зависимостей. [...] Пространство представлено равномерной сеткой, каждая ячейка которой, или клетка, содержит несколько битов данных; время изменяется дискретными шагами, а законы мира выражаются единственным набором правил, по которым любая клетка на каждом шаге вычисляет своё новое состояние по состояниям её близких соседей. Таким образом, законы системы являются локальными и повсюду одинаковыми".

Понятие клеточных автоматов впервые ввел фон Нейман в 1940-е годы XX века на основе предложения С. Улама для построения модели самовоспроизводящихся структур [15]. В это же время Н. Винер и А. Розенблют разработали клеточно-автоматную модель возбудимой среды для описания проведения импульсов в сердечной мышце [16]. Работа фон Неймана по самовоспроизводящимся автоматам была завершена и опубликована А. Бёрксом в книге «Essays on Cellular Automata» в 1966 году. Независимо от фон Неймана в 1969 году немецким инженером К. Цузе были придуманы "вычисляющие пространства" - клеточные автоматы, они были определены как универсальная вычислительная среда для построения алгоритмов, эквивалентная по своим выразительным возможностям машине Тьюринга [17]. Большую популярность клеточным автоматам принесла игра "Жизнь" Дж. Конвея, позволяющая с помощью простых правил переходов воспроизводить макроскопическое поведение популяций: зарождение, развитие и гибель колоний живых организмов [18].

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

7

Н. Маршлуса [14], сети транспьютеров, систолические системы, клеточные процессоры, параллельные сумматоры, умножители, декодеры и распознаватели сигналов.

Расширение сферы применения ЭВМ в СССР привело к появлению ряда работ по исследованию производительности существующих многопроцессорных вычислителей и поиска новых архитектур с улучшенными показателями. Проблемам создания и развития многопроцессорных вычислительных систем посвящены работы известных советских учёных: В.З. Аладьевым [19], В.М. Глушкова, Э.В. Евреинова, В.В. Игнатущенко, A.B. Каляева, Ю.Г. Косарева, И.В. Прангишвили и многих других. Существующие вычислительные системы с жёсткой архитектурой ориентированы на решение определённых задач и малоэффективны для решения задач другого класса. Тогда как использование многопроцессорных систем с программируемой структурой, реализованных на основе однородных сред, позволяет создать универсальные устройства, предназначенные для эффективного решения задач различных классов [20 - 22]. Однородные вычислительные среды представляют собой совокупность элементарных вычислителей (однородных структур), объединённых друг с другом регулярными связями. Однородными структурами (автоматами с программируемой структурой) называются структуры, состоящие их однотипных функциональных ячеек, соединённых одинаковым образом с соседними [23]. Функциональные ячейки могут быть запрограммированы на выполнение функции, необходимой для решения конкретной задачи, кроме того с помощью задания связей между ячейками и направленности передачи сигнала может быть реализована любая функциональная схема. Таким образом, для решения конкретной задачи производится настройка однородной среды путём определения функции, реализуемой функциональной ячейкой, и логических связей между ячейками. Благодаря возможности представления решаемой задачи в виде структурной схемы и реализации набора операций, характерных для данной задачи, однородные среды позволяют достичь высокой эффективности при выполнении широкого

8

класса задач. Кроме того, идентичность ячеек и однородность связей делает возможным наращивание вычислительной мощности и увеличение производительности системы [24].

В это же время велись теоретические исследования свойств клеточных автоматов. С. Вольфрам предложил классификацию клеточных автоматов по поведенческим признакам [25]. Он выделил 4 класса в зависимости от устойчивого состояния, к которому эволюционирует клеточный автомат: 1) однородное глобальное состояние, соответствует устойчивому фокусу на фазовой плоскости, 2) регулярные, устойчивые или периодические во времени структуры (предельный цикл), 3) непериодические структуры или хаотическое поведение, на фазовой плоскости соответствует предельным циклам с различным периодом, в том числе и равным бесконечности, 4) сложные структуры, распространяющиеся по пространству и развивающиеся во времени, такие клеточные автоматы способны моделировать динамику сложных систем (complex system).

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

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

тах многих российских и зарубежных авторов. С помощью синхронных клеточных автоматов промоделированы процессы разделения фаз [14], эвакуация людей из горящего здания [27], движение автотранспорта [28], гидродинамические и газодинамические течения [29-31]. Асинхронные вероятностные клеточные автоматы позволяют моделировать такие физико-химические процессы как диффузия [32], диффузия с агрегацией [33], реакционно-диффузионные системы [34-37], кумулятивный синтез [38], распространение фронта огня [39].

С помощью различных клеточн