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

УДК 004.4'416

На правах рукописи

005004196

Макошенко Денис Валентанович

АНАЛИТИЧЕСКОЕ ПРЕДСКАЗАНИЕ ВРЕМЕНИ ИСПОЛНЕНИЯ ПРОГРАММ И ОСНОВАННЫЕ НА НЕМ МЕТОДЫ ОПТИМИЗАЦИИ

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

АВТОРЕФЕРАТ

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

- 1 ДЕК 2011

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

005004196

Работа выполнена на кафедре алгебры и дискретной математики факультета математики, механики и компьютерных наук Южного федерального университета

Научный руководитель: Штейнберг Борис Яковлевич,

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

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

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

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

Ведущая организация: Ведущая организация: Институт точной

механики и вычислительной техники им. С.А. Лебедева РАН

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

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

Автореферат разослан ' < 6 ноября 2011г.

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

к.ф.-м.н. Мурзин Ф.А.

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

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

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

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

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

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

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

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

Широко используемые компиляторы, например, gcc, MSVS, Intel compiler, проводят комбинации преобразований, которые жестко подчиняются опциям, специфицированным в командной строке. Для некоторых конкретных оптимизируемых программ такие жестко зафиксированные комбинации преобразований могут привести к неоптимальному коду. Разработчики компиляторов зачастую выбирают некоторый пакет программ, на котором путем ручного подбора достигается хорошее взаимодействие преобразований.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Результаты диссертации внедрены в официальный курс лекций "Оптимизирующие компиляторы" и используются при обучении студентов кафедры микропроцессорных технологий факультета РТК Московского физико-технического института современным методам программирования и оптимизации для различных вычислительных архитектур.

6

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

1. Интеллектуальные и многопроцессорные системы ИМС-2003, Международная научно-техническая конференция, Дивноморское, Россия, 22-27 сентября 2003.

2. IEEE EAST-WEST DESIGN & TEST SYMPOSIUM 2009 MOSCOW, RUSSIA, September 18-21, 2009.

3. Современные проблемы фундаментальных и прикладных наук, 52-я научная конференция МФТИ, Долгопрудный, 27-28 ноября, 2009.

4. «Автоматическое распараллеливание программ», семинар кафедры алгебры и дискретной математики мехмата Южного федерального университета, 12 сентября 2005.

Публикации. Основные результаты диссертации опубликованы в семи работах, среди них четыре статьи, из которых две опубликованы в журналах из перечня ВАК [1], [2], одна в зарубежном журнале [3], одна в сборнике научных трудов [4], и три публикации в сборниках тезисов, докладов конференций [5], [6], [7].

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения и списка литературы. Объем диссертации - 122 стр. Список литературы содержит 109 наименований.

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

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

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

Пусть G - это граф потока управления (Control Flow Graph, CFG) процедуры P. Рассмотрим некоторый простой путь path в графе G и его

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

Обозначим через PDG(BB) подграф графа программных зависимостей (Program dependence graph, PDG), порожденный объединением множества вершин ВВ и вершин, из которых в вершины ВВ ведут дуги. Обозначим через weight(BB) сумму весов дуг критического пути в PDG(BB).

Пусть NumExec(BB) - это количество исполнений линейного участка во время исполнения программы. Тогда ЕТМ(ВВ) = max(resource(BB), •weight(BB)) * NumExec(BB) - это время вычисления ВВ.

Разобьем вершины G на множество линейных участков BBlocks(G). Тогда ЕТМ(Р) = 1ввеВВЮсща)ЕТМ(ВВ).

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

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

В данной главе предлагаются новые алгоритмы раскраски IG.

Рассмотрим граф G. Заметим, что если граф G полный, то его единственная возможная раскраска - каждая вершина - получает свой

собственный цвет. Если граф й не полный, то для его раскраски воспользуемся методом, предложенным Зыковым. Выберем две несмежные вершины и и V. Обозначим (<3;<и-у>) граф, в котором вершины и и V соединены ребром. Обозначим (й:<и=у>) граф, в котором вершины и и V стянуты в одну.

