Интернет Университет Суперкомпьютерных технологий Лекция 1 Основные понятия Учебный курс Введение в параллельные алгоритмы Якобовский М.В., проф., д.ф.-м.н. Институт прикладной математики им. М.В.Келдыша РАН, Москва..

Многопроцессорные системы –с распределенной памятью –с общей памятью –Гибридные Модель выполнения программ Методы взаимодействия процессов –Методы передачи данных –Семафоры Ускорение и эффективность параллельных алгоритмов Пример алгоритма низкой эффективности Содержание лекции Москва, 2011 г. Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 2 из 47

Транспьютерная материнская плата МТБ-8 Москва, 2011 г. Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 3 из 47

Транспьютер T-800 Москва, 2011 г. Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 4 из 47

Транспьютерная материнская плата МТБ-8 Москва, 2011 г. Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 5 из 47

Электронный коммутатор Москва, 2011 г. Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 6 из 47

Москва, 2011 г. Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 7 из 47

Узел с общей памятью – два процессора Москва, 2011 г. Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 8 из 47

Москва, 2011 г. Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 9 из 47

Узел PowerXplorer Москва, 2011 г. Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 10 из 47

Гибридная система Москва, 2011 г. Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 11 из 47

Москва, 2011 г. Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 12 из 47

Плата и 4 модуля Москва, 2011 г. Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 13 из 47

Многопроцессорные системы с распределенной памятью Москва, 2011 г. Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 14 из 47

Многопроцессорные системы с общей памятью Москва, 2011 г. Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 15 из 47

При запуске указываем число требуемых процессоров Np и название программы На выделенных для расчета узлах запускается Np копий указанной программы –Например, на двух узлах запущены три копии программы. Копия программы с номером 1 не имеет непосредственного доступа к оперативной памяти копий 0 и 2: Каждая копия программы получает две переменные –Np –rank из диапазона [0 … Np-1] Любые две копии программы могут непосредственно обмениваться данными с помощью функций передачи сообщений Модель программы на распределенной памяти Москва, 2011 г Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 16 из 47

Работа начинается с запуска одной программы При необходимости программа порождает новые процессы, эти процессы: –Обладают собственными локальными переменными –Имеют доступ к глобальным переменным int a_global; main нить1 нить2 main() { int b1_local; запуск нити1 Запуск нити(fun()) } запуск нити2 fun() { int b2_local; Запуск нити(…) } Модель программы на общей памяти Москва, 2011 г. Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 17 из 47

Синхронный метод Send(адрес данных, размер, номер процессора) Recv(адрес данных, размер, номер процессора) Асинхронные методы –Небуферизованный ASend(адрес данных, размер, номер процессора) ARecv(адрес данных, размер, номер процессора) ASync –Буферизованный ABSend(адрес данных, размер, номер процессора) Методы передачи данных Москва, 2011 г. Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 18 из 47

A=3 Send(&A) A=5 Синхронные Москва, 2011 г. B=4 Recv(&B) Print(B) Send Recv Print(B) A=5 B=4 A=3 Результат 3 Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 19 из 47

A=3 АSend(&A) A=5 Асинхронные Москва, 2011 г. B=4 АRecv(&B) Print(B) Send ASend Recv ARecv Print(B) A=5 B=4 Результат 3 ? 4 ? 5 A=3 Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 20 из 47

A=3 АSend(&A) Async() A=5 Асинхронные Москва, 2011 г. B=4 АRecv(&B) Print(B) ASync Send ASend Recv ARecv Print(B) A=5 B=4 Результат 3 ? 4 A=3 Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 21 из 47

A=3 АSend(&A) Async() A=5 Асинхронные Москва, 2011 г. B=4 АRecv(&B) Async() Print(B) Результат 3 ASync Send ASend ASync Recv ARecv Print(B) A=5 A=3 B=4 Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 22 из 47

A=3 АBSend(&A) A=5 Асинхронные буферизованные Москва, 2011 г. B=4 АRecv(&B) Async() Print(B) Результат 3 Send(&buf) ABSend ASync Recv ARecv Print(B) A=5 buf=A A=3 B=4 Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 23 из 47

Свойства канала передачи данных Москва, 2011 г. Gbit Ethernet Число передаваемых байт Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 24 из 47 T(n)=n*T передачи байта + T латентности

Свойства канала передачи данных Москва, 2011 г. T(n)=n*T передачи байта + T латентности Число передаваемых байт Infiniband Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 25 из 47

Целочисленная неотрицательная переменная Две атомарные операции, не считая инициализации V(S) –Увеличивает значение S на 1 P(S) –Если S положительно, то уменьшает S на 1 –Иначе ждет, пока S не станет больше 0 Семафор Языки програмирования. Редактор Ф.Женюи. Перевод с англ В.П.Кузнецова. Под ред. В.М.Курочкина. М:."Мир", 1972 Э. Дейкстра. Взаимодействие последовательных процессов. Москва, 2011 г. Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 26 из 47

