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

УДК 004.4'41б

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

Василец Павел Станиславович

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

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

Автореферат

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

Москва - 2006

Работа выполнена в Институте микропроцессорных вычислительных систем РАН и ЗАО "МЦСТ"

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

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

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

Семенихин Сергей Владимирович

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

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

Институт точной механики и вычислительной техники

Защита состоится «Щ » 2006 г. в /6 ч.£<?мин. на

заседании диссертационного совета Д 002.043.01 при Институте микропроцессорных вычислительных систем РАН по адресу: 117997, Москва, Нахимовский проспект 36, корпус 1

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

Автореферат разослан «....»................2006 г.

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

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

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

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

Актуальность

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

Одним из наиболее распространенных на сегодняшний день хпособов обеспечения параллельности остается применение аппаратных решений. Ярким примером такого решения могут служить целые поколения процессоров фирмы Intel (Pentium, Pentium Pro) с набором команд CISC (Complex Instruction Set Computing), представляющих собой суперскалярное ядро на базе RISC архитектуры и аппаратный перекодировщик из CISC в RISC инструкции ядра. В то же время данный способ приводит к дополнительным затратам оборудования, ухудшению физических характеристик, таких как размеры кристаллов и энергопотребление.

Обеспечение требуемой для современных задач параллельности можно достичь и путем существенных изменений микропроцессорных архитектур на хорошо зарекомендовавшую себя архитектуру VL1W (Very Long Instruction Word). Новые алгоритмы планирования и распределения ресурсов, реструктуризация управления позволяют получить значительный прирост производительности по сравнению с суперскалярными методами. Дополнительным преимуществом VLIW архитектуры является возможность эффективно применить к ней методы формальной верификации. Однако наряду с полученными преимуществами такие архитектуры приобрели и полную двоичную несовместимость с другими архитектурными решениями.

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

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

обладает рядом преимуществ по сравнению с аппаратной перекодировкой, таких как:

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

- экономия оборудования. Отсутствует необходимость использовать аппаратные перекодировщики и оптимизаторы;

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

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

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

- неполная совместимость с исходной эмулируемой архитектурой (несовместимость по операциям и типам данных);

- недостаточно эффективный результирующий код (ограничения на применение оптимизаций);

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

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

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

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

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

- семантика двоичного представления вещественного и мультимедийного контекстов сложна для анализа и оптимизации, в том числе и распараллеливания;

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

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

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

Цель исследований

Целью диссертационной работы является теоретический анализ проблем двоичной трансляции вещественных и мультимедийных кодов, разработка механизма эффективной реализации технологии их двоичной трансляции с использованием элементов аппаратной поддержки двоично-транслирующей системы, обеспечение полной совместимости двоично-транслированного вещественного и мультимедийного кода с исходной суперскалярной архитектуры Intel х86 (IA32) на целевую архитектуру с явно выраженным параллелизмом Эльбрус ЗМ (ЭЗМ).

В соответствии с этим были определены следующие задачи диссертационного исследования:

1. Анализ существующих двоично-транслирующих систем (ДТС).

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

3. Теоретическая разработка метода повышения производительности ДТС при обработке вещественного и мультимедийного контекстов.

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

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

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

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

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

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

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

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

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

- предложен метод модификации представления вещественного контекста в неоптимизированном двоично-транслированном коде

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

- реализован ряд алгоритмов быстрого (линейной сложности) анализа кода, а также алгоритмов его модификации, построенных наосновании предложенного метода;

- разработаны и реализованы алгоритмы обработки смешанного вещественного/мультимедийного кода;

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

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

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

- оптимизирующий двоичный транслятор с кодов архитектуры Intel х86 на архитектуру Эльбрус-ЗМ, работающий в составе многоязыковой системы программирования "Эльбрус-ЗМ", разработанной в ЗАО "МЦСТ" по заказу МО РФ;

- микропроцессор "Эльбрус-ЗМ", разработанный в ЗАО "МЦСТ", обеспечивающий совместимость с рядом архитектурных платформ, в том числе с Intel х86.

Апробация

Основные положения диссертационной работы докладывались и обсуждались на научно-технических конференциях Московского-Физико-Технического Института, Международной молодежной научной конференции «XXX Гагаринские чтения», презентациях оптимизирующей двоично-транслирующей системы, разработанных для фиры Intel.

Публикации

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

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

Диссертационная работа состоит из введения, трех глав, заключения и приложения. Диссертация содержит 120 страниц, 42 рисунка, 7 таблиц, приложение на 11 страницах. Список литературы насчитывает 58 наименований.

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

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

В первой главе вводится ряд понятий, связанных с двоичной трансляцией в целом и относительно вещественного контекста, поднимаются проблемы, связанные с оптимизацией трансляции данного контекста, рассматриваются всевозможные пути их решения, в результате чего производится постановка задачи диссертационной работы. Раздел 1.1 посвящен описанию двоично-транслирующей системы. Подраздел 1.1.1 посвящен введению ряда понятий, необходимых для описания процесса двоичной трансляции и составляющих базис терминологий, используемой в работе. "Целевой" будем называть архитектуру, нуждающуюся в поддержке программным обеспечением. "Исходной" будем называть архитектуру, двоичная совместимость с которой требуется достичь теми или иными средствами. Такой архитектурой обычно выбирается максимально распространенная с огромным количеством программных продуктов, созданных для нее. Процесс переноса исполняемого кода исходной вычислительной платформы в исполняемый двоичный код целевой вычислительной платформы называется "двоичной трансляцией". Программный продукт, обеспечивающий процесс двоичной трансляции, называется "двоичным транслятором". Комплекс программных продуктов, обеспечивающих корректное исполнение двоичных кодов исходной архитектуры на целевой платформе называется "двоично-транслирующей системой". В подразделе 1.1.2 поднимаются проблемы двоичной трансляции. В большинстве существующих микропроцессоров программа представляется линейным кодом. При решении задачи распараллеливания выполнение кода, для чего после дешифрации операций возникает необходимость группирования информационно независимых операций. В программной реализации систем двоичной совместимости возникает ряд проблем на этапах трансляции и исполнения кода. Основными задачами при анализе исходного кода являются:

