Прототип системы автоматического распараллеливания Parus Докладчик:Алексей Сальников Докладчик: Алексей Сальников Московский Государственный Университет им. М.В. Ломоносова, факультет ВМиК

Участники проекта. Королёв Лев Николаевич Попова Нина Николаевна Сазонов Александр Карев Максим Мусатова Елена Сальников Алексей

Цели проекта Выяснить возможность программирования в терминах графов. Разработать набор программных утилит, для этой цели. Исследовать возможность автоматического распараллеливания.

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

Предлагаемый подход Человек пишет программу в терминах графа изначально. По графу и данным о производительности процессоров и сети строится расписание. Граф преобразуется в программу с MPI вызовами. Полученная программа выполняется на процессорах.

Компоненты и связи

parser – по C программе строит граф алгоритма. graph2c++ – по графу алгоритма строит программу на C++ с MPI вызовами. graph2sch – по графу алгоритма и результатам тестов строит статическое расписание выполнения программы на многопроцессорной системе. network_test – производит тестирование коммуникаций в многопроцессорной системе. processor_test – производит тестирование процессоров в многопроцессорной системе. viewer – отображает граф алгоритма на мониторе компьютера. compiler – обычный компилятор MPI с помощью которого компилируется программа.

Автоматическое получение графа алгоритма. source Анализатор Граф

Пример 1 for(a=0; a

Пример 1 d[0]=0;d[2]=4;d[1]=1;d[3]=9; b=1; c=d[2]*b/a; a=b+1; Визуальное представление графа

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

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

Типы информационных зависимостей Прямая зависимость по данным «out-in» Прямая зависимость по данным «out-in» Обратная зависимость по данным «in-out» Обратная зависимость по данным «in-out» Зависимость по выходам «out-out» Зависимость по выходам «out-out»

Самый простой и очевидный тип зависимости между операторами: первый меняет данные, второй - читает измененные данные. Прямая информационная зависимость a = 1; b=a+1; Меняем «a» Читаем «a» «a»«a»«a»«a»

Первый читает данные, второй - меняет данные. Очевидно, порядок менять нельзя - изменится результат. Передача данных не происходит. Обратная информационная зависимость b=a+1; a = 1; Меняем «a» Читаем «a» «»

Это тип зависимости возникает при повторном изменении данных. Зависимость по выходам Зависимость по выходам a = 1; a=2; a = 1 a = 1 a = 2 Последовательныйвариант a = 1; a = 2; Параллельныйвариант a = 2 a = ?

Подобный тип зависимости может вызывать передачу данных, однако не всегда. Зависимость по выходам без передачи данных a = 1; a=2; Присваиваем 1 Присваиваем 2 Нет передачи

Зависимость по выходам с передачей данных a=1;... if (b == 1){ a=2; } c=a+2;

Зависимость по выходам с передачей данных a = 1; c=a+2; «a»«a»«a»«a»... if (b==1){ a=2; } «a»«a»«a»«a»

Пример графа (Один шаг метода Гаусса решения уравнения теплопроводности ).

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

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

Расписание исполнения графа алгоритма.

Описание Расписания Список элементов si=(Ti, Pi, ti), где: Ti – задача, описанная в вершине графа. Pi – процессор, исполняющий задачу Ti ti – время старта задачи Ti.

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

Решение задачи о расписании. Задача решается генетическим алгоритмом, где хромосома – само расписание, а ген элемент si, факт загрузки задачи на pi процессор в момент времени ti. В процессе работы алгоритма отметаются недопустимые расписания. Функция качества – длина расписания, время за которое выполнится программа.

Процесс исполнения графа алгоритма на многопроцессороной системе.

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

Функции остальных процессоров. Инициализируют передачу данных другим процессорам по команде от управляющего процессора. Вызывают узел графа. В узле графа принимают данные по ребрам от других узлов графа на других процессорах. Выполняют код узла. Накапливают в памяти выработанные данные необходимые другим узлам графа.

Узлы графа.

Рёбра графа

Расписание

Пример протокола обмена сообщениями между процессорами.

Тестирование многопроцессорной системы.

Тесты производительности процессоров и сети. Производительность процессора проверяется на неоднократном локальном перемножении матриц фиксированной размерности. Производительность сети измеряется на обменах типа точка - точка в 4-х различных режимах:

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

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

Выбор узла графа вызываемого на процессоре. node_weight – объём выполняемого кода узлом графа алгоритма в числе эталонных операций. processor_weight – время за которое процессор выполнит num_operation эталонных операций. link_weight(message_length) – время за которое будет передано через сеть message_length байт. edge_weight – число байт которое необходимо передать по данному ребру графа алгоритма. N – число входящих рёбер.

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

Результаты

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

Пример 2 (поиск минимума в wav файле)

На данном примере для запуска на 4-х процессорах по отношению к последовательной версии программы достигнуто ускорение 54/34. ( 1,58)

Перспективы и пути развития.

Что предполагается сделать в будущем. Изменить узел графа алгоритма, с целью борьбы с детерменизмом. Усовершенствовать редактор графа алгоритма, с целью предоставления возможности редактирования графа через графический интерфейс. Подключение всей системы в целом как узла GRID (Подключение авторизации, и набора эталонных задач). Добавить циклы и условное ветвление. Добавить перепланировщик графа, который будет учитывать особенности архитектуры.

Узел графа алгоритма (в будущем. ) code – код содержит описания переменных и начальную инициализацию данных необходимых узлу, обработку данных, утилизацию данных если они больше не нужны. Data change block – код связанный с получением или передачей данных. Генерируется автоматически.

Авторы приносят благодарности члену корреспонденту РАН, профессору Льву Николаевичу Королёву и доктору физ. мат. наук, доценту Нине Николаевне Поповой за консультации при создании данной системы. Данная работа выполняется в рамках студенческой лаборатории Intel МГУ. При поддержке гранта РФФИ и гранта РФФИ

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