Клеточно-автоматное моделирование пространственно распределенных процессов на суперкомпьютерах О.Л.Бандман Институт вычислительной математики и математической геофизики СОРАН Летняя школа 2012

Развитие методов компьютерного моделирования Классическая математика мат. физика Вычислительная мат-ка Параллельные выч. методы Клеточный автомат Мелкозернистый параллелизм complex systems компьютер комп. системы ?????? ФИЗИКАФИЗИКА химия биология экология... внутренний параллелизм нелинейность самоорганизация эволюционизм К л а с с и к аМ о д е р н Клеточный автомат t

(i,j)= (F 1,…,F h )- локальный оператор композиция функций переходов = A, X,, ρ A={0,1} {0,1,...,n} {Symbols} X={(i,j):i,j=0,…,N} T(i,j) = {(i,j) 0, (i-1,j) 1, (i,j+1) 2, (i+1,j) 3, (i,j-1) 4 } – шаблон V(T(i,j))={v 0,v 1,v 2,v 3,v 4 }- локальная конфигурация j i v 0 (t+1) = F(v 0,v 1,v 2,v 3,v 4 ) – функция переходов база контекст

Режимы функционирования Синхронный режим : 1) вычисляются v(i,j,t+1)= (i,j,t) (i,j) X 2) v(i,j,t) заменяются на v(i,j,t+1) (i,j) X Клеточный массив: Глобальное состояние Применение (i,j) ко всем (i,j) X : Ω(t) Ω(t+1): t-ая итерация Асинхронный режим: τ = 1,…, |Ω| 1) выбирается случайно (i,j) X, 2) вычисляется v(i,j,t+1)= (i,j,t), 3) v(i,j,t) заменяются на v(i,jt+1).

КА «разделение фаз» A={0,1} X={(i,j): i,j=0,…,199} Синхронный режим 1,if u0u0 u1u1 u2u2 u3u3 u4u4 u5u5 u6u6 u7u7 u8u8 u0u0 1, if u k >5 or u k =4 0, if u k

Современный взгдяд на КА CA are mathematical idealization of physical systems, in which time and space are discrete and physical quantities take a finite set of discrete values S Wolfram.Stat. mechanics of CA Review of Modern Physics 55 N3 (1983) КА – это математическая идеализация физической системы, в которой время и пространство дискретны, а физические величины принимают конечное множество значений

КА-моделирование пространственной динамики Использовапние КА для моделирования пространственных процессов вызвано следующими факторами Технологический: 1) специализированные процессоры 2) суперкомпьютеры, кластеры, Математический: 1) Нужда в методах моделирования нелинейных процессов (химия, биология, социология…) часто нет других моделей 2) Необходимость параллельных реализаций в связи с увеличением размеров задач 3) Трудности в преодолении сложности программирования Экономический: Переоценка ценностей вычислительной работы аппаратура дешевеет, программироваие дорожает

Классы КА-моделей (мелкозернистые алгоритмы) булев целочисленный вещественныйсимвольный Клеточный автомат синхронный асинхронный детерминированный вероятностный обучаемый

Классификация КА-моделей пространственной динамики Физико-химические процессы реакция-диффузия Физические явления на основе КА-гидродинамики Процессы самоорганизации - формирование устойчивых структур - взаимодействия «хищник-жертва» - агрегация, ограниченная диффузией - реакция Белоусова-Жаботинского - простая модель FHP - потоки, струи, волны

Процессы «реакция+диффузия»

Локальный оператор (i,j) = R( Agr Diff) ) Наивная диффузия Diff : Обмен состояниями со случайно выбранным соседом, если он не Асинхронный режим Агрегация Agr : p Прилипание к с вероятностью p Агрегация с ограниченной диффузией ( рост кораллов, электролиз, образование снега) Локальный оператор (i,j) = R( Agr Diff) ) Наивная диффузия Diff : Обмен состояниями со случайно выбранным соседом, если он не A={,, }, X={ (i,j) }, (0)={N = 0.1|X|, N = 0.9|X|, u(200,300,)=u(400,300)= }, Асинхронный режим Агрегация Agr : p Прилипание к с вероятностью p p |X|=

Агрегация, ограниченная диффузией (моделирование К.В. Калгина)

КА, моделирующий реакцию Белоусова-Жаботинского Малоновая кистота + окисленный бромат + соль церия = химический осциллятор =,A,X A={I,2,3….,255}, M={i,j}. u3u3 u1u1 u7u7 u uuu u0u0 (i,j) u2u2 Sum= u, a = число u: u=2,…,254 b = число u: u=255 c = число u ; u=1 T(i,j) ǜ {2,…,254}, f 1 = a/2+b/3+1, f 2 = Sum/(9-c) + Z (255,(i,j)) (1,(i,j)) (1,u 1,…,u 8 )(i,j) (f 1 (u 1,…,u 8 ),(i,j)) (ǜ,u 1,…,u 8 )(i,j) (f 2 (u 1,…,u 8 ),(i,j)) : Z=

