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

ВВЕДЕНИЕ.'.

1. АНАЛИЗ СОСТОЯНИЯ ПРОБЛЕМЫ И ПОСТАНОВКА ЗАДАЧИ

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

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

1.3. Постановка задачи и цели исследования.

2. СИНТЕЗ АЛГОРИТМОВ ТОПОЛОГИЧЕСКОГО АНАЛИЗА ГРАФ-МОДЕЛЕЙ ВП

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

2.2. Алгоритм обнаружения топологических некорректностей

2.3. Алгоритм топологической декомпозиции граф-моделей большой размерности

2.4. Алгоритм топологического анализа циклических граф-моделей

2.5. Выводы.

3. РАЗРАБОТКА МЕТОДОВ И АЛГОРИТМОВ ОЦЕНКИ ПАРАМЕТРОВ НА ДЕТЕРМИНИРОВАННЫХ ГРАФ-МОДЕЛЯХ ВП.

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

3.2. Алгоритм приведения детерминированных граф-моделей к ациклическому виду.

3.3. Критерий и алгоритм проверки целесообразности вероятностного моделирования ВП.

3.4. Анализ чувствительности вероятностных граф-моделей

ВП к вариациям вероятностей передач управления

3.5. Выводы.

4. СИНТЕЗ МЕТОДОВ И АЛГОРИТМОВ ОЦЕНКИ ВЕРОЯТНОСТНЫХ ХАРАКТЕРИСТИК ПАРАМЕТРОВ ВП.

4.1. Вероятностные граф-модели элементарного вычислительного процесса и вычислительного процесса в укрупненных состояниях

4.2. Методы оценки вероятностных характеристик параметров вычислительных процессов

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

4.4. Алгоритм оценки стационарных вероятностей состояний ВП

4.5. Выводы.

5. ЭКСПЕРИМЕНТАЛЬНАЯ ПРОВЕРКА МЕТОДОВ И АЛГОРИТМОВ АПРИОРНОЙ ОЦЕНКИ ПАРАМЕТРОВ ПОСЛЕДОВАТЕЛЬНЫХ ВП

5.1. Топологический анализ и оценка экстремальных значений времени реализации реального ВП

5.2. Анализ чувствительности и оценка вероятностных характеристик времени реализации реального ВП

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

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

5.5. Выводы.

Актуальность проблемы. Одной из важнейших задач, выдвинутых ХХУ1 съездом КПСС, является перевод экономики развитого социалистического общества на путь интенсивного развития. Важное место при этом отводится развитию производства и широкому применению в народном хозяйстве управляющих вычислительных систем (УВС) /I/.

Управляющая вычислительная система является важнейшей составной частью современных сложных систем управления, а программное обеспечение (ПО) УВС обладает всеми характерными признаками современных сложных систем /41/, такими как единство цели функционирования элементов ПО, взаимодействие большого количества элементов, иерархичность структуры, стохастичность поведения, надежность и помехоустойчивость. Программное обеспечение УВС представляет собой комплекс программ, создаваемый как отчуждаемый продукт и являющийся по сути промышленным изделием. В связи с этим проектирование ПО УВС должно осуществляться промышленными методами на основе системного подхода с использованием систем автоматизированного проектирования (САПР).

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

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

Для оценки ресурсов УВС, требуемых комплексу программ в целом, и программным модулям, входящим в его состав, на ранних стадиях проектирования ПО систем управления используют методы моделирования процессов выполнения программ, т.е. вычислительных процессов (Ш). При этом задаются некоторой гипотетической технической структурой УВС, эксплуатационные характеристики элементов которой известны.

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

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

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

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

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

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

Методология исследований основана на применении матричных ме-методов теории графов, аппарата теории множеств и теории цепей

Маркова для решения топологических, детерминированных и вероятностных задач моделирования и оценки параметров последовательных ВП.

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

1. Разработка алгоритмов топологической декомпозиции граф-моделей ВП большой размерности и топологического анализа граф-моделей ВП со сложными циклическими участками.

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

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

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

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

Научная новизна полученных результатов состоит в том, что:

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

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

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

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

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

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

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

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

Разработанные методы и алгоритмы использовались при проектировании специального программного обеспечения АСУ ТП производства CMC

Первомайского химического завода и внедрены на одном из предприятий г. Москвы. Суммарный экономический эффект от внедрения составил 74,614 тыс.руб./год, что подтверждается актами о внедрении и справками о долевом участии.

Апробация работы. Основные результаты и положения проведенных исследований докладывались и обсуждались на б-ти Всесоюзных и республиканских конференциях в период с 1979-1983 г.г.

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

