Мелкозернистый параллелизм клеточно-автоматных моделей пространственной динамики Лекция 3


The Presentation inside:

Slide 0

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


Slide 1

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


Slide 2

Классификация по режимам функционирования Синхронный Асинхронный Блочно-синхронный Упорядоченный асинхронный


Slide 3

Классификация по поведенческим свойствам Класс 1 предельная точка на фазовой плоскости, КА стремится к пространственно однородному устойчивому состоянию Класс 2 предельный цикл, КА стремится к устойчивому образу, или циклу Класс 3 хаотическое поведение, КА входит в «странный» аттрактор Класс 4 сложное поведение, универсальные вычисления, КА стремится к локализованным структурам, возможно движущимся ?(t+1) 1 2 3 4 Фазовая плоскость ?(t)


Slide 4

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


Slide 5

Классификация по построению: Класс 1 КА «разделение фаз» A={0,1) M={(i,j): i,j=0,…,200}


Slide 6

Классификация по построению: Класс 2 СO + ? = CO O2 + 2? = 2O CO + O = CO2+2O CO + ? = ? + CO адсорбция СО адсорбция О2 реакция диффузия Окисление CO на платиновом катализаторе: CO O O ? CO p2 p3 CO O CO ? p1


Slide 7

Классификация по построению: Класс 2 Процесс окисления CO на платиновом катализаторе: CO O Pt


Slide 8

Классификация по построению: Класс 3 Формирование устойчивого образа (процесс самоорганизаци) A={0,1) M={(i,j): I,j=0,…,200} ?(0)={(u, ij): u=1 if rand <0.5, u=0 otherwise} W = 1 a=0.2 1 1 1 1 1 1 0 0 0 0 0 0 0


Slide 9

Параллельная реализация КА-алгоритмов Общие сведения по параллельным архитектурам и средствам параллельного программирования Распараллеливание КА с разными режимами функционирования Реализация параллельных алгоритмов


Slide 10

Основные классы современных параллельных компьютеров Основной параметр классификации параллельных компьютеров – наличие общей (SMP) или распределенной памяти (MPP) Симметричные мультипроцессорные системы (SMP) Система состоит из нескольких однородных процессоров и массива общей памяти (обычно из нескольких независимых блоков). Все процессоры имеют доступ к любой точке памяти с одинаковой скоростью. Процессоры подключены к памяти либо с помощью общей шины (базовые 2-4 процессорные SMP-сервера), либо с помощью crossbar-коммутатора. Аппаратно поддерживается когерентность кэшей. В модели общей памяти параллельная программа представляет собой систему нитей (threads), взаимодействующих посредством общих переменных и примитивов синхронизации. Массивно-параллельные системы (MPP) Система состоит из однородных вычислительных узлов, включающих: один или несколько центральных процессоров, локальную память (прямой доступ к памяти других узлов невозможен), коммуникационный процессор или сетевой адаптер К системе могут быть добавлены специальные узлы ввода-вывода и управляющие узлы. Узлы связаны через некоторую коммуникационную среду (высокоскоростная сеть, коммутатор и т.п.) Кластерные системы являются более дешевым вариантом MPP В модели передачи сообщений параллельная программа представляет собой систему процессов, взаимодействующих посредством сообщений.


Slide 11

Характеристики производительности Ускорение – это отношение времени решения задачи на одном универсальном процессоре к времени решения той же задачи на системе из p таких же процессоров: Эффективность – это отношение ускорения к числу процессоров:


Slide 12

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


Slide 13

