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

• Шалимов, Александр Владиславович
• кандидат физико-математических наук
• 2010

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

Введение.

Глава 1. Задача компактного представления программ в системах реального времени.

1.1. Системы мягкого реального времени.

1.2. Постановка задачи.

Глава 2. Обзор методов компактного представления программ

2.1. Критерии классификации методов компактного представления программ.

2.2. Показатели эффективности методов компактного представления программ

2.3. Основные методы компактного представления программ

2.4. Результаты обзора.

2.5. Декомпозиция задачи.

Глава 3. Метод компактного представления программ на основе частотных характеристик их поведения.

3.1. Общее описание предложенного метода компактного представления программ.

3.2. Компактирование программы.

3.3. Выполнение скомпактированной программы.

3.4. Корректность предложенного метода компактного представления программ

Глава 4. Метод определения частотных характеристик программы.

4.1. Задача вычисления частоты выполнения фрагментов кода программы

4.2. Основные понятия и определения.

4.3. Методы профилирования программ.

4.4. Метод оценки частоты выполнения фрагментов кода программы

4.5. Практическое исследование метода. 4.6. Выводы.

Глава 5. Метод определения редко-выполняемого кода программы

5.1. Определение редко-выполняемого кода программы.

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

5.3. Задача компактного представления редко-выполняемого кода

5.4. Применение предложенного метода компактного представления программ в системах реального времени.

5.5. Выводы.

Глава 6. Реализация и апробация метода компактного представления программ.

6.1. Структура прототипа предложенного метода компактного представления программ.

6.2. Испытания прототипа предложенного метода компактного представления программ.

6.3. Выводы.

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

Программы реального времени - это широкий класс программ, время реакции которых на внешние воздействия должно укладываться в заданные временные рамки. Корректность работы таких программ определяется не только корректностью логики их функционирования, но и временем их исполнения в вычислительной системе. Примерами таких программ служат операционные системы реального времени, управляющие системы сложными техническими комплексами (например, атомные электростанции, автоматические производственные линии, системы противовоздушной и противоракетной обороны, системы обработки радиолокационной информации) и программное обеспечение встроенных систем [5, 6, 12, 13, 40, 56].

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

1. встроенные системы реального времени являются одним из наиболее распространенных классов систем реального времени [6, 13];

2. проблема компактного представления программ для встроенных систем реального времени является особо актуальной [6, 7, 9].

Встроенные системы

В настоящее время каждый технически сложный объект оснащается встроенной системой управления. Количество микропроцессоров, используемых во встроенных системах, превышает в несколько раз количество микропроцессоров, используемых в персональных компьютерах [6]. Это объясняет, почему встроенные системы являются одной из основных областей применения средств вычислительной техники и разработки программного обеспечения [13, 28, 40].

В отличие от систем общего назначения, проектирование различного рода встроенных систем накладывает на разработчиков дополнительные ограничения, что обеспечивает сложность разработки программного обеспечения встроенных систем. При разработке программного обеспечения необходимо учитывать такие вещи, как надежность, безопасность, временные ограничения и ограничения на количество ресурсов. Подходы, используемые современными программистами при создании больших программных систем общего назначения, в мире встроенных систем, как правило, не* применяются, или их применение затруднительно [6].

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

Например, как видно из таблицы 1, для большинства бортовых цифровых вычислительных машин современных летательных аппаратов объем доступной памяти находится в диапазоне от 0.5 до 10 Мб. А рекомендованный объем памяти для перспективных летательных аппаратов колеблется от 16 до 32 Мб [7, 9].

Добавление большего объема памяти является трудоемкой задачей из-за массогабаритных параметров системы. На модуль памяти накладываются требования надежности (например, резервирование), устойчивости к элек

БЦВМ Объем памяти (ОЗУ + ПЗУ) Самолет

0рбита-20 {1977) 132 КБайт Су-27, МиГ-29

Ц-100 (1982) 136 КБайт Су-27, МиГ-29

БЦВМ-386 (1995) БЦВМ-486 (1997) 2250 КБайт Су-ЗОМК(К)

16-32 МБайт

Таблица 1. Объем памяти в используемых БЦВМ. тропомехам и перегрузкам, что обеспечивает большую массу и размер этих устройств.

