Система разработки и поддержки исполнения параллельных программ Сальников А. Н. Факультет ВМиК МГУ

Введение Краткое описание системы PARUS Граф-программа как MPI-программа Тестирование многопроцессорной системы Создание расписания для статического режима работы Примеры использования системы PARUS

Несмотря на большое число высокоуровневых средств поддержки параллельного программирования создание специализированных средств, учитывающих особенности определённого класса задач - актуально.

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

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

Высокоуровневые средства параллельного программирования Расширение существующих языков программирования параллельными конструкциями DVM mpC Cilk Т-система Charm++ Специализированные библиотеки и языки PETSc НОРМА PARUS Автоматическое распараллеливание программ HPF IBM Visual AGE C/C++/FORTRAN90 compiler Intel C/C++ compiler PARUS

Введение Краткое описание системы PARUS Граф-программа как MPI-программа Тестирование многопроцессорной системы Создание расписания для статического режима работы Примеры использования системы PARUS

Краткое описание системы Parus Алгоритм решаемой задачи представляется как ориентированный граф: вершины соответствуют вычислениям рёбра соответствуют зависимости по данным.

Способ написания программ в виде графа потока данных Разработчик параллельной программы по своему усмотрению формирует участки программ (последовательные фрагменты кода) и схему их взаимодействия. Фрагменты (вершины): предназначены к исполнению на одном из процессоров, записываются на алгоритмическом языке высокого уровня (С++). обмены данными между последовательными фрагментами (рёбра) явно описываются, но реализуются автоматически, через вызовы MPI-функций.

Граф-программа Алгоритм описывается как сеть из вершин: истоков внутренних вершин стоков Описание графа хранится в текстовом файле, по которому затем строится C++ код c MPI вызовами. Чтение и инициализаци я данных Обработка данных Запись результатов

Описание вершины number 1 type 1 weight 100 layer 2 num_input_edges 1 edges ( 1 ) num_output_edges 1 edges ( 2 ) head "head" body "node" tail "" Код вершины (фрагменты кода) Вес вершины – выражается как число эталонных операций

Структура описания ребра графа Массивы принимаемой и передаваемой информации по рёбрам графа разбиваются на непересекающиеся фрагменты (чанки). Принимающей стороной фрагменты могут быть собраны в другом порядке.

Структура описания ребра графа

Пример текстового описания ребра number 2 weight 2 type GRAPH_NONE num_var 1 num_send_nodes 1 send_nodes ( 2 ) num_recv_nodes 1 recv_nodes ( 5 ) name "*data_out" type GRAPH_DOUBLE left_offset "0" right_offset "window_size+F_LEN" name "*data_out" type GRAPH_DOUBLE left_offset "0" right_offset "window_size" Границы в чанка в массиве могут вычисляться динамически

Этапы работы с системой PARUS Тестирование многопроцессорной системы Создание параллельной программы и её компиляция Исполнение параллельной программы

Этап создания граф-программы разработчиком Исходный файл граф-программы Преобразователь в C++ c MPI вызовами С++ MPI-программа Редактор графа Исходный файл С-программы Анализатор зависимостей

Этап предварительного тестирования многопроцессорной системы Тест сети Тест процессоров Результаты теста Монитор Сетевой информации

Этап исполнения параллельной программы Исходный файл граф-программы Построитель расписаний Результаты тестов Откомпилированная граф-программа Результаты работы Расписание

Введение Краткое описание системы PARUS Граф-программа как MPI-программа Тестирование многопроцессорной системы Создание расписания для статического режима работы Примеры использования системы PARUS

Механизм исполнения граф программы PARUS формирует систему MPI-процессов, которые осуществляют исполнение граф-программы. В процессе исполнения программы на многопроцессорной системе производится динамическое назначение вершин по MPI-процессам минимизируются времена передач данных минимизируется время обработки вершины при выборе свободного процессора. Данные по рёбрам передаются асинхронно

Представление вершины и рёбер Вершинам приписан вес (число эталонных операций) и уровень от истока. Далее они становятся С++ функциями. В зависимости от расположения данных рёбра с приписанным весом (количеством байт) соответствуют копированию памяти или MPI функциям передачи данных.

Глобальные атрибуты граф-программы head (для граф программы целиком) – декларация типов данных актуальных для полученной MPI-программы. root – код, исполняющийся сразу на всех MPI- процессах до запуска на процессе кода какой- либо вершины tail – код, исполняющийся сразу на всех MPI- процессах по окончании обработки всех вершин.

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

