Мелкозернистый параллелизм клеточно-автоматных моделей пространственной динамики Лекция 4 Руководитель: д.т.н., проф., Бандман О.Л. Лектор: к.ф.-м.н., - презентация

1 Мелкозернистый параллелизм клеточно-автоматных моделей пространственной динамики Лекция 4 Руководитель: д.т.н., проф., Бандман О.Л. Лектор: к.ф.-м.н., Нечаева О. И. Ассистент: Бессмельцев М.В.

2 Композиция мелкозернистых алгоритмов Зачем нужна композиция? Нет формальных процедур построения КА-моделей по описаниям процессов Зато есть много уже придуманных КА-моделей, из которых можно строить (собирать) модель сложных процессов Главная проблема: Как соединять совместные влияния факторов, выраженных в разных алфавитах ? булев алфавит вещественный алфавит = ?????

3 Примеры КА-моделей и их композиций Реакция Образование диссипативных структур Кристаллизация Конвекция Адсорбция Фазовые переходы Нагрев ДиффузияПоток жидкости Разделение фаз Распространение фронта

4 Операции на клеточных массивах А B = {0,1} – булев алфавит B = A B M B A R = [0,1] – вещественный алфавит R = A R M R Операции над клеточными массивами: Унарные осреднение булева дискретизация Бинарные сложение вычитание умножение

5 Осреднение : Bool Real Глобальный оператор: Av( B ) = R Локальный оператор: Av(m): (v, m) K Av (m) (u, m), где m M = {(i,j): i=1,…,N 1, j=1,…,N 2 }, v {0,1}, u [0,1], область осреднения T Av i j

6 Булева дискретизация : Real Bool Глобальный оператор: Dis( R ) = B Локальный оператор: Dis(m): (u, m) K Av (m) (v, m), где m M = {(i,j): i=1,…,N 1, j=1,…,N 2 }, v {0,1}, u [0,1],

7 Точность унарных операций Av( B ) = R & Dis( R ) = B Av( Dis( R ) ) R Dis( Av( B ) ) B

8 Точность унарных операций

9 u(j)=sin( /N)j v(j)=Dis(u(j)) u(j)= Av(Dis(u(j))) N Error Радиус осреднения: r Av = N N х N i j

10 Бинарные операции над клеточными массивами Для композиции клеточных автоматов может потребоваться вычисление функций от клеточных массивов. Как правило такие функции действуют на действительных алфавитах. Стандартные операции: { +, -, } 1 2 Av( 1 ) Av( 2 ) (i,j): v(i,j) u(i, j) u(i,j) v(i,j)

11 Методы композиции мелкозернистых алгоритмов Композиция Последовательная Параллельная Тривиальная Нетривиальная Глобальная Локальная Двунаправленная Однонаправленная

12 Нетривиальная глобальная суперпозиция t=0 t: ( ) = Dis( 3 (Av( 2 ( 1 ( ))))) Распространение водорослей в водоеме: 1) агломерация разделение фаз А –булев 2) диффузия синхронно-блочная 3) размножение логистическая функция F(u) 3 : (u,(i,j)) (u(i,j)) u= 0.5u(1-u) u

13 Локальная суперпозиция асинхронных КА = Loc ( 1,…, n ) k = A,M, k Один цикл : 1 ( rand i,j), 2 ( rand i,j),…, n ( rand i,j) 1 ( 2 (… n (i,j))) 1 ( rand ij): СO + = CO 2 ( rand ij): O = 2O 3 ( rand ij): CO + = CO ( rand ij): CO + = + CO CO O CO p2p2 p3p3 CO O CO адсорбция СО адсорбция О 2 реакция диффузия Окисление CO на платиновом катализаторе: p1p1

14 Устойчивые глобальные состояния от отношения парциальных давлений p 1 /p 2 O 2 (p 2 ) CO (p 1 ) Процесс окисления CO на платиновом катализаторе: -CO - O - Pt

15 Параллельная композиция = PGl ( 1, 2 ), A 1 A 2, 1 2, 1 2, M 1 ={(i,j) 1 }, M 2 ={(i,j) 2 }, M 1 M 2 Условия корректности параллельного функционирования : Каждый локальный оператор меняет состояния в своем клеточном массиве, используя в функциях переходов переменные из любого База T k (i,j) k M k, контекст T k (i,j) k (M 1 M 2 ) k=1,2

16 Случаи параллельных композиций 1 2 k : S(i,j) k S k (i,j) S k (i,j) S 1 (i,j) 1 S 1 (i,j) 1 2 S 2 (i,j) 2 S 2 (i,j) 1 2 Двунаправленная Однонаправленная S 1 (i,j) 1 S 2 (i,j) S 2 (i,j) 1 2 Тривиальная S 1 (i,j) 1 S 2 (i,j) 2 S 2 (i,j) 1 3 ( ) = 1 ( 1 ) 2 ( 2 )

