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

Московский государственный университет имени М.В. Ломоносова Факультет вычислительной математики и кибернетики

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

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

ИССЛЕДОВАНИЕ МЕТОДОВ КОМПАКТНОГО ПРЕДСТАВЛЕНИЯ ДЛЯ ПРОГРАММ РЕАЛЬНОГО ВРЕМЕНИ

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

МОСКВА 2011

1 7 МАР 2011

4840867

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

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

доктор физико-математических наук, профессор, академик РАЕН Смелянский Руслан Леонидович;

Официальные оппоненты:

доктор физико-математических наук, Петренко Александр Константинович;

кандидат технических наук, Егисапетов Эдуард Григорьевич.

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

НТЦ ОАО "ОКБ Сухого".

Защита состоится «18» марта 2011 г. в 11:00 па заседании диссертационного совета Д 501.001.44 при Московском государственном университете имени М.В. Ломоносова по адресу: 110991, ГСП-1, Москва, Ленинские горы, МГУ, 2-ой учебный корпус, факультет вычислительной математики и кибернетики, аудитория 085.

С диссертацией можно ознакомиться в библиотеке факультета ВМиК МГУ имени М.В. Ломоносова, с текстом автореферата — на официальном сайте ВМиК МГУ имени М.В. Ломоносова: http://www.cs.msu.su в разделе «Наука» — «Работа диссертационных советов» — «Д 501.001.44».

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

Ученый секретарь

диссертационного совета Д 501.001.44

профессор

Н.П. Трифонов

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

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

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

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

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

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

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

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

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

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

Апробация работы. Результаты, представленные в работе, докладывались на научном семинаре лаборатории вычислительных комплексов кафедры АСВК факультета ВМиК МГУ имени М.В. Ломоносова под руководством

профессора P.JI. Смелянского; на семинаре кафедры АСВК под руководством заведующего кафедрой член-корр. РАН JI.H. Королева; на научном семинаре группы "Computer Architecture" исследовательского подразделения компании Майкрософт, а также на следующих конференциях:

• Международная конференция «Ломоносов 2007» (Москва, апрель 2007 г.);

• Всероссийская межвузовская научно-техническая конференция «Микроэлектроника и информатика» (Зеленоград, май 2008 г.);

• Международная научная конференция «Интеллектуализация обработки информации» (Украина, Алушта, июнь 2008 г.);

• Всероссийская конференция «Методы и средства обработки информации» (Москва, октябрь 2009 г.);

• Летний коллоквиум молодых ученых в области программной инженерии (SYRCoSE) (Нижний-Новгород, июнь 2010 г.).

Публикации. По теме диссертации имеется 8 публикаций (включая 1 в издании из перечня ВАК), список которых приводится в конце автореферата.

Структура и объем диссертации. Диссертация состоит из введения, шести глав, заключения, списка литературы и приложения. Объём работы — 126 страниц (включая 3 страницы приложения). Список литературы содержит 65 наименований.

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

Во введении обоснована актуальность диссертационной работы и сформулирована цель исследований.

В первой главе описывается задача компактного представления программ в рассматриваемом классе систем реального времени - системах мягкого реального времени. В этих системах программа должна выполняться в свой директивный интервал в среднем случае (для систем жесткого реального времени - в худшем случае). Формально, пусть П(Х) - последовательная программа с набором входных параметров X. Тогда время выполнения программы П(Х) на всех допустимых входных данных в среднем не должно превышать директивного интервала А: Т(П(Х)) < Д в среднем для любых X, где Т(П(Х)) - это время работы программы П на наборе входных данных X.

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

Метод КПП для систем реального времени - это такое преобразование

программ С : П х т —» П', что:

• функциональности П'иП совпадают, где П' = С(П,г) - это скомпакти-рованный вариант исходной программы П;

• размер скомпактированной программы П' меньше размера исходной программы П: М(П') < М(П), где М(П) - это размер программы;

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

вается не более, чем на заданный коэффициент г: Т(П'(Х)) < (1 +т) * Т(П(Х)) в среднем для любого X.

При применении методов КПП в системах реального времени дополнительно учитываются следующие условия:

• Накладные расходы по памяти при использовании метода КПП в заданной системе не должны превышать суммарного выигрыша но памяти от компактного представления набора программ системы: 3к — М(П-)) > M (С), где M (С) - размер метода КПП в системе (если метод КПП не требует нахождения своих частей в системе, то M (С) = 0), {Л,} - набор программ системы реального времени, к - количество ком-пактирусмых программ а системе.