Структура вершины графа head – код содержит описания переменных и начальную инициализацию данных, необходимых узлу. body – код выполняемый после получения всех необходимых данных. tail – код содержит действия по очистке памяти и утилизации данных.

Редактор графа

Редактирование вершины

Редактирование расписаний

Механизм передачи данных между 2-мя вершинами

Разделение MPI-процессов по ролям Управляющий процесс: Выбирает вершину для назначения на процесс Выбирает ребро для инициализации передачи данных Остальные процессы: Исполняют вершины Хранят наработанные вершинами данные Пересылают и принимают данные по рёбрам другим MPI-процессам

Введение Краткое описание системы PARUS Граф-программа как MPI-программа Тестирование многопроцессорной системы Создание расписания для статического режима работы Примеры использования системы PARUS

Тесты особенностей многопроцессорной системы Реализованы тесты производительности процессоров и производительности сетевых обменов. Тестовые программы созданы с использованием библиотеки MPI.

Тестирование коммуникационной среды Тестируется: Пропускная способность канала Зависимость времени передачи сообщения от размера сообщения Влияние фоновых передач сообщений на время передачи целевого сообщения

Тесты системы PARUS С помощью системы тестов измеряется время передачи сообщений между машинами в сети. По результатам работы каждого теста формируется 4-мерная модель производительности сети (длина сообщения, передающий процессор, принимающий процессор, время передачи).

Тесты системы PARUS В системе создано 6 различных MPI тестов сетевых обменов, выбираемых разработчиком. Результаты теста используются динамическим загрузчиком.

Тесты сетевых обменов: виды тестов all_to_all - выяснение стрессоустойчивости сети; одновременный неблокированный обмен сообщениями с целью определения устойчивости коммуникационного оборудования к критическим нагрузкам one_to_one - определение пропускной способности каналов связи; блокированная передача от i-й машины к j-й, остальные молчат async_one_to_one - определение полнодуплексности каналов; неблокированный обмен MPI-сообщениями

Тесты сетевых обменов: виды тестов send_recv_and_recv_send – усредненная производительность обменов в обе стороны. test_noise - то же, что async_one_to_one, но добавлен параметр шума test_noise_blocking - измеряется время блокирующих передач на фоне шума

Машины, на которых проводилось тестирование MBC1000-M 768 процессоров Alpha (кластерная архитектура) IBM eServer pSeries 690 (Регата) 16 процессоров Power4+ ( NUMA архитектура) Sun Fujitsu PRIMEPOWER 850 Server 16 процессоров SPARC64-V (архитектура с общей памятью)

Визуализация результатов тестирования

Иллюстрация загруженности каналов связи многопроцессорной системы МВС-1000М, задействовано 15 процессоров, длина передаваемого сообщения 1000 байт

Визуализация результатов тестирования(МВС 15000)

Введение Краткое описание системы PARUS Граф-программа как MPI-программа Тестирование многопроцессорной системы Создание расписания для статического режима работы Примеры использования системы PARUS

Режимы назначения вершин на обработку MPI- прцессами, реализованные в PARUS Динамический Назначение вершин происходит согласно текущей ситуации Комбинированный Предоставляет возможность учитывать пожелания разработчика граф-программы по назначению вершины на MPI-процесс в спорных ситуациях Статический Назначение вершин происходит согласно составленному заранее расписанию

Время исполнения вершины вычисляется на основе подсчёта доли операций в вершине к доле операций при решении эталонной задачи. Среди списка ожидающих выполнения вершин, выбирается та, которая на данном MPI-процессе будет вычислена за минимальное время.

Учёт времени работы вершины при назначении вершины на MPI-процесс Среди списка ожидающих выполнения вершин, выбирается та, которая на данной MPI нити будет вычислена за минимальное время.

Динамический режим (вычисление времени) ExecTime вычисляется следующим образом: TransferTime вычисляется следующим образом:

Учёт задержек при передаче

Задержки с этапа тестирования Точное значение времени передачи, полученное после тестирования сети. Задаётся набором матриц по числу длин сообщений, указанных в тесте. (i,j) – время передачи от i-ой нити к j-ой

Учёт задержек при передаче данных Как результат этапа тестирования строится набор матриц для дискретных длин сообщений На этапе анализа программы определяется задержка для тройки (посылающий MPI-процесс, принимающий MPI-процесс, длинна сообщения) с использованием матриц. Величина задержки для длин сообщений не вошедших в одну из троек вычисляется интерполяцией.

Принцип построения расписания Под расписанием будем понимать вектор S элементов S node =(proc j, rank node ) rank node - порядковый номер вершины на MPI-процессе Для расписания определена функция времени исполнения граф-программы:

