ИЗВЕСТИЯ РАН. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2015, № 4, с. 39-44
КОМПЬЮТЕРНЫЕ ^^^^^^^^^^^^^^ МЕТОДЫ
УДК 004.422; 519.214
ОБ ОЦЕНИВАНИИ ЧАСТОТЫ ВЫПОЛНЕНИЯ ФРАГМЕНТОВ КОДА ПОСЛЕДОВАТЕЛЬНОЙ ПРОГРАММЫ*
© 2015 г. В. Ю. Королев, Р. Л. Смелянский, Т. Р. Смелянский, А. В. Шалимов
Москва, МГУ, факультет ВМК, ИПИРАН Поступила в редакцию 22.09.14 г., после доработки 29.12.14 г.
На основе асимптотических аппроксимаций, получаемых при помощи предельных теорем теории вероятностей, приводятся формулы, позволяющие получить гарантированные интервальные оценки частоты выполнения фрагментов кода последовательной программы. Описывается метод выбора надлежащей аппроксимации, основанный на современных оценках точности приближения биномиального распределения нормальным и пуассоновским распределениями.
Б01: 10.7868/80002338815040095
Введение. В статье рассматривается задача оценки частоты выполнения фрагментов кода последовательной программы. Эта задача возникает во многих приложениях, в частности, таких, как:
оптимизация, распараллеливание и тестирование программ: для того чтобы сконцентрировать усилия именно на активных участках программ;
повышение эффективности алгоритмов управления ресурсами в операционных системах;
выбор резидентной части в системах реального времени;
управление нагрузками в распределенных и многопроцессорных системах.
В работе используется строгое определение частоты выполнения фрагмента кода последовательной программы, предложенное и проанализированное в [1]. Под фрагментом кода понимается линейный участок программы, т.е. такой участок кода, где не нарушается естественный порядок выполнения.
Данная задача имеет тесную связь с областью профилировки программ [2, 3], где возникает задача определения частоты выполнения инструкций программы. Существующие решения в этой области сводятся к применению различных эмпирических данных или к предположению, что все входные данные программы равномерно распределены на области значений, что в общем случае не всегда верно.
1. Описание задачи. Пусть П(х) = {V, Е} — исходная последовательная программа с р входными параметрами х = (хь..., хр). Программа представлена в виде графа потока управления с вершинами V = {Ьу-}, где Ьу — линейные участки программы, у = 1, т, и дугами Е = {(Ьу, Ьу2)}, где (Ьу-, Ьу2) — переход управления от у^-го линейного участка к у2-му линейному участку.
Конкретное значение параметра XI будем обозначать , * = 1,Р. Также пусть X = (Хь ..., Хр). Множество Ж = {X} всех допустимых входных параметров программы будем считать метрическим пространством, что дает возможность формально рассмотреть борелевскую ст-алгебру его подмножеств и определить на ней распределение вероятностей 9 , которое позволяет интерпретировать вектор X как значение случайного элемента, принимающего значения в Ж и имеющего известное распределение 9. Заметим, что, вообще говоря, в силу дискретного характера представления информации в компьютере для каждого входного параметра х множество допустимых значений является конечным, так что упомянутое выше множество Ж конечно, а распределение входных значений дискретно. Однако для удобства мы рассматриваем более общую модель, поскольку для многих реальных программ мощность |Ж| множества Ж может иметь порядки 10100 [4], что, например, превосходит число атомов водорода (наиболее распространенного химического
* Работа выполнена при финансовой поддержке РФФИ (проект № 15-07-02984-а).
элемента) в видимой части Вселенной, которое по современным оценкам составляет примерно 1048 [5]. Поэтому методы теории вероятностей и математической статистики, ориентированные на конечные модели, в рассматриваемом случае неэффективны.
Приведем простой пример, свидетельствующий в пользу рассмотрения в данной задаче общих (в том числе непрерывных) вероятностных моделей. Возьмем входной параметр, отвечающий за показания альтиметра (пилотажно-навигационного прибора, указывающего высоту полета). Погрешности показаний альтиметра, которые, несомненно, имеются и вызваны суммарным воздействием большого числа случайных факторов, могут считаться случайными и, в силу центральной предельной теоремы теории вероятностей, нормально распределенными с дисперсией, обусловленной точностью прибора.
Рассматриваемая постановка задачи восходит к работам [6, 7], в которых впервые дана ее общая строгая формализация. Позднее с развитием техники профилировки программ появились частные случаи этой постановки [2, 3]. История данной задачи и подходы к ее решению описаны в [8]. Работа [9] посвящена применениям предлагаемого метода к анализу систем реального времени. Мы будем придерживаться уточненной формализации стохастического функционирования программы, предложенной в [10] (также см., например, [11]).
Будем считать, что программа П(х) не зацикливается на допустимых наборах входных данных, т.е. каждый линейный участок выполняется конечное число раз. Введем обозначение П у (X) для числа выполнений у -го линейного участка на векторе входных значений X.
Итак, пусть X = (Хъ Хр) — случайный элемент со значениями в Ж , интерпретируемый как случайный вектор входных значений программы. Пусть У у = П у (X) — соответствующее число выполнений у -го линейного участка программы. Очевидно, что У у — это дискретная случайная величина, принимающая значения в N и {0} и имеющая собственное распределение (т.е. принимающая бесконечное значение с нулевой вероятностью). Математическое ожидание, соответствующее распределению 9 , будет обозначаться Е.
Определение [6, 7]. Частотой выполнения у -го линейного участка при заданном распределении значений входных параметров называется величина
V у -у у (Ьу) = ЕУу = ЕП у (X).
Возможно несколько подходов к вычислению частоты Vу выполнения линейного участка Ьу. В [6, 7] предложены методы построения функции распределения числа выполнений линейных участков программы по распределениям входных параметров в аналитическом виде. Фактически используются формулы свертки и при реализации требуются значительные вычислительные затраты. В [1] предложен подход, позволяющий не вычислять точное значение частоты выполнения, так как это сопряжено с большими вычислительными затратами, сравнимыми с прогонами программы на всех входных данных, а оценивать значение частоты выполнения с заранее заданной точностью. Для оценки частоты выполнения линейного участка, которая заключается в приближенном вычислении математического ожидания случайной величины, в [1] предложено использовать метод статистических испытаний (метод Монте-Карло). Идея этого метода заключается в проведении многократных опытов с исследуемой случайной величиной и на основе полученных значений делается вывод о различных характеристиках этой случайной величины.
2. Метод оценки частоты выполнения линейных участков программы. Рассмотрим задачу доверительного оценивания параметра Vу. Требуется оценить значение Vу частоты выполнения линейного участка с заранее заданной точностью е > 0 (при этом е мало), т.е. найти Иу, удовлетворяющее неравенству ^у - Nу| < б, причем указанное неравенство должно выполняться с заранее заданной вероятностью (достоверностью, надежностью) у (близкой к единице).
Проведем п независимых испытаний, в результате каждого из которых наблюдается значение случайной величины У у. На практике это означает запуски программы П(х) на значениях (X), сгенерированных независимым образом в соответствии с распределением 9 на множестве Ж входных параметров [1]. При этом на каждом испытании используется новый экземпляр программы П(х). Получим выборку из п значений Уу- = (Уу®,..., У уп)) — числа выполнений у -го линейного участка при запусках программы на элементах из Ж , отвечающих распределению 9 . В соответствии с законом больших чисел в качестве оценки частоты Vj возьмем величину
n
N = 1 £ j.
При этом можно считать, что моменты любых порядков случайной величины У; существуют [1], причем
V; =
Дальнейшие рассуждения зависят от того, насколько много нулей среди полученных значений У('\ ' = 1,п. Если нулевых значений немного, то адекватную аппроксимацию для распределения случайной величины N можно получить, используя центральную предельную теорему и неравенство Берри—Эссеена. Если же выборка Уу- содержит много нулей, т.е. активация у -го линейного участка является редким событием относительно распределения то нормальная аппроксимация, вытекающая из центральной предельной теоремы, неточна и более адекватное приближение можно получить с помощью теоремы Пуассона (закона малых чисел). Рассмотрим задачу выбора оптимальной аппроксимации более подробно.
Обозначим X' = В(У;') > 0), где !(А) — индикатор события А:
_ \ 1, событие А произошло,
"\А) = )
[ 0, событие А не произошло.
Поскольку здесь и всюду далее речь идет только о фиксированном у-м линейном участке, для удобства обозначений индекс у у соответствующих случайных величин и их характеристик будем опускать.
Описанный выше способ организации испытаний позволяет считать случайные величины , ' = 1, п, независимыми и одинаково распределенными, причем
^ = 1) = Р = 1 - @(Х1 = 0), ' = й
Тогда, очевидно, случайная величина
Mn = £ ii
i = 1
имеет биномиальное распределение с параметрами n (число испытаний программы) и p е (0,1) (вероятность активации j -го линейного участка программы):
SP{Mn = k) = ck„pk(i-p)n-k, k = on
При больших n (а для обеспечения разумной точности s значение n должно быть большим) точное вычисление указанных вероятностей затруднено, но можно использовать асимптотические аппроксимации, устанавливаемые теоремой Муавра—Лапласа и теоремой Пуассона. Согласно теореме Муавра—Лапласа, для любого x е R
lim sup| $P(Mn < x) - Ф(x^np(1 - p) + np)| = 0,
n ^ да x
где Ф(х) — стандартная нормальная функция распределения,
Ф(х) I
х
2
-и /2 1
e du.
При этом, согласно неравенству Берри—Эссеена с наилучшей известной абсолютной константой, для рассматриваемого случая бернуллиевых слагаемых [12],
2 2
8ир10\Мп < х) - Ф(^пр(1 - Р) + пр)\ < 0.4138Р .+ (1 - Р) = 51(п,р). (2.1)
х Л/ПР(1 - Р)
n
Согласно теореме Пуассона, при больших значениях п и оч
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.