Презентация Технологии параллельных вычислений онлайн

Содержание слайда: Технологии параллельных вычислений Судаков А.А. “Параллельные и распределенные вычисления” Лекция 8

Содержание слайда: План Общие сведения Основные схемы параллельных систем Многопоточность OpenMP Обмен сообщениями MPI PVM Linda

Содержание слайда: Литература Спецификация OpenMP http://www.openmp.org/drupal/ MPI http://www-unix.mcs.anl.gov/mpi/

Содержание слайда: Особенности технологий для параллельных вычислений Параллелизм используется для ускорения вычислений Необходимы технологии, рассчитанные на быстрый обмен данными Рассмотренные ранее технологии распределенных вычислений могут использоваться, но они на параллелизм как правило не рассчитывались Параллельные вычисления в масштабах Интернет пока сомнительны

Содержание слайда: Требования к параллельным вычислениям Одновременная работа нескольких устройств Устройства не должны простаивать в ожидании на что-либо Обмен и синхронизация должны осуществляться как можно быстрее

Содержание слайда: Модели параллельных вычислений Общая (разделяемая) память Многопоточность Распределенная память Обмен сообщениями

Содержание слайда: Топологии параллельных систем Различные устройства связаны между собой Структура связей между различными устройствами называется топологией параллельной системы Различают логическую и физическую и виртуальную топологии Физическая определяется аппаратными связями Виртуальная – программными связями Логическая – определяет логику работы алгоритма

Содержание слайда: Примеры топологий

Содержание слайда: Классы параллельных систем SISD SIMD MIMD

Содержание слайда: Цель созданий программных технологий параллельных вычислений Простая реализация Моделей Топологий Классов Декомпозиции Связи Синхронизации Частично используются рассмотренные ранее технологии построения распределенных систем

Содержание слайда: Создание параллельных программ в модели с общей памятью API операционной системы (стандарт POSIX) Порождение процессов Сигналы Конвейеры Общая память System V Семафоры, блокировки Очереди сообщений Потоки Сокеты Стандарт OpenMP

Содержание слайда: Создание параллельных программ с обменом сообщениями API операционных систем Сокеты Стандарты MPI PVM Linda

Содержание слайда: Языки программирования с поддержкой параллелизма Поддержка автопараллелизма Pg[C, C++, Fortran] (Portland Group) Adaptor - Fortran Absoft – Fortran preprocessor Без поддержки автопараллелизма mpC HPF Erlang

Содержание слайда: Процессы Процесс – код выполняющийся в отдельном адресном пространстве Множество процессов может выполняться на одной машине параллельно или псевдопараллельно Каждый процесс имеет доступ к ресурсам Защищенные ресурсы ресурсы совместно используемые с другими процессами средства взаимодействия между процессами

Содержание слайда: Составные части процесса Память Сегменты кода Сегменты данных Сегменты стека Стек задачи Стек ядра Другие сегменты Общая память Дескриптор процесса Информация о выполняющемся процессе Доступ к файловой системе Файловые дескрипторы Файлы Каналы Сокеты

Содержание слайда: Память Физическая память разбита на страницы (обычно фиксированного размера) Страницы объединяются в виртуальные области (сегменты) Каждый процесс содержит ссылку на свои сегменты

Содержание слайда: Файловая система Системные вызовы open close read write Операционная система транслирует эти вызовы в специфические вызовы конкретных файловых систем fat ext3 pipe socket

Содержание слайда: Порождение процессов Один процесс может создать другой процесс Оба процесса будут выполняться параллельно fork+exec spawn

Содержание слайда: Особенности fork+exec и spawn fork Порожденный процесс наследует все ресурсы родителя! Порожденный процесс начинает выполняться с того мести, где был выполнен вызов Перед вызовом exec порожденный процесс может создать новые ресурсы eхес Порожденная программа наследует часть ресурсов родителя Порожденная программа начинает выполняться сначала spawn Порожденная программа наследует часть ресурсов родителя Порожденная программа начинает выполняться сначала

