Клеточно-автоматные модели диффузионного процесса Участники проекта: Кузнецов Дмитрий, Михайлов Александр, Спешилов Константин. Руководитель: Медведев Ю.Г.

План доклада 1.Булева синхронная модель 2.Булева асинхронная модель 3.Целочисленная асинхронная модель 4.Целочисленная синхронная модель 5.Сравнение синхронной и асинхронной моделей 6.Уравнение диффузии 7.Система диффузионной обработки изображений 8.Параллельная реализация алгоритмов диффузии

Синхронный булев КА Состояния клеток: 0, либо 1. Такт: –Вся область разбивается на блоки по 4 клетки –Клетки блока меняются состояниями равновероятно по или против часовой стрелки Итерация состоит из двух тактов: четного и нечетного. 2 способа обработки граничных клеток –Замыкание –Не обрабатываются

Асинхронный булев КА Состояния клеток: 0, либо 1. Микроитерация: –Случайным образом выбирается одна клетка области –Выбирается направление обмена (один из 4х соседей) –Выбранные две клетки меняются состояниями Одна итерация это N микроитераций, N количество клеток в автомате.

Асинхронный целочисленный КА Микроитерация: –Случайным образом выбирается одна клетка области –Выбирается направление обмена (один из 4х соседей) –Частицы в клетках делятся на две части в пропорции k : (1-k): активные пассивные –Выбранные две клетки меняются активными частями Одна итерация это N микроитераций, N количество клеток в автомате.

Синхронный целочисленный КА Такт: –Вся область разбивается на блоки по 4 клетки –Выделяется активная часть клеток, аналогично асинхронному автомату –Клетки блока меняются активными частями равновероятно по или против часовой стрелки Итерация состоит из двух тактов: четного и нечетного.

Сравнение синхронного и асинхронного КА Экспериментально было обнаружено, что для достаточно гладких исходных распределений скорость диффузии, представляемой синхронным и асинхронным автоматами одинакова при использовании одного коэффициента диффузии КА k, однако для этих автоматов различны линейные масштабы. Выявлен коэффициент пропорциональности между линейными масштабами: m = 1.16 Это означает, что если реализован один из КА (синхронный, либо асинхронный), можно получить распределение, которое дал бы второй КА.

Диффузия, описываемая ДУ Процесс беспорядочного блуждания частиц, который приводит к выравниванию концентрации вещества в пространстве, называется диффузией. В двумерном непрерывном случае при постоянном коэффициенте диффузии d процесс описывается уравнением Лапласа: u(x,y,t) концентрация вещества в точке с координатами x,y в момент времени t. Недостатки моделирования диффузии с помощью ДУ: –Использование вещественных чисел связано с потерей точности в вычислениях. –Для высокой точности результата нужно решать ДУ на достаточно подробных сетках, что требует много ресурсов и длительного времени вычисления

Система диффузионной обработки изображений

Москва неблокирующая Кол- во ядер Кол-во итераций Размер массива Вре мя Время нормирова нное УскорениеЭффе ктивн ость Размер массива, Мб, на один процессор Ширина полосы, клеток ,0551,01, ,0282,00, ,0143,90, ,0077,90, , ,40, , ,90, , ,80, , ,30, , ,70, , ,30, ,85938E-05938,70, ,92969E ,30, Размеры задачи – массив х250, 100 итераций

Параллельная реализация синхронных клеточных автоматов Метод – Domain decomposition Разбиение по процессам по одному измерению 2 метода измерения времени –Пропорциональный –Непропорциональный 2 метода реализации –Блокирующая(MPI_Send, MPI_Recv) –Неблокирующая(MPI_Isend, MPI_Irecv, MPI_Wait )

Использовавшиеся кластеры НКС-30Т Управляющий модуль - hp ProLiant DL380 G5 - 2 процессора Intel Quad-Core Xeon E5440, 2.83 ГГц, RAM 8 ГБайт Вычислительный блейд-сервер hp ProLiant BL2x220c ( 32 шт.) - 2 сервера по 2 процессора Intel Quad-Core Xeon Е5450, 3 ГГц, RAM 16 ГБайт всего 128 процессоров (512 ядер) пиковая производительность – 6.1 Тфлопс МВС-100К с пиковой производительностью 140,16 TFlops в настоящий момент является самым мощным суперкомпьютером, установленным в странах СНГ. В его состав входят 1460 вычислительных модуля, каждый из которых оснащён двумя четырёхядерными процессорами Intel Xeon, работающими на частоте 3 ГГц. Для объединения узлов кластера в единое решающее поле используется технология Infiniband.

Время обработки одной клетки на одной итерации 256 процессорами. Размеры задачи – массив х250, 100 итераций

Эффективность распараллеливания. Размеры задачи – массив х250, 100 итераций

Новосибирск блокирующая Кол- во ядер Кол-во итераций Размер массива Вре мя Время нормирова нное УскорениеЭффе ктивн ость Размер массива, Мб, на один процессор Ширина полосы, клеток ,61,01, ,351,90, ,6753,90, ,33757,70, ,17514,90, , ,70, , ,50, , ,90, , ,70, Размеры задачи – массив х250, 100 итераций

Москва блокирующая Кол- во ядер Кол-во итераци й Размер массив а Врем я Время нормирова нное Ускорени е Эффе ктивн ость Размер массива, Мб, на один процессор Ширина полосы, клеток ,41,01, ,22,01, ,64,01, ,38,01, , ,40, , ,70, , ,40, , ,80, , ,60, , ,10, , ,40, , ,50, , ,60, Размеры задачи – массив х250, 100 итераций

Новосибирск неблокирующая Кол- во ядер Кол-во итераций Размер массива ВремяВремя нормиро ванное УскорениеЭфф екти внос ть Размер массива, Мб, на один процессор Ширина полосы, клеток ,061,01, ,03151,90, ,016753,60, , ,40, , ,50, , ,20, , ,50, , ,30, , ,60, Размеры задачи – массив х250, 100 итераций

Москва неблокирующая Кол- во ядер Кол-во итераций Размер массива Вре мя Время нормирова нное УскорениеЭффе ктивн ость Размер массива, Мб, на один процессор Ширина полосы, клеток ,0551,01, ,0282,00, ,0143,90, ,0077,90, , ,40, , ,90, , ,80, , ,30, , ,70, , ,30, ,85938E-05938,70, ,92969E ,30, Размеры задачи – массив х250, 100 итераций