Структура и объем диссертации. Работа состоит из введения, пяти глав, заключения, изложенных на 159 страницах, включающих 21 рисунок, 10 таблиц, библиографии 82 отечественных и зарубежных источников и приложения.

Основные результаты работы приведены в работах /49,55,56,57, 63-65/, а также докладывались и обсуждались на:

- Всесоюзной научно-технической конференции "Состояние, перспективы разработки и применения средств вычислительной техники для управления технологическими процессами (г.Свердловск, 1979г.);

- Всесоюзном научно-техническом совещании "Высокопроизводительные вычислительные системы" (г.Тбилиси, 1981 г.);

- Ш Всесоюзном совещании по автоматизации проектирования систем автоматического и автоматизированного управления технологическими процессами (г.Иваново, 1981 г.);

- республиканской научно-технической конференции "Автоматизированные системы контроля и управления сложными промышленными объектами" (г.Харьков, 1982 г.);

- Всесоюзном семинаре "Оптимизация сложных систем" (г.Винница, 1983 г.);

- П республиканской научно-технической межведомственной конференции "Моделирование и автоматизация процессов проектирования, изготовления и эксплуатации сложных систем" (г.Одесса, 1983 г.);

- городской научной конференции "Перспективы применения статистических методов и развитие метрологии" (г.Харьков, 1982 г.г);

- заседании семинара "Автоматизированные системы управления и контроля" Дома техники Харьковского областного совета НТО (г.Харьков, 1982 г.);

- заседаниях семинара "Идентификация и оптимизация производственных комплексов" научного Совета по проблеме "Кибернетика"

АН УССР (г.Харьков, 1976-1982 гг.).

ЗАКЛЮЧЕНИЕ

1. Материалы ХХУ1 съезда КПСС.- М.: Политическая литература, 1981.- 223 с.

2. Артамонов Т.Т. Анализ производительности ЦВМ методами теории массового обслуживания.- М.: Энергия, 1972.- 177 с.

3. Артамонов Т.Т., Брехов О.М. Аналитические вероятностные модели функционирования ЭВМ.- М.: Энергия, 1978.- 368 с.

4. Балашов Е.П., Победнов В.А., Хвощ С.Т. К выбору способа статистического анализа характеристик программ специализированных ЦВМ.- УСиМ, Киев, 1979, № 4, с.8-43.

5. Басакер Р., Саати Т. Конечные графы и сети: Пер. с англ. /Под ред. А.И.Теймана.- М.: Наука, 1974.- 366 с.

6. Байцер Б. Архитектура вычислительных комплексов: Пер. с англ.

7. T.I и 2.- М.: Мир, 1974.- 498 с. и 566 с.

8. Берзтис А.Т. Структуры данных.- М.: Статистика, 1974.- 408 с.

9. Броди С.М., Кекелия В.И. Полумарковская модель машинной программы.- Кибернетика, 1972, $ I, с.66-69.

10. Важенин В.И., Воронцов Ю.В., Герман В.А. и др. Методы моделирования сложных систем на ЭВМ.- В кн.: Системотехника и математическое моделирование. Труды радиотехнического института АН СССР.- М., 1973, № 12, с.5-244.

11. Велев B.C., Боянов К.Л. Определение вероятностных характеристик времени выполнения машинных программ при помощи имитационного моделирования.- УСиМ, Киев: Наукова думка, 1977, № 6,с.65-67.

12. Герман В.А. О модели программ и методах расчета основных параметров модели.- В кн.: Алгоритмические методы проектирования цифровых систем.- Тезисы докладов П Всесоюзной межвузовской конференщи. Л., ЛИТМО: 1972, с.22.

13. Герман В.А. О расчете времени исполнения машинных программ.-В кн.: Цифровая вычислительная техника и программирование. /Под ред. А.И. Китова.-М.: Сов.радио, 1972, вып.7, с.31-50.

14. Головкин Б.А. Статистические методы в параллельном программировании для управляющих вычислительных систем. Управляющие системы и машины, 1973, №. 2, с. 69-73.

15. Головкин Б.А. Расчет паспределения вероятностей времени выполнения машинных программ. Управляющие системы и машины, 1974, № 3, с. 23-28.

16. Головкин Б.А. Графовые модели программ с вероятностными параметрами (современное состояние). Вопросы радиоэлектроники. Сер. Электронная вычислительная техника, 1976, вып. 6, с.3-26.

17. Головкин Б.А. Параллельная обработка информации. Программирование, вычислительные методы, вычислительные системы.- Изв. АН СССР. Техническая кибернетика, 1979, № 2, с. II6-I5I.

18. Головкин Б.А. Большие программные системы реального времении методы повышения их качества.- В кн.: Программное обеспечение вычислительных сетей и систем реального времени /ЙК АН УССР. Киев, 1981, с. 18-23.

19. Головкин Б.А. Расчет характеристик и планирование параллельных вычислительных процессов. М.: Радио и связь, 1983. - 273 с.

20. Голубев-Новоиилов Ю.О. Многомашинные комплексы вычислительных средств. М.: Сов.радио, 1967.- L\Zb- с.

21. Голубков Ю.А. Анализ вычислительной трудоемкости алгоритмаи некоторые смежные вопросы.- Труды семинара отдела структурных и логических схем /ИТМ и ВТ АН СССР.- М., 1968, сборник 5, с.71-93.

22. Голубков Ю.А. Вероятностные модели последовательного выполнения алгоритма.- Там же.- М., 1968, сборник № 5, с.51-70.

23. Дьяченко В.Ф. Определение времени выполнения алгоритмов.

24. В кн.: Управление сетями связи и синтез управляющих устройств.-М.: Наука, 1969, с.28-34.

25. Евдокимов А.Г. Оптимальные задачи на инженерных сетях.- Харьков, Вища школа, 1976,- 153 с.

26. Ершов А.Н., Ляпунов А.А. О формализации понятия программы.-Кибернетика, 1967, №5, с.40-57.

27. Зайцев В.Т. К определению среднего числа машинных операций реализуемого алгоритма.- В кн.: Вопросы промышленной кибернетики. Системы гра<|ической связи.- Киев, 1974, с.10-14.

28. Знак В.И. Алгоритм априорной оценки времени машинной реализации программы.- Автометрия, 1972, № I, c.IOI-IIO.

29. Знак В.И. К оценке времени достижения операторов программ.-Вычислительные системы /ИМ СО АН СССР.- Новосибирск, 1978, № 73, с.152-167.

30. Знак В.И. Некоторые вопросы априорной оценки эффективности алгоритмов, ориентированных на реализацию посредством ЭВМ /Автореф. дис. на соиск.уч.ст.канд.техн.наук.- Севастополь, 1979.- 19 с.

31. Знак В.И. К алгоритму оценки трудоемкости программ. Автометрия. Новосибирск, 1977, №4, с.34-40.

32. Иванов А.П. Оценка времени выполнения структурированных программ.- Механизация и автоматизация производства, 1981, № 3, с.29-31.

33. Карп P.M. Заметки о приложении теории графов к программированию для ЦВМ.- Кибернетический сборник. Пер.с англ. /Под ред. А.А.Ляпунова, О.Б.Лупанова, Н.Н.Рикко.- М.: ИЛ, 1962, вып.4, 123-134.

34. Касьянов В.Н. К оценке частоты выполнения операторов и переходов в программе.- Программирование, 1975, Л» 5, с.64-72.

35. Кемени Дж.Дж., Снелл Дж.Л. Конечные цепи Маркова: Пер. сангл. /Под ред. А.А.Юпкевича.- М.: Наука, Главная редакция физ.-мат. литературы, 1970.- 270 с.

36. Колин К.К., Липаев В.В. Проектирование алгоритмов управляющих ЦВМ.- М.: Сов.радио, 1970.- 343 с.

37. Корн Г., Корн Т. Справочник по математике (для научных работников и инженеров) /Под ред. И.Г.Арамановича.- М.: Наука, 1977.- 832 с.

38. Кузьмин И.В., Салыга В.И., Чайников С.И., Кадацкий А.Е. Марковские алгоритмы статистического анализа программ для управляющих вычислительных комплексов.- В кн.: Идентификация и оптимизация производственных комплексов /ИК АН УССР.- Киев, 1977, с.27-29.

39. Кутепов В.П., Перцов Е.Е. Оценка вероятности и среднего времени для множества путей вероятностного графа по регулярным выражениям.- ЦВТ и программирование /Под ред. А.И.Китова.-М.: Сов.радио, 1974, вып.8, с.16-20.

40. Ланкастер П. Теория матриц: Пер. с англ.- М.: Наука, 1978.280 с.

41. Липаев В.В. Качество программного обеспечения.- М.: Финансы и статистика, 1983.- 263 с.

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

43. Липаев В,В. Распределение ресурсов в вычислительных системах.- М.: Статистика, 1979.- 248 с.

44. Мессих И.Г., Собкин А.А., Штрик А.А. Методы автоматизированного анализа характеристик комплексов программ и распределения ресурсов производительности вычислительных средств.-УСиМ, Киев, 1980, № I, с.28-32.