Содержание слайда: Доступ к файловой системе В UNIX системах по возможности все реализовано как файл Обычные файлы open read Write Каналы (конвейер, pipe) Аналог файла, но данные поступают не на диск, а другому процессу Сокеты Аналог файла, но данные уходят/приходят в/из сети

Содержание слайда: Работа с файловой системой

Содержание слайда: Память общего доступа Процесс создает область общей памяти Другие процессы присоединяют эту область к себе Все данные, записанные одним процессом становятся сразу же видны другими процессами

Содержание слайда: Конфликты при обращении к общим ресурсам: 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) Уменьшение Если значение семафора становится меньше нуля, то процесс, который выполнил такую операцию останавливается, пока значение семафора не станет >=0 Увеличение Всегда проходит успешно Проверка на нуль Если значение семафора равно 0, то процесс продолжает выполнение Если не равно нулю, то процесс останавливается, пока значение на станет равным 0

Содержание слайда: Синхронизация с помощью семафоров Процесс 1 Создать семафор Присвоить семафору 1 Уменьшить семафор на 1 (семафор<=0) Обратится к совместно используемым ресурсам Увеличить семафор на 1

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

Содержание слайда: Потоки Часть процесса, которая выполняется параллельно другими частями процесса Все ресурсы потоков - общие Для создания потоков используется аналог функции fork, которой передается функция потока Pthread – стандарт на API для создания потоков

Содержание слайда: Стандарт OpenMP OpenMP – стандарт который включает директивы компилятора, библиотеки и системные переменные, которые могут быть использованы для указания параллелизма в системах с общей памятью Для распараллеливания с помощью OpenMP пользователь должен указать, что выполняется параллельно, какие данные совместно используются, а какие нет.

Содержание слайда: Пример 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<<endl; return 0; }

Содержание слайда: Обмен сообщениями Когда процессы работают на разных машинах, то доступ к одним и тем же данным невозможен Необходимо организовать передачу данных между процессами параллельной программы Данные передаются атомарными порциями – сообщениями Атомарность – сообщение обрабатывается как одно целое

Содержание слайда: Системные API Сокеты – независимый от протокола интерфейс, который позволяет организовать взаимодействие между процессами в сети Впервые – BSD 4.2 TCP - гарантированная доставка в потоке UDP – негарантированная дейтаграмная доставка RAW – Прямой доступ к заголовкам протоколов UNIX – сокеты на локальной машине С сокетами работать также как и с файлами

Содержание слайда: Сокет Серверный процесс socket() – создание сокета bind() – назначение адреса listen() – перевод в режим ожидания входных соединений accept() – прием входного соединения Клиентский процесс socket() – создание сокета bind() – назначение локального адреса (не обязательно) connect() – соединение с сервером Для соединенных сокетов recv(), read() – получение данных Send(), write() – отправка данных

Содержание слайда: Диаграмма работы с сокетами

Содержание слайда: Синхронный и асинхронный обмен Синхронный вызов – функции send(), recv(), accept(), connect() блокируются пока не будет выполнена операция Пока функция не завершится процесс ожидает При этом снижается эффективность распараллеливания Асинхронный вызов – функции send(), recv(), accept(), connect() начинают обмен и передают процессу управление Процесс сразу же начинает выполнять свои работу В случае успешного завершения ввода-вывода или ошибки процессу посылается сигнал или процесс сам проверяет состояние операции ввода-вывода Эффективность параллельной обработки значительно выше

Содержание слайда: API для асинхронных операций ввода-вывода select(), poll() – проверка состояния сокетов Функция возвращает может ли блокирующий вызов завершиться без блокировки Non-block IO – неблокирующий вызов Сокет переводится в неблокирующее состояние Функции завершаются сразу же и возвращают состояние операции Async IO – асинхронный ввод- вывод Сокет переводится в соответствующее состояние При возможности неблокирующего ввода-вывода процессу отправляется сигнал

