Эффективная параллельная реализация асинхронных клеточно-автоматных алгоритмов Калгин Константин ИВМиМГ СО РАН konstantin.kalgin@gmail.com. - презентация

1 Эффективная параллельная реализация асинхронных клеточно-автоматных алгоритмов Калгин Константин ИВМиМГ СО РАН

2 Применение А синхронных К леточных А втоматов Химические и Кинетические процессы в наносистемах эпитаксиальный рост кристаллов каталитические реакции намагничивание материала Поведение толпы во время паники Возникновение автомобильных пробок … и др.

3 Цель работы Разработать и Реализовать параллельный алгоритм функционирования асинхронных клеточных автоматов + исследовать эффективность распараллеливания

4 Клеточный автомат Параллельный алгоритм (СКА) Вероятностные свойства АКА Параллельный алгоритм (АКА) Оценка эффективности Результаты тестирования

5 Клеточный автомат Клеточный автомат – множество клеток Клетка – конечный автомат: + множество состояний + функция перехода + аргументы – состояния соседних клеток Различные шаблоны соседства

6 Итерация Синхронный режим Асинхронный режим Одновременное срабатывание всех клеток Разбивается на шаги Шаг – срабатывание одной случайной клетки Количество шагов = = количество клеток Клеточный Автомат «Игра Жизнь»

7 Параллельный алгоритм (СКА)

8 Проблемы распараллеливания (АКА) I.Каждое срабатывание граничной клетки требует обновления старого состояния в соседнем процессоре II.Время передачи состояния много больше времени срабатывания III.Во время передачи состояния необходимо исключить граничные срабатывания

9 Клеточный автомат Параллельный алгоритм (СКА) Вероятностные свойства АКА Параллельный алгоритм (АКА) Оценка эффективности Результаты тестирования

10 Свойства Асинхронного КА

11

12 Разбиение – набор множеств I и L k m k

13 Свойства Асинхронного КА 1. Два различных порядка срабатывания с равными разбиениями являются эквивалентными. 2. Для исполнения итерации достаточно знать разбиение, но не полный порядок. 3. Параметры разбиения формируются с помощью случайных чисел биномиального, экспоненциального и равномерного распределения.

14 Параллельный алгоритм (АКА) 1.Строится разбиение клеточной области на домены 2.Каждая итерация разбивается на этапы: 1.В каждом домене формируются параметры разбиения порядка (L, I ). 2.Соседние процессоры обмениваются граничными порядками L 3.В каждом домене запускается соответствующая часть итерации. На каждом граничном шаге: 1. получение необходимых состояний ( от соседей ) 2. срабатывание 3. передача нового состояния ( соседям ) k k m k

15 Клеточный автомат Параллельный алгоритм (СКА) Вероятностные свойства АКА Параллельный алгоритм (АКА) Оценка эффективности Результаты тестирования

16 Оценка эффективности Область : 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

17 Модель Изинга Модель Изинга – – модель статистической физики намагничивания материала Состояния клетки – { +1, -1 } – – ориентирование спина электрона Вероятность смены спина электрона: P = exp( – E / kT )

18 Результаты тестирования КА : модель Изинга Область : M = 32*1024 N = 2*1024

19 Заключение Параллельный алгоритм (АКА) – разработан – реализован Проведены – теоретическая оценка – тестирование Тестирование показало высокую эффективность реализации