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

• Автор: Калгин, Константин Викторович
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2012
• Место защиты: Новосибирск
• Количество страниц: 82 с. : ил.

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

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

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

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

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

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

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

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

Глава 2. Параллельные алгоритмы исполнения клеточно-автоматных моделей на вычислителях с различной архитектурой
2.1. Существующие параллельне алгоритмы
2.2. Новый алгоритм К для моделирования на параллельных вычислителях
2.3. Архитектуры параллельных вычислителей
2.4. Результаты тестирования параллельных алгоритмов на различных вычислителях
2.5. Заключение
Глава 3. Язык описания клеточно-автоматных моделей и его транслятор
3.1. Язык описания клеточно-автоматных моделей
3.2. Транслятор

3.3. Заключение
Заключение
Литература
Приложение А. Грамматика языка CACHE
Приложение Б. Описание асинхронной клеточно-автоматной модели на языке CACHE
Приложение В. Публикации автора

Введение
Клеточный автомат (КА) был предложен фон-Нейманом в середине прошлого века [1]. На основе этой модели подтверждалась мысль о том, что человек может создать устройство, обладающее присущими ему самому свойствами, в частности, возможностью воспроизводить себе подобного. Основные свойства клеточного автомата формулируются в следующем виде [2]: дискретность пространства, времени и состояний; однородность (все клетки организованы в регулярную пространственную структуру); синхронный режим изменения состояний; пространственная локальность; временная локальность.
Первое время клеточный автомат оставался объектом для игры ума. Сначала эта игра происходила на бумаге, затем она была перенесена на компьютер. Самым известным клеточным автоматом была и остается “Игра Жизнь” [3]. Интерес к этому клеточному автомату, как и вообще ко всем клеточным автоматам, постепенно перерос из игрового в научный. Когда начала бурно развиваться микроэлектроника (70-е годы) и появилась потребность в быстродействующих электронных схемах на многих элементарных автоматах, действующих параллельно, то клеточный автомат приобрёл важный практический смысл. Заложенные в его идее принципы параллельности и близкодей-ствия межклеточных взаимодействий как нельзя лучше соответствуют требованиям технологии больших интегральных схем.
Следующий всплеск интереса к клеточным автоматам был связан уже не с построением параллельных устройств, а с построением новых моделей вычислений [4, 5]. Это произошло в середине 80-х годов, когда были предложены клеточные автоматы, эволюция которых моделирует процесс диффузии [6-8], разделения фаз [2, 7], реакционно-диффузионные процессы [9-11], знаменитую реакцию Белоусова-Жаботинского [12], образование диссипативных

1. после изменения состояния любой граничной клетки необходимо мгновенно обновить это состояние в соседнем домене;
2. количество передач новых состояний на одной итерации имеет порядок yJDomk и они равномерно по ней разнесены;
3. передача сообщений по сети занимает большое время (на два-три порядка больше, чем время вычисления функции, реализующей локальный оператор перехода);
4. необходимо сохранять равноправие всех клеток, то есть вероятность применения 0 к некоторой клетке на некотором шаге должна быть равна вероятности применения 0 к любой другой клетке на любом другом шаге.
Таким образом, трудности при параллельном исполнении АКА возникают в момент применения оператора 0 к граничной клетке. В этот момент у процесса (потока) есть три варианта поведения:
1. процесс (поток) ждёт и ничего не делает пока локальное время всех соседних процессов (потоков) меньше его локального времени;
2. процесс (поток) не ждёт никакой другой процесс (поток) и применяет оператор 0 сразу же;
3. процесс (поток) принимает решение динамически, во время исполнения, ждать или не ждать соседние процессы (потоки) в зависимости от того, как спланированы их ближайшие будущие применения оператора 0.
На этих трёх вариантах поведения основаны три алгоритма параллельного исполнения [16, 17, 27]. Будем говорить, что эти алгоритмы сохраняют асинхро-низм, поскольку они не нарушают независимость выбора клеток на каждом шаге от чего бы то ни было. Алгоритмы [16, 17, 27] моделируют эволюцию КА с асинхронным режимом. Будем говорить, что алгоритмы, например [18, 19],