Содержание слайда: Сравнение синхронного и асинхронного ввода-вывода Синхронный Простота программирования Меньшее количество ошибок Неэффективен для параллельных программ Обычно все операции с общей памятью - синхронны Асинхронный Сложнее программировать Больше ошибок Очень эффективен для параллельных программ При обмене сообщениями позволяет выполнять вычисления одновременно с передачей

Содержание слайда: Интерфейсы параллельного программирования Часто при написании параллельных программ приходится выполнять сложные операции обмена данными Передача от одного процесса к другому Передача от одного процесса всем остальным Суммирование данных на всех процессах … Для этого необходимо разрабатывать свои протоколы и каждый раз программировать сокеты не удобно Были разработаны специальные интерфейсы, которые рассчитаны на быстрый обмен данными между процессами параллельных программ

Содержание слайда: Message Passing Interface (MPI) MPI - стандарт интерфейса (middleware) обмена сообщениями для компьютеров с распределенной памятью MPI программа состоит из нескольких процессов, которые взаимодействуют между собой с помощью вызовов библиотечных функций MPI MPI скрывает от пользователя низкоуровневые детали программирования, такие как программирование сокетов, обработка ошибок приема-передачи, сериализацию и др. MPI предоставляет функции для осуществления взаимодействия точка-точка, коллективных взаимодействий, других операций ввода-вывода

Содержание слайда: Диаграмма соответвия между сокетами, MPI и др

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

Содержание слайда: Разработка и запуск MPI программ Пользователь разрабатывает программу с MPI вызовами Программа компилируется и компонуется с соответствующими библиотеками Запуск программ на удаленных машинах выполняется через rsh,ssh Все программы выполняют один и тот же код, или разный код

Содержание слайда: Пример 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<proc_num; 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; }

Содержание слайда: Результат работы 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

Содержание слайда: Реализации MPI MPICH LAMMPI …. Существуют разные реализации Может отличаться все, кроме совместимости программного кода Некоторые реализации поддерживают не все особенности стандартов

Содержание слайда: Parallel Virtual Machine (PVM) PVM – программные средства для создания параллельных вычислительных комплексов на базе коллекции гетерогенных компьютеров, связанных друг с другом В отличие от MPI – PVM не только средство взаимодействия, но и средства управления процессами (MPI-2 такж)

Содержание слайда: Основные компоненты Платформенно независимый протокол обмена и методы сериализации Библиотека libpvm3 с которой компилируются программы и которая должна быть скомпилирована под все поддерживаемые платформы Демон pvmd, работающий на каждой машине Пользовательские программы, использующие библиотечные вызовы

Содержание слайда: Основные операции Управление процессами Запуск pvm_spawn Обмен сигналами pvm_kill Выход pvm_exit Сериализация/десериализация Упаковка pvm_pk Распаковка pvm_up Отправка/прием pvm_send pvm_recv Управление буфером сообщений Pvm_initsend Коллективные операции Pvm_broadcast

Содержание слайда: Принцип создания параллельных программ Пользователь компилирует для всех платформ одну или несколько программ Программы помещаются каждая в свой каталог для разных платформ В каждой программе используются вызовы PVM Запуск программ выполняется через демона pvmd Запуск демона pvmd через rsh, ssh

Содержание слайда: Пример запуска машины 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>

Содержание слайда: Пример PVM программы #include <stdio.h> #include <pvm3.h> #include <unistd.h> 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; }

Содержание слайда: Языки рассчитанные на параллельное программирование Обычно являются расширением к какому-либо из широко используемых языков и использую MPI, PVM, OpenMP mpC HPF – High Performance Fortran Компиляторы с автораспараллеливанием Модифицируют код Вставляют библиотечные вызовы в код Обычно не эффективны

Содержание слайда: Вопросы ?