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

УДК 004.4'416 На правах рукописи

Серебряный Константин Сергеевич

МЕТОДЫ ВЫСОКОУРОВНЕВОЙ ОПТИМИЗАЦИИ ЦИКЛОВ

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

Автореферат диссертации на соискание ученой степени кандидата технических наук

Москва - 2004

Работа выполнена в ЗАО "МЦСТ".

Научный руководитель: кандидат технических наук,

старший научный сотрудник Волконский Владимир Юрьевич

Официальные оппоненты: доктор физико-математических наук,

профессор

Серебряков Владимир Алексеевич

Ведущая организация:

кандидат технических наук Пиргач Иван Андреевич

ОАО НИИ Супер ЭВМ

Защита состоится " 10 "_ _2004 г. в_на

оиокА /Ь'-.Ю

заседании диссертационного совета Д 002.043.01 при Институте Микропроцессорных Вычислительных Систем РАН по адресу: 119435, г. Москва, Б. Саввинский пер., д. 14.

С диссертацией можно ознакомиться в библиотеке Института Микропроцессорных Вычислительных Систем РАН.

Автореферат разослан 2004 г.

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

д.ф-м.н., профессор

л/ч

Михайлюк М.В.

Общая характеристика работы

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

На форуме Intel для разработчиков (Intel Developci Forum, IDF), прошедшем 2-го октября 2002-го года в Москве, были названы девять основных факторов повышения производительности. Среди них: а) программная конвейеризация (software pipelining),, б) автопараллслизация (autoparallelization) и в) оптимизация по профилированию (profile guided optimization. PGO).

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

Автопараллелизация — это семейство оптимизирующих трансформаций, позволяющих запускать последовательные независимые участки программы параллельно в нескольких потоках управления Наиболее распространенное применение автопараллелизации — автоматическая параллелизация циклов. Автопараллелизация позволяет эффективно использовать преимущества мультипроцессорных архитектур, в том числе и псевдо-мультипроцессорных (например, системы HyperThieading фирмы Intel).

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

РОС. НАЦИОНАЛЬНА!

БИБЛИОТЕКА

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

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

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

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

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

• анализ и частичное решение проблем, связанных с "нестандартными" управляющими переменными циклов в языках С и C + + ;

• создание методов профилирования значений для последующей специализации кода.

Предмет исследования составляют различные аспекты разработки и реализации алгоритмов оптимизации программ:

• эффективные алгоритмы идентификации, анализа и трансформации индуктивных переменных;

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

оценка конечной производительности оптимизированного кода.

Методы исследования заимствованы из областей системного программирования, технологии компиляции, символьной алгебры и теории графов. Эффективность разработанных алгоритмов и конечная производительность программ оценивались путем замера времени исполнения ряда тестовых программ, в первую очередь программ пакета SPEC CPU2000 (состоящего из двух частей: SPEGnt2000— 12 программ, использующих преимущественно целочисленную арифметику и SPECfp2000— 14 программ, активно использующих арифметику с плавающей точкой).

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

• в разработке методов идентификации и символьного анализа индуктивных переменных;

• в описании и анализе различных разновидностей "нестандартных1' управляющих переменных цикла и возможностей их трансформации:

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

Практическая ценность работы. Разработанные алгоритмы были реализованы в рамках промышленного оптимизирующего компилятора фирмы Sun для платформы SPARC (поддерживает языки Си. Си+—, Фортран 77. Фортран 90) и показали прирост производительности па ряде реальных программ. Ббльшая часть разработанных алгоритмов имеет платформо- и языко-независимый характер, что позволяет распространить их использование на максимально широкий класс процессорных архитектур и языков программирования.

Основные научные и практические результаты, выносимые на защиту

В диссертационной работе представлены следующие результаты:

1. Новые алгоритмы анализа и трансформации индуктивных переменных:

• символьный анализ индуктивных переменных;

• снижение стоимости индуктивных переменных и выражений;

• подстановка индуктивных переменных.

