Розгляд задачі оцінки часу виконання програм для спеціалізованих комп’ютерних систем. Модель роботи програми у вигляді поглинаючого марківського ланцюга із дискретними станами і дискретним часом. Блок-схема алгоритму програми та її інтерпретація графом.
Якість та надійність ПЗ 39 ЦИБАЄВ, В. Г.Прогнозування часу виконання програми повязано з використанням цілого ряду статичних і статистичних методів оцінювання, а також із імітаціонним моделюванням роботи пристроїв обчислювальної системи. В даній роботі розглядається задача оцінки часу виконання програм для спеціалізованих компютерних систем. Модель враховує сукупність історій виконання програми та використовує метод оцінки часу виконання лінійних блоків програми, що запрограмовані мовою високого рівня. Ці обмеження можуть стосуватися як виконання програм умонопольному режимі, так і загального часу виконання програми з урахуванням часу очікування у черзі в багатозадачних системах. Наприклад, у роботі [4] вивчається така проблема: по тексту програми та інформації про поводження програми, опису архітектури обчислювача оцінити час виконання програми, опису архітектури обчислювача оцінити час виконання програми на цьому обчислювачі.Блок-схема алгоритму програми та можлива її інтерпретація графом G(i) 1 наведено приклад блок-схеми алгоритму та його можлива інтерпретація графом G(i). Як це показано у [7], за допомогою наведеної моделі випадкового процесу можна обчислити середній час знаходження випадкового процесу у групі станів Si до переходу у поглинаючий стан Sn, тобто середній час виконання задачі T сумарну кількість кроків k до завершення програми, сумарну кількість попадання процесу S(tk) у кожний із станів Si - Ki .
Вывод
б
Рис. 1. Блок-схема алгоритму програми та можлива її інтерпретація графом G(i)
На рис. 1 наведено приклад блок-схеми алгоритму та його можлива інтерпретація графом G(i). Як це показано у [7], за допомогою наведеної моделі випадкового процесу можна обчислити середній час знаходження випадкового процесу у групі станів Si до переходу у поглинаючий стан Sn, тобто середній час виконання задачі T сумарну кількість кроків k до завершення програми, сумарну кількість попадання процесу S(tk) у кожний із станів Si - Ki . Для такого обчислення попередньо необхідно визначити час виконання кожного з лінійних блоків ?i . Будемо вважати, що текст програми заданий на мові високого рівня.
Найпоширинішими методами виміру часу фрагментів програми є безпосереднє вимірювання [1].
Запропонований метод оцінки часу використання програм може бути ефективно застосовано для визначення середнього часу виконання програм у монопольному режимі.
Список литературы
1. Методика измерения времени выполнения заданного фрагмента программы [Электронный ресурс]. - Режим доступа: http//evatutin.narod.ru.
2. Калиниченко, Д. В. Методы и средства прогнозирования времени выполнения последовательных программ [Текст] / Д. В. Калиниченко, А. П. Капитонова, П. В. Ющенко // Методы математического моделирования. - М. : МГУ, 1997. - № 2.
3. Davidson, N. W. Relating Static and Dyanamic Machine Code Measurments [Text] / N. W. Davidson, N. R. Rabung, D. B. Whalley // IEETRANS. on Computers. - Apr. 1992. - V. 41, № 4. - P. 444 - 454.
42 ISSN 1814-4225. РАДІОЕЛЕКТРОННІ І КОМПЮТЕРНІ СИСТЕМИ, 2014, № 6 (70)
4. Капитонова, А. П. Методы и средства прогнозирования времени выполнения последовательных фрагментов программна вычислителях с различной архитектурой [Текст] : дис. на соискание ученой степени канд. физ.-мат. наук. МГУ им. М.В. Ломоносова. - М., 1997. - 99 с.
5. Nilson, K. D. Worst-Case Execution Time Analysison Modern Processors [Text] / K. D. Nilson, B. Rygg // Second ACM SIGPLAN Workshop on Zanguages Compilers and Tools for Real-Time Systems, June, 1995.
6. Pushnir, P. Calculating the Maximum Execution Time of Real-Time Programs [Text] /
P. Pushnir, C. H. Koza // The International Jornal of Time-Critical Computer Systems. - 1989. - V. 1(2). - P. 159 - 176.
7. Зайцев, В. Г. Математична модель для оцінки часу виконання програм [Текст] / В. Г. Зайцев, М. В. Плахотний, Є. І. Цибаєв // Управління розвитком складних систем. - 2013. - Вип. 15. - С. 126 - 130.
8. Романовский, Дискретный анализ.Учебное пособие для студентов [Текст] / Романовский. - 3-е изд. - СПБ. : «Невский диалект», БХВ Петр-бург, 2003. - 320 с.
Поступила в редакцию 19.02.2014, рассмотрена на редколлегии 25.03.2014
Рецензент: д-р техн. наук, проф. О. В. Поморова, Хмельницкий национальный университет, Хмельницкий, Украина.
ОЦЕНКА ВРЕМЕНИ ВЫПОЛНЕНИЯ ПРОГРАММ Е. И. Цибаев, В. Г. Зайцев, М. В. Плахотный
Прогнозирование времени выполнения программы связано с использованием целого ряда статических и статистических методов оценки, а также с имитационным моделированием работы устройств вычислительной системы. В данной статье рассматривается задача оценки времени выполнения программ для специализированных компьютерных систем. Предложенная модель работы программы, в виде ПОГЛОЩАЮЩЕЙМАРКОВСКОЙ цепи с дискретными состояниями и дискретным временем. Модель учитывает совокупность историй выполнения программы и использует метод оценки времени выполнения линейных блоков программы, запрограммированные на языке высокого уровня.Приведенная блок-схема алгоритма программы и возможная ее интерпретация графом, а также пример ее применения.
Ключевые слова: поглощающая Марковская цепь, истории выполнения программы, линейный блок программы, прогнозирования времени выполнения программы.
EVALUATION OF PROGRAM EXECUTION TIME E. I. Tsybaev, V. G. Zaitsev, M. V. Plakhotny
Predicting execution time associated with the use of a number of static and statistical evaluation methods and simulation modeling of the devices of the computer system as well. In thir article we consider problem of estimating execution time of programs for specialized computer systems. The proposed model of work program in absorbing Markov chain form with discrete states and discrete time. The model takes into account totality of stories run program uses method of evaluation of execution time of a linear block of code programmed in high level language. Also it shows a block diagram ofthe algorithm ofthe program, its possible interpretation ofthe graph and an example ofits use.
Key words: absorbing Markov chain, run history of program, linear block program, time prediction of program execution.
Цибаев Евгений Игоревич - аспирант кафедры Специализированных компьютерных систем и системного программирования Национального Технического Университета Украины «Киевский Политехнический Институт», Киев, e-mail: etsybaev@gmail.com.
Зайцев Владимир Григорьевич - д-р техн. наук, профессор, профессор кафедры Специализированных компьютерных систем и системного программирования Национального Технического Университета Украины «Киевский Политехнический Институт», Киев, e-mail: v_zaitsev@bigmir.net.
Плахотный Николай Викторович - канд. техн. наук, доцент, доцент кафедры Специализированных компьютерных систем и системного программирования Национального Технического Университета Украины «Киевский Политехнический Институт», Киев.
Вы можете ЗАГРУЗИТЬ и ПОВЫСИТЬ уникальность своей работы
