Методы и средства прогнозирования времени выполнения последовательных фрагментов программ на вычислителях с различной архитектурой тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат физико-математических наук Капитонова, Алла Петровна

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

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

Введение

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

1.1 Время — как мера производительности.

1.2 Подходы к оценке времени выполнения программы.

1.3 Прогнозирование на множестве историй выполнения программы

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

1.5 Инструментальные средства оценки времени выполнения программ

2 Статико—динамический метод оценки времени выполнения программы

2.1 Общая задача оценки времени выполнения программы.

2.2 Статико-динамический подход.

3 Решение задачи на классе последовательных вычислителей

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

3.2 Генерация оптимального кода для линейного участка

3.3 Модель последовательного вычислителя.

3.3.1 Алгоритмы генерации кода и свойства программ, вычисляющих дерево выражения.

3.3.2 Модель регистрового вычислителя

3.3.3 Модель стекового вычислителя

3.3.4 Обощенная модель регистро-стекового вычислителя

3.4 Инструментальная система оценки времени для вычислителей с регистро-стековой архитектурой.

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

3.4.2 Структура инструментальной системы.

3.4.3 Результаты тестирования системы.

4 Решение задачи на классе векторно-конвейерных вычислителей

4.1 Особенности векторно-конвейерных вычислителей.

4.2 Временные особенности выполнения векторных операций

4.3 Свойства программ, выполняемых на векторноконвейерных вычислителях

4.4 Модель векторно-конвейерного вычислителя.

4.5 Определение времени выполнения векторизуемых программ . . 61 4.5.1 Алгоритм динамического программирования на классе векторных вычислителей.

4.5.2 Алгоритм циклического планирования.

4.6 Формальное описание векторно-конвейерного вычислителя

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

5 Решение задачи на классе RISC вычислителей

5.1 Моделирование поведения конвейеров.

5.2 Моделирование поведения кэш-памяти.

5.2.1 Особенности кэш-памяти.

5.2.2 Методы статического моделирования кэш-памяти

5.3 Средства описания архитектуры процессора.

5.4 Архитектура системы оценки времени для RISC процессоров . 87 Заключение 92 Приложения

I. Описание алгоритмов генерации кода.

II. Разметка операторов языка Си.

Ш. Параметрическое описание регистро-стекового вычислителя.

IV. Параметрическое описание вычислителя с RISC архитектурой.

V. Пример статических предсказаний для RISC вычислителей.

Введение диссертации (часть автореферата) на тему «Методы и средства прогнозирования времени выполнения последовательных фрагментов программ на вычислителях с различной архитектурой»

Данная работа посвящена вопросу оценки времени выполнения последовательных программ.

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

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

Под оценкой времени выполнения обычно понимается одна из альтернатив:

• измерение определенных параметров функционирования вычислительной системы на этапе ее работы;

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

Первый подход обычно подразумевает наблюдение за выполнением программы, сбор трасс, построение программных и аппаратных эмуляторов [1, 2, 3]. Таким образом, он всегда связан с исследованием динамики программы. Достоинство динамических методов — в точности получаемых оценок. Однако их применение не всегда возможно по следующим причинам:

• отсутствие реального вычислителя;

• реализация эмулятора исследуемого вычислителя является дорогостоящим и трудоемким процессом;

• значительное замедление ( 10-1000 раз) выполнения программы из-за накладных расходов при измерении.

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

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

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

Для решения задачи разработана методика комплексного статико-динамического прогнозирования.

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

• последовательные вычислители фон-неймановского типа;

• векторно-конвейерные вычислители;

• вычислители с RISC архитектурой.

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

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

Данная работа организована следующим образом. В главе 1 проводится сравнительный анализ существующих методик оценки времени. В главе 2 излагаются основы предлагаемой нами методики. В главах 3, 4, 5 рассматривается решение задачи прогнозирования на разных классах вычислителей.

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Капитонова, Алла Петровна

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

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

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

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

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

Статико-динамический подход был применен при реализации подсистемы временной сложности в рамках среды БУАКА [56], предназначенной для анализа функционирования распределенных вычислительных систем. Методика прогнозирования времени использовалась для оценки сложности внутренних действий последовательных процессов. Поскольку среда БУАКА анализирует поведение распределенных программ путем имитационного моделирования работы исследуемой вычислительной системы, статико-динамическая методика органично вписывается в работу такой среды.

Заключение

Список литературы диссертационного исследования кандидат физико-математических наук Капитонова, Алла Петровна, 1997 год

1. Смелянский P.JI. Методы анализа и оценки производительности вычислительных систем. М.: МГУ. 1990.

2. Davidson J.W., Rabung J.R., Whalley D.B. Relating Static and Dyanamic Machine Code Measurements. // IEEE Trans, on Computers, V.41, N4, Apr. 1992, pp.444-454.

3. Rozwadowski R.T. A measure for the quantity of computation. // Proc. ACM SIGME Symp. on Measuremant and Evaluation, 1973, pp. 100-111.

4. Hellerman L. A measure of computational work. // IEEE Trans, on Computers. V.C-21, N5, 1972, pp. 439-446.

5. Hennessy J.L., Patterson D.A. Computer Architecture: a Quantitative Approach. California. 1990.

6. Смелянский P.JI. Взаимодействие программы и вычислительной среды. // Сб. Вычислительные комплексы и моделирование сложных систем. М., МГУ, 1990.

7. Капитонова А.П., Смелянский P.JI., Терехов И.В. Система для оценки временных характеристик программ: архитектура и реализация. // Сб. Программно-аппаратные средства и математическое обеспечение вычислительных систем. С.92-103. М., МГУ. 1994

8. Bharrat S.J., Jeffay К. Predicting Worst Case Execution Times on a Pipelined RISC Processor. // Technical Report, University of North Carolina, 1994.

9. Busquets J.V., Serano J.J., Ors R., Gil P., Wellings A., Adding Instruction Cache Effect to an Exact Schedulability Analysis of Preemptive Real-Time Systems.// Euromicro Workshop on Real-Time Systems, June 1996.

10. Busquets J.V, Serano J.J., The Impact of Extrinsic Cache Performance on Predictiability of real-Time Systems. // Proc. of 2nd International Workshop on real-Time Computing Systems and Applications (RTCSA'95).

11. Park C.Y., Shaw A.C., A Source-Level Tool for Predicting Deterministic Execution Time of Programs. // T.R. 89-09-12, Dpt. of Computer Science and Engineering, University of Washington. 1989.

12. Puschner P., Koza C.H. Calculating the Maximum Execution Time of Real-Time Programs. // The International Jornal of Time-Critical Computer Systems, 1(2), 1989, pp.159-176.

13. Ершов А.П. Современное состояние теории схем программ. // Проблемы кибернетики. Вып. 27. М., 1973. С.87-111.

14. Nilsen K.D., Rygg В., Worst-Case Execution Time Analysis on Modern Processors. // Second ACM SIGPLAN Workshop on Languages, Compilers, and Tools for Real-Time Systems, June, 1995.

15. Ко L., Whalley D.W., Harmon M.G., Suppoting User-Friendly Analysis of Timing Constraints. // Proc. ACM SIGPLAN Workshop on Language, Compilers and Tools for Real-Time Systems, June 1995, pp.107-115.

16. Harmon M.G., Baker T.P, Whalley D.B., A Retargetable Technique for Predicting Execution Time of Code Segments. // Real-Time Systems, September 1994, pp.159-182.

17. Narasimhan K., Nilsen K.D., Portable Execution Time Analysis for RISC Processors. // ACM SIGPLAN Workshop on Language, Compiler and Tools for Real-Time Systems, June 1994.

18. Lim S.S., Bae J.H., Jang G.T., An Accurate Worst Case Timing Analysis Technique for RISC Processors. // Proc. Fifteenth IEEE Real-Time Systems Symposium, Dec. 1994, pp.97-108.

19. Shaw A.C., Reasoning About Time in High-Level Language Software. // Research Report, Laboratory MASI, University of Paris 6.

20. Мок A.K., Evaluating Tight Execution Time Bounds of Programs by Annotations. // Sixth IEEE Workshop on Real-Time Operating Systems and Software. Pittsburg, PA, pp.74-80.

21. Stoenko A.D., A Real-Time Language With a Schedualability Analyser. // PhD Thesis, Department of Computer Science, University of Toronto, 1987, Toronto.

22. Healy C.A., Whalley D.B., Harmon M.G., Integrating the Timing Analysis of Pipelining and Instruction Caching. // Proceedings of the IEEE Real-Time Systems Symposium, December, 1995, pp.288-297.

23. Aho A.V., Sethi R., Ullman J.D. Compiling Principles, Techniques, and Tools. Addison-Wesley Publishing Company. 1988.

24. Mueller F., Static Cache Simulation and its Applications. // PhD Dissertation, Florida State University, Tallahassee, Fl, August, 1994.

25. Y-T. S., Malik S., Wolfe A., Efficient Microarchitecture Modeling and Path Analysis for Real-Time Systems. // Proc. of 16th IEEE Real-Time Systems Symposium, Dec. 1995, pp.298-307.

26. Y-T. S., Malik S., Wolfe A., Performance Estimation of Embedded Software with Instruction Cache Modeling // Proc. of ACM/IEEE International Conference on Computer Aided Design. November 1995.

