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

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

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

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

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

Задачи, которые приходится решать при создании параллельной программы Анализ зависимостей и собственно распараллеливание алгоритма и программы Выяснение деталей поведения компонентов многопроцессорной системы Балансировка нагрузки на процессоры и коммуникации

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

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

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

Краткое описание системы Parus (продолжение) Программа описывается как сеть из вершин: истоков внутренних вершин стоков Чтение и инициализаци я данных Обработка данных Запись результатов

Краткое описание системы Parus Алгоритм решаемой задачи представляется как ориентированный граф: вершины соответствуют вычислениям рёбра соответствуют зависимости по данным Описание графа хранится в текстовом файле, по которому затем строится 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 ""

Структура описания ребра графа Данные разбиты на кусочки (чанки), каждый из которых отвечает за свой фрагмент массива. Принимающей стороной фрагменты могут быть собраны в другом порядке. Int a[]; Int b[]; Принимающая вершина

Пример ребра 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 Тестирование многопроцессорной системы Создание параллельной программы и её компиляция Исполнение параллельной программы

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

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

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

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

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

Тест производительности процессоров Для каждого процессора измеряется время перемножения матриц определённого размера. Результат записывается как вектор в файл (элемент вектора - время работы каждой 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 байт

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

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

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

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

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

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

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

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

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

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

Задержки при передаче

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

Принцип работы комбинированного режима В случае 2-х одинаковых по времени работы номеров вершин после работы процедуры динамического режима выбирается тот, который присутствует в файле расписания для данной MPI-нити

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

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

Время расписания T node – время старта вершины на MPI-нити t node – время исполнения вершины при условии старта к моменту T node

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

Определение времени исполнения кода вершины MPI-нитью ExecTime и NodeTime вычисляются по тем же формулам, что и в случае динамического режима назначения вершин по MPI-нитям

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

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

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

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

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

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

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

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

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

Частотный фильтр звуковых сигналов Часто требуется для предварительной обработки данных Цель – создать параллельную реализацию фильтра частот в сигнале с использованием системы PARUS. Вычислительно сложная задача

Частотный фильтр звуковых сигналов на основе свёртки Операция свёртки реализуется с помощью алгоритма быстрой свёртки (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 по адресу:

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