T node – время старта вершины на MPI- процессе t node – время исполнения вершины при условии старта к моменту T node NodeTime – вычисляется также, как и для динамического режима.

Определение времени запуска вершины на MPI-процессе Функция StartTime – носит рекурсивный характер. Parents(node) – множество вершин из которых существует ребро входящее в node

Параметры Генетического алгоритма для построения расписания Хорошее расписание ищется генетическим алгоритмом Расписание – хромосома GlobalTime – функция качества Порядковый номер и номер нити – ген

Генетический алгоритм Популяция – некоторое подмножество множества допустимых расписаний Мутации – случайное изменение порядкового номера вызова вершины на MPI-нити или перемещение вершины на другую MPI-нить. (число мутаций задаётся в параметрах) Скрещивания производятся в позиции хромосомы, которая соответствует целиком одной из вершин графа. Номер позиции выбирается как равномерно распределённая случайная величина.

Генетический алгоритм На каждом шаге по результатам скрещиваний и мутаций порождается случайное число особей. Из полученной популяции выбирается некоторое количество лучших особей с учётом случайного штрафа. Алгоритм останавливается в случае малого изменения функции качества на очередном шаге или по исчерпанию числа итераций.

Введение Краткое описание системы PARUS Граф-программа как MPI-программа Тестирование многопроцессорной системы Создание расписания для статического режима работы Примеры использования системы PARUS

Искусственная нейронная сеть (параллельный перцептрон) Частотный фильтр звуковых сигналов Распределённая операция над массивом Задача построения множественного выравнивания нуклеотидных последовательностей

Схема перцептрона Трёхслойная сеть: число входов колеблется от 500 до Активационная функция – экспоненциальная сигмоида

Распараллеливание перцептрона Каждый слой сети разделяется на группы. Нейроны, попадающие в одну группу, относятся к одной вершине графа. Рёбра между нейронами сливаются в одно ребро и превращаются в рёбра между группами.

Зависимость ускорения от числа входов по отношению к 2-процессорной реализации параллельного перцептрона

Результаты тестирования (число групп меньше числа процессоров)

Частотный фильтр звуковых сигналов на основе свёртки Операция свёртки реализуется с помощью алгоритма быстрой свёртки (FFT Convolution). Фактически обработка сигнала S с помощью фильтра K производится по формуле: Свойства свёртки позволяют разбивать сигнал на части, которые обрабатываются параллельно. Однако, вследствие удлинения сигнала на ядро свёртки, полученные сегменты необходимо стыковать в правильном порядке.

Частотный фильтр звуковых сигналов Ядро фильтра строится на основе sinc-функции (функции вида sin(x)/x). В силу поведения sinc-функции на бесконечности необходимо проводить её обрезание и оконное взвешивание.

Метод распараллеливания фильтра звуковых сигналов

Пример параллельного фильтра звуковых сигналов Фильтр встроен в систему анализа и обработки экспериментальных данных: (грант РФФИ ) Для работы фильтра в параллельном режиме используется машина Регата.

Распределённая операция над массивом чисел. Суммирование в виде дерева. массив делится n на частей размера m. Эти части независимо друг от друга суммируются, в результате получается n значений суммы. получившийся массив также делится на части размера не больше чем m и процедура повторяется.

Граф для распределённой операции Массив разбит для операции над 2-мя элементами.

Ускорение для распределённого суммирования на машине МВС1000-М

Эффективность для распределённого суммирования на машине МВС1000-М

Множественное выравнивание нуклеотидных последовательностей Выравнивание используется для моделирования эволюции живых организмов, предсказания генов, и других задач генетики AY TAGACGCGCTAGCTTCAGGTGTTAGTGTCCTTACGGACGTGGGGGTTCAAGTCCCCCCCC AY TAGAC---CTCAACTGAGGTCTTTTTTTATGCCTGAAATCCAGTGTTTATCTATCTTTCC MC2TRGC CAGACGCACTAGACTTAGGATCTAGCGTCTTT---GACGTAAGGGTTCAAGTCCCTTATC ECTRNAL TAGACACGCTACCTTGAGGTGGTAGTGCCCAATAGGGCTTACGGGTTCAAGTCCCGTCCT **** ** * *** * * *** * * * AY TCGCACCACGACTTT---AAAG--AATTGAACTAAAAATTCAAAAAGCAGTATTTCGGCG AY CGCTATATTAACTCTCTCAAGGTCAACC GATATCAACGTAC-ATCTACCAACA MC2TRGC CCCCACCA--ATTTT---GAATTTAACC------AGATTTTTCTGGTTTTTTATTTGAAA ECTRNAL CGGTACCA-AATTCC---AGAA--AA GAGACGCTGAAAAGC-GTCTTTTTTCG * * * ** * * AY AGTAGCG----CAGCTTGGTAGC- AY TAT MC2TRGC TTTTAAAATGTTATTTTAAGAAAT ECTRNAL TTTTG GTCCTGGT----