1. Разделение данных и кода.

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

3. Обеспечение свойства точного прерывания исходного кода.

4. Сохранение семантической корректности при проведении оптимизаций.

5. Когерентность исходного кода и транслированного на целевую архитектуру при работе с памятью.

6. Обнаружение и обработка элементов нового кода.

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

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

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

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

• механизм контрольных точек;

• механизм поддержки переноса данных из памяти на регистры;

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

• механизм отложенного асинхронного прерывания;

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

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

БпоиХММ SSE регистры

_xmmO__^

Kmml_

_xmmZ_

хттЗ_

ummj_

_хтт5_

хтт/

Ретистр гояния j управления тия f

Рисунок 1. Представление контекста исходной платформы

О fi щи в регистры Регистры данных и адресов

еЬр

Указатель инструкций и регистр флагов

{ »'Р

) еАая»

Мат. сопроцессор Регистры данным FPU

Статусное и управляющее слоев

с

Под контекстом исходной Intel х86 (IA32) архитектуры (рисунок 1) понимаются такие глобальные элементы как:

• Все элементы памяти исходной архитектуры.

• Общие регистры. Регистры данных и адресов. Указатели

инструкций и регистр флагов

• Регистры данных математического сопроцессора FRU, его

управляющие и статусные регистры

• Регистры блока MMX/SSE, его регистр управления и состояния Сохранности первых двух пунктов контекста исходной архитектуры посвящено множество работ, однако задача диссертационной работы заключается именно в возможности сохранения следующих двух пунктов исходного контекста. Раздел 1.2 посвящен описанию вещественного контекста. Работа вещественного сопроцессора в рамках исходной архитектуры приведена в подразделе 1.2.1 и представляет собой обособленный контекст, состоящий из 8 регистров данных и регистров специального назначения:

• статусный регистр (status register);

• контрольный регистр (control register);

• регистр состояния регистров данных (tag Word register);

• указатель последней инструкции (last instruction pointer register);

• указатель последних данных (last data pointer register);

• код операции (opeode register).

Вещественные регистры данных представляют собой восемь 80-ти битных регистров. При загрузке целочисленных или вещественных данных из памяти они преобразуются в расширенный формат F80. Все вычисления производятся в формате F80. Вычисленные результаты сохраняются в памяти в требуемом вещественном или целочисленном формате. Основная особенность реализации вещественного контекста в исходной х86 архитектуре заключается в стековой организации хранения регистров данных. Индексация по вещественному стеку реализуется через указатель вершины вещественного стека, значение (ТОР) которого хранится в статусном регистре. Статусный регистр содержит также 6 флагов исключительных ситуаций вещественных вычислений, флага ошибки стека и Зх битов генерации условий. Биты ES и В эквивалентны и указывают, был ли выставлен хотя бы один из б флагов. Управление вещественными вычислениями производится при помощи контрольного регистра. На симметричных статусным 6 флагам исключений позициях расположены маски реакции на выставление данных флагов. Значимыми в данном регистре являются еще поля режима точности вычислений (PC) и режима округлений (RC). Регистр состояния регистров данных вещественного стека (Tag Word) хранит информацию о каждой позиции стека. Хранимые указатели на последнюю инструкцию, операнд и код операции позволяют корректно отрабатывать системы обработки прерываний.

В подразделе 1.2.2 рассматриваются аспекты обеспечения свойства двоичной совместимости вещественного контекста на целевой архитектуре, отмечаются введенные элементы контекста, позволяющие корректно отобразить контекст исходной архитектуры. Контрольный и статусный регистры исходной архитектуры получили абсолютно полное отображение в системных регистрах целевой архитектуры FPCR (Floating Point Control Register) и FPSR (Floating Point Status Register). Исключение составляет поле TOP статусного регистра исходной архитектуры, которое не было перенесено в регистр FPSR целевой архитектуры, ввиду чего позиции [13 : 11] статусного регистра остались незанятыми (резервированными). Двухбитовые поля, отвечающие за состояние каждого элемента вещественного стека трансформировались в однобитовое поле. А в дополнение к восьми битовым полям в новый регистр целевой архитектуры BGR (Base of Global Register) было добавлено поле положения вершины указателя вещественного стека (ТОР), перенесенные из статусного регистра исходной архитектуры. С помощью полученного статусного регистра состояния вещественного стека а также глобальных регистров целевой архитектуры G24 - G31 удалось полностью промоделировать работу вещественного стека исходной архитектуры. Помимо глобальных и статусных регистров целевой архитектуры несколько элементов исходной архитектуры было сохранено в памяти целевой платформы.

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

• изменение статусных регистров вещественного сопроцессора;

• генерация прерываний, в том числе и отложенных:

• продвижение указателя вершины вещественного стека;

• изменение значения бита округления С1 в статусном регистре.

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

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

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

- Разработчики выделили набор рабочих регистров под произвольное состояние вещественного стека. И основываясь на предположениях, что продвижение указателя вершины стека в широком диапазоне - ситуация крайне редкая, перенесли хранение выталкиваемых из отведенного диапазона регистров значения в память, а в случае запроса из области вне отведенного диапазона производят подкачку из памяти. В системах DAISY и BOA реализован иной принцип трансляции вещественного кода - трансляция с восстановлением контекста только в точках выхода единиц трансляции (регионов), а иногда даже с неполным его восстановлением, достаточным для корректного исполнения приложений на целевой архитектуре. В системе Crusoe для поддержания совместимости в архитектуру была введена аппаратная поддержка механизма контрольных точек и точечных прерываний. Данных механизм позволил производить восстановления контекста, в том числе и вещественного в фиксированных точках исполняемого кода. Преимущества данного метода в его мобильности, опирающейся на аппаратную поддержку двоичной трансляции. В отличие от рассмотренных ранее система IA-32 EL фирмы Intel позволяет оптимизировать простые вещественные последовательности. В основе достигнутых возможностей лежит механизм рассмотрения всех регистров вещественного стека как обычных регистров рабочей архитектуры. Исключение всех побочных эффектов (исключений вращения вещественного стека, работы со статусными регистрами) в системе IA-32 EL организовано в виде жестких ограничений на начальное состояние вещественного контекста.

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