• Когда невозможно скомпактировать программу так, чтобы были выполнены все временные ограничения, необходимо определить при каких требованиях к вычислительным ресурсам системы возможно применение заданного метода КПП. В качестве примера рассматривается следующее требование - повышение производительности процессора на величину р: Зр > 1 Proc2 = pProci : УХ Тргос (П'(Х)) < (1 + г) * ТрГОС1(П(Х)), где Ргосг - это процессор, производительность которого была увеличена в р раз по сравнению с Proci - исходным процессором системы реального времени, Трг0С.(П(Х)) - это время работы программы П на процессоре Ргос,; на наборе входных данных X.

Во второй главе дан обзор методов КПП. Представлены критерии классификации методов КПП и показатели эффективности методов КПП (коэффициент сжатия1 и коэффициент увеличения времени выполнения2). Опи-

1 Коэффициент сжатия - это отношение размера скомпактироваиной программы к размеру исходной программы.

2 Коэффициент увеличения времени выполнения - это отношение времени выполнения скомпакти-

саны основные методы КПП: компактное представление библиотек (на примере Java), методы оптимизации, одновременное применение в программе нескольких систем команд (на примере ARM), аппаратная реализация схемы компрессор/декомпрессор (на примере аппаратного декомпрессора для PowerPC), интерпретация и словарные методы.

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

Третья глава посвящена предложенному методу КПП на основе частотных характеристик поведения программ. Идея этого метода КПП основана на двух фактах. Первый: в последовательной программе исполнение 15-20% кода программы занимает 80% времени её исполнения. Второй: программа в интерпретируемой форме, как правило, занимает меньше места, чем в откомпилированной. На основании этих двух фактов было предложено исследовать метод КПП, который заключается в том, что редко-выполняемые фрагменты кода программы хранятся в сжатой интерпретируемой форме и динамически, по мере необходимости, распаковываются и выполняются, а часто-выполняемый код компилируется.

рованной программы к времени выполнения исходной программы.

I Рис. 3.1. Схема предложенного метода КПП.

Рисунок 3.1 показывает основные принципы работы метода КПП. Рассмотрим программу с тремя редко-выполняемыми фрагментами кода /, д и Л, как показано на рисунке 3.1(а). Структура метода и организация скомпакти-рованной программы представлена на рисунке 3.1(6). Каждый редко-выпол-ияемый фрагмент кода программы при её комиактировании заменяется очень короткой последовательностью команд - заглушкой, которая вызывает декомпрессор, чья работа заключается в распаковке интерпретируемого кода этого фрагмента в буфер выполнения и передаче управления интерпретатору, который будет выполнять распакованный код. Таблица смещения определяет, где внутри сжатого кода начинается код для данного фрагмента. Заглушка для каждого фрагмента передает декомпрессору аргумент, который является индексом в этой таблице; этот аргумент показан меткой ((0), (1), ■ • •) на дуге от каждой заглушки до декомпрессора. Декомпрессор использует этот номер для индексации в таблице смещения, извлекает начальный адрес сжатого кода соответствующего фрагмента и начинает распаковку интерпретируемого кода в буфер выполнения. Затем декомпрессор передает управление интерпретатору для выполнения сгенерированного кода. Когда распакованный

фрагмент заканчивает свое выполнение, управление возвращается скомпак-тированной программе.

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

Пусть П(хь... ,хр) = {V, Е} - исходная последовательная программа с р входными параметрами (х\,... ,хр). Программа представлена в виде графа потока управления с вершинами V = где Ь^ - линейные участки программы, э = 1,тп, и дугами Е = {(^,,6^)} , где - передача управления от линейного участка к ]2 линейному участку.

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

Вводятся следующие обозначения.

• Т(х;) - множество допустимых значений входного параметра Хг\

• XI - значение входного параметра из Т{х^)\

• П^(х1,... ,хр) - число выполнений j-гo линейного участка на векторе входных значений (¿1,..., хр);

• Мр — Т{х\) х • • • х Т{хр) - множество всех наборов входных данных мощности \МР\ и размерности р.

Каждый входной параметр программы рассматривается как случайная величина с заданной функцией распределения значений. Пусть Х\,... ,ХР -случайные величины для входных параметров (х\,... ,хр). Тогда

Yj = Uj(Xi,... ,Xp) является случайной величиной для числа выполнений j-го линейного участка. Отметим, что Yj - это дискретная случайная величина, так как число выполнений линейного участка при одном испытании принадлежит множеству натуральных чисел с нулем N U {0} и принимает только конечные значения.

Определение 4.1. Частотой выполнения j-го линейного участка при заданных распределениях входных параметров называется величина e(bj) = EYj = IIj(xi,... ,хр) ■ Р{(Х 1,...,Хр) = (ii,... ,хр)) - это математическое

(хи...,хР)€Мр

ожидание числа выполнений j-го линейного участка.

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

Определение 4.2. Частотой выполнения j-ro линейного участка называет-

£ ВДсь.-Д-р)

ся величина n(bj) = <J'.....1--это среднее число выполнений j-ro

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

Однако следует отметить, что при условии дискретного равномерного распределения входных параметров, величины из определений 4.1 и 4.2 совпадают, так как в этом случае Р((Хь ..., Хр) — (ij,..., хр)) = .

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

3 Smdianski R. LM Alanko Т. On the calculation of control transition probabilities in a program // Information Processing Letters.— 198ö.— Vol. 22.