Для мобильных устройств ситуация с памятью схожая, но причины её ограниченности несколько иные. Как видно из таблицы 2, в современных мобильных телефонах объем оперативной памяти находится в диапазоне от 4 до 64 Мбайт, в смартфонах от 384 до 768 Мбайт, а в используемых сенсорных датчиках от 2 до 8 Кбайт.

Сенсорные датчики1

MICA2 PIC16F СС1010 AtMegal28L WeBee3

4 КБайт, 4 КБайт 2 КБайт 4 КБайт 8 КБайт

Мобильные телефоны2

Nokia 6303 Nokia 7100 Nokia 3600 Nokia ХЗ Nokia 2323

32 МБайт 4 МБайт 32 МБайт 64 МБайт 4 МБайт

Смартфоны3

НТО Desire HD НТС Mozart Apple iPhone 4 НТС EVO 4G НТС Aria

768 МБайт 576 МБайт 512 МБайт 512 МБайт 384 МБайт

Таблица 2. Объем памяти в мобильных устройствах.

Добавить больше памяти в эти устройства проблематично из-за ограниченного количества энергетических элементов и ограниченного размера (пользователь хочет, чтобы, например, мобильный телефон был по-прежнему небольшим и компактным).

При этом постоянно растет количество и сложность задач, которые должны решаться во встроенных системах в независимости от того, что это - сенсорные датчики, мобильные телефоны или бортовые вычислительные системы.

В этих условиях важной характеристикой программы опять, как и в начале развития ЭВМ, становится занимаемый ею объем памяти.

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

Методы компактного представления программ (методы КПП) - это преобразования программ, которые уменьшают объем памяти, требуемый для размещения их программного кода в оперативной памяти компьютера (размер программы, англ. memory footprint), и при этом сохраняют функциональность программ.

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

Неформально работу методов КПП можно описать следующим образом. На вход методы КПП принимают программы в некотором представлении (от исходного текста до бинарного кода). Далее программы подвергаются

1 По материалам сайта capsil.org.

2 По материалам сайта wikimart.ru.

3 По материалам сайта phonegg.com. компактированию с целью уменьшения размера программы (см. рисунок 1).

Память

Рисунок 1. Работа методов КПП.

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

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

Применение методов КПП может способствовать сокращению требований программного обеспечения к памяти встроенной системы. Использование методов КПП в вычислительной системе потенциально приводит к снижению её стоимости и энергопотребления. Вышесказанное объясняет причину столь пристального внимания к развитию методов КПП.

Цель диссертационной работы

Целью данной диссертационной работы является исследование применимости методов компактного представления программ во встроенных системах реального времени.

Основные результаты

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

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

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

3. Предложен метод определения редко-выполняемого кода программы, позволяющий учитывать ограничения на время выполнения скомпак-тированной программы.

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

Структура работы

Работа состоит из введения, шести глав и заключения.

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

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

Третья глава посвящена новому методу КПП. Сформулированы ключевые идеи метода КПП, представлена схема и описан принцип его работы. Сформулированы задачи, которые надо решить при исследовании предлагаемого метода: определение частотных характеристик поведения программы и редко-выполняемого кода.

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

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

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

Заключение содержит описание основных результатов работы.

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

Основные результаты

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

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

3. Предложен метод определения редко-выполняемого кода программы, позволяющий учитывать ограничения на время выполнения скомпак-тированной программы.

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

Заключение

В данной главе сформулированы основные результаты диссертационной работы.

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

1. Смелянский Р.Л., Гурьев Д.Е., Бахмуров А.Г. Об одной математической модели для расчета динамических характеристик программы / / Программирование. — 1986. — Т. 6.

2. Ахо А., Сети Р., Ульман Д. Компиляторы: принципы, технологии и инструменты. — Издательский дом "Вильяме 2003. — Р. 768.

3. Калашников A.B., Костенко В.А., Маркин М.И. Средства конструирования итерационных алгоритмов для решения задач комбинаторной оптимизации // Искусственный интеллект. — 2004. — Т. 2. — С. 91-95.

4. Скрипкин В.А., Моисеенко Е.А. Математические методы исследования операций в военном деле. — М.: Военное издательство министерства обороны СССР, 1979.