Парное выравнивание Под парным выравниванием 2-х нуклеотидных последовательностей будем понимать 2 одинаковые по длине последовательности символов: a,t,g,c, –, расположенные друг над другом aagtta aa–ttg aagtta aattg

Оптимальное парное выравнивание Задача – найти выравнивание, максимизирующее P(a,b) Ищем оптимальную расстановку «гэпов» (символов «–») Для выравнивания строк a и b введём функцию P(a,b), которая задаёт качество выравнивания:

Множественное выравнивание Оптимизация множественного выравнивания включает максимизацию числа одинаковых символов в столбцах при минимизации гэпов CACGACTTT---AAAG--AA ATTAACTCTCTCAAGGTCAA CA--ATTTT---GAATTTAA CA-AATTCC---AGAA--AA

Алгоритм построения множественного выравнивания. На третьем этапе по кластерному дереву от листьев к корню производятся парные выравнивания, где вставки из - можно вставлять только целиком для столбца группы. CACGACTTT---AAAG--AA ATTAACTCTCTCAAGGTCAA CA--ATTTT---GAATTTAA CA-AATTCC---AGAA--AA AY283774MC2TRGCAY283775ECTRNAL 1 2 3

Распараллеливание алгоритма множественного выравнивания За основу брался пакет muscle Распараллеливание производится на этапе построения выравнивания по дереву, самом ресурсоёмком. Параллелизм достигается за счёт параллельности построений парных выравниваний на ветках дерева.

Данные для тестирования задачи множественного выравнивания. Основу составила коллекция длинных терминальных повторов класса 5 (LTR5). Совместный проект института физико-химичесой биологии им. А.Н. Белозерского МГУ и Людвиговского института раковых исследований "Ludwig Institute for Cancer Research", грант CRDF RB01277-MO-2 Alexeevski A.V., Lukina E.N., Salnikov A.N., Spirin S.A. Database of long terminal repeats in human genome: structure and synchronization with main genome archives Proceedings of the fours international conference on bioinformatics of genome regulation and structure Volume 1. BGRS 2004, Novosibirsk, редакционно издательский отдел ИциГ СО РАН стр

Результаты тестирования Тестирование проводилось на машине Prime Power 850. В однопроцессорном варианте множественное выравнивание для ~1200 последовательностей длины ~1000 занимает 1 час 8 минут. В многопроцессорном варианте для 12 процессоров – 28 минут

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

Практическая значимость результатов диссертационной работы Практическая применимость и эффективность созданной системы (PARUS) показана на примере решения ряда модельных и практических задач на современных параллельных вычислительных системах (IBM pSeries 690, МВС- 1000м, и др.) Система PARUS, оформлена как проект с открытым исходным кодом и доступна в Internet ( )

Результаты диссертационной работы Разработан метод построения параллельных программ и язык описания программ как граф-схемы потока данных. Разработаны и реализованы алгоритмы управления процессом исполнения параллельной программы с учётом структуры программы, динамики обменов данными и текущего состояния многопроцессорной системы. На основе предложенных метода, языка и алгоритмов создана с истема поддержки этапов разработки и исполнения параллельных программ PARUS, в основном ориентированная на решение задач на графах.

Спасибо за внимание!

Цель анализатора Построить по C-программе граф зависимостей. Основной стратегией при построении графа по C-программе, является стратегия максимального разделения операций с целью получения наиболее широкого представления графа. (Максимизация параллелизма)

Ограничения на исходный код для анализатора зависимостей в C – программе Анализ текстов проводится в предположении статического распределения памяти. Работа производится только с одним исходным файлом. Не производится раскрытие тел функции, кроме функции main, условных операторов и циклов с невычислимыми на стадии компиляции границами.

Вычисление весов операторов Для элементарных операций вес выбирается из статистических соображений Для условных операторов вес вычисляется как сумма веса условия оператора и максимального значения веса одной из альтернатив. Вес линейного участка кода вычисляется как сумма весов совляющих его оператстаоров. К сожалению про число итераций цикла while как правило ничего сказать нельзя, поэтому вес цикла считается как вес его тела. Тоже самое относится и к циклу do while

Вычисление веса для цикла for for (I1=L1 ; I1