Сравнительная отладка OpenMP программ

 

Московский государственный университет им. М.В. Ломоносова

Факультет вычислительной математики и кибернетики

Кафедра системного программирования

Дипломная работа

Сравнительная отладка OpenMP программ

Выполнил: Литвинович А.В.

Студент группы 528

Научный руководитель:

профессор, доктор физ.-мат. наук

Крюков Виктор Алексеевич

Москва 2009

Содержание

Аннотация

Введение

. Модели параллельного программирования

.1 Отладка параллельных программ

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

. Обзор существующих средств отладки OpenMP-программ

. Схема функционирования и программная реализация системы сравнительной отладки OpenMP-программ

.1 Основы работы OpenMP

.2 Сбор трассы: Проблемы и решения

.2.1 Инструментация программ

.2.2 Получение трассы

.2.3 Запись трассы

.3 Сравнение трасс: Проблемы и решения

.3.1 Применимость сравнения трасс

.3.2 Трассировка для сравнения

.3.3 Проблемы при сравнении

.4 Подробности реализации

.4.1 Используемый формат файлов трассы

.4.2 Процесс сравнения трасс

Заключение

Список литературы

Аннотация

Данная работа посвящена разработке универсальной системы сравнительной отладки для программ, написанных на языке Фортран-OpenMP.

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

Ни одна из известных нам систем сравнительной отладки для Фортран-OpenMP не является универсальной, то есть способной принять произвольную инструментированную программу на данном языке, и провести сравнительную отладку. Имеющиеся инструменты входят в более общие системы, например разрабатываемый в NAS инструмент автоматического распараллеливания [14], и используют информацию о связях и зависимостях, доступную только при использовании данной системы.

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

Введение

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

Ярким подобным примером является расширение языков С/С++ и Fortran - OpenMP. Благодаря использованию директив компилятора, привычная последовательная программа легко может быть переделана для выполнения в параллельном режиме. Однако, такая простота в высшей степени обманчива как для новичков, так и для опытных программистов. Прежде чем говорить о проблемах отладки OpenMP программ, проведём краткий обзор темы параллельных вычислений.

1. Модели параллельного программирования

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

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

Модель передачи сообщений. В этой модели программа представляет собой совокупность процессов, каждый из которых имеет своё адресное пространство. Причем эти процессы взаимодействуют и синхронизируются только через передачу сообщений между собой. Для этой модели разработан стандарт MPI (Message Passing Interface);

Модель неструктурированных нитей. Программа представляется как совокупность нитей (threads), способных выполняться параллельно и имеющих общее адресное пространство. Имеющиеся средства синхронизации нитей позволяют организовывать доступ к общим ресурсам. Многие среды программирования поддерживают эту модель: Win32 threads, POSIX threads, Java threads;

Модель параллелизма по данным. Основным её представителем является язык HPF. В этой модели программист самостоятельно распределяет данные последовательной программы по процессорам. Далее последовательная программа преобразуется компилятором в параллельную, выполняющуюся либо в модели передачи сообщений, либо в модели с общей памятью. При этом каждый процессор производит вычисления только над теми данными, которые на него распределены;

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

Гибридная модель параллелизма по управлению с передачей сообщений. Программа представляет собой систему взаимодействующих MPI - процессов, каждый из которых программируется на OpenMP [4, 5, 6].

.1 Отладка параллельных программ

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

Отладка параллельных программ осложняется (в большей степени, чем отладка последовательных программ) так называемым эффектом вмешательства (probe effect): отлаживаемая программа может вести себя по-разному при её запуске с отладочным средством и без него. Таким образом, отладочное средство может маскировать некоторые ошибки или, наоборот, способствовать их проявлению.

Поначалу ситуация с отладчиками параллельных программ была примерно такой же, как с первыми языками программирования - каждый владелец параллельной вычислительной системы имел свои собственные средства отладки. В 1997 году усилия по стандартизации командного интерфейса интерактивного отладчика параллельных программ возглавил форум по отладке высокопроизводительного программного обеспечения - HPDF (High Performance Debugging Forum) консорциума по параллельным инструментальным средствам Ptools (The Parallel Tools Consortium). В результате в 1998 году была создана версия 1 стандарта командного интерфейса интерактивного отладчика, однако, до сих пор не известно ни одной реализации отладчика, удовлетворяющей этому стандарту. Казалось бы, почему? По-видимому, стандарт был создан слишком поздно. Ко времени его написания уже существовало несколько широко используемых средств отладки параллельных программ [6].

Отладка параллельных программ достойна отдельного рассмотрения (вне контекста отладки последовательных программ), по крайней мере, по двум причинам:

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

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

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

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

Анализ отладочной информации после завершения выполнения программы (post-mortem analysis). Во время выполнения сохраняется отладочная информация, анализ которой производится уже после завершения выполнения отлаживаемой программы. Использование данной методики позволяет минимизировать эффект вмешательства отладчика в программы для систем с распределённой памятью;

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

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

Методика «записать и воспроизвести» (record&replay). Данная методика предназначена для обнаружения трудновоспроизводимых ошибок. Отладка программы по этой методике состоит из выполнения отлаживаемой программы со сбором информации, необходимой для детерминированного воспроизведения её выполнения с последующими повторными детерминированными запусками этой программы с использованием собранной информации и возможностей интерактивной отладки (точек останова, точек контроля данных, и т.п.).

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

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

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

Данная работа рассматривает теоретические и практические проблемы трассировки и сравнительной отладки программ, написанных на языке Fortran-OpenMP.

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

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

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

3. Обзор существующих средств отладки OpenMP-программ

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

Чтобы получить обзор возможностей средств отладки и компиляторов OpenMP по обнаружению ошибок правильности, рассмотрим 8 существенно распространённых из них:

- (icc) Intel Compiler 9.0

(pgcc) Portland Group Compiler 6.0

(sun) Sun Compiler 5.7

(guide) Guide component of the KAP/Pro Toolset C/C++ 4.0

(xlc) IBM XL C/C++ Enterprise Edition 7.0

(ompi) OMPi Compiler 0.8.2

(assure) Assure component of the KAP/Pro Toolset C/C++ 4.0

- (itc) Intel Thread Checker 2.2

Таблица 1

№Проблемаiccpgccsunguidexlcompiassureitc0Доступ к разделяемым переменным------+О+О1Использование замков без flush--------2Чтение разделяемой переменной без flush-------+О3Программист забыл private------+О+О4Ordered без конструкции ordered-------+О5Переменная цикла как shared+К+К+К+К+К+К+К+К6Программист забыл for------+О+О7Попытка изменить количество нитей--------8unset_lock() из нити, не владеющей замком--------9Изменение переменной цикла----+К---

Буква, идущая в таблице 1 после плюсов, обозначает когда была опознана ошибка - во время (К)омпиляции или (О)ценки. Только у Assure/Intel Thread Checker имеется оценочный этап, идущий после реального выполнения программы. [7]

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

Ни одна из известных нам систем сравнительной отладки для Фортран-OpenMP не является универсальной, то есть способной принять произвольную инструментированную программу на данном языке, и провести сравнительную отладку. Имеющиеся инструменты входят в более общие системы, например разрабатываемый в NAS инструмент автоматического распараллеливания [14], и используют информацию о связях и зависимостях, доступную только при использовании данной системы. [11, 12, 14]

4. Схема функционирования и программная реализация системы сравнительной отладки OpenMP-программ

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

.1 Основы работы OpenMP

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

Рисунок 1

Код программы представляет собой последовательный код, в котором расположены директивы - рекомендации к параллельному исполнению. Директивы оформляются в виде директив препроцессора (С/С++), либо комментариев (Fortran), делая их невидимыми для обычного компилятора.

Операционная система имеет некоторый пул нитей и по требованию программы выделяет ей необходимое количество. Каждая нить идентифицируется номером в группе OpenMP и системным номером нити в операционной системе. В каждом параллельном регионе нити нумеруются подряд, начиная с нуля. Где нулевая нить - это основная нить, существующая до входа в текущую параллельную часть. При вложенном параллелизме, может оказаться, что одновременно, в разных группах будут существовать две или более нитей с одинаковыми OpenMP номерами. Даже если в программе будет встречаться два идентичных параллельных региона подряд, нельзя гарантировать, что в выполнении этих регионов будут принимать участие одни и те же нити (нити с одинаковыми системными номерами). Тем более, нельзя построить соответствие между системными номерами и OpenMP номерами нитей в подобном случае (рис. 2). [1, 5]

Рисунок 2

4.2 Сбор трассы: Проблемы и решения

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

4.2.1 Инструментация программ

Шаг инструментации подразумевает добавление в код исходной программы необходимых вызовов функций библиотеки трассировки.

Большинство OpenMP-директив можно представить в следующем виде:

$OMP <директива>[<клауза> [[,]<клауза>]...]

<структурный блок>$OMP END <директива>[<клауза> [[,]<клауза>]...]

где <директива> - это одна из следующих: PARALLEL, DO, SECTIONS, SINGLE, CRITICAL, MASTER, ORDERED, а <клауза> - содержит некоторую дополнительную информацию о директиве.

Для каждой OpenMP-директивы был разработан собственный набор функций для инструментации. Схематично инструментация программы выполняется следующим образом:

DBG_Before<директива> (<параметры функции>)$OMP <директива>[<клауза> [[,]<клауза>]...]DBG_<директива>Event (<параметры функции>) <структурный

блок>$OMP END <директива>[<клауза> [[,]<клауза>]...]DBG_After<директива> (<параметры функции>)

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

<length>*type=<type>*name1=<name>*file=<file>*line1=<number>*...**

Помимо директив, регистрируются все используемые в программе переменные (их тип, размерность для массивов, наличие спецификации SAVE или оператора DATA) и COMMON-блоки. Инструментируются все чтения/записи в переменные, входы/выходы из процедур. Реализована возможность управлять степенью подробности инструментации с помощью опций, задаваемых при инструментации, или директив, указанных в программе

Стоит отметить, что по желанию пользователя возможно трассирование на нескольких уровнях подробности. Возможны четыре уровня: OFF, MINIMAL, MODIFY, FULL. Каждый последующий уровень производит трассировку с большей степенью подробности. Уровень OFF не подразумевает трассирование данного класса событий [2, 5, 8].

4.2.2 Получение трассы

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

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

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

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

отладка программа трасса формат

4.2.3 Запись трассы

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

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

Первоначально появилось решение: «При вызове функции трассировки осуществляется запись соответствующей информации в файл.».

Довольно ярко выделяются два недостатка подобного подхода:

. Так как наша программа параллельная, то возможна ситуация, когда несколько нитей одновременно изъявят желание писать в файл, и возможно даже запишут. В результате информация в файле будет некорректна.

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

Видоизменяя решение, мы добавляем: «Каждая нить работает со своим файлом. Файл создаётся в начале параллельного региона, и закрывается в конце».

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

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

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

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

Тем не менее, остаются проблемы - например, при некорректном завершении работы трассируемой программы осуществить сброс накопленных сегментов скорее всего не удастся, и в результате пропадёт самая интересная часть трассы. К счастью, разработчики основных операционных систем давно придумали решение, пригодное для таких проблем - memory mapped файлы. Memory mapped файл - способ доступа к файлу через буфер в памяти, ассоциированный с ним. ОС гарантирует сохранение и синхронность данных в этом буфере с тем, что находится в файле на диске, тем самым решая проблему.

В реализации использована комбинация из memory mapped файлов и вышеописанной сегментации памяти. Размер сегмента был выбран равным 2 Мб. У каждой нити запись идёт в свой файл, плюс основной файл с настройками и контекстными строками.

4.3 Сравнение трасс: Проблемы и решения

.3.1 Применимость сравнения трасс

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

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

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

Точность вычислений и поведение процессора на операциях сравнения может приводить к ещё одному виду проблем. Если в коде встречаются условные операторы, зависящие от сравнения чисел, возможно возникновение ситуации, когда сравниваемые числа А и Б близки друг к другу, и на одном процессоре число А оказывается больше числа Б, а на другом - меньше, и управление пойдёт на них по совершенно разным веткам, делая сравнение невозможным. Другой вариант аналогичной проблемы - сравнение чисел с плавающей запятой на равенство, по-разному обрабатываемое разными процессорами при близости или особенности значений (например, +INF).

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

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

Обнаружение каких ошибок доступно для метода сравнения трасс?

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

Не синхронизованная запись в память, например если не указать зависимую переменную как Shared:

Условие гонки (Race condition): может быть обнаружено в некоторых ситуациях, т.к. вносит в программу недетерминизм. Сравнение трасс сможет указать место расхождения, вызванного данной ошибкой, тем самым указав пользователь на область, где нужно её искать.

.3.2 Трассировка для сравнения

Одна из основных проблем использования трассировки для сравнительной отладки - это замедление работы программы на порядки и неприемлемые объемы трассы, что ограничивает «лобовое» применение данного подхода для отладки реальных программ.

