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

Что происходит? Вычислительная мощность суперкомпьютеров быстро растет Примеров успешного полноценного использования суперкомпьютеров немного В среднем вычислительная мощность суперкомпьютеров используется не более чем на несколько процентов 2

Кто виноват? Вычислительная мощность суперкомпьютера не более чем прямая сумма мощностей большого числа входящих в его состав процессоров или процессорных ядер Современные алгоритмы не могут автоматически использовать такую «распределенную» мощность 3

Что делать? Изучать известные методы анализа и создания параллельных алгоритмов Создавать новые методы использования многопроцессорных систем для решения актуальных значимых задач 4

Кризис эффективности Вычислительная мощность суперкомпьютеров велика, но: –Она образована суммой мощностей множества исполнительных устройств На протяжении ряда лет увеличение производительность компьютера автоматически означало снижение времени работы существующих программ. Теперь это не так: –Последовательные программы не могут работать на суперкомпьютерах быстрее 5

Кризис эффективности Время вычислительных систем, обладающих существенной производительностью и имеющих в своем составе только один процессор прошло, и, по всей видимости, безвозвратно Автоматическое преобразование последовательных программ в параллельные невозможно Необходимо знать существующие и развивать новые методы решения задач на многопроцессорных системах 6

Уточнение круга рассматриваемых систем Системы на основе объединенных сетью типовых вычислительных узлов – системы с распределенной оперативной памятью Системы с доступом всех процессоров к общей оперативной памяти Графические ускорители ПЛИС Нейрокомпьютеры Другие … 7

Многопроцессорные системы с распределенной памятью 8

Многопроцессорные системы с общей памятью 9

Уточнение круга рассматриваемых алгоритмов Слабо взаимодействующие последовательные процессы 10

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

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

Свойства канала передачи данных T(n)=n*T байта + T латентности Gbit Ethernet Infiniband 13

Свойства канала передачи данных T(n)=n*T байта + T латентности Gbit Ethernet Число передаваемых байт 14

Свойства канала передачи данных T(n)=n*T байта + T латентности Число передаваемых байт Infiniband 15

Синхронный метод Send(адрес данных, размер, номер процессора) Recv(адрес данных, размер, номер процессора) Асинхронные методы –Небуферизованный ASend(адрес данных, размер, номер процессора) ARecv(адрес данных, размер, номер процессора) ASync –Буферизованный ABSend(адрес данных, размер, номер процессора) Методы передачи данных 16

A=3 Send(&A) A=5 Синхронный B=4 Recv(&B) Print(B) Send Recv Print(B) A=5 B=4 A=3 Результат 3 17

A=3 АSend(&A) A=5 Асинхронные B=4 АRecv(&B) Print(B) Send ASend Recv ARecv Print(B) A=5 B=4 Результат 3 ? 4 ? 5 A=3 18

A=3 АSend(&A) Async() A=5 Асинхронные B=4 АRecv(&B) Print(B) ASync Send ASend Recv ARecv Print(B) A=5 B=4 Результат 3 ? 4 A=3 19

A=3 АSend(&A) Async() A=5 Асинхронные B=4 АRecv(&B) Async() Print(B) Результат 3 ASync Send ASend ASync Recv ARecv Print(B) A=5 A=3 B=4 20

A=3 АBSend(&A) A=5 Асинхронные буферизованные B=4 АRecv(&B) Async() Print(B) Результат 3 Send(&buf) ABSend ASync Recv ARecv Print(B) A=5 buf=A A=3 B=4 21

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

ускорение параллельного алгоритма S(p)=T(1)/T(p) Ускорение и эффективность параллельных алгоритмов Ускорение параллельного алгоритма относительно наилучшего последовательного S * (p)=T * /T(p) E * (p)=S * (p)/p эффективность использования процессорной мощности E(p)=S(p)/p 23

Да: –Плохой последовательный алгоритма –Влияние аппаратных особенностей вычислительной системы Может ли быть S(p)>p ? 24

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

Все элементарные операции (+ - * / ) выполняются за время с Все операции выполняются точно, результат не зависит от порядка их выполнения Определить сумму конечного ряда 26

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

Параллельный алгоритм Вычислить для всех i =1,…,n : x i Вычислить для всех i =1,…,n : i! Вычислить для всех i =1,…,n : a i = Вычислить сумму всех членов a i 28

Для вычисления 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 29

Для вычисления i! воспользуемся аналогичным методом =16! i! 30

Для вычисления i! воспользуемся аналогичным методом =12! ! 31

Для вычисления i! воспользуемся аналогичным методом =14! ! 32

Параллельный алгоритм Вычислить все x i : Вычислить все i! : Вычислить все a i :- надо n процессоров Вычислить сумму всех a i : 2 33

p=n Ускорение и эффективность при p=n

Определены понятия ускорения и эффективности параллельных алгоритмов Представлен ряд способов организации взаимодействия последовательных процессов Представлен алгоритм, обладающий низкой эффективностью, но высоким быстродействием Заключение 35

Литература… Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. - СПб.: БХВ- Петербург, Грегори Р. Эндрюс - Основы многопоточного, параллельного и распределенного программирования. "Вильямс ", 2003 Роберт Седжвик - Фундаментальные алгоритмы на C. Части Анализ. Структуры данных. Сортировка. Поиск. Алгоритмы на графах Языки программирования. Редактор Ф.Женюи. Перевод с англ. В.П.Кузнецова. Под ред. В.М.Курочкина. М:."Мир", 1972 Э. Дейкстра. Взаимодействие последовательных процессов. Дональд Э. Кнут Искусство программирования 36

Литература… Учебные курсы Интернет Университета Информационных технологий Гергель В.П. Теория и практика параллельных вычислений. Лекции в форме видео-конференций Гергель В.П. Основы параллельных вычислений. Немнюгин С.А. Основы параллельного программирования с использованием MPI. Крюков В.А., Бахтин В.А. Параллельное программирование с OpenMP. Дополнительные учебные курсы: Воеводин В.В. Вычислительная математика и структура алгоритмов

Литература Ресурсы Internet