- дата последнего обновления 08.02.10 -

Оглавление

1     Введение

2     Генерация файла трассы

3     Представление программы в виде иерархии интервалов

4     Компиляция и прогон программы

5     Подготовка файла конфигурации процессорной системы

6     Опции командной строки предиктора

7     Результаты работы предиктора

8     Протокол работы предиктора

Приложение 1. Тест на определение производительности процессоров 

1  Введение

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

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

Эффективность выполнения параллельных программ на многопроцессорных ЭВМ с распределенной памятью определяется следующими основными факторами:

•  степенью распараллеливания программы - долей параллельных вычислений в полном объеме вычислений;

•  равномерностью загрузки процессоров во время выполнения параллельных вычислений;

•  временем, необходимым для выполнения межпроцессорных обменов;

• степенью совмещения межпроцессорных обменов с вычислениями;

• эффективностью выполнения вычислений на каждом процессоре.

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

Точность предсказания определяется следующими реализационными ограничениями.

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

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

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

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

2         Генерация файла трассы

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

• Разбиение программы на интервалы, (т.е. выделение тех частей программы, времена выполнения которых интересуют пользователя);

• Компиляция программы;

• Прогон программы.

3         Представление программы в виде иерархии интервалов

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

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

Разбиением программы на интервалы пользователь управляет при ее компиляции. Он может задать такие режимы, при которых интервалами будут параллельные циклы, либо последовательные циклы, которые содержат внутри себя параллельные циклы, либо все последовательные циклы вообще, либо отмеченные им в программе последовательности операторов. Опции компиляторов, управляющие разбиением программы на интервалы, описаны в руководствах по их использованию. (“Компилятор C-DVM. Руководство пользователя”, “Компилятор Fortran-DVM. Руководство пользователя”).

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

4         Компиляция и прогон программы

После разбиения программы на интервалы необходимо выполнить следующие шаги:

• конвертацию программы;

• компиляцию и сборку программы;

• запуск программы на выполнение.

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

1.      Для конвертации, компиляции и сборки программы служат команды:

dvm  c  <имя_C-DVM-программы>
dvm  f  <имя_F-DVM-программы>

2.      Для запуска DVM-программы с накоплением трассировки для предиктора используется команда:

dvm runpred [<processor>] <имя_DVM-программы>

где:

<processor> - топология процессоров, т.е. число процессоров по каждому из измерений решетки процессоров. Является не обязательным параметром,
и по умолчанию считается топологией одного процессора.

Результат работы:

• если не указан параметр <processor>, то в текущей директории создается файл <имя_DVM-программы>.ptr с накопленной трассировкой.

• если указан параметр <processor>, то в текущей директории создаются файлы типа “<имя_DVM-программы>n_n.ptr” (где n меняется от 0 до количества процессоров, заданных параметром <processor>). В каждом таком файле накоплена трассировка для n-ого процессора из топологии.

Замечание 1. При выполнении данной команды автоматически устанавливаются следующие параметры:

Параметры PreUnderLine, PostUnderLine и MaxTraceLevel являются указанием LIB-DVM на то, что не надо накапливать в трассе строки, состоящие из подчеркиваний, а также не надо трассировать вложенные вызовы функций LIB-DVM, что приводит к существенному сокращению размера файла трассы.

Замечание 2. При запуске на одном процессоре параллельной программы, в которой явно указана требуемая ей конфигурация процессоров  или предусмотрена динамическая настройка на выделенное количество процессоров, необходимо задать соответствующую «виртуальную» процессорную систему с помощью параметров IsUserPS и UserPS.

Например, для задания «виртуальной» процессорной системы 2*2 значения параметров будут следующими:

Замечание 3. Для того чтобы в трассу попала информация об интервалах, надо в файле “pred_trc.par” задать значение Is_DVM_STAT = 1.

Замечание 4. Для того чтобы в трассу попала информация о векторе весов распределения массива с помощью WGTBLOCK, надо в файле “pred_trc.par” задать значение LoadWeightTrace = 1.

5         Подготовка файла конфигурации процессорной системы

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

Концептуально работа предиктора подразделяется на три основных этапа:

• чтение трассировки, извлечение из нее информации о структуре интервалов, о последовательности вызовов функций системы поддержки, о тех входных и возвращаемых параметрах вызовов функций, которые необходимы для их моделирования, а также о времени, затраченном на выполнение каждого из вызовов;

