maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State Universitymais-1033Research ArticleОригинальные статьиArticlesМетод оценки частоты выполнения фрагментов кода последовательной программыШалимовА. В.ShalimovAlexanderashalimov@lvk.cs.msu.suМГУ им. М.В. ЛомоносоваRussian Federation201020062010172122132Copyright © Шалимов А.В., 20102010Шалимов А.В.Shalimov A.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.mais-journal.ru/jour/article/view/1033

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

The goal of this article is to consider the task of determining the execution frequency of program basic blocks. This task is important for such applications as program optimization, paralleling program execution, computing resources allocation, program compaction, and malicious software detection. A new method is proposed in the article for evaluation of basic block execution frequency based on the Monte Carlo method. The method proposed allows us to estimate a number of program runs to get the execution frequency with a given precision.

частота выполненияанализ программметод статистических испытанийпрофилированиеexecution frequencyprogram analysisMonte Carlo methodprofilingReferencesSmelianski R.L., Alanko T. On the calculation of control transition probabilities in a program Inform // Processing Letters. 1986. N.3.Smelianski R.L., Alanko T. On the calculation of control transition probabilities in a program Inform // Processing Letters. 1986. N.3.Смелянский Р.Л., Гурьев Д.Е., Бахмуров А.Г. Об одной математической модели для расчета динамических характеристик программы // Программирование. 1986. N6.Смелянский Р.Л., Гурьев Д.Е., Бахмуров А.Г. Об одной математической модели для расчета динамических характеристик программы // Программирование. 1986. N6.Youfeng Wu, James R. Larus Static Branch Frequency and Program Profile Analysis // Proceedings of the 27th annual international symposium on Microarchitecture. 1994. P. 1-11.Youfeng Wu, James R. Larus Static Branch Frequency and Program Profile Analysis // Proceedings of the 27th annual international symposium on Microarchitecture. 1994. P. 1-11.Thomas Ball , James R. Larus Optimally profiling and tracing programs // ACM Transactions on Programming Languages and Systems (TOPLAS). 1994. P. 1319¬1360.Thomas Ball , James R. Larus Optimally profiling and tracing programs // ACM Transactions on Programming Languages and Systems (TOPLAS). 1994. P. 1319¬1360.Скрипкин В.А., Моисеенко Е.А. Математические методы исследования опера¬ций в военном деле. М.: Военное издательство министерства обороны СССР, 1979.Скрипкин В.А., Моисеенко Е.А. Математические методы исследования опера¬ций в военном деле. М.: Военное издательство министерства обороны СССР, 1979.Гнеденко Б.В. Курс теории вероятностей. 7-е изд. М.: УРСС, 2001. 448 с.Гнеденко Б.В. Курс теории вероятностей. 7-е изд. М.: УРСС, 2001. 448 с.Korolev V., Shevtsova I. An improvement of the Berry-Esseen inequality with applications to Poisson and Mixed Poisson random sums // Scandinavian Actuarial Journal. 2010 (to appear).Korolev V., Shevtsova I. An improvement of the Berry-Esseen inequality with applications to Poisson and Mixed Poisson random sums // Scandinavian Actuarial Journal. 2010 (to appear).Documentation for the LLVM System [HTML] (http://llvm.cs.uiuc.edu/docs/).Documentation for the LLVM System [HTML] (http://llvm.cs.uiuc.edu/docs/).The GNU Compiler Collection [HTML] (http://gcc.gnu.org/).The GNU Compiler Collection [HTML] (http://gcc.gnu.org/).Шалимов А.В. Метод компактного представления программ на основе частотных характеристик их поведения // Интеллектуализация обработки инфор¬мации: Тезисы докладов Международной научной конференции / Крымский научный центр НАН Украины. Симферополь, 2008.Шалимов А.В. Метод компактного представления программ на основе частотных характеристик их поведения // Интеллектуализация обработки инфор¬мации: Тезисы докладов Международной научной конференции / Крымский научный центр НАН Украины. Симферополь, 2008.

The authors declare that there are no conflicts of interest present.