Книги, научные публикации
УДК 004.4Т416
На правах рукописи
Серебряный Константин Сергеевич МЕТОДЫ ВЫСОКОУРОВНЕВОЙ ОПТИМИЗАЦИИ ЦИКЛОВ 05.13.11 - УМатематическое и программное обеспечение вычислительных машин, комплексов и
компьютерных сетейФ
Автореферат диссертации на соискание ученой степени кандидата технических наук
Москва - 2004
Работа выполнена в ЗАО УМЦСТФ.
Научный консультант: кандидат технических наук, старший научный сотрудник Волконский Владимир Юрьевич
Официальные оппоненты: доктор физико-математических наук, профессор Серебряков Владимир Алексеевич кандидат технических наук Пиргач Иван Андреевич
Ведущая организация: ОАО НИИ Супер ЭВМ
Защита состоится УФ 2004 г. в на заседании диссертационного совета Д 002.043.01 при Институте Микро процессорных Вычислительных Систем РАН по адресу:
119435, г. Москва, Б. Саввинский пер., д. 14.
С диссертацией можно ознакомиться в библиотеке Института Микропроцессорных Вычислительных Систем РАН.
Автореферат разослан УФ 2004 г.
Ученый секретарь диссертационного совета:
д.ф-м.н., профессор Михайлюк М.В.
Общая характеристика работы
Актуальность темы. С момента появления вычислительной техни ки и по сегодняшний день скорость выполнения программ была и остает ся важной темой исследований. Один из наиболее эффективных методов ускорения работы программ использование оптимизирующих компи ляторов. Увеличение мощности современных компьютеров приводит не только к ускорению выполнения программ, но и к появлению новых воз можностей, в том числе и для оптимизирующих компиляторов. Кроме того, изменение архитектуры процессоров определяет необходимость со здания новых и переработки уже имеющихся методов автоматической оптимизации.
На форуме Intel для разработчиков (Intel Developer Forum, IDF), прошедшем 2-го октября 2002-го года в Москве, были названы девять основных факторов повышения производительности. Среди них: а) про граммная конвейеризация (software pipelining), б) автопараллелизация (autoparallelization) и в) оптимизация по профилированию (profile guided optimization, PGO).
Программная конвейеризация это такая трансформация циклов, которая позволяет наиболее эффективно использовать параллелизм уровня команд в большинстве современных микропроцессоров, в том числе, например, в Sun ULTRASparcTM IIICu или Intel ItaniumTM.
Автопараллелизация это семейство оптимизирующих трансфор маций, позволяющих запускать последовательные независимые участ ки программы параллельно в нескольких потоках управления (threads).
Наиболее распространенное применение автопараллелизации автома тическая параллелизация циклов. Автопараллелизация позволяет эф фективно использовать преимущества мультипроцессорных архитек тур, в том числе и псевдо-мультипроцессорных (например, системы HyperThreading фирмы Intel).
Оптимизация по профилированию это многофазная схема оптими зации программ, состоящая из инструментирования программы, пробно го прогона на характерном наборе данных и последующего использова -1 ния полученной статистики при финальной компиляции. Оптимизация по профилированию позволяет правильно предсказывать переходы, на ходить критические пути исполнения, оценивать число итераций циклов и выявлять те участки программы, к которым следует применять наи более агрессивные оптимизации.
Наиболее важные виды оптимизации не случайно связаны именно с оптимизацией циклов. Как отмечается во многих работах по опти мизирующим компиляторам, основное время исполнения большинства программ приходится именно на циклы, и поэтому оптимизации циклов уделяется наибольшее внимание при разработке компиляторов.
Цель диссертационного исследования разработка новых и моди фикация имеющихся методов и алгоритмов оптимизации программ, свя занных с программной конвейеризацией и автопараллелизацией, а также использующих профилирование. Исходя из поставленной цели, в диссер тационной работе решаются следующие задачи:
Х разработка нового алгоритма снижения стоимости для индуктив ных переменных, позволяющего в ряде случаев улучшить возмож ности последующей программной конвейеризации;
Х разработка нового алгоритма подстановки индуктивных перемен ных, увеличивающего возможности автопараллелизации;
Х анализ и частичное решение проблем, связанных с Унестандартны миФ управляющими переменными циклов в языках С и C++;
Х создание методов профилирования значений для последующей спе циализации кода.
Предмет исследования составляют различные аспекты разработ ки и реализации алгоритмов оптимизации программ:
Х эффективные алгоритмы идентификации, анализа и трансформа ции индуктивных переменных;
Х эффективные методы профилирования значений и выбора участ ков кода для специализации;
-2 Х оценка конечной производительности оптимизированного кода.
Методы исследования заимствованы из областей системного про граммирования, технологии компиляции, символьной алгебры и тео рии графов. Эффективность разработанных алгоритмов и конечная производительность программ оценивались путем замера времени ис полнения ряда тестовых программ, в первую очередь программ паке та SPEC CPU2000 (состоящего из двух частей: SPECint2000 12 про грамм, использующих преимущественно целочисленную арифметику и SPECfp2000 14 программ, активно использующих арифметику с плава ющей точкой).
Научная новизна работы заключается в создании новых методов анализа и автоматической оптимизации программ, а именно:
Х в разработке методов идентификации и символьного анализа ин дуктивных переменных;
Х в описании и анализе различных разновидностей УнестандартныхФ управляющих переменных цикла и возможностей их трансформа ции;
Х в разработке быстрого метода профилирования значений с целью последующей оптимизации кода.
Практическая ценность работы. Разработанные алгоритмы были реализованы в рамках промышленного оптимизирующего компилятора фирмы Sun для платформы SPARC (поддерживает языки Си, Си++, Фортран 77, Фортран 90) и показали прирост производительности на ря де реальных программ. Б ольшая часть разработанных алгоритмов имеет платформо- и языко-независимый характер, что позволяет распростра нить их использование на максимально широкий класс процессорных архитектур и языков программирования.
-3 Основные научные и практические результаты, выно симые на защиту В диссертационной работе представлены следующие результаты:
1. Новые алгоритмы анализа и трансформации индуктивных пере менных:
Х символьный анализ индуктивных переменных;
Х снижение стоимости индуктивных переменных и выражений;
Х подстановка индуктивных переменных.
2. Методы решения проблемы УнестандартныхФ управляющих пере менных: применение специализации кода и интервального анализа для нормализации управляющих переменных.
3. Новые алгоритмы специализации кода, основанные на профилиро вании значений:
Х анализ возможных точек профилирования;
Х метод быстрого профилирования конкретных значений сразу нескольких переменных или выражений;
Х специализация кода по полученной статистике значений пере менных и выражений.
Все разработанные алгоритмы реализованы автором в оптимизирующем компиляторе для платформы SPARC и успешно прошли этап опытной эксплуатации в фирме Sun и в ЗАО УМЦСТФ, дав хорошие результаты и продемонстрировав высокую надежность методов. Часть алгоритмов включена в версию промышленного компилятора, поставляемую с мая 2003 года, другую часть планируется включить в следующую версию компилятора, готовящуюся к выпуску в середине 2005 года.
Апробация. Результаты работы докладывались на научных конфе ренциях -4 1. Всероссийская научно-техническая конференция УНовые материа лы и технологииФ, Москва 2002;
2. Научная конференция МФТИ, МоскваЦДолгопрудный 2002;
3. XXIX и XXX Международная молодежная научная конференция УГагаринские чтенияФ (Москва 2003 и 2004);
а также на научных и технических семинарах ЗАО УМЦСТФ и ИМВС РАН и в электронном форуме по методам реализации компиляторов фирмы Sun.
Публикации. По теме диссертации опубликованы шесть работ.
Структура и объем работы. Диссертация состоит из введения, трех глав, заключения и приложения. Диссертация содержит 91 страни цу, в том числе 3 иллюстрации, 13 таблиц и 33 примера кода. Список литературы насчитывает 56 наименований.
Содержание работы Во введении обоснована актуальность работы, сформулирована цель исследования и определены задачи, решаемые для ее достижения.
Отмечена научная новизна исследования;
дана общая характеристика работы и ее результатов.
Основы оптимизирующего компилятора фирмы Sun для платформы SPARC закладывались в начале восьмидесятых годов прошлого века с использованием самых современных (на тот момент) технологий, а один из создателей этого компилятора, С. Мучник, стал автором книги, кото рая по праву считается одной из фундаментальных работ по компилято рам. Практически с самого начала существования данного компилятора в нем были реализованы многие классические трансформации циклов, такие, например, как вынос инвариантов цикла и снижение стоимости индуктивных выражений. С момента своего создания и по сегодняшний день компилятор фирмы Sun активно развивается за последние годы в нем появились такие важные трансформации, как программная кон вейеризация и автоматическая параллелизация, а также многие другие.
-5 С развитием компилятора становилось очевидно, что алгоритмы, за ложенные при его создании, уже перестали удовлетворять все возраста ющие потребности. Среди прочего, возникла необходимость в разработке нового алгоритма снижения стоимости индуктивных выражений (далее для краткости: снижение стоимости). Вряд ли можно найти оптимиза цию, изученную подробнее, чем снижение стоимости: она описана во мно гих книгах по компиляторам и, без сомнения, так или иначе реализована во всех промышленных оптимизирующих компиляторах.
Тем не менее, новый алгоритм снижения стоимости, разработанный в рамках диссертационной работы, важен как минимум по двум причинам.
Во-первых, этот алгоритм разработан не только как теоретическое по строение, но и внедрен в работающий компилятор с его заданной струк турой представления программы, при этом за то же время выполняет существенно большее число трансформаций, чем предыдущий алгоритм, реализованный в компиляторе Sun. Во-вторых, в основу предлагаемого алгоритма снижения стоимости положен такой механизм символьного анализа индуктивных переменных и индуктивных выражений, который применим для очень широкого класса оптимизаций и точного аналога которому автор не нашел в известной ему литературе.
После успешного внедрения в компилятор механизма символьного анализа индуктивных выражений было решено применить данный ме ханизм для реализации еще одной оптимизирующей трансформации подстановки индуктивных переменных. Данная оптимизация, необходи мая в первую очередь для параллелизации циклов, достаточно изуче на, однако ее прежняя реализация не позволяла охватить ряд важных случаев. Применение символьного анализа к индуктивным переменным позволило существенно расширить множество обрабатываемых случаев, сохранив прежнее время компиляции.
В процессе работы над алгоритмами трансформации индуктивных переменных и в ходе исследования результатов их работы было обнару жено большое количество таких циклов, которые невозможно трансфор мировать из-за неправильной структуры управляющей переменной цик ла. Зачастую неправильная структура управляющей переменной цик -6 ла являлась следствием применения некоторых конструкций языка Си (и Си++), например, использования глобальной переменной в качестве верхней границы цикла или оператора неравенства для проверки усло вия выхода из цикла. Вероятно, подобные проблемы хорошо известны многим разработчикам компиляторов, однако они очень мало освещены в литературе и не были практически решены в компиляторе Sun.
В диссертационной работе предлагается метод нормализации струк туры цикла с использованием специализации кода, то есть при помощи дублирования цикла и вставки в код динамической проверки определен ных условий. Реализация данного метода широко использует механизм символьного анализа индуктивных переменных, упомянутый выше.
Еще одно применение специализации кода основано на использовании так называемого профиля значений, т. е. статистической информации, полученной в результате пробного запуска программы и позволяющей предсказать наиболее вероятные значения тех или иных переменных и выражений. Так, имея подробную информацию о возможных значениях некоторого инварианта цикла, можно произвести специализацию кода и подставить значение данного инварианта в одну из копий цикла. Во многих промышленных компиляторах реализованы методы использова ния различной профильной информации (самыми распространенными типами такой информации следует назвать профиль переходов и про филь вызовов виртуальных функций). Однако профили значений выра жений не нашли пока применения в большинстве компиляторов в си лу крайне низкой скорости сбора статистики о значениях выражений.
В большинстве работ по профилированию выражений упоминается за медление работы профилируемых программ на два порядка и более. В рамках диссертационой работы был разработан и реализован метод про филирования значений, замедляющий профилируемые программы всего лишь на несколько процентов, вместо десятков раз. Данный УбыстрыйФ метод позволяет собирать статистику несколько иного рода, чем ранее известные УмедленныеФ методы. Это дает возможность не только собрать б ольшую часть информации о значениях выражений, доступной при ис пользовании других методов, но также получить информацию о взаимо -7 зависимости значений различных выражений.
В главе 1 предлагается метод символьного анализа индуктивных переменных и выражений, в том числе и управляющих переменных, поз воляющий получить полную информацию о структуре индуктивных вы ражений и произвести над ними различные трансформации.
Для объяснения цели символьного анализа индуктивных перемен ных проанализированы наиболее характерные трансформации циклов с индуктивными переменными, в том числе: автопараллелизация, распо знавание циклов-идиом, перестановка циклов, снижение стоимости ин дуктивных переменных, развертка циклов.
Даны строгие определения индуктивных переменных цикла, индук тивных выражений, управляющей переменной цикла. Приведены алго ритмы идентификации индуктивных выражений.
Отдельно рассмотрены два вида индуктивных выражений, которые практически не описаны в литературе, однако часто встречаются на практике:
Х операция приведения типов, примененная к индуктивному выра жению;
Х операция деления индуктивного выражения на константу.
Центральным звеном символьного анализа индуктивных выражений является определяемое в разделе 1.3.1 понятие Уточка модификацииФ индуктивной переменной. Точкой модификации для индуктивной пере менной называется оператор присваивания, в котором индуктивная пере менная изменяет свое значение (индуктивная переменная с несколькими присваиваниями внутри цикла будет иметь несколько точек модифика ции). В качестве числового значения точки модификации принимается количество выполнений оператора присваивания с начала работы цикла.
При помощи понятия Уточка модификацииФ определяется символьная функция индуктивного выражения и предлагается алгоритм вычисления символьных функций для всех индуктивных выражений цикла.
Как и в любом другом механизме символьного анализа, в анализе индуктивных выражений необходимо приводить все символьные выра -8 жения к некоторому каноническому (стандартному) виду. В разделе 1.3. определяется такой канонический вид и дается алгоритм приведения к нему произвольного символьного выражения.
Подавляющее число трансформаций индуктивных выражений обра батывают только т. н. линейные индуктивные выражения. Поэтому от дельно определяется линейная символьная функция и задается алгоритм ее вычисления.
В качестве примеров применения разработанного метода символьно го анализа индуктивных выражений предлагаются алгоритмы двух важ ных трансформаций: подстановки индуктивных переменных и снижения стоимости индуктивных выражений. Кроме того, приводится ряд вспо могательных алгоритмов, основанных на символьном анализе индуктив ных выражений.
Проводится сравнение с одной стороны новых алгоритмов идентифи кации, анализа и трансформаций индуктивных выражений и с другой стороны ранее известных алгоритмов (в том числе, применявшихся ра нее в компиляторе Sun).
В конце главы обсуждаются результаты применения рассматрива емых алгоритмов на программах тестового пакета SPEC CPU2000. Из приведенных в разделе 1.7 таблиц видно, что новые алгоритмы позво ляют идентифицировать существенно большее число индуктивных вы ражений и произвести большее количество трансформаций, что, в свою очередь, приводит к уменьшению времени исполнения ряда тестов (до 12% на отдельном тесте). См. также рис. 2.
В главе 2 проанализированы несколько характерных для языков Си и Си++ проблем, связанных со структурой управляющих переменных:
Х Использование беззнакового целого типа для управляющей пере менной.
Беззнаковый тип имеет более жесткие ограничения на результа ты выполнения операций (а именно, на результат целочисленно го переполнения), чем знаковый. Эти ограничения зачастую пре пятствуют проведению ряда трансформаций индуктивных выра -9 жений, особенно в случае, когда размер управляющей переменной меньше размера указателя (характерная ситуация при компиляции для 64-битной архитектуры).
Х Применение оператора неравенства в условии выхода из цикла.
Циклы вида for(i=l;
i!=u;
i++) отличаются от циклов вида for(i=l;
i i++)тем, что число итераций может не быть равно u-l. Этот факт препятствует ряду трансформаций. Х Применение оператора постинкремента в условии выхода из цикла. Циклы вида for(i=l; i++ ) отличаются от циклов вида for(i=l; i<=u; i++)тем, что управляющая переменная на самом деле не находится в условии выхода из цикла (i++ i++; t Х Использования глобальной переменной или результата считывания из памяти в качестве верхней границы цикла. Для цикла for(i=l; i i++) (или for(i=l; i<*(ptr); i++)) зачастую невозможно выявить, что глобальная переменная GLOB(или результат считывания из памяти*(ptr)) является инва риантом цикла. А из этого следует, что цикл не имеет управляющей переменной. Для решения перечисленных проблем (т. е. для нормализации струк туры управляющей переменной) предлагается использовать а) методы интервального анализа значений выражений и б) специализацию кода. Наибольшее внимание уделено специализации кода. Специализация кода очень простая трансформация (рис. 1). Пред положим, что у нас имеется участок кода C и условное выражение. Если фрагмент C может быть упрощен в случае, когда выполнено усло вие, тогда мы можем заменить фрагмент C следующим кодом: if() then C else C -10 Рис. 1. Специализация кода где C это версия фрагмента C, упрощенная благодаря тому факту, что условие выполнено. Для корректности такой трансформации до статочно, чтобы условие не имело побочных эффектов, а фрагмент кода C имел ровно один вход. В данной главе анализируются возможности применения специали зации кода к циклам, имеющим одну или несколько проблем (перечис ленных выше) с управляющей переменной. Так, например, цикл extern i nt N; f o r(in t i = 0; i <= N; i++) a[i] = b[i]; может быть нормализован при помощи специализации кода следующим образом: i f(&N < a || &N > (a+N)){ i n t tmp = N; fo r(i nt i = 0; i <= tmp; i++) a[i] = b[i]; }e l s e{ <исходный цикл> } Предлагается также ряд УэвристикФ позволяющих компилятору оце нить необходимость проведения специализации кода. В конце главы обсуждаются результаты применения специализа ции кода для нормализации управляющих переменной на тестах пакета SPEC CPU2000. Нормализация управляющих переменных на ряде тестов позволяет существенно увеличить число таких трансформаций, как ав топараллелизация, программная конвейеризация и динамическое разре шение конфликтов по памяти. Это, в свою очередь, приводит к повыше нию скорости работы нескольких тестов (до 3% на отдельном тесте). См. рис. 2. -11 В главе 3 рассматривается еще одно применение специализации ко да к циклам: специализация, основанная на профилировании значений выражений. Рассматривается следующий распространенный тип цикла: f o r(i = 0; i < n; i++){ a[i] = c[i] * A; b[i] = d[i] * B; c[i] *= C; } где переменные (или, в общем случае, выражения)A,B,C инварианты цикла. Предположим, во время компиляции известны значения этих пе ременных:A==1,B==0,C==1. В таком случае тело цикла будет упрощено следующим образом (такая оптимизация называется распространением констант): a[i] = c[i]; b[i] = 0; Нередко встречается ситуация, при которой значения инвариантов цикла (в нашем примере значения переменныхA,B,C) нельзя вы числить во время компиляции, но во время исполнения программы они всегда принимают одно и то же значение, или одно из принимаемых ими значений наиболее вероятно. Статистическая информация о наиболее вероятных значениях выражений называется профилем значений выра жений. Профиль значений выражений (так же, как и профиль переходов или другие виды профилей) получается в ходе исполнения инструментиро ванной (т. е. специальным образом скомпилированной) программы, а за тем подается на вход компилятора. В данной главе обсуждается известный метод профилирования значе ний выражений, называемый методом TNVЦтаблиц (Top N Value table). Основным недостатком этого метода является то, что инструментиро ванная программа замедляется в десятки (а то и в сотни) раз, что суще ственно ограничивает область его применения. В качестве альтернативы методу TNV предлагается новый метод: -12 профилирование конкретных значений выражений. Данный метод поз воляет собирать статистику не о всех значениях, принимаемых выра жением, а только о нескольких конкретных значениях. Так, например, если необходимо собрать статистику о том, как часто переменныеA,B,C принимают значения0или1, в инструментированную программу будет вставлен следующий код (непосредственно перед началом цикла): s t a t i c long long VP[27]; // инициализирован нулями VP[ 1*((A==0)+2*(A==1)) +3*((B==0)+2*(B==1)) +9*((C==0)+2*(C==1))]++; Непосредственно перед завершением программы значения элементов массиваVPзаписываются на диск это и есть профиль значений. Так, например, значениеVP[2+3*1+9*2]==VP[23]равно числу раз, когда пе ременныеA,BиCодновременно принимали значения1,0и1соответ ственно. На этапе использования полученного профиля перед компилятором стоит задача выбрать такую комбинацию значений инвариантных выра жений, для которой: а) вероятность появления высока (исходя из про филя значений) и б) замена выражений на соответственные значения существенно упростит тело цикла. Для оценки выигрыша, получаемого в результате специализации цик ла, используется следующее уравнение: Benefit() = Freq()Iter(L)(Cost(B) - Cost(B)) - Cost() (в нашем примере: это условиеA==1&&B==0&&C==1, Freq() вероят VP[23] ность истинности этого условия ( VP[i]), Iter(L) среднее количе i=0, ство итераций цикла, B и B оригинальное и упрощенное тело цикла, Cost(x) стоимость выполнения участка кода x, Benefit() выигрыш от применения специализации кода по условию ). В конце главы приводятся результаты применения профилирования значений и специализации кода к тестам пакета SPEC CPU2000. Полу ченный прирост производительности составил до 10% на одном из тестов (см. рис. 2). -13 Рис. 2. Прирост производительности Проведенные эксперименты позволяют сделать следующие выводы: Х Предложенный метод профилирования значений существенно бы стрее метода TNV (инструментированные программы замедляются менее чем на 10%). Х Предложенный метод позволяет дополнительно собирать инфор мацию о взаимосвязи значений нескольких выражений, что дает возможность проводить специализацию кода сразу для нескольких переменных (или выражений). В заключении коротко излагаются полученные практические и те оретические результаты. В приложении дается краткое описание внутренней структуры ком пилятора фирмы Sun и показывается расположение реализованных оп -14 тимизаций в этом компиляторе. Все рассмотренные трансформации реа лизованы в модуле iropt, отвечающем за высокоуровневые оптимизации программ (см. рис. 3). Рис. 3. Структура оптимизирующего компилятора Sun -15 Выводы 1. Разработаны новые алгоритмы идентификации и символьного ана лиза индуктивных переменных и выражений, а также управляю щей переменной. На основе данных алгоритмов разработаны алго ритмы оптимизации: подстановка индуктивных переменных и сни жение стоимости индуктивных выражений. Новые алгоритмы позволяют: Х обрабатывать индуктивные переменные с несколькими при сваиваниями; Х учитывать взаимосвязь между различными индуктивными переменными; Х анализировать и оптимизировать операторы преобразования типов, примененные к индуктивным переменным и выраже ниям; Х трансформировать операторы деления индуктивного выраже ния на константу. 2. Проведен детальный анализ проблем, возникающих в программах на языках Си и Си++, и связанных с нестандартными способами описания управляющей переменной. Предложен механизм реше ния этих проблем с применением специализации кода. Рассмотрены следующие случаи и их комбинации: Х использование управляющей переменной, имеющей беззнако вый целый тип; Х использование оператора!=вместо оператора<в условии за вершения цикла; Х использование оператора постинкремента в условии заверше ния цикла; Х использование глобальной переменной (или оператора считы вания из памяти) в качестве верхней границы цикла. -16 3. Разработан метод быстрого профилирования конкретных значений выражений, учитывающий взаимозависимость значений несколь ких различных выражений. На основе этого метода разработан ме ханизм специализации кода по профилю значений. 4. Показано, что исследованные методы оптимизации, использующие специализацию циклов, являются УагрессивнымиФ, т. е. в некото рых случаях могут ухудшить производительность. Однако, про веденные эксперименты доказали, что использование адекватных тренировочных данных при многофазной схеме компиляции обес печивает отсутствие отрицательного результата. 5. Все исследованные методы анализа и оптимизации циклов реали зованы в оптимизирующем компиляторе для платформы SPARC, что является важным практическим результатом работы. 6. Все предложенные методы оптимизации являются универсальны ми, т. е. не привязаны к конкретной архитектуре, конкретному ком пилятору или набору тестовых задач. 7. Реализованные оптимизации позволяют существенно повысить производительность реальных программ. На программах тестово го набора SPEC CPU2000 был получен прирост производительности до 12%. -17 Публикации по теме диссертации 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. С. 22 - 29. 6. К. С. Серебряный. Нормализация структуры циклов // XXX Гага ринские чтения. Международная молодежная научная конферен ция. Тезисы докладов Т. 5, М.: 2004. С. 56.