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

УДК 004.051 На правах рукописи

I г

I

I

Баскаков Юрий Валерьевич

ОБЕСПЕЧЕНИЕ ПОДДЕРЖКИ ПРОЦЕССА ПОВЫШЕНИЯ ПРОИЗВОДИТЕЛЬНОСТИ КОМПИЛЯТОРОВ ДЛЯ АРХИТЕКТУР С ЯВНО ВЫРАЖЕННОЙ ПАРАЛЛЕЛЬНОСТЬЮ ПРИ ИХ СОВМЕСТНОЙ РАЗРАБОТКЕ

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

Автореферат

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

Москва - 2005

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

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

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

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

Сухомлин Владимир Александрович

Защита состоится «_/£_» декабря 2005 г. в ¿5" ч. СО мин, на заседании диссертационного совета Д 002.043.01 при Институте микропроцессорных вычислительных систем РАН по адресу: 117997, ГСП-7, г. Москва, Нахимовский проспект, д. 36, корп. 1.

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

Автореферат разослан «22» октября 2005 г.

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

кандидат технических наук Дроздов Александр Юльевич

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

программирования РАН

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

21\17М

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

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

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

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

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

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

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

РОС. НАЦИОЯАЛЬНА,

РОС. НАЦИС......-

БИБЛИОТЕКА^ 1 С. Петер 09

1ИОТЫЧ'» .

сложности и не могут масштабироваться до бесконечности для поддержания темпов роста производительности, к которым привыкло современное общество. Одним из путей к преодолению данного ограничения является перенос основных интеллектуальных функций аппаратуры на уровень программного обеспечения. Этот подход лежит в основе так называемых архитектур с явно выраженной параллельностью (Explicitly Parallel Instruction Computing, EPIC).

Производительность архитектур с явно выраженной параллельностью (далее, для краткости, EPIC-архитектур) сильно зависит от возможностей компилятора оптимальным образом распределять аппаратные ресурсы статически. Учитывая тот факт, что величина значения тактовой частоты и параллелизм уровня команд являются антагонистичными свойствами, коммерческий успех архитектуры в целом определяется качеством оптимизационных возможностей компилятора, что наглядно демонстрируется на примере архитектуры Itanium / Itanium 2. Действительно, на начальном этапе, отсутствие приемлемого компилятора являлось серьезным сдерживающим фактором продвижения данной архитектуры на рынок.

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

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

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

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

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

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

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

■ разработать комплексный подход к проблеме повышения производительности компиляторов, затрагивающий все значимые аспекты технологического цикла данного процесса и пригодный к использованию в условиях разработки ЕР1С -компилятора для новой архитектуры;

■ реализовать предложенный подход в виде комплекса программных средств и технологий.

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

■ технология повышения производительности компиляторов;

■ методы выявления наиболее приоритетных направлений развития компилятора;

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

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

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

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

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

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

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

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

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

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

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

Практическая ценность результатов диссертации состоит в том, что все предложенные в работе методы и технологии были использованы для обеспечения поддержки процесса повышения производительности оптимизирующего компилятора для архитектуры «Эльбрус 2000», разработанной в ЗАО МЦСТ. В частности, на основе исследований, выполненных по теме диссертации, были достигнуты следующие практические результаты:

■ Реализована автоматизированная система оперативного контроля деградаций.

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

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

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

■ Множество тестовых примеров, построенное для осуществления оперативного контроля, было также использовано в качестве основы для проведения базовых настроек компилятора для архитектуры «Эльбрус 2000» при его портировании на архитектуру Itanium 2.

Апробация

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

■ на научно-технической конференции «Развитие и внедрение в системах РКО перспективной вычислительной техники и новых вычислительных технологий», Москва, 2003;

■ на IX Санкт-Петербургской международной конференции «Региональная информатика - 2004», Санкт-Петербург, 2004;

■ на 1-ой Международной научно-практической конференции «Современные информационные технологии и ИТ-образование», Москва, 2005 г;

■ на научно-технических семинарах ЗАО МЦСТ и ИМВС РАН. Публикации

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

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

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

диссертации составляет 149 страниц текста. Диссертация содержит 7 таблиц и 43 рисунка.

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

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

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

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

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

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

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

б

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

В разделе 1.2.2 перечислены основные причины построения компилятором неоптимального кода.

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

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

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

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

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

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

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

Раздел 1.2.8 посвящен проблеме выбора приоритета для формулируемых предложений. Поскольку в ходе анализа производительности может обнаруживаться большое количество неоптимальностей, значимость которых сразу неочевидна (что особенно характерно для ЕР1С-архитектур), было предложено разделение архива предложений на два уровня - временный и основной. До тех пор, пока значимость предложения не доказана, последнее содержится во временном архиве и является невидимым для коллектива разработчиков. Также рассмотрены свойства предложений, которые могут учитываться при выборе приоритета.

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

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

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

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

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

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

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

В разделе 1.4.1 представлены детали реализации подхода к анализу производительности, применявшегося в рамках процесса разработки оптимизирующего компилятора для архитектуры «Эльбрус 2000». В

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

В разделе 1.4.2 представлены детали реализации процесса контроля деградаций, используемого в рамках процесса разработки оптимизирующего компилятора для архитектуры «Эльбрус 2000». Среди особенностей процесса разработки указываются: высокая интенсивность внесения изменений в архив проекта (в среднем, 19 за сутки при максимуме 36), высокий риск возникновения деградаций (р>0.3) и ведение работ при отсутствии готового процессора. В данных условиях предложено разделение контроля деградаций на оперативную и регулярную составляющие. В задачи первой входит базовый контроль при каждой модификации. Вторая же составляющая призвана обеспечить более обстоятельную проверку с заданным уровнем периодичности.

В качестве основных результатов главы 1, представленных в разделе 1.5, приводятся данные об ускорениях компилятора для архитектуры «Эльбрус 2000» на задачах из пакетов 8РЕС92 и 8РЕС95, достигнутые за год с момента начала использования предложенной в диссертационной работе методики. Так, среднее геометрическое ускорение по задачам из пакета 8РЕСш$2 составило 2.13 (рис.1.1), а по задачам из пакета БРЕС1р92 - 4.88 (рис. 1.2). При этом было отработано 565 предложений, из которых 453 являются результатом анализа производительности на задачах, а 112 получено в ходе исследования оптимизаций.

Рис. 1.1 Ускорение на задачах из пакета 5РЕСШ92 за рассматриваемый период

Рис.1.2. Ускорение на задачах из пакета 5РЕС/р92 за рассматриваемый период

Задачи из пакета БРЕС95 не участвовали в анализе. Первые замеры показателей производительности для целочисленных задач (БРЕСт195) и задач с плавающей точкой (5РЕСф95) из пакета БРЕС95 были сделаны приблизительно через 4 и 9 месяцев соответственно после начала анализа производительности для задач из пакета БРЕС92. За 8 месяцев

наблюдений, целочисленные задачи ускорились в среднем в 2 раза (рис. 1.3). Ускорение на задачах с плавающей точкой за 3 месяца наблюдений составило 1.46 раза (рис. 1.4).

Рис.1.3 Ускорение на задачах из Рис.1.4. Ускорение на задачах из пакета БРЕСт&З пакета БРЕфЯЗ

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

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

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

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

относительных метрик деградаций. Индивидуальные метрики позволяют поставить в соответствие отдельно взятой программе Р числовое значение, выражающее прогресс или ухудшение метрической характеристики ц5 на этой программе при переходе компилятора из «старого» состояния 5„ в «новое» состояние 5„. Интегральные метрики ставят числовое значение в соответствие целому множеству программ £2. Относительные метрики показывают процентное изменение измеряемой величины, в то время как абсотютные оперируют понятием разности и хорошо подходят для характеристик с небольшим дискретным диапазоном значений.

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

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

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

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

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

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

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

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

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

Раздел 2.5 посвящен реализации системы контроля деградаций в рамках проекта по созданию оптимизирующего компилятора для архитектуры «Эльбрус 2000». Характерными особенностями процесса разработки компилятора являлись: высокая частота внесения изменений в архив проекта, высокий риск возникновения деградаций, а также ведение работ при наличии лишь программной модели процессора. В разделе 2.5.1 рассмотрены основные положения выбранной методики контроля. В частности, процесс контроля деградаций был разделен на оперативную и регулярную составляющие, а для обеспечения оперативности использовались метод оценки по времени выполнения наиболее значимых фрагментов и метод оценки по фактам применения оптимизаций. Раздел 2.5.2 посвящен стратегии контроля деградаций - т.е. описано в какие момента времени этот контроль производится и какие методы при этом используются. В разделе 2.5.3 рассмотрены детали реализации методов оперативной оценки для задач из пакетов SPEC92 и SPEC95. В частности, в результате реализации метода оценки по времени выполнения наиболее значимых фрагментов был построен тестовый комплект specperf, состоящий из 121 тестового примера общим объемом 2,78МЬ. Для этого же множества задач при реализации метода оценки по фактам применения оптимизаций было выделено 1800 эталонных срабатываний (812 для задач из пакета SPEC92 и 988 для задач из пакета SPEC95). Также в данном разделе рассмотрены структура тестового окружения и структура тестовых примеров из пакета specperf. Кроме того, описаны форматы событий срабатывания и шаблонов, задающих ожидаемые срабатывания в контрольных точках. В разделе 2.5.4 рассмотрена структура системы контроля деградаций.

В качестве основных практических результатов главы 2, в разделе 2.6 приводится статистика об эффективности системы контроля деградаций, реализованной в рамках проекта по созданию оптимизирующего компилятора для архитектуры «Эльбрус 2000» в соответствии с предложенной в данной главе методикой. Так, система контроля признавала недопустимыми до 30% от общего числа вносимых в компилятор модификаций. При этом, отказ от контроля приводил бы к -3% деградации усредненного показателя производительности для пакетов SPEC92 и SPEC95 за месяц.

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

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

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

Раздел 3.3 посвящен системе тестирования ОСТеТ, разработанной в рамках проекта по созданию оптимизирующего компилятора для архитектуры «Эльбрус 2000».

В разделе 3.3.1 изложены особенности архитектуры «Эльбрус 2000», которые оказывают влияние на способ построения тестов и определяют выбор метода тестирования.

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

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

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

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

В разделе 3.3.4 рассмотрен пример проектирования тестовой спецификации для оптимизации Loop Fusion.

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

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

В состав системы ОСТеТ вошло 1928 самопроверяющихся тестов общим объемом ~4.5МЬ для 22 оптимизирующих преобразований. В частности, были затронуты 12 потоковых и цикловых оптимизаций, не меняющих структуру управления, 9 цикловых макрооптимизаций и 1 структурное нецикловое преобразование.

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

Построенная в соответствии с разработанной автором методологией, система ОСТеТ была успешно применена не только для исследования оптимизационных возможностей компилятора для архитектуры «Эльбрус 2000», но и для тестирования промышленного компилятора фирмы Intel для архитектуры Itanium 2. В последнем случае было выявлено 898 фактов несрабатывания оптимизаций в благоприятных контекстах.

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

В приложении приводятся примеры тестов из пакетов specperf и ОСТеТ, вместе с окружениями тестирования, представлены данные о результатах масштабирования задач из пакета SPEC95, а также приводятся примеры профилей системы принятия решений.

Выводы по результатам диссертации

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

■ архитектура предоставляет компилятору большие возможности по оптимизации, что подразумевает:

- существование множества альтернативных направлений для дальнейшего развития;

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

- высокая интенсивность внесения изменений в архив проекта;

- высокий риск возникновения деградаций;

■ ведение работ при отсутствии готового процессора.

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

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

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

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

■ Разработана методика поиска неоптимальностей на отдельном приложении.

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

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

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

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

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

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

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

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

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

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

■ На примере архитектуры «Эльбрус 2000» проведено исследование возможностей по выявлению дефектов оптимизаций в случае использования двухрежимного подхода в контексте ЕР1С-архитектур.

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

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

4. Осуществлено практическое воплощение предложенных методик в

виде комплекса средств и технологий:

■ Разработана автоматизированная система оперативного контроля деградаций.

■ Построено множество тестовых примеров, необходимое для осуществления оперативного контроля (для задач из пакетов 5РЕС92 и 8РЕС95 выделен 121 пример общим объемом 2,78МЪ).

■ Выделено множество наиболее значимых случаев применения оптимизаций, используемое для нужд оперативного контроля (1800 эталонных срабатываний - 812 для задач из пакета БРЕС92 и 988 для задач из пакета 8РЕС95).

■ Спроектирован и реализован тестовый комплект, предназначенный для исследования оптимизаций (тесты для 22 оптимизаций общим числом 1928 пггук, занимаемое место на диске ~4.5МЬ).

Все предложенные методы и средства составляют основу процесса повышения производительности оптимизирующего компилятора для архитектуры «Эльбрус 2000», разработанной в ЗАО МЦСТ. За год применения данная технология позволила получить среднее ускорение в 2.13 и 4.88 раз на задачах из пакетов 8РЕСпЛ92 и 8РЕС£р92 соответственно.

Список работ, опубликованных по теме диссертации

1. Баскаков Ю.В., Волконский В.Ю., Грабежной A.B., Нейман-заде М.И., Чернова Е.Ю. Методика анализа производительности компиляторов для архитектур с явной параллельностью // Компьютеры в учебном процессе, N11, с. 23-38,2005.

2. Баскаков Ю.В. Об организации контроля деградаций показателей производительности компилятора на этапе разработки // Высокопроизводительные вычислительные системы и микропроцессоры, сборник научных трудов ИМВС РАН, N8, с. 25-33, 2005.

3. Архангельская Е.Ю., Баскаков Ю.В., Серебряная H.H., Тарасенко Л.Г. Принципы построения тестов для исследования оптимизационных возможностей компиляторов для архитектур с явной параллельностью // Высокопроизводительные вычислительные системы и микропроцессоры, сборник научных трудов ИМВС РАН, N8, с. 9-24,2005.

4. Баскаков Ю.В., Волконский В.Ю., Грабежной A.B. Оценка влияния модификаций компилятора на быстродействие целевого кода // Информационные технологии и вычислительные системы, N3, с. 111-119, 2005.

5. Баскаков Ю.В. Об одном подходе к организации оперативного контроля деградаций показателей производительности компилятора на множестве приложений // 1-я Международная научно-практическая конференция «Современные информационные технологии и ИТ-образование», Москва, 2005. Сборник трудов, с. 355-364.

6. Архангельская Е.Ю., Баскаков Ю.В., Грабежной A.B., Серебряная H.H., Тарасенко Л.Г. ОСТеТ: система для исследования оптимизационных возможностей компиляторов // Высокопроизводительные вычислительные системы и микропроцессоры, сборник научных трудов ИМВС РАН, N7, с. 311,2004.

7. Баскаков Ю.В., Волконский В.Ю., Грабежной A.B., Нейман-заде М.И., Тарасенко Л.Г. Поддержка процесса повышения производительности компиляторов // Информационные технологии и вычислительные системы, N3, с. 78-92,2004.

8. Баскаков Ю.В., Грабежной A.B., Лаврешников A.A., Рогов Р.Ю., Тарасенко Л.Г., Чернова Е.Ю. Вопросы организации системы обеспечения качества оптимизирующих компиляторов // Высокопроизводительные вычислительные системы и микропроцессоры, сборник научных трудов ИМВС РАН, N6, с. 77-85, 2004.

9. Баскаков Ю.В. Поддержка процесса повышения производительности // IX Санкт-Петербургская международная конференция «Региональная информатика - 2004», Санкт-Петербург, 2004. Тезисы докладов.

10. Баскаков Ю.В. Об одном методе оперативного контроля эффективности целевого кода при разработке оптимизирующего компилятора // Научно-техническая конференция «Развитие и внедрение в системах РКО перспективной вычислительной техники и новых вычислительных технологий», Москва, 2003. Тезисы докладов.

Принято к исполнению 21/10/2003 Исполнено 21/10/2005

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

ООО «11-й ФОРМАТ» ИНН 7726330900 Москва, Варшавское ш., 36 (095)975-78-56 (095)747-64-70 ту\у>у.аи1оге&гаЦц

»21139

РНБ Русский фонд

2006-4 22588

Введение.

1. Технология повышения производительности компиляторов.

1.1 Тестовая база.

1.2 Анализ производительности.

1.2.1 Требования к поиску неоптимальностей и системе приоритетов.

1.2.2 Причины неоптимальностей.

1.2.3 Подходы к выявлению неоптимальностей.

1.2.4 Структурная модель анализа.

1.2.5 Классификация предложений и порядок поиска неоптимальностей.

1.2.6 Анализ производительности на отдельной задаче.

1.2.7 Оценки и предсказания.

1.2.7.1 Оценка эффекта от реализации выработанных предложений.

1.2.7.2 Предсказание пиковой производительности на задаче.

1.2.8 Система приоритетов предложений.

1.3 Контроль деградаций.

1.3.1 Общая постановка задачи (модель).

1.3.2 Виды деградаций.

1.3.3 Подходы к контролю деградаций.

1.3.4 Частота замеров показателей производительности.

1.4 Реализация технологии повышения производительности.

1.4.1 Реализация процесса анализа производительности.

1.4.2 Реализация процесса контроля деградаций.

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

1.6 Выводы.

2 Система контроля деградаций.

2.1 Метрические характеристики производительности.

2.2 Метрики деградаций.

2.3 Требования к выбору значений порога деградации.

2.4 Методы оценки эффекта модификаций на производительность.

2.4.1 Оперативная оценка общего времени выполнения.

2.4.2 Альтернативные подходы к обеспечению оперативности методов оценки.

2.4.2.1 Метод оценки по времени выполнения наиболее значимых фрагментов.

2.4.2.2 Метод оценки по фактам применения оптимизаций.

2.5 Реализация системы контроля деградаций.

2.5.1 Основные положения методики контроля (проектные решения).

2.5.2 Стратегия контроля.

2.5.3 Реализация методов оперативной оценки.

2.5.4 Структура системы контроля деградаций.

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

2.7 Выводы.

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

3.1 Требования к тестовому комплекту.

3.2 Подходы к тестированию оптимизаций.

3.3 Особенности реализации системы тестирования ОСТеТ.

3.3.1 Специфика окружения.

3.3.2 Метод тестирования и критерий полноты.

3.3.3 Спецификация метода тестирования.

3.3.4 Пример проектирования спецификации для оптимизации Loop

Fusion.

3.3.5 Принципы построения тестов.

3.3.6 Структура тестов.

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

3.5 Выводы.

Актуальность темы. При промышленной разработке систем информационных технологий к эффективности1 конечного продукта традиционно предъявляются высокие требования. Не исключением являются и компиляторы. Как отмечается в [RHD98], эффективность компиляторов имеет две составляющие. Одна из них характеризует этап компиляции и затрагивает такие его аспекты как, например, скорость компиляции и объем выделяемой в процессе компиляции динамической памяти. Другая же относится к качеству генерируемого компилятором кода и определяется временем его выполнения и/или его размером. Такое разделение выбрано неслучайно - время компиляции и затрачиваемая при этом память важны для разработчиков приложений, в то время как быстродействие и компактность кода представляют интерес с точки зрения их конечного пользователя.

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

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

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

1 Одно из определений понятия эффективности можно найти, например, в [ББКЛММ81]: программный продукт обладает свойством эффективности, если он выполняет требуемые функции без излишних затрат ресурсов, где ресурсы понимаются в широком смысле.

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

Кроме того, как показывает практика [RHD98], [БВГНТ04], при разработке компилятора приемлемого уровня быстродействия целевого кода можно добиться лишь в результате непрерывного контроля текущего состояния производительности. Действительно, любые модификации исходного кода компилятора, будь то исправление ошибок или расширение функциональности, являются потенциальными источниками деградации достигнутых показателей быстродействия.

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

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

Проблема разработки высокопроизводительных оптимизирующих компиляторов становится еще более актуальной в свете современных тенденций развития вычислительной техники. Традиционные суперскаляры, реализующие динамический подход к распараллеливанию вычислений, практически достигли предельного уровня аппаратной сложности и не могут масштабироваться до бесконечности для поддержания темпов роста производительности, к которым привыкло современное общество [LeVa03]. Одним из путей к преодолению данного ограничения является перенос основных интеллектуальных функций аппаратуры на уровень программного обеспечения. Этот подход лежит в основе так называемых архитектур с явно выраженным параллелизмом на уровне команд (Explicitly Parallel Instruction Computing, EPIC).

Производительность архитектур с явно выраженным параллелизмом (далее, для краткости, EPIC-архитектур) сильно зависит от возможностей компилятора оптимальным образом распределять аппаратные ресурсы статически [ACMS98]. Учитывая тот факт, что величина значения тактовой частоты и параллелизм уровня команд являются антагонистичными свойствами [АНКВОО], коммерческий успех архитектуры в целом определяется качеством оптимизационных возможностей компилятора, что наглядно демонстрируется на примере архитектуры Itanium / Itanium 2. Действительно, на начальном этапе отсутствие приемлемого компилятора являлось серьезным сдерживающим фактором продвижения данной архитектуры на рынок.

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

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

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

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

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

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

Методы исследования заимствованы из областей системного программирования, проектирования, технологии компиляции, аттестационного тестирования, системного анализа, математической статистики, теории алгоритмов. Эффективность предложенных решений оценивалась в рамках процесса разработки оптимизирующего компилятора для архитектуры «Эльбрус 2000». Показателем эффективности являлась динамика изменения показателей производительности компилятора на задачах из пакета SPEC [SPEC].

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

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

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

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

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

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

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

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

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

Практическая ценность результатов диссертации состоит в том, что все предложенные в работе методы и технологии были использованы для обеспечения поддержки процесса повышения производительности оптимизирующего компилятора для архитектуры «Эльбрус 2000» [Diefendorf99], [Кузьминский99], [BabayanOO], разработанной в ЗАО МЦСТ. В частности, на основе исследований, выполненных по теме диссертации, были достигнуты следующие практические результаты:

Разработана автоматизированная система оперативного контроля деградаций.

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

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

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

Множество тестовых примеров, построенное для осуществления оперативного контроля, было также использовано в качестве основы для проведения базовых настроек компилятора для архитектуры «Эльбрус 2000» при его портировании на архитектуру Itanium 2 [ItaniumRM].

Результаты работы

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

Исследована проблема повышения производительности компиляторов.

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

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

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

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

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

Осуществлено практическое воплощение предложенных идей в виде комплекса программных средств и технологий.

Публикации

По теме диссертации опубликовано 10 печатных работ:

1. Ю.В. Баскаков, В.Ю. Волконский, А.В. Грабежной, М.И. Нейман-заде, Е.Ю. Чернова. Методика анализа производительности компиляторов для архитектур с явной параллельностью // Компьютеры в учебном процессе, N11, с. 23-38, 2005.

2. Ю.В. Баскаков. Об организации контроля деградаций показателей производительности компилятора на этапе разработки // Высокопроизводительные вычислительные системы и микропроцессоры, сборник научных трудов ИМВС РАН, N8, с. 25-33, 2005.

3. Е.Ю. Архангельская, Ю.В. Баскаков, Н.Н. Серебряная, Л.Г. Тарасенко. Принципы построения тестов для исследования оптимизационных возможностей компиляторов для архитектур с явной параллельностью // Высокопроизводительные вычислительные системы и микропроцессоры, сборник научных трудов ИМВС РАН, N8, с. 9-24, 2005.

4. Ю.В. Баскаков, В.Ю. Волконский, А.В. Грабежной. Оценка влияния модификаций компилятора на быстродействие целевого кода // Информационные технологии и вычислительные системы, N3, с. 111-119, 2005.

5. Ю.В. Баскаков. Об одном подходе к организации оперативного контроля деградаций показателей производительности компилятора на множестве приложений // 1-я Международная научно-практическая конференция «Современные информационные технологии и ИТ-образование», Москва, 2005. Сборник трудов, с. 355-364.

6. Е.Ю. Архангельская, Ю.В. Баскаков, А.В. Грабежной, Н.Н. Серебряная, Л.Г. Тарасенко. ОСТеТ: система для исследования оптимизационных возможностей компиляторов // Высокопроизводительные вычислительные системы и микропроцессоры, сборник научных трудов ИМВС РАН, N7, с. 3-11, 2004.

7. Ю.В. Баскаков, В.Ю. Волконский, А.В. Грабежной, М.И. Нейман-заде, Л.Г. Тарасенко. Поддержка процесса повышения производительности компиляторов // Информационные технологии и вычислительные системы, N3, с. 78-92, 2004.

8. Ю.В. Баскаков, А.В. Грабежной, А.А. Лаврешников, Р.Ю. Рогов , Л.Г. Тарасенко, Е.Ю. Чернова. Вопросы организации системы обеспечения качества оптимизирующих компиляторов // Высокопроизводительные вычислительные системы и микропроцессоры, сборник научных трудов ИМВС РАН, N6, с. 77-85, 2004.

9. Ю.В. Баскаков. Поддержка процесса повышения производительности // IX Санкт-Петербургская международная конференция «Региональная информатика - 2004», Санкт-Петербург, 2004.

10. Ю.В. Баскаков Об одном методе оперативного контроля эффективности целевого кода при разработке оптимизирующего компилятора // Научно-техническая конференция «Развитие и внедрение в системах РКО перспективной вычислительной техники и новых вычислительных технологий», Москва, 2003.

Апробация

Результаты, полученные в работе, изложены в ряде печатных публикаций, докладывались на научных конференциях и семинарах, в частности: на научно-технической конференции «Развитие и внедрение в системах РКО перспективной вычислительной техники и новых вычислительных технологий», Москва, 2003; на IX Санкт-Петербургской международной конференции «Региональная информатика - 2004», Санкт-Петербург, 2004; на 1-ой Международной научно-практической конференции «Современные информационные технологии и ИТ-образование», Москва, 2005 г; на научно-технических семинарах ЗАО МЦСТ и ИМВС РАН.

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

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

3.5 Выводы

В данной главе были затронуты проблемы тестирования оптимизирующих преобразований. В частности, рассмотрена система ОСТеТ, разработанная для исследования пространства оптимизаций в контексте архитектуры «Эльбрус 2000» и осуществляющая их тестирование посредством изоляции функциональности последних.

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

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

Кроме того, на примере архитектуры «Эльбрус 2000» проведено исследование возможностей по выявлению дефектов оптимизаций в случае использования двухрежимного подхода в контексте EPIC-архитектур. Для каждого класса оптимизаций подробно рассмотрены разработанные автором принципы построения тестов, обеспечивающие наблюдаемое проявление эффекта от применения заданного преобразования. Также предложена структура тестов и разработана политика их взаимодействия с тестовым окружением. Для поддержки реализации преобразований, результат работы которых зависит от профильной информации, разработан механизм достижения заданного распределения вероятностей прохождения путей программы.

Построенная в соответствии с разработанной автором методологией, система ОСТеТ, включающая тесты для 22 оптимизаций общим числом 1928 штук, была успешно применена не только для исследования оптимизационных возможностей компилятора для архитектуры «Эльбрус 2000», но и для тестирования промышленного компилятора фирмы Intel для архитектуры Itanium 2. В последнем случае было выявлено 898 фактов несрабатывания оптимизаций в благоприятных контекстах.

Что касается результатов использования системы ОСТеТ в рамках процесса повышения производительности компилятора для архитектуры «Эльбрус 2000», то было выявлено и устранено 192 различных случая неприменения оптимизаций в благоприятных контекстах, а также 105 случаев нарушения работоспособности программ. При этом, был обнаружен ряд ошибок взаимодействия оптимизаций. Для текущего состояния компилятора системой ОСТеТ зафиксировано 527 фактов несрабатывания оптимизаций.

Заключение

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

- существование множества альтернативных направлений для дальнейшего развития;

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

- высокая интенсивность внесения изменений в архив проекта;

- высокий риск возникновения деградаций; ведение работ при отсутствии готового процессора.

В ходе решения поставленных задач были достигнуты следующие научные результаты:

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

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

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

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

1. АНКВОО. V. Agarwal, М. Hrishikesh, S. Keckler, D. Burger. Clock Rate versus IPC: The End of the Road for Conventional Microarchitectures. ACM, pp. 248-259, 2000

2. AKPW83. J.R. Allen, K. Kennedy, C. Porterfield, J. Warren. Conversion of Control Dependence to Data Dependence. In Proceedings of the 10th Annual ACM Symposium on the Principles of Programming Languages, pp. 177-189, 1983

3. BabayanOO. B. Babayan. E2K Technology and Implementation, in Proceedings of the 6th International Euro-Par Conference, Lecture Notes in Computer Science, Springer, vol. 1900, pp. 18-21, August 2000

4. BGS94. D. Bacon, S. Graham, O. Sharp. Compiler Transformations for High-Performance Computing. ACM Computing Surveys, 26 (4), pp. 345-420, 1994

5. BFG85. M. Bassman, G. Fisher, A. Gargaro. An Approach for Evaluating the Performance Efficiency of ADA Compilers, 1985

6. Beizer83. B. Beizer. Software System Testing and Quality Assurance. N.Y., Van Nostrand Reinhold, 1983

7. BCM94. D. Bernstein, D. Cohen, D. Maydan. Dynamic Memory Disambiguation for Array References. In Proceedings of the 27th Annual International Symposium on Microarchitecture, pp. 105-111, 1994.

8. CaKe94. S. Carr, K. Kennedy. Improving the Ratio of Memory Operations to Floating-Point Operations in Loops. ACM Transactions on Programming Languages and Systems, 16 (6), pp. 1768-1810, 1994

9. Cascaval99. C. Cascaval, L. DeRose, D. Padua, D. Reed. Compile-time Based Performance Prediction. Lecture Notes in Computer Science, Springer Verlag, 1999

10. CascavalOO. C. Cascaval. Compile-time Performance Prediction of Scientific Programs. PhD Thesis, University of Illinois at Urbana-Champaign, 2000

11. СаРаОЗ. С. Cascaval, D. Padua. Estimating Cache Misses and Locality Using Stack Distances. In Proceedings of ICS'03, pp. 150-159, 2003

12. Diefendorf99. K. Diefendorf. The Russians Are Coming: Supercomputer Maker Elbrus Seeks to Join x86/IA-64 Melee. Microprocessor report, vol. 2, no. 2, pp. 7-11, 1999

13. Eigenmann93. R. Eigenmann. Toward a Methodology of Optimizing Programs for High-Performance Computing. In Proceedings of the 7th International Conference on Supercomputing, pp. 27-36, 1993

14. FlWa86. P. Fleming, J. Wallace. How not to Lie with Statistics: the Correct Way to Summarize Benchmark Results. Communications of the ACM, vol. 29, no.3, pp. 218-221, March 1986

15. GKK82. S. Graham, P. Kessler, M. McKusick. gprof: A Call Graph Execution Profiler. In SIGPLAN Symposium on Compiler Construction, pp. 120-126, June 1982

16. HHR95. R. Hank, W. Hwu, B. Rau. Region-Based Compilation: An Introduction and Motivation. In Proceedings of the 28th Annual International Symposium on Microarchitecture, Micro-28, pp. 158168, December 1995

17. НеРаОЗ. J. Hennessy, D. Patterson. Computer Architecture: A Quantitative Approach. Morgan Kaufmann Publishers, San Francisco, Third Edition, 2003

18. JCNWLZ02. R. Ju, S. Chan, T.-F. Ngai, C. Wu, Yu. Lu, J. Zhang. Open Research Compiler (ORC) 2.0 and Tuning Performance on Itanium. Micro-35 Tutorial, 2002

19. KlLi02. AJ KleinOsowski, D. Lilja. MinneSPEC: A New SPEC Benchmark Workload for Simulation-Based Computer Architecture Research. Computer Architecture Letters, vol.1, May 2002

20. KRS92. J. Knoop, O. Ruthing, B. Steffen. Lazy Code Motion. ACM

21. SIGPLAN Notices, 27(7), pp.224-234, 1992

22. AmOO. S. Larsen, S. Amarasinghe. Exploiting Superword Parallelism with Multimedia Instruction Set. PLDI 2000, Vancouver, British Columbia, Canada

23. Va03. M. Len, I. Vaitsman. VLIW: Old Architectures of the New Generation, http://www.digit-life.com

24. St98. E. Limpert, W. Stahel. Life is Log-normal! Science and Art, Life and Statistics. ETH Zurich, 1998

25. W99. Y.-T. Li, S. Malik, A. Wolfe. Performance Estimation of Embedded Software with Instruction Cache Modeling. Design Automation of Electronic Systems, vol. 4, no. 3, pp. 257-279, 1999

26. Mashey04. J. Mashey. War of the Benchmark Means: Time for a Truce. ACM SIGARCH Computer Architecture News, vol. 32, no. 4, pp. 1-14, September 2004

27. MCT96. K. McKinley, S. Carr, C. Tseng. Improving Data Locality with Loop Transformations. ACM Transactions on Programming Languages and Systems, vol. 18, no. 4, pp. 424-453, 1996

28. McMahon88. F. McMahon. The Livermore Fortran Kernels Test of the Numerical Performance Range. Performance Evaluation of Supercomputers, pp. 143-185, Elsevier Science Publishers B.V., 1988

29. MGST70. R. Mattson, J. Gecsei, D. Slutz, I. Traiger. Evaluation Techniques for Storage Hierarchies. IBM Systems Journal, 9(2), 1970

30. Muchnick97. S. Muchnick. Advanced Compiler Design and Implementation. Morgan Kaufmann Publishers, 1997

31. MuWh95. F. Mueller, D. Whalley. Avoiding Conditional Branches by Code Replication. In Proceedings of the 1995 ACM SIGPLAN conference on Programming language design and implementation, 30(6), pp 5666

32. RHD98. H. Rotithor, K. Harris, M. Davis. Measurement and Analysis of С and С++ Performance. Digital Technical Journal, vol. 10, no. 1, pp. 32-47,1998

33. Sias05. J. Sias. A Systematic Approach to Delivering Instruction-Level Parallelism in EPIC Systems. PhD Thesis, University of Illinois at Urbana-Champaign, 2005

34. TVVA03. S. Triantafyllis, M. Vachharajani, N. Vachharajani, D. August.

35. Compiler Optimization-Space Exploration. In Proceedings of the International Symposium on Code Generation and Optimization: Feedback-directed and Runtime Optimization CGO'03, pp. 204-215, 2003

36. VoMa93. V. Volkonsky, D. Maslennikov. Compiler Method and Apparatus for Elimination of Redundant Speculative Computations from Innermost Loops. US Patent, US 6301706 Bl, Oct.9, 2001

37. АБГСТ04. Е.Ю. Архангельская, Ю.В. Баскаков, A.B. Грабежной, Н.Н.

38. Серебряная, Л.Г. Тарасенко. ОСТеТ: система для исследования оптимизационных возможностей компиляторов. Высокопроизводительные вычислительные системы и микропроцессоры, сборник научных трудов ИМВС РАН, N7, с. 3-11, 2004

39. АСУ01. А. Ахо, Р. Сети, Дж. Ульман. Компиляторы принципы, технологии, инструменты. - М.: Издательский дом «Вильяме», 2001

40. БГЛТРЧ04. Ю.В. Баскаков, А.В. Грабежной, А.А. Лаврешников, Р.Ю.

41. Рогов, Л.Г. Тарасенко, Е.Ю. Чернова. Вопросы организациисистемы обеспечения качества оптимизирующих компиляторов. Высокопроизводительные вычислительные системы и микропроцессоры, сборник научных трудов ИМВС РАН, N6, с. 77-85, 2004

42. БВГНТ04. Ю.В. Баскаков, В.Ю. Волконский, А.В. Грабежной, М.И.

43. Нейман-заде, Л.Г. Тарасенко. Поддержка процесса повышения производительности компиляторов. Информационные технологии и вычислительные системы, N3, с.78-92, 2004

44. ББКЛММ81. Б. Боэм, Дж. Браун, X. Каспар и др. Характеристики качества программного обеспечения. М.: Мир, 1981

45. ДрНо05. А.Ю. Дроздов, С.В. Новиков. Алгоритм формирования гиперблоков, 2005 (в печати)

46. ДрРо04. А.Ю. Дроздов, Е.В. Ровинский. Технология использования векторных операций для получения оптимального кода. Компьютеры в учебном процессе, N9, 2004

47. ДрСт04. А.Ю. Дроздов, А.М. Степаненков. Технология оптимизации цикловых участков процедур в компиляторах для архитектур с явно выраженной параллельностью. Информационные технологии и вычислительные системы, N3, с.52-62, 2004

48. КанерОО. С. Канер и др. Тестирование программного обеспечения. К.: ТИД «DiaSoft», 2000

49. Кауфман84. В.Ш. Кауфман. Стандартизация и контроль трансляторов.

50. Различные аспекты системного программирования. М.: Изд-во Моск. ун-та, с.47-85, 1984

51. Кузьминский99. М. Кузьминский. Отечественные микропроцессоры: Elbrus Е2К. Открытые системы, N05-06, с. 8-13, 1999

52. Кулаков84. А.Ф. Кулаков. Оценка качества программ ЭВМ. К.: Техшка, 1984

53. Лаврешников02. А.А. Лаврешников. Пакет для оперативной оценки производительности оптимизирующих компиляторов. Высокопроизводительные вычислительные системы и микропроцессоры, сборник научных трудов ИМВС РАН, 2002

54. Майерс80. Г. Майерс. Надежность программного обеспечения М.: Мир, 1980

55. Майерс82. Г. Майерс. Искусство тестирования программ. М.: Финансы и статистика, 1982

56. Сухомлин97. В. А. Сухомлин. Система программирования тройного стандарта (ЗС++). IV Международная конференция «Развитие и применение открытых систем». Сборник докладов, с. 37-47, Нижний Новгород, 1997

57. ФофановОО. В. А. Фофанов. Внешнее тестирование интерфейсных библиотек (на примере интерфейса ASIS). Диссертационная работа. Москва, 2000

58. Хамби76. Э. Хамби. Программирование таблиц решений. М.: Мир, 1976

59. ARCTIC. The Laboratory for Advanced Research in Computing Technology and Compilers, University of Minnesota -http ://w w w. arctic .umn.edu

60. Bench. Orost J., The Bench++ Benchmark Suitehttp://www.research.att.com/~orost/bench plus pi us/paper, html

61. Blitz. Blitz++ library http://www.oonumerics.org/blitz/

62. CVS. The Concurrent Versions System http://www.cvshome.org/

63. DEC. Digital Equipment Corporation http://www.dec.com

64. Fortran. ANSI X3.9-1978 FORTRAN 77

65. GPROF. GNU gprof http://ftp.gnu.Org/gnu/Manuals/gprof-2.9.l

66. PACT. The IMPACT Research Grouphttp://www.crhc. uiuc .edu/IMP ACT/1.tel. Intel, Inc http://www.intel.com1.aniumRM. Intel Itanium 2 Processor Reference Manual, Document Number: 251110-001, May 2004

67. Nullstone. Nullstone Corporation http://www.nullstone.com

68. POSIX. ISO/IEC JTC1/SC22 DIS 13210: 1996, Information Technology -Requirements and Guidelines for Test Methods Specifications and

69. Test Method Implementation for Measuring Conformance to POSIX Standard.

70. SPEC. Standard Performance Evaluation Corporation http://www.spec.org Sun] Sun Microsystems, Inc - http://www.sun.com