5. Блискавицкий A.A., Кабаев C.B. Операционные системы реального времени (обзор) // Мир компьютерной автоматизации — 1995. — Т. 1.

6. Программное обеспечение встроенных вычислительных систем. / А.О. Ключев, П.В. Кустарев, Д.Р. Ковязина, Е.В. Петров. — СПб.: СПб-ГУ ИТМО, 2009.-С. 212.

7. Колпаков К. История развития бортовых цифровых вычислительных машин в России // PCWeek. 1999. - Т. 32.

8. Гнеденко Б.В. Курс теории вероятностей. — УРСС, 2001. — Р. 448.

9. Павлов A.M. Принципы организации бортовых вычислительных систем перспективных летательных аппаратов // Мир Компьютерной Автоматизации: Встраиваемые Компьютерные Системы — 2001. — Т. 4.

10. Ногин В.Д. Принятие решений в многокритериальной среде: количественный подход, — М.: Физматлит, 2002. — Р. 176.

11. Ватолин Д. Методы сжатия данных.— М.: Диалог-МИФИ, 2003.— С. 384.

12. Золотарев С. Современные операционные системы реального времени для перспективной авионики // Военный парад. — 2006. — Т. 6.

13. Энджел Д. 2011-й: главные тенденции на рынке встроенных систем // PC Week. 2010.

14. Arm documentation. — www.arm.com/documentation/.

15. Arm processors. — www. arm. com/products/processors/.

16. Arnold K., Gosling J., Holmes D. The Java Programming Language. — Prentice Hall, 2000. P. 704.

17. Ball Т., Larus J. Optimally profiling and tracing programs // ACM Transactions on Programming Languages and Systems (TOPLAS').—■ July.— Vol. 16. Pp. 1319-1360.

18. Ball Т., Larus J. Optimally profiling and tracing program // Principles of Programming Languages (POPL). — ACM, 1992. —January. — Pp. 59-70.

19. Benini L. Selective instruction compression for memory energy reduction in embedded systems // The International Symposium on Low Power Electronics and Design (ISLPED). ACM, 1999.

20. Beszedes A., Ferenc R., Gyimothy T. Survey of code-size reduction methods // ACM Computing Surveys. — 2003.

21. Brown P. Macros without tears // Softiuare: Practice and Experience.— 1979. Vol. 9.

22. Cate V., Gross T. Combining the concepts of compression and caching for a two-level filesystem // Architectural Support for Programming Languages and Operating Systems (ASPLOS).- 1991.

23. De Sutter B., Bosschere K. Software techniques for program compaction // Communications of the ACM. — 2003. — August. Vol. 46. — Pp. 47-52.

24. Debray S., Evans W. Profile-guided code compression // Programming language design and implementation (PLDI).— ACM, 2002.

25. Debray S., Evans W. Cold code decompression at runtime // Communications of the ACM. 2003. - August. - Vol. 46. - Pp. 55-60.

26. Documentation for the llvm system. — http://llvm.org/docs.

27. Drtesy. — http://lvk.es.msu.su/index.php/articles/65.

28. Embedded computing design. — www. embeddedcomputing. com.

29. Ernst J., Evans W. Code compression // Programming Language Design and Implementation (PLDI). — ACM, 1997.- Pp. 358-365.

30. Fisher A., Freudenberger S. Predicting conditional branch directions from previous runs of a program // Architectural Support for Programming Language and Operation Systems (ASPLOS). — ACM, 1992. — October.— Pp. 85-95.

31. Fraser C. Automatic inference of models for statistical code compression // Programming Language Design and Implementation (PLDI).— Vol. 5.— ACM, 1999.- Pp. 242-246.

32. The gnu compiler collection. — http: //gcc. gnu. org/.

33. Graham S. An execution profiler for modular programs // Software: Practice and Experience. — 1983. — Pp. 671-685.

34. Grove D., Chambers C. A framework for call graph construction algorithms // Transactions on Programming Languages and Systems (TOPLAS). Vol. 23. - ACM, 2001. - November. - Pp. 685-746.

35. Huffman D.A. A method for the construction of minimum-redundancy codes // Institute of Radio Engineers. — Vol. 40. — 1952. — September. — Pp. 1098-1101.