2. Методы решения проблемы "нестандартных" управляющих переменных: применение специализации кода и интервального анализа для нормализации управляющих переменных.

3. Новые алгоритмы специализации кода, основанные на профилировании значений:

• анализ возможных точек профилирования;

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

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

Все разработанные алгоритмы реализованы автором в оптимизирующем компиляторе для платформы SPARC и успешно прошли этап опытной эксплуатации в фирме Sun и в ЗАО "МЦСТ", дав хорошие результаты и продемонстрировав высокую надежность методов. Часть алгоритмов включена в версию промышленного компилятора, поставляемую с мая 2003 года, другую часть планируется включить в следующую версию компилятора, готовящуюся к выпуску в середине 2005 года.

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

1. Всероссийская научно-техническая конференция "Новые материалы и технологии", Москва 2002;

2. Научная конференция МФТИ, Москва-Долгопрудный 2002;

3. XXIX и XXX Международная молодежная научная конференция 'Гагаринские чтения"' (Москва 2003 и 2004);

а также на научных и технических семинарах ЗАО "МЦСТ' и ИМВС РАН и в электронном форуме по методам реализации компиляторов фирмы

Публикации. По теме диссертации опубликованы шесть работ.

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

Содержание работы

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

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

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

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

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

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

ла являлась следствием применения некоторых конструкций языка Си (и Си + + ), например, использования глобальной переменной в качестве верхней границы цикла или оператора неравенства для проверки условия выхода из цикла. Вероятно, подобные проблемы хорошо известны многим разработчикам компиляторов, однако они очень мало освещены в литературе и не были практически решены в компиляторе Sun.

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

Еще одно применение специализации кода основано на использовании так называемого профиля значений, т. е. статистической информации, полученной в результате пробного запуска программы и позволяющей предсказать наиболее вероятные значения тех или иных переменных и выражений. Так, имея подробную информацию о возможных значениях некоторого инварианта цикла, можно произвести специализацию кода и подставить значение данного инварианта в одну из копий цикла. Во многих промышленных компиляторах реализованы методы использования различной профильной информации (самыми распространенными типами такой информации следует назвать профиль переходов и профиль вызовов виртуальных функций). Однако профили значений выражений не нашли пока применения в большинстве компиляторов в силу крайне низкой скорости сбора статистики о значениях выражений. В большинстве работ по профилированию выражений упоминается замедление работы профилируемых программ на два порядка и более. В рамках диссертационой работы был разработан и реализован метод профилирования значений, замедляющий профилируемые программы всего лишь на несколько процентов, вместо десятков раз. Данный "быстрый" метод позволяет собирать статистику несколько иного рода, чем ранее известные "медленные" методы. Это дает возможность не только собрать большую часть информации о значениях выражений, доступной при использовании других методов, но также получить информацию о взаимо-

зависимости значений различных выражений.

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

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

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

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

• операция приведения типов, примененная к индуктивному выражению;

• операция деления индуктивного выражения на константу.

Центральным звеном символьного анализа индуктивных выражений является определяемое в разделе 1.3.1 понятие "точка модификации!' индуктивной переменной. Точкой модификации для индуктивной переменной называется оператор присваивания, в котором индуктивная переменная изменяет свое значение (индуктивная переменная с несколькими присваиваниями внутри цикла будет иметь несколько точек модификации). В качестве числового значения точки модификации принимается количество выполнений оператора присваивания с начала работы цикла.

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

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

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

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

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

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

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

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

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

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

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

• Применение оператора неравенства в условии выхода из цикла.

Циклы вида for(i=l; i!=u; i++) отличаются от циклов вида for(i=l; i<u; i++) тем, что число итераций может не быть равно и-1. Этот факт препятствует ряду трансформаций.

• Применение оператора постинкремента в условии выхода из цикла.

Циклы вида for(i=l; i++<u;) отличаются от циклов вида тем, что управляющая переменная на самом деле не находится в условии выхода из цикла на самом деле

