Предсказатель
эффективности DVM-программ |
- дата последнего обновления 20.10.00 -
Оглавление
1
Функции предсказателя
2
Состав предсказателя
3
Подход и принципы реализации
предсказателя
3.1 Представление программы в виде иерархии интервалов
3.2 Обработка трассировочной информации
3.2.1 Сбор информации об интервалах
3.2.2 Моделирование параллельного выполнения DVM-программы
3.2.3 Вычисление основных временных характеристик
Предсказатель предназначен для анализа и отладки производительности DVM-программ без использования реальной параллельной машины (доступ к которой обычно ограничен или сложен). С помощью предсказателя пользователь имеет возможность получить предсказанные временные характеристики выполнения его программы на MPP или кластере рабочих станций с различной степенью подробности.
Производительность параллельных программ на многопроцессорных ЭВМ с распределенной памятью определяется следующими основными факторами:
Существенным достоинством DVM-подхода по сравнению с подходами, базирующимися на явном использовании коммуникационных библиотек (MPI, PVM), является то, что в любой момент выполнения программы на любом процессоре всегда известно, какой участок программы выполняется - последовательный или параллельный. Кроме того, известны все точки программы, в которых выполняются операции, требующие синхронизации процессоров. Поэтому имеется возможность количественно оценить влияние на эффективность выполнения программы каждого из четырех перечисленных выше факторов. Невозможно последовательные вычисления отличить от параллельных и определить степень распараллеливания программы, когда параллельная программа представлена в виде системы взаимодействующих процессов, при явном использовании коммуникационных библиотек.
Возможность различать последовательные и параллельные участки программы при ее выполнении на многопроцессорной ЭВМ, позволяет предсказателю выдать пользователю следующие основные показатели выполнения параллельной программы:
Время выполнения это максимальное из времен выполнения программы на каждом процессоре.
Для вычисления главной характеристики параллельного выполнения – коэффициента эффективности следует вычислить два времени. Во-первых, полезное время, это время, которое потребуется для выполнения программы на однопроцессорной ЭВМ. Во-вторых, общее время использования процессоров, которое вычисляется как произведение времени выполнения на число процессоров. Коэффициент эффективности равен отношению полезного времени к общему времени использования процессоров.
Разница между общим временем использования процессоров и полезным временем представляет собой потерянное время. Если программист не удовлетворен коэффициентом эффективности выполнения своей программы, то он должен проанализировать составляющие части потерянного времени и причины их возникновения.
Существуют следующие составляющие потерянного времени:
Для оценки суммарных потенциальных потерь, которые могут возникнуть из-за неодновременного запуска коллективных операций на разных процессорах, должна вычисляться и выдаваться пользователю специальная характеристика – синхронизация. Основная причина этих потерь, на устранение которой должен быть нацелен программист – разбалансировка загрузки процессоров при выполнении параллельных циклов. Для оценки возможных потерь из-за разбалансировки программисту выдается обобщенная характеристика – разбалансировка. Рассинхронизация может возникать не только из-за разбалансировки, но также из-за различий во временах завершения выполнения на разных процессорах одной и той же коллективной операции, вызванных особенностями ее реализации на конкретной параллельной ЭВМ. Для оценки величины такой потенциальной рассинхронизации программисту выдается специальная характеристика – разброс времен завершения коллективных операций.
Важной характеристикой, отражающей степень совмещения межпроцессорных обменов с вычислениями, является время перекрытия обменов вычислениями.
Для более детального анализа эффективности программы пользователю будут предоставлены средства разбиения выполнения программы на интервалы и возможности получения характеристик производительности для каждого из них.
Предсказатель представляет собой систему обработки трассировочной информации собранной LIB-DVM системой во время выполнения программы на рабочей станции (в случае нескольких рабочих станций существует утилита объединения нескольких трассировок в одну). Эта система по данным трассировки и параметрам заданным пользователем вычисляет и выдает ему предсказанные временные характеристики выполнения данной программы на MPP или кластере рабочих станций, используя библиотеку моделирующую параллельное выполнение DVM-программ.
3 Подход и принципы реализации предсказателя
3.1 Представление программы в виде иерархии интервалов
Выполнение программы можно представить в виде последовательности чередующихся интервалов ее последовательного и параллельного выполнения. По умолчанию, вся программа является одним интервалом. Также интервалами являются интервалы определенные пользователем средствами языков C-DVM и Fortran-DVM (Ограничение: при использовании предсказателя не допускается задание целочисленного выражения с интервалом внутри параллельного цикла).
Имеется также возможность задать режим компиляции, при котором интервалами являются все параллельные циклы, либо все последовательные циклы, которые содержат внутри себя параллельные циклы, либо все последовательные циклы вообще.
Пользователь может также разбить любой интервал на несколько интервалов или объединить несколько соседних (по порядку выполнения) интервалов в новый единый интервал, т.е. представить программу в виде иерархии интервалов нескольких уровней (самый высокий уровень всегда имеет вся программа целиком - уровень 0).
Механизм разбиения программы на интервалы служит для более детального анализа поведения программы во время ее выполнения. При просмотре результатов с помощью предсказателя, пользователь имеет возможность задать глубину детализации, то есть исключить из рассмотрения интервалы, начиная с некоторого уровня вложенности.
3.2 Обработка трассировочной информации
Для упрощения дальнейшего описания введем следующие понятия. Интервал будем называть простым, если он не содержит внутри себя других интервалов (вложенных) интервалов. Интервалы, включающие в себя вложенные интервалы, будем называть составными. Во время обработки трассировочной информации сразу несколько интервалов являются активными интервалами (в которые вошли, но не вышли). Тот из них, который имеет самый низкий уровень, будем называть текущим интервалом.
Накопленная в файле при выполнении DVM-программы трассировочная информация обрабатывается на рабочей станции следующим образом.
3.2.1 Сбор информации об интервалах
Во время обработки трассировочной информации собирается информация о каждом интервале (тип интервала, номер интервала, номер уровня вложенности, количество вхождений в интервал, имя файла с исходным текстом программы и номер строки в нем, соответствующей началу интервала), а для текущих интервалов вычисляются следующие времена, характеризующие его выполнение на однопроцессорной ЭВМ (при этом производительность процессора берется равной производительности процессоров целевой системы):
При сборе этих времен также учитываются излишние накладные расходы на вывод трассировочной информации в файл во время выполнения программы на рабочей станции.
3.2.2 Моделирование параллельного выполнения DVM-программы
Производится моделирование основных функций LIB-DVM, используя трассировочную информацию накопленную в файле и параметры многопроцессорной системы заданные пользователем. Это позволяет определить времена необходимые для выполнения межпроцессорных обменов, а также информацию о распределении вычислений между процессорами. Таким образом, производится вычисление следующих времен, характеризующих параллельное выполнение интервалов (эти характеристики являются обобщенными для всех процессоров):
При выходе из составных интервалов осуществляется коррекция всех перечисленных в пунктах 3.2.1 и 3.2.2. характеристик (кроме характеристики Idle). При этом каждая характеристика любого интервала i-го уровня вычисляется посредством добавления к ней одноименных характеристик всех интервалов (i+1)-го уровня, входящих в этот интервал.
После коррекции, а также при выходе из простых интервалов производится вычисление характеристики разбалансировка (Load_Imbalance) (Определяется, используя процессорные времена параллельных вычислений данного интервала, как сумма по всем процессорам разностей между максимальным временем (на каком-то процессоре) и временем на текущем процессоре).
3.2.3 Вычисление основных временных характеристик
Эти характеристики относятся ко всей параллельной программе и ее интервалам. В соответствии с заданной пользователем степенью детализации (уровень вложенности интервалов) может быть выдана следующая информация о предсказанной эффективности выполнения программы: