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

Введение .• • •

1. Организация и структура системы автоматизированного проектирования больших программ

1.1.Методы автоматизированного проектирования и отладки сложных программных комплексов

1.2.Функционирование подсистем в процессе проектирования встроенного программного обеспечения

1.3.Организация глобального контроля проектируемых программ в подсистеме оптимизации '.

Выводы

2. Алгоритмические основы функционирования подсистемы оптимизации

2.1.Практические методы глобальной оптимизации программ

2.2.Сведение задачи оптимального использования регистровой памяти к задачам теории графов.

2.3.Методы минимизации числа операторов безусловной передачи управления .•••.

2.4.Распределение регистровой памяти на линейных участках программ

2.5.Особенности минимизации числа операторов перехода в реальных программах. •

2.6.Ликвидация избыточных маршрутов

Выводы

3. Реализация и функционирование подсистемы оптимизации встроенных программ

3.1.Реализация распределения памяти мевду простыми переменными

3.2.Квазилинейные алгоритмы построения маршрутов переменных и графа несовместимости

3.3.Скоростной алгоритм линеаризации графа управления •

3.4.Реализация метода Урбано-Мюллера получения тупиковых дизъюнктивных форм булевых функций

3.5.Возможности и результаты оптимизации реальных встроенных программ

Выводы.

Актуальность проблемы. В настоящее время в развитии вычислительной техники наблюдается тенденция к повышению удельного веса так называемых персональных ЭВМ. Небольшие размеры, относительная дешевизна, возможность оперативного получения результатов вычислений, отсутствие рутинной работы, связанной с подготовкой задач к счету в вычислительных центрах, оборудованных большими универсальными ЭВМ, доступность для непрофессионалов - вот основные качества персональных машин, которые определяют их массовое распространение. Тем не менее, являясь малыми по размерам и стоимости, многие из персональных ЭВМ обладают развитой периферией и сложным программным обеспечением; операционными системами, позволяющими объединить в единый вычислительный комплекс ЭВМ и внешние устройства, трансляторами и интерпретаторами с языков высокого уровня. Вычислительная мощность таких персональных ЭВМ позволяет поставить их в один ряд с большими вычислительными машинами второго поколения. Варьируя состав программного обеспечения, на основе и тех же аппаратных средств можно создавать различные по своему назначению вычислительные комплексы.

Создание программного обеспечения вычислительных комплексов на базе микро- и мини-ЭВМ требует больших затрат труда квалифицированных программистов.Если программное обеспечение - встроенное, то оно становится частью аппаратуры и оперативному изменению не подлежит. Все их недостатки тиражируются при производстве ЭВМ. Более эффективные программы позволяют получить фактически более мощные машины. Поэтому одной из целей при разработке встроенного программного обеспечения (ВПО) должна быть оптимиаация программ в отношении быстродействия и занимаемого объема.

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

САПР)»которые обеспечивают формирование и отладку программ, а также выпуск проектной документации, поступающей на производство. Проектируемые программы имеют, как правило, большой объем (десятки тысяч команд). В этих условиях значительно возрастает трудоемкость отладки. В процессе формирования программное обеспечение разбивается на модули, и возрастают накладные расходы, связанные с организацией межмодульных связей. Возникают задачи по согласованию глобальной информации, используемой в нескольких модулях. С ростом величины программ возрастают требуемые ресурсы инструментальной ЭВМ и время тестирования. Традиционные САПР не содержат средств решения указанных задач. Возникает противоречие между объемом и качеством проектируемых программ. Поэтому представляет интерес создание в рамках САПР средств глобального контроля и от-тимизации программ. Такие средства целесообразно оформить в виде подсистемы, совместимой, с точки зрения представления информации, с другими подсистемами. Желательный режим работы подсистемы - диалоговый, позволяющий удобно совместить процессы оптимизации и отладки. Наряду с традиционными методами, использование методов оптимизации приведет к повышению качества проектируемых программ.

Предметом исследования является комплекс вопросов, связанных с оптимизацией и контролем проектируемых программ в рамках САПР ВПО.

Цель работы заключается в исследовании и разработке структуры и алгоритмов функционирования подсистемы оптимизации в рамках САПР ВПО. Указанная цель достигается решением следующих задач:

- организация взаимодействия подсистемы оптимизации с другими подсистемами в процессе проектирования ВПО;

- - анализ и разработка алгоритмов оптимизации программ, лежащих в основе функционирования подсистемы оптимизации; особое внимание уделено алгоритмам глобального распределения памяти;

- создание входного и выходного языка подсистемы оптимизации; разработка и реализация транслятора входного языка;