ускорение параллельного алгоритма S(p)=T1/T(p) Ускорение и эффективность параллельных алгоритмов Москва, 2011 г. Ускорение параллельного алгоритма относительно наилучшего последовательного S * (p)=T1 * /T(p) E * (p)=S * (p)/p эффективность использования процессорной мощности E(p)=S(p)/p Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 27 из 47

Да: –Плохой последовательный алгоритм –Влияние аппаратных особенностей вычислительной системы Может ли быть S(p)>p ? Москва, 2011 г. Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 28 из 47

Да –Если первый алгоритм позволяет использовать больше процессоров, чем второй. Самый эффективный алгоритм – использующий один (1) процессор. –Его эффективность по определению равна 100%, но он не всегда самый быстрый. Может ли неэффективный алгоритм работать быстрее эффективного? Москва, 2011 г. Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 29 из 47

Все элементарные операции (+ - * / ) выполняются за время с Все операции выполняются точно, результат не зависит от порядка их выполнения Число процессоров неограничено Определить сумму конечного ряда 30 Москва, 2011 г. Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 30 из 47

S=1; a=1; for(i=1;i

Параллельный алгоритм Вычислить для всех i =1,…,n : x i Вычислить для всех i =1,…,n : i! Вычислить для всех i =1,…,n : a i = Вычислить сумму всех членов a i 32 Москва, 2011 г. Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 32 из 47

Для вычисления x i воспользуемся методом бинарного умножения x 1x 2 2x 3 x 4 3x 5 x 6 x 7 x 8 4 x 9 x 10 x 11 x 12 x 13 x 14 x 15 x 16 xixi 33 Москва, 2011 г. Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 33 из 47

Параллельное вычисление всех требуемых i! ? 34 ? Москва, 2011 г. Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 34 из 47

=16! i! 35 Москва, 2011 г. Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 35 из 47

Для вычисления i! воспользуемся аналогичным методом =12! ! 36 Москва, 2011 г. Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 36 из 47

Для вычисления i! воспользуемся аналогичным методом =14! ! 37 Москва, 2011 г. Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 37 из 47

Шаг Процессор 1Процессор 2Процессор 3Процессор Новые операции Москва, 2009 г. Параллельные методы и алгоритмы: Методы построения параллельных программ © Якобовский М.В. Вычисление всех факториалов до 8! включительно 38 из 6038

Шаг Процессор 1Процессор 2Процессор 3Процессор Новые операции Москва, 2009 г. Параллельные методы и алгоритмы: Методы построения параллельных программ © Якобовский М.В. Вычисление всех факториалов до 8! включительно 39 из 6039

Шаг Процессор 1Процессор 2Процессор 3Процессор Новые операции Москва, 2009 г. Параллельные методы и алгоритмы: Методы построения параллельных программ © Якобовский М.В. Вычисление всех факториалов до 8! включительно 40 из 6040

Шаг Процессор 1Процессор 2Процессор 3Процессор Новые операции Москва, 2009 г. Параллельные методы и алгоритмы: Методы построения параллельных программ © Якобовский М.В. Вычисление всех факториалов до 8! включительно 41 из 6041

Шаг Процессор 1Процессор 2Процессор 3Процессор Новые операции Москва, 2009 г. Параллельные методы и алгоритмы: Методы построения параллельных программ © Якобовский М.В. F=1; for(i=2;i

Шаг Процессор 1Процессор 2Процессор 3Процессор Новые операции Москва, 2009 г. Параллельные методы и алгоритмы: Методы построения параллельных программ © Якобовский М.В. Шаг Процессор 1Процессор 2Процессор 3Процессор 4 12! !4! !6!7!8! из 6043

p=n Ускорение и эффективность при p=n Москва, 2011 г. Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 44 из 47

Определены классы рассматриваемых вычислительных систем Представлены модели параллельных программ Представлен ряд способов организации взаимодействия последовательных процессов Представлен алгоритм, обладающий низкой эффективностью, но высоким быстродействием Заключение Москва, 2011 г. Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 45 из 47

Сколько нужно процессоров для вычисления суммы ряда за время 2 + q, где q – константа Какие преимущества и недостатки присущи синхронным и асинхронным методам обмена данными? Приведите примеры алгоритмов обладающих эффективностью больше 100%. Есть ли процессорные инструкции P(S) и V(S)? Вопросы для обсуждения Москва, 2011 г. Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 46 из 47

Якобовский М.В. д.ф.-м.н., проф., зав. сектором «Программного обеспечения многопроцессорных систем и вычислительных сетей» Института прикладной математики им. М.В.Келдыша Российской академии наук mail: web: Контакты Москва, 2011 г. Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 47 из 47