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

ВВЕДЕНИЕ.

1 АНАЛИЗ МЕТОДОВ РАСЧЕТА И СИНТЕЗА ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ.

1.1 Понятие спецвычислителя и алгоритма его функционирования.

1.2 Понятие и этапы конструирование программного обеспечения спецвычислителей.

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

1.4 Цели и методы моделирования спецвычислителей.

1.5 Анализ существующих методов оценки эффективности функционирования вычислительной системы.

1.6 Выводы.

2 ТЕОРЕТИЧЕСКИЕ ОСНОВЫ КОНСТРУИРОВАНИЯ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ СПЕЦВЫЧИСЛИГЕЛЕЙ.

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

2.2 Синтез множества возможных вариантов программного обеспечения спецвычислителя.

2.3 Синтез параметров оценки эффективности алгоритма функционирования вычислительной системы.

2.4 Группировка параметров оценки эффективности функционирования вычислительной системы.

2.5 Моделирование при конструировании программного обеспечения спецвычислителей.

2.6 Поиск внутри ограничивающей поверхности.

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

2.8 Выводы.

3 ОЦЕНКА ОСНОВНЫХ ХАРАКТЕРИСТИК ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ.

3.1 Оценка временных и вероятностных характеристик функционирования системы.

3.2 Моделирование прерываний.

3.3 Моделирование систем с общим каналом передачи данных.

3.4 Применение методов сокращения множества допустимых решений.

3.5 Оценка точности расчета параметров.

3.6 Выводы.

4 ЭКСПЕРИМЕНТАЛЬНЫЕ ИССЛЕДОВАНИЯ МЕТОДОЛОГИИ КОНСТРУИРОВАНИЯ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ СПЕЦВЫЧИСЛИТЕЛЕЙ.

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

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

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

4.4 Исследование точности полученных результатов.

4.5 Выводы.

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

- рост сложности целей и задач функционирования технических систем [2, 6, 8, 16, 34, 44, 45] и разнообразие входящих в их состав подсистем;

- развитие номенклатуры цифровых вычислительных устройств и расширение возможностей их применения для решения задач различной сложности [21,35, 46, 52, 58, 72].

На этапе системного проектирования [60, 75, 76] технического объекта возникает необходимость выбора или разработки программного обеспечения, структуры и аппаратной реализации спецвычислителя с тем, чтобы результаты проектирования отвечали предъявляемым к ним требованиям [1, 4]. В большинстве случаев решение таких задач связано с проблемой выбора структуры и технической реализации всей системы в целом [11, 12, 49]. Это обусловлено тем, что задачи, решаемые вычислителем, при неизменных алгоритмах решения могут иметь несколько возможных технических реализаций, что определяет альтернативные варианты программного обеспечения и структуры спецвычислителя. Каждый из вариантов обладает преимуществами и недостатками, характеризуется наборами показателей и обеспечивает различные характеристики разрабатываемой системы. Выбор неоптимального варианта влечет за собой рост технических и экономических затрат вследствие возможного неоднократного выбора варианта реализации спецвычислителя в случае необеспечения необходимых требований. Следует отметить, что выбор программного обеспечения однозначно определяет требования к структуре и аппаратной реализации спецвычислителя вследствие однозначности значений параметров, характеризующих выбранный вариант. Сказанное показывает актуальность задачи выбора программного обеспечения спецвычислителя на этапе системного проектирования.

Работы по автоматизации проектирования различных систем проводились рядом отечественных и зарубежных ученых, таких как Сергиенко И.В., Горбатов В.А., Глушков В.М., Дроздов Е.А., Воронов В.Г., Железнов И.Г., Крон Г., Альсведе Р., Вегенер Г. и др. [2, 3, 16, 17, 19, 20, 24, 28, 29]. Однако научные исследования в этой области не обладают достаточной формализацией и не учитывают особенности отдельных классов технических систем. При этом разрабатываемые методы отличаются сложностью математического аппарата, что в практических случаях не всегда оправдано. Вследствие этого непосредственное применение методов автоматизации проектирования для решения задач, исследуемых в диссертации, не обеспечивает необходимых результатов.

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

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

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

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

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

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

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

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

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

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

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

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

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

Научная новизна работы заключается в следующем.

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

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

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

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

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

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

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

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

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

Материалы диссертации являются частью исследований при выполнении хоздоговорной НИР по договору № 23105 от 28 ноября 2001 г. «Разработка методик анализа и синтеза цифровых вычислительных систем мобильного комплекса» с ГУЛ КБП г. Тула.

Реализация результатов диссертационной работы. Прикладные результаты диссертационной работы были внедрены в ГУЛ «КБ Приборостроения», г. Тула; компания «Модем», г. Тула; Институт теоретической и экспериментальной биофизики РАН, г. Пущино Московской обл.

Теоретические результаты работы внедрены в учебном курсе «Микропроцессорные системы» на кафедре ЭВМ Тульского государственного университета.

Апробация работы. Основные положения диссертационной работы докладывались на следующих конференциях и семинарах: 1) Всероссийская межвузовская научно-техническая конференция студентов и аспирантов «Микроэлектроника и информатика - 99» (г. Москва, 1999); 2) 7 - я Международная студенческая школа - семинар «Новые информационные технологии» (г. Москва, 1999 г.); 3) Международная молодежная научная конференция «XXV Гагаринские чтения» (г. Москва, 1999 г.); 4) научно - техническая студенческая конференция технических вузов центральной России (г. Орел, 1999 г.); 5) Международная студенческая научно-техническая конференция, (г. Белгород, 2001 г.); 6) Всероссийская научно-практическая конференция. «Проблемы информатизации образования» (г. Тула, 2001 г.); 7) XV Международная научная конференция «Математические методы в технике и технологиях» (г. Тамбов, 2001 г.); 8) Научно-практические конференции профессорско-преподавательского состава ТулГУ (г. Тула 2000-2002 г.г.).

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

Характеристика работы. Диссертационная работа состоит из введения, четырех глав и заключения, изложенных на 135 страницах машинописного текста, содержит 31 рисунок, 5 таблиц, список использованной литературы из 88 наименований и приложения.

-1244.5. Выводы

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

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

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

5. ЗАКЛЮЧЕНИЕ

В целом по работе можно сделать следующие выводы.

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

2. Определен класс и рассмотрены этапы проектирования спецвычислителей, показана актуальность решения задачи конструирования программного обеспечения спецвычислителей на этапе системного проектирования.

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

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

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

6. Приведены целевые функции, применяемые при решении задач оценки допустимых вариантов, а также метод т+1 набора показателей для определения весовых коэффициентов целевых функций.

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

8. Разработана методика анализа прерываний при функционировании вычислительных систем.

1. Авен О.И., Гурин H.H., Коган A.A. Оценка качества и оптимизация вычислительных систем. М.: Наука, 1982. 376 с.

2. Автоматизация проектирования сложных логических структур / Горбатов В.А. и др., М., 1978. 352 с.

3. Алексеев О. Г., Комплексное применение методов дискретной оптимизации. М.: Наука, 1987. - 316 с.

4. Аоки М. Введение в методы оптимизации. Пер с англ. Главная редакция физико-математической литературы издательства «Наука», M., 1977. -344 с.

5. Балагуров В.А., Галтеев Ф.Ф. Электрические генераторы с постоянными магнитами. М.: Энергоатомиздат, 1988. 279 с.

6. Балыбердин В.А., Белевцев A.M., Степанов O.A. Оптимизация информационных процессов в автоматизированных системах с распределенной обработкой данных. М.: изд-во «Технология», 2002. 280 с.

7. Белкин А.Р., Левин М. Ш. Принятие решений: комбинаторные модели аппроксимации информации. М.: Наука. Гл. ред. физ.-мат. лит., 1990. 160 с.

8. Беляев Л. С. Решение сложных оптимизационных задач в условиях неопределенности. Новосибирск: Наука, 1978. - 126 с.

9. Богомолов A.M., Салий В.Н. Алгебраические основы теории дискретных систем. М.: Наука: Физматлит, 1997. - 368 с.

10. Браславский И .Я. Асинхронный электропривод с параметрическим управлением. М.: Энергоатомиздат. 1988. 222 с.

11. Брахман Т.Р. Многокритериалность и выбор альтернативы в технике. -М.: Радио и связь, 1984. 288 с.-12812. Бусленко Н.П. Моделирование сложных систем. М.: «Наука», М.,1978.

12. Вентцель Е.С. Введение в исследование операций. М.: Сов. радио, 1964. -388 с.

13. Вентцель Е.С. Теория вероятностей. М.: Наука. Гл. ред. физ.-мат. лит. - 1964.-576 с.