4 Смеляпский Р.Л., Гурьев Д.Е., Бахмуров А.Г. Об одной математической модели для расчета динамических характеристик программы // Программирование.— 1986,— Т. 6.

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

Монте-Карло).

Необходимо оценить значение е(Ь^) = ЕУ^ = ..., Хр) частоты

выполнения линейного участка с заранее заданной точностью £, то есть найти ■ |е(^) — < е. Указанное неравенство должно выполняться с наперед заданной достоверностью 7.

Проводится п испытаний случайной величины У] = ПД-Х-!,... ,ХР). На практике это означает запуски программы П(хь... ,хр) на значениях, сгенерированных по функциям распределения случайных величин для входных параметров. При каждом испытании используется новый экземпляр программы П(х1,..., Хр). Входные наборы (хг,..., хР) выбираются случайным образом и независимо от наборов, использованных на предыдущих итерациях.

Получается выборка из п значений У^ ,У?,... ,У" - числа выполнений ,?-го линейного участка при запусках программы на элементах из Мр, отвечающих распределениям Хи ■ ■ •, Хр.

п

Определяется величина ТУ,- = 1/п • УД которая и есть искомая оцен-

¿=1

ка частоты выполнения 3-го линейного участка. Это следует из следующих утверждений.

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

в графе потока управления программы). Тогда для выборки УД У?,..., У" значений случайной величины У} = ПД-Х],...,Хр) (] = 1 ,т) верно, что она состоит из независимых, одинаково распределенных величин с конечными моментами любых конечных порядков.

Это утверждение имеет важное следствие.

Следствие 4.1. Если дополнительно предположить, что случайная величина У) имеет ненулевую дисперсию, то к выборкам вида У^, У?,..., У-1,... различных характеристик программы применимы Закон больших чисел5 и Центральная предельная теорема6.

Следующее утверждение определяет взаимосвязь N3 и е(бД

Утверждение 4.2. Ес.п,и для программы П(х1,... ,хр) выполнены условия утверждения 4-1 и следствия 4-1, по справедливо следующее:

1. А^- —> е(Ь^) при п —> оо.

2. При достаточно больших п с достоверностью, близкой к 7, можно утверждать, что \е(Ь— Л^ < • иш,

где о| = ИУ^ > 0 - дисперсия случайной величины У/, ищ. - квантиль порядка Цр стандартного нормального закона.

Из первого пункта утверждения 4.2 следует, что при увеличении числа прогонов программы значение оценки частоты выполнения линейного участка Nj будет приближаться к частоте е(6,).

5 Закон больших чисел. Пусть А'1, А'2, - ■. - независимые одинаково распределенные случайные

величины и ЕХ1 = а. Тогда с вероятностью единица выполняется соотношение Пт 1/п У\ Хь = а.

1 = 1

6 Центральная предельная теорема. Пусть Х\,Х-2,.- - - независимые одинаково распределенные случайные величины и ЕХ 1 — а, и ОХ] = <т2, причем 0 < а2 < оо. Тогда при л —» 00 наибольшее по .? значение величины < х) - Ф(ж)| стремится к нулю.

Второй пункт утверждения'4.2 позволяет оценить число прогонов программы, необходимое для вычисления e(bj) с заданной точностью и достоверностью. Если в какой-то момент проведения испытаний выполнено условие п > ' т0 это означает, что частота выполнения была вычислена

с заранее заданной точностью е и достоверностью 7, то есть удалось найти такую величину Nj, что P(\e(bj) — Nj\ < е) = 7.

Заметим, что из Центральной предельной теоремы вытекает, что при больших п распределение суммы случайных величин можно аппроксимировать нормальным законом. На практике необходимо проверять адекватность такой нормальной аппроксимации. Это можно сделать с помощью теоремы Берри-Эссеена7 (теорема применима к данной задаче - см. утверждение 4.1 и следствие 4.1). Из теоремы следует, что на практике для применимости нормальной аппроксимации необходимо, чтобы < е', где е' - задаваемая точность нормальной аппроксимации, которую можно выбирать из условия е' < (1 - 7)с, 0 < с < 1. Например, е' =

На практике crj и ¡лj не известны. В этом случае при достаточно большом числе испытаний (п > 30) вместо них можно использовать оценки

п п

sj = • - Nif (выборочная дисперсия) и rrvj = ^ • J2(Yj ~ Njf

i=i ¿=1

(выборочный третий центральный момент), соответственно. Конкретное значение достаточного числа испытаний зависит от задачи. В данной работе в качестве порога берется 30 испытаний.

Всё вышесказанное сформулировано в следующем алгоритме 4.1.

Алгоритм 4.1. Вычисление частоты выполнения линейного участка.

1. Задать е, 7.

7 Теорема Берри-Эссеена. Предположим, что выполнены условия Центральной предельной теоремы для независимых одинаково распределенных случайных величин и существует /г3 = E\Xi — а|'\ то sup|<х) - Ф(х)| < 1 где Со - абсолютная положительная постоянная, 0.4097... < С(| < 0.4784.

2. Инициализировать счетчик числа испытаний нулем, п = 0.

3. Провести одно испытание случайной величины У) с результатом У^" и увеличить счетчик числа испытаний на единицу, п = п + 1.

4. Если п > 30, то вычислить текущие значения оценки частоты выполнения ^'-го линейного участка Л^, выборочной дисперсии и выборочного третьего момента тр

а- Щ = 1/п-£у?;

¿=1

М = ¡¿г ¿07 -«=1

в. >п:!

«=1

Иначе провести еще один прогон программы (пункт 2).

5. Если п > " 11 — "ТТм т0 Щ является искомой оценкой е(Ь^) с заданной точностью е и достоверностью 7. Иначе провести очередной прогон программы (пункт 2).

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

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

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

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

• ¿(6.;) - время единичного выполнения j-гo линейного участка на заданном вычислителе. Оценка основана на знании среднего количества тактов синхронизации на одну команду.;

• 1(Ь}) * е(6г) - это среднее время работы ^'-го линейного участка за время работы программы;

• Т = ¿(Ь?) * - среднее время выполнения всей программы;

• 9 - доля времени работы некоторого кода программы от времени работы всей программы (порог редко-выполняемого кода).

Определение 5.1. Редко-выполняемый код - это множество линейных участков, среднее время выполнения которых не превышает в от среднего времени

выполнения всей программы:

COLD = {Ъп, ■ ■ ■ , bj,| ELi Ф.п) * e&J < 0 * Г}.

Далее рассматривается задача компактного представления редко-выполняемого кода, которая решается предложенным методом КПП на этапе отбора редко-выполняемых линейных участков. Пусть С{П,0) - метод КПП, который подвергает компактировашпо редко-выполняемый код. Для каждого линейного участка bj известен его исходный размер s(bj), его размер s'(bj) после компактирования методом С, время ¿(6,) выполнения этого линейного участка и частота выполнения e(bj). Тогда необходимо найти вектор Z — (zi, ■ ■ ■ , zm), где, если Zj = 0, то не надо комиактировать линейный участок bj, а если Zj = 1, то надо комиактировать линейный участок bj, такой что:

' т

* s'(bj) + (1 - Zj) * s(bj)) min при Z = (zu-- - , zm) £ Bm;

< i=1

m

^ zj * * e(bj) <9*T.

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

1. Все линейные участки рассматриваются в порядке уменьшения выигрыша от компактирования этого линейного участка,_s(6j) — s'(bj).

2. Если сумма весов линейных участков t(bj) * e(bj) превысит д * Т, то работа алгоритма завершается.

3. Все отобранные линейные участки считаются редко-выполняемыми и далее подвергаются компактировашпо (см. определение 5.1).

Доказанные в главе утверждения формулируют условия применимости метода КПП редко-выполняемого кода в системах мягкого реального времени.

Утверждение 5.1. Для того, чтобы метод КПП С(И,в) можно было применять в системах реального времени с коэффициентом т, необходимо выбирать в исходя из условия в < - Г_1, где ас - коэффициент увеличения времени выполнения скомпактироваиной программы.

Следствие 5,1. Зависимость коэффициента увеличения времени выполнения скомпактироваиной программы т от параметра в имеет вид т(в) = (ас-1)*в.

"Утверждение 5.2. Для того, чтобы получить выигрыш по памяти от использования метода КПП С(П, в) в системе реального времени, необходимо выбрать программы, суммарный объем которых будет больше где А с (9) - коэффициент сжатия.

Утверждение 5.3. Для того, чтобы сохранить возмоэюпость применения метода КПП С(И,в) в системе реального времени, необходимо выбирать р - коэффициент необходимого увеличения производительности процессора, исходя из условия р > .

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

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

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

' т

* s'(bj) + (1 - Zj) * s(bj)) -> min при Z = (zb • • • , zm) 6 Bm\

3=i

vi

< ^T^ Zj * e(bj) —» min;

i=i

m

, j=i

Задача компактпо!'о представления редко-выполняемого кода при минимизации общей задержки по времени выполнения программы рассматривается как следующая задача многокритериальной оптимизации (для этого при оценке частоты выполнения линейного участка дополнительно запоминается максимальное зарегистрированное значение частоты выполнения линейного участка max{bj)):

' m

* s'(bj) + (1 - Zj) * s(bj)) min при Z = (zh ■ ■ ■ , zm) 6 Bm;

j=l

in

< * (rnax(bj) — e(bj)) —> min;

i=i

TU

. i=i

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

Шестая глава посвящена реализации предложенного метода КПП и результатам его экспериментального исследования. Система компактного представления программы, реализующая предложенный метод КПП (Глава 3), написана на языке С++. Она состоит из двух частей (рисунок 6.1): блок ком-нактирования программы (компрессор) и блок исполнения скомпактирован-ной программы (декомпрессор). На вход система КПП принимает программу

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

Декомпрессор Интерпретатор

