Эффективная параллельная реализация асинхронных клеточно-автоматных алгоритмов Калгин Константин ИВМиМГ СО РАН
Применение А синхронных К леточных А втоматов Химические и Кинетические процессы в наносистемах эпитаксиальный рост кристаллов каталитические реакции намагничивание материала Поведение толпы во время паники Возникновение автомобильных пробок … и др.
Цель работы Разработать и Реализовать параллельный алгоритм функционирования асинхронных клеточных автоматов + исследовать эффективность распараллеливания
Клеточный автомат Параллельный алгоритм (СКА) Вероятностные свойства АКА Параллельный алгоритм (АКА) Оценка эффективности Результаты тестирования
Клеточный автомат Клеточный автомат – множество клеток Клетка – конечный автомат: + множество состояний + функция перехода + аргументы – состояния соседних клеток Различные шаблоны соседства
Итерация Синхронный режим Асинхронный режим Одновременное срабатывание всех клеток Разбивается на шаги Шаг – срабатывание одной случайной клетки Количество шагов = = количество клеток Клеточный Автомат «Игра Жизнь»
Параллельный алгоритм (СКА)
Проблемы распараллеливания (АКА) I.Каждое срабатывание граничной клетки требует обновления старого состояния в соседнем процессоре II.Время передачи состояния много больше времени срабатывания III.Во время передачи состояния необходимо исключить граничные срабатывания
Клеточный автомат Параллельный алгоритм (СКА) Вероятностные свойства АКА Параллельный алгоритм (АКА) Оценка эффективности Результаты тестирования
Свойства Асинхронного КА
Разбиение – набор множеств I и L k m k
Свойства Асинхронного КА 1. Два различных порядка срабатывания с равными разбиениями являются эквивалентными. 2. Для исполнения итерации достаточно знать разбиение, но не полный порядок. 3. Параметры разбиения формируются с помощью случайных чисел биномиального, экспоненциального и равномерного распределения.
Параллельный алгоритм (АКА) 1.Строится разбиение клеточной области на домены 2.Каждая итерация разбивается на этапы: 1.В каждом домене формируются параметры разбиения порядка (L, I ). 2.Соседние процессоры обмениваются граничными порядками L 3.В каждом домене запускается соответствующая часть итерации. На каждом граничном шаге: 1. получение необходимых состояний ( от соседей ) 2. срабатывание 3. передача нового состояния ( соседям ) k k m k
Клеточный автомат Параллельный алгоритм (СКА) Вероятностные свойства АКА Параллельный алгоритм (АКА) Оценка эффективности Результаты тестирования
Оценка эффективности Область : M x N клеток Декомпозиция области : вдоль одной размерности (N) Эффективность : E P = T 1 /(P*T P ) T 1 = T func *(M*N) T P = T func *(M*N/P) + 2*M*T send + Т coord Эффективность 75% достигается при размерах доменов 3000х3000
Модель Изинга Модель Изинга – – модель статистической физики намагничивания материала Состояния клетки – { +1, -1 } – – ориентирование спина электрона Вероятность смены спина электрона: P = exp( – E / kT )
Результаты тестирования КА : модель Изинга Область : M = 32*1024 N = 2*1024
Заключение Параллельный алгоритм (АКА) – разработан – реализован Проведены – теоретическая оценка – тестирование Тестирование показало высокую эффективность реализации