WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

загрузка...
   Добро пожаловать!

Pages:     | 1 || 3 | 4 |

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

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

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

Фортран-программа Анализатор 1 Анализатор Описание ЭВМ База данных Эксперт 1 Эксперт Фортран-DVM-программа Фортран-OpenMP-программа Рис. 1. Схема работы компилятора ПАРФОР.

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

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

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

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

На вход эксперту поступает следующая информация:

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

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

Например, когда в цикле вычисляется сумма элементов массива) • описание ЭВМ • параметры задачи (значения переменных, которые определяют размеры массивов и количество витков циклов).

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

Выходом эксперта является текст параллельной программы.

Текущая версия компилятора ПАРФОР состоит из трех компонентов:

1. статический анализатор Фортран-программ ВерБа, 2. DVM-эксперт (преобразует исходные Фортран-программы в параллельные программы для кластера на языке Фортран-DVM), 3. Система управления базой данных компилятора.

Компилятор ПАРФОР на данный момент ориентирован на автоматическое распараллеливание программ из класса задач, при решении которых используются разностные методы на статических структурных сетках.

К тому же эти программы должны удовлетворять следующим требованиям:

• быть написаны на языке Фортран 77;

• не содержать процедуры или допускать их инлайн-подстановку.

Эти ограничения были приняты, потому что статический анализатор компилятора ПАРФОР работает только с программами на языке Фортран 77 и не осуществляет межпроцедурный анализ зависимостей.

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

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

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

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

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

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

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

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

Набор характеристик эффективности выполнения для каждого интервала выполнения выглядит следующим образом:

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

• общее время использования процессоров, то есть произведение времени выполнения на число процессоров;

• полезное время – предполагаемое время выполнения на одном процессоре, равное сумме следующих характеристик:

- полезное процессорное время;

- полезные системные расходы;

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

• коэффициент эффективности, равный отношению полезного времени к общему времени;

• потерянное время, равное сумме следующих характеристик:

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

- время коммуникаций;

- время простоев процессоров;

• разбалансировка загрузки процессоров при параллельных вычислениях - это потенциальные потери, которые могут быть вызваны неравномерностью загрузки процессоров;

• общее время перекрытия обменов сообщениями и вычислений.

Алгоритм моделирования связан с особенностями DVM-системы.

Как было сказано выше, язык Фортран-DVM представляет собой язык Фортран, расширенный спецификациями параллелизма. Эти спецификации можно условно разделить на три подмножества:

• распределение данных;

• распределение вычислений;

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

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

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

• Отображение абстрактной параллельной машины на заданную при запуске решетку процессоров.

• Создание и уничтожение распределенного массива.

• Отображение распределенного массива на абстрактную параллельную машину.

• Отображение параллельного цикла на абстрактную параллельную машину.

• Отображение параллельных задач на абстрактную параллельную машину.

• Выполнение редукционных операций.

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

• Создание и загрузка буферов для доступа к удаленным данным.

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

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

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

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

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

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

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

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

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

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

Моделирование удаленного доступа к секциям массива подобно моделированию копирования.

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

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

Необходимо заметить, что точное прогнозирование времени параллельного выполнения практически невозможно для современных ЭВМ.

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

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

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

Pages:     | 1 || 3 | 4 |






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»