• моделирование выполнения программы на целевой машине на основе полученной на предыдущем этапе информации и вычисление временных характеристик выполнения программы на каждом из интервалов;

• запись вычисленных характеристик в файл формата HTML.

Конфигурационная информация, записанная в файле “predictor.par” определяет характеристики целевой (моделируемой) многопроцессорной системы и  имеет следующую структуру:

cluster = mvs;

// search optimal processor set   0=off   1=euristik

search=0;

// Cluster properties: 

//     string = { [int 'x']string [,[int 'x']string]*} | float

//     string.CommType = ethernet | transputer | myrinet (num_channels) | string.CommType

// Communication characteristics (mks)

//     string.TStart = float

//     string.TByte = float

mvs = {512 x mvsP2};

mvs.CommType = myrinet (1);

mvs.TStart = 7;

mvs.TByte = 0.004;

mvsP2 = {2 x mvsP1};

mvsP2.CommType = myrinet (1);

mvsP2.TStart = 1;

mvsP2.TByte = 0.001;

mvsP1 = 1.00;

Предложения, начинающиеся с “//” являются комментариями.

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

Параметр search позволяет выполнить поиск оптимальной конфигурации процессоров, исходя из общего количества процессоров, заданных в кластере (параметром cluster и параметрами дальнейшего уточнения его структуры). По умолчанию параметр search равен 0 (отключен). Эвристический поиск оптимальной конфигурации задается значением 1. Результаты предсказания программы на оптимальной конфигурации записываются в файл best.html.

Дальнейшая структура кластеров, описывается при помощи двух способов

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

• Если кластер состоит из одного процессора, то надо указать отношение его производительности к производительности процессора инструментальной машины, на которой была получена трассировка для предиктора. Если такой параметр не указан, то по умолчанию считается равным 1. Для определения производительности процессоров разработан тест (см. Приложение 1.)

Если кластер состоит из подкластеров, то для него надо указать параметр CommType, который задает тип коммуникационной сети, связывающей подкластеры между собой. Значение ethernet говорит о том, что система подкластеров объединена в сеть с шинной организацией; значение transputer указывает на то, что для коммуникаций между подкластерами используется система транспьютерного типа; а значение myrinet( num_channels ) используется в случаях, когда передача данных между подкластерами осуществляется по нескольким каналам сети myrinet. При этом возможен вариант, когда для задания CommType используется имя коммуникационной среды другого кластера и тогда в качестве параметров новой среды возьмутся такие же параметры. Это следует рассматривать как сокращение записи параметров.

TStart и TByte являются характеристиками коммуникационной среды между подкластерами и равны соответственно ее латентности и пропускной способности. Эти характеристики используются для вычисления времен передач сообщений. Например для сети рабочих станций при вычислении времени передачи n байт используется линейная апроксимация

T = TStart + n * TByte,

где:

6         Опции командной строки предиктора

Запуск предиктора может осуществляться в режиме командной строки командой:

predictor <par_file> <trace_file> <html_file> [<processor>]

где:

Все параметры командной строки, кроме <processor> являются обязательными.

Для удобства запуска предиктора существует команда:

dvm pred [матрица процессоров] <имя_DVM-программы>

Выполнение команды управляется переменными окружения (см. файл dvm.bat):

·        Pred_sys - имя конфигурационного файла, описывающего целевую машину;

·        Pred_vis - имя программы Web–браузера.

Предиктор проверяет наличие в текущей директории файла <имя_DVM-программы>.ptr. Если файл есть, то он используется.

Если файла нет, то ищется файл <имя_DVM-программы>0_0.ptr, по которому определяется: на каком количестве процессоров запускалась задача, и идет объединение соответствующих трасс (<имя_DVM-программы>0_0.ptr и jac<имя_DVM-программы>1_1.ptr) в <имя_DVM-программы>.ptr. Если при объединении какой-то трассы не хватает, то выдается сообщение об ошибке. Далее предиктор работает с трассой <имя_DVM-программы>.ptr.

Результат работы:

• файл best.html, если был указан параметр поиска оптимальной конфигурации процесоров (search = 1 в файле конфигурации процессорной системы).