• исследование проблем двоичной трансляции с исходной х86 (IA32) платформы на целевую Эльбрус ЗМ (ЭЗМ);

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

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

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

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

- введение оптимистических предположений;

- анализ неоптимизированного кода на применимость метода;

- сбор статической информации;

- построение условий проверок шс справедливости;

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

- сам механизм переименования;

- построение механизмов восстановления исходного контекста в требуемых для этого случаях.

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

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

2. Отслеживание изменения состояния флагов статусного регистра,

ответственных за прерывание вещественной арифметики FPSR.

3. Отслеживание изменения бита округления С1 в статусном

регистре FPSR.

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

5. Отслеживание изменений контрольного регистра FPCR.

6. Контроль за статусными регистрами вещественного сопроцессора.

Следует отметить, что для каждой из перечисленных групп

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

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

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

3. Неоднозначность изменения бита округления С1 в статусном регистре FPSR возможна лишь после исполнения одиночных вещественных операций.

4. Изменения статусных регистров сопроцессора FPU, хранящихся в памяти целевой архитектуры в теле региона не меняются.

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

Раздел 2.3 посвящен анализу неоптимизированного кода на предмет применимости предлагаемого метода переименования. Непреодолимыми для работы анализа являются точки (полюсы) в неоптимизированном представлении, где невозможно предсказать статическим способом состояние системного регистра BGR, в частности положение указателя вершины вещественного стека. К таким точкам можно отнести:

• прямую запись в регистр BGR;

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

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

• циклы, несбалансированные по смещению указателя вершины вещественного стека.

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

Ык

(=0

На каждой итерации цикла в фиксированной точке значение изменение указателя вершины вещественного стека будет различным.

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

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

1. Фиксация способа изменения бита округления С1.

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

3. Накапливаются с постоянной коррекцией и глобальные шкалы чтений и записи в регистры вещественного стека (Ох24 —31).

4. Фиксируются места изменения контрольного регистра ИРСИ..

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

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

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

- признак локальной работы с вещественным стеком:

- признак наличия полюса анализа;

- тип использования вещественного стека полезен при работе со смешанным контекстом;

- маска признака последнего смещения указателя вещественного стека;

- признак работы со статусным регистром; способ восстановления бита С! регистра РР8Я;

- индекс операции восстановления бита С1;

- диагностический признак невозможности применения переименования.

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

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

Раздел 2.6 работы освещает вопрос распаковки глобального контекста. Под распаковкой понимается механизм переноса на рабочие регистры элементов вещественного контекста, динамическое слежение за которыми просто необходимо на протяжении работы региона. К таким элементам относятся все 8 регистров вещественного стека, начальное значение регистров РРЭР, РРСГ<.

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

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

• операции чтения и записи регистра стека В GR заменяются на статически вычисляемые значения его состояния.

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

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

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

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

• макровызовы рассматриваются как операции полюса анализа.

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

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

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

псевдооперация REST_C1 (х), позволяющая без дополнительного анализа фиксировать способ модификации бита CI по представлению аргумента {1/O/Reg}.

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

вход вредом 1 ... вход в pewcti х

Рисунок 2. Схема модификации исходного представления в следствии применения метода переименования.

Рост кода, связанный с построением проверок, распаковок и запаковок является незначительным ввиду эффективного размещения в коде. Увеличение аргументов у части контрольных точек для гарантирования корректного восстановления контекста не влияет на производительность получаемого кода. Рост алгоритмической нагрузки оптимизирующего компилятора за счет работы метода переименования является оправданным, так как в результате удается достигнуть роста производительности на пакетах Эрес95)р и эресрегй) в среднем до 1.5 - 3 раз.

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

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

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

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

Наличие подобного ряда~задач позволяет считать предложенную ранее методику переименования перспективным направлением в развитии оптимизирующего двоичного компилятора с целью достижения максимальной производительности транслируемых вещественных приложений. Первому направлению дальнейшего развития методики посвящен раздел 3.1. В процессе тестирования на практике предложенного к рассмотрению в работе метода переименования вещественного контекста была найдена и зафиксирована характерная особенность в поведении исходной архитектуры при обработке вещественных кодов. Вещественная операция FSTP, читающая значение из первого регистра вещественного стека относительно текущего положения указателя вершины стека и затем значение указателя на единицу освобождая считанную позицию в стеке, совершает дополнительное действие. Для облегчения анализа подобной ситуации на стадии трансляции были добавлены признаки трансляции именно тех операций FSTP, результат которых пишется обратно в вещественный стек. В коде оптимизирующего компилятора введенный признак был представлен в виде псевдооперации SBGRBs (х). Аббревиатура команды складывается из фразы (Set BGR Bit) установка (определение) бита регистра BGR. При глобальном анализе метода переименования операции SBGRBs обрабатываются по специальному дополнительному алгоритму. Статически собранные данные на момент появления операции в представлении способны однозначно разрешить ситуацию либо в сторону ее безопасности для применимости метода, либо в сторону полной непроходимости анализа.

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

преобразования операндов позволили сократить в некоторых случаях длину цепочек вещественных операций в 2-3 раза. В подразделе 3.2.2 рассмотрен вопрос проставления или удаления диагностической операции TEST. Данная операция была введена с целью отслеживания точного места нарушения корректности вычисления по выставленным битам дефектности в результирующих операндах операций, в том числе и вещественных. Предложенные правила удаления избыточных операций контроля корректности операндов вещественных операций позволили сократить в некоторых случаях длину цепочек вещественных операций до 2 раз. Подраздел 3.2.3 затрагивает еще одну неоппшальность в неоптимизированном вещественном коде, а именно построение условий переходов, основанных на вещественных сравнениях. В результате трансляции исходного кода подобные условия перехода получаются в виде цепочки операций сравнения, вырабатывающей результат в виде флагов, и операции преобразования флагов в условие перехода. Благодаря тому факту, что в многообразии вещественных операций целевой архитектуры наряду с операциями вещественного сравнения с выработкой результата в виде флагов существуют аналогичные им, вырабатывающие результат в виде условия перехода (предиката), возникает возможность применить ряд преобразований и к данной цепочке операций. Удаление избыточной работы с регистром флагов за счет сверки операции вещественного сравнения с операцией выработки предиката часто позволяет произвести целочисленные преобразования над операциями, его модифицирующими. Подраздел 3.2.4 посвящен результатам всего раздела 3.2. Суммарное ускорение на тестовых пакетах SPEC95ip b specperfb составило ~ 15%.

