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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Определение семафора Целочисленная неотрицательная переменная Две атомарные операции V(S) –Увеличивает значение S на 1 P(S) –Если S положительно, уменьшает S на 1 –Иначе ждет Семафоры Москва, 2009 г. Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 16 из 31

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

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

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

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

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

Параллельный алгоритм Москва, 2009 г. Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. Вычислить для всех i =1,…,n : x i Вычислить для всех i =1,…,n : i! Вычислить для всех i =1,…,n : a i = Вычислить сумму всех членов a i 22 из 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 Москва, 2009 г. Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 23 из 31

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

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

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

Параллельный алгоритм Москва, 2009 г. Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. Вычислить все x i : Вычислить все i! : Вычислить все a i :- надо n процессоров Вычислить сумму всех a i : 2 27 из 31

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

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

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

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