ПРОГРАММИРОВАНИЕ, 2011, No 4, с. 28-38
ТЕСТИРОВАНИЕ, ВЕРИФИКАЦИЯ И ВАЛИДАЦИЯ ПРОГРАММ =
УДК 681.3.06
ОБ ОЦЕНКЕ ЧАСТОТЫ ВЫПОЛНЯЕМОГО КОДА ПОСЛЕДОВАТЕЛЬНЫХ ПРОГРАММ
© 2011 г. Р.Л. Смелянский Московский государственный университет имени М.В.Ломоносова 119992 г. Москва, В-234, факультет вычислительной математики и кибернетики
E-mail: smel@cs.msu.su Поступила в редакцию 03.10.2010 г.
Статья относится к проблематике, называемой в современной терминологии профилировкой программ. В ней представлена ретроспектива решений задачи профилировки кода, суть которой сводится к оценке частоты выполнения команд в программе. Также представлен новый подход к ее решению, основанный на методе статистических испытаний, который позволяет оценить число испытаний программы для оценки с заданной точностью частоты выполнения ее команд.
1. ВВЕДЕНИЕ
Из практики хорошо известно, что при исполнении последовательной программы работа не более 20% ее кода занимает не менее 80% всего времени ее исполнения [1]. Именно это явление объясняет эффективность применения кэш-памяти команд в процессорах, различных стратегий вытеснения страниц виртуальной памяти.
Назовем множество команд программы, число выполнения каждой из которых не ниже некоторой наперед заданной величины 7, ядром программы. Обозначим С7 (п, (х^ ...Хгп)) - множество операторов программы п, выполняющихся с частотой не ниже некоторой, наперед заданной величины 7, где п - программа, (х^ ... х^п) - набор значений исходных данных программы п.
Тогда возникает вопрос о выполнимости отношения
п с7 (п, (хп ...хгп )) = 0,
(хп ...хг„ )емп
где Мп - множество всех эффективных, т.е. фактически используемых, наборов исходных данных программы п. Другими словами, не может ли оказаться, что искомое ядро
уникально для каждого прогона, т.е. оно «плавает» от прогона к прогону. В этом случае применение кэш-памяти команд по-прежнему будет эффективно, но говорить о стабильном ядре программы не приходится. Если же ответ на поставленный выше вопрос отрицателен, т.е. стабильно часто выполняемое ядро существует, то уместно было бы задать вопрос о его флуктуациях от прогона к прогону, какова структура ядра программы?
Пусть
с; = п с7 (п, (хг1 ...хгп))
(хП ...хг„ )емп
- ядро программы п, тогда полезно знать какова величина
ДС7 = С^(п, (х*1 .. .хг„))\С^, где на
с'!у(п, (х^ ... х^п)) достигается
>емп 1 с* Пст(п (х»1 .. .х»п))|.
Вопросы о существовании ядра С*, умение находить как его, так и множества ДС7 имеют большое прикладное значение. Так, например, умение вычислять ядро программы позволило бы:
• при оптимизации и распараллеливании программы сконцентрировать усилия именно на ядре программы, а не «распылять» ресурсы на всю программу;
• в системах реального времени обоснованно выбирать резидентную часть и компактно представлять программу в памяти вычислителя;
• надлежащим образом планировать нагрузку в многопроцессорных и многоядерных вычислителях;
• выбирать надлежащую эвристику в алгоритмах look ahead при выборе ветки в условных операторах;
• обоснованно выбирать стратегии управления процессами и распределения ресурсов в операционных системах;
• упростить поиск решения задачи наихудшего времени выполнения программы (WCET) за счет сокращения пространства возможных решений;
• избежать многочисленных прогонов при профилировке программ.
Несколько слов о последнем пункте. Под профилировкой программ обычно понимают сбор разнообразной информации о поведении программы в ходе ее выполнения. Например, частоту выполнения той или иной команды, какие альтернативы в операторах условного перехода были активизированы, множество значений, которые хранились в той или иной области памяти и т.п. Эту информацию собирают при каждом конкретном прогоне программы. Методы профилировки можно классифицировать по типу собираемой информации и по способам ее получения. По первому признаку методы профилировки делятся на профилировку:
• кода - информацию о частоте выполнения линейных участков, переходов или времени выполнения функций в программе;
• памяти - информацию о частоте обращения к переменным, регистрам, используемых значениях или промахах в кэш.
По способам получения информации о поведении программы на:
• динамическую, когда информацию о поведении программы получают во время прогона программы на как-то выбранных данных;
• статическую, когда информацию о поведении программы получают на основе статического анализа текста программы.
Подробнее на задачах профилировки и техниках их решения мы остановимся в разделе 3.
2. ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ
Пусть n(v\... vin) - последовательная программа, где vi... vin - ее входные переменные. Представлять программу будем в виде графа потока управления, т.е. ориентированного графа. CFn = (An, En), где An = {Ъ3 - множество линейных участков программы П; En = {(bj, bi)}, где bj, bi G An, а (bj, bi) - передача управления от bj к bi; bi - линейный участок кода программы П т.е. такая последовательность операторов П где не нарушается естественный порядок их выполнения. Заметим, что линейный участок всегда завершается оператором управления, нарушающим естественный порядок выполнения.
Обозначим:
• Vn = {vi}P=i - множество всех переменных программы П.
• VIn - множество входных переменных программы, Vin ç Vn.
• TVi - тип переменной vi G Vn, т.е. множество
значении переменной Vi.
х TVp, т.е. Tn
это
ТП - TV1 х TV2 х
множество всех состояний памяти программы П.
Tin - декартово произведение T(v) для всех v G Vin.
Чтобы в дальнейшем отличить саму переменную от ее значения, будем обозначать значение переменной vi как < vi >, а значение набора переменных V1 С V, как <V' > .
• #nj(< Vin >) - число выполнений блока bj G An на наборе значений < VIn > .
В сделанных обозначениях определим понятие nbj - частоту выполнения bj G An, как
пь> - |Tin|:
где # П - #П(< Vin >).
{<VIn>\<VIn>C TIn}
Другими словами п^. - это среднее число выполнений блока bj, где усреднение взято по множеству Tin.
Отметим, что это не единственный способ усреднения. Например, можно брать усреднение по длине вычислительного процесса, порождаемого конкретным набором значений
< Vin >, либо по максимальной длине среди всех вычислительных процессов.
Упорядочим множество Vin и далее под Vin будем понимать вектор (v\,... ,vin), где vi G Vin i — l,...,In. Не трудно убедиться, что Tin и Tn - Гильбертовы пространства. Поэтому мы можем рассмотреть Vin как случайную величину на множестве значений Tin. Обозначим < Vin > значение случайной величины Vin. Тогда # nj(< Vin >) мы можем рассмотреть как функцию от случайной величины Vin на множестве Vin.
Теперь в терминах случайных величин частоту выполнения bj можно определить как
Еь^ - E# nj(< Vin >) -= E<Vin>k€Mn #nj (< Vin >) • P(< Vin >-
=<Vin >k), (2.1) где p(< Vin >-< Vin >k) - вероятность, что набор переменных Vin примет значение
< Vin >k ; Mn - множество всех эффективных исходных данных для программы n, т.е. множество тех наборов исходных данных, которые встречаются на практике. Ясно, что
Mn С TIn. Из формулы 2.1 следует еще один очень важный вывод, а именно: без информации о значениях исходных данных программы и их распределениях вычисление частотных характеристик поведения программы сродни шаманству. Примеры подобных «чудес» будут продемонстрированы ниже.
3. ПОСТАНОВКА ЗАДАЧИ И РЕТРОСПЕКТИВА ЕЕ РЕШЕНИЯ
Мы будем рассматривать задачу о вычислении характеристик поведения программы в следующей постановке. Пусть дана программа n в виде исходного кода (язык программирования в данном случае не важен, лишь бы он был императивный ). Для каждой v G Vin известен T(и). Пока для простоты техники изложения будем считать что все входные переменные -простые переменные. Требуется вычислить Еь для Vbj : bj G An.
В работах [2, 3] дано решение этой задачи при следующих предположениях:
Для каждой v G VIn известна функция распределения значений v на Tv
Dv(x) = p(v = x), где x G Tv.
Значения переменных из VIn в < VIn > статистически независимы.
В статье [3] показано, как, зная Dv(x) для всех v G Vin, можно в аналитическом виде получить вид функции Dv(x) для переменных программы, а зная эти функции получить вероятности переходов на дугах графа CFn. При этом предполагалось, что Vv G Vn : Tv С N, где N - множество натуральных чисел, т.е. любой тип перечислим, и значения любой переменной в программе n - есть рациональная функция от переменных из Vn, задаваемая в виде арифметического выражения, в котором допускаются только элементарные функции.
В работе [2] была построена математическая модель, позволившая в сделанных предположениях 1-2 по статическому представлению n получить характеристики ее поведения. В этой статье показано, как в рамках построенной модели и при условии, что n не зацикливается, получить Ebj для Vbj : bj G An из C F n.
В этой же статье показана связь построенной математической модели с моделями поведения
программ на основе цепей Маркова и показано, что в рамках построенной модели выполняется гипотеза, сформулированная в [9] о том, что средняя условная вероятность q окончания цикла "№Ы1е_ёо определяется соотношением:
1
q
п + 1'
где п - среднее число итераций цикла.
Как показали эксперименты, выполненные еще в 80-е годы, решения рассматриваемой задачи, сформулированные в [2, 3], обладают большой вычислительной сложностью и трудны для применения на практике.
Теперь кратко рассмотрим основные, более поздние достижения в области профилировки программ. Надо отметить, что в этой области задача об анализе поведения программы рассматривается в постановке, несколько отличной от сформулированной выше. Предполагается, что дана программа в исходном виде, множество наборов значений ее входных параметров, на которых прогоняют программу. Как получают это множество, не обсуждается.
Основная идея подходов к динамической профилировке для получения частот линейных участков программы заключается в размещении счетчиков в программе в каждом линейном участке и прогон программы на различных входных значениях [10, 11]. В самом простом случае счетчики помещают в
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.