46798 (Анализ эффективности MPI-программ), страница 4

Поэтому важно создать такие средства для получения характеристик эффективности MPI-программ, которые могли бы быть доступны пользователям на любых многопроцессорных ЭВМ.

Целью данной дипломной работы является создание экспериментальной системы отладки эффективности MPI-программ.

Входными данными для нее будут трассы, создаваемые DVM-системой для функциональной отладки MPI-программ. В этих трассах отражены обращения к MPI-функциям и времена их работы. Для получения характеристик, аналогичных тем, которые выдаются для DVM-программ, от программиста потребуется дополнительная информация о том, какие вычисления являются параллельными, а какие последовательными (дублированными на каждом процессоре). Эти указания должны быть оформлены таким образом, что их наличие в MPI-программе не мешало ее правильному и эффективному выполнению на тех ЭВМ, где отсутствует данная система отладки эффективности MPI-программ. Таким же образом должны оформляться и средства описания тех интервалов выполнения программы, для которых требуется отдельно собирать все характеристики эффективности.

Этапы работы анализатора.

В работе анализатора можно выделить следующие этапы.

Этап 1

Обработка трасс со всех процессоров и вычисление для каждого интервала и каждого процессора следующих характеристик:

Основные характеристики и их компоненты

Коэффициент эффективности (Parallelization efficiency) равен отношению полезного времени к общему времени использования процессоров.

Время выполнения (Execution time).

Число используемых процессоров (Processors).

Общее время использования процессоров (Total time) - произведение времени выполнения (Execution time) на число используемых процессоров (Processors).

Полезное время (Productive time) – прогнозируемое время выполнения на одном процессоре

Потерянное время (Lost time).

Коммуникации (Communication) и все компоненты.

Простои (Idle time).

Разбалансировка (Load_Imbalance).

Потенциальные потери из-за синхронизации (Synchronization) и все компоненты.

Потенциальные потери из-за разброса времен (Time_variation) и все компоненты.

Характеристики выполнения программы на каждом процессоре

Потерянное время (Lost time) - сумма его составляющих – потерь из-за недостаточного параллелизма (User insufficient_par), системных потерь из-за недостаточного параллелизма (Sys insufficient_par), коммуникаций (Communication) и простоев (Idle time).

Простои на данном процессоре (Idle time) - разность между максимальным временем выполнения интервала (на каком-то процессоре) и временем его выполнения на данном процессоре.

Общее время коммуникаций (Communication).

Реальные потери из-за рассинхронизации (Real synchronization).

Потенциальные потери из-за разброса времен (Variation).

Разбалансировка (Load_imbalance) вычисляется как разность между максимальным процессорным временем (CPU+MPI) и соответствующим временем на данном процессоре.

Время выполнения интервала (Execution_time).

Полезное процессорное время (User CPU_time).

Полезное системное время (MPI time).

Число используемых процессоров для данного интервала (Processors).

Времена коммуникаций для всех типов коллективных операций

Реальные потери из-за рассинхронизации для всех типов коллективных операций.

Потенциальные потери из-за рассинхронизации для всех типов коллективных операций.

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

Этап 2

Подготовка текстового представления вычисленных характеристик. Такое представление упрощает первоначальный анализ характеристик при запуске параллельной программы на удаленной ЭВМ.

Этап 3

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

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

5.3 Устройство анализатора

Итак, анализатор состоит из трех основных компонент.

Первая – сбор информации по трассе. Вторая – анализ собранных данных. Третья – визуализация.

5.3.1 Сбор трассы

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

Далее полученные данные поступают на вход модулям анализа и сбора характеристик.

5.3.2 Анализ

В соответствии с описанной в пункте 4.2 методикой, вся программа будет разбита на систему интервалов, точнее дерево интервалов. Корнем дерева будет вся программа, она считается интервалом нулевого уровня.

Далее в соответствии с вложенностью интервалы первого уровня и т.д.

Как указать границы интервалов?

Для этого используются пара функций MPI_Send() и MPI_Recv() для указания начала интервала, и такая же пара для указания его окончания. При этом посылка и прием сообщения происходят самому себе и от самого себя (имеется ввиду, что в качестве номера отправителя/получателя используется номер самого процесса). Кроме того, тэг сообщения имеет следующий вид:

TAG = 0x(aa)(id)(aa/bb).

