Анализатор производительности
параллельных программ
Предварительный дизайн
* 21 июня 2000 *


Оглавление

1 Функции АППП
2 Состав АППП
3 Подход и принципы реализации АППП

3.1 Подход и принципы реализации АППП
3.2 Сбор информации
3.3 Обработка информации

3.3.1 Вычисление характеристик выполнения на каждом процессоре
3.3.2 Вычисление характеристик рассинхронизации и разброса времен коллективных операций
3.3.3 Вычисление времени перекрытия обменов вычислениями
3.3.4 Вычисление сравнительных характеристик выполнения на разных процессорах
3.3.5 Вычисление основных характеристик


1 Функции АППП

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

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

  1. Степенью распараллеливания программы - долей объема параллельных вычислений в общем объеме вычислений;
  2. Равномерностью загрузки процессоров во время выполнения параллельных вычислений;
  3. Временем межпроцессорных обменов;
  4. Степенью совмещения межпроцессорных обменов с вычислениями.

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

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

Время выполнения это максимальное из времен выполнения программы на каждом процессоре.

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

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

При этом различаются следующие независимые компоненты потерянного времени:

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

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

2 Состав АППП

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

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

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

3 Подход и принципы реализации АППП

3.1 Подход и принципы реализации АППП

Выполнение программы можно представить в виде последовательности чередующихся интервалов ее последовательного и параллельного выполнения. По умолчанию, вся программа является одним интервалом. Также интервалами являются интервалы определенные пользователем средствами языков С-DVM и Fortran DVM.

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

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

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

3.2 Сбор информации

На каждом процессоре собирается и записывается в файл следующая информация:

  1. Информация о системе поддержки и аппаратно-программной среде
    (размерность многопроцессорной системы, количество процессоров, тип системы передачи сообщений).
  2. Информация о каждом интервале (тип интервала, номер интервала, номер уровня вложенности, количество вхождений в интервал, имя файла с исходным текстом программы и номер строки в нем, соответствующей началу интервала) и относящиеся к нему времена, наиболее важными из которых являются:
  1. Информация о временах выдачи и завершения операций, требующих синхронизации (редукция, обновление теневых граней, загрузка буферов и др.).

3.3 Обработка информации

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

3.3.1 Вычисление характеристик выполнения на каждом процессоре

На этом этапе вычисляются простои, разбалансировка и потерянное время на данном процессоре.

3.3.2 Вычисление характеристик рассинхронизации и разброса времен коллективных операций

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

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

3.3.3 Вычисление времени перекрытия обменов вычислениями

Время перекрытия редукции (Reduction_overlap) равно сумме отрезков времени от самого максимального времени окончания выполнения операции запуска редукции (Start_reduction) каким-либо процессором до начала выполнения соответствующей операции ожидания завершения редукции (Wait_reduction) всеми остальными процессорами. Время перекрытия обновления теневых элементов (Shadow_renewing_overlap) и времена перекрытия других коллективных операций, имеющих операции запуска и завершения вычисляются аналогичным образом.

3.3.4 Вычисление сравнительных характеристик выполнения на разных процессорах

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

3.3.5 Вычисление основных характеристик

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

Характеристики реальной рассинхронизации (Real_synchronization), потенциальной рассинхронизации (Synchronization), разброс времен (Time_variation), разбалансировка (Load_Imbalance), а также все их компоненты вычисляются аналогичным образом.