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

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

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

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

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

Структура транспьютера T-800 Москва, 2012 г. Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 6

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

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

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

Уточнение круга рассматриваемых систем Системы на основе объединенных сетью типовых вычислительных узлов – системы с распределенной оперативной памятью Системы с доступом всех процессоров к общей оперативной памяти Сеть передачи данных Москва, 2012 г. Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 10 процессор оперативная память вычислительный узел

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

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

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

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

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

Что будет напечатано? Москва, 2012 г. Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. Нить1 { a=a+2 } int a=1; Нить2 { a=a+3 } Нить3 { print(a) } 16 a=?

Что будет напечатано? Москва, 2012 г. Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. Нить1 { a=a+2 } Нить2 { a=a+3 } Нить3 { print(a) } 6 int a=1; 17

Что будет напечатано? Москва, 2012 г. Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 3 Нить1 { a=a+2 } Нить2 { a=a+3 } Нить3 { print(a) } int a=1; 18

Что будет напечатано? Москва, 2012 г. Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 6 ? 4 ? 3 Нить1 { a=a+2 } Нить2 { a=a+3 } Нить3 { print(a) } int a=1; 19 Процессор1 2+1=3 2 Процессор2 3+1=

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

Что будет напечатано? Москва, 2012 г. Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 6 Нить1 { P(S) a=a+2 V(S) V(S1) } Нить2 { P(S) a=a+3 V(S) V(S2) } Нить3 { P(S1) P(S2) print(a) } int a=0; Sem S=1, S1=0, S2=0; 21

ускорение параллельного алгоритма S(p)=T(1)/T(p) Ускорение и эффективность параллельных алгоритмов Москва, 2012 г. эффективность использования вычислительной мощности E(p)=S(p)/p Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 22 Может ли ускорение превышать число процессоров ? S(p)> p E(p)>100%

ускорение параллельного алгоритма S(p)=T(1)/T(p) Ускорение и эффективность параллельных алгоритмов Москва, 2012 г. эффективность использования вычислительной мощности E(p)=S(p)/p Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 23 Может ли ускорение превышать число процессоров ? S(p)> p E(p)>100% Да, если учитывать влияние аппаратных особенностей вычислительной системы

ускорение параллельного алгоритма S(p)=T(1)/T(p) Ускорение и эффективность параллельных алгоритмов Москва, 2012 г. эффективность использования вычислительной мощности E(p)=S(p)/p Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 24 Может ли ускорение превышать число процессоров ? S(p)> p E(p)>100% Да, если выбран неудачный последовательный алгоритм

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

–В последовательном алгоритме выполняется больше операций, чем в параллельном Может ли быть S(p)>p ? Москва, 2012 г. Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. сортировка половины массива сортировка половины массива слияние отсортированных половинок массива 26 Сортировка массива

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

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

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

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

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

Для вычисления 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 32 Москва, 2012 г. Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 32

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

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

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

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

Шаг Процессор 1Процессор 2Процессор 3Процессор 4 1 2!= !=(2!) (3)4!=(1 2) (3 4) 3 Новые операции Москва, 2009 г. Параллельные методы и алгоритмы: Методы построения параллельных программ © Якобовский М.В. Вычисление всех факториалов до 4! включительно 37 из 60 Шаг Процессор 1Процессор 2Процессор 3Процессор 4 1 2!= !=12 34!=

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

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

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

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

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

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

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

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

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