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

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

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

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

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

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

Москва - 2003

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

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

Рожков Сергей Алексеевич

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

профессор

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

кандидат технических наук, с.н.с.

Ревякин Вадим Александрович

Ведущая организация: ОАО "Институт электронных управляющих

машин"

Защита состоится " ¿У " декабря 2003 г. в /5" ч. Ю мин. на заседании Диссертационного совета Д 002.043.01 при Институте микропроцессорных вычислительных систем РАН по адресу: 119435, г. Москва, Б. Саввинский пер., д. 14.

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

Автореферат разослан " ¿{ " ноября 2003 г.

Ученый секретарь Диссертационного совета д. ф.-м.н., профессор

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

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

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

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

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

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

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

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

и возможности многократного их исполнена_._—-"ьцад )

Техника двоичной трансляции развив одна-

С.Пегербчп»'- '' ^ 09

егербюг у & . ;

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

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

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

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

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

• анализ принятых принципов построения ДТС;

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

• теоретическая разработка модели ДТС, опирающейся на полученные результаты;

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

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

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

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

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

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

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

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

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

Реализованы несколько версий действующих ДТС, подтверждающих выносимые на защиту результаты.

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

• семейство инструментальных динамических двоичных трансляторов уровня приложений для переноса приложений платформы 5о1апз/1А-32 на модель микропроцессора "Эльбрус-ЗМ";

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

• ВК "Эльбрус-ЗМ", разработанный в ЗАО МЦСТ, обеспечивающий совместимость с архитектурной платформой 1А-32 на уровне виртуальной машины.

Апробация. Основные положения диссертационной работы докладывались на международных конференциях "Региональная Информатика -2000" (Санкт-Петербург, 2000 г.), "Региональная Информатика - 2002" (Санкт-Петербург, 2002 г.); международных молодежных научных конференциях XXVI Гагаринские чтения (Москва, 2000 г.), XXVII Гагарин-ские чтения (Москва, 2001 г.), XXVIII Гагаринские чтения (Москва, 2002 г.), XXIX Гагаринские чтения (Москва, 2003 г.); всероссийской научно-технической конференции "Новые материалы и технологии - НМТ-2002 (Москва, 2002 г.); а также докладывались и обсуждались на научно-технических семинарах ЗАО МЦСТ и ИМВС РАН.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• уменьшение накладных расходов: снижение затрат на обслуживание двоично-транслированных кодов должно вести к росту эффективности функционирования ДТС в целом;

• повышение коэффициента переиспользуемости двоично-транслированного кода: ДТС должна по возможности мини-

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

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

Примером оригинальной отечественной разработки в области современных высокопроизводительных вычислительных машин может служить разрабатываемый ЗАО "МЦСТ" вычислительный комплекс "Эльбрус-ЗМ" ("ЭЗМ"), основанный на одноименном микропроцессоре. Микропроцессор "ЭЗМ" является первой практической реализацией архитектуры микропроцессора с явным параллелизмом исполняемых команд "Е2К" и ориентирован на достижение крайне высокой эффективности работы, в том числе за счет аппаратной поддержки проведения множества агрессивных оптимизаций в исполняемом коде.

Одним из возможных режимов функционирования "ЭЗМ" является работа в режиме двоичной совместимости с архитектурой 1А-32. Необходимая аппаратная поддержка позволяет спроектировать и реализовать для "ЭЗМ" ДТС, включая оптимизирующие ее компоненты, позволяющую эффективное исполнения кодов IA-32 на платформе "ЭЗМ". Реализация двоичной совместимости на уровне виртуальной машины обеспечивает ВК "ЭЗМ" незамедлительный доступ ко множеству прикладного и системного ПО, реализованного для платформы IA-32. Основными составными частями ДТС "ЭЗМ" являются интерпретатор, неоптимизирующий и оптимизирующий двоичные трансляторы, макроподдержка семантически сложных операций и набор сервисов системной поддержки.

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

Неоптимизирующий двоичный транслятор построен по принципу ша-

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

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

Макроподдержка семантически сложных операций используется для отображения семантики сложных команд и процессов исходной архитектуры, раскрытие которой непосредственно в двоично-транслированном коде является нецелесообразным. Соответствующая семантика описывается в виде набора процедур ЯВУ, транслируемых при сборке ДТС компилятором ЦП, вызываемых из двоично-транслированных кодов.

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

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

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

Выделим основные свойства трансляторов, входящих в состав Lintel. Шаблонный транслятор не приспособлен для создания высокоэффективного кода, но зато'Обладает наивысшей скоростью работы и поддерживает точный контекст ИП на каждой отдельно взятой команде. Оптимизирующий транслятор может работать с различными уровнями оптимизации, в зависимости от набора применяемых на этом этапе преобразований. На момент написания диссертационной работы, в рамках Lintel велась реализация двух уровней оптимизаций. Уровень '00' выполняет только несложные оптимизации, но уже позволяет получить код намного превосходящий шаблонный по эффективности, однако при этом время трансляции значительно превышает показатели шаблонного транслятора. Уровень '01' позволяет задействовать аппаратуру "ЭЗМ" наиболее полным образом, однако работает значительно дольше даже по сравнению с уровнем '00'.

Для оценки эффективности работы Lintel, в последующих главах диссертационной работы приводятся результаты прогона тестовых задач на покомандном симуляторе модели машины архитектуры "ЭЗМ". Применявшийся тестовый набор включал в себя тесты пакета SPECint2000, пропускавшиеся на test и train наборах данных (164.gzip - далее по тексту работы 164.test и 164.train, 181.mcf - ISl.test и 181.train, 186.crafty - 186.test и 186.train, 197.parser - 197.test и 197.train, 255.vortex - 255.test и 255.train, 256.bzip2 - 256.test и 256.train, 300.twol! - 300.test и 300.train), а также подготовленные автором тесты (win31 и tcc2).

Тест win31 представляет собой раскрутку Microsoft Windows 3.1 в расширенном режиме из-под MS-DOS 6.22. Данный тест хорошо отражает работу ДТС в неблагоприятных для нее условиях начальной раскрутки ОС,

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

Тест tcc2 представляет собой сборку небольшого проекта на языке С, выполняемую инструментальными средствами пакета Borland Turbo С 2.0. Проект включает в себя около пятидесяти файлов исходного кода небольшого объема, по-отдельности транслируемых компилятором tec и затем собираемые библиотекарем tlib в единый архив. В этом тесте, множественные запуски компилятора хорошо отражают характер сборки современного ПО, обычно представленного в виде набора модулей из множества независимо транслируемых файлов. В то же время, небольшой объем каждого из файлов в отдельности в значительной степени осложняет работу ДТС, не давая компилятору исполняться достаточно долго для того, чтобы компенсировать затраты на оптимизирующую трансляцию его кода.

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

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

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

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

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

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

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

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

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

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

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

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

Необходимо также учитывать различную степень проявления воздействия размера единицы трансляции в зависимости от уровня оптимизаций. К примеру, в LIntel транслятор уровня 00 не производит ни if-conversion, ни прочие комплексные оптимизационные преобразования, и эффект от увеличения размера регионов сводится в основном к увеличению числа внутрирегионных переходов, тогда как на более высоких уровнях оптимизации эффект будет возрастать. В то же время, и замедление, вносимое в работу на уровне ОО линейно, тогда как на уровне 01 замедление компилятора уже заметно опережает рост региона. Подытоживая рассмотрение, сформулируем второй принцип построения адаптивной ДТС: методы формирования единиц трансляции могут выступать в роли дополнительно определяющего уровень оптимизаций спецификатора.

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

Возникающие нештатные ситуации при исполнении оптимизированного кода выявляются посредством самопроверок и аппаратной поддержки

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

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

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

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

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

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

Функционирование такой АДДТС протекает в соответствии со следующими схемами.

Основной поток исполнения:

1. Управление ИП переходит на очередной адрес ИП.

2. Анализируя профильную информацию, определяем необходимость перехода к шагу 5 для изменения уровня оптимизации исполняемого кода до 0„ew Первое исполнение кода можно считать переходом к уровню оптимизации 0^,:=0о.

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

4. Возвращаемся к шагу 1.

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

6. Полагая теперь для рассматриваемого кода переходим к шагу 3.

Поток обратных связей:

1. Функционирование АДДТС в целом порождает множество макрособытий, таких как создание и удаление трансляций, заполненность кэшей трансляций, и пр..

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

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

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

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

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

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

R=°+Z 1 к

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

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

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

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

Последовательно объединяя несколько линейных участков мы полу-

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

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

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

Можно отметить, что более сложная, трехуровневая схема {интерпретатор шаблонный -> 00) была успешно апробирована в ходе работ над инструментальной реализацией АДДТС уровня приложений, а в дальнейшем готовность уровня 01 оптимизаций для Lintel позволит , повысить глубину работы схемы и для него.

Наилучшие результаты работы ДТС демонстрируют тесты 164.test, 164.trainrl81.traInrl86.test,-I86.train,-197.test, 197.train, 255.test, 255-train, 256.test, 256.train и 300.train, во время исполнения которых более 80% времени работы Lintel тратится непосредственно на исполнение оптимизированного двоично-транслированного кода. Это свидетельствует об удачной локализации счетного ядра этих пакетов в серию регионов, позволивших достаточно быстро перевести его в оптимизированный двоично-транслированный код с последующим успешным связыванием большинства межрегиональных передач управления.

Тесты 181.test и 300.test являются двумя самыми короткими тестами из пакета SPECint2000, и достаточно низкая доля исполнения (45-55%) оптимизированного кода обусловлена малым размером их тестовых данных, так как полученные регионы не успевают проработать достаточно долгое время для того, чтобы уверенно перевесить время самой оптимизирующей трансляции. Хорошие показатели исполнения этих же тестов на более длинных train данных свидетельствуют о справедливости выдвину-

тых предположений.

Тест win31 - единственный из участвовавших в тестировании, в котором более 2% времени исполнения тратится на шаблонную трансляцию. Здесь сказывается работа задачи в неустановившемся режиме, обуславливающая активное знакомство системы с новыми кодами ИП. И тем не менее, даже при исполнении задачи с таким непостоянным характером работы в итоге более 50% времени работы Lintel приходится на исполнение оптимизированного кода, что можно считать достаточно хорошим результатом.

Тест tcc2, как и предполагалось, оказался самым серьезным испытанием для Lintel. Короткое время исполнения каждого из запусков компилятора по отдельности, свойственная большинству компиляторов "размазанность профиля по задаче, работа большой задачи в реальном режиме работы микропроцессора ИП под управлением DOS и связанные с этим высокий уровень потребления сервисов макроподдержки и чрезвычайно высокая нагрузка на системную поддержку - все это не позволило оптимизированному двоично-транслированному коду занять доминирующую позицию в профиле исполнения Lintel. Важной особенностью можно считать тот факт, что время самой оптимизирующей трансляции значительно превосходит время исполнения полученных оптимизированных кодов - характер задачи меняется столь стремительно, что оптимизированные коды просто не успевают отработать достаточное время для компенсации затрат на их получение. Введение демпфирующего коэффициента в метод расчета порогового значения счетчика АДДТС нацелено на решение именно этой проблемы, и позволит смягчить наблюдавшийся эффект.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ля в системе и размещать всю информацию непосредственно в файловой системе наперед заданной исходной ОС.

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

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

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

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

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

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

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

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

Наибольший эффект от введения БК был отмечен на тестах, демонстрировавших высокий уровень расходов на оптимизирующую трансляцию - так, тесты 181.test, 300.test, tcc2 и win31 продемонстрировали повышение эффективности работы системы в диапазоне 7-22%. В то же время, заметное ухудшение времени первого запуска для тестов 300.test и win31 (7-11%) объясняется проявившимися неэффективностями в текущей практической реализации прототипа БК и будет устранено в дальнейшем.

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

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

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

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

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

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

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

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

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

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

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

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

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

4. Реализована двухуровневая АДДТС уровня виртуальной машины с платформы IA-32 на платформу Е2К.

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

6. Реализованы несколько алгоритмов работы базы кодов для динамической ДТС уровня виртуальной машины с платформы IA-32 на платформу Е2К.

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

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

Основной вывод по результатам работы

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

СПИСОК РАБОТ, ОПУБЛИКОВАННЫХ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Ермолович A.B. Динамическое профилирование для двоично-транслирующей системы // Информационные технологии, №3, 2002, с. 9-13.

2. Ермолович A.B. База кодов как средство повышения эффективности динамической двоично-транслирующей системы // Информационные технологии, №9, 2003, с. 14-22.

3. Ермолович A.B. Применение базы кодов в динамической двоично-транслирующей системе - Высокопроизводительные вычислительные

системы и микропроцессоры, сборник научных трудов, выпуск 4, М., ИМВС РАН, 2003, с. 55-66.

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

5. Ермолович A.B. Технология выделения и последующей оптимизации регионов в двоично-транслируемом коде как средство повышения производительности вновь разрабатываемых систем динамической двоичной трансляции - Тезисы докладов Международной конференции

XXVII Гагаринские чтения, М., 2001.

6. Ермолович A.B. Применение базы данных двоично-транслированного кода для повышения производительности систем динамической двоичной трансляции - Тезисы докладов Международной конференции

XXVIII Гагаринские чтения, М., 2002.

7. Ермолович A.B. Метод выбора глобальных меток в динамически формируемых регионах двоично-транслируемого кода - Тезисы докладов Международной конференции XXIX Гагаринские чтения, М., 2003.

8. Ермолович A.B. Применение концепции региональной компиляции в динамической компоненте двоично-транслирующей системы - Тезисы докладов Международной конференции "РИ-2000", СПб., 2000.

9. Ермолович A.B. Специализированная база данных как средство повышения производительности оптимизирующей двоично-транслирующей системы - Тезисы докладов Международной конференции "РИ-2002", СПб., 2002.

!0. Ермолович A.B. Поддержка-механизма долговременного хранения трансляций для оптимизирующей двоично-транслирующей системы - Тезисы докладов Всероссийской научно-технической конференции НМТ-2002, М., 2002, Том 3, с. 36-37.

Патентная заявка США

И. Method of using a plurality of virtual memory spaces for providing efficient binary compatibility between a plurality of source architectures and a single target architecture. Inventors: Boris A. Babaian; Roman A. Khvatov; Alexander V. Ermolovich. Appl. No.: 10/453,448. Filed: June 2, 2003

Сдано в печать 20.11.03г. Формат 60x90/16 Объем 1,5 печл. Тираж 100 экз. Зак №22

Отпечатано в ООО «Эдэль-М» 105005, г.Москва, ул.Бауманская д.43/1

-, 1775 H975t

Введение

1 Эффективность двоично-транслирующих систем

1.1 Двоичная трансляция и перспективные архитектуры вычислительных систем.

1.2 Оптимизирующие системы двоичной трансляции.

1.3 Существующие системы двоичной трансляции.

1.4 Проблемы повышения эффективности.

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

1.6 Выводы.

2 Система "Lintel"

2.1 Архитектура "Эльбрус".

2.2 Схема двоичной трансляции на "Эльбрусе".

2.3 Особенности двоично-транслирующей системы "Lintel".

2.4 Шаблонная и оптимизирующая трансляции.

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

2.6 Выводы.

3 Адаптивность в двоично-транслирующей системе

3.1 Проблема адаптивности.

3.2 Построение адаптивной двоично-транслирующей системы.

3.3 Двухуровневая реализация.

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

3.5 Выводы. ф 4 База данных кода

4.1 Управление памятью в "Lintel".

4.2 Хранение двоично-транслированного кода в памяти.

4.3 Хранение двоично-транслированного кода на внешнем носителе

4.4 Структура базы данных кода.

4.5 Распознавание кода и загрузка.

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

4.7 Выводы.

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

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

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

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

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

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

Тем не менее, на протяжении целого ряда лет именно методы аппаратной поддержки использовались для достижения двоичной совместимости между различными архитектурами коммерчески успешных микропроцессоров. Двоичная совместимость на аппаратном уровне стала неотъемлемым атрибутом анонсов новых микропроцессоров, будь то Intel, Sun, AMD или IBM. Разработчики декларируют как минимум совместимость на уровне приложений [2], а как максимум - полную совместимость со всеми ранее созданными кодами для ранних моделей микропроцессоров этого семейства [3].

О масштабах возможных дополнительных затрат на совместимость на аппаратном уровне можно судить по современным микропроцессорам архитектуры IA-32, уже давно [4, 5] превратившихся из микропроцессоров с полным набором команд (CISC) в связку из суперскалярного ядра, представляющего собой микропроцессор с сокращенным набором команд (RISC), и аппаратного перекодировщика команд, разбивающего сложные CISC-инструкции на множество простых RISC-операций, уже непосредственно исполняемых этим ядром.

Однако подобные, весьма сложные, чисто аппаратные средства отнюдь не являются единственным способом обеспечения двоичной совместимости между различными моделями микропроцессоров. Реальную альтернативу им составляет техника двоичной трансляции [6, 7, 8] - высокопроизводительный программный метод обеспечения двоичной совместимости.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Научная новизна работы

К составляющим научную новизну диссертационной работы решениям можно отнести:

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

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

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

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

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

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

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

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

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

I»

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

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

• семейство инструментальных динамических двоичных трансляторов уровня приложений для переноса приложений платформы Solaris/IA-32 на модель микропроцессора "Эльбрус-ЗМ";

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

• ВК "Эльбрус-ЗМ", разработанный в ЗАО МЦСТ, обеспечивающий совместимость с архитектурной платформой IA-32 на уровне виртуальной машины.

Апробация

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

• международная конференция "Региональная Информатика - 2000" (Санкт-Петербург, 2000 г.);

• международная конференция "Региональная Информатика - 2002" (Санкт-Петербург, 2002 г.);

• международная молодежная научная конференция XXVI Гагаринские чтения (Москва, 2000 г.);

• международная молодежная научная конференция XXVII Гагаринские чтения (Москва, 2001 г.); ^

• международная молодежная научная конференция XXVIII Гагаринские чтения (Москва, 2002 г.);

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

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

Кроме того, результаты диссертационной работы докладывались и обсуждались на научно-технических семинарах ЗАО МЦСТ и ИМВС РАН.

Публикации

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

1. Ермолович А.В. Динамическое профилирование для двоично-транслирующей системы // Информационные технологии, №3, 2002, с. 9-13.

2. Ермолович А.В. База кодов как средство повышения эффективности динамической двоично-транслирующей системы // Информационные технологии, №9, 2003, с. 14-22.

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

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

5. Ермолович А.В. Технология выделения и последующей оптимизации регионов в двоично-транслируемом коде как средство повышения производительности вновь разрабатываемых систем динамической двоичной трансляции -Тезисы докладов Международной конференции XXVII Гагаринские чтения, М., 2001.

6. Ермолович А.В. Применение базы данных двоично-транслированного кода для повышения производительности систем динамической двоичной трансляции - Тезисы докладов Международной конференции XXVIII Гагаринские чтения, М., 2002.

7. Ермолович А.В. Метод выбора глобальных меток в динамически формируемых регионах двоично-транслируемого кода - Тезисы докладов Международной конференции XXIX Гагаринские чтения, М., 2003.

8. Ермолович А.В. Применение концепции региональной компиляции в динамической компоненте двоично-транслирующей системы - Тезисы докладов Международной конференции "РИ-2000", СПб., 2000.

9. Ермолович А.В. Специализированная база данных как средство повышения производительности оптимизирующей двоично-транслирующей системы - Тезисы докладов Международной конференции "РИ-2002", СПб., 2002.

10. Ермолович А.В. Поддержка механизма долговременного хранения трансляций для оптимизирующей двоично-транслирующей системы - Тезисы докладов Всероссийской научно-технической конференции НМТ-2002, М., 2002, Том 3, с. 36-37.

Кроме того, имеется патентная заявка США 10/453,448 (в соавторстве) по теме диссертации, поданная 2 июня 2003 года.

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

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

4.7. Выводы

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

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

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

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

Заключение

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

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

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

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

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

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

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

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

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

4. Реализована двухуровневая адаптивная динамическая двоично-транслирующая система уровня виртуальной машины с платформы IA-32 на платформу Е2К.

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

6. Реализованы несколько алгоритмов работы базы кодов для динамической двоично-транслирующей системы уровня виртуальной машины с платформы IA-32 на платформу Е2К.

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

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

Основной вывод по результатам работы

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

Личный вклад автора

Автором были выполнены:

• техническое проектирование подсистемы динамической поддержки и реализация алгоритмов ее функционирования при создании комплекса двоично-транслирующих систем с архитектуры IA-32 на архитектуру Е2К;

• реализация основного комплекса сервисов системной поддержки;

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

• реализация механизма базы данных двоично-транслированных кодов;

• разработка ряда архитектурных решений в составе ВК "Эльбрус-ЗМ", направленных на повышение эффективности работы рассматриваемых двоично-транслирующих систем (управление внешними прерываниями из пользовательского режима, специализированные расширения функциональности local APIC, асинхронное прерывание при коллизиях прямого доступа в память с выносом данных из памяти на регистры, эмуляция режима работы с маскированной линией А20 в устройстве управления памятью микропроцессора, механизм поддержания когерентности двоично-транслированных кодов при прямом доступе в память со стороны внешних устройств, интерфейс накопителя базы кодов).

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

2. UltraSPARC III Processor White Paper - http://www.sun.com/processors/ UltraSPARC-Ill/.

3. The AMD64 Computing Platform: Your Link to the Future of Computing

AMD64 White Paper, http://www.amd. com/us-en/Processors/ Productlnformation/O, ,3011893318996, 00.html.

4. Halfhill T.R. AMD Vs. Superman // Byte, November 1994.

5. Halfhill T.R. Intel's P6 // Byte, April 1995.

6. Рожков С.А. Двоичная трансляция и двоичная совместимость - Тезисы докладов Международной конференции XXV Гагаринские чтения, Том 1, М., 1999, с. 383384.

7. Silberman G.M., Ebcioglu К. An architectural framework for migration from CISC to higher performance platforms - In Proc. of the 1992 International Conference on Supercomputing, pp. 198-215, Washington, DC, July 1992, ACM Press.

8. Sites R., Chernoff A., Kirk M., Marks M., Robinson S. Binary Translation // Communications of the ACM, Vol. 36, №2, February 1993, pp. 69-81.

9. FlashPort product literature, AT&T Bell Laboratories, August 1994.

10. Intel, HP Make EPIC Disclosure // Microprocessor Report, Vol. 11, №14, Oct. 27, 1997.

11. Cifuentes С., Malhotra V. Binary Translation: Static, Dynamic, Retargetable? -Proceedings of the 1996 International Conference on Software Maintenance (ICSM '96), Monterey, CA, November, 1996.

12. Chernoff A., Hookway R. DIGITAL FX!32: Running 32-Bit x86 Applications on Alpha NT - Proceedings of the USENIX Windows NT Workshop Seattle, Washington, August 1997.

13. Chernoff A., Herdeg M„ Hookway R., Reeve C., Rubin N., Туе Т., Yadavalli S.B., Yates J. FX!32: A Profile-Directed Binary Translator // IEEE Micro, March/April 1998 (Vol. 18, №2), pp. 56-64.

14. Connectix Virtual PC - http://www.connectix.com.

15. Klaiber A. The technology behind Crusoe processors - Technical report, Transmeta Corp., Santa Clara, CA, January 2000.

16. Cramer Т., Friedman R., Miller Т., Seberger D., Wilson R., Wolczko M. Compiling Java Just in Time // IEEE Micro, May/June 1997 (Vol. 17, №3), pp. 36-43.

17. Ebcioglu K. et al. Dynamic Binary Translation and Optimization // IEEE Transactions on Computers, Vol. 50, №6, pp. 529-548, Jun 2001.

18. Drozdov A., Volkonski V. 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.

19. Krewell K. EPIC: Designed for the 21st Century - In-Stat/MDR EPIC Whitepaper, November 2002.

20. Bala V., Duesterwald E., Banerjia S. Transparent Dynamic Optimization: The Design and Implementation of Dynamo - HP Laboratories Cambridge, June 1999.

21. Merten M.C., Thiems M.S. An Overview of the IMPACT X86 Binary Reoptimization Framework - IMPACT Technical Report, IMPACT-98-05, University of Illinois, Urbana, IL 1998.

22. Рожков С.А. Методы двоичной трансляции с использованием аппаратных средств - Тезисы докладов конференции Мельниковские чтения, М., 1999 .

23. Рожков С.А. Надежность оптимизирующих двоично-транслирующих систем // Информационные технологии и вычислительные системы, №1, 1999, с. 14-22.

24. Gschwind М., Altman Е. Precise exceptions in dynamic compilation - In Proc. of the 2002 Workshop on Compiler Construction, LNCS, Grenoble, France, 2002.

25. Рожков С.А. Программные методы исполнения двоичных кодов на основе аппаратной поддержки - Диссертация на соискание ученой степени кандидата технических наук, М., НИИ "Вычислительные Технологии", 1999.

26. Performance Of Connectix Virtual PC - http://www.macspeedzone.com/ archive/Comparison/VPC.html.

27. QEMU CPU Emulator - http://fabrice.bellard.free.fr/qemu.

28. Hohensee P., Myszewski M., Reese D. Wabi Cpu Emulation - Hot Chips VIII Proceedings, Stanford, August 1996.

29. Sun delivers best-of-both-worlds with SunPCi and SunForum PC interoperability solutions - Sun Microsystems, Inc. press release, February 1999, http://www. sun.com/smi/Press/sunflash/9902/sunflash.990202.3.html.

30. Altman E., Gschwind M., Sathaye S., Kosonocky S., Bright A., Fritts J., Ledak P., Appenzeller D., Agricola C., Filan Z. BOA: The Architecture of a Binary Translation Processor - IBM Research Report RC 21665 (97500), 16 December 2000.

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

32. Diefendorff K. The Russians Are Coming // Microprocessor Report, Vol. 13, №2, Feb. 15, 1999.

33. Бабаян Б.А., Волконский В.Ю. и др. Высокопроизводительный центральный процессор МВК Эльбрус-3 с архитектурой широкого командного слова - Семейство моделей многопроцессорных вычислительных комплексов "Эльбрус" -состояние и перспективы: Тез. докладов Всесоюзного научно-технического семинара НПО СВТ, ИТМ и ВТ АН СССР, ИЦ НПО АСУ "Москва", М. 1990, с. 24-25.

34. Babaian В., Volkonsky V. et al. Wide Instruction Word Architecture Central Processor - United States Patent №5418975, May 23, 1995; PCT Pub. Date: Oct. 15, 1992; PCT Filed: Aug. 20, 1991.

35. Волконский В.Ю., Тихонов В.Г., Эльцин Е.А., Матвеев П.Г. Реализация объектно-ориентированных языков программирования, гарантирующая межмодульную защиту - Высокопроизводительные вычислительные системы и микропроцессоры, сборник научных трудов, выпуск 4, Мм ИМВС РАН, 2003, с. 18-37.

36. IA-32 Intel Architecture Software Developer's Manual, Vol. 1-3, Intel Corp.

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

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

39. Muchnick S.S. Advanced Compiler Design and Implementation - Morgan Kaufmann Publishers, Inc., SF, California, 1997.

40. Ball Т., Larus J.R. Efficient Path Profiling - MICRO-29, December 1996.

41. Chang P.P. Trace selection for compiling large С application programs to microcode - MICRO-21, November 1988.

42. Ермолович А.В. Динамическое профилирование для двоично-транслирующей системы // Информационные технологии, №3, 2002, с. 9-13.

43. Anderson J.M., Berc L.M., Dean J., Ghemawat S., Henzinger M.R., Leung S.A., Sites R.L., Vandevoorde M.T., Waldspurger C.A., and Weihl W.E. Continuous profiling: Where have all the cycles gone? // ACM Transactions on Computer Systems, Vol. 15, №4, pp. 357-390, November 1997.

44. Sastry S.S., Bodik R., and Smith J.E. Rapid profiling via stratified sampling - In International Symposium on Computer Architecture (ISCA), 2001, pp. 278-289.

45. Conte T.M., Menezes K.N., and Hirsch M.A. Accurate and practical profile-driven compilation using the profile buffer - In Proc. 29th Annual Intl. Symp. on Microarchitecture, pp. 36-45, Paris, France, Dec. 1996.

46. Hank R.E. Region Based Compilation - Doctoral thesis, University of Illinois at Urbana Champaign,1996.

47. Hank R.E., Hwu W.W., Rau B.R. Region-Based Compilation: An Introduction and Motivation - MICRO-28, December 1995.

48. Ермолович А.В. Применение концепции региональной компиляции в динамической компоненте двоично-транслирующей системы - Тезисы докладов Международной конференции "РИ-2000", СПб., 2000.

49. Ермолович А.В. Технология выделения и последующей оптимизации регионов в двоично-транслируемом коде как средство повышения производительности вновь разрабатываемых систем динамической двоичной трансляции - Тезисы докладов Международной конференции XXVII Гагаринские чтения, М., 2001.

50. Ермолович А.В. Метод выбора глобальных меток в динамически формируемых регионах двоично-транслируемого кода - Тезисы докладов Международной конференции XXIX Гагаринские чтения, М., 2003.

51. Ермолович А.В. Применение базы данных двоично-транслированного кода для повышения производительности систем динамической двоичной трансляции

Тезисы докладов Международной конференции XXVIII Гагаринские чтения, М., 2002.

52. Ермолович А.В. Поддержка механизма долговременного хранения трансляций для оптимизирующей двоично-транслирующей системы - Тезисы докладов Всероссийской научно-технической конференции НМТ-2002, Том 3, М., 2002, с. 36-37.

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

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

55. Ермолович А.В. База кодов как средство повышения эффективности динамической двоично-транслирующей системы // Информационные технологии, №9, 2003, с. 14-22.

Патентная заявка США

56. Method of using a plurality of virtual memory spaces for providing efficient binary compatibility between a plurality of source architectures and a single target architecture. Inventors: Boris A. Babaian; Roman A. Khvatov; Alexander V. Ermolovich. Appl. No.: 10/453,448. Filed: June 2, 2003

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

4. Halfhill T.R, AMD Vs. Superman / / Byte, November 1994.

5. Halfhill T.R. Intel's P6 / / Byte, April 1995.

6. Рожков с.A. Двоичная трансляция и двоичная совместимость - Тезисы докладов Международной конференции XXV Гагаринские чтения. Том 1, М., 1999, с. 383-384.

7. Silberman G.M., Ebcioglu К. An architectural framework for migration from CISC to higher performance platforms - In Proc. of the 1992 International Conference on Supercomputing, pp. 198-215, Washington, DC, July 1992, ACM Press.

8. Sites R., Chernoff A., Kirk M., Marks M., Robinson S. Binary Translation / / Communications of the ACM, Vol. 36, №2, February 1993, pp. 69-81.

9. FlashPort product literature, AT&T Bell Laboratories, August 1994.

10. Chernoff A., Hookway R. DIGITAL FX!32: Running 32-Bit x86 Applications on Alpha NT - Proceedings of the USENIX Windows NT Workshop Seattle, Washington, August 1997.

11. Chernoff A., Herdeg M., Hookway R., Reeve C„ Rubin N.. Туе Т., Yadavalli S.B., Yates J. FXI32: A Profile-Directed Binary Translator / / IEEE Micro, March/April 1998 (Vol. 18, №2), pp. 56-64.

13. Klaiber A. The technology behind Crusoe processors - Technical report, Transmeta Corp., Santa Clara, CA, January 2000.

14. Cramer Т., Friedman R., Miller Т., Seberger D., Wilson R., Wolczko M. Compiling H Java Just in Time / / IEEE Micro, May/June 1997 (Vol. 17, №3), pp. 36-43.

15. Ebcioglu K. et al. Dynamic Binary Translation and Optimization / / IEEE Transactions on Computers, Vol. 50, №6, pp. 529-548, Jun 2001,

16. Drozdov A., Volkonski V, et al. The Optimizing Compiler for the Elbrus-

17. Supercomputer - International Congress on Computer Systems and Applied Mathematics. CSAM'93, Abstracts, St. Petersburg, July 19-23, 1993, pp. 127-128.

18. Krewell K. EPIC: Designed for the 21st Century - In-Stat/MDR EPIC Whitepaper, November 2002.

19. Bala V., Duesterwald E., Banerjia S. Transparent Dynamic Optimization: The Design and Implementation of Dynamo - HP Laboratories Cambridge, June 1999.

20. Рожков А. Надежность оптимизирующих двоично-транслирующих систем / / Информационные технологии и вычислительные системы, №1, 1999, с, 14-22.

21. Gschwind М., Altman Е. Precise exceptions in dynamic compilation - In Proc. of the 2002 Workshop on Compiler Construction, LNCS, Grenoble, France, 2002,

22. Рожков C.A. Программные методы исполнения двоичных кодов на основе аппаратной поддержки - Диссертация на соискание ученой степени кандидата технических наук, М., НИИ "Вычислительные Технологии", 1999,

25. Hohensee P., Myszewski M., Reese D. Wabi Cpu Emulation - Hot Chips VIII Proceedings, Stanford, August 1996.

26. Altman E., Gschwind M., Sathaye S., Kosonocky S., Bright A., Fritts J., Ledak P., Appenzeller D., Agricola C , Filan Z. BOA: The Architecture of a Binary Translation Processor - IBM Research Report RC 21665 (97500), 16 December 2000,

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

28. Diefendorff K. The Russians Are Coming / / Microprocessor Report, Vol. 13, №2, Feb. 15, 1999. •116-#

29. Babaian В., Volkonsky V. et al. Wide Instruction Word Architecture Central Processor - United States Patent №5418975, May 23, 1995; PCT Pub. Date: Oct. 15, 1992; PCT Filed: Aug. 20, 1991.

30. IA-32 Intel Architecture Software Developer's Manual, Vol. 1-3, Intel Corp..

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

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

33. Muchnick S.S. Advanced Compiler Design and Implementation - Morgan Kaufmann Publishers, Inc., SF, California, 1997.

34. Ball Т., Larus J.R. Efficient Path Profiling - MICRO-29, December 1996.

35. Chang P.P. Trace selection for compiling large С application programs to microcode - MICRO-21, November 1988. -117-i|^ 42. Ермолович А.В. Динамическое профилирование для двоично-транслирующей системы / / Информационные технологии, №3, 2002, с, 9-13.

36. Sastry S.S., Bodfk R., and Smith J.E. Rapid profiling via stratified sampling - In International Symposium on Computer Architecture (ISCA), 2001, pp. 278-289.

37. Conte T.M., Menezes K.N., and Hirsch M.A. Accurate and practical profile- driven compilation using the profile buffer - In Proc. 29th Annual Intl. Symp. on Microarchitecture, pp. 36-45, Paris, France, Dec. 1996.

38. Hank R.E. Region Based Compilation - Doctoral thesis. University of Illinois at Urbana Champaign,1996. 1^ 47. Hank R.E., Hwu W.W., Rau B.R. Region-Based Compilation: An Introduction and Motivation - MICRO-28, December 1995.

39. Ермолович А.В. Применение концепции региональной компиляции в динамической компоненте двоично-транслирующей системы - Тезисы докладов Международной конференции "РИ-2000", СПб., 2000.

40. Ермолович А.В. Метод выбора глобальных меток в динамически формируемых регионах двоично-транслируемого кода - Тезисы докладов Международной конференции XXIX Гагаринские чтения, М., 2003.

41. Ермолович А.В. Применение базы данных двоично-транслированного кода для , ^ повышения производительности систем динамической двоичной трансляции --118-j|||r* Тезисы докладов Международной конференции XXVIII Гагаринские чтения, М., 2002.

42. Ермолович А.В. Поддержка механизма долговременного хранения трансляций для оптимизирующей двоично-транслирующей системы - Тезисы докладов Всероссийской научно-технической конференции НМТ-2002, Том 3, М., 2002, с. 36-37.

43. Ермолович А.В. Специализированная база данных как средство повышения производительности оптимизирующей двоично-транслирующей системы - Тезисы докладов Международной конференции "РИ-2002", СПб., 2002.

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

45. Ермолович А.В. База кодов как средство повышения эффективности динамической двоично-транслирующей системы / / Информационные технологии, №9, 2003, с. 14-22. Патентная заявка США