17 Тривиальная параллельная композиция (сравнение дискретной и непрерывной модели) b) u t = 0,2(u xx + u yy ) + (u-0.1)(u-0.5)(u-0.9) - уравнение Schlőgla a) 1 : ( v,(i,j) 1 ) S(I,j) v,(i,j) 1 ) 1, if =12 or >13 0, if =13 or

18 Солитон t= 0: … t= 6: … t=30: … t=36: … d=12, p=6 d=7,p=2 1 : A 1 ={0,1}, M 1 = {0,1,2,…,i,..,N} 1 : (u,i) {(u -5,i-5),…(u 5,i+5)} (u,i) 1, если u i-5 +,…u i + u i+5 =0(mod2), но 0 0 в остальных случаях u= Режим упорядоченный асинхронный 2 : A 2 =[0,1], M 2 = {0,1,2,..,i,…,N} 2 : (v,i) {(u -r,i-r),…(u r,i+r) ( 1,m)} (v,i) 3 : (t,m) (t,m), u = r -r u i 1 2r+1 Параллельная композиция ( Однонаправленная локальная ) 1, if t(mod6)=0 0, в иных случаях t=

19 Возникновение локализованных самоорганизующихся структур (газовый разряд) ( двунаправленная параллельная глобальная композиция) Два вещества u и v в нейтральном газе, Каждое вещество 1) диффундирует в газ - булев КА диффузии 2) вступает в реакцию - u= F U (u,v), v= F V (u,v) t-ая итерация : u, v u1 = RU ( u v ) v1 = RV ( u v ) Real u2 = Dis( u ), v2 = Dis( v1 ) Bool u3 = DU ( u2 ) v3 = DV ( v2 ) Bool u4 = Av( u3 )+ u1 v4 = Av( v3 ) + v1 Real (t+1)-ая итерация u, v Real

20 Возникновение локализованных самоорганизующихся структур (газовый разряд) ( двунаправленная локальная композиция) RU : (u, (i,j)) (u,(i,j)) u=(v-u) RV : (v, (i,j)) (v,(i,j)) v=1.4v+v u DV – блочно-синхронная диффузия Модельные С v =0.15 С u =1.5 h=1 = 1 Физ. величины d v = см 2.сек, d u = см 2.сек, = сек h =0.01см v (0) =0.8, u (0) =0.2 u(x,t) t U(I,j)

21 Экологические катастрофы Intel Winter School 2008

22 Моделирование воды Intel Winter School 2008

23 Моделирование воды Дан массив из MxN клеток. В каждой клетке может присутствовать от 0 до 4 частиц c единичной скоростью в одном из 4 направлений Правила столкновения частиц: Правила столкновения частиц: (импульс и масса сохраняются)

24 Модель кластеризации пятен нефти Intel Winter School 2008

25 Модель кластеризации пятен нефти В течение итерационного процесса состояние каждой клетки G ij изменяется по правилу:

26 Модель горения Intel Winter School 2008

27 Модель горения Численное решение уравнения теплопроводности c ненулевой правой частью на квадратной сетке: Начальное распределение огня: в одном или нескольких узлах сетки u ij =1 (имитируя поджог), а в остальных точках u ij =0.

28 Моделирование Модель идеальной жидкости на 2D квадратном клеточном массиве Модель распространения фронта огня Модель образования пятен нефти на поверхности воды Модель текущей жидкости Модель нефтяных пятен Модель горения Intel Winter School 2008

29 Сведение трех моделей На каждой макроитерации: –Фаза распространения огня (на нефти) –Фаза движения воды –Фаза сдвига нефти по направлению движения воды –Фаза кластеризации пятен нефти Количество итераций на каждой фазе может регулироваться

30 Подробнее: фаза сдвига нефти Случайным образом выбирается клетка G ij «нефтяного» массива. Выбирается тот сосед G ij, на которого указывает вектор скорости частицы клетки W ij «водного» массива. Состоянию этого соседа присваивается состояние клетки G ij. Если частиц несколько, та же процедура применяется к каждой из них. За фазу сдвига нефти выбирается столько клеток «нефтяного» массива, каков размер массива.

31 Содержание курса Первая часть Экскурс в историю развития КА-моделирования Основные понятия и формальная модель клеточного автомата Параллельная реализация клеточно-автоматных алгоритмов Вторая часть Классификация клеточных автоматов –по поведенческим свойствам, –по свойствам процессов, которые они моделируют, –по способам построения КА моделей. Композиция КА-моделей с введением операций на множестве клеточных автоматов. Третья часть Рассмотрение конкретных КА-моделей в гидродинамике, поверхностной химии, биологии, кинетике и синтезе нано систем, и др. Вычислительные свойства клеточных автоматов