Раздел 3.3 является описанием дополнительной экспериментальной работы, посвященной попытке расширить область применения предлагаемой методики переименования на мультимедийный контекст. Часть элементов контекста напрямую использует те же архитектурные ресурсы, в частности регистры вещественного стека. Особенностям описания данного контекста посвящен подраздел 3.3.1. Блок мультимедийных операций представляет расширенные функциональные способности новых х86 архитектур, начиная с семейства процессоров Pentium. ММХ технология поддерживает модель обработки данных SIMD (Single_instruction, multiple_data). Начиная с семейства процессоров х86 Pentium III набор мультимедийных операций расширен SSE (Streaming SIMD Extension) блоком. ММХ технология позволила обрабатывать целочисленные данные запакованных типов, a SSE расширение позволило увеличить формат упакованных данных до 128 разрядов и применить параллельные вычисления к вещественным операндам. Мультимедийный контекст состоит из двух групп по 8 регистров, данных и регистра специального назначения MXCSR.

Для обеспечения сохранности свойства двоичной совместимости мультимедийного контекста на целевой архитектуре были добавлены элементы контекста, позволяющие корректно отобразить весь мультимедийный контекст исходной архитектуры. Из описания элементов мультимедийного контекста исходной архитектуры следует, что 64 битовые ММХ регистры данных отображаются на младшие части 80 битовых регистров вещественного стека. Отличительной особенностью отображения ММХ регистров является всегда определенное состояние статусного регистра BGR: нулевое значение положения указателя вершины вещественного стека Регистр MXCSR, совмещающий функции контроля и отображения статусного состояния SSE контекста, полностью перенесен на свой аналог на целевой архитектуре PFPFR (Packed Floating Point Flag - Register). Мультимедийный контекст представляет собой упрощенное представление вещественного контекста. В частности, положение указателя вершины вещественного стека строго фиксировано, операции ММХ пакета являются целочисленными и не обладают дополнительной функциональностью, а операции SSE пакета не имеют точек пересечения по ресурсам с вещественным контекстом.

Реальная проблема применения метода переименования возникла при обработке смешанного неоптимизированного кода. Основная проблема потери производительности заключается в постоянной необходимости переключения контекста. Возникает необходимость в случае использования метода переименования точно знать точки кода, где закончилась обработка одного и началась обработка другого контекста. Подобная задача возникает только в случае конфликтов по ресурсам, в данном случае, при обращениях к вещественному стеку, то есть при обработке ММХ контекста в рамках вещественного кода. Возникает необходимость рассматривать точки переключения контекста как блокирующие продолжение анализ полюса. Однако для получения информации о точках переключения контекста необходимо совершить дополнительный анализ В подразделе 3.3.2 описан метод, разработанный для данной задачи, позволяющий решить возникшую проблему обработки смешанного контекста. Подраздел 3.3.2.1 посвящен описанию нового метода, построенного на базе производимого анализа при поиске точек переключения контекстов. Причем информацией о точках переключения контекста необходимо обладать до момента разметки кода на блоки разрешенного анализа. Процесс получения точек переключения FP/MMX контекста получил название "раскрашивания" управляющего графа на области вещественной /мультимедийной,' "не затронутой ими" арифметики. Основными критериями разметки являются:

• Цикл должен принадлежать одному цвету.

• Узел неопределенного цвета получает его по доминирующему цвету предшественников и потомков.

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

• Боковые входы или выходы в/из цикла могут получать цвет отличный от цвета цикла.

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

Рисунок 3. Схема переименованного смешанного представления.

Завершают раздел 3.3 описание преимуществ и недостатков метода переименования в рамках смешанного контекста, а также достигнутые в данной работе результаты. Переименованный регион становится свободен не только от ограничений, свойственных вещественным операциям, но появляется возможность перемешивать вычисления различных контекстов: производить параллельные их вычисления, забрасывать арифметические операции друг за друга. К недостаткам обработки смешанного контекста можно отнести, конечно же, расширение целевого неоптимизированного кода за счет операций проверки, распаковок и запаковок. Однако часть данных операций уйдет в компенсирующие кода контрольных точек, часть свернется оптимизациями (peephole, global copy propagation, constant propagation). Замедление работы метода при вводе универсализации анализа составила не более нескольких процентов от времени работы всего механизма переименования в целом. Экспериментальные данные подтверждают не только факт работоспособности методики и тем самым

ее универсальности, но и показывают небольшой прирост производительности двоично-транслированных кодов ~ 5%.

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

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

- -Выводы- по результатам работы

Представленная диссертационная работа посвящена вопросу повышения производительности исполняемых кодов целевой архитектуры ЭльбрусЗМ, полученных в результате двоичной трансляции с исходной Intel х86 архитектуры. Рассмотрены всевозможные способы решения поставленной задачи, их положительные и отрицательные стороны. В рамках поставленной задачи выбран программный путь достижения двоичной совместимости исходной и целевой архитектур, как наиболее гибкий (позволяющий вносить необходимые изменения в процессе трансляции как в обрабатываемый код так и в сам процесс) и мобильный ( процесс развития алгоритмической составляющей оптимизирующего компилятора в рамках двоично-транслирующей системы непрерывен). Ключевой задачей диссертационной работы является вопрос повышения производительности двоично-транслированных кодов, затрагивающих наиболее проблемные с точки зрения оптимизации элементов контекста исходной архитектуры, таких как вещественный и мультимедийный контексты.

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

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

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

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

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

- SPECfp95(small ref data) = 1.8;

- SPECfp95(ref) = 1.5;

- Specperfb = 1.5-12.

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

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

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

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

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

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

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

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

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

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

Все представленные в диссертационной работе алгоритмы и

методы, реализованы в составе оптимизирующего двоичного

компилятора с кодов исходной архитектуры Intel х86 на архитектуру

Эльбрус-ЗМ. Данный факт подтвержден актом о внедрении.

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

1. Статья «Методика представления конвейера при формальной верификации микропроцессоров». Информационные технологии и вычислительные системы 1/1999.

2. Статья «Совместимость MPEG-1 и MPEG-2 стандартов». Информационные технологии и вычислительные системы. Сборник научных трудов ИМВС РАН, 2002.

3. Статья «Оптимизация обработки вещественного контекста в двоично-оптимизирующей системе». Информационные технологии и вычислительные системы 3/2004.

4. Статья «Обработка смешанного вещественного/мультимедийного контекста в оптимизирующих двоично-транслирующих системах». Компьютеры в учебном процессе. 9/2005.

5. Статья «Оптимизирующая двоичная трансляция вещественных приложений». Информационные технологии. 6/2006

6. Статья «Специфика оптимизации вещественных приложений в оптимизирующем двоичном компиляторе». Компьютеры в учебном процессе. 3/2006.

7. Тезисы доклада «Обработка вещественного контекста в оптимизирующей двоично-транслирующей системе». XXI научно-техническая конференция войсковой части 03425. - М.:, 2003.

8. Тезисы доклада «Метод повышения производительности вещественных и мультимедийных кодов в процессе двоичной трансляции с архитектуры Intel х86 IA32 на архитектуру с явно выраженным параллелизмом». XXXI Гагаринские чтения, международная молодежная научная конференция, М, 2005.

9. Статья «Специфические оптимизации вещественных кодов в процессе оптимизирующей двоичной трансляции с архитектуры Intel х86 на архитектуру Эльбрус-ЗМ» XXXII Гагаринские чтения, научные труды международной молодежной научной конференции, М, 2006.

Принято к исполнению 21/06/2006 Исполнено 22/06/2006

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

ООО «11-й ФОРМАТ» ИНН 7726330900 Москва, Варшавское ш., 36 (495) 975-78-56 (495) 747-64-70 www.autoreferat.rn

ВВЕДЕНИЕ.

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

1.1 Двоично-транслирующая система (ЦТС).

1.1.1 Основные понятия ДТС.

1.1.2 Проблемы двоичной трансляции.

1.1.3 Структура двоично-транслирующей системы.

1.1.4 Классификация существующих двоично-транслирующих систем.

1.1.5 Оптимизирующий компилятор в двоично-транслирующей системе.

1.2 Двоичная трансляция вещественного контекста.

1.2.1 Описание вещественного контекста исходной Intel х86 (IA32) архитектуры. 20 1.2.2. Описание реализации поддержки семантической корректности вещественного контекста исходной архитектуры на целевой платформе.

1.3 Проблемы оптимизации вещественного контекста.

1.4 Возможные пути решения. Обзор существующих систем двоичной трансляции.

1.5 Постановка задачи.

Выводы.

2. БАЗОВАЯ МЕТОДИКА ОБРАБОТКИ ВЕЩЕСТВЕННОГО КОНТЕКСТА.

2.1. Технология переименования вещественного контекста.

2.2 Введение оптимистических предположений.

2.3 Анализ неоптимизированного кода на применимость метода переименования.

2.4 Сбор статической информации для применения метода переименования.

2.4.1 Локальный анализ применимости метода переименования.

2.4.2 Глобальный анализ применимости метода.

2.5 Построение контрольных условий.

2.6 Построение распаковок.

2.7 Механизм переименования.

2.8 Восстановление исходного контекста.

2.9 Преимущества и недостатки метода переименования.

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

Выводы.

3. РАСШИРЕННЫЕ ВОЗМОЖНОСТИ ПРИМЕНЕНИЯ БАЗОВОЙ МЕТОДИКИ.

3.1 Недокументированные особенности обработки вещественного контекста на исходной архитектуре. Адаптация метода переименования.

3.2 Специфические оптимизации вещественного контекста.

3.2.1 Удаление избыточности форматных преобразований операндов.

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

3.2.3 Модификация построения условий переходов.

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

3.3 Обработка смешанного мультимедийного/вещественного контекста.

3.3.1 Общее описание.

3.3.2 Особенности обработки смешанного кода.

3.3.3 Преимущества и недостатки оптимизаций смешанного кода.

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

Выводы.

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

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

Одним из наиболее распространенных на сегодняшний день способов обеспечения параллельности остается применение аппаратных решений. Ярким примером такого решения могут служить целые поколения процессоров фирмы Intel (Pentium, Pentium Pro) с набором команд CISC (Complex Instruction Set Computing), представляющих собой суперскалярное ядро па базе RISC архитектуры и аппаратный перекодировщик из CISC в RISC инструкции ядра. В то же время данный способ приводит к дополнительным затратам оборудования, ухудшению физических характеристик, таких как размеры кристаллов и энергопотребление.

Обеспечение требуемой для современных задач параллельности можно достичь и путем существенных изменений микропроцессорных архитектур па хорошо зарекомендовавшую себя архитектуру VLIW (Very Long Instruction Word) [4]. Новые алгоритмы планирования и распределения ресурсов, реструктуризация управления позволяют получить значительный прирост производительности по сравнению с суперскалярными методами. Дополнительным преимуществом VLIW архитектуры является возможность эффективно применить к ней методы формальной верификации [50]. Однако наряду с полученными преимуществами такие архитектуры приобрели и полную двоичную несовместимость [1] с другими архитектурными решениями.

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

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

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

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

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

Ввиду специфики данной проблематики, существующие на данный момент в мировой практике системы двоичной трансляции [16,25,26,27,29,30,55] не уделяют должного внимания путям решения проблеме повышения производительности двоично- транслированных мультимедийных приложений. Это происходит по нескольким причинам, таким как: семантика двоичного представления вещественного и мультимедийного контекстов сложна для анализа и оптимизации, в том числе и распараллеливания; в существующих аппаратных реализациях не достаточно средств для обеспечения возможности распараллеливания вещественных вычислений; возникает необходимость применения новых специализированных методов обработки данных контекстов.

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

Цель исследования

Целью диссертационной работы является теоретический анализ проблем двоичной трансляции вещественных и мультимедийных кодов, разработка механизма эффективной реализации технологии их двоичной трансляции с использованием элементов аппаратной поддержки двоично-транслирующей системы, обеспечение полной совместимости двоично-транслированного вещественного и мультимедийного кода с исходной суперскалярной архитектуры Intel х86 (IA32) [7] па целевую архитектуру с явно выраженным параллелизмом Эльбрус ЗМ (ЭЗМ) [8, 9, 10].

В соответствии с этим были определены следующие задачи диссертационного исследования:

1. Анализ существующих двоично-транслирующих систем (ДТС).

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

3. Теоретическая разработка метода повышения производительности ДТС при обработке вещественного и мультимедийного контекстов.

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

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

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

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

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

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

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

- реализован ряд алгоритмов быстрого (линейной сложности) анализа кода, а также алгоритмов его модификации, построенных паосновании предложенного метода;

- разработаны и реализованы алгоритмы обработки смешанного вещественного/мультимедийного кода;

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

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

Результаты исследований, выполненных по теме диссертационной работы, нашли практическое применение в следующих программных и аппаратных системах: оптимизирующий двоичный транслятор с кодов архитектуры Intel х86 на архитектуру Эльбрус-ЗМ, работающий в составе многоязыковой системы программирования "Эльбрус-ЗМ", разработанной в ЗАО "МЦСТ" по заказу МО РФ; микропроцессор "Эльбрус-ЗМ", разработанный в ЗАО "МЦСТ", обеспечивающий совместимость с рядом архитектурных платформ, в том числе с Intel х86.

Апробация

Основные положения диссертационной работы докладывались и обсуждались на научно-технических конференциях Московского-Физико-Техпического Института, Международной молодежной научной конференции «XXX Гагаринские чтения», презентациях оптимизирующей двоично-транслирующей системы, разработанных для фиры Intel.

Публикации

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

1. Статья «Оптимизация обработки вещественного контекста в двоично-оптимизирующей системе». Информационные технологии и вычислительные системы 3/2004.

2. Статья «Обработка смешанного вещественного/мультимедийного контекста в оптимизирующих двоично-транслирующих системах». Компьютеры в учебном процессе. 9/2005.

3. Статья «Оптимизирующая двоичная трансляция вещественных приложений». Информационные технологии. 6/2006.

4. Статья «Специфика оптимизации вещественных приложений в оптимизирующем двоичном компиляторе». Компьютеры в учебном процессе. 3/2006.

5. Статья «Методика представления конвейера при формальной верификации микропроцессоров». Информационные технологии и вычислительные системы 1/1999.

6. Статья «Совместимость MPEG-1 и MPEG-2 стандартов». Информационные технологии и вычислительные системы. Сборник научных трудов ИМВС РАН, 2002.

7. Тезисы доклада «Обработка вещественного контекста в оптимизирующей двоично-транслирующей системе». XXI научно-техническая конференция войсковой части 03425. - М.:, в/ч 03425, 2003.

8. Тезисы доклада «Метод повышения производительности вещественных и мультимедийных кодов в процессе двоичной трансляции с архитектуры Intel х86 IA32 на архитектуру с явно выраженным параллелизмом». XXXI Гагарииские чтения, международная молодежная научная конференция, Москва, 2005 Том 4.

9. Тезисы доклада «Специфические оптимизации вещественных кодов в процессе оптимизирующей двоичной трансляции с архитектуры Intel х86 па архитектуру Эльбрус-ЗМ», XXXII Гагаринские чтения, международная молодежная научная конференция, Москва, 2006.

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

Работа состоит из введения, трех глав и заключения.

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

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

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

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

- оптимистические предположения;

- анализ применимости; сбор информации;

- построение контрольных условий;

- механизм переименования; восстановление контекста.

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

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

- обработка недокументированныз особенностей исходной архитектуры;

- специфические оптимизации представления вещественного контекста; обработка смешанного вещественного/мультимедийного контекста.

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

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

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

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

Выводы

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

Экспериментальное применение разработанных в данной главе специфических оптимизаций позволило достичь повышения производительности вещественных двоично-транслированных кодов на пакетах SPECfp95, specperfb составило в среднем -15%. Суммарное ускорение применения базовой методики составило -80% на пакете SPECfp95 и достиглол 1.5-12 раз ускорения на пакете specperfb. Применение разработанной методики обработки вещественного контекста позволило впервые в мировой практике получить двоично транслированный с исходной Х86 архитектуры вещественный код исполняемый быстрее своего исходного аналога. В результате применения метода переименования коэффициент суммарного ускорения па тестовом пакете SPECfp95 увеличился с величины 0.74 до преодолевшего единицу значения 1.29

Данная глава диссертационной работы показывает универсальность разработанного метода переименования па примере применимости его к не менее объемному, чем вещественный, классу операций мультимедийных операций. Экспериментальные замеры на тестовых пакетах SPECint95 и specperfb, собранных компилятором с языков высокого уровня исходной архитектуры с использованием мультимедийных пакетов операций ММХ и SSE, подтверждают работоспособность метода переименования на мультимедийных кодах.

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

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

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

Заключение

Представленная диссертационная работа посвящена вопросу повышения производительности исполняемых кодов целевой архитектуры ЭльбрусЗМ, полученных в результате двоичной трансляции с исходной Intel х86 архитектуры. Рассмотрены всевозможные способы решения поставленной задачи, их положительные и отрицательные стороны. В рамках поставленной задачи выбран программный путь достижения двоичной совместимости исходной и целевой архитектур, как наиболее гибкий (позволяющий вносить необходимые изменения в процессе трансляции как в обрабатываемый код так и в сам процесс) и мобильный ( процесс развития алгоритмической составляющей оптимизирующего компилятора в рамках двоично-транслирующей системы непрерывен). Ключевым моментом диссертационной работы является вопрос повышения производительности двоично-транслированных кодов, затрагивающих наиболее проблемные с точки зрения оптимизации элементов контекста исходной архитектуры, таких как вещественный и мультимедийный контексты.

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

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

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

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

- SPECfp95(small ref data) = 1.8;

- SPECfp95(ref) = 1.5;

- Specperfb = 1.5- 12

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

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

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

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

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

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

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

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

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

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

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

1. С.А. Рожков Технология двоичной совместимости программно-аппаратных ^ средств. Программные продукты и системы, N 1,1999.

2. Halfhill T.R. AMD Vs. Superman. Byte, Nov, 1994.

3. Halfman T.R. Intel's P6. Byte, Apr, 1995.

4. J.A. Fisher. Very Long Instruction Word Architecture and the ELI-512. Proceedings of the 10th Annual International Symposium on Computer Architecture, p. 140-150. Stockholm, Sweeden, Jun. 13-17, 1983. Computer Architecture News, 11(3), Jun, 1983.

5. R. Sites, A. Chemoff, M. Kirk, M. Marks and S. Robinson. Binary Translation. Communications of the ACM, vol.36, No.2, Feb, 1993, pp. 69-81.

6. G.M. Silberman, K.Ebcioglu An architectural framework for migration from CISC to higher performance platform In Proc. Of the 1992 Inrenational Conference on Supercomputing, pp 198-215, Washington, DC, Jul 1992, ACM Press.

7. C.A. Рожков Надежность оптимизирующих двоично-транслирующих систем. Информационные технологии и вычислительные системы, N 1, 1999

8. IA-32 Intel Architecture Software Developer's Manual. Volume 1-3, Intel1. Corporation.

9. Babayan B.A. Main Principles of E2K Architecture. Free Software Magazine, Vol. 1, Issue 02, Feb 2002.

10. Keith Diefendorf "The Russians Are Coming: Supercomputer Maker Elbrus Seeks to Join x86/IA-64 Melee" Microprocessor report, vol. 11, num. 2, Feb. 15, 1999.

11. А.А.Иванов Обобщенное описание семантики в двоично-транслирующей системе с платформы Intel на платформу Эльбрус. Высокопроизводительные вычислительные системы и микропроцессоры, Сборник научных трудов, выпуск1. Ш 4, М., ИМВС РАН. 2003.

12. А.В.Ермолович Системная поддержка динамического двоичного компилатора: управление памятью. Тезисы докладов Международной конференции XXVI Гагаринские чтения, М.,2000.

13. А.В.Ермолович Применение базы кодов в динамической двоично-траислирующей системе. Высокопроизводительные вычислительные системы и микроппроцессоры, Сборник научных трудов, выпуск 4, М., ИМВС РАН, 2003.

