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

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

Зачем нужно моделирование?

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

Процесс моделирования

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

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

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

Классический КА 1 этап, гг. 1. J. von Neumann CA ( Stanislav Ulam ) КА – это регулярная структура двоичных конечных автоматов с одинаковыми правилами переходов, выраженных в виде булевых функций от состояний соседних автоматов 2.Игра «жизнь» u 0 (t+1)= 1, if (u 0 =0 ) & ( u k =3) 0, if(u 0 =1) & ( (u k 3)

1, if (u 0 =0) & ( u k =3) 0, if (u 0 =1) & ( u k 3) u(t+1) = t t+1 t+2 t Perpetuum mobile (часы) Игра жизнь

t 0 t 1 t 2 t 3 t 4 t 5 t 6 u(t+1) = (mod2) u k k=0,1,…9 Самовоспроизведение (фракталы) Игра жизнь

Турбина 1, if (u 0 =0) & ( u k =3) 0, if (u 0 =1) & ( u k =4 V u k =1) u(t+1) =

Однородные вычислительные структуры Этап 2 (1960 – 1990) Свойства структурной однородности и функциональной локальности стимулировали появление новых идей в проектировании архитектур вычислительных устройств в СБИС микроэлектронике Вычислительная среда - универсальные программируемые вычислительные структуры Tesselation automata - клеточные автоматы с функциональной неоднородностью Ассоциативные процессоры - структурно –однородные с глобальными связями Прообразы параллельных спецвычислителей ( массовая арифметика, обработка сигналов и изображений…

Обобщенная формальная модель : Алгоритм параллельных подстановок Замечательный пример: Параллельный сумматор многих чисел j i = =

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

Современный взгдяд на КА 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) 7 КА – это математическая идеализация физической системы, в которой время и пространство дискретны, а физические величины принимают конечное множество значений

КА «разделение фаз» A={0,1) M={(i,j): i,j=0,…,200} Synchronous mode of operation 8 1,if u0u0 u1u1 u2u2 u3u3 u4u4 u5u5 u6u6 u7u7 u8u8 u0u0 1, if u k >5 or u k =4 0, otherwise u= u t =0.2(u xx +u yy ) -0.2(u-0.1)(u-0.5)(u-0.9); Asynchronous mode of operation R Крит. d(0) = 0.5, T=400, d(T)=0.7 t итер = 0, 18сек Крит. D(0)= , T=220, d(T)=1 t итер = 0.19 сек

Рост островов на катализаторе

Два утверждения отцов-основателей Cellular automaton is an alternative (rather than approximation) to differential equations in modeling physics Tomas Toffolli - Physica, D10 (1984 ) Cellular automata despite their simple construction, have sufficient complexity to accomplish universal computing Wolfram, NKS,

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

Мелкозернистый параллелизм в задачах моделирования естественных процессов Формальные модели Методы Алгоритмы Технологии программирования Основные свойства мелкозернистых моделей Однородность (много одинаковых простых вычислительных элементов) Виртуальный параллелизм) Локальность взаимодействий Имитация процессов на микроуровне 12

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