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

Текст из файла

12

Институт прикладной математики им. М.В.Келдыша

Российская Академия наук

DVM отладчик

Предварительный дизайн

Октябрь, 1999

Оглавление

1 Функции DVM отладчика 3

1.1 Метод динамического контроля DVM-указаний 4

1.2 Типы выявляемых ошибок 4

1.3 Метод сравнения результатов выполнения 5

2 Состав DVM отладчика 5

3 Подход и принципы реализации DVM-отладчика 6

3.1 Метод контроля DVM-указаний 6

3.1.1 Контроль инициализации переменных и элементов массивов 6

3.1.2 Контроль доступа к элементам распределенного массива 7

3.1.3 Контроль приватных и неизменяемых переменных 8

3.1.4 Контроль редукционных переменных 8

3.1.5 Контроль использования буфера удаленных элементов 8

3.2 Метод сравнения результатов выполнения 9

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

3.2.2 Сравнение результатов 9

3.2.3 Контроль редукционных операций 10

1Функции DVM отладчика

DVM отладчик предназначен для отладки DVM-программ (написанных на языках Fortran-DVM и C-DVM). Для отладки DVM-программ используется следующий подход. Сначала программа отлаживается на рабочей станции как последовательная программа с использованием обычных средств отладки. Затем программа выполняется на той же рабочей станции в специальном режиме проверки DVM-директив. На третьем этапе программа выполняется на параллельном компьютере в специальном режиме сравнения промежуточных результатов выполнения с эталонными результатами (например, с результатами последовательного выполнения).

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

В общем случае можно выделить следующие четыре класса ошибок:

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

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

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

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

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

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

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

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

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

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

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

1.1Метод динамического контроля DVM-указаний

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

1.2Типы выявляемых ошибок

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

1. Необъявленная зависимость по данным в параллельном цикле или между параллельными задачами.

2. Чтение неинициализированных переменных.

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

4. Использование редукционных переменных после запуска асинхронной редукции, но до ее завершения.

5. Выход за пределы распределенного массива.

6. Необъявленный доступ к нелокальным элементам распределенного массива.

7. Запись в теневые грани распределенного массива.

8. Чтение теневых элементов массива до завершения операции их обновления.

1.3Метод сравнения результатов выполнения

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

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

2Состав DVM отладчика

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

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

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

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

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

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

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

• Блок накопления трассировки в памяти. Производит накопление и структуризацию трассировочных событий в ходе выполнения программы.

• Блок записи трассировки в файл. Используется из блока накопления трассировки при задании режима записи трассировки в ходе выполнения программы.

• Блок чтения трассировки из файлов. Использует как вспомогательный блок накопления трассировки.

• Блок сравнения трассировок. Сравнивает события трассируемой программы с эталонной трассировкой, сформированной предварительно в памяти блоком накопления трассировки.

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

3Подход и принципы реализации DVM-отладчика

3.1Метод контроля DVM-указаний

Все данные, которые могут использоваться в DVM-программе, разделяются на следующие классы:

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

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

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

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

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

Исходя из этих классов данных, строятся алгоритмы проверки.

3.1.1Контроль инициализации переменных и элементов массивов

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

3.1.2Контроль доступа к элементам распределенного массива

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

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

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

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

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

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

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

3.1.3 Контроль приватных и неизменяемых переменных

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

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

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

3.1.4Контроль редукционных переменных

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

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

• Параллельная конструкция завершилась, но операция асинхронной редукции еще не стартовала.

• Для переменной запущена операция асинхронной редукции. Установка данного флага происходит при запуске асинхронной редукции.

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

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

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

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

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

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

Список файлов учебной работы