Рассмотрим множество М(О) всех раскрасок С. Множество М(С) представимо в виде объединения двух непересекающихся множеств:

М(О) = М((С;<и-у>)) иМ((С:<и=у>)) (1)

Пользуясь соотношением (1), построим дерево Тс перебора всех раскрасок О. Каждая вершина дерева - это некоторый граф йкорень дерева - граф С. Если О' - не полный граф, то у него есть два сына -1кг, причем, 1=(й ';<и-г=(С':<и=у>), где и и у некоторые вершины, не связанные ребром. Если й' - полный граф, то он является листом.

Теперь сопоставим каждой вершине I некоторое множество Х(1)сМ(й), корню дерева сопоставим множество М(й). Если у вершины I есть сыновья / и г, то им сопоставляются множества М(1) и М(г) соответственно.

Известно, что, используя раскраски графов, являющихся вершинами пути от листа к корню Тс, можно восстановить множество раскрасок графа О.

Пусть Тс' - некоторое поддерево дерева Тс всех вариантов раскраски, причем Тс' содержит корень Тс. Пусть величина ВиИф) - это количество левых сыновей на пути от корня дерева Тс' к вершине I. Пусть параметр О -это максимальное количество левых сыновей на любом пути от корня к листу в дереве Тс'. Обозначим через Тс(й) семейство всех возможных поддеревьев Тс' дерева таких, что для любой их вершины п выполняется ВиШ(п) < О.

Пусть Г(у) - это множество всех вершин смежных вершине V графа С.

Лемма I.1 Возьмем две произвольные вершины и и v графа G. Пусть выполняется Г(у)сГ(и) или Г(и)сГ(у). Тогда хроматическое число графа (G:<u=v>) не больше, чем хроматическое число графа G.

Рассмотрим перебор множества раскрасок IG G с помощью обхода поддеревьев из семейства T(LeftChilds). Рассмотрим текущую при данном обходе вершину t дерева Тс'eT(LeftChilds). У вершины t есть поддеревья, нуждающиеся в обходе, если она является не полным графом G". Будем всегда обходить правое поддерево вершины t. Затем выберем пару не соединенных ребром вершин и и v графа G'. Будем обходить левое поддерево t, если предикат ¡(u,v) = (Г(у) сГ(и) ==TRUE) v(r(u) сГ(\>) ==TRUE) ложен. Согласно лемме 1 истинность этого предиката означает, что обход левого поддерева излишен, поскольку хроматическое число графа левого сына не меньше хроматического числа графа правого сына.

Параметрический алгоритм перебора раскрасок G заключается в предложенном обходе дерева Тс'eT(LeftChilds).

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

Будем называть генератором виртуального регистра v такую инструкцию, которая присваивает значение v; использованием v такую инструкцию, потребляющую v в качестве операнда, что существует генератор v. Будем говорить, что инструкция inst потребляет значение v, присвоенное v генератором gen, если на пути в CFG между вершинами, соответствующими gen и inst, нет генераторов v.

Определим множество Access(v) следующим образом.

1 Номера лемм и теорем соответствуют номерам в тексте диссертации.

10

• Если вершина х в CFG является использованием v, то множество Access(v) содержит пару <x,use>. Символ use означает, что инструкция, соответствующая вершине х, рассматривается как использование.

• Если вершина х в CFG является генератором v, то множество Access (v) содержит пару <x,def>. Символ def означает, что инструкция, соответствующая вершине х, рассматривается как определение.

• Множество Access(v) не содержит никаких других пар.

Рассмотрим некоторое множество UcAccessfv). Будем говорить, что

использование х виртуального регистра v относительно U является использованием типа Common, если выполнены следующие условия.

• Пара <х, use> 0 U.

• Существует путь Р от некоторой вершины у eV(U) к использованию х.

• На пути Р нет генераторов v и других вершин zeV(U).

Пусть uses(U) - это все вершины типа Common относительно данного множества U. Путь в CFG является путем типа Common относительно множества U, если существует xeV(U), являющаяся началом этого пути к использованию типа Common. Обозначим через Starts(U) множество всех вершин, в которых начинается хотя бы один путь типа Common.

