Основы параллельного программирования Посыпкин Михаил Анатольевич. - презентация

1 Основы параллельного программирования Посыпкин Михаил Анатольевич

2 Параллельное программирование Приложения требуют увеличения производительности компьютеров. Производительность процессора и памяти ограничена физическими характеристиками применяемых материалов. Многие задачи содержат независимые компоненты, которые могут решаться одновременно (т.е. параллельно).

3 Параллельное программирование Перечисленное приводит к естественному решению – увеличивать число компонент оборудования, участвующего в решении задач. В частности, увеличивается число функциональных устройств одного процессора и общее число процессоров.

4 Спектр задач параллельного программирования Математическое моделирование: Газовая и гидро-динамика. Химическая физика. Процессы в полупроводниках. Имитационное моделирование в экономике. Биология. Оптимизация: Дискретное и линейное программирование. Общая задача нахождения экстремума. Оптимальный поиск: Дискретная оптимизация. Распознавание образов. Автоматическая верификация и доказательство теорем.

5 Параллелизм внутри процессора Различные функциональные устройства. Конвейерная обработка. Векторные сопроцессоры. Многоядерные процессоры.

6 Многопроцессорный параллелизм В решении задачи принимает участие несколько (более одного) процессоров, взаимодействующих между собой. CPU

7 Виды многопроцессорного параллелизма. Общая память Распределенная память

8 Иерархия памяти Регистры Кэш 1-го уровня Кэш 2(3)-го уровня Оперативная память Дисковая память

9 Аппаратные ресурсы МСЦ Общая память: HP V-Class HP Superdome Гибридная память: MVS-1000M (768 x Alpha 21264) MVS 15000BM (768 x IBM Power 970) кластеры Athlon, Xeon, IBM

10

11 Архитектура HP-Superdome

12 Архитектура HP-Superdome: общая орагнизация: ccNuma ячейка коммутатор ячейка коммутатор

13 Архитектура HP-Superdome: Ячейка – SMP система CPU Контроллер Memory I/O Коммутатор

14

15 Характеристики MareNostrum Пиковая производительность: 42,35 TFlops 4812 PowerPC 970FX 2.2 GHz Оперативная память: 9,6 Tb Дисковая память: 236 Tb Коммуникации Myrinet (вычисления) Gigabit Ethernet (загрузка, управление)

16 Архитектура 29 x IBM Rack Blade Center Blade Server JS320

17 Библиотеки общего назначения Проблемно- ориентирован ные библиотеки Традиционны е языки программиро вания Специальные расширения языков Внутрипроцес сорный параллелизм Многопроцес сорный параллелизм ++--

18 Средства параллельного программирования Общая памятьРаспределенная память Системные средства threadsпроцессы + сокеты Языки C/C++, Fortran 95 HPF, DVM, mpC, Charm ++, Occam Специальные библиотеки и пакеты OpenMPMPI PVM

19 ОСНОВНЫЕ ХАРАКТЕРИСТИКИ ПРОИЗВОДИТЕЛЬНОСТИ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ

20 Ускорение -время параллельных вычислений -время последовательны вычислений

21 Производительность пиковая и реальная Пиковая производительность – максимальное количество операций, которые вычислительное устройство может выполнить за единицу времени. Реальная производительность – количество операций, которое вычислительное устройство реально выполняет. Загруженность = (реальная производительность)/(пиковая производительность)

22 Производительность системы из нескольких устройств Имеется n устройств - реальная производительность i-го устройства - пиковая производительность i-го устройства - загруженность i-го устройства Производительность такой системы:

23 Ускорение Еслито

24 Измерение ускорения -время параллельных вычислений -время последовательны вычислений

25 Линейное и «сверхлинейное» ускорение Линейное ускорение: S = n. Эффект «сверхлинейного» ускорения: наблюдаемое ускорение больше числа процессоров: S > n. Причина – не учитывается загруженность процессоров, либо изменение количества операций.

26 Эффект увеличения памяти При больших объемах данных включаются более медленные слои иерархии памяти => увеличиваются задержки => снижается загруженность процессоров.

27 Закон Амдала -доля последовательных вычислений -общий объем работы

28 Эффективность Эффективность – отношение ускорения к числу процессоров. Показывает насколько эффективно используются аппаратные ресурсы.

29 Тест LINPACK (LU-разложение): кластер из 8 компьютеров Эффективность и ускорение при разном количестве процессоров. (информация с сайта Кемеровского ГУ)

30 Информационные зависимости Зависимость по данным: 1: a = 1; 2: b = a; 1 2 Зависимость по управлению: 1: if(a) { 2: x = c + d; 3: y = 1; 4: } 1 23

31 Граф зависимостей Операции, соединенные путем из дуг, не могут выполняться одновременно. 1 Другие операции могут выполняться одновременно при наличии требуемых функциональн ых устройств.

32 Концепция неограниченного параллелизма CPU..... Количество процессоров неограниченно. Концепция может применяться для исследования максимально возможного ускорения.

33 Упрощенная модель параллельной машины с общей памятью CPU MEMORY Процессоры работают синхронно по шагам: на каждом шаге выполняется операция (выборка операндов + арифметичекая операция + запись в память). Шаг занимает 1 такт.

34 Лемма Брента Пусть q – число операций алгоритма, выполнение каждой операции занимает в точности одну единицу времени (такт), t – время выполнения на системе с достаточным числом одинаковых процессоров, то на системе, содержащей n процессоров, алгоритм может быть выполнен за время, не превосходящее t + (q – t)/n.

35 Асимптотические свойства формулы Брента

36 CPU ICPU II Количество CPU не ограничено

37 Пусть для бесконечного числа процессоров на i-м шаге выполнялось s i операций, тогда при наличии n процессоров потребуется не более операций.