Тэг является четырехбайтным целым числом. Первый байт у «нашего» тэга – это 0xaa. Это позволяет отличить его от обычных посылок/приемов сообщений. Последний байт может быть 0xaa – символизирует начало интервала, 0xbb – конец интервала. Внутри специальный идентификатор интервала (2 байта), его можно использовать, например, для того, чтобы отдельно выделить итерации цикла.

Такой способ выделения был выбран потому, что:

• он всегда попадает в трассировку (некоторые специальные функции вроде MPI_Pcontrol() в текущей версии трассировщика не попадают).

• занимает относительно немного времени (порядка 100 тиков процессора).

• прост в использовании и не требует дополнительных средств, помимо стандартных MPI-функций.

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

Далее по этим тэгам среди всех событий будут найдены те, которые являются границами интервалов и будут определены их идентификаторы.

Для этого вводится специальный класс:

class Margin

{

public:

Margin(bool ,unsigned long ,int ,unsigned int ,int);

friend bool operator <( const Margin& s1, const Margin& s2)

bool enter_leave;

unsigned long time;

int identity;

unsigned int proc;

unsigned int scl;

};

И функция:

vector<Margin>* createMargins(void);

которая и вычисляет=> определяет необходимые границы вместе со всеми параметрами.

После определения границ, создается структура дерево, в которой хранятся все данные обо всех интервалах.

Кратко об используемых структурах данных.

Создан специальный класс tree:

class tree

{

public:

static int Intervallevel; // current interval level

static int IntervalID; // current interval ID

long index;

int level; // Interval level

int EXE_count;

int source_line;

string source_file;

int ID;

//Characteristics for every interval

unsigned long Exec_time;

unsigned long Productive_time;

double Efficiency;

unsigned long CPU_time;

unsigned long MPI_time;

unsigned long Lost_time;

unsigned long Comm_time;

unsigned long SendRecv_time;

unsigned long CollectiveAll_time;

unsigned long Idle_time;

unsigned long AllToAll_time;

unsigned long Time_variation;

unsigned long Potent_sync;

unsigned long T_start;

vector < pair >* cmp_pairs;

//for intelval's tree

tree* parent_interval;

int count;

vector nested_intervals;

vector Procs;

};

Этот класс содержит информацию обо всех характеристиках данного интервала, описанных в 5.2. Кроме того, в нем есть информация о родительском узле дерева, а также обо всех «листьях-потомках».

В этом классе в качестве вспомогательного используется класс Processors.

class Processors

{

public:

unsigned long enter_time;

unsigned long leave_time;

unsigned int number;

unsigned long MPI_time;

unsigned long SendRecv_time;

unsigned long CollectiveAll_time;

unsigned long Idle_time;

unsigned long AllToAll_time;

unsigned long CPU_time;

unsigned long Comm_time;

unsigned long Time_variation;

unsigned long Potent_sync;

unsigned long T_start;

};

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

Далее, после определения границ интервалов, происходит создание дерева интервалов. В этом дереве и будет храниться информация обо всех интервалах.

Класс tree включает методы, которые и собирают информацию из структур, собранных на трассе.

Первая группа характеристик собирается в функции

Leave(int line, char* file, long index,unsigned int proc,unsigned long time).

• MPI_time Используем – getMPITimebyProc();

• SendRecv_time - getSendRecvCommunicationTimebyProc();

• CollectiveAll_time – getCollectiveAllByProc();

• AllToAll_time - getAllToAllByProc();

• Potent_sync - getPotentSyncByProc();

• Time_variation - getTimeVariationByProc();

• T_start - getNonBlockedTimebyProc();

Вычисление характеристик.

getMPITimebyProc() – Происходит суммирование интервалов времени, занятых под MPI-функции (интервалы получаются как разность между временем выхода и входа в MPI-функцию).

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

getPotentSyncByProc() – Вычисляется по-разному для операций одиночных посылок/приемов сообщений и коллективных операций. Сюда входят все случаи, когда Recv был выдан раньше Send’а. Эти «задержки» как раз и суммируются. Для коллективных же операций суммируется время «задержки» старта операции на некоторых процессорах.

getTimeVariationByProc() – Вычисляется время, рассинхронизации окончания коллективной операции.

getNonBlockedTimebyProc() – Вычисляется аналогично getMPITimebyProc(), только суммируются времена работы только не блокирующих операций.

Все эти характеристики собираются на каждом процессоре для данного интервала. Прототип всех функций одинаков:

getFunction(unsigned long enter_time, unsigned long leave_time, unsigned int proc).