Дипломы, курсовые, рефераты, контрольные...
Срочная помощь в учёбе

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

ДиссертацияПомощь в написанииУзнать стоимостьмоей работы

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

Содержание

  • Введение
  • 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. В.П., Курчидис В. А. Об укладке графов программ. Изв. АН СССР. Техническая кибернетика. 1979, № 6, с.129−136.
  40. В.П., Сускин В. В. Принципы организации САПР специализированных ЦВМ. В кн.: Всесоюзный семинар «Однородные вычислительные структуры и малые ЭВМ». М.: Институт проблем управления, 1979, с.77−79.
  41. В.Е. Введение в теорию схем программ. Новосибирск: Наука, 1978, 257 с.
  42. В.Е. Теория параллельного программирования. Прикладные аспекты. Кибернетика, 1974, № 2, с.1−18.
  43. Л.И., Неменман М. Е. Некоторые технологические принципы построения модульных программных систем. В кн.: Технология программирования. Киев: ИК АН УССР, 1977, с.16−45.
  44. Н. Теория графов. Алгоритмический подход. М.: Мир, 1978, 432 с.
  45. В.В., Родов A.A. Организация вычислительного процесса в САПР. В кн.: Автоматизация проектирования сложных систем. Новочеркасск: Политехнический институт, 1982, с.107−115.
  46. С.С. Об экономии памяти в замкнутых операторных схемах.- Журнал вычислительной математики и математической физики, 196I, т.1, № 4, с.687−701.
  47. В.Г. Способ минимизации логической схемы алгоритме.- Автоматика и телемеханика, 1965, т.26, № 10, с.1838−1844.
  48. Г. В., Кузнецов В. Е., Яроцкий В. П. ЭКВМ терминал с развитой системой интерпретации. — В кн.: Системы телеобработки. Рефераты докладов I Всесоюзной конференции. Рига: Зинатне, 1977, с.115−117.
  49. В.В., Колин К. К., Серебровский Л. А. Математическое обеспечение управляющих ЦВМ. М.: Советское радио, 1972, 528 с.
  50. В.В., Минаев М. А., Орлов С. Т. Функции и характеристики базы данных систем автоматизации проектирования комплексов программ. В кн.: Автоматизация проектирования систем управления. М., 1982, с.75−84.
  51. М.Г., Попов В. В. Интерактивная САПР технологических процессов. Приборы и системы управления, 1982, № 8, с.4−6.
  52. В.В. Об анализе графа переходов для операторной схемы.- Журнал вычислительной математики и математической физики, 1965, т.5, № 2, с.298−310.
  53. В.В. Об экономном распределении памяти. Журнал вычислительной математики и математической физики, 1962, т.1,3, с.469−481.
  54. Математйчёскоё обеспечение и автоматизация проектирования ЭВМ. -М.: ЦНЭУМ, 1981, 107 с.
  55. Р. Теория переключательных схем. М.: Наука, 1970, т.1, 416 с.
  56. Т.Р. Разработка методов оптимизации в среднем для решения задач упорядочения в системах управления. Л.: ЛЭТИ, 1977, канд. дисс.
  57. К.К., Одиноков В. Г., Курейчик В. М. Автоматизированное проектирование конструкций радиоэлектронной аппаратуры. М.: Радио и связь, 1983, 280 с.
  58. A.A. Организация управляющих вычислительных комплексов. М.: Энергия, 1980, 272 с.
  59. Ойт М. Система машинного проектирования. В кн.: Методы исследования нелинейных систем управления. М., 1983, с.215−221.
  60. Г. И., Дорфман Я. Г. Оптимальное деление графов на несколько подграфов. Изв. АН СССР. Техническая кибернетика, 1972, № I, с.118−121.
  61. В.К., Петраш В. Я. Вопросы построения системных программ, управляющих процессом автоматизированного проектирования. В кн.: Организация управления процессами в САПР ЛА. М.: МАИ, 1982, с.19−23.
  62. Поспелов Д^А. Введение в теорию вычислительных систем. М.: Советское радио, 1972, 280 с.
  63. Д.А. Логические методы анализа и синтеза схем. М.: Энергия, 1968, 228 с.
  64. И.В. Экономия выражений в АЛЬФА-трансляторе. В кн.: АЛЬФА-система автоматизации программирования. Новосибирск: Наука, 1967, с.187−200.
  65. Проблемы математического обеспечения систем автоматизированного проектирования. М.: МАИ, 1982, 74 с.
  66. Г. Г., Арделян В. В. Принципы организации пакета программ для решения прикладных задач теории графов. Программирование, 1978, № 2, с.82−84.
  67. Система ВАНГ-2200. Руководство для пользователей. Рига: Зинатне, 1974, 254 с.
  68. Соботка 3., Стары Я. Микропроцессорные системы. М.: Энерго-издат, 1981, 494 с.
  69. Н.С. Диалоговая процедура формализации задач проектирования. В кн.: Диалоговые системы. Рига: Зинатне, 1980, вып. З, с.17−23.
  70. Ф. Теория графов. М.: Мир, 1973, 302 с.
  71. М.М., Гитович А. А. Железняк Г. И., Сорокин А. С., Хав-кин В.М. Расширение языка БЭЙСИК для автономных средств графического диалога.-В кн.: Системы телеобработки. Рефераты докладов I Всесоюзной конференции. Рига: Зинатне, 1977, с. Ю5--107.
  72. И.Ф., Лукашевич В. П. Автоматизированные системы проектирования в машиностроении. М.: ЦИНТИ, 1982, 54 с.
  73. Ю.И. 0 логических схемах алгоритмов. В кн.: Проблемы кибернетики. М.: Физматгиз, 1958, вып.1. с.75−127.
  74. 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.
  75. 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
Заполнить форму текущей работой