- обеспечение диалогового режима работы по оптимизации проектируемых программ.

Методы исследования.При решении поставленных задач использовались принципы организации и использования САПР ВПО, теория программирования, аппарат теории графов и теории вероятностей. Использовались также результаты практического использования САПР ВПО.

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

1) разработана методика проектирования больших программных комплексов, ориентированная на достижение высокого качества проектируемых программ; ее особенностями являются:

- этап перехода от проектируемой программы, заданной в терминах входного языка САПР, к объектной программе состоит в том, что из некоторого класса эквивалентных между собой программ, удовлетворяющих заданию на проектирование, выбирается программа, отличающаяся высоким быстродействием и занимающая минимально возможный объем памяти;

- в САПР ВПО вводится специальный компонент, решающий указанную задачу: подсистема оптимизации ВПО;

- вая работа по оптимизации программ проводится в терминах входного языка САПР ВПО;

2) в рамках исследования алгоритмических основ функционирования подсистемы оптимизации:

- обобщена задача экономии памяти в схеме Лаврова на случай максимального полного использования регистровой памяти;

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

- решена задача минимизации числа пересылок между простыми переменными;

- получены оценки эффективности алгоритмов, решающих перечисленные выше задачи;

- получена новая верхняя оценка хроматического числа графа;

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

4) разработана структура подсистемы оптимизации, ядро которой инвариантно по отношению к особенностям процессора объектной ЭВМ.

Практическая ценность и реализация результатов. На основании полученных теоретических результатов создана САПР ВПО, включающая в себя подсистему оптимизации. Подсистема позволяет обрабатывать в одном сеансе программы достаточно большого объема (до б тыс.инструкций для самой трудоемкой операции). САПР была использована в ВЦ ИСЭП АН СССР и ПО "ЛЭМЗ" при разработке персональных мини-ЭВМ с развитой системой интерпретации, серийно выпускаемых в настоящее время Курским заводом "Счетмаш". Некоторые алгоритмы, реализованные в подсистеме оптимизации, используются в библиотеках общего пользования в ВЦ ИСЭП АН СССР.

Апробация работы. Основные результаты диссертационной работы докладывались на I Всесоюзной конференции "Системы телеобработки" (Рига, 1977 г.), на республиканском семинаре "Методы и средства имитационного моделирования и их использование при анализе и проектировании сложных технических систем" (Киев, 1981 г.), на семинарах по системному программированию в Институте кибернетики АН УССР (Киев, 1982 г.), в Институте проблем управления АН СССР (Москва, 1982 г.).

Публикации. По теме диссертационной работы опубликовано шесть печатных работ.

I. ОРГАНИЗАЦИЯ И СТРУКТУРА СИСТЕМЫ АВТОМАТИЗИРОВАННОГО ПРОЕКТИРОВАНИЯ БОЛЬШИХ ПРОГРАММ

Выводы:

- показана возможность реализации методов глобальной оптимизации программ в диалоговых системах автоматизации проектирования вычислительных комплексов;

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

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

- на основании разработанных алгоритмов в рамках САПР ВПО создана подсистема оптимизации встроенных программ;

- показана структура подсистемы и методы ее применения к проектируемым программам;

- на примере показаны возможности применения подсистемы к реальной программе;

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

ЗАКЛЮЧЕНИЕ

В результате проведенных в диссертационной работе исследований получены следующие основные результаты:

1) разработана методика проектирования больших программных комплексов, ориентированная на достижение высокого качества проектируемых программ; в отличие от известных, предлагаемая методика позволяет представить процесс получения объектной программы в виде двух этапов: первый этап состоит в переходе от программы, заданной на входном языке САПР ВПО, к схеме программы, которой соответствует класс объектных программ, удовлетворяющих заданию на проектирование программного обеспечения; второй этап заключается в построении по заданной схеме такой объектной программы, которая отличается повышенным быстродействием и наименьшим объемом занимаемой памяти;

2) предложена структура САПР ВПО, особенностью которой является наличие в ней специального компонента, решающего указанную выше задачу получения объектной программы - подсистемы оптимизации, совместимой по представлению информации с другими подсистемами; предусмотрен автономный режим работы подсистемы, позволяющий повысить надежность и достоверность проводимых преобразований; наличие в САПР ВПО подсистемы оптимизации позволяет реализовать подход к проектированию программ, заключающийся в систематическом повышении их качества путем применения методов глобальной оптимизации программ;

3) в рамках исследования алгоритмических основ функционирования подсистемы оптимизации решены задачи:

- максимально полного использования регистровой памяти в программах общего вида;

- размещения объектных программ в памяти миниЭВМ, занимающего минимальный объем;

- минимизации пересылок между простыми переменными;

- получения оценок эффективности алгоритмов, решающих указанныв выше задачи;

4) разработан диалоговый язык директив оптимизации проектируемого программного обеспечения;

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

6) на основании разработанных алгоритмов и языка управления оптимизацией создана подсистема оптимизации встроенного программного обеспечения, ориентированная на автономную работу; ядро подсистемы составляют алгоритмы оптимизации программ, инвариантные относительно особенностей процессора объектной ЭВМ;

7) с использованием полученных в работе результатов была создана САПР ВПО, отличительной особенностью которой является наличие в ней подсистемы оптимизации; САПР ВПО была использована в ВЦ ИСЭП АН СССР и в ПО "ЛЭМЗ" при разработке персональных миниЭВМ с развитой системой интерпретации, серийно выпускаемых в настоящее время Курским заводом "Счетмаш".

1. Авен О.И., Коган Я.А. Управление вычислительным процессом в ЭВМ (алгоритмы и модели). - М.: Энергия, 1978, 240 с.

2. Автоматизация конструкторского проектирования в радиоэлектронике и вычислительной технике. Межвузовский тематический сборник. Вильнюс, 1982, т.2, 149 с.

3. Автоматизация логического проектирования. Минск: ИТК АН БССР, 1982, 158 с.

4. Автоматизированная система производства программ АПРОП. -Киев: ИК АН УССР, 1976, 134 с.

5. Айзенберг Я.Е. и др. Автоматизированная система производства программ СИНТЕРМ-2. В кн.: Технология программирования. Киев: ИК АН УССР, 1977, с.57-64.

6. Бабецкий Г.И. и др. АЛЬФА-система автоматизации программирования. Новосибирск: Наука, 1967, 308 с.

7. Баранов С.И. Автоматы на матрицах. Л.: ЛДНТП, 1976, с.5-26.

8. Баранов С.И. Синтез микропрограммных автоматов. Л.: Энергия, 1974, 2X6 с.

9. Баранов С.И. Минимизация условных вершин в граф-схемах алгоритмов. Киев: ИК АН СССР, 1972, 43 с.

10. Баранов С.И., Майоров С.А., Сахаров Ю.П., Селютин В.А. Автоматизация проектирования цифровых устройств. Л.: Судостроение, 1979, 264 с.

11. Батанов Л.А., Ковригин Б.Н., Саблуков A.M. Система автоматизации проектирования цифровых устройств. М.: МИФИ, 1977, 64 с.

12. Батищев Д.И. Системный подход к задачам машинного проектирования радиоэлектронных схем. В кн.: Автоматизированное оптимальное проектирование инженерных объектов и технологических процессов. 4.2. Горький, 1974, с.П-18.

13. Бессонов Ю.Е., Скоробогатов В.А. Применение относительных разбиений для поиска клик. В кн.: Автоматизация проектирования в микроэлектронике. Теория. Методы. Алгоритмы. Новосибирск: Институт математики СО АН СССР, 1978, с.24-33.

14. Борухович Е.П. Разработка и исследование автоматизированной системы производства программ для малых ЦВМ. Ленинград: ЛИАП, 1973, канд. дисс.

15. Вайда Ф., Чакань А. Микро-ЭВМ. М.: Энергия, 1980, с.105-274.

16. Варшавский В.И. Некоторые вопросы применения алгебры логики к конструированию вычислительных машин. В кн.: Трубы Государственного. комитета СМ СССР по судостроению. Л.: Судпромгиз, i960, вып. 1(22), с.16-42.

17. Вельбицкий СВ., Ходаковский В.Н., Шолмов Л.И. Технологический комплекс производства программ на машинах ЕС ЭВМ и БЭСМ-6. М.: Статистика, 1980, 263 с.

18. Виноградский Э.В. Диалоговая система для оперативной разработки программ САПР. В кн.: Организация управления процессами в САПР ЛА. М.: МАИ, 1982, с.47-54.

19. Витавер Л.М. Нахождение минимальных раскрасок вершин графа с помощью булевых степеней матрицы смежностей. Доклады АН СССР, 1962, т.147, № 4, с.758-759.

20. Глушков В.М., Капитонова Ю.В., Легппчевский A.A. О методике проектирования вычислительных машин в системе ПРОЕКТ. Кибернетика, 197I, № 2, с.1-17.

21. Грис Д. Конструирование компиляторов для цифровых вычислительных машин. М.: Мир, 1975, 544 с.