означает t=i; i++; t<n1.

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

Для цикла for(i=l; i<GL0B; i++) (или :for(i=l; i<*(ptr);

)) зачастую невозможно выявить, что глобальная переменная GLOB (или результат считывания из памяти * (ptr)) является инвариантом цикла. А из этого следует, что цикл не имеет управляющей переменной.

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

Специализация кода — очень простая трансформация (рис. 1). Предположим, что у нас имеется участок кода С и условное выражение а. Если фрагмент С может быть упрощен в случае, когда выполнено условие , тогда мы можем заменить фрагмент С следующим кодом:

if(a) then Са else С

Рис. 1. Специализация кода

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

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

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

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

В конце главы обсуждаются результаты применения специализации кода для нормализации управляющих переменной на тестах пакета SPEC CPU2000. Нормализация управляющих переменных на ряде тестов позволяет существенно увеличить число таких трансформаций, как ав-топараллелизация, программная конвейеризация и динамическое разрешение конфликтов по памяти. Это, в свою очередь, приводит к повышению скорости работы нескольких тестов (до 3% на отдельном тесте). См. рис. 2.

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

Рассматривается следующий распространенный тип цикла:

for (i = 0; i < n; i++H a[i] - c[i] * A; b[i] = dCi] * B; c[i] *= C;

}

где переменные (или, в общем случае, выражения) А, В, С — инварианты цикла. Предположим, во время компиляции известны значения этих переменных: А==1, В==0, С==1. В таком случае тело цикла будет упрощено следующим образом (такая оптимизация называется распространением констант):

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

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

В данной главе обсуждается известный метод профилирования значений выражений, называемый методом TNV-таблиц (Тор N Value table). Основным недостатком этого метода является то, что инструментированная программа замедляется в десятки (а то и в сотни) раз, что существенно ограничивает область его применения.

В качестве альтернативы методу TNV предлагается новый метод:

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

static long long VP [27] ; Ц инициализирован нулями VP[ 1*((А==0)+2*(А==1)) +3*((В==0)+2*(В==1)) +9*((С==0)+2*(С=-1))]++;

Непосредственно перед завершением программы значения элементов массива YP записываются на диск — это и есть профиль значений. Так, например, значение равно числу раз, когда пе-

ременные А, В и С одновременно принимали значения 1, 0 и 1 соответственно.

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

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

(в нашем примере: а ■— это условие А==1&&В==0&&С==1, Freq(a) — вероят-

ство итераций цикла, В и Ва — оригинальное и упрощенное тело цикла, Cost(x) — стоимость выполнения участка кода х, Benefit(a) -- выигрыш от применения специализации кода по условию ).

В конце главы приводятся результаты применения профилирования значений и специализации кода к тестам пакета SPEC CPU2000. Полученный прирост производительности составил до 10% на одном из тестов (см. рис. 2).

Benefit(a) = Freq(a)lter(L)(Cost(£) - Cost(Ва)) - Cost(a)

ность истинности этого у с

Рис. 2. Прирост производительности

Проведенные эксперименты позволяют сделать следующие выводы:

• Предложенный метод профилирования значений существенно быстрее метода TNV (инструментированные программы замедляются менее чем на 10%).

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

В заключении коротко излагаются полученные практические и теоретические результаты.

В приложении дается краткое описание внутренней структуры компилятора фирмы Sun и показывается расположение реализованных оп-

тимизаций в этом компиляторе. Все рассмотренные трансформации реализованы в модуле ¡гор<;., отвечающем за высокоуровневые оптимизации программ (см. рис. 3).

*.с ' -*.срр: •,*Л90>

випИ ф

•! *.о ■

Рис. 3. Структура оптимизирующего компилятора Sun

Выводы

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

Новые алгоритмы позволяют:

• обрабатывать индуктивные переменные с несколькими присваиваниями;

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

• анализировать и оптимизировать операторы преобразования типов; примененные к индуктивным переменным и выражениям;

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

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

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