45. Отладка систем управляющих алгоритмов ЦВМ /Под ред. В.В.Липа-ева.- М.: Сов.радио, 1974.- 328 с.

46. Основы теории вычислительных систем /Под ред. Майорова С.А.-М.: Высшая школа, 1978.- 408 с.

47. Поспелов Д.А. Классификация структур алгоритмов, реализуемых на вычислительных системах.- Изв. АН СССР. Техническая кибернетика, 1967, №5, с.128-135.

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

49. Разработка методов и инженерных методик оценки эффективности, оптимизации и синтеза АСУ предприятиями с дискретными производственными процессами. /Отчет по НИР, № IP 76012902 /В.И.Са-лыга, С.И.Чайников и др.- Харьков: ХИРЭ, 1977.- 131 с.

50. Разработка элементов математического обеспечения АСУ ТП производств CMC /Отчет по НИР, № IP 76030889 /В.И.Салыга, С.И. Чайников и др.- Харьков: ХИРЭ, 1982.- 229 с.

51. Разработка методов и алгоритмов автоматизированного проектирования систем контроля сложных объектов /Отчет по НИР,

52. IP 0182.0073465 /В.И.Салыга, С.И.Чайников и др.- Харьков: ХИРЭ, 1983.- 81 с.

53. РыжковА.П. Определение вероятностных характеристик вычислительного процесса, описываемого билогическим графом.- Изв. АН СССР. Техническая кибернетика, 1976, № 6, с.101-112.

54. Рыжков А.П. Правильная билогическая граф-модель параллельного вычислительного процесса и ее свойства.- Изв. АНСССР. Техническая кибернетика, 1976, J6 2, с.96-104.

55. Салыга В.И., Чайников С.И. Алгоритмы статистической оценки характеристик математического обеспечения управляющих вычислительных систем.- В кн.: Высокопроизводительные вычислительные системы. Тезисы докладов ВНТС /ИПУ АН СССР.- М., 1981,с.22-23.

56. Салыга В.И., Чайников С.И. Об одном подходе к решению задачи интеграции комплекса программ АСУ.- В кн.: Анализ и синтез систем управления и контроля /ИК АН УССР.- Киев, 1976, с.38-41.

57. Салыга В.И., Чайников С.И. Комплекс методов и алгоритмов анализа характеристик программного обеспечения ВС.- В кн.: Оптимизация сложных систем /Тезисы докладов Всесоюзного семинара. Винница: ВПИ, 1983, часть 2, с.137.

58. Салыга В.И., Чайников С.И. Методы решения задачи оценки ресурсов ВС в условиях САПР АСУ ТП.- В кн.: Тезисы докладов

59. Ш Всесоюзного совещания по автоматизации проектирования систем автоматического и автоматизированного управления технологическими процессами. Иваново: ИЭИ, 1981, с.31-32.

60. Сборник научных программ на Фортране. Часть 2 /Под ред. С.Я. Виленкина.- М.: Статистика, 1974.- 224 с.

61. Стратонович Р.Л. Теория информации.- М.: Сов.радио, 1975.424 с.

62. Трахтенброт Б.А. Алгоритмы и вычислительные автоматы.- М.: Сов.радио, 1974.- 200 с.

63. Трахтенгерц Э.А. Программное обеспечение автоматизированных систем управления.- М.: Статистика, 1974.- 288 с.

64. Цой С., Цхай С.М. Прикладная теория графов.- Алма-Ата: Наука, Казахской ССР, 1971.- 500 с.

65. Чайников С.И. Об одном алгоритме классификации состояний вычислительного процесса.- В кн.: Идентификация и оптимизация производственных комплексов. Киев, 1977, с.42-45.

66. Шаракшанэ А.С., Шахин В.П., Халецкий А.К. Испытания программ сложных автоматизированных систем.- М.: Высшая школа, 1982.- 192 с.

67. Янов Ю.И. О равносильности и преобразованиях схем программ. ДАН СССР. Т.ИЗ, 1957, № I, с.39-42.

68. Янов Ю.И. О матричных схемах. ДАН СССР. Т.ИЗ, 1957, № 2, с.283-286.

69. Заег СалрАеуД. ^е^^в/гta/согь шюС cptS/nizafton. of jrzogzctm* гуеЗс .—4PTPS A&c. mz, F&SS, iK4p,/>. 23-36.71. Seuzee S. foz sfatciti&iEoff&pecun диллсяр ЛFIPS Л&с. ffW,

70. Bowie, ttftf, fypfoafian* qf g&yti Ыеогу cn- fenyxdeg fafe&tKfteri /Ф6, tXf, ^,p 9-3/,