О некоторых задачах анализа и трансформации программ

С.С. Гайсарян, А.В. Чернов, А.А. Белеванцев, О.Р. Маликов, Д.М. Мельник, А.В. Меньшикова

Аннотация.

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

1. Введение

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

В отделе ведётся работа и в традиционной области оптимизации программ. Упор делается на разработку новых методов анализа указателей в программах на языке Си. Также проводятся исследования так называемых "полустатических" (profile-based) методов оптимизации программ. Такие методы заключаются в использовании на стадии оптимизации кода информации, накопленной с предварительных её запусков.

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

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

Данная работа имеет следующую структуру: в разделе 2 мы рассматриваем задачу автоматического разбиения программы на нити, в разделе 3 рассматриваются задачи маскировки программ, а в разделе 4 задача автоматического выявления уязвимостей. Далее в разделе 5 кратко описывается интегрированная среда IRE, её состав и внутреннее представление MIF, используемое всеми компонентами IRE. Наконец, в разделе 6 мы формулируем выводы данной работы и даём направления дальнейших исследований.

2. Разбиение программ на нити и повышение локальности

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

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

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

Системы с разделяемой памятью наиболее удобны для программиста параллельных приложений. Более того, часть работы по распараллеливанию последовательного кода может быть выполнена компилятором. Существует много исследований по автоматическому распараллеливанию циклов и рекурсивных процедур на таких системах. Некоторые разработки реализованы в промышленных компиляторах, например, IBM Visual Age C++, Intel C++ Compiler, SGI MIPSPro, REAPAR и других.

В последнее время проводятся исследования по автоматическому распарал-леливанию любого последовательного кода. Предложено несколько подходов, таких, как управление выполнением нитей (thread-level speculation) [6], коммутативный анализ, динамическое распределение задач на нити (dynamic task scheduling) [5], автоматическое разделение на нити на этапе компиляции. Часть предложенных алгоритмов проверена авторами на эмуляторах, часть реализована в существующих исследовательских компиляторах, например, в компиляторе SUIF Стенфордского университета [7].

Формализация понятия локальности проведена в [8]. Рассматривается два вида событий локальности:

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

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

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

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

Упаковка данных в памяти (data packing) для увеличения количества событий пространственной локальности.

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

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

Похожие работы

Анализ эффективности MPI-программ

Скачать

60039

6

8

... из-за динамической подзагрузки программы из файловой системы) и отлаживать его производительность по той же методике, которая была описана выше применительно к программе целиком. 5. Средство анализа эффективности MPI программ 5.1 Постановка задачи В системе DVM существуют развитые средства анализа эффективности выполнения параллельной DVM-программы. Эти средства являются более мощными, ...

Трансформация фразеологизмов и детские тексты

Скачать

203142

15

1

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

Уроки рыночных трансформаций

Скачать

40761

0

0

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

Трансформации социально-экономических систем в КНР и Венгрии

Скачать

241465

35

0

... же важны при экономико-географическом анализе. По всем этим показателям существуют весьма ощутимые различия между тремя группами стран. Характеристики трансформаций социально-экономических систем в КНР и Венгрии 2.1   Трансформации социально-экономической системы КНР 2.1.1     Предыстория и цели трансформации Социально-экономические сдвиги в Китае 1918-1927 гг. Завершение Национальной ...