Национальный исследовательский университет "Высшая школа экономики" Рассматривается реализация программного инструментария для выработки эффективных стратегий преобразования представлений информационных графов алгоритмов с целью как выявления скрытого параллелизма, так и определения рационального плана (расписания) выполнения параллельных частей программ при учете ограничений реальных многопроцессорных вычислительных систем. Для достижения гибкости разработки сценариев преобразований представлений графа используется встроенный скриптовый язык Lua. Ключевые слова: информационный граф алгоритма, тонкая информационная структура программы, скрытый параллелизм, ярусно-параллельная форма информационного графа, преобразования представления информационного графа, встроенный скриптовый язык программирования Lua, рациональная стратегия построения плана выполнения параллельной программы.
Информационный граф алгоритма (вычислительная модель “операторы - операнды”, далее ИГА) суть наиболее простое представление конкретного алгоритма в графовом виде. ИГА описывает исключительно информационные зависимости алгоритма (вершины графа соответствуют отдельным операциям - преобразователям информации (арифметико-логические действия и т.п.); наличие дуги между вершинами i,j говорит о необходимости при выполнении операции j априорного существования аргументов (операндов), выработанных операцией i; в случае независимости выполнения операций i и j дуга между вершинами отсутствует). Свойства ИГА: ацикличность, направленность, детерминированность. Конечно, в данном случае термин "операторы" в известной степени условен, ибо под "операторами" можно понимать отдельные независимые по данным последовательности вычислений (гранулы параллелизма) любого (желательно приблизительно одинакового) размера.
Существуют и иные формы графового представления алгоритма - напр., с вершинами -
распознавателями (это условные операторы, переключатели и др.), которые определяют
последовательность срабатывания преобразователей при работе программы [
Формально процедура выявления параллелизма по информационному графу алгоритма (ИГА) состоит в построении его ярусно-параллельной формы (ЯПФ). Ярусно-Параллельная Форма (ЯПФ, SPF – Stacked Parallel Form) информационного графа алгоритма суть форма представления графа, при которой операторы, могущиеся выполняться независимо друг от друга (фактически параллельно) располагаются на одном уровне (ярусе). Представление графа в ЯПФ - одно из наиболее мощных средств выявления скрытого параллелизма в алгоритме. Формально ЯПФ строится на основе ИГА с помощью несложного алгоритма трудоемкостью порядка O(N2); на рис. 1 приведена ЯПФ графа процедуры вычисления вещественных корней полного квадратного уравнения.
Рис. 1. Информационный граф (см. рисунок слева, общий вид: узлы 11,12,13 - входные данные, 9 и 10 - вычисление выходных данных) и его представление в ЯПФ (справа) процедуры нахождения вещественных корней полного квадратного уравнения (цифры крайние справа - номера ярусов ЯПФ) agora.guru.ru/pavt Высота ЯПФ (вычисляемая чрез число ярусов) определяет общее время выполнения алгоритма, ширина ЯПФ – максимальное число задействованных отдельных (параллельно работающих) вычислителей (напр., отдельных ядер процессора) данной МВС. 3. Применяемые при исследовании методы
Реальные ЯПФ информационных графов обладают большой неравномерностью распределения числа операторов по ярусам, при этом использование ресурсов МВС очень нерационально - максимум эффективности использования ресурсов обычно достигается при равномерном (или близком к равномерному) распределении операторов по ярусам.
Однако практически в любом ЯПФ имеется вариативность в расположении вершин графа
(операторов) между ярусами (перемещение операторов между ярусами ограничивается
соблюдением информационных зависимостей операторов в графе; для ЯПФ графа на рис.1 оператор
14 может быть перемещен "вниз" на любой ярус с 2 по 5-й, оператор 2 - на любой ярус с 2 по
4й, оператор 1 - на ярус 2); возможный диапазон перемещений показан на рис.1 пунктиром. Эта
особенность ЯПФ дает возможность оптимизации ЯПФ (в смысле, напр., достижения
наибольшей равномерности распределения операторов по ярусам – при этом автоматически достигается
максимум использования ресурсов МВС). Для ИГА большого размера трудоемкость такой
оптимизации запредельно велика (задача перестановок с учетом влияния изменения конфигурации
ЯПФ после каждой), существующие алгоритмы разбиения графов являются эвристическими
(напр., KL-алгоритм [
Итак, имеем две (обязательно последовательно выполняемые) задачи: a) Выявление в заданном алгоритме собственно наличие параллелизма (для выполнения этого как нельзя лучше подходит метод представления ИГА в ярусно-параллельной форме). б) Планирование параллельного выполнения алгоритма с учетом реалий (ограничений) конкретОграничения МВС - число параллельно работающих вычислителей, объемы их памяти и др., выполнение программы с учетом этого достигается эквивалентными (не изменяющими информационных зависимостей в графе) преобразованиями ИГА в ЯПФ.
Основные параметры ЯПФ графа (применяются также и иные): • - высота ЯПФ графа, определяется количеством ярусов • – ширина i-того яруса (количество операторов на нем) • – ширина ЯПФ графа, определяется максимумом операторов по всем ярусам графа; = нации):
• ̅ – средняя ширина ЯПФ; ̅ = 1 ∑ ==1 , - число ярусов ЯПФ • = ⁄ ̅ – степень (коэффициент) заполнения i-того яруса ЯПФ графа
– минимальное количество (параллельно работающих) вычислителей, необходимое для реализации вычислений согласно данного графа; = ( ) ЯПФ графа; = ( )⁄
( ) - степень (коэффициент) неравномерности распределения операторов по ярусам • = √1 ∑ ==1 ( − ̅)2 - среднеквадратичное отклонение ширин ярусов ЯПФ Основные постановки оптимизационной задачи (не только возможны, но и полезны комбивысот у ЯПФ данного ациклического графа). a) Наиболее полная загрузка неизвестного заранее числа параллельно работающих вычислительных узлов имеющейся МВС при минимальном времени выполнения задачи: → 1,0 при = 0 = (где 0 - длина критического пути - минимальная из всех возможных б) Наиболее полное использование ресурсов (вычислительных узлов) имеющейся МВС при допущении увеличения времени выполнения: ( ) ≤ 0 при ≥ 0 (здесь 0 - число доступных параллельно работающих вычислителей в заданной МВС); однако желательно − 0 → (минимизация времени выполнения). Может быть полезно представить этот процесс как подготовку состоящей из не более чем заданного числа M0 заведомо независимых (ортогональных) по данным команд для вычислительной системы архитектуры VLIW (Very Long Instruction Word) в иделогеме EPIC (Explicitly Parallel Instruction Computing - микропроцессорная архитектура с явным параллелизмом команд).
По данным [
Одной из тенденций современного программирования является использование встраиваемых скриптовых языков (ВСЯ) для расширения возможностей программных комплексов в области сложной обработки данных. Историю собственно скриптовых языков можно проследить с 60-х годов (языки пакетной обработки и языки командных оболочек, используемые чаще всего в пакетном режиме обработки), однако большую часть прошедшего времени применение их ограничивалось системными проектами (уровень операционных систем), только в последнее время проявляется тенденция использования ВСЯ в программном обеспечении меньшего масштаба.
Встраиваемые скриптовые языки вследствие присущей гибкости описания алгоритмов дают богатые возможности сложного преобразования данных, недостижимые традиционными методами (напр., привычными системами организации интерфейса с пользователем - меню, кнопками и др.). В случае ВСЯ разработчик (иногда и квалифицированный пользователь) описывает (обычно при этом вызовы ВСЯ становятся "оберткой" функций API "родительского" приложения, при этом ВСЯ фактически становится предметно-ориентированным языком программирования) необходимые действия на ВСЯ, в дальнейшем "родительское" приложение использует это описание для совершения заданных действий. Успехи в разработке ВСЯ позволили существенно уменьшить размер их кода (часто такие языки поставляются в виде исходных текстов в режиме Open Source), в этом случае при встраивании размер "родительского" приложения возрастает незначительно. В настоящее время известны встраиваемые системы на основе Basic-подобного языка (семейство программ 1С), Java (JavaScript, JScript), Python, Ruby, Tcl, PHP, Perl, REBOL, NewLISP и др.
Недостатками скриптовых языков являются повышенное время исполнения вследствие интепретируемости (идеологема применения этих ВСЯ в качестве "оберток" над вызовами быстрых компилируемых языков эту проблемы практически снимает), отсутствие удобной интегрированной среды разработки (IDE) и маркетингового бюджета.
Интересным ВСЯ является Lua, разрабатываемый с 1993 г. в католическом университете
Рио-де-Жанейро [
Встроенный скриптовый язык Lua использован при разработке описываемой в данной работе программной системы выявления скрытого параллелизма и составления расписания выполнения параллельных частей программы. Данная программная система написана на языке программирования С++ и является 32-битным приложением Windows (рис. 2); в связи с предполагаемым большим числом вычислений предполагается интегрирование ее в инфраструктуру BOINC (Berkeley Open Infrastructure for Network Computing) и расположение на сервере ВУЗ'а. Рис. 2. Главное окно программного модуля выявления скрытого параллелизма и составления расписания выполнения параллельных частей программы Программный инструментарий (фактически API пользователя) разработанной системы позволяет реализовывать любой из перечисленных критериев оптимизации (а также их комбинации), т.к. выбор критерия осуществляет собственно пользователь (на основе задач, им поставленных). К родственным по тематике с данным проектам можно отнести V-Ray и ПАРУС (оба разработки МГУ им. М.В.Ломоносова, Россия); известны также системы METIS и ParMETIS (университет Миннесоты, 1998-2003), функционал которых для данного случая явно избыточен.
Инструментарий системы включает три типа API-вызовов (всего около 30 штук, причем каждый является Lua-"оберткой", соответствующей С-функции): Информационные (служат для получения информации о ИГА и его ЯПФ; именно на основании этих данных принимается решение о применимости одной из стратегий преобразования ЯПФ графа, реализуемой в дальнейшем на языке Lua). Акционные (служат для эквивалентных, т.е. не меняющих информационные связи в ИГА, преобразований ЯПФ). Вспомогательные (работа с файловой системой и т.п.).
Примерами информационных вызовов являются - получить общее число ярусов ЯПФ, число операторов на заданном ярусе, получить диапазон ярусов для возможного нахождения на них заданного оператора и др., акционных – переместить заданный оператор на конкретный ярус ЯПФ (с учетом ненарушения информационных зависимостей), создать новый пустой ярус, уничтожить пустой ярус и др. В процессе выполнения акционных функций собственно ИГА не изменяется (т.е. программа остается той же самой) - меняется лишь представление графа (в данном случае - его ЯПФ).
Исходный (и преобразуемый в дальнейшем) информационный граф алгоритма может быть получен следующими методами: 1) Построен вручную согласно текстовому описанию алгоритма или же представлению его на псевдоязыке или в виде блок-схемы (для вновь разрабатываемых алгоритмов). 2) Путем анализа исходного текста программы на одном из традиционных языков программирования (подобные анализаторы существуют, однако зачастую выдают противоречивые результаты). agora.guru.ru/pavt 3) балансировки ярусно-параллельной формы информационного графа алгоритма; здесь под балансировкой понимается равномерность распределения операторов по ярусам ЯПФ. Задача имеет прямое отношение к проблеме эффективного распараллеливания алгоритмов и, в частности, к вопросу наиболее эффективного использования ресурсов МВС. На первой стадии из всех реалий конкретной МВС учитывается только число параллельных вычислителей, но в перспективе стоят планы учета дополнительных параметров.
В качестве параметра эффективности каждого предложенного решения использовалось число перестановок операторов с яруса на ярус ЯПФ для получения заданного результата. 4. Результаты и их обсуждение
Эффективность обработки данных иллюстрирована табл. 1 (описанная на Lua стратегия балансировки ширин ярусов ИГА без увеличения высоты ЯПФ) и табл. 2,3 (стратегия снижения ширины ЯПФ к заданной величине совместно с балансировкой) для нескольких ИГА различной сложности.
Преобразования ЯПФ выполнены для различных алгоритмов, заданных информационными графами. Информационные графы slau_2a, slau_3a, slau_5a и slau_10а - решение СЛАУ порядков 2,3,4,5,10 соответственно классическим методом Гаусса, mnk_10 и mnk_20 – линейная аппроксимация по методу наименьших квадратов для 10 и 20 точек, korr_10 и korr_20 – определение коэффициента парной корреляции для 10 и 20 точек, m_matr_5 и m_matr_10 – умножение квадратных матриц порядков 5 и 10 классическим методом.
Стратегия преобразования ЯПФ, с помощью которой получены приведенные в табл. 1 результаты, названа (условно) “Бульдозер” и основана на перемещении операторов с наиболее нагруженных ярусов на недогруженные (так нож бульдозера срезает холмы и сдвигает их материал во впадины); критерий остановки алгоритма – перебор всех операторов, могущих быть перенесенными “с холмов во впадины” с целью балансировки ЯПФ. Табл. 2 и 3 – результат применения стратегии “Бисекция” – наиболее нагруженные ярусы разгружаются путем перенесения половины находящихся на них операторов на вновь образованные ярусы, созданные под данным ярусом; критерий останова – “ужатие” ЯПФ до ширины, не превышающей заданной.
Качество достигнутых преобразований ЯПФ в табл. 1-3 характеризуется безразмерными показателями =
и = нии данной стратегии снизилась величина СКО распределения числа операторов по ярусам, второй - то же по коэффициенту нерегулярности (original и reformed - показатели до и после преобразования ЯПФ); трудоемкость преобразования - числом перестановок операторов с яруса на ярус.
Как видно из данных табл. 1-3, описанные (не являющимися излишне изощренными) стратегии в самом деле позволяют достичь требуемого результата (наблюдается снижение неравномерности ширин ЯПФ по ярусам), однако с совершенно разной эффективность для различных ИГА. В целом наблюдается повышение эффективности стратегии при увеличении сложности (вариативности) ИГА. Особенна интересна и практически важна задача априорного (до проведения собственно преобразований ЯПФ) предсказания уровня их эффективности (задача распознавания). Большего эффекта можно добиться путем совершенствования стратегий и разумного их совместного применения.
, где первый показывает, во сколько раз при применеagora.guru.ru/pavt Таблица 1. Эффективность применения стратегии балансировки ширины ЯПФ
ИГА при неизменной высоте ЯПФ средняя ширина ЯПФ показатель показатель
число перестановок операторов 1,00 1,00 1,80 8,10 2,99 3,72 3,28 6,16 43,3 230/115/25 1610/805/63 252/126/26 174/88/15 334/168/25
450/225/5 3800/1300/10 1,00 2,11 3,99 18,9 3,74 6,37 5,96 10,8 80,0 540 5. Выводы
Предложена программная система (инструментарий) для анализа информационной структуры программ по их представлению в виде информационного графа, позволяющая не только выявлять скрытый параллелизм, но и разрабатывать рациональные расписания выполнения частей параллельных программ с учетом параметров реальных многопроцессорных систем. Исключительно применение встроенного скриптового языка Lua для реализации стратегий целенаправленного изменения ярусно-параллельной формы графового представления позволило добиться гибкости и эффективности в реализации поставленной цели; это было бы немыслимо иными методами.
На примерах показана действенность данного подхода для решения поставленных задач. Результаты исследований могут быть использованы как для теоретического анализа алгоритмов, так и в практике при разработке эффективных распараллеливающих компиляторов. Опыт показывает эффективность применения данной разработки при усвоении основ параллелизации студентами ВУЗ'ов, при этом естественным образом реализуются разработки исследовательского направления. Литература
608 c. 1,00 2,00 4,00 18,0 4,40 8,40 6,40 12,4 3,76 7,52
число перестановок операторов 1234 0 6 70 27 67 51 124 451 6152 Software analysis tools information structure algorithms by their information graphs
National Research University "Higher School of Economics" The realization of software tools for developing effective strategies to transform ideas information graphs algorithms for the purpose of identifying how parallelism, and the definition of management plan (schedule) of parallel parts of the program taking into account the limitations of the real multiprocessor systems. To achieve flexibility in the development of scenarios graph representations of transformations using embedded scripting language Lua.
Keywords: information graph algorithm, the thin structure of the program information, hidden parallelism, parallel-stacked form of the information graph, convert the graph representation of the information, built-in scripting language Lua programming, rational strategy of building plan of the parallel program.