46798 (588445), страница 3

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

Текст из файла (страница 3)

Существуют следующие составляющие потерянного времени:

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

• потери из-за выполнения межпроцессорных обменов (коммуникации).

• потери из-за простоев тех процессоров, на которых выполнение программы завершилось раньше, чем на остальных (простои).

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

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

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

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

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

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

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

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

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

4.2 Методика отладки эффективности

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

В системе DVM были реализованы соответствующие средства, которые позволяют представить выполнение программы в виде иерархии интервалов [подробнее - 6].

Интервалы:

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

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

4.3 Рекомендации по анализу

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

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

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

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

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

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

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

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

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

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

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

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

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

В случае если причиной оказался недостаточный параллелизм, необходимо уточнить, на каких участках он обнаружен – последовательных или параллельных. В последнем случае причина может быть очень простой – неверное задание матрицы процессоров при запуске программы или неверное распределение данных и вычислений. Если же недостаточный параллелизм обнаружен на последовательных участках, то причиной этого, скорее всего, является наличие последовательного цикла, выполняющего большой объем вычислений. Устранение этой причины может потребовать больших усилий.

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

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

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

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

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

5. Средство анализа эффективности MPI программ

5.1 Постановка задачи

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

Характеристики

Список файлов ВКР