14. Вентцель Е.С., Овчаров JT.A. Теория вероятностей и ее инженерные приложения. М.: Наука. Гл. ред. физ.-мат. лит. - 1988. -480 с.

15. Востриков A.A. Синтез нелинейных систем методом локализации. -Новосибирск: Изд-во Новосиб. Ун-та, 1990. 120 с.

16. Вычислительные методы выбора оптимальных проектных решений. Михалевич B.C., Шор Н.З., Галустова Л.А. и др. / Киев: «Наукова думка», 1977. -178 с.

17. Герасимяк Р.П. и др. асинхронный электропривод с тиристорным управлением. Киев.: Техника, 1984. 150 с.

18. Горбатов В.А. Семантическая теория проектирования автоматов. М., 1979. 264 с.

19. Глушков В.М, Капитонова Ю.В., Летичевский A.A. Автоматическое проектирование вычислительных машин. Киев., 1978. 230 с.

20. Денисов A.A. Информационные основы управления. Л.: «Энергоатомиздат», Ленингр. Отделение. 1983. 72 с.

21. Диковский А.Я. Математические методы анализа программ: учеб. пособие. Калинин: КГУ, 1983. 49 с.

22. Дискретная математика для программистов / Ф. А. Новиков СПб: Питер, 2000. - 304 е.: ил.

23. Дроздов Е.А. Оптимизация структур цифровых автоматов. М., 1975.352 с.-12925. Евстигнеев В. А. Применение теории графов в программировани Наука, 1985. 352 с.

24. Еремин И.Н. Теория линейной оптимизации. Екатерт Екатеринбург, 1999. 312 с.

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

