Основы распараллеливания программ, их динамический анализ (стр. 4 из 5)

программу-инструментатор (реализована в рамках отдельной работы);

библиотеку, содержащую реализации функций анализатора.

Библиотека-анализатор была реализована на языке C++. Этот язык легко может быть использован совместно с языками Си и Фортран, которые широко используются для программирования вычислительных задач.

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

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

4.1 Инструментация

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

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

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

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

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

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

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

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

Учитывая вышесказанное, был получен следующий интерфейс библиотеки анализатора.

DA_init() – инициализация библиотеки анализа, необходимо вызывать до вызова любой другой функции.

DA_exit() – завершение анализа и сохранение результатов

DA_SagePos(long sageNumber) – сообщает анализатору о начале оператора с идентификатором sageNumber

DA_LinePos(long lineNumber, char * filename) – сообщает анализатору о текущем номере строки и файле.

DA_WriteBegin(void * addr, long size), DA_WriteEnd() – пара функций, отмечающие начало и завершение оператора присваивания – запись в ячейку памяти

DA_Read(void * addr, long size) – чтение ячейки памяти

DA_LoopDo(), DA_LoopFor(), DA_LoopWhile(), DA_LoopDowhile() – начало соответствующего цикла.

DA_LoopIter() – начало очередной итерации цикла

DA_LoopEnd() – завершение цикла

RegArrId(long id, void * addr, long rank, long size[], long elemsize, const char * name) – регистрация нединамического массива в анализаторе.

RegArr(void * addr, long rank, long size[], long elemsize, const char * name) – регистрация динамического массива.

DA_UnregArrId(long id), DA_UnregArr(void * addr) – соответствующие функции отмены регистрации массивов.

4.2 Формат результатов

В качестве результата анализатор предоставляет дерево контекстов с дополнительной информацией, размещенной в вершинах:

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

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

Также в узлах накапливается профилировочная информация, которая может быть полезной при принятии решений о распараллеливании:

количество выполнений поддерева с корнем в данном узле,

общее время выполнения поддерева с корнем в данном узле,

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

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

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

Основу библиотеки работы с результатами составляет класс ContextNode, представляющий вершину дерева контекстов. В этом классе предусмотрены методы для:

добавления непосредственных потомков,

навигации по дереву контекстов: переход к родительской вершине, к потомкам, к следующей вершине на том же уровне,

получения и изменения идентификационной информации о вершине: Sage-номер, тип вершины, номер строки исходного файла программы,

получения и изменения информации о зависимостях по данным, сохраненных в данной вершине,

получения и изменения профилировочной информации,

сохранения информации в файл и загрузки информации из файла.

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

Dependence – класс, представляющий одну зависимость, содержащий вектор расстояния,

DependenceStore – класс, предназначенный для хранения всех зависимостей одного типа.

Информация о массивах, используемых в программе, представляется классами CArrays и CArrayData. Класс CArrayData содержит информацию об одном массиве:

имя массива, номер строки, в котором он был определен,

Sage-номер или внутренний идентификатор массива для динамических массивов,

число измерений массива и размеры каждого измерения,

размер одного элемента массива.

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

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

4.3 Внутреннее устройство анализатора

Внутренняя структура анализатора показана на Рисунке 2.

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

Рисунок 2 Внутренняя структура анализатора

Ядро анализатора использует внутренний интерфейс, основные операции которого соответствуют операциям интерфейса анализатора, описанным в разделе 4.1. Имеются, тем не менее, незначительные отличия, обусловленные соображениями удобства и простоты. Блок внешнего интерфейса необходим для преобразования вызовов функций анализа в вызовы интерфейса ядра. Исторически такое преобразование было необходимо в связи с тем, что первая версия анализатора была реализована на основе интерфейса отладчика системы DVM [6]. Этот отладчик предназначен для проверки корректности DVM-программы посредством моделирования ее параллельного выполнения, а также посредством накопления и сравнения трасс при ее последовательном и параллельном выполнении. В его интерфейс входят базовые функции, необходимые динамическому анализатору: чтение и запись значений переменных, начало и завершение циклов, начало итераций циклов. Поэтому до появления специального инструментатора было возможно использовать инструментатор, предназначенный для отладчика DVM. В данный момент наличие блока внешнего интерфейса позволяет при необходимости изменять интерфейс анализатора, не затрагивая основную часть библиотеки.

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