Слайд 2
Содержание лекции
Формальный подход к определению параллельной программы
Меры качества
параллельных программ
Предел ускорения вычислений при распараллеливании
Реализация параллельных программ в
модели общей памяти и в модели распределенной памяти
Программирование в распределенной памяти: MPI
Пример задачи: численное решение уравнения Пуассона
Работа на вычислительных системах Сибирского суперкомпьютерного центра
По ходу лекции: комментарии об ошибках, характерных для параллельного программирования (дедлоки, несогласованный доступ к данным)
Слайд 3
Последовательное и параллельное
Задача: 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
Алгоритм задает необходимый частичный порядок (потоковое управление):
Слайд 4
Представление алгоритма A, вычисляющего функцию F
Представление алгоритма A
– это набор
S = (X, F, C, M),
где
X – конечное множество переменных
F – конечное множество операций
С – управление (множество ограничений на порядок операций) = потоковое управление + прямое управление
М – функция, задающая отображение множеств X и F в физические устройства параллельной вычислительной машины
Слайд 5
Реализация алгоритма A, представленного в форме S
– это
выполнение операций в некотором порядке, не противоречащим управлению C
Представление
корректно, если любая реализация вычисляет функцию F, т.е. С содержит потоковое управление.
Слайд 6
Последовательное и параллельное: резюме
Если множество реализаций алгоритма A,
представленного в форме S содержит более одной реализации, то
представление S называется параллельным.
Если это множество одноэлементно, то представление S назвается последовательным.
Слайд 7
Меры качества параллельной реализации
Ускорение параллельной реализации относительно последовательной:
S
= Ts/Tp, где Ts – время выполнения последовательной программы,
Tp – параллельной
Эффективность использования N процессоров относительно одного
E = Ts/(N*TN), где TN – время выполнения параллельной программы на N процессорах
Слайд 8
Предел ускорения: Закон Амдала
Если P – это доля
вычислений, которые могут быть выполнены параллельно, а 1-P –
доля последовательной части, то максимальное ускорение, которое можно получить на N процессорах равно
1
((1-P)+(P/N))
Слайд 9
Закон Амдала: диаграмма
Изображение из Википедии
Слайд 10
Иерархия параллельных вычислительных систем
Микропроцессоры
SMP-узлы: объединения микропроцессоров над общим
полем памяти
Мультикомпьютеры: SMP-узлы, связанные выделенной сетью передачи данных
Grid: объединение
произвольных ресурсов
Слайд 11
От алгоритма к программе: взаимодействующие процессы
Программа часто задается
как множество взаимодействующих процессов. Системы программирования отличаются средствами задания
взаимодействия.
Слайд 12
Модель программирования в общей памяти
Слайд 13
Модель программирования в разделенной памяти: обмен сообщениями
Слайд 14
Пример параллельной программы в модели общей памяти: 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];
}
<…>
}
Слайд 15
Параллельное программирование в модели разделенной памяти:
Message Passing
Interface
Слайд 16
Первый пример: идентификация процессов
#include
#include
#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 << "Rank = " << rank << ", hostname = "
<< hostname << ", size = " << size << "\n";
MPI_Finalize();
return 0;
}
Пример команды запуска программы: mpirun –np 4 first_example.exe
Запускается 4 копии программы – 4 процесса, каждый получает свой идентификатор rank: 0, 1, 2, 3
Слайд 17
Взаимодействия точка-точка: MPI_Send, MPI_Recv
if(size!=2){
std::cerr
processes required\n";
MPI_Finalize();
return 1;
}
int intBuff =
1234;
MPI_Status st;
if(rank==0){
MPI_Send(&rank, 1, MPI_INT, 1, 0, MPI_COMM_WORLD);
std::cerr << "Rank " << rank << ": initial value of intBuff = " << intBuff << "\n";
MPI_Recv(&intBuff, 1, MPI_INT, 1, 0, MPI_COMM_WORLD, &st);
std::cerr << "Rank " << rank << ": received from Rank 1 intBuff = " << intBuff << "\n";
}
else
if(rank==1) {
std::cerr << "Rank " << rank << ": initial value of intBuff = " << intBuff << "\n";
MPI_Recv(&intBuff, 1, MPI_INT, 0, 0, MPI_COMM_WORLD, &st);
std::cerr << "Rank " << rank << ": received from Rank 0 intBuff = " << intBuff << "\n";
MPI_Send(&rank, 1, MPI_INT, 0, 0, MPI_COMM_WORLD);
}
Слайд 18
MPI_Sendrecv
intBuff = 1234;
std::cerr
intBuff << "\n";
MPI_Sendrecv(&rank, 1, MPI_INT, !rank, 0,
&intBuff, 1, MPI_INT, !rank, 0, MPI_COMM_WORLD, &st);
std::cerr << "Rank " << rank << ": received from Rank "
<< (!rank) << " intBuff = " << intBuff << "\n";
Слайд 19
Групповые взаимодействия: MPI_Bcast, MPI_Barrier
int intBuff = rank;
std::cerr
"Rank = "
" << intBuff << "\n";
MPI_Bcast(&intBuff, 1, MPI_INT, 0, MPI_COMM_WORLD);
std::cerr << "Rank = " << rank << ", after Bcast intBuff = " << intBuff << "\n";
//example of another scenario
MPI_Barrier(MPI_COMM_WORLD);
if(rank==0)
std::cerr << "---- Another scenario ----\n";
MPI_Barrier(MPI_COMM_WORLD);
intBuff = rank;
std::cerr << "Rank = " << rank << ", again intBuff = rank = " << intBuff << "\n";
if(rank==0)
MPI_Bcast(&rank, 1, MPI_INT, 0, MPI_COMM_WORLD);
else
MPI_Bcast(&intBuff, 1, MPI_INT, 0, MPI_COMM_WORLD);
std::cerr << "Rank = " << rank << ", after second Bcast intBuff = " << intBuff << "\n";
Слайд 20
MPI_Reduce, MPI_Allreduce
int intBuff = 0;
std::cerr
"
<< intBuff << "\n";
MPI_Reduce(&rank, &intBuff, 1, MPI_INT,
MPI_SUM, 0, MPI_COMM_WORLD);
std::cerr << "Rank = " << rank
<< ", after Reduce intBuff = " << intBuff << "\n";
intBuff = 0;
MPI_Allreduce(&rank, &intBuff, 1,
MPI_INT, MPI_SUM, MPI_COMM_WORLD);
std::cerr << "Rank = " << rank
<< ", after Allreduce intBuff = " << intBuff << "\n";
Слайд 21
Асинхронные взаимодействия точка-точка: 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<100; i++)
std::cout << "working\n";
int flag = 0;
MPI_Status st;
MPI_Wait(&rq, &st);
//we can write to intBuff again: receiving into intBuff now.
//we can use rq again.
MPI_Irecv(&intBuff, 1, MPI_INT, !rank, 0, MPI_COMM_WORLD, &rq);
for(int i = 0; i<100; i++)
std::cout << "working again\n";
MPI_Wait(&rq, &st);
//now intBuff contains a message received from a peer
std::cerr << "Rank " << rank << ": intBuff = " << intBuff << "\n";
Слайд 22
Другие функции
Сбор распределенных векторов: MPI_Gather, MPI_Allgather
Распределение вектора: MPI_Scatter
и
т.д.
Слайд 23
“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
Слайд 24
Пример решения уравнения Пуассона явным методом
Двумерное уравнение:
d2u/dx2+d2u/dy2-a*u=f
Дискретизация:
(u(i+1)j-2uij+u(i-1)j)/h2+ (ui(j+1)-2uij+ui(j-1))/h2-a*uij
= fij
Итеративный метод:
un+1ij = 0.25(un(i+1)j+un(i-1)j+uni(j+1)+uni(j-1)-h2fij)
Слайд 25
Декомпозиция задачи
Как организовать коммуникации на разрезе?
Слайд 26
Организация коммуникаций с помощью дополнительных слоев
Создается 2 массива
в каждом процессе: для значений предыдущей итерации и новой.
Когда
значения на границах посчитаны на предыдущей итерации, производится обмен, при этом значения от соседа помещаются в дополнительный слой того же массива.
Вычисляются значения на новой итерации с использованием массива предыдущей итерации.
Слайд 27
О кластере НКС-30T
nks-30t.sscc.ru
32 двойных блейд-серверов HP BL2x220c, в
каждом узле два 4-х ядерных процессора Intel Xeon Е5450
(Intel(R) Xeon(R) CPU E5450 @ 3.00GHz)
= 512 ядер
Пиковая производительнось: ~6 ТФлопс.
Операционная система: RedHat Linux (RHEL 5u2)
Очередь заданий / система пакетной обработки: PBS Pro 10.0
Компиляторы: Intel C/C++ и Fortran 11.0.081 Professional Edition,
включают в себя Intel MKL, Intel IPP ...
Intel MPI 3.2.0.011 и Intel TraceAnalyzer&Collector 7.2.0.011
Слайд 28
Работа на кластере НКС-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
Слайд 29
Схема устройства кластера
Головной узел
Высокоскоростная сеть
«Медленная» сеть для управления
и устройства общей файловой системы
Internet
Вычислительные узлы
Машина пользователя
Слайд 30
Устройство скрипта запуска задачи 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 <количество процессов MPI> <путь к исполняемому файлу>
date