26. Железнов И.Г. Сложные технические системы (оценка характер! Учеб. пособие для техн. вузов. М.: Высшая школа, 1984. - 119 с.

27. Железнов И.Г., Семенов Г.П. Комбинированная оценка характер сложных систем. М.: «Машиностроение», 1976. -55 с.

28. Карманов В.Г., Федоров В.В. Моделирование в исследовании опер М.: Твема, 1996.

29. Карпенко Б.К. и др. Шаговые электродвигатели. Киев: Техника, -216 с.

30. Кенио Т. Шаговые двигатели и их микропроцессорные сис управления. М.: Энергоатомиздат, 1987. 200 с.

31. Кини Р.Л., Райфа X. Принятие решений при многих критер предпочтения и замещения: Пер. с англ./Под ред. И.Ф. Шахнова. М.: Рад1 связь, 1981.-560 с.

32. Киселев В.Д., Есиков О.В., Кислицин A.C. Защита и нформащ системах ее передачи и обработки. М.: «Солид», 2000. - 200 с.

33. Клингман Э. Проектирование специализирован; микропроцессорных систем. Пер. с англ. к.т.н. В.И. Гуревича и др. М.: Мир, I1.- 363 с.

34. Комбинаторные методы и алгоритмы решения задач дискретt оптимизации большой размерности. М.: Наука, 2000. 360 с.

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

36. Кузьмин И.В., Кедрус В. А. Основы теории информации и кодирования. Киев: Вища школа, 1986. - 360 с.

37. Левин В. И. Структурно-логические методы исследования сложных систем.

38. Майника Э. Алгоритмы оптимизации на сетях и графах. М.: Мир, 1985. - 323 с.

39. Малашенко Ю.Е., Новикова Н.М. Модели неопределенности в многопользовательских сетях. М. : Эдиторал УРСС, 1999. 160 с.

40. Малишевский A.B. Качественные модели в теории сложных систем. -М.: Наука. Физматлит, 1998. 528 с.

41. Мальцев П. А. и др. Основы теории построения и контроля сложных систем. Л.: Энергоатомиздат, 1988. - 191 с.

42. Мальцев П.А. и др. Сети Петри в моделировании и управлении. Л.:1989.

43. Марков А.А, Нагорный Н.М. Теория алгоритмов. М.: Наука, 1984.432 с.

44. Меламед И.И., Сигал И.Х. Теория и алгоритмы решения многокритериальных задач комбинаторной оптимизации. М.: ВЦ РАН, 1996.

45. Месарович М., Такахара Я. общая теория систем: математические основы / Пер. с англ. Э.Л. Налпельбаума, М.: Мир, 197850. методы проектирования систем управления / В.Г. Воронов, В.Н. Гриценко, В. А. Клочко и др. Харьков: Основа, 1996. - 253 с.

46. Нильсон Н. Искусственный интеллект. Методы поиска решений. М.: , 1973.-272 с.

47. Острейковский В.А. Теория систем: Учеб. для вузов по спец. «Автом. Сист. Обр. информ. И упр.». М.: Высш. Шк., 1997. - 240 с.

48. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. Пер. с англ. М.: Мир, 1985 . - 512 с.

49. Питерсон Дж. Теория сетей Петри и моделирование систем: Пер. с англ. М.: Мир, 1984. - 264 с.

50. Пойа Д. Математическое открытие. М.:, 1976. 448 с.

51. Савин Г.И. Системное моделирование сложных процессов. М.: Фазис: ВЦ РАН, 2000 . -288 с.

52. Свами М. Тхуласираман К. Графы, сети и алгоритмы. М.: Мир, 1984.455 с.

53. Сигнаевский В,А., Коган Я.А. методы оценки быстродействия вычислительных систем / Под ред. О.И. Авена. М. : Наука, 1991. - 256 с.

54. Скэнлон Л. Персональные ЭВМ IBM PC и ХТ. Программирование на языке ассемблера. М.: Радио и связь. 1989. - 336 с.

55. Советов Б.Я. Яковлев С.А. Моделирование систем. М.: Высшая школа, 1985.-271 с.

56. Столов Л.И. и др. Моментные двигатели постоянного тока. М.: Энергоатомиздат, 1989. - 233 с.

57. Сычугов A.A. Вероятностный анализ алгоритмов.// Международная студенческая научно-техническая конференция: Сб. тез. докл. Белгород: Изд-во БелГТАСМ, 2001. - 4.2, - с. 61.

58. Сычугов A.A., Данилкин Ф.А. Использование графовой модели для анализа алгоритмов // Известия Тульского государственного университета. Серия: «Вычислительная техника, автоматика, управление». Том 3. Выпуск 1. Тула: ТулГУ, 2001, с. 75-81.

59. Сычугов A.A., Игнатьева Т.В. Оценка надежности записи на магнитных носителях // «Микроэлектроника и информатика 99». Всероссийская межвузовская научно - техническая конференция студентов и аспирантов: тезисы докладов. М.: МИЭТ, 1999. - с. 152.

60. Теория систем и методы системного анализа в управлении и связи /1. ВН.

61. Управление бесконтактными двигателями постоянного тока / Н.П. Адволотин и др., 1984. 160 с.

62. Фишберн П. Теория полезности для принятия решений. М.: Наука,1978.74. фон Нейман Дж., Моргенштерн О. Теория игр и экономическое поведение. М.: Наука, 1970.

63. Цвиркун А.Д. и др. Имитационное моделирование в задачах синтеза структуры сложных систем.

64. Цвиркун А. Д. Основы синтеза и структуры сложных систем. М.: Наука, 1982.

65. Шеннон Р. Имитационное моделирование систем искусство и наука. / Пер. с англ. под ред. Е.К. Масловского. М.: «Мир», 1978. - 418 с.

66. Штойер Р. Многокритериальная оптимизация. Теория, вычисления и приложения. Пер. с англ. М.: Радио и связь, 1992. - 504 с.

67. Игнатьев В.М., Ларкин Е.В. Сети Петри-Маркова. Учеб. пособие / ТулГУ. Тула, 1997. - 164 с.

68. Benot D. Motion estimation using invariance under group transformation. // Proc. 12th IAPR Int. Conf. Pattern Recogn., Jerusalem. Los Alamitos (Calif.), 1994. -P. 159-163.

69. Bernstein A., Program Analysis for Parallel Processing, IEEE Transactions on Electronic Computers, EC 15, No. 5, 1966, p. 757-762.

70. Karmakar N. A new polynomial-time algorithm for linear programming. Combinatorica, 1984, N 4, p, 373-395.

71. Karp R.M., Papadimitriu C.H. On Linear Characterization of Combinatorial Optimization Problems, Proc. Twenty-First Annual Symp. on Foundations of Comp. Sei., IEEE, 1980.

72. Mangasarian O.L., Meyer R.R., eds. Parallel methods in mathematical programming // Math Prog., 1988. V. 42.

73. Schriver A. Theory of linear and integer programming. N.Y. John Wiley, 1986,526 p.

74. The Windows Interface: an application design guide. Microsoft Windows Software Development Kit. // Microsoft, 1996.