0 1 0 0 0 1 0 0 Противоречие ! ?= {(u,(i,j),(v(i,j+1)} ? {(v,(i,j),(u(i,j+1)} Пример некорректного поведения: A={0,1}, M={(i,j)}, синхронный режим j i 0 1 2 3 4 5 0 1 2 3 4 ?(2,2): S’(2,2)={(1,(2,2))(1(2,3))} ?(2,3): S’(2,3)={(0,(2,3))(1(2,4))} T(2,2) ? T(2,3) = (2,3) Вспомним условия корректности КА


Slide 14

Параллельная реализация корректных синхронных КА Распределенная память Общая память Последовательная машина


Slide 15

Параллельная реализация асинхронных КА Распределенная память Общая память Последовательная машина


Slide 16

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


Slide 17

Параллельная реализация блочно-синхронных КА Размер каждого блока больше или равен размера шаблона. Пусть b – количество клеток в блоке. Итерация состоит из b стадий. На каждой стадии выполняется синхронное применение оператора подстановки ко всем клеткам одного цвета. Поскольку на каждой стадии шаблоны не пересекаются, результат не зависит от порядка обработки блоков. Если машина с распределенной памятью: обмен границами происходит после каждой стадии.


Slide 18

Средства параллельного программирования MPI и OpenMP OpenMP - программный интерфейс (API) для программирования компьютеров с разделяемой памятью (SMP/NUMA). OpenMP можно использовать для программирования на языках Fortran и C/C++. MPI – message passing interface - хорошо стандартизованный механизм для построения программ по модели обмена сообщениями. Существуют стандартные "привязки" MPI к языкам С, С++, Fortran 77, Fortran 90. Существуют бесплатные и коммерческие реализации почти для всех суперкомпьютерных платформ, а также для сетей рабочих станций UNIX и Windows NT. В настоящее время MPI - наиболее широко используемый и динамично развивающийся интерфейс из своего класса.


Slide 19

Hello #include "mpi.h" #include <stdio.h> int main( argc, argv ) int argc; char *argv[]; { int rank, size; MPI_Init( &argc, &argv ); MPI_Comm_rank( MPI_COMM_WORLD, &rank ); MPI_Comm_size( MPI_COMM_WORLD, &size ); printf( "I am %d of %d\n", rank, size ); MPI_Finalize(); return 0; }


Slide 20

Передача числа по кольцу // Передача числа по кольцу из четырех процессоров // По мере передачи каждый процессор увеличивает число на 1 #include <mpi.h> // включение библиотеки MPI #include <stdio.h>   int main(int argc, char ** argv) { int size, rank, count; float D1=123; // число, которое будет передаваться и обрабатываться MPI_Status st; MPI_Init (&argc, &argv); // инициализация программы MPI_Comm_size (MPI_COMM_WORLD, &size); // получаем количество процессоров MPI_Comm_rank (MPI_COMM_WORLD, &rank); // получаем номер текущего процессора if (rank==0) // обмен начинается от нулевого процессора { // отправляем число 1-му процессору MPI_Send (&D1, 1, MPI_FLOAT, 1, 12, MPI_COMM_WORLD); // принимаем результат от 3-го процессора MPI_Recv (&D1, 1, MPI_FLOAT, 3, 12, MPI_COMM_WORLD, &st); } else // для остальных процессоров { // принимаем число от предыдущего процессора MPI_Recv (&D1, 1, MPI_FLOAT, rank-1, 12, MPI_COMM_WORLD, &st); // увеличиваем принятое число на 1 D1+=1; // пересылаем следующему процессору MPI_Send (&D1, 1, MPI_FLOAT, (rank+1)%4, 12, MPI_COMM_WORLD); }; printf ("process %d, received %f\n",rank,D1); // вывод числа MPI_Finalize(); // завершение работы в среде MPI return 0; };


Slide 21

Простой пример Определяются средние значения двух соседних элементов массива и записываются результаты в другой массив. #pragma omp parallel { #pragma omp for for(int i = 1; i < size; ++i) x[i] = (y[i-1] + y[i+1])/2; } Например, для четырехпроцессорного компьютера и size=100, выполнение итераций 1—25 могло бы быть поручено первому процессору, 26—50 — второму, 51—75 — третьему, а 76—99 — четвертому. Это статическая политика планирования. Достигнув конца региона, все потоки блокируются до тех пор, пока последний поток не завершит свою работу. Если исключить директиву #pragma omp for, каждый поток выполнит полный цикл for, проделав много лишней работы: #pragma omp parallel { for(int i = 1; i < size; ++i) x[i] = (y[i-1] + y[i+1])/2; } Можно написать короче: #pragma omp parallel for for(int i = 1; i < size; ++i) x[i] = (y[i-1] + y[i+1])/2; Замечание: в этом цикле нет зависимостей, т. е. одна итерация цикла не зависит от результатов выполнения других итераций.


Slide 22

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


×

HTML:





Ссылка: