Размещено на http://www.allbest.ru/

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

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

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

ДИПЛОМНАЯ РАБОТА

Повышение эффективности отладки DVM_программ

Выполнил:

Кудрявцев Максим Владимирович

группа 527

Москва 2003

Введение

Система DVM [1], разработанная в Институте прикладной математики им. М.В. Келдыша РАН в 1998 году предназначена для разработки мобильных и эффективных программ для ЭВМ различной архитектуры.

Существующие средства отладки системы DVM сильно замедляют выполнение программы и используют большое количество памяти для накопления трассировки. С этим можно бороться, используя высокопроизводительную ЭВМ с большим количеством как оперативной, так и внешней памяти, либо можно предложить пользователю запускать его программу на модельных данных. У последнего варианта есть недостатки. Например, могут возникнуть сложности с подбором модельных данных (программа «чужая», для подбора модельных данных в ней надо разбираться) или программа с модельными данными может давать правильные результаты (ошибка может не проявляться).

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

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

Глава 1. Параллельные программы и их отладка

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

Растущие потребности человека заставляют его искать способы увеличения производительности выполнения компьютерных программ. Что обычно делают люди для того, чтобы увеличить производительность своей работы? Есть несколько способов [2]: работать интенсивнее, работать сообразительнее и попросить чьей-либо помощи. Можно привести аналогию по отношению к вычислительной технике: чтобы повысить производительность выполнения компьютерных программ можно использовать более мощное аппаратное обеспечение, более эффективные алгоритмы (как на уровне программного обеспечения, так и аппаратного), либо использовать возможности параллельной обработки информации.

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

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

В настоящее время существуют следующие модели программирования [3]:

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

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

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

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

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

§ Модель параллелизма по данным и управлению - DVM (Distributed Virtual Machine, Distributed Virtual Memory) [1].

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

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

§ распределение элементов массива между процессорами;

§ распределение витков цикла между процессорами;

§ спецификация параллельно выполняющихся секций программы (параллельных задач) и отображение их на процессоры;

§ организация эффективного доступа к удаленным (расположенным на других процессорах) данным;

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

Модель выполнения DVM-программы можно упрощенно описать следующим образом [3].

Параллельная программа на исходном языке Фортран-DVM (или Си-DVM) при помощи специального компилятора превращается в программу на языке Фортран 77 (или Си), содержащую вызовы функций системы поддержки Lib-DVM, и выполняющуюся в соответствии с моделью SPMD (одна программа - много данных) на каждом выделенном задаче процессоре.

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

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

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

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

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

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

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

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

§ растёт сложность программирования и, следовательно, вероятность совершения ошибок и сложность отладки;

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

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

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

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

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

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

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

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

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

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

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

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

- выполнения отлаживаемой программы со сбором информации, необходимой для детерминированного воспроизведения её выполнения;

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

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

- сравнение данных может производиться в процессе выполнения обоих программ;

- при выполнении одной программы её данные сравниваются с данными трассировки, полученной при выполнении другой;

- сравниваются данные трассировок обоих программ.

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

Существующие реализации методики сравнительной отладки в области параллельных вычислений - сравнительный отладчик Guard [8], исследовательский проект NASA Ames (прототипная реализация системы сравнительной отладки для программ, полученных при помощи средств автоматизированного распараллеливания (computer-aided tools) [9]) и отладчик системы DVM [1], который кроме методики сравнительной отладки реализует методику динамического контроля.

Глава 2. Отладка в системе DVM

2.1 Основные положения

Отладчик системы DVM (входит в состав системы времени выполнения) предназначен для функциональной отладки параллельных программ, написанных на языках системы DVM - Fortran-DVM и C-DVM [10, 11].

Предлагается следующая методика отладки DVM-программ [1, 12, 13]:

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

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

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

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

Можно выделить следующие классы ошибок [1, 12, 13]:

1. Синтаксические ошибки в DVM-указаниях (неправильная запись оператора, отсутствие скобки и т.д.), а также нарушение статической семантики.

2. Неправильная последовательность выполнения DVM-указаний или неправильные параметры DVM-указаний.

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

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

Синтаксические ошибки в программе выявляются при компиляции.

Ошибки второго класса обнаруживаются библиотекой Lib-DVM при параллельном выполнении программы: функции библиотеки проверяют корректность порядка выполнения DVM-указаний и передаваемых параметров.

Ошибки третьего класса должны выявляться динамическим отладчиком при:

§ запуске DVM-программы на одном процессоре в режиме динамического контроля;

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

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

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

§ начало последовательного или параллельного цикла;

§ завершение последовательного или параллельного цикла;

§ начало нового витка цикла;

§ обращение к переменной на чтение;

§ перед обращением к переменной на запись;

§ после обращения к переменной на запись.

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

В рамках методик динамического контроля и сравнительной отладки отладчик системы DVM предоставляет возможности:

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

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

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

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

2.2 Накопление трассировки

Так как размер трассировочного файла может достигать очень больших размеров, то пользователю предоставляются следующие возможности сокращения объема трассировки:

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

2. При запуске программы с помощью специального параметра можно задать один из следующих возможных уровней подробности трассировки:

§ отсутствие трассировки (уровень NONE);

§ трассировка редукционных операций, начала и завершения циклов или областей задач и начала витков или задач (уровень MINIMAL);

§ предыдущий уровень, плюс трассировка модификаций переменных и результатов вычисления редукции (уровень MODIFY);

§ трассировка всех событий (уровень FULL).

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

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

Использование возможности (2) без комбинации с другими возможностями представляется нам не очень перспективным, поскольку вероятность обнаружения ошибки с использованием уровня подробности трассировки MINIMAL достаточно мала, а размер трассировки и время выполнения программы на уровнях MODIFY и FULL высоки.

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

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

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

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

2.3 Сравнение результатов вычислений

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

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

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

2.4 Файл трассировки

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

Формат заголовка аналогичен формату конфигурационного файла и имеет следующий вид:

MODE = <NONE | MINIMAL | MODIFY | FULL>, [EMPTYITER] # Begin trace header. Don't modify these records <SL | PL | TR> <номер конструкции> (<номер объемлющей конструкции>) [<ранг цикла>] {<имя файла>, <номер строки>} = <NONE | MINIMAL | MODIFY | FULL>, (<измерение>:<первый виток>, < последний виток>, <шаг >), … EL: <номер конструкции>

…

<SL | PL | TR> <номер конструкции> (<номер объемлющей конструкции>) [<ранг цикла>] {<имя файла>, <номер строки>} = <NONE | MINIMAL | MODIFY | FULL>, (<измерение>:<первый виток>, < последний виток>, <шаг >), … EL: <номер конструкции>

END_HEADER # End trace header

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

После заголовка, в файле трассировки идут записи следующих типов и форматов:

§ Чтение переменной: RD: [<тип переменной>] <имя переменной> = <значение>; {<файл>, <строка>}

§ Начало оператора присваивания нового значения переменной: BW: [<тип переменной>] <имя переменной> ; {<файл>, <строка>}

§ Запись нового значения переменной: AW: [<тип переменной>] < имя переменной > = <значение>; {<файл>, <строка>}

§ Чтение редукционной переменной: RV_RD: [<тип переменной >] < имя переменной > = < значение >; {< файл>, <строка >}

§ Начало оператора присваивания нового значения редукционной переменной: RV_BW: [<тип переменной >] < имя переменной >; {< файл>, <строка >}

§ Запись нового значения редукционной переменной: RV_AW: [<тип переменной>] <имя переменной> = <значение>; {<файл>, <строка>}

§ Результат вычисления редукции: RV: [<тип переменной >] <значение>; {< файл>, <строка >}

§ Завершение блока собственных вычислений в последовательной части программы: SKP: {< файл>, <строка >}

§ Начало параллельного цикла: PL: <номер конструкции> (<номер объемлющей конструкции>) [<ранг цикла>] ; {<файл>, <строка>}

§ Начало последовательного цикла: SL: <номер конструкции> (<номер объемлющей конструкции>) [<ранг цикла (всегда равен единице)>] ; {<файл>, <строка>}

§ Начало области параллельных задач: TR: <номер конструкции> (<номер объемлющей конструкции>) [<ранг области (всегда равен единице)>] ; {<файл>, <строка>}

§ Начало витка или параллельной задачи: IT: <абсолютный индекс витка (вычисляется из значений всех индексных переменных цикла) или номер задачи>, (<значение индексной переменной 1>,< значение индексной переменной 2>,…).

§ Завершение параллельного или последовательного цикла или области задач: EL: <номер конструкции>; {<файл>, <строка>}

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

2.5 Конфигурационный файл трассировки

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

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

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

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

Комментарии в конфигурационном файле начинаются с символа `#'. Вся строка после этого символа игнорируется. Формат конфигурационного файла аналогичен формату заголовка файла трассировки. Некоторые подробности здесь опущены, см. [1, 12, 13].

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

С учётом выделенных замечаний для повышения эффективности отладки DVM-программ предлагается:

1. Разработать и внедрить в существующий отладчик системы DVM дополнительные возможности управления размером трассировки, а именно

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

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

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

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

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

Глава 3. Новые возможности управления размером трассировки

3.1 Нумерация параллельных конструкций

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

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

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

§ дисциплина их прохождения: любая параллельная конструкция единожды выполняется на всех процессорах текущей процессорной системы (вне области задач - на всех процессорах системы, внутри области задач - на всех процессорах текущей подзадачи);

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

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

if (NUMBER_OF_PROCESSORS() == 1)

{

. . .

<параллельный цикл 1>

. . .

}

else

{

. . .

<параллельный цикл 2>

. . .

}

Поскольку нумерацию предполагается использовать для указания точек и диапазонов, то имеет смысл отличать начало конструкции от её конца. Предлагается следующий алгоритм нумерации. Начнём нумерацию с единицы. Параллельные конструкции, не находящиеся внутри области задач нумеруются по порядку. Начало конструкции и её конец различаются указанием символов «B» и «E» соответственно после номера конструкции с точкой. Параллельные циклы находящиеся внутри подзадачи области задач будем нумеровать следующим образом:

<номер области задач>.<номер подзадачи>.<номер параллельного цикла внутри подзадачи (нумерация начинается с единицы)>.<B или E>

Заметим, что вложенные друг в друга параллельные циклы недопустимы.

Опишем изменения синтаксиса записей конструкций трассировки:

§ Начало параллельного цикла:

PL: <номер цикла> (<номер родительской конструкции или пусто>) [<размерность цикла>] = <уровень трассировки: FULL, MODIFY, MINIMAL, NONE>, (<диапазон трассируемых итераций (может отсутствовать)>); {<имя файла>, <номер строки>}, <динамический номер конструкции>

Начало области задач:

TR: <номер области> (<номер родительской конструкции или пусто>) [<размерность области>] = <уровень трассировки: FULL, MODIFY, MINIMAL, NONE>, (<диапазон трассируемых задач>); {<имя файла>, <номер строки>}, <динамический номер конструкции>

§ Завершение параллельного или последовательного цикла или области задач:

EL: <номер конструкции>; {<имя файла>, <номер строки>}, <динамический номер конструкции (для посл. циклов отсутствует)>

Примеры нумерации:

§ параллельный цикл:

PL: 2() [2]; {"a.cdv", 31}, 6.B

...

EL: 2; {"a.cdv", 31}, 6.E

§ область задач:

TR: 5(10) [1]; {"b.cdv", 95}, 256.B

...

EL: 5; {"b.cdv", 95}, 256.E

§ параллельный цикл внутри области задач:

TR: 5(10) [1]; {"c.cdv", 95}, 256.B

...

PL: 13(5) [2]; {"c.cdv", 40}, 256.3.4.B

...

EL: 13; {"c.cdv", 40}, 256.3.4.E

...

EL: 5; {"c.cdv", 95}, 256.E

Особенности реализации

Библиотека времени выполнения системы DVM написана на языке программирования Си, поэтому наши модификации библиотеки тоже производятся на этом языка.

Для хранения номеров используется тип NUMBER:

typedef struct tag_NUMBER

{

struct level

{

long val; /* number */

char ref; /* 'B' - loop begin, 'E' - loop end */

};

/* main level */

struct level main;

/* nested level */

struct level nested;

/* selector: which level to choose, 0 - main, 1 - nested */

byte selector;

/* iteration if we are in task region */

long iter;

}

NUMBER;

Значение 1 поля selector означает, что данная структура является номером параллельного цикла внутри области задач. Поле main используется для хранения информации о номере области задач, поле nested - для хранения информации о номере вложенного в область задач параллельного цикла. В противном случае (значение поля selector 0) структура нумерует параллельный цикл, номер которого находится в поле main.

Функции для работы с номерами:

char* to_string(NUMBER *num, char *buffer)

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

byte parse_number(char *str, NUMBER *num)

Функция переводит строковое представление номера в числовое. В случае синтаксической ошибки возвращается нулевое значение, иначе единица

int num_cmp(NUMBER *num1, NUMBER *num2)

Функция производит сравнение двух номеров. Возвращаемые значения:

0: номера равны 1: num1 > num2 -1: num1 < num2 -2: номера не сравнимы, например, 1.0.1.E и 1.1.1.E

void num_init(NUMBER *num)

Функция инициализирует передаваемую ей структуру нулевым номером

void ploop_beg(NUMBER *num)

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

void ploop_end(NUMBER *num)

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

void tr_beg(NUMBER *num)

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

void tr_it(NUMBER *num, long iter)

Функция устанавливает передаваемому номеру области задач номер итерации iter

void tr_end(NUMBER *num)

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

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

3.2 Задание точек начала и окончания подробной трассировки

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

Точки начала и окончания подробной трассировки задаются при помощи параметров TraceOptions.StartPoint и TraceOptions.FinishPoint соответственно. Требуемый уровень подробности устанавливается при помощи параметра TraceOptions.TraceLevel файла параметров, при этом учитываются и другие возможности управления подробностью Более подробно см. [1, 12, 13]. За пределами указанного интервала в трассировку сохраняются только записи начал и завершений конструкций. Указание пустой строки в качестве значения параметра включает подробную трассировку с начала выполнения программы (в случае параметра TraceOptions.StartPoint), либо подробная трассировка собирается до завершения её выполнения (в случае параметра TraceOptions.FinishPoint). Например, если в качестве обоих параметров заданы пустые строки (по умолчанию), то трассировка с заданным уровнем подробности собирается на протяжении всего выполнения программы.

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

1. Обе точки заданы внутри разных подзадач одной и той же области задач. Такое задание некорректно, поэтому будет выдано сообщение об ошибке Сообщения об ошибках и их краткие описания даны в Приложении 1.

2. Обе точки заданы внутри подзадачи одной и той же области задач. В этом случае трассировка заданной подробности будет собираться в заданном интервале только одной подзадачи. Однако пользователь отладчика может указать и всю область задач целиком, изменяя значения, указываемые в нумерации после первого символа точки. Например, при желании получить подробную трассировку не с точки 13.2.4.B по точку 13.2.6.E, а для всей области задач целиком он может указать в качестве первой точки точку 13.B, в качестве второй - 13.E.

3. Первая точка находится до области задач, вторая - внутри подзадачи. В этом случае, начиная с первой точки будет собираться трассировка заданной подробности, далее - только в пределах интересующей подзадачи до требуемой точки. Также как и в случае (2) можно указать отладчику выключить подробную трассировку либо перед началом области задач, либо после этой области задач.

4. Первая точка находится внутри подзадачи, вторая - после области задач. В этом случае трассировка заданной подробности начнёт собираться после заданной конструкции внутри требуемой подзадачи и закончится за пределами области задач в заданной точке. Также как и в случае (2) можно указать отладчику включить подробную трассировку либо с начала области задач, либо после этой области задач.

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

Особенности реализации

При работе с точками начала/окончания подробной трассировки используются функции, описанные в предыдущей главе. Можно отметить, что в структуру TRACE были добавлены два поля (NUMBER *StartPoint, *FinishPoint), хранящие текущие ограничения по нумерации.

3.3 Задание ограничений на трассировку итераций

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

Введём пять параметров Ig_left, Ig_right, Iloc_left, Iloc_right, Irep_left. Будем считать, что параметр не задан, если его значение равно -1. Если все параметры не заданы (по умолчанию), то ограничения на трассировку итераций не действуют.

Опишем алгоритм ограничений на трассировку итераций:

Пусть текущий цикл последовательный. Если параметр Irep_left не задан, то текущая итерация трассируется.

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

Пусть текущий цикл параллельный. Если не задан ни один из параметров Ig_left, Ig_right, Iloc_left, Iloc_right, то текущая итерация трассируется.

Рассмотрим следующие характеристики текущего цикла:

§ upper - массив максимальных значений переменных цикла (по каждому измерению);

§ lower - массив минимальных значений переменных цикла;

§ step - массив шагов переменных цикла;

§ loc_upper - массив максимальных значений переменных цикла на данном процессоре;

§ loc_lower - массив минимальных значений переменных цикла на данном процессоре.

Построим множества витков:



Пусть index - массив индексов текущей итерации цикла. Очевидно, что выполняется неравенство lower[i] ? index[i] ? upper[i].

Если , то текущая итерация трассируется, в противном случае текущая итерация не трассируется.

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

Особенности реализации

При реализации предложенных ограничений на трассировку итераций было написано 2 функции, вызовы которых были вставлены в другие функции отладчика системы DVM.

byte was_not_traced(long *index)

Функция возвращает 1, если указанная в качестве параметра итерация не трассировалась в текущем параллельном цикле в файле трассировки. В противном случае функция возвращает 0

byte out_of_bounds(long *index)

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

На время выполнения нетрассируемых итераций для повышения быстродействия отладчика вызовы отладочных функций trc_put_variable и trc_cmp_variable через указатели подменяются на вызовы функции dummy_var, которая имеет такой же прототип, как и указанные функции, но никаких действий не производит.

Глава 4. Уровень подробности контрольных сумм

Как уже было сказано выше, уровень подробности трассировки MINIMAL не позволяет обнаруживать ошибки, отличные от неправильной спецификации редукционных операций, а размер трассировки и время выполнения программы при использовании уровней подробности MODIFY и FULL высоки. Это не позволяет пользователю отлаживать программы на целевых данных. Уровень подробности контрольных сумм позволяет отлаживать программы на целевых данных, поскольку он не требует большого объёма памяти (как оперативной, так и внешней) и работает быстрее уровней подробности MODIFY и FULL Результаты сравнения производительности см. в главе 6. Так же этот уровень подробности определяет (если, конечно, результаты ошибки отражаются на контрольных суммах массивов) диапазон нумерации, для которого имеет смысл рассматривать подробную трассировку. Уровень подробности контрольных сумм является в некоторой степени компромиссом между точностью локализации ошибки и размером трассировки (а так же и временем выполнения программы).

Включение уровня подробности контрольных сумм производится при помощи установки параметру TraceOptions.TraceLevel значения 4 в файле параметров. Переключение между режимами создания конфигурационного файла, накопления трассировки, сравнения контрольных сумм осуществляется в соответствии с документацией к системе DVM [1, 12, 13].

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

Дальнейшее рассмотрение уровня подробности контрольных сумм удобно произвести по следующему плану:

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

2. Запись/чтение трассировки и конфигурационного файла трассировки с контрольными суммами.

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

4.1 Накопление контрольных сумм

К элементам массивов возможны следующие типы доступа:

a) чтение;

b) запись;

c) чтение и запись.

Далее, под словами «доступ к массиву» будем понимать доступ к элементам этого массива.

Контрольные суммы вычисляются по завершении выполнения параллельных циклов и областей задач для тех массивов, к которым был доступ в этом цикле (или области задач), определяемый параметром TraceOptions.ChecksumMode.

§ TraceOptions.ChecksumMode = 1 (по умолчанию). В этом случае контрольные суммы будут вычисляться для массивов, к которым производился доступ типа b) или c).

§ TraceOptions.ChecksumMode = 2. Контрольные суммы будут вычисляться для массивов, к которым производился доступ любого из указанных типов.

Контрольная сумма элементов массива вычисляется по следующей формуле:



где - размеры измерений массива Array, в пределах которых меняются индексные переменные соответственно.

Деление на количество элементов необходимо для защиты от переполнения.

Замечания:

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

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