Слайд 1Технологии параллельных вычислений
Судаков А.А.
“Параллельные и распределенные вычисления” Лекция 8
Слайд 2План
Общие сведения
Основные схемы параллельных систем
Многопоточность
OpenMP
Обмен сообщениями
MPI
PVM
Linda
Слайд 3Литература
Спецификация OpenMP http://www.openmp.org/drupal/
MPI http://www-unix.mcs.anl.gov/mpi/
Слайд 4Особенности технологий для параллельных вычислений
Параллелизм используется для ускорения вычислений
Необходимы технологии,
рассчитанные на быстрый обмен данными
Рассмотренные ранее технологии распределенных вычислений могут
использоваться, но они на параллелизм как правило не рассчитывались
Параллельные вычисления в масштабах Интернет пока сомнительны
Слайд 5Требования к параллельным вычислениям
Одновременная работа нескольких устройств
Устройства не должны
простаивать в ожидании на что-либо
Обмен и синхронизация должны осуществляться как
можно быстрее
Слайд 6Модели параллельных вычислений
Общая (разделяемая) память
Многопоточность
Распределенная память
Обмен сообщениями
Слайд 7Топологии параллельных систем
Различные устройства связаны между собой
Структура связей между различными
устройствами называется топологией параллельной системы
Различают логическую и физическую и виртуальную
топологии
Физическая определяется аппаратными связями
Виртуальная – программными связями
Логическая – определяет логику работы алгоритма
Слайд 8Примеры топологий
звезда
Линейка (ферма)
решетка
Слайд 9Классы параллельных систем
SISD
SIMD
MIMD
Слайд 10Цель созданий программных технологий параллельных вычислений
Простая реализация
Моделей
Топологий
Классов
Декомпозиции
Связи
Синхронизации
Частично используются рассмотренные
ранее технологии построения распределенных систем
Слайд 11Создание параллельных программ в модели с общей памятью
API операционной
системы (стандарт POSIX)
Порождение процессов
Сигналы
Конвейеры
Общая память System V
Семафоры, блокировки
Очереди сообщений
Потоки
Сокеты
Стандарт
OpenMP
Слайд 12Создание параллельных программ с обменом сообщениями
API операционных систем
Сокеты
Стандарты
MPI
PVM
Linda
Слайд 13Языки программирования с поддержкой параллелизма
Поддержка автопараллелизма
Pg[C, C++, Fortran] (Portland Group)
Adaptor
- Fortran
Absoft – Fortran preprocessor
Без поддержки автопараллелизма
mpC
HPF
Erlang
Слайд 14Процессы
Процесс – код выполняющийся в отдельном адресном пространстве
Множество процессов может
выполняться на одной машине параллельно или псевдопараллельно
Каждый процесс имеет доступ
к ресурсам
Защищенные ресурсы
ресурсы совместно используемые с другими процессами
средства взаимодействия между процессами
Слайд 15Составные части процесса
Память
Сегменты кода
Сегменты данных
Сегменты стека
Стек задачи
Стек ядра
Другие сегменты
Общая память
Дескриптор
процесса
Информация о выполняющемся процессе
Доступ к файловой системе
Файловые дескрипторы
Файлы
Каналы
Сокеты
Слайд 16Память
Физическая память разбита на страницы (обычно фиксированного размера)
Страницы объединяются в
виртуальные области (сегменты)
Каждый процесс содержит ссылку на свои сегменты
Слайд 17Файловая система
Системные вызовы
open
close
read
write
Операционная система транслирует эти вызовы в специфические вызовы
конкретных файловых систем
fat
ext3
pipe
socket
Слайд 18Порождение процессов
Один процесс может создать другой процесс
Оба процесса будут выполняться
параллельно
fork+exec
spawn
Процесс А
i=fork()
Процесс А
i!=0
Процесс A
i==0
exec(программа B)
Процесс B
Процесс А
Процесс А
spawn(программа B)
Процесс B
Процесс
А
Слайд 19Особенности fork+exec и spawn
fork
Порожденный процесс наследует все ресурсы родителя!
Порожденный процесс
начинает выполняться с того мести, где был выполнен вызов
Перед вызовом
exec порожденный процесс может создать новые ресурсы
eхес
Порожденная программа наследует часть ресурсов родителя
Порожденная программа начинает выполняться сначала
spawn
Порожденная программа наследует часть ресурсов родителя
Порожденная программа начинает выполняться сначала
Слайд 20Доступ к файловой системе
В UNIX системах по возможности все
реализовано как файл
Обычные файлы
open
read
Write
Каналы (конвейер, pipe)
Аналог файла, но данные поступают
не на диск, а другому процессу
Сокеты
Аналог файла, но данные уходят/приходят в/из сети
Слайд 21Работа с файловой системой
Открываем
файл, канал, сокет
open(), pipe(), socket()
запись
write()
Чтение read()
Закрываем файл
close()
pipe
Обычный файл
сокет
запись write()
Чтение read()
Процесс 1
Процесс 2
На диск
запись
write()
Чтение read()
Процесс 3
По сети
Слайд 22Память общего доступа
Процесс создает область общей памяти
Другие процессы присоединяют
эту область к себе
Все данные, записанные одним процессом становятся сразу
же видны другими процессами
Слайд 23Конфликты при обращении к общим ресурсам: a – общая переменная
Процесс1
: считываем a=1
Процесс1 : увеличивает a на 1 a=2
Процесс 1: записывает
a назад a=2
Процесс2 : считываем a=2
Процесс2 : увеличивает a на 1 a=3
Процесс 2: записывает a назад a=3
Процесс1 : считываем a=1
Процесс2 : считываем a=1
Процесс1 : увеличивает a на 1 a=2
Процесс2 : увеличивает a на 1 a=2
Процесс 2: записывает a назад a=2
Процесс 1: записывает a назад a=2
Слайд 24Семафоры
Семафор – совместно используемая атомарная целочисленная переменная
В каждый момент времени
изменять значение семафора может только один процесс
Значение семафорам может увеличиваться
или уменьшатся на целое число (обычно на 1)
Уменьшение
Если значение семафора становится меньше нуля, то процесс, который выполнил такую операцию останавливается, пока значение семафора не станет >=0
Увеличение
Всегда проходит успешно
Проверка на нуль
Если значение семафора равно 0, то процесс продолжает выполнение
Если не равно нулю, то процесс останавливается, пока значение на станет равным 0
Слайд 25Синхронизация с помощью семафоров
Процесс 1
Создать семафор
Присвоить семафору 1
Уменьшить семафор на
1 (семафор
семафор на 1 (семафор<=0)
Обратится к совместно используемым ресурсам
Увеличить семафор на 1
Слайд 26Сигналы
Сигнал – аналог прерывания
Асинхронное событие – неизвестно когда произойдет
Один процесс
может послать другому сигнал с определенным номером
Процесс может сигнал перехватить,
игнорировать или выполнить действие по умолчанию
Слайд 27Потоки
Часть процесса, которая выполняется параллельно другими частями процесса
Все ресурсы потоков
- общие
Для создания потоков используется аналог функции fork, которой
передается функция потока
Pthread – стандарт на API для создания потоков
Слайд 28Стандарт OpenMP
OpenMP – стандарт который включает директивы компилятора, библиотеки и
системные переменные, которые могут быть использованы для указания параллелизма в
системах с общей памятью
Для распараллеливания с помощью OpenMP пользователь должен указать, что выполняется параллельно, какие данные совместно используются, а какие нет.
Слайд 29Пример OpenMP
int main (void){
int i;
int k = 0;
#pragma omp parallel
for default(shared) private(i) \
reduction(+:k)
for (i
=0; i<=1000000; i++)
k+=func(i);
cout << k<return 0;
}
Слайд 30Обмен сообщениями
Когда процессы работают на разных машинах, то доступ к
одним и тем же данным невозможен
Необходимо организовать передачу данных между
процессами параллельной программы
Данные передаются атомарными порциями – сообщениями
Атомарность – сообщение обрабатывается как одно целое
Слайд 31Системные API
Сокеты – независимый от протокола интерфейс, который позволяет организовать
взаимодействие между процессами в сети
Впервые – BSD 4.2
TCP - гарантированная
доставка в потоке
UDP – негарантированная дейтаграмная доставка
RAW – Прямой доступ к заголовкам протоколов
UNIX – сокеты на локальной машине
С сокетами работать также как и с файлами
Слайд 32Сокет
Серверный процесс
socket() – создание сокета
bind() – назначение адреса
listen() – перевод
в режим ожидания входных соединений
accept() – прием входного соединения
Клиентский процесс
socket()
– создание сокета
bind() – назначение локального адреса (не обязательно)
connect() – соединение с сервером
Для соединенных сокетов
recv(), read() – получение данных
Send(), write() – отправка данных
Слайд 33Диаграмма работы с сокетами
Сервер
socket()
Создаем сокет
bind()
Назначаем адрес и порт
cluster.univ.kiev.ua:22
listen()
Переводим в режим
«слушать»
На входящие соединения
accept()
Ожидаем входящее
соединение
Клиент
socket()
Создаем сокет
connect()
Соединение с
cluster.univ.kiev.ua:22
возвращаем
соединенный сокет
Соединенный сокет
с другим клиентом
Обмен данными
По сети
Слайд 34Синхронный и асинхронный обмен
Синхронный вызов –
функции send(), recv(), accept(),
connect() блокируются пока не будет выполнена операция
Пока функция не завершится
процесс ожидает
При этом снижается эффективность распараллеливания
Асинхронный вызов –
функции send(), recv(), accept(), connect() начинают обмен и передают процессу управление
Процесс сразу же начинает выполнять свои работу
В случае успешного завершения ввода-вывода или ошибки процессу посылается сигнал или процесс сам проверяет состояние операции ввода-вывода
Эффективность параллельной обработки значительно выше
Слайд 35API для асинхронных операций ввода-вывода
select(), poll() – проверка состояния сокетов
Функция
возвращает может ли блокирующий вызов завершиться без блокировки
Non-block IO –
неблокирующий вызов
Сокет переводится в неблокирующее состояние
Функции завершаются сразу же и возвращают состояние операции
Async IO – асинхронный ввод- вывод
Сокет переводится в соответствующее состояние
При возможности неблокирующего ввода-вывода процессу отправляется сигнал
Слайд 36Сравнение синхронного и асинхронного ввода-вывода
Синхронный
Простота программирования
Меньшее количество ошибок
Неэффективен для параллельных
программ
Обычно все операции с общей памятью - синхронны
Асинхронный
Сложнее программировать
Больше ошибок
Очень
эффективен для параллельных программ
При обмене сообщениями позволяет выполнять вычисления одновременно с передачей
Слайд 37Интерфейсы параллельного программирования
Часто при написании параллельных программ приходится выполнять сложные
операции обмена данными
Передача от одного процесса к другому
Передача от одного
процесса всем остальным
Суммирование данных на всех процессах
…
Для этого необходимо разрабатывать свои протоколы и каждый раз программировать сокеты не удобно
Были разработаны специальные интерфейсы, которые рассчитаны на быстрый обмен данными между процессами параллельных программ
Слайд 38Message Passing Interface (MPI)
MPI - стандарт интерфейса (middleware) обмена сообщениями
для компьютеров с распределенной памятью
MPI программа состоит из нескольких процессов,
которые взаимодействуют между собой с помощью вызовов библиотечных функций MPI
MPI скрывает от пользователя низкоуровневые детали программирования, такие как программирование сокетов, обработка ошибок приема-передачи, сериализацию и др.
MPI предоставляет функции для осуществления взаимодействия точка-точка, коллективных взаимодействий, других операций ввода-вывода
Слайд 39Диаграмма соответвия между сокетами, MPI и др
Интерфейс сокетов
Интерфейсы взаимодействия с
общей памятью
Ядро
Аппаратное обеспечение
Middleware – MPI, PVM, RPC, CORBA
Пользовательская программа
Слайд 40Основные определения
Процесс
Программа, которая выполняет свой код
Процесс характеризуется только своим
номером в группе
Группы процессов
Процессы можно группировать по любому признаку
Коммуникаторы
Группы процессов,
которые используются для определения номера при взаимодействиях
Вначале определен MPI_COMM_WORLD
Новые коммуникаторы можно создавать используя существующие
Топологии
Соответствие номера процесса в коммуникаторе узлу топологии
Слайд 41Разработка и запуск MPI программ
Пользователь разрабатывает программу с MPI вызовами
Программа
компилируется и компонуется с соответствующими библиотеками
Запуск программ на удаленных машинах
выполняется через rsh,ssh
Все программы выполняют один и тот же код, или разный код
Слайд 42Пример MPI программы
int main(int argc, char* argv[]){
int my_number; //Мой номер процесса
int proc_num;
//общее количество процессов
int data; //данные, получаемые от других процессов
int i; //парамтер цикла
MPI_Init(&argc, &argv);
MPI_Comm_size(MPI_COMM_WORLD, &proc_num);
MPI_Comm_rank(MPI_COMM_WORLD, &my_number);
printf("I an process %d, sending data\n", my_number);
MPI_Send((void*)&my_number,1,MPI_INT,0,0,MPI_COMM_WORLD);
if(!my_number){
printf ("MPI %d processes\n Am root, reciving data, \n",proc_num);
for (i = 0; i
MPI_Recv((void*)&data,1,MPI_INT,i,0,MPI_COMM_WORLD, NULL);
printf ("Am root, recived data %d from %d \n",data,i);
}
}
MPI_Finalize();
return 0;
}
Слайд 43Результат работы MPI программы
[saa@cluster mpi]$ mpirun -np 10 ./a.out
I an
process 0, sending data
MPI 10 processes
Am root, reciving data,
Am
root, recived data 0 from 0
Am root, recived data 1 from 1
Am root, recived data 2 from 2
I an process 1, sending data
I an process 2, sending data
I an process 3, sending data
I an process 4, sending data
I an process 5, sending data
I an process 6, sending data
I an process 8, sending data
I an process 9, sending data
Am root, recived data 3 from 3
Am root, recived data 4 from 4
Am root, recived data 5 from 5
Am root, recived data 6 from 6
Am root, recived data 7 from 7
Am root, recived data 8 from 8
Am root, recived data 9 from 9
I an process 7, sending data
Слайд 44Реализации MPI
MPICH
LAMMPI
….
Существуют разные реализации
Может отличаться все, кроме совместимости программного кода
Некоторые
реализации поддерживают не все особенности стандартов
Слайд 45Parallel Virtual Machine (PVM)
PVM – программные средства для создания параллельных
вычислительных комплексов на базе коллекции гетерогенных компьютеров, связанных друг с
другом
В отличие от MPI – PVM не только средство взаимодействия, но и средства управления процессами (MPI-2 такж)
Слайд 46Основные компоненты
Платформенно независимый протокол обмена и методы сериализации
Библиотека libpvm3 с
которой компилируются программы и которая должна быть скомпилирована под все
поддерживаемые платформы
Демон pvmd, работающий на каждой машине
Пользовательские программы, использующие библиотечные вызовы
Слайд 47Основные операции
Управление процессами
Запуск pvm_spawn
Обмен сигналами pvm_kill
Выход pvm_exit
Сериализация/десериализация
Упаковка pvm_pk
Распаковка
pvm_up
Отправка/прием
pvm_send
pvm_recv
Управление буфером сообщений
Pvm_initsend
Коллективные операции
Pvm_broadcast
Слайд 48Принцип создания параллельных программ
Пользователь компилирует для всех платформ одну или
несколько программ
Программы помещаются каждая в свой каталог для разных платформ
В
каждой программе используются вызовы PVM
Запуск программ выполняется через демона pvmd
Запуск демона pvmd через rsh, ssh
Слайд 49Пример запуска машины PVM
[saa@cluster mpi]$ pvm
pvmd already running.
pvm> conf
conf
1 host,
1 data format
HOST DTID ARCH SPEED DSIG
cluster.univ.kiev.ua 40000 LINUXI386 1000 0x00408841
pvm> add s15
add s15
1 successful
HOST DTID
s15 1c0000
pvm> conf
conf
2 hosts, 2 data formats
HOST DTID ARCH SPEED DSIG
cluster.univ.kiev.ua 40000 LINUXI386 1000 0x00408841
s15 1c0000 LINUXX86_64 1000 0x00408c41
pvm>
Слайд 50Пример PVM программы
#include
#include
#include
int main(int argc, char* argv[]){
int p_tid, c_tid;
int
res;
char message[4096];
p_tid = pvm_mytid();
if(argc < 2) { // child
p_tid = pvm_parent();
pvm_initsend(PvmDataDefault);
gethostname(message,4095);
pvm_pkstr(message);
pvm_send(p_tid,1);
pvm_exit();
} else { // parent
p_tid = pvm_mytid();
res = pvm_spawn("test_pvm",NULL,0,"",1,&c_tid);
if(res == 1){
pvm_recv(c_tid,1);
pvm_upkstr(message);
printf("Child is working at %s\n",message);
pvm_exit();
}
}
return 0;
}
Результат
[saa@cluster pvm]$ ./test_pvm parent
Child is working at cluster.univ.kiev.ua
Слайд 51Языки рассчитанные на параллельное программирование
Обычно являются расширением к какому-либо из
широко используемых языков и использую MPI, PVM, OpenMP
mpC
HPF – High
Performance Fortran
Компиляторы с автораспараллеливанием
Модифицируют код
Вставляют библиотечные вызовы в код
Обычно не эффективны
![Языки программирования с поддержкой параллелизмаПоддержка автопараллелизмаPg[C, C++, Fortran] (Portland Group)Adaptor - FortranAbsoft – Fortran preprocessorБез поддержки автопараллелизмаmpCHPFErlang](/img/thumbs/c74210edc9c135d006508e35acd2d254-800x.jpg "Технологии параллельных вычислений Языки программирования с поддержкой параллелизмаПоддержка автопараллелизмаPg[C, C++, Fortran] (Portland Group)Adaptor -")
![Пример MPI программыint main(int argc, char* argv[]){ int my_number; //Мой номер процесса](/img/thumbs/8052e5d09aedbc7aff1dfb311e31d61f-800x.jpg "Технологии параллельных вычислений Пример MPI программыint main(int argc, char* argv[]){ int my_number; //Мой")
![Результат работы MPI программы[saa@cluster mpi]$ mpirun -np 10 ./a.outI an process 0, sending dataMPI 10 processes Am](/img/thumbs/fa83a7df3954978593a04cc909f855a2-800x.jpg "Технологии параллельных вычислений Результат работы MPI программы[saa@cluster mpi]$ mpirun -np 10 ./a.outI an process")
![Пример запуска машины PVM[saa@cluster mpi]$ pvmpvmd already running.pvm> confconf1 host, 1 data format](/img/thumbs/7f0a9cb0c14cd3a077521146f1bf3cc4-800x.jpg "Технологии параллельных вычислений Пример запуска машины PVM[saa@cluster mpi]$ pvmpvmd already running.pvm> confconf1 host, 1")
![Пример PVM программы#include #include #include int main(int argc, char* argv[]){ int p_tid, c_tid;](/img/thumbs/240640d20fd55c0c4e58a3d06b6f9369-800x.jpg "Технологии параллельных вычислений Пример PVM программы#include #include #include int main(int argc, char* argv[]){")