Процесс реакции Белоусова-Жаботинского Спирали Z=70

КА – гидродинамика Lattice-Gas Hydrodynamics ( решеточный газ )

Гексогональная Lattice-Gas модель вязкой жидкости FHP u = (s 7, s 6, s 5, s 4, s 3, s 2, s 1 ) S k {0,1} U.Frish, B Hasslacher, Y.Pomeau в 1986 совершили открытие: Структура клеточного массива гексагональная В каждой клетке не более 6 движущихся частиц Масса частицы m=1 Скорость частицы u i =1 в одном из 6 направлений В клетке не может быть более одной частицы, движущейся в одном направлении M={(i,j)} A={(s k: ):k=1….7 Режим синхронный = 2 ( 1 ) 2D Поток может быть представлен абстрактными частицами движущимися с единичной скоростью в 6 направлениях.

столкновение Условия cохранения масс и импульсов соблюдаются локально 1 : u(i,j) u(i,j) u= V s ĸ (i k.j k ), k=1,…,6 Локальные операторы КА FHP (Gas-Lattice) Одна частица покоя с массой m=1 сдвиг Условия сохранения соблюдаются глобально 2 : u(i,j) S(i,j) u(i,j)

FHP – модель процесс эволюции t сдвиг t+1/2 столкновение t+1 (t) (t+1)

Осредненный вектор скорости 30 v k Av (i,j): u = v k 1 |Av|

Результат применения FHP- модели From : Rothman D.H., Zalesky S. Lattice-Gas Cellular Automata Simple Models of Complex Hydrodynamics, London, 1997

Целочисленная Lattice-Gas модель FHP-MP Ю.Г.Медведев

КА-модели процессов самоорганизации

Активаторно-ингибиторная КА-модель D.Younga активатор ингибитор r R u r R 1984, David Young A local activator-inhibitor model of vertebrate skin patterns Math. Biosciences, v Условия образования устойчивых структур: 1) Ингибитор должен оказывать влияние на пространстве с большим радиусом действия чем активатор ( D u

Формирование устойчивых структур КА с взвешенными шаблонами u(t+1) = Синхронный КA Асинхронный КA W=

Хищник - Жертва v = {(v, (i,j )}, V (I,j) = T v (i,j) u = {(u,(i,j) }, U (i,j) = T u( i,j) Хищник Если V>U, то v(i,j)=0 (p=(V-U)/V ); ( голодный хищник умирает) Если U>V, то v=1 (p=0.5 v (1- v )) (сытый хищник размножается) тактов диффузии (i,j) Жертва (i,j) Если V>U, то u=0 ( хищник съедает все) Если U>V, то u=1 (p=0.5 u-v (1- u-v )) (оставшаяся жертва размножается) + 1 такт диффузии

Двунаправленная параллельная композиция v = A v, X v, v u = A u, X u, u V U F(u,v)

Эволюция КА : хищник (V) -- жертва (U) ρ v (0)= 0.2, ρ u (0)= 0.3, полоса ρ v (0)= 0.8

Эволюция КА : хищник (V) -- жертва (U) ρ v (0)= 0.2, ρ u (0)= 0.6, в центре ρ v (0)= 0.8

Реализация КА-системы на многоядерном компьютере Общая память n Thread 1: 1 1 Thread 2: 2 2 Thread 3: 3 3 Thread n: n n Параллельная программа КА-1 КА-2 КА-3 КА-n t : кортексты базы

Number of threads time speedup time speedup time speedup CA, Dv/Du= CA, Dv/Du= Dom. Decomp Prey –predatory CA system Parallel multicore implementation time = computation time of 500 iterations (sec) Speedup = time(1)/time(n)

Пожалуйста, задавайте вопросы!

u0u0 u1u1 u2u2 u3u3 u4u4 u5u5 u6u6 u7u7 u8u8 u 0 (t+1) Классический КА этап J. von Neumann CA (Stanislav Ulam 1946) КА – это регулярная структура двоичных конечных автоматов с одинаковыми правилами переходов, выраженных в виде булевых функций от состояний соседних автоматов 2.Игра «жизнь» John Convey (1970) u 0 (t+1)= 1, if (u 0 =0 & u k =3) V (u 0 =1 & (u k 3) 0, в остальных случаях Локальный оператор Функция перехода

Три этапа развития идей о КА 1.Классический КА - проблема самовоспроизведения, интеллектуальные игры (1956 – 1980) 2.Однородные структуры - параллельные универсальные перестраиваемые схемы для микроэлектроники (1970 – 2000) 3.КА-модели пространственной динамики – гидродинамика, поверхностная химия, кристаллизация, кинетика нано-систем, биология, социальные процессы (1985