• файл <имя_DVM-программы><[матрица процессоров]>.html с характеристиками выполнения программы в виде html-страницы.

• Если задан Web - браузер (например, Netscape), то он автоматически вызывается и открывает страницу с результатами предсказания выполнения <имя_DVM-программы> на указанной матрице процессоров. Выполнение команды в этом случае завершается после завершения работы браузера.

7         Результаты работы предиктора

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

Любая DVM-программа делится на интервалы, которые подразделяются на четыре типа. Выполнение всей программы целиком рассматривается как интервал самого высокого (нулевого) уровня, и является отдельным типом интервала. Этот интервал может включать в себя несколько интервалов следующего (первого) уровня. Такими интервалами могут быть параллельные циклы, называемые параллельными интервалами (PAR), последовательные циклы, называемые последовательными интервалами (SEQ), а также любые отмеченные программистом последовательности операторов, называемые пользовательскими интервалами (USER). Интервалы первого уровня могут в свою очередь включать в себя интервалы второго уровня, и т.д.

Каждый фрагмент HTML-файла, содержащий характеристики интервала, начинается с «желтого поля», состоящего из ключа интервала (File - имя файла с исходным текстом DVM-программы, Line - номер строки, в которой расположен первый оператор интервала, Type -типом и,  возможно, заданным целочисленным номером – Expr). Кроме того, «желтое поле» содержит две характеристики интервала: Count - количеством входов в интервал и Level – уровень вложенности интервала.

По окончании моделирования для каждого интервала вычисляются и выдаются на HTML-странице интегральные характеристики выполнения программы на данном интервале. Ниже приведен список характеристик “голубого поля”:

Processors – топология целевой процессорной системы;

Efficiency – коэффициент эффективности, равный отношению Productive time к Total time;

Execution time – время выполнения, равное максимальному значению среди времен выполнения данного интервала на каждом процессоре;

Total time – общее время использования процессоров, то есть произведение Execution time на число процессоров;

Productive time – полезное время, равное сумме Productive time:CPU, Productive time:SYS  и Productive time:I/O:

Productive time:CPU	–	полезное процессорное время (за вычетом системных расходов);
Productive time:SYS	–	полезные системные расходы;
Productive time:I/O	–	сумма времен выполнения выданных в интервале операций ввода-вывода, без учета затрат на коммуникации;

Lost time – суммарное потерянное время на интервале:

Lost time:Insufficient parallelism		–	общее время потерь из-за недостаточного параллелизма (дублирования вычислений на нескольких процессорах):
	Lost time:Insufficient parallelism:USR	–	потери из-за недостаточного параллелизма (за вычетом системных потерь);
	Lost time:Insufficient parallelism:SYS	–	системные потери из-за недостаточного параллелизма;
Lost time:Communication		–	общее время коммуникаций, то есть сумма времен коммуникаций всех коллективных операций:
	Lost time:Communication:SYN	–	время потерь из-за рассинхронизации коммуникационных операций;
Lost time:Idle		–	время простоя процессора;

Load Imbalance – неравномерность загрузки процессоров при параллельных вычислениях;

Synchronization – время потерь из-за рассинхронизации коллективных операций;

Overlap – общее время перекрытия обменов сообщениями и вычислений.

Xарактеристики  “зеленого поля” – это характеристики коллективных операций (I/O, Reduction, Shadow, Remote access и Redistribution); по каждой из операций выдаются: число операций, время, затраченное операцией на коммуникации, время потерь из-за рассинхронизации коммуникационных операций и время перекрытия обменов сообщениями и вычислений.

 8   Протокол работы предиктора

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

Файл можно просмотреть с помощью обычного текстового редактора.

 Приложение 1. Тест на определение производительности процессоров

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

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

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

Тест на производительность называется power.cdv находится в папке demo. Он состоит из нескольких интервалов. На каждом интервале замеряется некоторый объем вычислений. Для того чтобы получить производительность процессоров на каждом интервале, пользователь должен запустить программу (командой dvm run [<processor>] <имя_DVM-программы>). В результате получится в файле proc_power.txt столбец времен работы процессора при вычислениях в интервале. Такие столбцы строятся (либо пользователем, либо заранее системой) для каждой ЭВМ (всех целевых и инструментальной).

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

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