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

Российская Академия Наук Сибирское Отделение Институт систем информатики им. А. П. Е",,,Г1ПЯ

004603305 На правах руУош^си"

УДК 004.432.42

Идрисов Ренат Искандерович

МЕЖПРОЦЕДУРНЫЙ АНАЛИЗ И РАСПАРАЛЛЕЛИВАНИЕ ПОТОКОВЫХ ПРОГРАММ НА БАЗЕ ГРАФА ИСПОЛНЕНИЙ ВЫЗОВОВ

05.13.11 — математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

1 о ИЮН 2010

Новосибирск - 2010

004603805

Работа выполнена в Учреждении Российской академии наук Институте систем информатики им. А.П. Ершова СО РАН

Научные руководители: Евстигнеев Владимир Анатольевич

Официальные оппоненты: Легалов Александр Иванович

доктор технических наук, профессор

Ведущая организация: Южный Федеральный Университет

(г. Ростов-на-Дону)

Защита состоится 16 июня 2010 года в 15 часов 30 минут на заседании диссертационного совета ДМ003.032.01 при Институте систем информатики им. А.П. Ершова Сибирского отделения РАН по адресу: 630090, г. Новосибирск, пр. Акад. Лаврентьева, 6.

С диссертацией можно ознакомиться в читальном зале ИСИ СО РАН (г.Новосибирск, пр.Акад.Лаврентьева, 6).

Автореферат разослан _ "? 2010 г.

Ученый секретарь Диссертационного совета,

доктор физико-математических наук, профессор

Касьянов Виктор Николаевич доктор физико-математических наук, профессор

Скопин Игорь Николаевич

кандидат физико-математических наук,

доцент

к.ф.-м.н

Мурзин Ф.А.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность проблемы

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

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

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

Оптимизации и работа компилятора вообще заключается в преобразовании внутреннего представления. Внутренние представления варьируются от приближенных к языкам высокого уровня до приближенных к уровню машинного кода. Параллелизм наиболее универсально описывается при помощи представлений, основанных на потоке данных. В таких представлениях не требуется тратить дополнительные усилия для анализа зависимостей. Примером могут служить многочисленные проекты, развивающие SSA форму. Одним из таких представлений является IR2, рассматриваемое в данной работе. К такому представлению может быть приведён даже императивный язык. Известны проекты, где Fortran транслируется в JF1, представление с аналогичной структурой, но другим набором вершин.

з

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

Все перечисленные причины делают анализ и оптимизацию потоковых структур актуальными.

Цель работы — адаптация известных оптимизаций и распараллеливания для потоковой модели вычислений. Разработка новых алгоритмов анализа и оптимизации.

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

Научная новизна.

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

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

3. Впервые исследованы параллельные свойства и преобразования потоковых программ в рамках иерархического графового представления 1Я2.

Практическая ценность.

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

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

Разработанные методы реализованы в рамках компилятора Sisal 3.2. Компилятор Sisal 3.2 является частью системы SFP, разрабатываемой в рамках проекта ПРОГРЕСС. Компилятор будет использоваться другими разработчиками системы, которая ориентирована на решение математических задач на суперкомпьютерах и обучение функциональному программированию.

Апробация работы. Основные положения диссертации обсуждались на следующих конференциях и семинарах:

1.Семинар «Конструирование и оптимизация программ», Новосибирск, ИСИ СО РАН, 2004-2008 г.;

2.конференция-конкурс «Технологии Microsoft в информатике и программировании», Новосибирск, 2008 год.

3.XLIV Международная научная студенческая конференция «Студент и научно-технический прогресс», Новосибирск, 2006 г.

4.Четвертая азиатская международная школа-семинар «Проблемы оптимизации сложных систем» / ИВМиМГ 2008

5.Решетнёвские чтения / Красноярск 2009

Публикации. Результаты работы опубликованы в 9 печатных работах, из которых 4 полных статьи и 5 тезисов конференций.

Структура и объем работы

Диссертационная работа состоит из введения, трёх глав, заключения, списка литературы и двух приложений. Объем диссертации - 127 стр. Список литературы содержит 80 наименований. Работа включает 26 рисунков и графиков, полученных в результате расчетов на ЭВМ.

СОДЕРЖАНИЕ РАБОТЫ

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

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

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

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

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

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

Для более точного анализа следует рассматривать компоненты массивов отдельно. В работе рассмотрены точные и неточные алгоритмы описания областей массивов: Регулярные секции (Regular Sections), Дескрипторы доступа к данным (Data Access Descriptors), Регионы (Regions), Образы (Atom Images), Линеаризация (Linearization), Омега-тест.

Анализ контекста использования направлен на уточнение оптимизаций путём анализа различных вариантов использования процедуры. Информация о совмещениях, диапазоны изменения

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

Язык Sisal является базовым языком для данной работы. Аббревиатура SISAL образована от выражения: Streams and Iteration in a Single Assignment Language. Что буквально означает: «Язык однократного присваивания с потоками и итерациями». Для функциональных языков наличие циклических конструкций не характерно, более характерным является использование рекурсии. Наличие в Sisal циклических конструкций связано с ориентацией на научные вычисления.