27. Choi J.-Y., Lee I., Kang I. Timing Analysis of Superscalar Processor Programs using ACSR. // 1993.

28. Diep T.A., Shen J.P. Systematic Validation of Pipeline Interlock for Superscalar Microarchitectures. // Proc. of the International Symposium on Fault-Tolerant Computing, 1995.

29. Diep T.A. A Visualization-based Microarchitecture Workbench. // PhD Dissertation. Carnegie Mellon University. 1995.

30. Aho A.V., Johnson S.C. Optimal Code Generation for Expression Trees. // J. ACM, V.23, N3, 1976, pp.488-501.

31. Уокерли Дж. Архитектура и программирование микро-ЭВМ. — М., кн. 1, гл. 5.

32. Bruno J.L., Lassagne Т. The Generation of Optimal Code for Stack Machines. // J. ACM, V.22, N3, 1975, pp.382-396.

33. Aho A.V., Johnson S.C., Ullman J.D. Code Generation for Expression with Common Subexpression. //J. ACM, V.24, N1, 1977, pp. 146-160.

34. Aho A.V., Ganapathi, Tjiang W.K. Code Generation Using Tree Matching and Dynamic Programming. // ACM Trans. Program. Lang. Syst., V.ll, N4, 1989, pp.491-516.

35. Knuth D.E. The Art of Computer Programming, V. 1, Fundamental Algorithms, 2nd Ed. 1973.

36. Aho A.V., Johnson S.C. Optimal Code Generation for Expression Trees. // J. ACM, V.23, N3, 1976, pp.488-501.

37. Капитонова А.П., Смелянский P.JI., Терехов И.В. Инструментальная системы оценки трудоемкости вычислений в программах. // Сб. Системное программирование и модели исследования операций. С. 57-72. М., МГУ. 1993.

38. Морс С.П., Алберт Д.Д. Архитектура микропроцессора 80286. М., Радио и связь. 1990.

39. Воеводин В л. В., Капитонова А. П. Методы описания и классификации вычислительных систем. М., МГУ, 1994.

40. Хокни Р., Джесхоуп К. Параллельные ЭВМ. М., Радио и связь. 1986.

41. Воеводин В.В., Воеводин Вл.В., Еремин А.Ю., Тыртышников Е.Е. Комплексное изучение параллелизма — ключ к эффективному использованию супер-ЭВМ. М., МГУ. 1994.

42. Padua D.A., Wolfe M.J. Advanced Compiler Optimizations for Supercom-puting. // Com. of the ACM, V,29, N12, pp.1184-1201.

43. Eisenbeis C., Jalby W., Lichnevsky A. Squeezing More CPU Performance Out of a Cray-2 by Nector Block Sheduling. INRIA. Report N 841. 1988.

44. Bernstein D., Boral H., Pinter R. Optimal Chaining in Expression Trees. // J. ACM. 1986. pp.1-10.

45. Eisenbeis C., Jalby VV. Static Dependence Analysis and Control for Loop Scheduling. INRIA. Report N 1296. 1990.

46. Y-T. S., Malik S., Performance Analysis of Embedded Software Using Implicit Path Enumeration. // Proc. of ACM Design Automation Conference, June 1995.

47. The SPARC Technical Papers, Ed. Catanzaro B.J., Springer-Verlag, 1991.

48. Петрова Ю. RISC процессоры третьего поколения. // Computer Week Moscow. N22,23. 1995.

49. Калиниченко Д.В., Капитонова А.П., Ющенко Н.В. Методы и средства прогнозирования времени выполнения последовательных программ. // Сб. Методы математического моделирования. В печати.

50. Kim S., Min S., На R., Efficient Worst Case Timing Analysing of data Caching. // Proc. of IEEE RTAS'96.

51. Groves R.D., Oehler R.R. IBM RISC System/6000 Processor Architecture. // IBM J. Res. Develop., V.34, N.l, 1990, pp.23-36.

52. Аваков В. Микропроцессор MIPS R10000. // Открытые системы, N6, 1995. С.62-69.

53. Kane J., Heinrich J., MIPS RISC Architecture. Prentice Hall. 1992.

54. Rawat J., Static Analysis of Cache Performance for Real-Time Programming. // Master's thesis, Iowa State University, 1993.

55. Bakhmurov A.G., Smeliansky R.L. DYANA: An Environment for Distributed System Design and Analysis. // Proc. of the VII Int. Workshop on Parellel Processing by Cellular Automata and arrays. 1996. pp.85-92.

56. The SPARC Architecture Manual. Version 8. Prentice Hall. 1992.