Система автоматизации распараллеливания: отображение на мультипроцессор Выполнил: студент 528 группы Лойко Михаил Юрьевич Научный руководитель: профессор, д. ф.-м. наук Крюков Виктор Алексеевич

Система автоматизации распараллеливания DVM рекомендации OpenMP рекомендации Последовательная программа Пользователь program compute_pi parameter (n = 1000) integer i double precision w,x,sum,pi,f,a f(a) = 4.d0/(1.d0+a*a) w = 1.0d0/n … end program compute_pi parameter (n = 1000) integer i double precision w,x,sum,pi,f,a f(a) = 4.d0/(1.d0+a*a) w = 1.0d0/n … end program compute_pi parameter (n = 1000) integer i double precision !$OMP PARALLEL DO PRIVATE(x), HARED(w) w,x,sum,pi,f,a f(a) = 4.d0/(1.d0+a*a) w = 1.0d0/n … end program compute_pi parameter (n = 1000) integer i double precision !$OMP PARALLEL DO PRIVATE(x), HARED(w) w,x,sum,pi,f,a f(a) = 4.d0/(1.d0+a*a) w = 1.0d0/n … end Анализ программы База данных OpenMP эксперт OpenMP эксперт DVM эксперт DVM эксперт program compute_pi parameter (n = 1000) integer i double precision DVM PARALLEL w,x,sum,pi,f,a f(a) = 4.d0/(1.d0+a*a) w = 1.0d0/n … end program compute_pi parameter (n = 1000) integer i double precision DVM PARALLEL w,x,sum,pi,f,a f(a) = 4.d0/(1.d0+a*a) w = 1.0d0/n … end

Цель дипломной работы: «Эксперт для мультипроцессора» Входные данные*: Дерево циклов с описанием циклов. Описание цикла содержит: указание на переменную цикла; первое, последнее значение, шаг; наличие в цикле операторов ввода-вывода, побочных выходов и т.п.; оценка трудоемкости одного витка цикла; признак тесной вложенности; список обращений к массивам и переменным; список зависимостей. Список массивов (и простых переменных). Для каждого массива: идентификатор; размер по каждому измерению; список обращений к массиву. Вариант задачи: список пар (переменная, значение). Система автоматизации распараллеливания Выходные данные: Вариант распараллеливания программы**. Вариант представляет собой программу со вставленными OpenMP директивами. Оценка эффективности для данного варианта распараллеливания и данного варианта запуска: параметры производительности каждого цикла, программы в целом и эффективности распараллеливания. Информация, объясняющая, почему выбрано данное распараллеливание. * Входные данные представляют собой Базу Данных, работа с которой для «Эксперта» осуществляется посредством интерфейса. ** Заносится в Базу Данных посредством интерфейса.

Стандарт OpenMP Интерфейс OpenMP задуман как стандарт для программирования на масштабируемых SMP-системах в модели общей памяти (shared memory model). Последовательная секция Параллельная секция Последовательная секция Процесс исполнения OpenMP программы. В OpenMP используется модель параллельного выполнения fork/join. Программа начинает выполняться как один процесс, который в ОpenMP называется главной нитью (master thread). Этот процесс выполняется последовательно до тех пор, пока он не дойдет до первой параллельной конструкции (в простейшем случае - области, заключенной между директивами PARALLEL и END PARALLEL). В этот момент создается "бригада" (team) нитей, а "бригадиром" для нее является главная нить. После завершения выполнения параллельной конструкции нити бригады синхронизируются, а выполнение продолжает только главная нить. Естественно, в программе может быть много параллельных конструкций; соответственно бригады нитей могут образовываться не один раз. !$OMP PARALLEL !$OMP END PARALLEL

При составлении алгоритмов работы «Эксперта» были учтены следующие возможности OpenMP: возможность работы с циклами (директива DO); возможность обработки редукционных переменных (директива REDUCTION); возможность исполнять часть кода внутри цикла в «естественном» порядке (директива ORDERED); возможность приватизировать переменные (директива PRIVATE); возможность образовывать конвейер посредством OpenMP директив (директива IF(), BARRIER и функции для определения количества нитей и порядковый номер текущей нити дают возможность создать конвейер с помощью директив OpenMP); возможность отмены синхронизациями между параллельными циклами (директива NOWAIT). Система автоматизации распараллеливания Основные аспекты работы «Эксперта для мультипроцессора» Во время работы «Эксперт» перебирает все возможные варианты параллелизма циклов и варианты локализации переменных. «Эксперт» пытается распараллелить циклы: не имеющие зависимостей по данным; имеющие редукционные переменные; имеющие скалярные зависимости; имеющие зависимости по данным в массиве. Однако «Эксперт» не пытается распараллелить циклы, следующих видов: содержащие ввод/вывод; содержащие выход из цикла.

Основная цель «Эксперта» - нахождение для последовательной программы набора директив OpenMP такого, что ускорение параллельной программы при заданном варианте работы программы будет максимально. Сравнение вариантов распараллеливания программы происходит посредством оценочной функции. В итоге работа «Эксперта» сводится к нахождению схемы распараллеливания, для которой оценочная функция минимальна. Система автоматизации распараллеливания Практическая реализация «Эксперта для мультипроцессора» Работа Эксперта для мультипроцессора разделена на 4 стадии: 1)разделение всех циклов программы на Потенциально Параллельные Циклы и Циклы Неподдающиеся Распараллеливанию, обозначение видов Потенциально Параллельных Циклов и предварительное фиксирование набора вариантов локализации переменных; 2)перебор всевозможных вариантов распараллеливания программы, предварительное фиксирование наилучшего варианта параллелизма; 3)перебор вариантов локализаций программы, фиксирование наилучшей схемы распараллеливания, подсчет ускорения; 4)расстановка директив OpenMP, соответствующих наилучшей схеме распараллеливания, в программу, формирование отчета. База Данных Предварительный анализ Выбор варианта распараллеливания Выбор варианта локализации Внесение конечных комментариев

Реализованный прототип «Эксперта для мультипроцессора» представляет собой проект на языке С++, общий объем которого превышает 1800 строк. Работа «Системы автоматизации распараллеливания» была протестирована 4 примерах, показавших работу «Эксперта»: по созданию параллельных регионов в случае вложенности циклов; по созданию конвейера средствами OpenMP; по созданию директив ORDERED при зависимости данных в массиве; по проверке условий по пропуску синхронизации между двумя параллельными циклами. В качестве результата формируется файл с выходной программой и файл, описывающий пошаговые действия «Эксперта» с аргументированием принятых решений по распараллеливанию, а также выдается прогноз ускорения программы. Все выходные программы были протестированы на работоспособность на комплексе REGATTA. Система автоматизации распараллеливания Заключение.