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

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

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

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

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

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

6 Классификация по построению: Класс 1 КА «разделение фаз» A={0,1) M={(i,j): i,j=0,…,200} 1,if u0u0 u1u1 u2u2 u3u3 u4u4 u5u5 u6u6 u7u7 u8u8 u0u0 1, if u k >5 or u k =4 0, otherwise u=

7 Классификация по построению: Класс 2 СO + = CO O = 2O CO + O = CO 2 +2O CO + = + CO адсорбция СО адсорбция О 2 реакция диффузия Окисление CO на платиновом катализаторе: CO O CO p2p2 p3p3 CO O CO p1p1

8 Классификация по построению: Класс 2 Процесс окисления CO на платиновом катализаторе: -CO - O - Pt Устойчивые глобальные состояния от отношения парциальных давлений p 1 /p 2 O 2 (p 2 ) CO (p 1 )

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

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

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

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

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

14 ? 0 Противоречие ! = {(u,(i,j),(v(i,j+1)} {(v,(i,j),(u(i,j+1)} Пример некорректного поведения: A={0,1}, M={(i,j)}, синхронный режим j i (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) Вспомним условия корректности КА

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

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

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

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

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

20 Hello #include "mpi.h" #include 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; }

21 Передача числа по кольцу // Передача числа по кольцу из четырех процессоров // По мере передачи каждый процессор увеличивает число на 1 #include // включение библиотеки MPI #include 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; };

22 Простой пример Определяются средние значения двух соседних элементов массива и записываются результаты в другой массив. #pragma omp parallel { #pragma omp for for(int i = 1; i < size; ++i) x[i] = (y[i-1] + y[i+1])/2; } Например, для четырехпроцессорного компьютера и size=100, выполнение итераций 125 могло бы быть поручено первому процессору, 2650 второму, 5175 третьему, а 7699 четвертому. Это статическая политика планирования. Достигнув конца региона, все потоки блокируются до тех пор, пока последний поток не завершит свою работу. Если исключить директиву #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; Замечание: в этом цикле нет зависимостей, т. е. одна итерация цикла не зависит от результатов выполнения других итераций.

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