Проверки на модельных программах и некоторых тестах NAS-omp показали, что всего лишь наличия пустых вызовов инструментатора на уровне подробности FULL достаточно, чтобы замедлить выполнение программы в 5-18 раз относительно оптимизированной компилятором версии, или в 3-6 раз относительно не оптимизированной версии. Наличие одного оператора, считающего количество вызовов, ухудшает эти значения до 13-100 раз. Подсчёт вызовов даёт оценку размера трассы - имея в среднем 16.12 байт на вызов и около 1.5 миллионов вызовов в секунду, получаем от восьмидесяти гигабайт до десятков терабайт для программ работающих час и неделю соответственно.

На реализованной библиотеке и двух процессорах программа вычисления якобиана, выполняемая в чистом виде за 0.1 секунды, с полной трассировкой выполнилась за 18 секунд, и сгенерировала 450 Мб трассы. Получается, что при полной трассировке программа, работающая 1 час в чистом виде будет работать больше недели с трассировкой, и сгенерирует 16 Тб трассы, как и было рассчитано. Возникает необходимость сокращать размеры трассы.

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

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

На реализованной библиотеке вышеописанный тест, исполнявшийся 18 секунд и давший пол-гигабайта трассы, трассированный по данной схеме с границей в 2 итерации выполнялся 0.7 секунды и выдал 7 Мб трассы - в 50 раз быстрее и почти на 2 порядка меньше по объёму.

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

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

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

4.3.3 Проблемы при сравнении

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

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

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

4.4 Подробности реализации

Разработка системы сравнительной отладки производилась на языке С с использованием Intel(R) C++ Compiler 10.1.021, для сборки целевых программ использовался Intel(R) Visual Fortran Compiler 10.1.021. Было написано 1364 строки исходных кодов библиотеки трассировки и 391 строк исходных кодов программы сравнения трасс, 266 строк из которых у обоих программ общие.

Тестирование и замеры производились на персональном компьютере с двухядерным процессором Pentium D 3.4 Ггц, 4Гб RAM, под управлением Windows XP 32 bit. Архитектура системы позволяет ей с небольшими доработками заработать на машинах с ОС Unix/Linux.

Ограничения разработанной экспериментальной версии:

Никак не рассматриваются и не обрабатываются вызовы подпрограмм (Subroutines), заданных в тексте программы, что делает такие программы непригодными для сравнения, оставляя только возможность замеров времени и объёма трассы.

Прочие упрощения, предположения и известные почти-ошибки («глюки») помечены в коде комментариями FIXME: с описанием.

4.4.1 Используемый формат файлов трассы

Файлы трассы называются по схеме [id]_trace_номер_нити.log, например 000000001df9fcf8_trace_0.log. У основного файла вместо номера нити «main». В нём первой строкой записаны настройки трассировки - уровень, на котором она производилась, и размер граничных итераций для выборочной трассировки. За настройками следуют пронумерованные контекстные строки, описанные в разделе 4.2.1.

Файлы с трассами выполнения нитей начинаются строкой с идентификатором нити. После неё идёт непосредственно трасса в формате E номер_события C номер_контекстной строки|дополнительные_параметры. Пример фрагмента записи трассы приведён на рис. 3

Рисунок 3

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

·BeforeParallel (перед началом параллельного региона):

oPID: идентификатор параллельного региона. Регионы нумеруются последовательно, по мере входа и выхода из них.

oIF: значение, полученное в результате вычисления клаузы if или -1, если этой клаузы в текущей директиве parallel нет.

oNTR: значение, полученное в результате вычисления клаузы NUM_THREADS или -1, если этой клаузы в текущей директиве parallel нет.

·BeforeOMPLoop (начало параллельного цикла):

oI: номер первой итерации

oL: номер последней итерации

oS: шаг цикла

oCS: значение, полученное в результате вычисления выражения chunk_size, указанного в клаузе SCHEDULE или -1, если chunk_size не указан.

·OMPIter (начало очередной итерации параллельного цикла):

oIN: Номер начинающейся итерации

·WriteArrEnd (После записи в переменную):

oVR: номер контекстной строки переменной, в которую производилась запись

oVL: записанное в переменную значение

4.4.2 Процесс сравнения трасс

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

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

Основная рекурсивная функция сравнения трасс «do_the_compare» получает в качестве параметров списки нитей и идентификатор параллельного региона. Последовательный регион обозначается идентификатором 0. Вначале идёт сравнение событий нулевых нитей. Если обнаружено начало нового параллельного региона (событие E 1, BeforeParallel), то производится перебор текущих событий всех нитей обоих сторон. Создаются два списка, в которые заносятся все те нити, у которых текущие события соответствует началу параллельного региона с соответствующим идентификатором. Созданные списки затем используются как параметры рекурсивного вызова основной функции сравнения трасс «do_the_compare». Такая схема позволяет сравнение трасс со вложенным параллелизмом.