Частичный сброс виртуального регистра v - это пара <U,m>, где X -подмножество множества Access (v); m - некоторая ячейка памяти.

При проведении частичного сброса согласно <U,m> программа изменяется в четыре шага следующим образом.

1. Для каждой пары вида <х, def>, входящей в U, после вершины х вставляется инструкция, записывающая в ячейку памяти m значение виртуального регистра v, определенное этим генератором.

2. Ищется незанятый виртуальный регистр v '.

3. Для каждой пары вида <x,use> из Starts(U) перед вершиной х вставляется инструкция, считывающая значение из m в v'; в каждом использовании, принадлежащем множеству uses(U) iMtarts(U) каждый

потребляемый (определяемый остается без изменений) виртуальный регистр V заменяется на V'.

4. Рассматриваем все пары вида <х, ше>, входящие в II, такие, что первые элементы этих пар не входят в Ааг/з/ГУ/ Перед каждым таким использованием х вставляется инструкция, считывающая значение из т в V', а в использовании х потребляемый (определяемый остается без изменений) виртуальный регистр V заменяется на V'.

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

сброс V согласно паре <[/, т> приводит к эквивалентной процедуре.

Обозначим через Оеп(Ву) множество генераторов, определяющих виртуальный регистр V, потребляемый использованием В.

Приведем наиболее важные теоремы, доказанные в третьей главе.

Теорема 1. Пусть имеется процедура Р и ячейка памяти т. Рассмотрим некоторый виртуальный регистр V и некоторое множество Пусть для каждой пары <В, и$е> из множества С/ и для каждого генератора А из множества Сеп(В, у) выполняется хотя бы одно из двух условий:

• значение ячейки т совпадает со значением V после исполнения А;

• пара <А, с1е/> входит во множество (У.

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

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

Время жизни виртуального регистра Ы/еТме(х) - это множество вершин графа потока управления, в которых виртуальный регистр V жив.

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

Pressure(x)=Zie(i.....n)\{x}nLifeTime(vj)\-min(\Def(x)\,\LastUse(x)\) (2)

Здесь и далее будем считать, что N - это количество физических регистров, доступных в архитектуре. Обозначим через V(G) множество вершин графа потока управленя G. Виртуальные регистры v;.v2, ...,v„ могут быть размещены в N физических регистрах, если для каждой вершины xeV(G) выполняется

Press ure(x)<N (3)

Обозначим через D(BB) такое разбиение линейного участка ВВ на линейные участки, что для любого линейного участка QeD(BB) и любых двух вершин х и у линейного участка Q выполняется Pressure(x) =Pressure(y).

Для любого линейного участка QeD(BB) можно определить величину регистрового давления на этом участке как величину

Pressure(Q)=Pressure(v), где v - это любая вершина Q. Тогда перепишем формулу (3) следующим образом: VQeD(BB), Pressure(Q) < N.

Пусть линейный участок Q' принадлежит разбиению D(BB'), где ВВ' -это линейный участок, полученный из линейного участка ВВ после проведения частичного сброса. Тогда введем множество Dsptu(BB) = {Q'\S | Q'eD(BB')}, S=BB'\BB.

Теорема 3. Множество Dspm(BB) - это одно из разбиений вида D(BB).

Теорема 5. Если для любого QeDsp,n(BB) выполняется Pressure(Q) <N, то для ВВ' все виртуальные регистры могут быть размещены в N физических.

Пусть Num(v) - это номер вершины v линейного участка ВВ. Пусть линейный участок QeD(BB), first(Q) - это вершина О с наименьшим номером, a last(Q) - это вершина О с наибольшим номером. Тогда Q можно сопоставить сегмент I = [Num(first(Q)),Num(last(Q))].

Определим Pressure([Num(first(Q)),Num(last(Q))]) = Pressure(Q). Тогда вместо множества D(BB) можно оперировать множеством пар DI(BB) ={<1, Pressure(I)> \ I=[Num(first(Q)),Num(last(Q))], QeD(BB)}.

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

Рассмотрим виртуальный регистр v, и некоторую ячейку памяти тп где ie{l,2,...,n}. Обозначим AllSpill(v,)=(<E, mj>\EcAccess(v¿j, причем Е является

множеством корректным для сброса}. Пусть SteAUSpill(vi), где ie{l, 2.....п},

тогда обозначим E(SJ первый элемент пары S,.

Будем называть множеством всех комбинаций частичных сбросов декартово произведение AllSpill(vi)xAllSpill(v>)x... xAllSpill(vJ.

Проведением комбинации частичных сбросов относительно точки декартова произведения (Si,S2,~.,SJ называется применение к программе частичных сбросов согласно каждому S„ где ie{l, 2, ... ,п}.

Пусть L - подграф CFG, порожденный линейным участком ВВ. Обозначим через S(L) такое подмножество множества всех комбинаций частичных сбросов, что для любого его элемента (S^—.S^ выполняется условие: для любого iefl,2, ...,п} если пара <A,def> принадлежит множеству E(Si), то минимум одна пара <B,use>, потребляющая значение, вычисленное генератором А, также принадлежит E(S).

Рассмотрим некоторое подмножество X множества S(L). Пусть существует

(Si,S2.....SJeX, и выберем некоторый частичный сброс S„ где ie{l,2.....п}.

Выберем пару <А, def> eE(S,).

Обозначим через Spill(L, А)сХ множество всех таких комбинаций частичных сбросов, что для любого (S,,... Д,..., S„) eSpillfL, А) выполняется <А. def> eE(Sj).

Обозначим через NoSpill(L, А)сЛ' множество всех таких комбинаций частичных сбросов, что для любой (Si, ...,S„...,SJ eNoSpillfL, А) выполняется

<A, def>0E(Si). Тогда множество X можно представить в виде двух непересекающихся подмножеств:

X = Spill(L, A) uNoSpill(L, А) (4)

Пусть существует (S/,S2.....SJ еХ, тогда выберем некоторый частичный

сброс St, где ¡£{1,2.....п}. Выберем пару <В,ше>eE(Si). Поскольку L

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

Обозначим через Reload(L,A,B)cX множество таких комбинаций

частичных сбросов, что для любой (S/,...,S,.....S,J eReloadfL, А) выполняется

<В, use> eE(Si).

Обозначим через NoReload(L, А, В)сХ множество таких комбинаций

частичных сбросов, что для любой (Si.....S,.....SJ eNoReload(L, А, В)

выполняется <В, use> ¿E(SJ. Тогда множество X можно представить в виде двух непересекающихся подмножеств:

X = Reload(L, А, В) uNoReload(L, А, В) (5)

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

Каждая вершина t дерева Ts - это множество XcS(L).

Если Xразбиваемо согласно формуле (4), причем Spill(L,A)?0n NoSpill(L, А)*0, то у вершины t есть два сына у и z, вершине у ставится в соответствие множество Spill(L, А), вершине - ставится в соответствие множество NoSpill(L, А).

Пусть у вершины t нет сыновей у и г. Тогда, если X разбиваемо согласно формуле (5), причем Reload(L, А, В)*0и NoReload(L, А, В)*0, у вершины t

есть два сына w и v, то вершине w ставится в соответствие множество Reload(L, А, В), вершине v ставится в соответствие множество NoReload(L, А, В).

В противном случае, сыновей у вершины ( нет, и мощность |f|=/.

Пусть Leaves — это множество листьев дерева Ts достижимых из вершины t. Путь от корня Ts к его вершине t определяет комбинацию частичных сбросов S(t), описывающую принятые на этом пути решения о том, какие частичные сбросы войдут в комбинации частичных сбросов принадлежащие Leaves. Комбинация S(t) определяет линейный участок ВВ'(0, получаемый после ее применения к ВВ. Оценив эффект от проведения комбинации S(t) над ВВ, можно оценить эффект от проведения комбинаций из Leaves на ВВ.

Множеству листьев Ts соответствует множество линейных участков, получаемых после применения всех возможных комбинаций из S(L).

Обозначим через BuiltNoSpill(t) множество вершин дерева Ts такое, что:

• Vz eBuiltNoSpill(t) выполняется г е P(t)\

• Vz eBuiltNoSpill(t) у родителя г есть другие сыновья кроме z\

• Vz е BuiltNoSpill(t) соответствует множество типа NoSpill(L, А).

Обозначим через BuiltNoReload(t) множество вершин дерева Ts, такое, что:

• Vz е BuiltNoReload(t) выполняется г е P(t);

• Vz е BuillNoReload(t) у родителя z есть другие сыновья кроме

• Vz € BuiltNoReload(t) соответствует множество типа NoReload(L, А).

Пусть Dl, D2 - это некоторые неотрицательные целые числа. Семейство

поддеревьев TS(D1,D2) - это семейство, которому принадлежат все поддеревья Ts такие, что для любой их вершины t величины \BuiltNoSpill(t)\ и \BuiltNoReload(t)\ не превышают значений D1 и D2 соответственно.

Осуществим перебор множества комбинаций частичных сбросов с помощью обхода дерева Ts'eTs(Dl,D2). При обходе дерева будем использовать метод ветвей и границ для отсечения веток обхода, которые заведомо не находят наилучшей комбинации. Для этого введем переменную Record и положим ее равной бесконечности. В дальнейшем будем

16

присваивать переменной Record значение ETM(BB'(t)) для некоторой вершины I дерева Ts, если выполняются следующие два условия.

• Текущее значение Record больше величины ЕТМ(ВВ '(t)).

• Для каждого </, Pressure(I)> eDl(BB), Pressure(I)<N.

Заметим, что на пути от корня дерева Ts к его листу функция ETM(BB'ft)) монотонно не убывает. Поэтому метод ветвей и границ, реализуемый с помощью переменной Record, корректен.

Рассмотрим текущую при данном обходе вершину t дерева Г/. Если у вершины I есть сын г, то он обходится, если предикат Record>ETM(BB'(:)) истинен. Пара <l(child),Pressure(I(child))> строится по паре <l(t), Pressure(I(t))> с помощью операций над числовыми интервалами.

Параметрический алгоритм перебора комбинаций частичных сбросов заключается в предложенном обходе дерева Ts'eT(Dl, D2).

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

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

Будем называть элементарным преобразованием такое, которое является не разложимым на более мелкие. Будем говорить, что элементарное преобразование Е' зависит от преобразования £", если £'не может быть проведено без предшествующего проведения Е". Будем называть элементарное преобразование Е' несовместимым с преобразованием Е'\ если Е'не может быть проведено, если проведено Е", и Е"не может быть проведено, если проведено £'.

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

граф зависимостей между возможными преобразованиями (Transformation's dependences graph, TDG) [2].

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

• Вершина и - это виртуальный регистр, вершина v - это преобразование над инструкциями, использующими или определяющими виртуальный регистр, соответствующий и.

• Вершина и - это преобразование £„, вершина v - это преобразование Е„ преобразование Ev зависит от преобразования Еи.

Пусть элементарные преобразования Е/, Е2, ..., Е„ принадлежат множеству Trans(F), эквивалентных элементарных преобразований процедуры F. Комбинацией элементарных преобразований будем называть упорядоченную последовательность <£;, Еь ..., £„>, где 1<!<к<т<п.

Обозначим через AllTransComb(F) все комбинации элементарных преобразований из множества Trans(F) такие, что они приводят к эквивалентной процедуре F'. Рассмотрим некоторое подмножество ХсАllTransComb(F). Пусть существует комбинация CombeX, выберем некоторое элементарное преобразование Е, входящее в Comb.

Обозначим через Present(F,Ei)cX множество всех комбинаций элементарных преобразований, содержащих Et. Обозначим через NotPreseni(F,Ej)cX множество всех комбинаций элементарных преобразований, не содержащих Е

Множество X можно представить в виде разбиения

Х= Present(F, EJ uNotPresent(F, EJ (6)

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

18

Корень этого дерева - это AllTransComb(F). Каждая вершина t дерева Та -это некоторое подмножество XcAllTransComb(F).

Если X разбиваемо согласно формуле (6) относительно некоторого Е, из комбинации Comb, где CombeX, то у вершины t существует два сына y=Present(F, Ei) и z=NotPresent(F, EJ.

Путь от корня Та к его вершине / определяет комбинацию элементарных преобразований Comb(t), состоящую из преобразований разбивающих предшественника каждой вершины на этом пути согласно формуле (6). Комбинации Comb(t) соответствует процедура F'(t), которая получается из процедуры F последовательным применением преобразований Е, eComb(t). Заметим, что множество листьев дерева Та - это множество AllTransComb(F).

Пусть D — некоторое неотрицательное целое число. Рассмотрим семейство поддеревьев Ta(D) дерева Та. Обозначим через NumOßJotPresent(Ta') количество вершин типа NotPresent(L, EJ в поддереве Ta'eTa(D). Семейству поддеревьев Ta(D) принадлежат все поддеревья дерева Та, для которых выполняется NumOß!otPresent(Ta') < D.

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

Рассмотрим перебор множества комбинаций элементарных преобразований с помощью построения дерева Ta'eTa(D). Обозначим через Loop'(t+Ej) цикл, получаемый после проведения преобразования Е, над циклом Loop'(l), где t - это вершина дерева Та'. Обозначим через {EJ множество допустимых к выбору преобразований для цикла Loop'(t). Положим MaxPressure(BB)=maxV€Bs(Pressure(v)). Рассмотрим возможную стратегию выбора сыновей для вершины I.

Пусть верно, что 3E,e{Ej} такое, что MaxPressure(Loop'(t+Ej))< MaxPressure(Loop'(t)). Тогда левый сын вершины t - это множество

Present(L, EJ. Если NumOfNotPresent(Ta') < D, то правый сын вершины t - это множество NotPresent(L, Е,).

В противном случае, левый сын вершины t - это множество Present(L, E/J, такое, что VEiefEJ выполняется MaxPressure(Loop '(t+E/JJ < MaxPressure(Loop'(t+Ei)). Если NumOJNotPresent(Ta') < D, то правый сын вершины t - это множество NotPresent(L, Е0.

Для выбора наилучшей комбинации преобразований необходимо вычислять ETM(Loop'(t)) для каждой вершины t дерева Та', потому, что множество листьев дерева Та' не описывает все возможные комбинации преобразований. Эффективная оценка времени исполнения цикла Loop'(t), соответствующего вершине t, возможна, если Trans(Loop) содержит: вынос инвариантного выражения из цикла, подстановку вперед, понижение силы операций и удаление общих подвыражений.

В главе 5 проводится анализ распараллеливаемости алгоритмов построения деревьев из семейств TC(D), T/DI.D2) и Ta(D). Показывается, что параллельные варианты алгоритмов построения требуют разное количество пересылок данных и синхронизаций. С другой стороны, устанавливается, что число таких пересылок и синхронизаций невелико, поэтому предложенные методы целесообразно распараллеливать. Таким образом, время компиляции программы может быть существенно сокращено путем распараллеливания предложенных алгоритмов.

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

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

Проведены комплексные теоретические исследования и разработаны методы для проведения оптимизации программ написанных на таких современных языках программирования как С, С++, Fortran, Java и С#.

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

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

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

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

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

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Макошенко Д.В. Математическая модель времени вычислений для оптимизации программ // Известия Вузов / Издательство ЮФУ. — Ростов-на-Дону, 2009. — №2. — С. 10-13.

2. Макошенко Д.В. Назначение переменных на регистры с помощью древовидного параметрического алгоритма раскраски графа // Информационные Технологии / Москва, 2010. — № б — С. 41 - 46.

3. Штейнберг Б.Я., Макошенко Д.В., Черданцев Д.Н., Шульженко А.М. Внутреннее представление в открытой распараллеливающей системе // Искусственный интеллект / Институт проблем искусственного интеллекта НАНУ. — Украина, Донецк, 2003. — № 3. — С. 89-96.

4. Макошенко Д.В. Нахождение оптимальной комбинации преобразований для минимизации времени исполнения программы // Труды научной школы И.Б. Симоненко / Издательство ЮФУ. — Ростов-на-Дону, 2010. — С. 163-167.

5. Steinberg В., Abramov A., Alymova Е., Baglij A., Guda S., Demin S., Dubrov D., Ivchenko A., Kravchenko E., Makoshenko D., Molotnikov Z., Morilev R., Nis Z., Petrenko V., Povazhnij A., Poluyan S., Skiba I., Suhoverkhov S., Shapovalov V., Steinberg O., Steinberg R. Dialogue-Based Optimizing Parallelizing Tool and C2HDL Converter // Proceedings of IEEE EAST-WEST DESIGN & TEST SYMPOSIUM 2009 / MOSCOW, 2009. — P. 216-218.

6. Макошенко Д.В. Назначение переменных на регистры с помощью новых алгоритмов раскраски графа // Труды 52-й научной конференции МФТИ «Современные проблемы фундаментальных и прикладных наук». — Долгопрудный, 2009. — Часть I. Радиотехника и кибернетика. Том 1. — С. 96-98.

7. Штейнберг Б.Я., Макошенко Д.В., Черданцев Д.Н., Шульженко A.M. Внутреннее представление в открытой распараллеливающей системе // Интеллектуальные и многопроцессорные системы ИМС-2003, материалы Международной научно-технической конференции. — Дивноморское, 2003. — Т. 2. —С. 47-50.

Макошенко Д.В.

АНАЛИТИЧЕСКОЕ ПРЕДСКАЗАНИЕ ВРЕМЕНИ ИСПОЛНЕНИЯ ПРОГРАММ И ОСНОВАННЫЕ НА НЕМ МЕТОДЫ ОПТИМИЗАЦИИ

Отпечатано в типографии «Реглет» 119526, г.Москва, ул. Бауманская д.ЗЗ стр.1 (495) 979-96-99 www.reglet.ru

Заказ №358965

Автореферат

Подписано в печать 07.11.11 Формат бумаги 60 x90 1/16

Объем 1.5 уч.-изд. л. _Тираж 100 экз.

ВВЕДЕНИЕ.

1. ОЦЕНКА ВРЕМЕНИ ИСПОЛНЕНИЯ ПРОГРАММЫ.

1.1. Основные понятия и определения.

1.2. Модель памяти вычислительной системы.

1.3. Модель времени вычислений.

Выводы по главе 1.

2. РАСКРАСКА ГРАФА НЕСОВМЕСТИМОСТИ.

2.1. Задача оптимального распределения физических регистров

2.2. Алгоритм Чейтина-Бриггса раскраски графа несовместимости и его модификация.

2.3. Древовидный алгоритм раскраски графа несовместимости

2.4. Жадный алгоритм раскраски графа несовместимости.

2.5. Параметрический древовидный алгоритм раскраски графа несовместимости.

2.6. Особенности реализации и оценка сложности параметрического алгоритма раскраски.

Выводы по главе 2.

3. ПОНИЖЕНИЕ ХРОМАТИЧЕСКОГО ЧИСЛА ГРАФА НЕСОМЕСТИМОСТИ С ПОМОЩЬЮ РЕГИСТРОВЫХ СБРОСОВ.

3.1. Частичный сброс виртуального регистра и его свойства.

3.2. Условие распределения физических регистров.

3.3. Достаточное условие распределения регистров.

3.4. Дерево вариантов всех комбинаций частичных сбросов для линейного участка.

3.5. Выбор оптимальной комбинации частичных сбросов с помощью дерева вариантов.

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

Выводы по главе 3.

4. ВЫБОР КОМБИНАЦИИ ПРЕОБРАЗОВАНИЙ ДЛЯ МИНИМИЗАЦИИ ВРЕМЕНИ ИСПОЛНЕНИЯ ПРОГРАММЫ.

4.1. Проблема выбора комбинации преобразований.

4.2. Граф зависимостей возможных преобразований.

4.3. Дерево перебора всех возможных комбинаций элементарных преобразований.

4.4. Выбор оптимальной комбинации преобразований.

4.5. Параметрический алгоритм минимизации времени исполнения цикла программы.

Выводы по главе 4.

5. РАСПАРАЛЛЕЛИВАНИЕ ПАРАМЕТРИЧЕСКИХ АЛГОРИТМОВ ДЛЯ СОКРАЩЕНИЯ ВРЕМЕНИ КОМПИЛЯЦИИ.

5.1. Оценка целесообразности распараллеливания обхода поддеревьев из семейств ТС(Б), ТД)1,В2) и Та(0).

5.2. Анализ распараллеливаемости построения поддеревьев из семейств Тс(0).

5.3. Анализ распараллеливаемости построения поддеревьев из семейств Т5(01, Б2).

5.4. Анализ распараллеливаемости построения поддеревьев из семейств Та(1Ч).

Выводы по главе 5.

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

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

Помимо аппаратной составляющей наибольший вклад в повышение производительности дают операционная система [61], [17], [75], [1] и оптимизирующий компилятор [89], [90], [66], [32], [3], [50]. Причем, согласно измерениям, приведенным на www.spec.org [77], компилятор вносит значительно больший вклад в производительность программы, чем операционная система.

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

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

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

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

97].

Широко используемые компиляторы, например, gcc [41], MSVS[64], Intel compiler [49], проводят комбинации преобразований, которые жестко подчиняются опциям, специфицированным в командной строке. Для некоторых конкретных оптимизируемых программ такие жестко 1 зафиксированные комбинации преобразований могут привести к неоптимальному коду. Разработчики компиляторов зачастую выбирают некоторый пакет программ, например [77], на котором путем ручного подбора достигается хорошее взаимодействие преобразований.

Различными авторами исследовался метод перебора различных сочетаний параметров командной строки компилятора [29], [39] и машинное обучение [2], [79], которые влияют на выбор проводимых преобразований. Однако, задачу можно считать нерешенной для промышленных компиляторов.

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

Большое подмножество преобразований, проводимых компилятором, решают задачи, которые являются ТчГР-полными [20], [81]. Поэтому, зачастую, при разработке компилятора оптимальные алгоритмы заменяются эвристическими, чтобы сократить время компиляции до приемлемого.

Возможность контролировать эвристики, управляющие качеством преобразований, дает пользователю компилятора свободу в вопросе выбора, что в данный момент является более важным: время компиляции программы или качество проведенной оптимизации. Современные компиляторы дают возможность контролировать набор проводимых преобразований, но не оптимальность каждого конкретного преобразования [42], [82].

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

Цель и задачи работы

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

Целью данной диссертации является повышение эффективности использования системы процессор+память.

Достижение цели связано с решением следующих задач:

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

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

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

Методы исследования

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

Результаты выносимые на защиту

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

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

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

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

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

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

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

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

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

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

Результаты диссертации внедрены в официальный курс лекций "Оптимизирующие компиляторы" и используются при обучении студентов кафедры микропроцессорных технологий факультета РТК Московского физико-технического института современным методам программирования и оптимизации для различных вычислительных архитектур.

Апробация работы

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

1. Интеллектуальные и многопроцессорные системы ИМС-2003, Международная научно-техническая конференция, Дивноморское, Россия, 22-27 сентября 2003.

2. IEEE EAST-WEST DESIGN & TEST SYMPOSIUM 2009 MOSCOW, RUSSIA, September 18-21, 2009.

3. Современные проблемы фундаментальных и прикладных наук, 52-я научная конференция МФТИ, Долгопрудный, 27-28 ноября, 2009.

4. «Автоматическое распараллеливание программ», семинар кафедры алгебры и дискретной математики мехмата Южного федерального университета, 12 сентября 2005.

Публикации

Основные результаты диссертации опубликованы в семи работах, среди них четыре статьи, из которых две опубликованы в журналах перечня ВАК [97], [98], одна - в зарубежном журнале [108], одна - в сборнике научных трудов [99] и три публикации - в сборниках тезисов докладов конференций [109], [100], [78].

Структура диссертации

Диссертационная работа состоит из введения, четырех глав, заключения и списка литературы. Объем диссертации - 122 стр. Список литературы содержит 109 наименований.

ЗАКЛЮЧЕНИЕ