Устройство анализатора. 
Сравнительный анализ эффективности инструментария MPI и NET для задачи суммирования

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

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

Сбор трассы

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

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

Анализ

В соответствии с описанной в пункте 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* 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).

Собранные «элементарные» характеристики, затем собираются в более общие по всему интервалу.

Первая используемая для этого функция — это функция Integrate ().

В этой функции собираются следующие характеристики:

• · CPU_time
• · MPI_time
• · SendRecv_time
• · CollectiveAll_time
• · AllToAll_time
• · Comm_time (Общее время коммуникаций)
• · Idle_time (время бездействия)
• · Potent_sync
• · Time_variation
• · T_start

Все они уже являются характеристиками всего интервала.

Далее происходит вычисление уже не общих, а сравнительных характеристик. Зная все эти компоненты на каждом процессоре для интервала, мы находим процессоры с максимальным, минимальным значением по времени, а также среднее значения всех характеристик.

После функции Integrate () вычисляется полезное время calculateProductive (), потом время запуска — calculateExecution (),

эффективность распараллеливания — efficiency (), и, наконец, потерянное время — calculateLost ().

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

Пример. Текстовый файл с итоговыми характеристиками.

Interval (LineNumber = 153 SourceFile = exch. c) Level=0 EXE_Count=1.

—-Main Characteristics—;

Parallelization Efficiency 0.978 833.

Execution Time 2.79 975.

Processors 4.

Total Time 8.319 900.

Productive Time 8.143 794 (CPU MPI).

MPI время на одном процессоре считается полезным, а на остальных — потерянным.

Lost Time 0.176 106.

• —-MPI Time 0.173 490
• —-Idle Time 0.2 616

Communication Time 0.76 563.

• *****SendRecv Time 0.13 295
• *****CollectiveAll Time 0.63 268
• *****AllToAll Time 0.0

Potential Sync. 0.68 763.

Time Variation 0.1 790.

Time of Start 0.0.

—-Comparative Characteristics—;

Tmin Nproc Tmax Nproc Tmid.

Lost Time 0.33 087 3 0.60 057 0 0.44 026.

Idle Time 0.0 1 0.898 0 0.654.

Comm. Time 0.6 597 3 0.34 854 0 0.19 140.

MPI Time 0.32 259 3 0.59 159 0 0.43 372.

Potential Sync. 0.1 800 0 0.29 369 3 0.17 190.

Time variation 0.161 1 0.607 3 0.447.

Time of Start 0.0 0 0.0 0 0.0.

Для каждого интервала выдается следующая информация:

• · имя файла с исходным текстом MPI-программы и номер первого оператора интервала в нем (SourceFile, LineNumber);
• · номер уровня вложенности (Level);
• · количество входов (и выходов) в интервал (EXE_Count);
• · основные характеристики выполнения и их компоненты (Main characteristics);
• · минимальные, максимальные и средние значения характеристик выполнения программы на каждом процессоре (Comparative characteristics);

При выдаче характеристик их компоненты располагаются в той же строке (справа в скобках), либо в следующей строке (справа от символов «*» или «-»).

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