При обнаружении в трассе события начала параллельного цикла (событие E 14, BeforeOMPLoop), производится поиск нитей с событием начала первой итерации этого цикла. Если они найдены, то вызывается подпрограмма сравнения трасс с номерами соответствующих нитей в качастве параметров. По окончанию сравнения итерации происходит ряд проверок - проверка окончания цикла, проверка границ трассировки итераций если включена выборочная трассировка, вычисление следующей итерации. Если цикл заканчивается, то проверяется наличие событий окончания цикла (событие E 16, AfterOMPLoop). Если цикл ещё не закончен, то начинается поиск следующей итерации в текущих событиях нитей, и цикл проверки продолжается.

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

Результатом работы программы сравнения трасс может быть либо фраза «Completed comparing. No inconsistencies detected.», означающая, что расхождений обнаружено небыло, либо сообщение о первом найденном расхождении. Сообщения имеют формат «Inconsistency: A(строка_в_трассе): имя_файла:строка_файла=событие, B: имя_файла:строка_файла=событие», где данные после A относятся к первой трассе, а после B - ко второй. «имя_файла» и «строка_файла» указывают, где в исходном коде наблюдается расхождение, поля «событие» указывают, какие события наблюдались с обеих сторон.

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

Пример вывода программы сравнения трасс для ошибки «неинициализированная PRIVATE переменная» приведён на рисунке 4. Указанная в расхождении строка 43 содержала в себе оператор, использующий неинициализированную переменную.

Рисунок 4

В реализации сравнение происходит в среднем со скоростью 7Мб трассы в секунду (считая одну сторону). На тесте вычисления якобиана с внесённой ошибкой, заключающейся в объявлении переменной цикла как shared, расхождение было найдено в течении 0.1 секунды на трассе размером 2Мб.

Заключение

Была реализована экспериментальная версия системы сравнительной отладки Fortran-OpenMP программ, показывающая некоторые из описанных в данной работе подходов.

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

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

Работа показала возможность практической реализации универсальной системы сравнительной отладки OpenMP программ и работоспособность некоторых методов улучшения её производительности и уменьшения размеров трассы на 1-2 порядка относительно стандартного подхода полной трассировки.

Список литературы

1. OpenMP Application Program Interface. V2.5 [PDF]

2. В.А. Бахтин, Н.А. Коновалов, В.А. Крюков. Расширение языка Open MP Fortran для распределенных систем. Вопросы атомной науки и техники. сер. Математическое моделирование физических процессов. 2002 г. Вып.4. стр.65-70.

. В.А. Крюков. Разработка параллельных программ для вычислительных кластеров и сетей. Информационные технологии и вычислительные системы. № 1-2, 2003 г., стр. 42-61.

4. MPI: A Message-Passing Interface Standard [HTML]

. OpenMP Consortium [HTML]

. High Performance Debugging Forum [HTML]

. Michael Su¨ß and Claudia Leopold. Common Mistakes in OpenMP and How To Avoid Them [PDF]

. В.А. Бахтин. Интерфейс инструментации Fortran OpenMP-программ [DOC]

9. Использование трассировщика функций MPI [DOC]

10. Bernd Mohr, Allen D. Malony, Sameer Shende, and Felix Wolfand Prototype of a Performance Tool Interface for OpenMP [PDF]

. В.А. Алексахин, В.О. Баринова, В.А. Бахтин, В.Д. Емельянов, В.А. Крюков, Ю.Л. Сазанов. Средства отладки OpenMP программ. // Труды Всероссийской научной конференции Научный сервис в сети Интернет: решение больших задач, сентябрь 2008 г., г. Новороссийск. - М.: Изд-во МГУ, 2008, стр. 281-285.

. Крюков В.А., Кудрявцев М.В. Автоматизация отладки параллельных программ // Вычислительные методы и программирование. 2006. Том 7, раздел 2. 102-109.

. Intel 313445-001 US: Intel Thread Checker 3.1 Getting Started Guide [PDF]

. NAS Automatic Relative Debugging of OpenMP Programs

Московский государственный университет им. М.В. Ломоносова Факультет вычислительной математики и кибернетики Кафедра системного программирования

Больше работ по теме: