Адрес:
109004, г. Москва,
ул. А. Солженицына,
дом 25.
Факс:
+7(495) 912-15-24
E-mail:
Отдел «Компиляторных технологий»
Проекты
1. Проект ParJava.
ParJava - интегрированная среда, обеспечивающая высокопродуктивную разработку параллельных Java-программ для кластерных систем.
- Создан итеративный технологический процесс разработки параллельных программ в среде ParJava, базирующийся на модели параллельной программы и возможности ее интерпретации. Это позволило перенести большую часть разработки на инструментальный компьютер и значительно сократить период отладки и доводки параллельной программы. Среда ParJava интегрирована в среду разработки Eclipse.
подробнее - Реализован пакет MPI для среды Java как «привязка» к реализации стандарта MPI на языке C. Разработан и реализован протокол создания контрольных точек.
подробнее - Технологический процесс апробирован на реальных приложениях, в том числе, совместно с ИФЗ РАН моделирование процесса зарождения торнадо.
подробнее
2. Поиск дефектов в программах при помощи статического анализа исходного кода.
Целью проекта является создание системы автоматического обнаружения дефектов в программах при помощи статического анализа исходного кода. Разрабатываемая система позволяет анализировать программы на Си и Си++, не имеет ограничений на размер анализируемой программы, и обнаруживает такие дефекты, как переполнение буфера, разыменование нулевого указателя, уязвимость форматной строки.
3. Проект «Квант».
Целью проекта «Квант» является исследование и разработка методов анализа бинарного кода программ, позволяющих получать высокоуровневое описание алгоритма и выявлять недекларированные возможности. Работы по проекту были начаты летом 2007 по контракту с ФГУП «НИИ «Квант».
В выполнении исследований программного обеспечения, оформленного в виде готового к работе бинарного кода, часто без исходных текстов, заинтересованы многие организации, решающие задачи сертификации ПО, а также проблемы отладки своих разработок или их совместимости с другими программами и системами. Всем им требуется проводить анализ бинарного кода различных программ, как по отдельности, так и в комплексе со всей средой исполнения компьютера, иногда вплоть до самого низкоуровневого кода, относящегося к операционной системе. Целью таких исследований является получение информации об особенностях реализации алгоритмов, восстановление реализации этих алгоритмов и их представление в понятном аналитику виде, восстановление протоколов обмена информацией и форматов данных, а также поиск недекларированных возможностей, ошибок и уязвимостей.
Развитие методов защиты программного кода, заметно усилившееся в последние годы, не позволяет проводить исследования, используя только статические методы анализа. Отметим только некоторые из них: упаковка/шифрование кода, использование виртуальных машин, применение обфускации. По отдельности и, особенно, в комбинации эти способы защиты делают статический анализ совершенно неэффективным вследствие значительной трудоемкости, в результате чего аналитик вынужден применять динамические средства анализа, такие как отладчик и трассировщик. Однако на данный момент для динамического анализа нет доступных средств автоматизации труда, и практически все действия выполняемые аналитиком являются ручными операциями.
Описанная ситуация послужила основанием для выбора динамического подхода в качестве отправной точки для анализа защищенного бинарного кода. Разрабатываемые в проекте «Квант» программные средства для анализа бинарного кода реализуются в рамках программной среды TrEx. На данный момент среда поддерживает две целевые платформы: Intel 64 и MIPS 64.
Возможности среды TrEx позволяют решать задачу восстановления алгоритма, преодолевая при этом комплекс средств защиты от анализа. Основным языком разработки является C++. Среда рассчитана на работу под ОС Windows. Модульный подход к организации среды, открытый интерфейс разработчика и доступность функционала в скриптовом языке Lua и позволяют выполнять быстрое прототипирование специфических для каждого отдельного случая алгоритмов анализа.
4. Исследование и разработка компиляторных методов, обеспечивающих повышение продуктивности программирования для графических акселераторов (GPU) при решении задач общего назначения.
В настоящее время актуальной является задача об организации вычислений на специализированных архитектурах, содержащих большое количество параллельно работающих процессоров на одном чипе. Примерами таких архитектур являются IBM Cell, в которой предусмотрено восемь специализированных процессоров SPE, и графические акселераторы компаний AMD и Nvidia, содержащие десятки потоковых мультипроцессоров. В любой из этих систем также имеется несколько видов оперативной памяти с различным уровнем доступа (локальная, общая) и показателями латентности и пропускной способности. Пиковая производительность этих систем более чем на порядок превосходит производительность современных процессоров общего назначения при схожей стоимости, а энергии при этом тратится всего в 2-3 раза больше.
Для того, чтобы эффективно организовать параллельные вычисления на таких архитектурах, программисту необходимо явно выделить процедуры, которые будут выполняться параллельно, и организовать распределение потока данных между ними, а также между отдельными процессорами. Для этого компаниями-разработчиками архитектур предлагаются различные решения. Так, программирование для систем на базе процессоров Cell осуществляется на языках Cи/Cи++ с использованием библиотеки pthreads, а за организацию потока данных программист отвечает сам. Для графических акселераторов компанией Nvidia предложена технология CUDA, в которой программист использует расширение языка Си для явного распределения данных по регионам памяти, а параллельных потоков выполнения по мультипроцессорам. Компанией AMD предложен язык Brook+, в котором язык Си расширен конструкциями поэлементной обработки потоков данных. Компания Intel предлагает модель программирования Ct, расширяющая язык Си++ параллельными операциями над массивами и соответствующими типами.
Описанные технологии программирования дают возможность организовать вычисления на специализированных архитектурах, но не упрощают программирование в достаточной степени, чтобы обеспечить широкое применение этих архитектур для параллельных вычислений. Для этого необходимы компиляторные решения, облегчающие для программиста прежде всего организацию потока данных и написание параллельно работающего кода: комбинация языковых расширений и оптимизаций компилятора. Институтом системного программирования РАН совместно с Кембриджским университетом ведется проект по разработке таких компиляторных решений для графических акселераторов, спонсируемый Российским фондом фундаментальных исследований (РФФИ).
5. Разработка и реализация в GCC планировщика команд с поддержкой конвейеризации циклов для архитектур с явно выраженным параллелизмом (2006-2008г.).
Архитектура EPIC (Explicitly Parallel Instruction Computer – архитектура с явным параллелизмом команд) обладает большими возможностями параллельного выполнения команд. К ним относятся наличие большого количества функциональных устройств и регистров, спекулятивное и условное выполнение, вращающиеся регистры и предзагрузка значений. При этом вся работа по использованию этих возможностей возлагается на компилятор – сам процессор лишь выполняет команды в точном соответствии с тем порядком, который заранее был определен при компиляции. Поэтому для достижения высокой производительности на данной архитектуре необходимо прежде всего оптимизировать порядок выполнения команд, максимально используя доступные функциональные устройства и возможности процессора по параллельному выполнению. Эту задачу решает компиляторная оптимизация, называемая планированием команд.
В ходе проекта по оптимизации компилятора GCC для процессора Itanium был разработан новый планировщик команд, который позволяет находить и эффективно использовать имеющийся в программе параллелизм на уровне команд. Разработанный алгоритм планирования поддерживает спекулятивное и условное выполнение команд, а также позволяет эффективно выполнять конвейеризацию циклов, в том числе таких, в теле которых имеется большое число ветвлений, а также вложенных циклов.
По результатам тестирования алгоритма планирования на платформе Intel Itanium было получено среднее ускорение в 3-4% на пакете тестов SPEC FP 2000 (на отдельных тестах до 10%). Разработанный планировщик был принят для включения в компилятор GCC версии 4.4 как планировщик по умолчанию для архитектуры Itanium для уровня оптимизации –O3.
Результаты исследований неоднократно были представлены на конференции разработчиков GCC Developers’ Summit, конференции Gelato, а также на семинарах по архитектуре EPIC конференций PACT и CGO.
6. Улучшение алгоритма поворотного модульного планирования (swing modulo scheduling) в GCC для Itanium (2007г.).
Алгоритм поворотного модульного планирования (swing modulo scheduling) является одним из алгоритмов конвейеризации циклов. Для своей эффективной работы модульному планировщику требуется информация о зависимостях по данным, а также расстояние в пространстве итераций между обращениями к памяти. В GCC имеется два анализатора зависимостей, реализованных соответственно на уровнях внутреннего представления Tree-SSA и RTL. Так как модульный планировщик работает на уровне RTL, он использует результаты анализатора именно этого уровня. Однако RTL-анализатор обладает существенными недостатками, которые могут быть устранены при использовании результатов анализа более высокого уровня Tree-SSA, которые, в свою очередь, не могут быть напрямую использованы планировщиком на уровне RTL из-за отсутствия соответствующих механизмов обмена информацией между этими уровнями.
Таким образом, цель проекта состояла в анализе недостатков используемых методов анализа зависимостей с точки зрения модульного планирования, а также разработке и реализации механизмов сохранения и распространения информации, полученной в ходе анализа зависимостей с уровня Tree-SSA на RTL. Основной сложностью при этом являлось обеспечение корректного сохранения информации в течение всех оптимизаций на обоих уровнях внутреннего представления, выполняющихся между Tree-SSA анализом зависимостей и использованием его результатов в модульном планировщике на RTL.
В результате реализации проекта удалось увеличить производительность на наборе тестов SPEC FP в среднем на 1.2%, при этом на некоторых тестах достигнуто ускорение 11%.
Работа поддержана грантом российского отделения компании Intel, а также грантом компании Google в рамках проекта Google Summer of Code.
7. Добавление поддержки спекулятивного выполнения по данным и управлению для целевой архитектуры Itanium в компиляторе GCC (2005г.).
Целью проекта являлась реализация в компиляторе GCC специфических для архитектуры Intel Itanium техник спекулятивного выполнения по данным и управлению. Задачи, решенные в ходе выполнения проекта включают в себя изменение анализа зависимостей для создания спекулятивных зависимостей, доработка существующего планировщика команд с тем, чтобы он мог создавать команды спекулятивного выполнения, а также добавление в описание целевой архитектуры компилятора соответствующих команд и функций. Добавление поддержки спекулятивного выполнения позволило на наборе тестов SPEC FP 2000 получить в среднем ускорение 2.5%, достигающее 20% на отдельных тестах. Работа была одобрена сообществом GCC и изменения вошли в официальный релиз компилятора версии 4.2.0.
По результатам работы были выполнены доклад и публикация на конференции GCC Developers' Summit.
8. Улучшение анализа алиасов на уровне представления RTL в компиляторе GCC (2005г.).
В компиляторе GCC имеются два уровня внутреннего представления: Tree-SSA и RTL. Более высокий уровень представления Tree-SSA позволяет реализовывать более совершенные методы анализа указателей в сравнении с уровнем RTL. Качество некоторых оптимизаций, выполняющихся на нижнем уровне представления RTL (например, планирование команд), может быть улучшено за счет более точного анализа указателей.
Целью проекта являлась разработка метода распространения информации, полученной с помощью анализа алиасов на уровне Tree-SSA, на уровень RTL, где она стала бы доступной оптимизациям нижнего уровня (back-end).
Результаты работы были представлены сообществу разработчиков GCC, в том числе на семинаре GREPS конференции PACT. Полученные результаты также были использованы в проекте по улучшению алгоритма поворотного модульного планирования.