Введение в параллельное программирование Максим Городничев Летняя школа отдела МО ВВС ИВМиМГ СО РАН

Содержание лекции 1)Формальный подход к определению параллельной программы 2)Меры качества параллельных программ 3)Предел ускорения вычислений при распараллеливании 4)Реализация параллельных программ в модели общей памяти и в модели распределенной памяти 5)Программирование в распределенной памяти: MPI 6)Пример задачи: численное решение уравнения Пуассона 7)Работа на вычислительных системах Сибирского суперкомпьютерного центра По ходу лекции: комментарии об ошибках, характерных для параллельного программирования (дедлоки, несогласованный доступ к данным)

Последовательное и параллельное Задача: a = b*c+d*e; Последовательная программа: Load r1,b Load r2, c Mul r1, r1, r2 Load r2, d Load r3, d Mul r2, r2, r3 Sum r1, r1, r2 Store a, r1 Алгоритм задает необходимый частичный порядок (потоковое управление):

Представление алгоритма A, вычисляющего функцию F Представление алгоритма A – это набор S = (X, F, C, M), где X – конечное множество переменных F – конечное множество операций С – управление (множество ограничений на порядок операций) = потоковое управление + прямое управление М – функция, задающая отображение множеств X и F в физические устройства параллельной вычислительной машины

Реализация алгоритма A, представленного в форме S – это выполнение операций в некотором порядке, не противоречащим управлению C Представление корректно, если любая реализация вычисляет функцию F, т.е. С содержит потоковое управление.

Последовательное и параллельное: резюме Если множество реализаций алгоритма A, представленного в форме S содержит более одной реализации, то представление S называется параллельным. Если это множество одноэлементно, то представление S назвается последовательным.

Меры качества параллельной реализации Ускорение параллельной реализации относительно последовательной: S = T s /T p, где T s – время выполнения последовательной программы, T p – параллельной Эффективность использования N процессоров относительно одного E = T s /(N*T N ), где T N – время выполнения параллельной программы на N процессорах

Предел ускорения: Закон Амдала Если P – это доля вычислений, которые могут быть выполнены параллельно, а 1-P – доля последовательной части, то максимальное ускорение, которое можно получить на N процессорах равно 1 ((1-P)+(P/N))

Закон Амдала: диаграмма Изображение из Википедии

Иерархия параллельных вычислительных систем Микропроцессоры SMP-узлы: объединения микропроцессоров над общим полем памяти Мультикомпьютеры: SMP-узлы, связанные выделенной сетью передачи данных Grid: объединение произвольных ресурсов

От алгоритма к программе: взаимодействующие процессы Программа часто задается как множество взаимодействующих процессов. Системы программирования отличаются средствами задания взаимодействия.

Модель программирования в общей памяти

Модель программирования в разделенной памяти: обмен сообщениями

Пример параллельной программы в модели общей памяти: OpenMP #include int main() { #pragma omp parallel shared(a, b, c) private(i) { #pragma omp for for (i = 0; i < N; i++) a[i] = b[i] + c[i]; } }

Параллельное программирование в модели разделенной памяти: Message Passing Interface

Первый пример: идентификация процессов #include int main(int argc, char** argv) { int rank, size; char hostname[50]; MPI_Init(&argc, &argv); MPI_Comm_rank(MPI_COMM_WORLD, &rank); MPI_Comm_size(MPI_COMM_WORLD, &size); gethostname(hostname, 50); std::cerr

Взаимодействия точка-точка: MPI_Send, MPI_Recv if(size!=2){ std::cerr

MPI_Sendrecv intBuff = 1234; std::cerr

Групповые взаимодействия: MPI_Bcast, MPI_Barrier int intBuff = rank; std::cerr

MPI_Reduce, MPI_Allreduce int intBuff = 0; std::cerr

Асинхронные взаимодействия точка-точка: MPI_Isend, MPI_Iresv int intBuff = rank; MPI_Request rq; MPI_Isend(&intBuff, 1, MPI_INT, !rank, 0, MPI_COMM_WORLD, &rq); for(int i = 0; i

Другие функции Сбор распределенных векторов: MPI_Gather, MPI_Allgather Распределение вектора: MPI_Scatter и т.д.

The standard includes: (Section 1.7 of MPI 2.1 Standard) Point-to-point communication Datatypes Collective operations Process groups Communication contexts Process topologies Environmental Management and inquiry The info object Process creation and management One-sided communication External interfaces Parallel file I/O Language Bindings for Fortran, C and C++ Profiling interface

Пример решения уравнения Пуассона явным методом Двумерное уравнение: d 2 u/dx 2 +d 2 u/dy 2 -a*u=f Дискретизация: (u (i+1)j -2u ij +u (i-1)j )/h 2 + (u i(j+1) -2uij+u i(j-1) )/h 2 -a*u ij = f ij Итеративный метод: u n+1 ij = 0.25(u n (i+1)j +u n (i-1)j +u n i(j+1) +u n i(j-1) -h 2 f ij )

Декомпозиция задачи Как организовать коммуникации на разрезе?

Организация коммуникаций с помощью дополнительных слоев Создается 2 массива в каждом процессе: для значений предыдущей итерации и новой. Когда значения на границах посчитаны на предыдущей итерации, производится обмен, при этом значения от соседа помещаются в дополнительный слой того же массива. Вычисляются значения на новой итерации с использованием массива предыдущей итерации.

О кластере НКС-30T nks-30t.sscc.ru 32 двойных блейд-серверов HP BL2x220c, в каждом узле два 4-х ядерных процессора Intel Xeon Е5450 (Intel(R) Xeon(R) CPU 3.00GHz) = 512 ядер Пиковая производительнось: ~6 ТФлопс. Операционная система: RedHat Linux (RHEL 5u2) Очередь заданий / система пакетной обработки: PBS Pro 10.0 Компиляторы: Intel C/C++ и Fortran Professional Edition, включают в себя Intel MKL, Intel IPP... Intel MPI и Intel TraceAnalyzer&Collector

Работа на кластере НКС-30T 1 Вход с помощью программы putty.exe : 1.1Имя сервера: nks-30t.sscc.ru 1.2 Логин: 1.3 Пароль: 2. Панельный файловый менеджер: mc 3. Создать в домашней директории папку для своей работы 4. Скопировать себе примеры (содержимое папки ~/examples ) 5. Запустить пример: qsub run.sh 6. Смотреть очередь: qstat 7. Удалить задачу из очереди: qdel 8. Компиляция программы mpiexample.cpp: mpiicpc –o mpiexample.exe mpiexample.cpp 9. Компиляция программы mpiexample.c: mpiicc –o mpiexample.exe mpiexample.c

Схема устройства кластера Головной узел Высокоскоростная сеть «Медленная» сеть для управления и устройства общей файловой системы Internet Вычислительные узлы Машина пользователя

Устройство скрипта запуска задачи run.sh #!/bin/bash #PBS -V #PBS -r n #PBS -l nodes= :ppn=,cput=00:10:00,walltime=15:00 #PBS -k oe #PBS -N name_of_the_job #PBS -j oe date cd $PBS_O_WORKDIR pwd mpirun -r ssh -genv I_MPI_DEVICE rdma -genv I_MPI_RDMA_TRANSLATION_CACHE disable -n date

Где найти информацию? MPI: