Курсовые и дипломные работы

Курсовые и дипломные работы

Список некоторых курсовых и дипломных работ, выполненных студентами во время стажировки в компании "Эксельсиор". Все перечисленные работы были представлены на кафедре программирования ММФ НГУ и кафедре АФТИ ФФ НГУ и получили оценку "отлично".

2017

Автоматическое управление памятью с неполным подстчетом ссылок

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

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

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

Работа выполнялась в рамках проекта Excelsior RVM, статического компилятора и среды исполнения Java программ. Для проверки построенной модели на практике, дипломник реализовал прототип подсистемы управления памятью, позволющий выполнять локальные сборки мусора, реализовав необходимые компоненты в статическом и оперативном компиляторах, а также в среде исполнения. Это позволило испытать полученную систему на достаточно сложных современных Java-приложениях и стандартных тестах производительности. Приведенные в тексте диплома экспериментальные результаты показывают, что предложенный подход к инкрементальной сборке мусора имеет хорошие перспективы для внедрения в промышленную эксплуатацию – от 30 до 70% объектов, выделенных в динамической памяти могут быть утилизированы путем локальных сборок мусора.

2016

Разработка алгоритма эффективной расстановки точек переключения в машинном коде

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

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

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

Эффективная интерпретация объектно-ориентированных программ в среде исполнения с ограничениями по безопасности

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

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

Непосредственным практическим следствием выполнения данной квалификационной работы является создание возможности для полнофункциональной реализации языка Java на такой закрытой платформе, как Apple iOS. Работа выполняется с использованием инфраструктуры Excelsior RVM - статического компилятора и управляемой среды для языка Java.

2015

Внутрипотоковая сборка мусора

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

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

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

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

2015

Динамическая генерация метаданных для объектно-ориентированных программ в управляемых средах

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

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

2016

Адаптивная сборка мусора

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

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

Работа выполнялась в рамках проекта Excelsior RVM, статического компилятора и среды исполнения Java программ. В качестве альтернативного существующему в системе «классическому» компактизатору, был реализован дополнительный, использующий идеи IBM Moving Compactor - одного из алгоритмов, появившихся в последнее десятилетие. Следует отметить, что границы применимости этого алгоритма были расширены – он был адаптирован для динамической пямяти с блочной структурой, что может квалифицироваться как научная новизна. В тексте работы приведен анализ достоинств и недостатков классического и нового алгоритмов, а также сформулированы условия применения этих алгоритмов поочередно либо совместно с целью повышения производительности.

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

2012

Точная сборка мусора

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

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

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

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

2012

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

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

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

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

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

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

2011

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

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

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

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

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

2010

Повышение надежности языков системного программирования

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

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

В рамках дипломной работы приведен достаточно интересный обзор языков, включающий Modula-3, D, Spec#, Sync#, Go, Vault, и возможностей, предоставляемых небезопасными модулями языка C#. В большинстве рассмотренных работ предпринимается попытка «повысить» уровень языка путем добавления средств, присущих языкам с управляемым кодом, однако надежность взаимодействия между частями системы, использующим как высокоуровневые, так и низкоуровневые средства авторами этих языков зачастую не рассматривалась.

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

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

2010

Оптимизация времени старта Java-приложений

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

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

Реализация предложенных оптимизаций была выполнена на базе Excelsior RVM, системы статической компиляции и среды исполнения для Java SE. Были реализованы все необходимые системные компоненты в оперативном компиляторе, компоновщике исполняемых файлов и среде исполнения Javа, что позволило проверить эффективность предложенных методов на реальных Java-приложениях.

2010

Реализация модульной инфраструктуры OSGi на уровне виртуальной машины Java

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

Изначально, OSGi была разработана для встроенных систем, но в настоящее время получила широкое промышленное распростанение как для клиентских, так и для серверных приложений. Достаточно упомянуть, что Eclipse Rich Client Platform (платформа для разработки клиентских приложений с развитой функциональностью) основана на одной из реализаций OSGi. Кроме того, ведущие производители серверов приложений Java (Java EE application servers) уже перешли или перейдут в ближайшее время на компонентную модель OSGi.

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

Целью работы является проектирование и реализация динамической модульной системы на базе проекта Excelsior RVM, статического компилятора и среды исполнения Java программ. Кроме того, в качестве экспериментальных платформ будут взяты Equinox Runtime (реализация OSGi) и базирующаяся на нем система Eclipse.

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

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

2009

Декомпиляция Java-байткода с восстановлением структур обработки исключений

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

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

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

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

2009

Спецификация и реализация сборки мусора по поколениям

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

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

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

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

Экспериментальные результаты, подтверждающие эффективность реализованного алгоритма сборки мусора были получены на базе системы Excelsior RVM, статического компилятора и среды исполнения для платформы Java SE.

Эта работа отмечена дипломом и медалью Министерства образования и науки РФ "За лучшую студенческую научную работу"

2007

Эффективная кодогенерация операций вещественной арифметики языка Java

Спецификация языка Java требует соблюдения стандарта IEEE 754 при реализации операций вещественной арифметики. Это существенно затрудняет эффективную кодогенерацию для младших моделей процессоров архитектуры x86 (IA-32), использующихся в настоящее время во встроенных системах. Основную трудность представляет требование к точности вычислений, при котором результат каждой операции (в том числе промежуточный) должен быть приведен к точности типа операндов. Целью работы является проектирование и реализация алгоритмов статического анализа на управляющем графе процедуры, осуществляющих глобальную оптимальную расстановку операций приведения и/или переключения точности АЛУ (FPU). Также в работе решена задача распределения регистров (элементов стека FPU) с требованием корректности к точности вычислений. В работе представлено описание разработанного алгоритма и показано, что данная техника позволяет улучшить производительность программ. Также дается обзор предшествующих работ, посвященных расстановке операций переключений точности АЛУ. Работа выполнена в рамках проекта Excelsior RVM, статического компилятора и среды исполнения Java программ.

2007

Глобальное планирование оптимизаций открытой подстановки методов

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

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

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

2007

Построение локальных трасс и их применение для машинно-зависимых оптимизаций Java-программ

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

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

В работе должен быть сделан полный обзор предшествующих работ и представлены результаты адаптивной оптимизации стандартных тестов производительности и промышленных Java приложений с использованием off-line profile. Работа выполняется в рамках проекта Excelsior RVM, статического компилятора и среды исполнения для платформы Java SE.

2006

Комплексный подход к задаче распределения регистров: оптимальная расстановка присваиваний

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

2005

Усовершенствование механизма финализации в модели динамической памяти языка Java

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

Предполагается дать обзор ранее сделанных в этой области работ и предложить обоснование корректности реализованного алгоритма, опираясь на спецификацию языка Java. Работа выполняется в рамках проекта Excelsior RVM, статического компилятора и среды исполнения для платформы Java SE.

2003

Межпроцедурный типовый анализ Java программ

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

Кроме того, в работе должны быть предложены дальнейшие оптимизации, использующие результаты типового анализа, такие как раскрытие виртуальных вызовов, удаление проверок времени исполнения (Java run-time checks) и т.д. Предполагается дать обзор ранее сделанных в этой области работ и предложить обоснование корректности реализованного алгоритма, опираясь на спецификацию языка Java. Работа выполняется в рамках проекта Excelsior RVM, статического компилятора и среды исполнения для платформы Java SE.

2003

Адаптивные оптимизации Java программ

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

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

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

2003

Квазистатическая компиляция

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

2003

Оптимизации на этапе компоновки

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

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

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

2002

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

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

  • разработан алгоритм анализа, выявляющий возможность удаления TCF-блока, в том числе неявных try-finally блоков в конструкциях синхронизации;
  • описаны действия по удалению TCF-блока, включая трансформацию TCF-блока и опасных для него операций;
  • разработана формальная модель исполнения Java-программы с исключениями;
  • в терминах этой формальной модели описана трансформация программы, соответствующая удалению TCF-блоков;
  • сформулирована и доказана теорема о корректности этой трансформации;
  • данная оптимизация была реализована в компиляторе Excelsior RVM с ограничением на класс опасных инструкций, позволяющих удалить около 90% TCF-блоков от числа принципиально поддающихся данной оптимизации.

2002

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

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

Java - объектно-ориентированный язык, имеющий широкий набор динамических возможностей, в частности, метаязыковые средства (Reflection API, Java Native Interface). При статической компиляции основной груз поддержки метаязыковых средств ложится на систему поддержки времени выполнения (RTS).

В рамках работы разработаны:

  • Полная поддержка Reflection API в составе RTS.
  • Полная поддержка Java Native Interface в составе RTS.
  • Эффективное построение метатиповой информации.
  • Оптимизации, проводимые на стадии компоновки, позволяющие уменьшить объем памяти, занимаемый метатиповой информацией, а также ускоряющие загрузку приложений.

При разработке особое внимание было уделено эффективности реализации.

2001

Использование принципов ООП при создании транслятора

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

2001

Языково-зависимые оптимизации для Java

Данная работа представляет собой попытку ответить на вопрос "как улучшить качество оптимизации кода для современных объектно-ориентированных языков?". Рассматривается язык Java, как пример широко распространенного языка, обладающего развитыми объектно-ориентированными средствами. В работе исследовано использование "классических" методов оптимизации и анализа в применении к языку Java, выявлены причины ограничений на применимость таких методов и разработаны способы преодоления этих ограничений, рассмотрены новые классы оптимизаций. Эта задача интересна как теоретически, с точки зрения исследования вопросов оптимизации объектно-ориентированных языков, так и практически, с точки зрения генерации эффективного машинного кода на различных платформах. Практическим результатом работы является реализация разработанных методов в промышленном компиляторе Excelsior RVM.

2001

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

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

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

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

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

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

2000

Эффективная кодогенерация средств структурной обработки исключительных ситуаций, 2000

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

2000

Генерация блоков try-catch-finally в оптимизирующем компиляторе с языка Java

Поддержка исключительных ситуаций в языке Java, реализованная как поддержка конструкции try{:} catch{:} finally{:} - бесспорно, одно из мощнейших средств, предоставляемых этим языком. Вместе с тем общепризнанно, что данная конструкция является одним из <наименее структурных> средств программирования. В частности, она достаточно нетривиально переводится на язык конструкций if-then-loop-break, каковыми (в каком-то смысле) являются машинные языки различных процессоров. Данная задача интересна как теоретически, с точки зрения исследования самой системы обработки исключительных ситуаций, так и практически, с точки зрения генерации оптимального машинного кода на различных платформах.

1999

Коррекция программ во время исполнения

Целью данной работы является реализация системы динамической коррекции исполняемого кода телефонной станции Meridian, работающей под управлением системы VxWorks. Языками, на которых написано программное обеспечение телефонной станции, являются C/C++.

1999

Низкоуровневая оптимизация машинного кода для процессоров с конвейерной архитектурой в системе программирования XDS

Работа посвящена разработке алгоритма низкоуровневой оптимизации кода путем переупорядочивания инструкций, применяемой для процессоров с конвейерной архитектурой, и реализации данного алгоритма для процессора PowerPC 604 в системе XDS. В результате работы разработан эффективный эвристический алгоритм, точность которого составляет в среднем 70% от оптимального решения, что позволило улучшить временную характеристику генерируемого кода в системе XDS в среднем на 3,5%, при этом общее время трансляции увеличилось всего на 4%.

1998

Трансляция файлов заголовков языка Си в модули определений языка Модула‑2

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

1996

Настраиваемая среда отладки

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

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

  • В рамках системы разработки программного обеспечения XDS для платформы Intel-x86 для операционных систем OS/2 Warp, Windows 95/NT были реализованы интегрированный полнофункциональный символьный отладчик XD, позволяющий отлаживать программы также и в удаленном режиме кросс-отладки, два профилировщика разных типов, средства отображения состояния программы при возникновении во время ее работы исключительных ситуаций.
  • В рамках кросс-системы программирования для встроенных систем для платформы VAX с эмулируемой целевой машиной (интерпретатором) был реализован интегрированный полнофункциональный символьный отладчик DVX с поддержкой моделируемых внешних устройств.

1997

Интерпретатор языка отладки встроенных систем

Работа описывает разработку и реализацию интерпретатора языка отладки встроенных систем. Данная дипломная работа выполнялась в рамках проекта СОКРАТ, который предполагает создание среды поддержки разработки программ для встроенных ЭВМ. Проект СОКРАТ содержит многие компоненты, одной из которых является система отладки и тестирования (СОТ), предназначенная для отладки и тестирования одной или нескольких взаимосвязанных бортовых программ, разработанных на языке Ассемблера для БЦВМ типа Салют-4/6. СОТ содержит несколько частей, в частности, интерпретатор системы команд БЦВМ типа Салют-4/6, диалоговый отладчик, позволяющий отлаживать программы в интерактивном режиме, а также интерпретатор языка пакетной отладки, предназначенный, в первую очередь, для тестирования бортовых программ и отслеживания стабильности работы программ при внесении в них каких-либо изменений. В работе рассказано о принципах работы всей системы и при этом особое внимание уделено частям, созданным лично автором.

1995