• использование оператора ! = вместо оператора < в условии завершения цикла;

• использование оператора постинкремента в условии завершения цикла;

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

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

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

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

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

7. Реализованные оптимизации позволяют существенно повысить производительность реальных программ. На программах тестового набора SPEC CPU2000 был получен прирост производительности до 12%.

Публикации по теме диссертации

1. И. Л. Дьячков, К. С. Серебряный. Профилирование значений выражений для оптимизации программ // XXIX Гагаринские чтения. Международная молодежная научная конференция. Тезисы докладов Т. 5, М.: 2003. С. 20-21.

2. К. С. Серебряный. Методы оптимизации программ, использующие дублирование кода // Новые материалы и технологии. Тезисы докладов Всероссийской научно-технической конференции. Т. 3. М.: 2002. С. 40-41.

3. К. С. Серебряный. Способ оптимизации программ с использованием раскрутки циклов // Информационные технологии 2003, N 1. С. 12-15.

4. К. С. Серебряный. Трансформации циклов, производимые оптимизирующими компиляторами // Современные проблемы фундаментальных и прикладных наук. Научная конференция МФТИ. Часть I: Радиотехника и кибернетика. Москва-Долгопрудный, 2002. С. 42-43.

5. К. С. Серебряный. Трансформации циклов, содержащих индуктивные переменные // Информационные технологии 2003, N 9. С. 2229.

6. К. С. Серебряный. Нормализация структуры циклов // XXX Гага-ринские чтения. Международная молодежная научная конференция. Тезисы докладов Т. 5, М.: 2004. С. 56.

Принято к исполнению 27/04/2004 Исполнено 28/04/2004

Заказ № 167 Тираж: 100 экз.

ООО «11-й ФОРМАТ» ИНН 7726330900 Москва, Балаклавскийпр-т, 20-2-93 (095)318-40-68 www.autoreferat.ru

9457

Содержание

Введение

1 Трансформации индуктивных переменных

1.1 Трансформации циклов.

1.1.1 Автоматическая параллелизация

1.1.2 Распознавание циклов-идиом.

1.1.3 Перестановка циклов.

1.1.4 Снижение стоимости индуктивных выражений.

1.1.5 Развертка циклов.

1.2 Индуктивные переменные и выражения

1.2.1 Преобразование типов индуктивных переменных.

1.2.2 Деление индуктивного выражения на константу

1.3 Символьное представление индуктивных выражений.

1.3.1 С-функция.

1.3.2 Каноническая форма С-функции.

1.3.3 Линейные С-функции.

1.4 Подстановка индуктивных переменных.

1.4.1 Подстановка точек модификации

1.4.2 Вычисление количества итераций цикла.

1.4.3 Подстановка индуктивных переменных.

1.5 Снижение стоимости

1.6 Другие реализации алгоритмов.

1.6.1 Идентификация индуктивных переменных.

1.6.2 Снижение стоимости индуктивных выражений.

1.6.3 Подстановка индуктивных переменных.

1.7 Результаты.

1.8 Выводы.

2 Нормализация структуры управляющей переменной цикла

2.1 Использование беззнакового типа.

2.2 Использование оператора != в условии цикла.

2.3 Использование оператора постинкремента

2.4 Использование глобальной переменной в качестве верхней границы

2.5 Порядок нормализации циклов

2.6 Ограничения применения специализации кода.

2.7 Результаты.

2.8 Выводы.

3 Профилирование значений выражений для специализации кода

3.1 Специализация кода по конкретным значениям инвариантов.

3.2 Профилирование значений выражений.

3.2.1 Инструментирование программы

3.2.2 Использование результатов инструментирования.

3.3 Результаты.

3.4 Выводы.

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

На форуме Intel для разработчиков (Intel Developer Forum, IDF), прошедшем 2-го октября 2002-го года в Москве, были названы девять основных факторов повышения производительности при использовании компиляторов Intel [11]. Среди них:

1. программная конвейеризация (software pipelining) для архитектуры Itanium,

2. автопараллелизация (autoparallelization) и

3. оптимизация по профилированию (profile guided optimization, PGO).

Программная конвейеризация — это такая трансформация циклов, которая позволяет наиболее эффективно использовать параллелизм уровня команд в большинстве современных микропроцессоров, в том числе, например, в Sun ULTRASparc™ IIICu или Intel Itanium™.

Автопараллелизация — это семейство оптимизирующих трансформаций, позволяющих запускать последовательные независимые участки программы параллельно в нескольких потоках управления (threads). Наиболее распространенное применение автопараллелизации — автоматическая параллелизация циклов. Автопараллелизация позволяет эффективно использовать преимущества мультипроцессорных архитектур, в том числе и псевдо-мультипроцессорных (например, системы HyperThreading фирмы Intel).

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

Наиболее важные виды оптимизации не случайно связаны именно с оптимизацией циклов. Как отмечается во многих работах по оптимизирующим компиляторам, основное время исполнения большинства программ приходится именно на циклы ([20], [13, §10.2]), и поэтому оптимизации циклов уделяется наибольшее внимание при разработке компиляторов.

Основы оптимизирующего компилятора фирмы Sun для платформы SPARC закладывались в начале восьмидесятых годов прошлого века с использованием самых современных (на тот момент) технологий, а один из создателей этого компилятора, Steven Muchnick, позднее написал книгу [41], которая по праву считается одной из фундаментальных работ по компиляторам. Практически с самого начала существования данного компилятора в нем были реализованы многие классические трансформации циклов, такие, например, как вынос инвариантов цикла и снижение стоимости индуктивных выражений. С момента своего создания и по сегодняшний день компилятор фирмы Sun активно развивается — за последние годы в нем появились такие важные трансформации, как программная конвейеризация и автоматическая параллелизация, а также многие другие.

Однако, с развитием компилятора становилось очевидно, что алгоритмы, заложенные при его создании, уже перестали удовлетворять все возрастающие потребности. Среди прочего, возникла необходимость в разработке нового алгоритма снижения стоимости индуктивных выражений (далее для краткости: снижение стоимости). Вряд ли можно найти оптимизацию, изученную подробнее, чем снижение стоимости: она описана во многих книгах по компиляторам ([13, §10.2], [41, §14.1.2],

17, §6.2.3]) и, без сомнения, так или иначе реализована во всех промышленных оптимизирующих компиляторах.

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

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

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

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

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

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

Еще одно применение специализации кода основано на использовании так называемого профиля значений, т. е. статистической информации, полученной в результате пробного запуска программы и позволяющей предсказать наиболее вероятные значения тех или иных переменных и выражений. Так, имея подробную информацию о возможных значениях некоторого инварианта цикла, можно произвести специализацию кода и подставить значение данного инварианта в одну из копий цикла. Во многих промышленных компиляторах реализованы методы использования различной профильной информации (самыми распространенными типами такой информации следует назвать профиль переходов и профиль вызовов виртуальных функций). Однако профили значений выражений не нашли пока применения в большинстве компиляторов в силу крайне низкой скорости сбора статистики о значениях выражений. В большинстве работ по профилированию выражений упоминается замедление работы профилируемых программ на два порядка и более. В рамках диссертационой работы был разработан и реализован метод профилирования значений, замедляющий профилируемые программы всего лишь на несколько процентов, вместо десятков раз. Данный "быстрый" метод позволяет собирать статистику несколько иного рода, чем ранее известные "медленные" методы. Это дает возможность не только собрать бблыпую часть информации о значениях выражений, доступной при использовании других методов, но также получить информаг цию о взаимозависимости значений различных выражений.

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

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

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

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

• анализ и частичное решение проблем, связанных с "нестандартными" управляющими переменными циклов в языках С и С++;

• создание методов профилирования значений для последующей специализации кода.

Предмет исследования составляют различные аспекты разработки и реализации алгоритмов оптимизации программ:

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

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

• оценка конечной производительности оптимизированного кода.

Методы исследования заимствованы из областей системного программирования, технологии компиляции, символьной алгебры и теории графов. Эффективность разработанных алгоритмов и конечная производительность программ оценивались путем замера времени исполнения ряда тестовых программ, в первую очередь SPEC CPU2000, на двухпроцессорной рабочей станции SunBlade™ 1000.

Тестовый набор SPEC CPU2000 ([56]) — это международно признанный пакет тестов для оценки производительности вычислительных систем, состоящий из двух частей: набор программ, использующих преимущественно целочисленную арифметику (SPECint2000) и набор программ, использующих в основном арифметику с плавающей запятой (SPECfp2000). Пакет содержит в общей сложности 26 программ (12 в SPECint2000 и 14 в SPECfp2000), представляющих различные сферы применения языков программирования Си, Си++, Фортран 77 и Фортран 90, таг ких как: архивация данных, компьютерная графика и распознавание образов, компиляция и интерпретация языков программирования, теория чисел, базы данных, искусственный интеллект (игра в шахматы), физика, химия, метеорология и др. Для каждой программы из тестового пакета имеется три набора входных данных: test — малый набор данных, используемый для проверки работоспособности теста, train — набор данных среднего размера, используемый для пробного запуска при многофазной схеме компиляции и ref — большой набор данных, используемый для измерения времени работы программы. Кроме пакета SPEC CPU2000, в процессе анализа и тестирования разработанных алгоритмов использовались тесты SPEC CPU95, bench++ и другие.

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

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

• в разработке методов идентификации и символьного анализа индуктивных переменных;

• в описании и анализе различных разновидностей "нестандартных" управляющих переменных цикла и возможностей их трансформации;

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

Практическая ценность работы. Разработанные алгоритмы были реализованы в рамках промышленного оптимизирующего компилятора фирмы Sun для платформы SPARC (поддерживает языки Си, Си++, Фортран 77, Фортран 90) и показали прирост производительности на ряде реальных программ. Бблыпая часть разработанных алгоритмов имеет платформо- и языко-независимый характер, что позволяет распространить их использование на максимально широкий класс процессорных архитектур и языков программирования.

Основные научные и практические результаты, выносимые на защиту

В диссертационной работе представлены следующие результаты:

1. Новые алгоритмы анализа и трансформации индуктивных переменных:

• символьный анализ индуктивных переменных;

• снижение стоимости индуктивных переменных и выражений;

• подстановка индуктивных переменных.

2. Исследование проблемы "нестандартных" управляющих переменных и методы ее решения: применение специализации кода и интервального анализа для нормализации управляющих переменных.

3. Новые алгоритмы специализации кода, основанные на профилировании значений:

• анализ возможных точек профилирования;

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

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

Все разработанные алгоритмы реализованы автором в оптимизирующем компиляторе фирмы Sun и успешно прошли этап опытной эксплуатации в фирме Sun и в ЗАО "МЦСТ", дав хорошие результаты и продемонстрировав высокую надежность методов. Часть алгоритмов включена в версию компилятора, поставляемого с мая 2003 года, другую часть планируется включить в коммерческую версию компилятора, готовящуюся к выпуску в середине 2005 года.

Публикации

По теме диссертации опубликовано шесть работ:

1. И. Л. Дьячков, К. С. Серебряный. Профилирование значений выражений для оптимизации программ // XXIX Гагаринские чтения. Международная молодежная научная конференция. Тезисы докладов Т. 5, 2003. С. 20-21 ([1]).

2. К. С. Серебряный. Методы оптимизации программ, использующие дублирование кода // Новые материалы и технологии. Тезисы докладов Всероссийской научно-технической конференции, Т. 3, 2002. С. 40-41 ([2]).

3. К. С. Серебряный. Трансформации циклов, производимые оптимизирующими компиляторами // Современные проблемы фундаментальных и прикладных наук. Научная конференция МФТИ. Часть I: Радиотехника и кибернетика. Москва-Долгопрудный, 2002. С. 42-43 ([3]).

4. К. С. Серебряный. Способ оптимизации программ с использованием раскрутки циклов // Информационные технологии 2003, N 1. С. 12-15 ([4]).

5. К. С. Серебряный. Трансформации циклов, содержащих индуктивные переменные // Информационные технологии 2003, N 9. С. 22-29 ([5]).

6. К. С. Серебряный. Нормализация структуры циклов // XXX Гагаринские чтения. Международная молодежная научная конференция. Тезисы докладов Т. 5, 2004. С. 56 ([б]).

Апробация ~

Результаты работы докладывались на научных конференциях:

1. Всероссийская научно-техническая конференция "Новые материалы и технологии", Москва 2002;

2. Научная конференция МФТИ, Москва-Долгопрудный 2002;

3. XXIX и XXX Международная молодежная научная конференция "Гагарин-ские чтения" (Москва 2003 и 2004); а также на научных и технических семинарах ЗАО "МЦСТ" и ИМВС РАН и в электронном форуме по методам реализации компиляторов фирмы Sun.

Краткое содержание работы

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

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

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

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

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

1 Трансформаций* индуктивных переменных

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

Таблица 1.

Типы циклов в пакете SPEC CPU2000.

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

SPECint2000 3500 4400 3100

SPECfp2000 10200 1150 400

Всего 13700 5550 3500

Автором работы предлагается метод символьного анализа индуктивных переменных и выражений, в том числе и управляющих переменных, позволяющий получить полную информацию о структуре индуктивных выражений и произвести над ними различные трансформации. Две таких трансформации — снижение стоимости индуктивных выражений и подстановка индуктивных переменных, разработанные автором в рамках диссертационной работы — также описываются в данной главе. Реализации этих трансформаций были внедрены в компилятор Sun, заняв место предыдущих реализаций этих же трансформаций, что позволило улучшить качество создаваемого кода. Описание и сравнительный анализ прежних алгоритмов приводятся в разделе 1.6, а в разделе 1.7 представлены практические результаты применения новых алгоритмов по сравнению со старыми. Кроме алгоритмов

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

3.4 Выводы

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

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

Основным практическим результатом данной главы является реализация описанных методов профилирования значений для специализации циклов. Эти методы позволили получить большое увеличение производительности реальных программ (до 10% на тестах пакета SPEC CPU2000).

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

Заключение

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

Новые алгоритмы позволяют:

• обрабатывать индуктивные переменные с несколькими присваиваниями;

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

• анализировать и оптимизировать операторы преобразования типов, примененные к индуктивным переменным и выражениям;

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

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

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

• использование оператора != вместо оператора < в условии завершения цикла;

• использование оператора постинкремента в условии завершения цикла;

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

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

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

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

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

7. Реализованные оптимизации позволяют существенно повысить производительность реальных программ. На программах тестового набора SPEC CPU2000 был получен прирост производительности до 12%.

Разработка и исследование в области высокоуровневых оптимизаций циклов осуществлялась (и продолжает осуществляться) в рамках проекта оптимизатора промежуточного представления iropt (см. приложение), проводимого совместно фирмами ЗАО "МЦСТ" и Sun Microsystems с 1992 года. Автором были разработаны и реализованы все оптимизации, предложенные в главах 1, 2 и 3.

В заключение автору хотелось бы поблагодарить всех специалистов, принимавших (и принимающих) участие в проекте iropt, в том числе: С. Гурьева, Е. Черниса, В. Яковлева, В. Броля (Россия) и X. Kong, Б. Синдеева (США). Я выражаю глубокую признательность руководителю проекта iropt г-ну J.-Z. Wang за проявленное понимание и предоставленную возможность работать над диссертацией. Особо хочу поблагодарить моего научного руководителя к.т.н. В.Ю. Волконского и проф. В.В. Шилова, без которых данная работа не могла бы осуществиться.