22. Губинский А.И., Ротштейн А.П. Применение обобщенного структурного метода для оценки диалоговых систем "человек-ЭВМ". В кн.: Диалоговые системы. Рига: Зинатне, 1980, вып.З, с.31-49.

23. Ершов А.П. Аксиоматика распределения памяти. В кн.: Теория языков и методы построения систем программирования. Киев-Алушта: 1972, с.3-21.

24. Ершов А.П. Введение в теоретическое программирование. М.: Наука, 1977, 288 с.

25. Ершов А.П. Операторные алгоритмы. Ш (об операторных схемах Янова). В кн.: Проблемы кибернетики. М.: Наука, 1968, с.181--200.

26. Ершов А.П. Основные проблемы построения программирующей программы. В кн.: АЛЬФА-система автоматизации программирования. Новосибирск: Наука, 1967, с.279-300.

27. Ершов А.П. Сведение задачи экономии памяти при составлении программ к задаче раскраски вершин графов. Доклады АН СССР, 1962, т.142, № 4, с.785-787.

28. Ершов А.П., Кожухин Г.И. Об оценках хроматического числа связных графов. Доклады АН СССР, 1962, т. 142, № 2, с.270-273.

29. Захаров В.Н., Поспелов Д.А., Хазацкий В.Е. Системы управления. Задание. Проектирование. Реализация. М.: Энергия, 1977,424 с.

30. Золотаревская М.Я. 0 реализации систем булевых функций в программируемых логических устройствах. В кн.: Проблемы управления в технике, экономике, биологии. М.: Наука, 1981, с. 64-70.

31. Зыков A.A. Теория конечных графов. Новосибирск: Наука, 1969, 544 с.

32. Илзиня И.Г. 0 проблеме выбора расцветки проводов. Автоматика и вычислительная техника. Рига: Зинатне, 1965, с.161-163.

33. ИСКРА-126. Техническое описание. 1Ц1.320.П9. Л.: Государственное союзное конструкторско-технологическое бюро по производству счетных машин, 1979.

34. Каневский Е.А. ЭКВМ на выставке "Системотехника-71". В кн.: Вопросы проектирования ЭКВМ. М.: ЦЭМИ АН СССР, 1973, вып.2, с.3-18.

35. Капитонова Ю.В. Вопросы проектирования вычислительных машин и специальных систем математического обеспечения. Автореферат докторской диссертации. Киев: ИК АН УССР, 1974, 19 с.

36. Капитонова Ю.В., Парницкий В.И. О реализации средств информационного обеспечения пользователей системы автоматизации проектирования. В кн.: Специальные средства проектирования и моделирования систем (проект ЕС). Киев, 1981, с.14-23.

37. Карцев М.А. Архитектура цифровых вычислительных машин. М.: Наука, 1978, 295 с.

38. Кнут Д. Искусство программирования для ЭВМ. М.: Мир, 1977, т.2, 724 с.

39. Кожухин Г.И. Взвешенная окраска вершин графа. В кн.: К.Берж. Теория графов и ее применения. М.: Издательство иностранной литературы, 1962, с.289-290.

40. Корячко В.П., Курчидис В.А. Об укладке графов программ. Изв. АН СССР. Техническая кибернетика. 1979, № 6, с.129-136.

41. Корячко В.П., Сускин В.В. Принципы организации САПР специализированных ЦВМ. В кн.: Всесоюзный семинар "Однородные вычислительные структуры и малые ЭВМ". М.: Институт проблем управления, 1979, с.77-79.

42. Котов В.Е. Введение в теорию схем программ. Новосибирск: Наука, 1978, 257 с.

43. Котов В.Е. Теория параллельного программирования. Прикладные аспекты. Кибернетика, 1974, № 2, с.1-18.

44. Красник Л.И., Неменман М.Е. Некоторые технологические принципы построения модульных программных систем. В кн.: Технология программирования. Киев: ИК АН УССР, 1977, с.16-45.

45. Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978, 432 с.

46. Кузнецов В.В., Родов A.A. Организация вычислительного процесса в САПР. В кн.: Автоматизация проектирования сложных систем. Новочеркасск: Политехнический институт, 1982, с.107-115.

47. Лавров С.С. Об экономии памяти в замкнутых операторных схемах.- Журнал вычислительной математики и математической физики, 196I, т.1, № 4, с.687-701.

48. Лазарев В.Г. Способ минимизации логической схемы алгоритме.- Автоматика и телемеханика, 1965, т.26, № 10, с.1838-1844.

49. Лезин Г.В., Кузнецов В.Е., Яроцкий В.П. ЭКВМ терминал с развитой системой интерпретации. - В кн.: Системы телеобработки. Рефераты докладов I Всесоюзной конференции. Рига: Зинатне, 1977, с.115-117.

