Оглавление
1.Введение. 3
2.Обзор существующих моделей параллельного программирования. 5
3.Обзор средств отладки эффективности MPI-программ. 9
3.1Общие проблемывсех средствтрассировки. 10
3.2Обзор основных средств отладки. 11
3.2.1 AIMS — Automated Instrumentation and Monitoring System… 11
3.2.2 Vampir,VampirTrace. 12
3.2.3 Jumpshot 14
3.2.4 Pablo Performance Analysis Toolkit Software. 15
3.2.5 Paradyn. 17
3.2.6 CXperf 18
4.Характеристики и методика отладки DVM-программ. 20
4.1 Основные характеристики производительности. 20
4.2 Методика отладки эффективности. 22
4.3 Рекомендации по анализу. 23
5.Средство анализа эффективности MPI программ. 27
5.1. Постановка задачи. 27
5.2 Этапы работы анализатора. 28
5.3 Устройство анализатора. 29
5.3.1 Сбор трассы… 29
5.3.2 Анализ. 30
5.3.3 Визуализация. 35
Заключение. 37
Списоклитературы… 39
Приложение 1. 40
Приложение2. 40
1.Введение
Сегодня невозможнопредставить себе эффективную организацию работы без применения компьютеров втаких областях, как планирование и управление производством, проектирование иразработка сложных технических устройств, издательская деятельность,образование — словом, во всех областях, где возникает необходимость в обработкебольших объемов информации. Однако наиболее важным по-прежнему остаетсяиспользование их в том направлении, для которого они собственно и создавались,а именно, для решения больших задач, требующих выполнения громадных объемоввычислений. Такие задачи возникли в середине прошлого века в связи с развитиематомной энергетики, авиастроения, ракетно-космических технологий и ряда другихобластей науки и техники.
В наше время круг задач,требующих для своего решения применения мощных вычислительных ресурсов, ещеболее расширился. Это связано с тем, что произошли фундаментальные изменения всамой организации научных исследований. Вследствие широкого внедрениявычислительной техники значительно усилилось направление численногомоделирования и численного эксперимента. Численное моделирование, заполняяпромежуток между физическими экспериментами и аналитическими подходами,позволило изучать явления, которые являются либо слишком сложными дляисследования аналитическими методами, либо слишком дорогостоящими или опаснымидля экспериментального изучения. При этом численный эксперимент позволилзначительно удешевить процесс научного и технологического поиска. Сталовозможным моделировать в реальном времени процессы интенсивныхфизико-химических и ядерных реакций, глобальные атмосферные процессы, процессыэкономического и промышленного развития регионов и т.д. Очевидно, что решениетаких масштабных задач требует значительных вычислительных ресурсов[12].
Вычислительное направление применения компьютеров всегдаоставалось основным двигателем прогресса в компьютерных технологиях. Неудивительно поэтому, что в качестве основной характеристики компьютеровиспользуется такой показатель, как производительность — величина,показывающая, какое количество арифметических операций он может выполнить заединицу времени. Именно этот показатель с наибольшей очевидностью демонстрируетмасштабы прогресса, достигнутого в компьютерных технологиях.
В настоящее время главным направлением повышенияпроизводительности ЭВМ является создание многопроцессорных систем сраспределенной памятью. Создание прикладных программ для подобныхраспределенных систем наталкивается на ряд серьезных трудностей. Разработкапараллельной программы требует выбора или создания подходящего вычислительногометода. При этом для достижения требуемой эффективности приходится многократно проходитьпуть от спецификации алгоритма к программе на языке программирования, который дляпараллельных вычислительных систем оказывается гораздо более сложным, чем дляпоследовательных.
При переходеот одного процессора к нескольким резко возрастает сложность программирования.И многие традиционные подходы здесь уже не работают. Причём если намультипроцессорной системе достаточно правильно распределить вычисления, то вслучае распределённой системы необходимо ещё распределить данные, и самоеглавное, нужно, чтобы распределение данных и вычислений было согласованным.
Одной изключевых проблем является проблема эффективности компьютерной программы. Важновидеть, какой эффект дает распараллеливание нашей программы и что можносделать, чтобы максимизировать этот эффект.
Эффективность выполнения параллельных программ на многопроцессорных ЭВМ сраспределенной памятью определяется следующими основными факторами:
· степеньюраспараллеливания программы — долей параллельных вычислений в общем объемевычислений;
· равномерностьюзагрузки процессоров во время выполнения параллельных вычислений;
· временем,необходимым для выполнения межпроцессорных обменов;
· степеньюсовмещения межпроцессорных обменов с вычислениями;
· эффективностьювыполнения вычислений на каждом процессоре (а она может варьироватьсязначительно в зависимости от степени использования кэша).
Методы и средства отладки производительности параллельной программысущественно зависят от той модели, в рамках которой разрабатываетсяпараллельная программа.
2. Обзор существующихмоделей параллельного программирования
Дляорганизации доступа к данным на многопроцессорных ЭВМ требуется взаимодействиемежду её процессорами. Это взаимодействие может происходить либо через общуюпамять, либо через механизм передачи сообщений – две основные моделипараллельного выполнения программы. Однако эти модели являются довольнонизкоуровневыми. Поэтому главным недостатком выбора одной из них в качестве моделипрограммирования является то, что такая модель непривычна и неудобна дляпрограммистов, разрабатывающих вычислительные программы.
Можно отметить системы автоматического распараллеливания,которые вполне успешно использовались на мультипроцессорах. А использованиеэтих систем на распределённых системах существенно затруднено тем, что
Во-первых, поскольку взаимодействие процессоров через коммуникационную системутребует значительного времени (латентность – время самого простоговзаимодействия — велика по сравнению со временем выполнения одной машиннойкоманды), то вычислительная работа должна распределяться между процессорамикрупными порциями.
Во-вторых, в отличие от многопроцессорных ЭВМ с общей памятью, насистемах с распределенной памятью необходимо произвести не только распределениевычислений, но и распределение данных, а также обеспечить на каждом процессоре доступк удаленным данным — данным, расположенным на других процессорах. Дляобеспечения эффективного доступа к удаленным данным требуется производитьанализ индексных выражений не только внутри одного цикла, но и между разнымициклами. К тому же, недостаточно просто обнаруживать факт наличия зависимостипо данным, а требуется определить точно тот сегмент данных, который должен бытьпереслан с одного процессора на другой.
В третьих, распределение вычислений и данных должно быть произведено согласованно.
Несогласованность распределения вычислений и данных приведет,вероятнее всего, к тому, что параллельная программа будет выполняться гораздомедленнее последовательной. Согласованное распределение вычислений и данныхтребует тщательного анализа всей программы, и любая неточность анализаможет привести к катастрофическому замедлению выполнения программы.
В настоящеевремя существуют следующие модели программирования:
Модельпередачи сообщений. MPI.[1]
В модели передачи сообщений параллельная программапредставляет собой множество процессов, каждый из которых имеет собственноелокальное адресное пространство. Взаимодействие процессов — обмен данными исинхронизация — осуществляется посредством передачи сообщений. Обобщение и стандартизацияразличных библиотек передачи сообщений привели в 1993 году к разработкестандарта MPI (Message Passing Interface). Его широкое внедрение в последующиегоды обеспечило коренной перелом в решении проблемы переносимости параллельныхпрограмм, разрабатываемых в рамках разных подходов, использующих модельпередачи сообщений в качестве модели выполнения.
В числе основных достоинств MPI по сравнению с интерфейсамидругих коммуникационных библиотек обычно называют следующие его возможности:
· Возможностьиспользования в языках Фортран, Си, Си++;
· Предоставлениевозможностей для совмещения обменов сообщениями и вычислений;
· Предоставлениережимов передачи сообщений, позволяющих избежать излишнего копированияинформации для буферизации;
· Широкий наборколлективных операций (например, широковещательная рассылка информации, сборинформации с разных процессоров), допускающих гораздо более эффективнуюреализацию, чем использование соответствующей последовательности пересылокточка-точка;
· Широкий наборредукционных операций (например, суммирование расположенных на разныхпроцессорах данных, или нахождение их максимальных или минимальных значений),не только упрощающих работу программиста, но и допускающих гораздо болееэффективную реализацию, чем это может сделать прикладной программист, неимеющий информации о характеристиках коммуникационной системы;
· Удобные средстваименования адресатов сообщений, упрощающие разработку стандартных программ илиразделение программы на функциональные блоки;
· Возможностьзадания типа передаваемой информации, что позволяет обеспечить ееавтоматическое преобразование в случае различий в представлении данных наразных узлах системы.
Однако разработчики MPI подвергаются и суровой критике за то,что интерфейс получился слишком громоздким и сложным для прикладногопрограммиста. Интерфейс оказался сложным и для реализации, в итоге, в настоящеевремя практически не существует реализаций MPI, в которых в полной мереобеспечивается совмещение обменов с вычислениями.
Появившийся в 1997 проект стандарта MPI-2 [2] выглядит ещеболее громоздким и неподъемным для полной реализации. Он предусматриваетразвитие в следующих направлениях:
· Динамическоесоздание и уничтожение процессов;
· Односторонниекоммуникации и средства синхронизации для организации взаимодействия процессовчерез общую память (для эффективной работы на системах с непосредственнымдоступом процессоров к памяти других процессоров);
· Параллельныеоперации ввода-вывода (для эффективного использования существующих возможностейпараллельного доступа многих процессоров к различным дисковым устройствам).
Вкратцео других моделях:
Модельнеструктурированных нитей. Программа представляется как совокупность нитей (threads), способных выполняться параллельно и имеющих общееадресное пространство. Имеющиеся средства синхронизации нитей позволяюторганизовывать доступ к общим ресурсам. Многие системы программированияподдерживают эту модель: Win32 threads, POSIX threads, Java threads.
Модельпараллелизма по данным. Основным её представителем является язык HPF [3]. В этой модели программист самостоятельнораспределяет данные последовательной программы по процессорам. Далеепоследовательная программа преобразуется компилятором в параллельную,выполняющуюся либо в модели передачи сообщений, либо в модели с общей памятью.При этом каждый процессор производит вычисления только над теми данными,которые на него распределены.
Модельпараллелизма по управлению. Эта модель возникла в применении к мультипроцессорам. Вместо терминовнитей предлагалось использовать специальные конструкции – параллельные циклы ипараллельные секции. Создание, уничтожение нитей, распределение на них витковпараллельных циклов или параллельных секций – всё это брал на себя компилятор.Стандартом для этой модели сейчас является интерфейс OpenMP[4].
Гибриднаямодель параллелизма по управлению с передачей сообщений. Программа представляет собойсистему взаимодействующих MPI –процессов, каждый из которых программируется на OpenMP.
Модельпараллелизмаподаннымиуправлению – DVM (DistributedVirtual Machine, Distributed Virtual Memory)[5]. Эта модель была разработана вИнституте прикладной математики им. М. В. Келдыша РАН.
3. Обзор средств отладкиэффективности MPI-программ
При анализе MPI-программ могут возникать различныесложные ситуации, для анализа которых можно применить специально разработанныеинструменты. Эти программы могут помочь в решении возникающих проблем.Большинство таких инструментов объединяет то, что они во время выполненияпрограммы производят сбор информацию в трассу (описание событий), а затемпредоставляют различные средства анализа и визуализации полученных данных.
Обычно для целей трассировки в исследуемую программу встраиваются«профилировочные» вызовы, которые фиксируют наступление определенныхсобытий или продолжительность интервалов, и фиксируют эту информацию в журналетрассировки, передают ее online-анализаторуили просто модифицируют собираемую статистику.
Можно выделить два основных подхода к анализу производительности:
· A. «Трассировка +Визуализация». Данный подход подразумевает два этапа:
o A1. Во время исполнения программысобирается «трасса», т.е. журнал о ходе работы программы.
o A2. Затем полученная трасса просматриваетсяи анализируется.
· B. «Online-анализ». Поведение программы анализируетсянепосредственно в ходе ее выполнения.
/>/>/>
Рис.1 Схема А.“Трассировка + Визуализация”.3.1Общие проблемы всех средств трассировки
1. Формат трасс неунифицирован и обычно ориентирован на конкретную библиотеку передачи сообщений.
2. Сбор информации — слабые возможности настройки фильтров событий (какие события и какую информациювключать в трассы). Нет возможности варьировать объем трассы.
3. Не учитываетсяэффекта замера — средство трассировки достаточно сильно изменяет поведениепрограммы.
Проблемы визуализации.
1. Что показывать?Какая информация интересна и полезна для отладки эффективности MPI программы.
2. Как показывать?Рис.2. Надо проводить обобщение собираемой информации. Просто вид всех событийможет быть неинформативен.
3. Когда показывать?Важно показывать то, что полезно в данный момент для отладки эффективности,чтобы не загромождать пользователя излишней информацией.
/>
Рис.2 VAMPIR. 3.2 Обзор основных средств отладки
Ниже будут кратко описанынекоторые основные средства отладки MPI-программ:
· AIMS -инструментарий, библиотекамониторинга и средства анализа
· MPE -библиотека сохранения Log-файлов средство визуализации Nupshot
· Pablo — библиотека мониторинга и средстваанализа
· Paradyn – динамический инструментарий и рантайм библиотека
· SvPablo – интегрированный инструментарий,библиотека мониторинга, средства анализа
· VAMPIRtrace — библиотека мониторинга and VAMPIR – средство визуализации
3.2.1 AIMS — AutomatedInstrumentation and Monitoring System
Место разработки: Некоммерческий продукт, разрабатывается в NASA Ames Research Center в рамках программы High Performance Computing and Communication Program.
Тип Тип А (трассировка + визуализация)
Языки/Библиотеки Fortran 77, HPF, С. Библиотеки передачи сообщений: MPI,PVM,NX.
Платформы IBM RS/6000 SP, рабочие станции Sun и SGI, Cray T3D/T3E.
Функциональность трассировки
Сбор трасс. Автоматизированное изменение исходного кода программы путем вставки специальных вызовов. Параллельно со сбором трассы создается файл со статической информацией.
Уровни детализации. Подпрограммы, вызовы процедур, процедуры различного типа (процедуры ввода-вывода, MPI процедуры т.п.)
Формат трасс. Формат описан в[7]. Ориентирован на передачу сообщений.
Тип трассировки. События, статистика (может собираться без полной трассы).
Визуализация
Процессы — параллельные линии. События изображаются точками на этих линиях. Особым образом изображаются накладные расходы: времена ожидания, блокировка. Есть возможность «проигрывания» трасс.
Время — реальное (астрономическое)
Связь линий процессов линиями, обозначающими взаимодействия (передача сообщений, глобальные операции).
Диаграммы взаимодействия процессов, временные срезы, история вызовов и трассируемых блоков.
Поддерживается связь с исходным кодом.
Статистика Суммарное время по замеряемым инструкциям или типам инструкций и количество срабатываний.
/>
Рис.3 AIMS. Результат подробного анализазапуска.
Vampir, VampirTrace
URL www.pallas.de/pages/vampir.htm
Где разрабатывается?
Коммерческий продукт, разработка компании Pallas (Германия).
Версии VAMPIR 4.0 (X Window), VAMPIRtrace 4.0
Тип Тип А (трассировка + визуализация). VampirTrace — система генерации трасс (A1), Vampir — система визуализации (A2).
Языки/библиотеки Языки — Fortran, C; передача сообщений в рамках MPI.
Платформы
· Cray T3D/T3E
· DEC Alpha (OSF/1)
· Fujitsu VP 300/700
· Hitachi SR2201
· HP 9000
· IBM RS/6000, SP
· Intel Paragon
· NEC SX-4
· SGI Origin, PowerChallenge (IRIX 6)
· Sun SPARC
· Intel x86 (Solaris 2.5)
Функциональность трассировки.
Сбор трасс. Линковка с VampirTrace — прослойкой между MPI и пользовательской программой. Уровни детализации. Cлабые вохможности настройки уровня детализации — только по подпрограммам. Возможна установка точек начала/конца трассировки. Тип трассировки. Только события (статистика собирается на этапе анализа трасс).
Визуализация
Процессы — параллельные линии, события — точки на них.
Взаимодействия. Связь линий процессов, матрицы объемов и количества пересылок
Другие объекты. Круговые диаграммы и статистические гистограммы.
Поддерживается связь с исходным кодом.
Статистика Cуммарное время по замеряемым инструкциям или типам инструкций и количеству срабатываний; отображается на круговых диаграммах и гистограммах.
/>
Рис.4. VAMPIR 4.0Jumpshot
URL www-unix.mcs.anl.gov/mpi/www/www1/Jumpshot.html
Где разрабатывается?
Некоммерческое средство, разработано в Аргоннской национальной лаборатории. Распространяется вместе с пакетом MPICH.
Версия Jumpshot 1.0 (требуется Java 1.1 или выше)
Тип A2 (визуализация трасс)
Языки/библиотеки Передача сообщений: MPI.
Платформа Сбор трасс — любые платформы, где работает MPICH. Визуализация — Java.
Функциональность трассировки
Сбор трасс. Для получения трассы программу необходимо откомпилировать с профилировочной версией библиотеки MPICH. Формат трасс. CLOG. Тип трасс. События
Визуализация
Процессы — параллельные линии, цветом изображается тип функции. Взаимодействия. Связь линий процессов. Другие объекты. Объемы пересылок по времени, гистограммы накладных расходов по времени.
Статистика Суммарные времена работы различных типов процедур.
Разное
jumpshot входит в состав MPICH начиная с версии 1.1.1 и заменяет собой Tcl/Tk-программы upshot/nupshot, входившие в состав MPICH более ранних версий. Pablo Performance Analysis Toolkit Software
Пакет состоит из набора средств:
· SvPablo — визуализатор статистической информации (X Window).
· SDDF — библиотекадля записи трасс и набор средств для работы с SDDF файлами
· TraceLibrary and Extensions — библиотека для трассировки
· I/O Analysis — статистика операций ввода-вывода
· MPII/O Analysis — статистика MPI I/O
· HDF(Hierarchical Data Format) Analysis — анализиспользования HDF операций
· Analysis GUI — библиотека средств для просмотра SDDF трасс
· IO Benchmarks — cбор трасс операций ввода-вывода
·
URL vibes.cs.uiuc.edu/Software/Pablo/pablo.htm
Где разрабатывается? Некоммерческий пакет, разработан в университете шт. Иллинойс.
Языки/библиотеки ANSI C, Fortran 77, Fortran 90 (с ограничениями), HPF (Portland Group).
Платформы
· SvPablo — SunOS 5.6, SGI Irix 6.5
· Trace Library and Extensions — Sun SunOS, Sun Solaris, RS6000, SP2, Intel Paragon, Convex Exemplar, SGI IRIX
· I/O Analysis — Sun Solaris, SGI IRIX
· MPI I/O Analysis — Sun SunOS, SGI IRIX
· HDF Analysis — Sun Solaris, SGI IRIX
· Analysis GUI — Sun Solaris (X11R5+Motif)
· IO Benchmarks — Sun Solaris, SGI IRIX, Intel Paragon
Функциональность трассировки.
Уровни детализации. Hа уровне интерфейсов, можно делать ручную разметку с использованием svPablo. Формат трасс — SDDF Тип трасс. Статистика, события.
Визуализация
SvPablo. Основа визуализации — связь с исходным кодом. Представляет цветом число вызовов и общее время фрагмента.
Analysis GUI. Библиотека подпрограмм для визуализации трасс в формате SDDF
Статистика
Развернутые средства статистики, в виде набора пакетов.
· I/O Analysis: анализ операций ввода-вывода
· MPI I/O Analysis: анализ ввода-вывода MPI функций
· HDF Analysis: анализ операций HDF.
Совместимость Есть конверторы из разных форматов в SDDF – IBM VT Trace, AIMS.
Развитие Поддержка HPF, Fortran 90. Поддержка MPI 2.0.
/>
Рис5. Возможности Pablo. Paradyn
URL www.cs.wisc.edu/paradyn
Где разрабатывается? Некоммерческое средство, разрабатывается в University of Wisconsin,
Версия 4.0
Тип B (онлайн-анализ)
Языки/библиотеки Fortran, Fortran 90, C, C++: MPI, PVM; HPF
Платформы
· Sun SPARC (только PVM)
· Windows NT на x86
· IBM RS/6000 (AIX 4.1 или старше)
Функциональность трассировки Динамическая настраиваемая инструментовка программ во время выполнения. В код программы во время ее выполнения динамической вставляются и убираются вызовы трассирующих процедур. Все делается автоматически, в результате значительно уменьшаются накладные расходы. Начинает с крупных блоков, затем постепенно детализирует узкие места (для этого программа должна достаточно долго работать)
Визуализация
В основе визуализации лежат два вектора
· измеряемые параметры производительности: процессорное время, различные накладные расходы, ожидания, времена пересылок и ввода-вывода и т.д.
· компоненты программы/вычислительной системы, к которым относятся параметры: процедуры, процессоры, диски, каналы передачи сообщений, барьеры и т.д.
На этих векторах образуется матрица: ее элементы либо скаляр (значение, среднее, минимум, максимум и т.д.), либо временная диаграмма (история изменения характеристики).
Все характеристики отображаются во время исполнения программы.
Проблемы Есть проблемы с масштабируемостью. На программе при малом числе процессоров (меньше 12) все выглядело нормально, а на большем числе процессоров — более чем 80% увеличение времени. Так же сейчас самой системой занимается очень много памяти.
Развитие Устранение проблем масштабируемости, уменьшение требуемой памяти, поддержка других платформ. CXperf
URL
HP Performance Analysis Tools — www.hp.com/esy/lang/tools/Performance/ CXperf User's Guide
Где разрабатывается?
Коммерческое средство, разработка Hewlett-Packard.
Тип A (трассировка + визуализация)
Языки/библиотеки HP ANSI C (c89), ANSI C++ (aCC), Fortran 90 (f90), HP Parallel 32-bit Fortran 77
Платформы Сервера HP на базе PA-RISC
Функциональность трассировки Сбор и настройка трасс осуществляется с помощью указания специальных профилировочных опций компилятора.
Визуализация 3D-визуализация, связь с кодом программы, масштабирование, сопоставительный анализ, графы вызовов.
Некоторые другие средства анализаповедения паралелльных программ:
· XMPI — графическая среда запуска иотладки MPI-программ, входит в состав пакета LAM.
· HPPak — наборсредств от Hewlett-Packard для анализа поведения многопоточных программ.
· TAU (Tuning and Analysis Utilities) — некоммерческий набор утилит анализа производительности программ, написанных наязыке C++ и его параллельных вариантах. Включает пакет профилировки TAU Portable Profiling.
· Carnival
· Chiron — средство для оценкипроизводительности многопроцессорных систем с общей памятью.
· Pangaea
· GUARD — параллельный отладчик.
· MPP-Apprentice — средство в составе Message-Passing Toolkit от SGI.
· ParaGraph
· PGPVM2
· TraceInvader
· XPVM — графическое средство мониторингаPVM-программ.
Подробнее можно прочитатьв [8].
4. Характеристики и методика отладки DVM-программ
4.1 Основныехарактеристики производительности
Возможность различать последовательные и параллельные участкипрограммы позволяет при ее выполнении на многопроцессорной ЭВМ спрогнозироватьвремя, которое потребуется для выполнения этой программы на однопроцессорнойЭВМ. Это время называется полезным временем. Тем самым появляетсявозможность вычислить главную характеристику эффективности параллельноговыполнения — коэффициент эффективности, равный отношению полезноговремени к общему времени использования процессоров, которое в своюочередь равно произведению времени выполнения программы намногопроцессорной ЭВМ (максимальное значение среди времен выполнения программына всех используемых ею процессорах) на число используемых процессоров. Разницамежду общим временемиспользования процессоров и полезным временемпредставляет собой потерянное время. Если программист не удовлетворенкоэффициентом эффективности выполнения своей программы, то он долженпроанализировать составляющие части потерянного времени и причины ихвозникновения.
Существуют следующие составляющие потерянного времени:
· потери из-занедостатка параллелизма, приводящего к дублированию вычислений на несколькихпроцессорах (недостаточный параллелизм). Дублирование вычисленийосуществляется в двух случаях. Во-первых, последовательные участки программывыполняются всеми процессорами. Во-вторых, витки некоторых параллельных цикловмогут быть по указанию программиста полностью или частично размножены.
· потери из-завыполнения межпроцессорных обменов (коммуникации).
· потери из-запростоев тех процессоров, на которых выполнение программы завершилось раньше,чем на остальных (простои).
Время выполнения межпроцессорных обменов, помимо временипересылки данных с одного процессора на другой, может включать в себя и время,которое тратится из-за того, что операция приема сообщения на одном процессоревыдана раньше соответствующей операции посылки сообщения на другом процессоре.Такая ситуация называется рассинхронизацией процессоров и может быть вызванаразными причинами.
Поскольку потери, вызываемые рассинхронизацией процессоров,очень часто составляют подавляющую часть времени коммуникаций, то важнопредоставить программисту информацию, позволяющую ему оценить эти потери инайти их причины. Однако, точное определение потерь, вызванныхрассинхронизацией, связано со значительными накладными расходами
Если какая-либо из перечисленных операций выдана разнымипроцессорами не одновременно, то при ее выполнении возникнут потери из-зарассинхронизации процессоров. Для оценки величины таких потерь для каждойколлективной операции вычисляются потенциальные потери из-за еенеодновременного запуска — время, которое было бы потрачено всеми процессорамина синхронизацию, если бы выполнение любой коллективной операции начиналось быс синхронизации процессоров. При этом накладные расходы на пересылку синхронизационныхсообщений игнорируются.
Для оценки суммарных потенциальных потерь, которые могутвозникнуть из-за неодновременного запуска коллективных операций на разныхпроцессорах, служит специальная характеристика – синхронизация.
Основная причина потерь из-за рассинхронизации, на устранениекоторой должен быть нацелен программист – разбалансировка загрузки процессоров.Разбалансировка может возникать из-за того, что выполняющиеся в параллельномцикле вычисления распределены между процессорами неравномерно.
Если бы при входе в каждый параллельный цикл и при выходе изнего производилась бы синхронизация процессоров (межпроцессорный обмен), торазбалансировка загрузки процессоров обязательно приводила бы к потерям из-зарассинхронизации. Однако, поскольку такая синхронизация осуществляется не длявсех циклов, то разбалансировка на разных участках программы можеткомпенсироваться и реальные потери могут быть незначительными или вообщеотсутствовать. Для оценки возможных потерь из-за разбалансировки программистуможет выдаваться некоторая обобщенная характеристика — разбалансировка. Сцелью снижения накладных расходов привычислении этой характеристикиделается предположение, что синхронизация процессоров будет производитьсятолько один раз — при завершении выполнении программы. Поэтому сначала длякаждого процессора определяется его суммарная вычислительная загрузка, а затемпрогнозируется вызываемая разбалансировкой величина потерь из-зарассинхронизации. Однако, поскольку в реальной программе синхронизацияпроцессоров осуществляется не только при завершении программы, а гораздо чаще,то реальные потери будут превосходить эту величину. Реальные потери из-зарассинхронизации будут еще более превосходить величину разбалансировки в томслучае, когда вычислительная загрузка процессоров сильно изменяется примногократном выполнении одного и того же параллельного цикла.
Рассинхронизация может возникать не только из-заразбалансировки, но также из-за различий во временах завершения выполнения наразных процессорах одной и той же коллективной операции, вызванныхособенностями ее реализации на конкретной параллельной ЭВМ. Для оценки величинытакой потенциальной рассинхронизации программисту может выдаваться специальнаяхарактеристика – разброс времен завершения коллективных операций. Как ивремя разбалансировки, эта характеристика является интегральной. Она достаточноточно отражает возможные потери из-за рассинхронизации в том случае, когдаразличия времен выполнения коллективных операций не являются случайными, а определяются,например, топологией коммуникационной сети или функциональной специализациейпроцессоров (процессор ввода-вывода, процессор-исполнитель редукционныхопераций, и т.п.).
Важной характеристикой, отражающей степень совмещениямежпроцессорных обменов с вычислениями, является время перекрытияобменов вычислениями.
Основные характеристики эффективности являются интегральнымихарактеристиками, позволяющими оценить степень распараллеливания программы иосновные резервы ее повышения. Однако для исследования эффективности сложныхпрограмм одних интегральных характеристик может оказаться недостаточно. В такомслучае программист хочет получить более подробную информацию о выполнении своейпрограммы и ее отдельных частей.4.2 Методика отладки эффективности
Для анализа эффективности выполнения сложных параллельныхпрограмм недостаточно иметь характеристики выполнения всей программы целиком, атребуется уметь детализировать эти характеристики применительно к отдельным частямпрограммы.
В системе DVMбыли реализованы соответствующие средства, которые позволяют представитьвыполнение программы в виде иерархии интервалов [подробнее — 6].
Интервалы:
Выполнение всей программы целиком рассматривается какинтервал самого высокого (нулевого) уровня. Этот интервал может включать в себянесколько интервалов следующего (первого) уровня. Такими интервалами могут бытьпараллельные циклы, последовательные циклы, а также любые отмеченныепрограммистом последовательности операторов, выполнение которых всегданачинается с выполнения первого оператора, а заканчивается выполнениемпоследнего. Все описанные выше характеристики вычисляются не только для всейпрограммы, но и для каждого ее интервала. При этом многократное выполнениеинтервала может рассматриваться (с некоторой долей условности) как выполнениена тех же процессорах отдельной программы, состоящей из развернутойпоследовательности тех операторов интервала, которые были выполнены приреальном прохождении параллельной программы. Фактически же, характеристикитаких многократно выполняемых интервалов накапливаются при каждом ихвыполнении. При этом интервалы, входящие в состав одного и того же интервалаболее высокого уровня, идентифицируются именем файла с исходным текстомпрограммы и номером строки в нем, соответствующим началу интервала, а также,возможно, некоторым приписанным ему программистом целочисленным номером.
Разбиением программы на интервалы пользователь управляет приее компиляции. Он может задать такие режимы, при которых интервалами будутпоследовательные циклы, которые содержат внутри себя параллельные циклы, либовсе последовательные циклы вообще, либо отмеченные им в программепоследовательности операторов.4.3 Рекомендациипо анализу
При разработкепараллельной программы пользователь, как правило, преследует одну из двухвозможных целей – обеспечить решение задачи в приемлемые сроки, либо создатьпрограмму, способную эффективно решать на различных параллельных ЭВМ задачиопределенного класса.
В первом случае, есливремя выполнения программы удовлетворяет пользователя, то другие характеристикиего могут уже не интересовать. Во втором случае главным критерием дляпользователя является коэффициент эффективности распараллеливания. Если времявыполнения или коэффициент эффективности не удовлетворяет пользователя, то емунеобходимо анализировать потерянное время и его компоненты.
Важно помнить, что: во-первых,потерянное время (как и коэффициент эффективности распараллеливания)вычисляется, опираясь не на реальное время выполнения программы на одномпроцессоре, а на прогнозируемое время. Этот прогноз может отличаться отреального времени и в ту, и в другую сторону.
Реальное время может бытьбольше прогнозируемого из-за того, что при выполнении программы на одномпроцессоре одни и те же вычисления могут осуществляться медленнее, чем привыполнении на нескольких процессорах. Это объясняется тем, что при измененииобъема используемых при вычислениях данных меняется скорость доступа к нимчерез кэш-память. Поскольку производительность современных процессоров сильнозависит от эффективности использования кэш-памяти, то реальное время можетзаметно превысить прогнозируемое.
Реальное время может бытьменьше прогнозируемого, поскольку при прогнозе учитываются не все накладныерасходы на поддержку выполнения параллельной программы. Эти неучтенные расходы,например, поиск информации в системных таблицах при выполнении некоторых частоиспользуемых функций (замерять время выполнения которых невозможно без внесениянеприемлемых искажений в выполнение программы), могут значительно сократитьсяпри уменьшении количества процессоров до одного.
В результате влиянияэффективности использования кэш-памяти и системных накладных расходов привыполнении программы на разных конфигурациях параллельной ЭВМ будут выдаватьсяразличные значения полезного времени. Поэтому, если есть возможность выполнитьпрограмму на одном процессоре (а она может требовать гораздо больше оперативнойпамяти, чем имеется на одном процессоре), то желательно это сделать дляполучения представления об отличиях прогнозируемых времен от реального времени.
Во-вторых, времявыполнения параллельной DVM-программы на одном процессоре может значительноотличаться от времени ее выполнения как последовательной программы. Это можетбыть следствием следующих причин:
· Доступ краспределенным данным в параллельной программе отличается от доступа к ним впоследовательной программе. Дополнительные накладные расходы, появляющиеся впараллельной программе, могут увеличить время ее выполнения на 10-30 процентов.Однако в параллельной программе может быть проведена такая оптимизация доступак данным, которая для некоторых программ приведет к ускорению их выполнения посравнению с последовательным случаем.
· Трансформацияпрограммы в программу на стандартных языках Фортран 77 или Си может привести кразличиям в оптимизации программ стандартными компиляторами. В результате,параллельная программа может выполняться либо медленнее, либо быстрее.Особенности оптимизации программ современными компиляторами существенно(десятки и сотни процентов) определяют эффективность их выполнения.
· Некоторыенакладные расходы на поддержку выполнения параллельной программы могутзначительно замедлить ее выполнение (например, операции запроса и освобожденияпамяти в последовательной программе могут превратиться в параллельной программев гораздо более сложные операции создания и уничтожения распределенного массива).
Поэтому, если естьвозможность выполнить программу как обычную последовательную программу на одномпроцессоре (если это нельзя сделать на параллельной ЭВМ, то может быть этоокажется возможным на рабочей станции), то желательно это сделать.
Все это пользователюнеобходимо иметь в виду, приступая к анализу потерянного времени и егокомпонент.
Сначала следует оценитьтри компоненты потерянного времени для интервала нулевого уровня (всейпрограммы). Наиболее вероятно, что основная доля потерянного времени приходитсяна одну из первых двух компонент (недостаточный параллелизм или коммуникации).
В случае если причинойоказался недостаточный параллелизм, необходимо уточнить, на какихучастках он обнаружен – последовательных или параллельных. В последнем случаепричина может быть очень простой – неверное задание матрицы процессоров призапуске программы или неверное распределение данных и вычислений. Если женедостаточный параллелизм обнаружен на последовательных участках, то причинойэтого, скорее всего, является наличие последовательного цикла, выполняющегобольшой объем вычислений. Устранение этой причины может потребовать большихусилий.
В том же случае, еслиосновной причиной потерь являются коммуникации, то необходимо, преждевсего, обратить внимание на характеристику потери из-за рассинхронизации.Если ее значение близко к размерам потерь из-за коммуникаций, то необходиморассмотреть характеристику разбалансировка, поскольку именноразбалансировка вычислений в параллельном цикле является наиболее вероятнойпричиной рассинхронизации и больших потерь на коммуникациях. Если величинаразбалансировки намного меньше величины синхронизации, то необходимообратить внимание на величину разброса времен коллективных операций.Если рассинхронизация не является следствием разброса времен завершенияколлективных операций, то ее возможной причиной могут быть разбалансировкинекоторых параллельных циклов, которые на рассматриваемом интервале выполненияпрограммы могли взаимно компенсироваться. Поэтому имеет смысл перейти крассмотрению характеристик разбалансировки на интервалах более низкого уровня.
Второй вероятной причинойбольших потерь из-за рассинхронизации может быть рассинхронизация процессоров,которая возникает при выдаче операций ввода-вывода. Это происходит из-за того,что основная работа (обращение к функциям ввода-вывода операционной системы)производится на процессоре ввода-вывода, а остальные процессоры в это времяждут получения от него данных или информации о завершении коллективнойоперации. Эту причину потерь легко обнаружить, обратив внимание насоответствующую компоненту характеристики коммуникации – потери из-закоммуникаций при вводе-выводе.
Еще одной причинойбольших потерь из-за коммуникаций могут оказаться задержки при запускеколлективных операций в асинхронном режиме, возникающие из-за того, чтонекоторые реализации MPI необеспечивают совмещение вычислений с обменами.
Возможен и другой подход к анализухарактеристик, когда сначала анализируются коэффициенты эффективности ипотерянное время на различных интервалах первого уровня, затем второго уровня,и т.д. В результате определяется критический участок программы, на анализхарактеристик которого и направляются основные усилия. При этом необходимоиметь в виду, что причиной потерь на данном интервале из-за рассинхронизации ипростоев могут быть разбалансировки и разбросы времен не только на этоминтервале, но и на других, выполнявшихся до него интервалах.
При отладкепроизводительности программы пользователь не обязательно должен запускать ее стем большим объемом вычислений, который будет характерен для использованияпрограммы при решении реальных задач. Он может ограничить, например, количестворегулярно повторяющихся внешних итераций до одной — двух итераций. При этомкоэффициент эффективности программы, существенно зависящий от потерь на техучастках программы, которые выполняются до начала первой итерации или послеокончания последней итерации, может значительно снизиться. Однако пользовательможет оформить выполнение внешних итераций в виде отдельного интервала (но приэтом надо учитывать тот факт, что выполнение первой итерации можетсопровождаться значительными задержками из-за динамической подзагрузкипрограммы из файловой системы) и отлаживать его производительность по той жеметодике, которая была описана выше применительно к программе целиком.
5. Средство анализа эффективности MPIпрограмм5.1 Постановка задачи
В системе DVM существуют развитые средства анализаэффективности выполнения параллельной DVM-программы. Эти средства являются более мощными, чем те, которыесуществуют для MPI-программ,поскольку многие важные характеристики выполнения MPI-программ (например, соотношение параллельных ипоследовательных вычислений) невозможно определить из-за отсутствия необходимойинформации. Кроме того, в настоящее время при разработке MPI-программ у нас в стране практическине используются инструментальные средства отладки эффективности. Это вызваноследующими основными факторами: — разные средства требуют от пользователязнания их собственного интерфейса (отсутствие фактического стандарта); — отсутствием вообще каких-либо инструментальных средств анализа эффективности намногих параллельных ЭВМ.
Поэтому важно создать такие средства для получения характеристикэффективности MPI-программ, которые могли бы бытьдоступны пользователям на любых многопроцессорных ЭВМ.
Целью данной дипломной работы является созданиеэкспериментальной системы отладки эффективности MPI-программ.
Входными данными для нее будут трассы, создаваемые DVM-системой для функциональной отладки MPI-программ. В этих трассах отраженыобращения к MPI-функциям и времена их работы. Дляполучения характеристик, аналогичных тем, которые выдаются для DVM-программ, от программистапотребуется дополнительная информация о том, какие вычисления являютсяпараллельными, а какие последовательными (дублированными на каждом процессоре).Эти указания должны быть оформлены таким образом, что их наличие в MPI-программе не мешало ее правильному иэффективному выполнению на тех ЭВМ, где отсутствует данная система отладкиэффективности MPI-программ. Таким же образом должныоформляться и средства описания тех интервалов выполнения программы, длякоторых требуется отдельно собирать все характеристики эффективности. Этапы работы анализатора.
В работе анализатораможно выделить следующие этапы.
Этап 1
Обработка трасс со всехпроцессоров и вычисление для каждого интервала и каждого процессора следующиххарактеристик:
Основные характеристики и ихкомпоненты
Коэффициент эффективности (Parallelizationefficiency) равен отношению полезного времени кобщему времени использования процессоров.
Время выполнения (Executiontime).
Число используемых процессоров (Processors).
Общее время использования процессоров (Totaltime) — произведение времени выполнения (Executiontime) на число используемых процессоров (Processors).
Полезное время (Productivetime) – прогнозируемое время выполненияна одном процессоре
Потерянное время (Losttime).
Коммуникации (Communication) и все компоненты.
Простои (Idletime).
Разбалансировка (Load_Imbalance).
Потенциальные потери из-засинхронизации (Synchronization) и все компоненты.
Потенциальные потери из-за разбросавремен (Time_variation) и все компоненты.
Характеристикивыполнения программы на каждом процессоре
Потерянное время (Losttime) — сумма его составляющих – потерьиз-за недостаточного параллелизма (Userinsufficient_par),системных потерь из-за недостаточного параллелизма (Sysinsufficient_par), коммуникаций (Communication) и простоев (Idletime).
Простои на данном процессоре (Idletime) — разность между максимальнымвременем выполнения интервала (на каком-то процессоре) и временем еговыполнения на данном процессоре.
Общее время коммуникаций (Communication).
Реальные потери из-зарассинхронизации (Realsynchronization).
Потенциальные потери из-за разбросавремен (Variation).
Разбалансировка (Load_imbalance) вычисляется как разность междумаксимальным процессорным временем (CPU+MPI) и соответствующим временем на данном процессоре.
Время выполнения интервала (Execution_time).
Полезное процессорное время (UserCPU_time).
Полезное системное время (MPItime).
Число используемых процессоров дляданного интервала (Processors).
Времена коммуникаций для всех типовколлективных операций
Реальные потери из-зарассинхронизации для всех типов коллективных операций.
Потенциальные потери из-зарассинхронизации для всех типов коллективных операций.
Потенциальные потери из-за разбросавремен для всех типов коллективных операций.
Этап 2
Подготовка текстовогопредставления вычисленных характеристик. Такое представление упрощаетпервоначальный анализ характеристик при запуске параллельной программы наудаленной ЭВМ.
Этап 3
Визуализация результатованализа эффективности.
Подсистема визуализациидолжна обеспечить графическое представление вычисленных характеристикэффективности и помочь пользователю их исследовать — позволить с разнойстепенью подробности просматривать историю выполнения программы и объяснять,как были вычислены те или иные характеристики.5.3 Устройствоанализатора
Итак, анализатор состоитиз трех основных компонент.
Первая – сбор информации по трассе. Вторая– анализ собранных данных. Третья – визуализация. 5.3.1 Сбор трассы
При каждом запуске параллельной программыв режиме трассировки, создается группа файлов с информацией обо всех ключевыхсобытиях в трассе. Тут есть времена и параметры всех событий, которые имелиместо при выполнении программы. К этим данным есть возможность доступа черезспециальные функции интерфейса. Также можно получить информацию для разногорода вспомогательных таблиц (имена используемых функций, исходных файлов ит.п.).
Далее полученные данныепоступают на вход модулям анализа и сбора характеристик.5.3.2 Анализ
В соответствии сописанной в пункте 4.2 методикой, вся программа будет разбита на системуинтервалов, точнее дерево интервалов. Корнем дерева будет вся программа, онасчитается интервалом нулевого уровня.
Далее в соответствии свложенностью интервалы первого уровня и т.д.
Как указать границыинтервалов?
Для этого используютсяпара функций MPI_Send() и MPI_Recv() для указания начала интервала, итакая же пара для указания его окончания. При этом посылка и прием сообщенияпроисходят самому себе и от самого себя (имеется ввиду, что в качестве номераотправителя/получателя используется номер самого процесса). Кроме того, тэгсообщения имеет следующий вид:
TAG = 0x(aa)(id)(aa/bb).
Тэг являетсячетырехбайтным целым числом. Первый байт у «нашего» тэга – это 0xaa. Это позволяет отличить его отобычных посылок/приемов сообщений. Последний байт может быть 0xaa – символизирует начало интервала, 0xbb – конец интервала. Внутриспециальный идентификатор интервала (2 байта), его можно использовать,например, для того, чтобы отдельно выделить итерации цикла.
Такой способ выделениябыл выбран потому, что:
· он всегдапопадает в трассировку (некоторые специальные функции вроде MPI_Pcontrol() в текущей версии трассировщика не попадают).
· занимаетотносительно немного времени (порядка 100 тиков процессора).
· прост виспользовании и не требует дополнительных средств, помимо стандартных MPI-функций.
Таким образом,программист может добавить в свой код границы интересующих его областейпрограммы (в нашей терминологии интервалы).
Далее по этим тэгам средивсех событий будут найдены те, которые являются границами интервалов и будутопределены их идентификаторы.
Для этого вводится специальныйкласс:
classMargin
{
public:
Margin(bool,unsigned long ,int ,unsigned int ,int);
friendbool operator
boolenter_leave;
unsignedlong time;
intidentity;
unsignedint proc;
unsignedint scl;
};
И функция:
vectorMargin>* createMargins(void);
которая и вычисляет=>определяет необходимые границы вместе со всеми параметрами.
После определения границ,создается структура дерево, в которой хранятся все данные обо всех интервалах.
Кратко об используемыхструктурах данных.
Создан специальный класс tree:
classtree
{
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;
//Characteristicsfor every interval
unsignedlong Exec_time;
unsignedlong Productive_time;
double Efficiency;
unsignedlong CPU_time;
unsignedlong MPI_time;
unsignedlong Lost_time;
unsignedlong Comm_time;
unsignedlong SendRecv_time;
unsignedlong CollectiveAll_time;
unsignedlong Idle_time;
unsignedlong AllToAll_time;
unsignedlong Time_variation;
unsignedlong Potent_sync;
unsignedlong T_start;
vector >* cmp_pairs;
//forintelval's tree
tree* parent_interval;
int count;
vector nested_intervals;
vector Procs;
};
Этот класс содержитинформацию обо всех характеристиках данного интервала, описанных в 5.2. Крометого, в нем есть информация о родительском узле дерева, а также обо всех«листьях-потомках».
В этом классе в качествевспомогательного используется класс Processors.
classProcessors
{
public:
unsignedlong enter_time;
unsignedlong leave_time;
unsignedint number;
unsignedlong MPI_time;
unsignedlong SendRecv_time;
unsignedlong CollectiveAll_time;
unsignedlong Idle_time;
unsignedlong AllToAll_time;
unsignedlong CPU_time;
unsignedlong Comm_time;
unsignedlong Time_variation;
unsignedlong Potent_sync;
unsignedlong T_start;
};
В этом классе содержатсяэлементарные составляющие всех компонентов, собранные на каждом интервалекаждого процессора.
Далее, после определенияграниц интервалов, происходит создание дерева интервалов. В этом дереве и будетхраниться информация обо всех интервалах.
Класс treeвключает методы, которые и собираютинформацию из структур, собранных на трассе.
Первая группахарактеристик собирается в функции
Leave(int line, char* file, longindex,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(unsignedlong 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
---MainCharacteristics---
ParallelizationEfficiency 0.978833
Execution Time 2.079975
Processors 4
Total Time 8.319900
ProductiveTime 8.143794 (CPU MPI)
MPI время на одном процессоре считаетсяполезным, а на остальных — потерянным
Lost Time 0.176106
---MPI Time 0.173490
---Idle Time 0.002616CommunicationTime 0.076563
*****SendRecvTime 0.013295
*****CollectiveAllTime 0.063268
*****AllToAllTime 0.000000
PotentialSync. 0.068763
Time Variation 0.001790
Time of Start 0.000000
---ComparativeCharacteristics---
Tmin Nproc Tmax Nproc Tmid
Lost Time 0.033087 3 0.060057 0 0.044026
Idle Time 0.000000 1 0.000898 0 0.000654
Comm. Time 0.006597 3 0.034854 0 0.019140
MPI Time 0.0322593 0.059159 0 0.043372
PotentialSync. 0.001800 0 0.029369 3 0.017190
Time variation 0.000161 1 0.000607 3 0.000447
Time of Start 0.0000000 0.000000 0 0.000000
Для каждого интервалавыдается следующая информация:
· имя файла сисходным текстом MPI-программы иномер первого оператора интервала в нем (SourceFile, LineNumber);
· номер уровнявложенности (Level);
· количество входов(и выходов) в интервал (EXE_Count);
· основныехарактеристики выполнения и их компоненты (Main characteristics);
· минимальные,максимальные и средние значения характеристик выполнения программы на каждомпроцессоре (Comparative characteristics);
При выдаче характеристиких компоненты располагаются в той же строке (справа в скобках), либо вследующей строке (справа от символов “*” или “-“).
Информация о минимальных,максимальных и средних значениях характеристик оформлена в таблицу. Также естьинформация обо всех характеристиках на каждом процессоре.
5.3.3 Визуализация
Следующим этапом послетого, как все необходимые характеристики собраны, является этап визуализации.
Этот этап необходим, таккак хотя текстовый файл содержит всю необходимую информацию, при большом числеинтервалов пользоваться им не очень удобно. Кажется целесообразным, что, таккак интервалы “отображались” логически в виде дерева, то и визуализировать ихнужно в виде дерева. Было выбрана форма отображения, аналогичная древовиднойорганизации файловой структуры данных на дисках. Соответственно, каждыйинтервал доступен из своего родителя, интервалы нижних уровней отображаютсяправее. Также при нажатии на интервал, в текстовое поле
выводится информация обовсех характеристиках именно этого интервала.
Это значительно облегчаетпоиск необходимой для анализа области.
/>
Рис.6. Окно программыанализа.
Также полезным дляпредставления общей картины запуска является упорядоченный по времени списоксобытий. При этом используется так называемый (TimeLine), все события отображаются на линииопределенным цветом в соответствии со временем, когда они произошли. Этопозволяет отслеживать не просто нужную область, а точно интересующее событие.
Используя механизм Tooltip’ов, пользователь получаетвозможность узнать тип события (пользовательский (UserCode) или MPI) и название функции (для MPI — функций).
/>
Рис.7. TimeLine
Узнать это можно по цветулинии с событием. Список цветов описан в Приложении 2.
Заключение
В данной работеисследовались возможности анализа эффективности MPI-программ. Было разработано собственное программноесредство, использующее подходы, применяемые в DVM-системе.
Приблизительный объемпрограммы на С++ в строках кода = 6500 строк.
Программа оттестированана тестах, поставляемых с MPI –реализациями, а также с тестами NAS (NPB2.3), с добавлением описанных вышедиректив для границ интервала.
В процессе дипломнойработы были:
ü Проанализированы современные средстваанализа параллельных программ.
ü Изучены алгоритмы анализа и сборахарактеристик.
ü Реализовано программное средство соследующими возможностями:
1. Отображение выполнения программы ввиде дерева интервалов
2. Сбор и отображение характеристиквыбранного интервала.
3. Выдача общей информации обо всехинтервалах в текстовый файл.
4. Показ time-line.
Выводы:
· Отладка эффективности параллельныхпрограмм – процесс очень сложный и трудоемкий
· Развитые средства анализаэффективности могут существенно ускорить этот процесс.
· Необходима грамотная — нагляднаявизуализация результатов.
· Для достижения эффективностипараллельной программы приходится многократно изменять программу, иногдакардинально меняя схему ее распараллеливания. Поэтому важно использоватьвысокоуровневые средства разработки параллельных программ
· Необходимоучитывать различные эффекты, связанные с нестабильностью поведения параллельныхпрограмм.
В дальнейшем планируетсявести работу в направлении интеллектуализации системы. Желательно получениеавтоматических советов пользователю-программисту по улучшению эффективностипрограммы. Это поможет упростить решение традиционных сложностей, возникающихна пути отладки параллельной программы.
Приложение1
Структура программы.
/>
Модуль main – вызов процедур сбора информации, анализа и генерациирезультата. Compute – вычисление все необходимыххарактеристик трассы. Для этого используется модуль tree,который отвечает за формирование дерева с данными об искомых характеристиках.Модуль determine позволяет находить и выделятьинтервалы в исходном коде и в трассе программы. Модуль visualзанимается графическим отображением полученных данных и состоит и timeline – события в трассе, и characteristics – деревоинтервалов с отображаемыми характеристиками.
Приложение2
Используемые цвета на TimeLine:
1. Коллективные операции:
MPI_Barrier, MPI_Bcast, MPI_Gather,MPI_Gatherv, MPI_Scatter, MPI_Scatterv, MPI_Allgather, MPI_Allgatherv, MPI_Alltoall, MPI_Alltoallv, MPI_Reduce, MPI_Allreduce, MPI_Reduce_scatter, MPI_Scan
черный
2. Операции посылки
MPI_Send, MPI_Bsend, MPI_Ssend,MPI_Rsend
тёмно-зелёный
3. Неблокирующие операциипосылки
MPI_Isend, MPI_Ibsend, MPI_Issend,MPI_Irsend
светло-зелёный
4. Операцииполучения/ожидания/посылки-получения с блокировкой MPI_Recv, MPI_Wait, MPI_Waitany, MPI_Waitall,MPI_Waitsome, MPI_Probe,MPI_Sendrecv, MPI_Sendrecv_replace
темно-синий
5. Операцииполучения/проверки без блокировки
MPI_Irecv,MPI_Test, MPI_Testany, MPI_Testall, MPI_Testsome, MPI_Iprobe голубой
6. Другие(малоиспользуемые) операции
MPI_Request_free,MPI_Cancel, MPI_Test_cancelled, MPI_Send_init, MPI_Bsend_init, MPI_Ssend_init,MPI_Rsend_init, MPI_Recv_init, MPI_Start, MPI_Startall
светло-серый
7. Пользовательский код
светло-розовый