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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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