50. Лйпаев В.В., Колин К.К., Серебровский Л.А. Математическое обеспечение управляющих ЦВМ. М.: Советское радио, 1972, 528 с.

51. Липаев В.В., Минаев М.А., Орлов С.Т. Функции и характеристики базы данных систем автоматизации проектирования комплексов программ. В кн.: Автоматизация проектирования систем управления. М., 1982, с.75-84.

52. Максимов М.Г., Попов В.В. Интерактивная САПР технологических процессов. Приборы и системы управления, 1982, № 8, с.4-6.

53. Мартынюк В.В. Об анализе графа переходов для операторной схемы.- Журнал вычислительной математики и математической физики, 1965, т.5, № 2, с.298-310.

54. Мартынюк В.В. Об экономном распределении памяти. Журнал вычислительной математики и математической физики, 1962, т.1,3, с.469-481.

55. Математйчёскоё обеспечение и автоматизация проектирования ЭВМ. -М.: ЦНЭУМ, 1981, 107 с.

56. Миллер Р. Теория переключательных схем. М.: Наука, 1970, т.1, 416 с.

57. Минина Т.Р. Разработка методов оптимизации в среднем для решения задач упорядочения в системах управления. Л.: ЛЭТИ, 1977, канд. дисс.

58. Морозов К.К., Одиноков В.Г., Курейчик В.М. Автоматизированное проектирование конструкций радиоэлектронной аппаратуры. М.: Радио и связь, 1983, 280 с.

59. Мячев A.A. Организация управляющих вычислительных комплексов. М.: Энергия, 1980, 272 с.

60. Ойт М. Система машинного проектирования. В кн.: Методы исследования нелинейных систем управления. М., 1983, с.215-221.

61. Орлова Г.И., Дорфман Я.Г. Оптимальное деление графов на несколько подграфов. Изв.АН СССР. Техническая кибернетика, 1972, № I, с.118-121.

62. Павленко В.К., Петраш В.Я. Вопросы построения системных программ, управляющих процессом автоматизированного проектирования. В кн.: Организация управления процессами в САПР ЛА. М.: МАИ, 1982, с.19-23.

63. Поспелов Д^А. Введение в теорию вычислительных систем. М.: Советское радио, 1972, 280 с.

64. Поспелов Д.А. Логические методы анализа и синтеза схем. М.: Энергия, 1968, 228 с.

65. Поттосин И.В. Экономия выражений в АЛЬФА-трансляторе. В кн.: АЛЬФА-система автоматизации программирования. Новосибирск: Наука, 1967, с.187-200.

66. Проблемы математического обеспечения систем автоматизированного проектирования. М.: МАИ, 1982, 74 с.

67. Рябов Г.Г., Арделян В.В. Принципы организации пакета программ для решения прикладных задач теории графов. Программирование, 1978, № 2, с.82-84.

68. Система ВАНГ-2200. Руководство для пользователей. Рига: Зинатне, 1974, 254 с.

69. Соботка 3., Стары Я. Микропроцессорные системы. М.: Энерго-издат, 1981, 494 с.

70. Сотникова Н.С. Диалоговая процедура формализации задач проектирования. В кн.: Диалоговые системы. Рига: Зинатне, 1980, вып.З, с.17-23.

71. Харари Ф. Теория графов. М.: Мир, 1973, 302 с.

72. Черейский М.М., Гитович А.А. Железняк Г.И., Сорокин А.С., Хав-кин В.М. Расширение языка БЭЙСИК для автономных средств графического диалога.-В кн.: Системы телеобработки. Рефераты докладов I Всесоюзной конференции. Рига: Зинатне, 1977, с.Ю5--107.

73. Щипулин И.Ф., Лукашевич В.П. Автоматизированные системы проектирования в машиностроении. М.: ЦИНТИ, 1982, 54 с.

74. Янов Ю.И. 0 логических схемах алгоритмов. В кн.: Проблемы кибернетики. М.: Физматгиз, 1958, вып.1. с.75-127.

75. Allen F.E. Program optimization. Annual Report, 1969 , 5, p.239-307.77* Anderson J.P. A note on compiling algorithms. Communications of the ACM, 1964, v.7, n.3, p.145-150.

76. Belady L.A. A study of replacement algorithms of a virtual-storage computer. IBM system ¿journal, 1966, 5, p.78-82.79* Brooks R.L. On colouring the nodes of a network. Proc. Cambridge Philos. Soc., 1941, 37, p.194-197.80