36. Raster D., Wilhelm S. Generic control flow reconstruction from assembly code // Languages, Compilers, and Tools for Embedded Systems (LCTES). — ACM, 2002.-June.

37. Kemp T.M., Montoye R.M. A decompression core for powerpc // IBM Jour- > nal of Research and Development. — September. — Vol. 42.

38. Knuth D.E. An empirical study of fortran programs // Software: Practice and Experience. — 1971. — Vol. 1. — Pp. 105-133.

39. Korolev V., Shevtsova I. An improvement of the berry-esseen inequality with applications to poisson and mixed poisson random sums // Scandinavian Actuarial Journal. — 2010.

40. Kozuch M., Wolfe A. Compression of embedded system programs // IEEE International Conference on Computer Design: VLSI in Computers and Processors. — 2000.

41. Krishnaswamy A., Giipta R. Profile guided selection of arm and thumb instructions // Languages, Compilers, and Tools for Embedded Systems (LCTES). ACM, 2002. - June. - Pp. 55-64.

42. Krishnaswamy A., Gupta R. Mixed-width instruction sets // Communications of the ACM. 2003. - Vol. 46. - Pp. 47-52.

43. Lecture on computer organization.— http://meseec.ce.rit.edu/ eecc550-winter2009/.

44. Lefurgy C. Efficient execution of compressed program: Ph.D. thesis / The University of Michigan. — 2000.

45. Levine S. Linkers and Loaders. — Morgan Kaufmann, 2000. — P. 256.

46. Lindholm T., Yellin F. The Java Virtual Machine Specification. — Prentice Hall, 1999. P. 496.

47. Mibench. — http : //www. eecs. umich. edu/mibench/.

48. Mips technologies. — www.mips . com/products/resourcelibrary/.

49. Muchnick S. Advanced Compiler Design and Implementation. — Morgan Kaufmann, 1997. P. 856.

50. Post-pass compaction techniques / B. De Bus, D. Kastner, D. Chanet et al. // Communications of the ACM. — 2003. — August. — Vol. 46. — Pp. 41-46.

51. Sarkar V. Determining average program execution times and their variance // Programing Language Design and Implementation (PLDI). — ACM, 1989. June. - Pp. 298-312.

52. Seal D. ARM Architecture Reference Manual. — Addison-Wesley Professional, 2000. P. 816.

53. Shafer G. A Mathematical Theory of Evidence. — Princeton University Press, 1976.

54. Smelianski R. L., Alanko T. On the calculation of control transition probabilities in a program // Information Processing Letters. — 1986. — Vol. 22.

55. Snu real-time benchmarks.— http://www.cprover.org/goto-cc/ examples/snu. html.

56. Stankovic J.A. Real-time computing // Byte Magazine. — 1992. — Vol. 17. — Pp. 155-160.

57. Sutter B., Bus B., Bosschere K. Sifting out the mud: Low level C++ code reuse // Object-Oriented Programming, Systems, Languages and Applications (OOPSLA).- ACM, 2002.-November. Pp. 275-291.

58. System support for automatic profiling and optimization / X. Zhang, Z. Wang, N. Gloy et al. // Symposium of Operating Systems Principles (SOSP). — ACM, 1997.-October.-Pp. 15-26.

59. Thuresson M., Stenstrom P. Evaluation of extended dictionary based static code compression schemes // Computing Frontiers (CF).— ACM, 2005.— Italy. P. 10.

60. Tip F., Sweeney P. Class hierarchy specialization // Acta Informatica. — 2000. Vol. 36.

61. Tip F., Sweeney P., Laffra C. Extracting library-based java applications // Communications of the ACM. — 2003. — August. — Vol. 46. — Pp. 33-40.

62. Visual c++ developer center.— http://msdn.microsoft.com/en-us/ visualc/.

63. Wall D. Predicting program behavior using real or estimated profiles // Programming Language Design and Implementation (PLDI).— ACM, 1991.— June. Pp. 59-70.

64. Whaley J. Partial method compilation using dynamic profile information // Object Oriented Programming Systems, Languages, and Applications (OOP-SLA). — ACM, 2001. — October. — Pp. 166-179.

65. Wu Y., Larus J. Static branch frequency and program profile analysis // International Symposium on Microarchitecture (MICRO). — ACM, 1994.— Pp. 1-11.