Распаковка фрагментов сжатого кода программы

Управление общим процессом выполнения программы

Рис. 6.1. Структ.ура прототипа предложенного метода КПП.

Испытания системы КПП проводились на программах реального времени, использующихся в современных встроенных системах. Целью являлось определение показателей эффективности предложенного метода КПП:

1. А(#) - коэффициент сжатия в зависимости от значения входного параметра в - порога редко-выполняемого кода.

2. т(в) - коэффициент увеличения времени выполнения в зависимости от значения входного параметра 9 - порога редко-выполняемого кода.

В качестве тестовых данных использовались программы из следующих источников: DrTesy (МГУ им. М.В. Ломоносова; международный проект по моделированию навигационного комплекса летательного апиарарата), SNU Real-time (Сеульский Национальный Университет; набор программ численных вычислений для DSP систем реального времени), MiBench (Мичиганский университет; набор программ, используемых во встроенных системах реального времени).

Компрессор

| Определение частот выполнения [ фрагментов кода программы

| Определение редко-выполняемых | ф ра гм е нтов кода прогр а м м ы

Формирование областей кода программы, пригодных для компактирования

Компактирование выбранных областей

Для каждой тестовой программы производился 31 запуск системы КПП с разными значениями в = 0.01,0.02,0.03,0.04,0.05,0.06,0.07,0.08,0.09,0.1, 0.12,0.14,0.16,0.18,0.2,0.25,0.3,0.35,0.4,0.45,0.5,0.55,0.6,0.65,0.7,0.75, 0.8, 0.85,0.9,0.95,1. После каждого запуска определялся размер и среднее время выполнения полученной скомпактированной программы. На основе этих величин определялся коэффициент сжатия и коэффициент увеличения времени выполнения скомпактированной программы относительно исходной про-

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

На рисунке 6.2 представлена полученная зависимость между коэффициентом сжатия и входным параметром Л (в). Максимальный коэффициент сжатия Х(9) = 0.77 при 9=1 (комиактировашпо подвергаются все команды программы). Из графика видно, что целесообразно выбирать входной параметр из условия в < 0.5, так как при больших значениях в прирост коэффициента сжатия незначителен.

0,7 .....

0,6 -0,5 0,4 0,3 0,2 ОД

О 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

Рис. 6.2. Зависимость коэффициента сжатия от входного параметра А(0). На рисунке 6.3 представлена полученная зависимость между коэффици-

грамммы.

х

0,0

в

ентом увеличения времени выполнения программы и входным параметром т(в). Как видно из графика, экспериментально полученные значения т(в) не превосходят аналитически полученного выражения т(в) = (ас — 1) * в (при ас = 9), сформулированного в следствии из утверждения 5.1 (пунктирная линия) . Это означает, что при выборе входного параметра согласно описанным в главе 5 рекомендациям, время выполнения скомиактированной программы будет удовлетворять заданным временным ограничениям.

т

10

Рис. 6.3. Зависимость коэффициента увеличения времени выполнения программы от входного параметра т(9).

Приложение содержит синтаксис языка интерпретируемого представления, использующегося в разработанном методе КПП.

Основные результаты работы.

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

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

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

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

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Смелянский P.JL, Шалимов A.B. Метод оценки частот выполнения фрагментов кода последовательной программы // Программные системы и инструменты. Тематический сборник N7, М.: Изд-во факультета ВМиК МГУ, 2006

2. Шалимов A.B. Исследование метода компактного представления программ на основе частотных характеристик их поведения // Ломоносов 2007: XIV Международная конференция студентов, аспирантов и молодых ученых; секция "Вычислительная математика и кибернетикам.: Издательский отдел факультета ВМиК МГУ, 2007

3. Шалимов A.B. Исследование метода компактного представления программ на основе частотных характеристик их поведения // Микроэлектроника и информатика - 2008. 15-я Всероссийская межвузовская научно-техническая конференция студентов и аспирантов, М.: МИЭТ, 2008

4. Шалимов A.B. Метод компактного представления программ на основе частотных характеристик их поведения // Таврический вестник инфор-

матики и математики / Крымский научный центр НАН Украины - 2008. - N2. - С. 243-250

5. Смелянский Р.Л., Шалимов А.В. Разработка системы компактного представления программ. // Программные системы и инструменты. Тематический сборник N9, М.: Изд-во факультета ВМиК МГУ, 2008. стр. 20-31.

6. Смелянский P.JL, Шалимов А.В. К вопросу о частоте выполнения фрагментов кода последовательной программы // Методы и средства обработки информации: Третья Всероссийская научная конференция. Труды конференции. М.: Изд-во факультета ВМиК МГУ, 2009. - стр. 57-63.

7. A. Shalimov The Method of Programs Compression Base on the Frequency Characteristics of Programs Behaviour. Proceeding of the 4th Spring/Summer Young Researchers' Colloquim on Software Engineering (SYRCoSE 2010), June 1-2, 2010 - Nizhny Novgorod, Russia

8. Шалимов А.В. Метод оценки частоты выполнения фрагментов кода последовательной программы // Моделирование и анализ информационных систем, Том 17, Номер 2, 2010. С.122-132.

Заказ № 187-1/02/2011 Подписано в печать 14.02.2011 Тираж 100 экз. Усл. п.л. 1,2

/¿С-—ООО "Цифровичок", тел. (495) 649-83-30 '/ с/г. ги; е-таИ:т/о@с/г. т

Введение.

Глава 1. Задача компактного представления программ в системах реального времени.

1.1. Системы мягкого реального времени.

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

Глава 2. Обзор методов компактного представления программ

2.1. Критерии классификации методов компактного представления программ.

2.2. Показатели эффективности методов компактного представления программ

2.3. Основные методы компактного представления программ

2.4. Результаты обзора.

2.5. Декомпозиция задачи.

Глава 3. Метод компактного представления программ на основе частотных характеристик их поведения.

3.1. Общее описание предложенного метода компактного представления программ.

3.2. Компактирование программы.

3.3. Выполнение скомпактированной программы.

3.4. Корректность предложенного метода компактного представления программ

Глава 4. Метод определения частотных характеристик программы.

4.1. Задача вычисления частоты выполнения фрагментов кода программы

4.2. Основные понятия и определения.

4.3. Методы профилирования программ.

4.4. Метод оценки частоты выполнения фрагментов кода программы

4.5. Практическое исследование метода. 4.6. Выводы.

Глава 5. Метод определения редко-выполняемого кода программы

5.1. Определение редко-выполняемого кода программы.

5.2. Оценка времени выполнения линейного участка.

5.3. Задача компактного представления редко-выполняемого кода

5.4. Применение предложенного метода компактного представления программ в системах реального времени.

5.5. Выводы.

Глава 6. Реализация и апробация метода компактного представления программ.

6.1. Структура прототипа предложенного метода компактного представления программ.

6.2. Испытания прототипа предложенного метода компактного представления программ.

6.3. Выводы.

Программы реального времени - это широкий класс программ, время реакции которых на внешние воздействия должно укладываться в заданные временные рамки. Корректность работы таких программ определяется не только корректностью логики их функционирования, но и временем их исполнения в вычислительной системе. Примерами таких программ служат операционные системы реального времени, управляющие системы сложными техническими комплексами (например, атомные электростанции, автоматические производственные линии, системы противовоздушной и противоракетной обороны, системы обработки радиолокационной информации) и программное обеспечение встроенных систем [5, 6, 12, 13, 40, 56].

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

1. встроенные системы реального времени являются одним из наиболее распространенных классов систем реального времени [6, 13];

2. проблема компактного представления программ для встроенных систем реального времени является особо актуальной [6, 7, 9].

Встроенные системы

В настоящее время каждый технически сложный объект оснащается встроенной системой управления. Количество микропроцессоров, используемых во встроенных системах, превышает в несколько раз количество микропроцессоров, используемых в персональных компьютерах [6]. Это объясняет, почему встроенные системы являются одной из основных областей применения средств вычислительной техники и разработки программного обеспечения [13, 28, 40].

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

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

Например, как видно из таблицы 1, для большинства бортовых цифровых вычислительных машин современных летательных аппаратов объем доступной памяти находится в диапазоне от 0.5 до 10 Мб. А рекомендованный объем памяти для перспективных летательных аппаратов колеблется от 16 до 32 Мб [7, 9].

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

БЦВМ Объем памяти (ОЗУ + ПЗУ) Самолет

0рбита-20 {1977) 132 КБайт Су-27, МиГ-29

Ц-100 (1982) 136 КБайт Су-27, МиГ-29

БЦВМ-386 (1995) БЦВМ-486 (1997) 2250 КБайт Су-ЗОМК(К)

16-32 МБайт

Таблица 1. Объем памяти в используемых БЦВМ. тропомехам и перегрузкам, что обеспечивает большую массу и размер этих устройств.

Для мобильных устройств ситуация с памятью схожая, но причины её ограниченности несколько иные. Как видно из таблицы 2, в современных мобильных телефонах объем оперативной памяти находится в диапазоне от 4 до 64 Мбайт, в смартфонах от 384 до 768 Мбайт, а в используемых сенсорных датчиках от 2 до 8 Кбайт.

Сенсорные датчики1

MICA2 PIC16F СС1010 AtMegal28L WeBee3

4 КБайт, 4 КБайт 2 КБайт 4 КБайт 8 КБайт

Мобильные телефоны2

Nokia 6303 Nokia 7100 Nokia 3600 Nokia ХЗ Nokia 2323

32 МБайт 4 МБайт 32 МБайт 64 МБайт 4 МБайт

Смартфоны3

НТО Desire HD НТС Mozart Apple iPhone 4 НТС EVO 4G НТС Aria

768 МБайт 576 МБайт 512 МБайт 512 МБайт 384 МБайт

Таблица 2. Объем памяти в мобильных устройствах.

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

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

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

Методы компактного представления программ

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

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

Неформально работу методов КПП можно описать следующим образом. На вход методы КПП принимают программы в некотором представлении (от исходного текста до бинарного кода). Далее программы подвергаются

1 По материалам сайта capsil.org.

2 По материалам сайта wikimart.ru.

3 По материалам сайта phonegg.com. компактированию с целью уменьшения размера программы (см. рисунок 1).

Память

Рисунок 1. Работа методов КПП.

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

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

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

Цель диссертационной работы

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

Основные результаты

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

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

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

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

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

Структура работы

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

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

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

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

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

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

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

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

Основные результаты

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

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

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

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

Заключение

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

1. Смелянский Р.Л., Гурьев Д.Е., Бахмуров А.Г. Об одной математической модели для расчета динамических характеристик программы / / Программирование. — 1986. — Т. 6.

2. Ахо А., Сети Р., Ульман Д. Компиляторы: принципы, технологии и инструменты. — Издательский дом "Вильяме 2003. — Р. 768.

3. Калашников A.B., Костенко В.А., Маркин М.И. Средства конструирования итерационных алгоритмов для решения задач комбинаторной оптимизации // Искусственный интеллект. — 2004. — Т. 2. — С. 91-95.

4. Скрипкин В.А., Моисеенко Е.А. Математические методы исследования операций в военном деле. — М.: Военное издательство министерства обороны СССР, 1979.

5. Блискавицкий A.A., Кабаев C.B. Операционные системы реального времени (обзор) // Мир компьютерной автоматизации — 1995. — Т. 1.

6. Программное обеспечение встроенных вычислительных систем. / А.О. Ключев, П.В. Кустарев, Д.Р. Ковязина, Е.В. Петров. — СПб.: СПб-ГУ ИТМО, 2009.-С. 212.

7. Колпаков К. История развития бортовых цифровых вычислительных машин в России // PCWeek. 1999. - Т. 32.

8. Гнеденко Б.В. Курс теории вероятностей. — УРСС, 2001. — Р. 448.

9. Павлов A.M. Принципы организации бортовых вычислительных систем перспективных летательных аппаратов // Мир Компьютерной Автоматизации: Встраиваемые Компьютерные Системы — 2001. — Т. 4.

10. Ногин В.Д. Принятие решений в многокритериальной среде: количественный подход, — М.: Физматлит, 2002. — Р. 176.

11. Ватолин Д. Методы сжатия данных.— М.: Диалог-МИФИ, 2003.— С. 384.

12. Золотарев С. Современные операционные системы реального времени для перспективной авионики // Военный парад. — 2006. — Т. 6.

13. Энджел Д. 2011-й: главные тенденции на рынке встроенных систем // PC Week. 2010.

14. Arm documentation. — www.arm.com/documentation/.

15. Arm processors. — www. arm. com/products/processors/.

16. Arnold K., Gosling J., Holmes D. The Java Programming Language. — Prentice Hall, 2000. P. 704.

17. Ball Т., Larus J. Optimally profiling and tracing programs // ACM Transactions on Programming Languages and Systems (TOPLAS').—■ July.— Vol. 16. Pp. 1319-1360.

18. Ball Т., Larus J. Optimally profiling and tracing program // Principles of Programming Languages (POPL). — ACM, 1992. —January. — Pp. 59-70.

19. Benini L. Selective instruction compression for memory energy reduction in embedded systems // The International Symposium on Low Power Electronics and Design (ISLPED). ACM, 1999.

20. Beszedes A., Ferenc R., Gyimothy T. Survey of code-size reduction methods // ACM Computing Surveys. — 2003.

21. Brown P. Macros without tears // Softiuare: Practice and Experience.— 1979. Vol. 9.

22. Cate V., Gross T. Combining the concepts of compression and caching for a two-level filesystem // Architectural Support for Programming Languages and Operating Systems (ASPLOS).- 1991.

23. De Sutter B., Bosschere K. Software techniques for program compaction // Communications of the ACM. — 2003. — August. Vol. 46. — Pp. 47-52.

24. Debray S., Evans W. Profile-guided code compression // Programming language design and implementation (PLDI).— ACM, 2002.

25. Debray S., Evans W. Cold code decompression at runtime // Communications of the ACM. 2003. - August. - Vol. 46. - Pp. 55-60.

26. Documentation for the llvm system. — http://llvm.org/docs.

27. Drtesy. — http://lvk.es.msu.su/index.php/articles/65.

28. Embedded computing design. — www. embeddedcomputing. com.

29. Ernst J., Evans W. Code compression // Programming Language Design and Implementation (PLDI). — ACM, 1997.- Pp. 358-365.

30. Fisher A., Freudenberger S. Predicting conditional branch directions from previous runs of a program // Architectural Support for Programming Language and Operation Systems (ASPLOS). — ACM, 1992. — October.— Pp. 85-95.

31. Fraser C. Automatic inference of models for statistical code compression // Programming Language Design and Implementation (PLDI).— Vol. 5.— ACM, 1999.- Pp. 242-246.

32. The gnu compiler collection. — http: //gcc. gnu. org/.

33. Graham S. An execution profiler for modular programs // Software: Practice and Experience. — 1983. — Pp. 671-685.

34. Grove D., Chambers C. A framework for call graph construction algorithms // Transactions on Programming Languages and Systems (TOPLAS). Vol. 23. - ACM, 2001. - November. - Pp. 685-746.

35. Huffman D.A. A method for the construction of minimum-redundancy codes // Institute of Radio Engineers. — Vol. 40. — 1952. — September. — Pp. 1098-1101.

36. Raster D., Wilhelm S. Generic control flow reconstruction from assembly code // Languages, Compilers, and Tools for Embedded Systems (LCTES). — ACM, 2002.-June.

37. Kemp T.M., Montoye R.M. A decompression core for powerpc // IBM Jour- > nal of Research and Development. — September. — Vol. 42.

38. Knuth D.E. An empirical study of fortran programs // Software: Practice and Experience. — 1971. — Vol. 1. — Pp. 105-133.

39. Korolev V., Shevtsova I. An improvement of the berry-esseen inequality with applications to poisson and mixed poisson random sums // Scandinavian Actuarial Journal. — 2010.

40. Kozuch M., Wolfe A. Compression of embedded system programs // IEEE International Conference on Computer Design: VLSI in Computers and Processors. — 2000.

41. Krishnaswamy A., Giipta R. Profile guided selection of arm and thumb instructions // Languages, Compilers, and Tools for Embedded Systems (LCTES). ACM, 2002. - June. - Pp. 55-64.

42. Krishnaswamy A., Gupta R. Mixed-width instruction sets // Communications of the ACM. 2003. - Vol. 46. - Pp. 47-52.

43. Lecture on computer organization.— http://meseec.ce.rit.edu/ eecc550-winter2009/.

44. Lefurgy C. Efficient execution of compressed program: Ph.D. thesis / The University of Michigan. — 2000.

45. Levine S. Linkers and Loaders. — Morgan Kaufmann, 2000. — P. 256.

46. Lindholm T., Yellin F. The Java Virtual Machine Specification. — Prentice Hall, 1999. P. 496.

47. Mibench. — http : //www. eecs. umich. edu/mibench/.

48. Mips technologies. — www.mips . com/products/resourcelibrary/.

49. Muchnick S. Advanced Compiler Design and Implementation. — Morgan Kaufmann, 1997. P. 856.

50. Post-pass compaction techniques / B. De Bus, D. Kastner, D. Chanet et al. // Communications of the ACM. — 2003. — August. — Vol. 46. — Pp. 41-46.

51. Sarkar V. Determining average program execution times and their variance // Programing Language Design and Implementation (PLDI). — ACM, 1989. June. - Pp. 298-312.

52. Seal D. ARM Architecture Reference Manual. — Addison-Wesley Professional, 2000. P. 816.

53. Shafer G. A Mathematical Theory of Evidence. — Princeton University Press, 1976.

54. Smelianski R. L., Alanko T. On the calculation of control transition probabilities in a program // Information Processing Letters. — 1986. — Vol. 22.

55. Snu real-time benchmarks.— http://www.cprover.org/goto-cc/ examples/snu. html.

56. Stankovic J.A. Real-time computing // Byte Magazine. — 1992. — Vol. 17. — Pp. 155-160.

57. Sutter B., Bus B., Bosschere K. Sifting out the mud: Low level C++ code reuse // Object-Oriented Programming, Systems, Languages and Applications (OOPSLA).- ACM, 2002.-November. Pp. 275-291.

58. System support for automatic profiling and optimization / X. Zhang, Z. Wang, N. Gloy et al. // Symposium of Operating Systems Principles (SOSP). — ACM, 1997.-October.-Pp. 15-26.

59. Thuresson M., Stenstrom P. Evaluation of extended dictionary based static code compression schemes // Computing Frontiers (CF).— ACM, 2005.— Italy. P. 10.

60. Tip F., Sweeney P. Class hierarchy specialization // Acta Informatica. — 2000. Vol. 36.

61. Tip F., Sweeney P., Laffra C. Extracting library-based java applications // Communications of the ACM. — 2003. — August. — Vol. 46. — Pp. 33-40.

62. Visual c++ developer center.— http://msdn.microsoft.com/en-us/ visualc/.

63. Wall D. Predicting program behavior using real or estimated profiles // Programming Language Design and Implementation (PLDI).— ACM, 1991.— June. Pp. 59-70.

64. Whaley J. Partial method compilation using dynamic profile information // Object Oriented Programming Systems, Languages, and Applications (OOP-SLA). — ACM, 2001. — October. — Pp. 166-179.

65. Wu Y., Larus J. Static branch frequency and program profile analysis // International Symposium on Microarchitecture (MICRO). — ACM, 1994.— Pp. 1-11.