Ориентация на научные вычисления и наличие неявного параллелизма делают Sisal потенциально привлекательным для решения вычислительных задач. Sisal является входным языком системы поддержки параллельного программирования SFP. Основные оптимизации и распараллеливание производится на уровне back-end транслятора в рамках представления IR2.

Внутреннее представление IR1, используемое в компиляторе языка Sisal, состоит из множества ориентированных безконтурных графов, соответствующих функциям исходной программы. Граф 1R1 G — (N, Р, Е, РР°"'), где N - множество вершин, Р — множество портов, Е с РхР — множество дуг, Р" с Р — множество входных портов графа G, Р°и' с Р — множество выходных портов графа G. Каждой вершине Nt е N соответствуют два подмножества портов из Р: входные порты Р/" с Р и выходные порты РГ с Р. Дуга Ei=(Pi, Р2) е Е, если для некоторых i и j Р1 е Р""' и Р2 ePj" и Г"' или Р, е Pin и Р2 ePj" иР°ш.

Внутреннее представление IR2 также является потоковым представлением программы. Граф IR2 изоморфен графу IR1, но в IR2 дугам сопоставляются переменные, а между вершинами возникает нестрогое отношение порядка. Основные оптимизационные и распараллеливающие преобразования производятся на уровне этого представления. Более формально: граф IR2 для функции языка Sisal - это объект (G, VAR, <J„ <д), где G — граф IR1, VAR — множество переменных, <ги — отображение Е —> VAR,

задающее привязку переменных к дугам графа в, <р - порядок на Ых^ задающий последовательность исполнения.

Внутреннее представление 1Ю является классическим императивным представлением программы в виде косвенных троек1.

Во второй главе приведены теоретические результаты данной диссертационной работы. Внутренние представления Ш1 и ГО2 рассмотрены более подробно. Введены понятия непосредственной вложенности, достижимости вершин в ГО2, исполнения вызова и графа исполнений вызовов. Сформулированы алгоритмы преобразования и анализа программ, записанных в виде внутреннего представления Ж2.

Определение З2. Составными вершинами графа Ж1 будем называть вершины, которым соответствует некоторый фрагмент иерархии графа. Этот фрагмент в совокупности с типом вершины описывает производимые вычисления. Простые вершины описывают функции, неделимые с точки зрения внутреннего представления. Примерами простых вершин могут служить вершины типа «сложить», «умножить». Примерами составных вершин для ГО1 являются вершины типа «цикл», «оператор выбора».

Определение 4. Будем называть вершины д, и д2 непосредственно соединёнными, если 3 е=(р1, р2) е Е,гдв а р2еРп(ц£ или

Определение 5. Для любой составной вершины п непосредственно вложенными будем называть такие вершины q, для которых Зе=(рь рт) е Е, р1еРри'(п), р2еРри'(д) или 3 Щи ... Цк такие, что Зе1=(рь р2) е Е, р1еР°"'(п), р2еРри'(д,), а пары вершин (ць Цг), (ц2, Щз),... (Цкь Як), (Яь я)~ непосредственно соединены.

Для анализа значений на графе ГО2 описаны алгоритмы протягивания значений, протягивания мультизначений, протягивания диапазонов и протягивания мультидиапазонов. Для каждого из алгоритмов доказаны временные характеристики (Теоремы 9, 10, 11 и 12), свойства детермини-

1 В. А. Серебряков Лекции по конструированию компиляторов // ВЦ РАН — Москва, 1994 — 174 с.

2 Номера определений и теорем соответствуют номерам в тексте работы.

рованности (Теорема 7), эквивалентности исходной программы относительно подстановки найденных значений (Теорема 8).

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

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

Результатом вычисления в языке Sisal может являться «ошибка», это не приводит к завершению вычисления без получения остальных результатов. Таким образом, язык Sisal реализует модель всюду завершаемых частичных вычислений. Алгоритмы анализа значений переменных позволяют существенно оптимизировать работу с такими значениями.

В главе также рассмотрены алгоритмы оптимизации циклических конструкций, удаления «мёртвого» кода и выноса инвариантных значений, которые основываются на данных, полученных в результате анализа. Доказаны временные характеристики алгоритмов (Теоремы 15 и 17).

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

Определение 18. Будем называть функцию F' «исполнением» функции F, если F' получается из F при конкретизации её входных параметров, в соответствии с данными, которые выявляются на стадии статического анализа. А так же если функция F' тождественна F.

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

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

Свойство 1. Граф вызовов является вырожденным случаем графа исполнений вызовов, в котором каждый фрагмент иерархии графа состоит из единственной вершины.

Свойство 2. Одной исходной программе могут соответствовать несколько графов исполнений вызовов.

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

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

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

ю

темы SFP. Доказываются завершимость (Теоремы 19 и 23) и свойства детерминизма (Теоремы 20, 21 и 22) алгоритмов межпроцедурного анализа.

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

Третья глава посвящена экспериментальным результатам работы Sisal — программ. На данный момент компилятор Sisal, описанный в этой работе существует в виде Source-to-Source транслятора из Sisal 3.2 в С#. В дальнейшем планируется трансляция в язык IL внутреннего представления платформы .NET. Вместе с компилятором предоставляются средства для поддержки системы типов языка Sisal в С# и средства для организации ввода-вывода. Данные в программу поступают из xml-файла с параметрами. Аналогичным образом сохраняются результаты работы программы.

В рамках данной работы был доработан Back-End транслятор системы SFP языка Sisal. Объём исходного кода Back-End транслятора составлял 575кб, в результате изменений, отражённых в данной работе размер кода увеличился до 882кб. Библиотека поддержки во время исполнения программы (Run-Time Library) составляла 14кб исходного кода С# и была увеличена до 50кб.

Трансляцию Sisal-программы можно разбить на следующие части:

1. Трансляция из исходного текста в представление IR1

Эта часть называется Front-End транслятором, на этой стадии производится лексический и семантический анализ текста. Эта стадия была полностью оставлена без изменений и не относится к результатам данной диссертационной работы

2. Трансляция из внутреннего представления IR1 в представление FR2

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

и

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

3. Трансляция из IR2 в граф исполнений вызовов

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

4. Межпроцедурный анализ и оптимизации

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

5. Трансляция из графа исполнений вызовов в IR2

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

6. Распараллеливание

Распараллеливание также изначально отсутствовало в компиляторе Sisal и является полностью результатом работы автора. Сейчас распараллеливание ориентировано на платформу SMP и тяжеловесные нити. Компилятор выбирает наиболее крупные участки кода, которые можно исполнить параллельно на заданном количестве вычислителей.

7. Трансляция из IR2 в IR3

Эта стадия была доработана не только с целью добавления новых типов и языковых конструкций, которые были отмечены на шаге 2, но и специальных конструкций, необходимых для распараллеливания и оптимизаций значений ошибочности. Были добавлены такие конструкции как ThreadFork, ThreadJoin, введено само понятие функции-нити, которая исполняется параллельно с другими функциями-нитями. Конструкция Un Warp для получения значения, содержащего свойство ошибочности из переменной, которая изначально его не содержала.

8. Оптимизации IR3

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

существующие оптимизации удаления лишних присваиваний в виду добавления новых языковых конструкций. 9. Трансляция в С#

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

Приведены тесты компилятора на некоторых вычислительных задачах, одна из которых называлась smooth (рис. 2, 3). Эта программа являлась фрагментом большой аэродинамической задачи от NASA, реализованной на Sisal 1.3 и транслированной в Sisal 3.2 для тестирования производительности. Задача генерирует и обрабатывает 3-мерные массивы заданного размера. Для проверки корректности работы программ, сгенерированных компилятором, выходные данные сохранялись в файл и сравнивались при помощи утилиты fc (file compare) с эталонной версией. Входные данные были получены при помощи генератора псевдослучайных чисел платформы .NET.

Рис. 2. Время выполнения smooth (по у, в секундах) в зависимости от размера обрабатываемых массивов. Здесь ромбом обозначается Sisal без оптимизаций, квадратом — Sisal без межпроцедурных оптимизаций, а

треугольником — Sisal с полным набором оптимизаций.

Поскольку, в Sisal каждое значение может иметь тип «ошибка» и за счёт того, что обычный компилятор С#, работая с такой системой типов, не использует оптимизаций проверки ошибочности значений — оптимизированный Sisal код оказывается эффективней. Тесты производились на ПК с процессором Intel Core 2 Duo 3.16GHz на одном ядре, поскольку требовалось сравнить последовательные реализации.

1200

0 i

0 20 40 60 80 100 120 140 160 ISO 200

Рис. 3. Расход в Мб для задачи smooth, обозначения трендов аналогичны предыдущему графику

Hand-coded Optimized Sisal

-p i_г_2_i_--a_i_a_ы-

Рис. 4. Распараллеливание программы перемножения матриц

Распараллеливающая система реализована для архитектуры SMP при помощи библиотек Threading платформы ".NET". Тесты производились на четырёхпроцессорной вычислительной машине (рис. 4). По оси X отложено количество вычислителей, заданное при компиляции Sisal-программы. После N=4 наблюдается плавный рост времени вычисления, поскольку возникают дополнительные расходы на поддержание большего числа параллельных нитей.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ

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

2. Механизм исследования параллельных свойств императивных программ при помощи временных развёрток обобщён на граф IR2. Доказаны временные характеристики алгоритмов оптимизации и их влияние на параллельные характеристики программы.

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

4. Впервые предложен и реализован анализ значений элементов п-мерных массивов для модели всюду завершаемых частичных вычислений.

5. Компилятор системы SFP дополнен более развитой средой поддержки времени исполнения (RTL), конструкциями, обеспечивающими распараллеливание для платформы SMP, возможностью ввода и вывода данных посредством XML.

6. Компилятор проверен на реальных вычислительных задачах, которые показали эффективность внедрённых преобразований. Результаты вычислений сверены с неоптимизированной версией.

Все выносимые на защиту результаты принадлежат автору лично. ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Стасенко А.П. Пыжов К. Идрисов Р.И. Компилятор в системе функционального программирования SFP. // Вестник НГУ. Серия: информационные технологии. Т.1. Вып.2. Новосибирск: 2008. Стр. 73-90.

2. Идрисов Р. И. Временная развёртка внутреннего представления IR2 языка Sisal 3.1 // Методы и инструменты конструирования программ / РАН, Сиб. Отд-е, Ин-т систем информатики. - Новосибирск, 2007.-С. 31-37.

3. Идрисов Р. И. Методы межпроцедурного анализа // Методы и инструменты конструирования программ / РАН, Сиб. Отд-е, Ин-т систем информатики. - Новосибирск, 2007. - С. 38 - 55.

4. Идрисов Р. И. Межпроцедурный анализ в автоматических распараллеливающих системах // XLIV Междунар. науч. студенческая конф. «Студент и научно-технический прогресс»: Информационные технологии / НГУ — Новосибирск, 2006 — С. 10-11.

5. Идрисов Р. И. Russian supercomputer software // Развитие вычислительной техники в России и странах бывшего СССР: история и перспективы / Материалы международной конференции в двух частях.

Часть 2 / Петрозаводский Государственный Университет, 2006 — С. 33.

6. Идрисов Р. И. Протягивание констант в графе IR2 внутреннего представления языка SISAL // Конструирование и оптимизация параллельных программ / РАН Сиб. Отд-е, Ин-т систем информатики. - Новосибирск 2008. - С. 83-95.

7. Идрисов Р. И., Пыжов К. А. Распараллеливание и оптимизация на уровне внутреннего представления в компиляторе Sisal 3.1 // Технологии Microsoft в теории и практике программирования / Новосибирск 2008 - С. 128 - 129.

8. Идрисов Р. И., Пыжов К.А. Настоящее и будущее функциональных языков программирования на примере языков Sisal и F#. // Четвертая азиатская международная школа-семинар «Проблемы оптимизации сложных систем» / Труды ИВМиМГ СО РАН Выпуск 8, 2007, Серия: Информатика - С. 194-201.

9. Идрисов Р. И. Межпроцедурные оптимизации «ошибочности» значений для функционального языка, ориентированного на научные вычисления // Материалы Х1П Международной научной конференции, посвященной 50-летию Сибирского государственного университета имени академика М. Ф. Решетнёва/ Часть 2 — Красноярск 2009 - С. 425-426

Идрисов Р.И.

МЕЖПРОЦЕДУРНЫЙ АНАЛИЗ И РАСПАРАЛЛЕЛИВАНИЕ ПОТОКОВЫХ ПРОГРАММ НА БАЗЕ ГРАФА ИСПОЛНЕНИЙ ВЫЗОВОВ

Автореферат

Подписано в печать 06.05.2010 Объем 1,1 уч.-изд. л.

Формат бумаги 60 х 90 1/16_Тираж 100 экз.

Отпечатано в ЗАО РИЦ «Прайс-курьер»

630090, г. Новосибирск, пр. Ак. Лаврентьева, 6, тел. 330-72-02

Заказ №233

Введение.

1. Обзор методов межпроцедурного анализа и внутренних представлений целевого языка.

1.1 Анализ совмещений.

1.2 Анализ значений.

1.3 Анализ использования переменных.

1.3.1 Неточные алгоритмы описания областей массивов.

1.3.1.1 Регулярные секции (Regular Sections).

1.3.1.2 Дескрипторы доступа к данным (Data Access Descriptors).

1.3.1.3 Регионы (Regions).

1.3.2 Точные алгоритмы описания областей массивов.

1.3.2.1 Образы (Atom Images).

1.3.2.2 Линеаризация (Linearization).

1.3.2.3 Омега-тест.

1.3.3 Комбинированные методы.;.

1.4 Анализ контекста использования процедуры.

1.5 Язык SISAL.

1.5.1 Система SFP.

1.5.2 Внутреннее представление IR1.

1.5.3 Внутреннее представление IR2.

1.5.4 Внутреннее представление IR3.

Выводы по первой главе.

2. Практическая реализация анализа и оптимизаций.

2.1 Свойства внутренних представлений.

2.2 Хранение контекстных условий.

2.3 Алгоритмы анализа.

2.3.1 Протягивание одиночных значений.

2.3.2 Протягивание мультизначений.

2.3.3 Протягивание диапазонов.

2.3.4 Протягивание мультидиапазонов.

2.3.5 Протягивание другой информации о значениях.

2.3.6 Анализ массивов.

2.3.7 Реализация алгоритмов анализа значений.

2.4 Алгоритмы оптимизации.

2.4.1 Удаление избыточного кода.

2.4.3 Вынос инвариантных вычислений.

2.4.4 Оптимизация циклических конструкций.

2.4.5 Оптимизация копирования.

2.5 Межпроцедурный анализ.

2.5.1 Граф исполнений вызовов.

2.5.3 Алгоритмы анализа.

2.6. Алгоритмы распараллеливания.

2.6.1 Построение развёртки.

2.6.2 Влияние оптимизирующих алгоритмов.

2.6.3 Макропараллелизм циклов SISAL.

Выводы по второй главе.

3. Тестирование анализа и оптимизаций.

3.1 Структура разработанного транслятора.

3.2 Ввод и вывод данных.

3.3 Вычислительные задачи.

Выводы по третьей главе.

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

Межпроцедурный анализ относится в первую очередь к анализу потока данных, который поступает при вызове в процедуру и из неё. В рамках данной работы под межпроцедурным анализом будем понимать анализ влияния вызова процедуры на контекст вызова [5] и определение влияния контекста вызова на исполнение вызываемой процедуры [11]. Возникновение и развитие такого вида анализа непосредственно связано с развитием потокового анализа, началом которого можно считать создание системы автоматизации программирования АЛЬФА [38, 39]. В трансляторе АЛЬФА процедурные вызовы анализировались отдельно, производилась подстановка висячих процедур, частично анализировались совмещения параметров и присутствовал анализ записываемых переменных. С момента создания системы АЛЬФА, анализ процедурных вызовов стал неотъемлемой частью оптимизирующего транслятора. Об этом свидетельствуют дальнейшие публикации по оптимизирующим трансляторам [78]. Приблизительно в начале 80-х годов межпроцедурный анализ был выделен в качестве отдельного вида анализа [76, 77]. Область применения такого анализа не ограничивается оптимизирующими компиляторами, он также используется для контролирования свойств программ в средах разработки [48].

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

Оптимизации и работа компилятора вообще заключается в преобразовании внутреннего представления. Внутренние представления варьируются от приближенных к языкам высокого уровня до приближенных к уровню машинного кода. Параллелизм наиболее универсально описывается при помощи представлений, основанных на потоке данных. В таких представлениях не требуется тратить дополнительные усилия для анализа зависимостей. Примером могут служить многочисленные проекты, развивающие SSA форму. Одним из таких представлений является IR2, рассматриваемое в данной работе. К такому представлению может быть приведён даже императивный язык. Известны проекты, где Fortran транслируется в IF1, представление с аналогичной структурой, но другим набором вершин.

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

Все перечисленные причины делают анализ и оптимизацию потоковых структур актуальными.

Цель работы — адаптация известных оптимизаций и распараллеливания для потоковой модели вычислений. Разработка новых алгоритмов анализа и оптимизации.

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

Научная новизна.

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

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

3. Впервые исследованы параллельные свойства и преобразования потоковых программ в рамках иерархического графового представления IR2.

Практическая ценность.

Практическая часть данной работы описывает реализацию межпроцедурного анализа и распараллеливания в рамках системы функционального программирования (SFP), разрабатываемой в Институте Систем Информатики им. А.П. Ершова (ИСИ СО РАН). Основные оптимизирующие преобразования в SFP производятся на уровне внутреннего потокового представления IR2, которое может быть использовано в качестве внутреннего представления императивного языка. Оно может описывать массивы и циклические конструкции, что не является обычным для внутреннего представления функционального языка программирования. 6

Разработанные методы реализованы в рамках компилятора Sisal 3.2. Компилятор Sisal 3.2 является частью системы SFP, разрабатываемой в рамках проекта ПРОГРЕСС. Компилятор будет использоваться другими разработчиками системы, которая ориентирована на решение математических задач на суперкомпьютерах и обучение функциональному программированию.

Апробация работы. Основные положения диссертации обсуждались на следующих конференциях и семинарах:

1. Семинар «Конструирование и оптимизация программ», Новосибирск, ИСИ СО РАН, 2004-2009 г.

2. Конференция-конкурс «Технологии Microsoft в информатике и программировании», Новосибирск, 2008 год.

3. XLIV Международная научная студенческая конференция «Студент и научно-технический прогресс», Новосибирск, 2006 г.

4. Четвертая азиатская международная школа-семинар «Проблемы оптимизации сложных систем» / ИВМиМГ 2008.

5. Решетнёвские чтения / Красноярск 2009.

Публикации. Результаты работы опубликованы в 9 печатных работах, из которых 4 полных статьи и 5 тезисов конференций.

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

Основные результаты диссертационной работы:

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

2. Механизм исследования параллельных свойств императивных программ при помощи временных развёрток обобщён на граф IR2. Доказаны временные характеристики алгоритмов оптимизации и их влияние на параллельные характеристики программы.

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

4. Впервые предложен и реализован анализ значений элементов п-мерных массивов для модели всюду завершаемых частичных вычислений.

5. Компилятор системы SFP дополнен более развитой средой поддержки времени исполнения (RTL), конструкциями, обеспечивающими распараллеливание для платформы SMP, возможностью ввода и вывода данных посредством XML.

6. Компилятор проверен на реальных вычислительных задачах, которые показали эффективность внедрённых преобразований. Результаты вычислений сверены с неоптимизированной версией.

Все выносимые на защиту результаты принадлежат автору лично.

Заключение

1. Steensgaard В. Points-to analysis in almost linear time. II In proceedings of POPL'96 / St. Petersburg Beach, Florida, January 1996. —P. 32-41.

2. Schouten D.A. An Overview of interprocedural analysis technologies for high performance parallelizing compilers — Illinois, May 1990 — 62 p. — (Tech. Rep. / Center for Supercomputing Research and Development / University of Illinois; No. 1005).

3. Евстигнеев В.А., Серебряков В.А. Методы межпрог{едурного анализа (обзор) II Программирование — 1992 — N3 — С. 4-15.

4. Касьянов B.H., Мирзуитова И.Л. SLICING: Срезы программ и их использование — Новосибирск 2002 — 116 с. — (Конструирование и оптимизация программ)

5. Hind М. et al. An Empirical Study of Precise Interprocedural Array Analysis / M. Hind, M. Burke, P. Carini, S. Midkiff // Scientific Programming — 1994 — Vol. 3, N 3 — P. 255-271

6. Callahan D., Kennedy K. Analysis of Interprocedural Side Effects in a Parallel Programming Environment. II Journal of Parallel and Distributed Computing—1988 —Vol. 5 —P. 517-550.

7. Антонов A.C. Современные методы межпроцедурного анализа программ!'/ Программирование — 1998 —N 5 — С. 3-14.

8. Triolet R., Irigoin F., Feautrier P. Direct Parallelization of Call Statements. // Proceedings of the SIGPLAN Symposium on Compiler Construction — SIGPLAN Notices, Vol. 21. 7, 1986 — P. 176-185.

9. Burke M., Cytron R. Interprocedural dependence analysis andpar allelization. I I In Proceedings of the SIGPLAN Symposium on Compiler Construction — SIGPLAN Notices, Vol. 26, 6, 1986 — P. 145-156.

10. Pugh W. The Omega Test: a fast and practical integer programming algorithm for dependence analysis —University of Maryland, 1991 — 10 p. — (ACM 0-89791-459-7/91/0004).

11. Tang P. Exact Side Effects for Interprocedural Dependence Analysis // Proceedings of the ACM International Conference on Supercomputing / Tokyo, Japan, July 1993 — P. 137-146

12. Стасенко А.П. Внутреннее представление системы функционального программирования Sisal 3.0. — Новосибирск, 2004. — 54 с. — (Препр. / РАН. Сиб. отд-е. ИСИ; № 110).

13. Воеводин В. В., Воеводин Вл. В. Параллельные вычисления. — СПб.: БХВ-Петербург, 2002. — 608 с.

14. Касьянов В. Н., Бирюкова Ю.В. Евстигнеев В.А. Функциональный язык SISAL 3.0II Поддержка супервычислений и Интернет-ориентированные технологии. — Новосибирск, 2001. — С. 54-67.

15. McGraw, J. R. et. al. Sisal: Streams and iterations in a single assignment language, Language Reference Manual Version 1.1 II Lawrence Livermore Nat. Lab. Manual M-146. — Livermore, CA 1983.

16. McGraw, J. R. et. al. Sisal: Streams and iterations in a single assignment language, Language Reference Manual Version 1.2 II Lawrence Livermore Nat. Lab. Manual M-146 (Rev.l). — Livermore, CA 1985.

17. Cann, D.C.; Feo, J. Т.; DeBoni, T.M. Sisal 1.2: High-performance applicative computing II Parallel and Distributed Processing, 1990. Proceedings of the Second IEEE Symposium / Volume , Issue ,9-13 Dec 1990 —P. 612-616

18. Sarkar, V.; Cann, D. POSC—a partitioning and optimizing SISAL compiler!I Proceedings of the 4th international conference on Supercomputing / Amsterdam, The Netherlands, 1990 — P. 148 164

19. Acherman W. В., Dennis J. В., Ackerman William B, VAL- oriented algorithmic language, preliminary reference manual II Massachusetts Institute of Technology, Cambridge, MA, 1979 — 80 p.

20. Bohm A. P. W. et. al. The SISAL 2.0 Reference Manual. I I Livermore, CA, 1991. — (Prepr. / Lawrence Livermore Nat. Lab.; UCRLMA-109098, LLNL).

21. Евстигнеев В. А., Городняя Л. В., Густокашина Ю. В. Язык функционального программирования SISAL II Интеллектуализация и качество программного обеспечения. — Новосибирск, 1994. — С. 21— 42.

22. Feo D. Т., Miller P. J., Skedzielewski S. К., Denton S. М. Sisal 90 User's Guide II Lawrence Livermore Nat. Lab. Draft 0.96. — Livermore, CA, 1995.

23. Бирюкова Ю. В. SISAL 90руководство пользователя. — Новосибирск, 2000. — 84с. — (Препр./ РАН. Сиб. Отд-е. ИСИ; № 72).

24. Стасенко А.П. Пыжов К. Идрисов Р.И. Компилятор в системе функционального программирования SFP. II Вестник НГУ. Серия:информационные технологии. Т.1. Вып.2. Новосибирск: 2008. Стр. 73— 90.

25. Kasyanov V. N. et. al, SFP — An interactive visual environment for supporting of functional programming and supercomputing IIWSEAS Transactions on Computers. — Athens: WSEAS Press, 2006. — Vol. 5, N 9. — P. 2063-2070.

26. Глуханков M. П. и др. Транслирующие компоненты системы функционального программирования SFP // Современные проблемы конструирования программ. — Новосибирск: Институт систем информатики имени А. П. Ершова СО РАН, 2002. — С. 69-87.

27. Стасенко А. П. Система интерфейсов транслятора во внутреннее представление IR1 // Методы и инструменты конструирования и оптимизации программ. — Новосибирск: Институт систем информатики имени А. П. Ершова СО РАН, 2005. — С. 229-238.

28. Skedzielewski S. К Glauert J. IF 1 An intermediate form for applicative languages. II Manual M-170 / Lawrence Livermore National Laboratory — Livermore, CA, 1985.

29. Густокашина Ю.В., Евстигнеев B.A. IF1 — промежуточное представление Sisal-программ II Проблемы конструирования эффективных и надежных программ. — Новосибирск, 1995. — С. 7078.

30. Welcome М. et. al. IF2 — An applicative language intermediate form with explicit memory management I I Lawrence Livermore Nat. Lab. Manual M-195. — Livermore, CA, 1986.

31. Kasyanov V. N., Stasenko A. P. Sisal 3.1 language structures decomposition И European Computing Conference. Book of Abstracts. — Athens: WSEAS Press, 2007. — P. 92.

32. Kasyanov V. N., Stasenko A. P. Sisal 3.2 language structures decomposition II Lecture Notes in Electrical Engineering. — Berlin: Springer-Verlag, 2009. — Vol. 28. — P. 582-594.

33. Пыжов К. А. Внутренние представления среднего уровня для компиляторов языка Sisal II Методы и инструменты конструирования программ / РАН, Сиб. Отд-е, Ин-т систем информатики. — Новосибирск, 2007. С. 174 - 185.

34. АЛЬФА-система автоматизации программирования / Под. ред. А.П. Ершова). —АН СССР. Сиб.отд-ние. — Новосибирск: Наука, 1967. — 308 с.

35. The Alpha automatic programming system / (Ed. by A.P.Ershov). — Acad. Press, London—New York, 1971. — 247 p.

36. D. A. Turner Miranda: A Non-Strict Functional Language with Polymorphic Types //Proceedings IFIP Conference on Functional Programming Languages and Computer Architecture — Nancy, France, September 1985, LNCS 201 — pp. 1-16.

37. Кряженков П.Б. Пользовательский интерфейс интегрированной среды функционального программирования SFP И Современные проблемы конструирования программ / РАН, Сиб. Отд-е, Ин-т систем информатики. — Новосибирск, 2002. — С. 182 198.

38. Keith D. С. et al. The Impact of Interprocedural Analysis and Optimization in the Rn Programming Environment II ACM Transactions on Programming Languages and Systems, Vol. 8 No. 4, October 1986, Pages 491-523

39. R.Wilson and M.Lam, Efficient context-sensitive pointer analysis for С programs II In Proceeding of the ACM SIGPLAN'95 Conference on Programing language Design and Implementation, June 1995, pp. 1-12.

40. Erik Ruf, Context-insensitive alias analysis reconsidered И Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation / La Jolla, California, United States, 1995, Pages: 13 22

41. Бульонков M. А., Кочетов Д. В. Визуализация свойств программ — Новосибирск, 1998. — 36 с. — (Препр. / РАН. Сиб. отд-е. ИСИ; № 51).

42. Jong-deok Choi et al. Efficient Flow-Sensitive Interprocedural Computation of Pointer-Induced Aliases and Side Effects II The Twentieth Annual ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages January 10-13, 1993 — Pages 232-245

43. Burke M., Carini P. Flow-Insensitive Interprocedural Alias Analysis in the Presence of Pointers I I Lecture Notes In Computer Science; Vol. 892 — 1994 —Pages: 234-250

44. Aho A. V., Ulman J. D. The theory ofparsing translation, and compiling I I Englewood, 1973 Vol. 2: Compiling — Cliffs N. J.: Prentice -Hall — 542 p.

45. Chase D. R. et al Analysis of pointers and structures II Chase D.R., Wegman M. Zadeck F. K. / Proc. of the ACM SIGPLAN'90 Conf. on Programming Language Design and Implementation SIGPLAN Not. -1990 - Vol. 25, N6 - P. 296-310

46. Landi W., Rider B. G. A safe approximate algorithm for interprocedural pointer aliasing II Proc. of the ACM SIGPLAN'92 Conf. on Programming Language Design and Implementation SIGPLAN Not. - 1992 - Vol. 27 -N7-P. 235-248

47. Брюханова И. В., Емельянов П. Г., Касьянов В. Н. Сабельфельд В.

48. К. Методы и средства семантического анализа Модула- программ . Оптимизация и конструирование программ 1993. С. 7- 23

49. Бульонков М. А. Кочетов Д. В. Грамматический подход к анализу синонимов II Программирование — 1996 — N3 — С. 36-46.

50. Шелехов В. И. Структура программы в языково-ориентированном потоковом анализе II Программирование — 1996 —N3 — С. 47-59.

51. Richardson S., Ganapathi М. Interprocedural Analysis Useless for Code Optimization И Stanford University. Tech. Rep. CSL-TR-87-342. November 1987-34 p.

52. Касьянов В. H. Трансформационные методы и средства конструирования эффективных программ II Кибернетика и системный анализ — Киев, 1993 — N2 — С 30-39.

53. Ершов А.П. Смешанные вычисления: потенциальные приложения и проблемы исследования. И Всесоюзная конференция "Методы математической логики в проблемах искусственного интеллекта и систематическое программирование", ч.2 — Вильнюс, 1980 — с. 26-55

54. Касьянов В.Н., Поттосин И.В. Методы построения трансляторов. — Новосибирск: Наука, 1986 — 344 С.

55. Carley A., Hall М. FIAT: A Framework for Interprocedural Analysis and Transformation II Lecture Notes in Computer Science — Volume 768 — 1994 —pp. 522-545.

56. Касьянов В. H. Методы оптимизации программ II НГУ — Новосибирск, 1984. — 92 с.

57. Касьянов В. Н. Применение графов в программировании II Поддержка супервычислений и интернет-ориентированные технологии — РАН, Сиб. Отд-е, Ин-т систем информатики — Новосибирск, 2001. — С 139167

58. Городняя JI. В., Касьянов В. Н. Проблемы и перспективы исследования преобразований программ на базе современныхтехнических средств II Проблемы конструирования эффективных и надежных программ. —Новосибирск, 1995. — С. 5—7.

59. Евстигнеев В. А., Касьянов В. Н. Сводимые графы и граф-модели в программировании II Новосибирск, 1999.— 288 с.

60. Котов В. Е. Формальные модели параллельных вычислений. — Новосибирск, 1979. — 56с. — (Препр./ СО АН СССР ВЦ; № 165).

61. Karp R. М., Miller R. Е. Parallel program Schemata I I Journal Computer Systems Science — v. 3,No. 2— 1969 — pp. 147-195.

62. Карп P. M., Миллер P. E. Параллельные схемы программ II Сборник «Кибернетический сборник», выпуск 13 (новая серия) —Москва: Мир — 1975—с. 5-61.

63. Нариньяни А. С. Теория параллельного программирования. Формальные модели. II «Кибернетика» — 1974 — № 3, с 1-16, №5, с. 114.

64. Котов В. Е., Нариньяни А. С. Асинхронные вычислительные процессы над памятью И «Кибернетика» — № 3, 1966 — с. 64-71.

65. Karp R. М., Miller R. Е. Properties of a Model for Parallel Computations: Determinacy, Terminations, Queueing. II ASIAM Journal of Applied Mathematics, v. 14 — Nov. 1966 —pp. 1390-1411.

66. Adams D. A. A computation Model with Data Flow Sequencing II CS-117, Computer Science Department — Stanford University — Stanford — .California, Dec. 1968

67. Rodriguez J. E. A Graph Model for Parallel Computations II Ph. D. Thesis, Massachusetts Institute of Technology, Dept. of Electrical Engineering — Cambridge — Massachusetts — Sept. 1967.

68. Kotov V. E. Concurrent Programming with Control Types II Constructing Quality Software, North-Holl. Publ. Co. — Amsterdam — 1978 — pp. 207208

69. Kotov V.E. An Algebra for parallelism Based on Petri Nets II Lecture Notes in Computer Science, v. 64, Springer-Verlag — Berlin — 1978 — pp. 39-55.

70. E. Myers. A precise inter-procedural data flow algorithm. II In Conference Record of the Eighth Annual Symposium on Principles of Programming Languages. ACM, January 1981.

71. M. Sharir, A. Pnueli. Two approaches to interprocedural data flow analysis. И In S. Muchnick and N.D. Jones, editors, / Program Flow Analysis: Theory and Applications. Prentice Hall Inc, 1981.

72. И. В. Поттосин, А. П. Ершов, В.В.Грушецкий, С.Б.Покровский. Методы декомпозиг}ии, синтеза и оптимизации в многоязыковой системе программирования. II Препр./ АН СССР, Сиб. отд-ние, ВЦ — Новосибирск, 1974. — 22 с.

73. В. А. Серебряков Лекции по конструированию компиляторов II ВЦ РАН — Москва, 1994 — 174 с.

74. Hind М. et al. Interprocedural Pointer Alias Analysis / M. Hind, M. Burke, P. Carini, J.-D. Choi // ACM Transactions on Programming Languages and Systems (TOPLAS) — 1999 — Vol. 21, Issue 4 (July 1999) — P. 848-894