14. С. Cifiientes, V. Malhotra Binary Translation: Static, Dynamic, Retargetable? -Proceeding of the 1996 International Conference on Software Maintenance (ICSM'96), Monterey, CA, Nov, 1996.

15. Anton Chernoff, Mark Herdeg, Ray Hookway, Chris Reeve, Norman Rubin, Tony Туе, S. Bharadwaj Yadavall and John Yates " FXI32: A Profile-Directed Binary Translator" IEEE Micro(18), March/April 1998.

16. A. Chernoff, R. Hookway DIGITAL FXI32: Running 32-Bit x86 Applications on Alpha NT. Proceeding of the USENIX Windows NT Workshop Seattle, Washington, Aug, 1997.

17. T. Cramer, R. Friedman, T. Miller, D. Seberger, R.Wilson, M.Wolczko Compiling Java Just in Time. IEEE Micro, May/Jun 1997, Vol.17,3, pp36-43.

18. V. Bala, E. Duesterwald, S. Baneijia. Transparent Dynamic Optimization: The Design and Implementation of Dynamo. Hewlett Packard Laboratories Cambridge, Tech. Report HPL-1999-78, June 1999.

19. Michael Gschwind and Eric R. Altman "Optimizing and Precise Exceptions in Dynamic Compilation", Second Workshop on Binary Translation Held in PACT 2000.

20. A.Aho, R.Sethi, J.Ullman "Compilers: principles, techniques, and tools". Addison-Wesley, Reading, MA, 1986

21. A. Drozdov, V. Volkonski et al. "The Optimizing Compiler for the Elbrus-3 Supercomputer", International Congress on Computer Systems and Applied Mathematics, CSAM'93, Abstracts, St. Petersburg, July 19-23, 1993, pp.127-128.

22. E.R Altman, K. Ebcioglu, M. Gschwind and S. Sathaye "Advances and Future Challenges in Binary Translation and Optimization", Proceedings of the IEEE Special Issue on Microprocessor Architecture and Compiler Technology, Nov 2001.

23. P. Hohensee, M. Myszewski, D. Reese, Wabi Cpu Emulation. Hot Chips VIII Proceeding, Stanford, Aug, 1996.

24. Wabi Users Guide. SunSoft A Sun Microsystems, Inc. Business, May 1996.

25. K. Ebcioglu, E.R. Altman "DAISY: Dynamic Compilation for 100% Architectural Compatibility", Proceedings of the 24th Annual Symposium on Computer Architecture, Jun 2001.

26. E. Altman, M.Gschwind, S.Sathaye, S.Kosonosky, A.Bright, J.Fritts, P.Ledak, D.Appenzeller, C.Agricola, Z.Filan. BOA: The Architecture of a Binary Translation Processor. IBM Research Report RC 21655 (97500), Dec, 1999.

27. K.Ebcioglu, E. Altman, M.Gschwind, S.Sathaye. Dynamic Binary Translation and Optimization. IBM Research Report RC 22025 (98128), Jul, 2000.

28. Vasanth Bala, Evelyn Duesterwald and Sanjeev Banjeria, "DYNAMO: A Transparent Dynamic Optimization System", Programming Language Design and Implementation, June 2000.

29. Intel Itanium Processor Family Reference Guide: IA-32 Execution Layer. IA-32 Application Support Provides Flexibility in Migrating to Itanium Architecture. Quick Reference Guide. Intel Corporation, 2004.33. http://intel.com/go/itanium2

30. IA-32 Intel Architecture Software Developer's Manual. Vol.3, Intel Corporation. Chapter 8, Programming with the X87 FPU.

31. ANSI/IEEE Std 754-1985 An American National Standard. IEEE Standard for Binary Floating Point Arithmetic.

32. J.Henessy. Program optimization and exception handling. ACM SIGPLAN. Jan 1981, pp. 200-206.

33. П.С.Василец, Д.М.Масленников, О.С.Драгошанский, Оптимизация обработки вещественного контекста в двоично-оптимизирующей системе. Информационные технологии и вычислительные системы, 3, 2004.

34. В.А.Евстигнеев, В.Н.Касьянов. Теория графов. Алгоритмы обработки деревьев -Новосибирск: Наука. 1994.

35. J.Ferrante, KJ.Ottenstein, J.D.Warren. The program dependence graph and its use in optimization // ACM TOPLAS. July 1987.

36. S.Muchnick. Compiler design and implementation Morgan Kaufmann Publishers. San Francisco, California. 1997.

37. IA-32 Intel Architecture Software Developer's Manual. Vol.3, Intel Corporation. Chapter 9, Programming with the Intel MMX Technology.

38. IA-32 Intel Architecture Software Developer s Manual. Vol.3, Intel Corporation. Chapter 10, Programming with the StreamingSIMD Extensions (SSE).

39. П.С.Василец Обработка смешанного вещественного/мультимедийного контекста в оптимизирующих двоично-трапслирующих системах. Компьютеры в учебном процессе, 9, 2005.

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

41. П.С.Василец, Л.А.Кулаков Совместимость MPEG-1 и MPEG-2 стандартов. Информационные технологии и вычислительные системы. Сборник научных трудов ИМВС РАН, 2002.

42. П.С.Василец, В.В.Тихорский Методика представления конвейера при формальной верификации микропроцессоров. Информационные технологии и вычислительные системы 1/1999.

43. М.Жвинд, Э.Олтмен, С.Сатхаи, П.Ледак, Д.Аппензеллер Динамическая и прозрачная двоичная трансляция. Открытые системы 4/2000.

44. К.Зепг, К.Томпсон Из РА-RISC в IA-64: прозрачное выполнение, никакой перекомпиляции. Открытые системы 4/2000.

45. Максименков Д.А. Генератор тестов для бинарного компилятора. Сборник трудов «Современные информационные технологии и ИТ-образование» Москва, 200554. http://www.transitive.com/

46. T.P.Morgan Transitive Emulates Srver Platforms on Other Iron, DeepApple.com

47. Л.Башкиров Светлое будущее Apple, OSX погубит Linux, больше конкретики о Rosetta. MacTime.ru

48. K.Krewell Transitive's Tech Frees ISA Dependence Microprocessor Report 8/8/2005

49. D.Bacon, S.Graham, O.SharpCompiler Transformations for High-Performance Computing. Computer Science Division, University of Califirnia, Berkely, California 94720.

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

51. Василец П.С., Масленников Д.М. Оптимизирующая двоичная трансляция вещественных приложений. Информационные технологии, 6, 2006.1. Список иллюстраций

52. Рис. 1 Структура двоично-транслирующей системы.

53. Рис.2 Схема статической двоично-транслирующей системы.

54. Рис. 3 Схема динамической двоично-транслирующей системы.

55. Рис. 4 Схематическое представление контекста исходной платформы.

56. Рис. 5 Схематическое представление вещественного контекста исходной архитектуры

57. Рис. 6 Контрольный регистр вещественной арифметики целевой архитектуры. Floating point control register FPCR

58. Рис. 7 Статусный регистр вещественной арифметики целевой архитектуры. Floating point status register FPSR.

59. Рис. 8 Принцип соответствия элементов вещественного контекста исходной архитектуры и статусного регистра состояния вещественного стека целевой архитектуры.

60. Рис. 9 Принцип соответствия полей статусного регистра и регистров вещественного стека целевой архитектуры.

61. Рис. 10 Алгоритмическое представление операции продвижения указателя вещественного стека (ABG) целевой архитектуры.

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

63. Рис.12 Критерий сбалансированности цикла по относительному смещению указателя вершины вещественного стека.

64. Рис. 13 Пример представления управляющего графа сбалансированного по относительному изменению указателя вершины вещественного стека.

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

66. Рис. 15 Схематическое представление алгоритма расстановки искусственного смещения stp в узлах управляющего графа.

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

68. Рис. 17 Накопления статической информации па примере последовательности вещественных операций.

69. Рис. 18 Примеры элементов управляющего графа с прямым наследованием с множественным схождением.

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

71. Рис. 20 Пример рекурсивного распространения сверху-вниз информационной зависимости от узла с проявлением анализируемого признака АО до его использования ВО.

72. Рис.21 Алгоритмическое представление метода переименования вещественного контекста.

73. Рис. 22 Схематическое представление механизма построения контрольных условий на входе в регион.

74. Рис. 23 Согласованные состояния регистра BGR (а). Согласованные циклически смещенные состояния регистра BGR (б ).

75. Рис. 24 Получения максимального относительного смещения указателявершины вещественного стека на примере управляющего графа.

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

77. Рис. 26 Схематическое представление механизма построения распаковок на входе в регион

78. Рис. 27 Схематическое представление механизма построения распаковок на входе в регион

79. Рис. 28 Пример точки схождения управляющего графа с альтернативными вариантами модификации состояния бита С1 регистра FPSR.

80. Рис. 29 Алгоритм восстановления бита С1 статусного регистра FPSR

81. Рис. 30 Схема модификации исходного представления в следствии применения метода переименования.

82. Рис.31 Пример применения правила сбора общих подвыражений с вещественной спецификой

83. Рис. 32 Схематическое представление мультимедийного контекста исходной архитектуры.

84. Рис.33 Принцип отображения элементов мультимедийного ММХ контекста исходной архитектуры на вещественный стек.

85. Рис.34 Контрольный и статусный регистр мультимедийного SSE контекста исходной архитектуры

86. Рис. 35 Схематическое представление мультимедийного контекста на целевой архитектуре.

87. Рис. 36 Схема модификации исходного представление в следствии применения метода переименования мультимедийного контекста.

88. Рис. 37 Схематическое представление разрыва цикловой зависимости в случае ее препятствия работе метода переименования.

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

90. Рис. 39 Пример спорного узла при раскрашивании управляющего графа.

91. Рис. 40 Пример 2 спорного узла при раскрашивании управляющего графа.

92. Рис.41 Схема модифицированного исходного смешанного представления в следствии применения метода переименования.

93. Рис. 42 Схема простейшего случая смешанного исходного представления.