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

Введение.

Глава I. Модели вычислительных систем и методы моделирования

1.1. Особенности моделей ЭШ и вычислительных систем

1.2. Характеристики информационных потоков в вычислительных системах.

1.3. Методы имитационного моделирования

1.4. Аналитические методы.

Выводы.

Глава П. Моделирование вычислительных систем кусочно-линейным- марковским процесс ом.' с доходом

2.1. Переход от стохастической сетевой модели к кусочно-линейному марковскому процессу.

2.2. Кусочно-линейный марковский процесс с доходом.

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

2.4. Модель системы графического обеспечения.

Выводы. '.

Глава Ш. Приближенный метод анализа моделей вычислительных систем.

3.1. Система уравнений в вариациях для ожидаемого дохода кусочно-линейного марковского процесса

3.2.^-инвариантные кусочно-линейные марковские процессы и вычисление поправки к вероятности состояния .••.

3.3. Алгоритм и программная реализация метода.

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

3.4.1. Модель 2-х программной ЭВМ.

3.4.2. Модель 3-х программной ЭВМ.

3.4.3. Модель интерактивной системы с двумя терминалами.

Выводы.

Глава 1У. Применение метода последовательных вариаций для расчета устройств и систем вычислительной техники.

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

4.2. Оценка надежности структурно-резервируемых технических средств вычислительной техники в случае скользящего резервирования

4.3. Модель процессора с конвейерной обработкой команд

Выводы.

Актуальность проблемы. Широкое внедрение средств вычислительной техники во все отрасли народного хозяйства вызывает, как отмечается в "Основных направлениях экономического и социального развития на 1981-1985 годы и на период до 1990 года", необходимость "совершенствования вычислительной техники, ее элементной базы и математического обеспечения, средств и систем сбора, передачи и обработки информации" /I/.

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

Среди работ, посвященных исследованию и разработке методов анализа ВС, в первую очередь надо отметить работы Г.Т.Артамонова, О.М.Брехова, В.В.Липаева, О.И.Авена, Я.А.Когана, С.А.Майорова, Г.И.Новикова, Н.П.Бусленко, Л.Клейнрока /3,4,10,23,29,31/.

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

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

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

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

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

Методы исследования. Теоретической основой диссертации являются методы теории вероятностей, теории случайных процессов, теории марковских процессов с доходом.

Научная новизна. Предложен метод представления моделей ВС в виде кусочно-линейного марковского процесса с доходом.

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

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

Драктическая ценность и реализация результатов. Предложенный метод использовался в НИИЭВМ в 1979-1983 гг. для анализа структур разрабатываемых ЭВМ общего назначения. Созданная на основе метода программа включена в стандарт предприятия по расчету надежности вычислительных систем.

Дпробапия работы. Основные результаты диссертационной работы обсуждены на 1-ом Совместном советско-болгарском семинаре ИТК АН БССР - ИТК БАН "Оптимизация систем сбора, передачи и обработки аналоговой и дискретной информации в локальных ЭВМ" (г. Минск, 1973 г.), П-ой Всесоюзной конференции "Математическое обеспечение моделирования сложных систем (г. Киев, 1977 г.), Ш-ей Республиканской научно-технической конференции по радиоэлектронике (г. Вильнюс, 1979 г.), Всесоюзном совещании "Высокопроизводительные вычислительные системы" (г. Тбилиси, 1981 г.), Всесоюзном совещании "Автоматизированные системы массового обслуживания" (г. Нальчик, 1982 г.).

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

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

Основные результаты работы сводятся к следующему,

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

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

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

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

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

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

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

Заключение

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

1. Основные направления экономического и социального развития СССР на 1.8I-I985 годы и на период до 1990 года. - М.: Политиздат, 1981. - 95 с.

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

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

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

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

6. Артемьев В.М. Теория динамических систем со случайными изменениями структуры. Мн.: Вышэйшая школа, 1979. - 160 стр.

7. Башмаков И.А., Вензель Е.Ф. Приближенный метод анализа вычислительных систем. В сб. Использование ЭВМ в инженерных и научных исследованиях. Труды МЭИ. М., 1979, №'438,с. 69-74.

8. Беллман Р., Калаба Р. Динамическое программирование и современная .теория управления. М.: Наука, 1969. - 118 с.

9. Боровков A.A. Об условиях сходимости к диффузионным процессам в асимптотических методах теории массового обслуживания.

10. В кн. Труды международного конгресса математиков. М.: 1966, - с. 533-538.

11. Бусленко Н.П. Моделирование сложных систем. М.: Наука, 1968, - 400 с.

12. Валентейчик В.В., Вензель Е.Ф. Оценка параметров системы массового обслуживания при неопределенности в задании входного потока заявок. В сб. Вычислительная техника в машиностроении. Мн.: 1972, № 25. - с. 3-9.

13. Вензель Е.Ф. Применение аппарата динамического программирования для анализа кусочно-линейных процессов. Изв. АН БССР, физико-техн. серия. - Мн.: изд. АН БССР. - 1977, № 2,с. 105-110.

14. Вензель Е.Ф. Аналитическая модель некоторых типов вычислительных систем. В сб. Математическое обеспечение моделирования сложных систем. - Тезисы докладов. - К.: 1977.с. 98-100.

15. Вензель Е.Ф., Грек В.В., Заблоцкий В.Н. Модель вычислительного процесса на основе экспериментальных данных. В сб. Вопросы радиоэлектроники. Серия электронная вычислительнаятехника. Мн.: 1978, № 12, - с. 18-25.

16. Гнеденко Б.В., Коваленко И.Н. Введение в теорию массового обслуживания, М.: Наука, 1966. - 431 с.

17. Гуляев В.И. Численный метод исследования систем массового обслуживания. Изв. АН СССР, Техническая кибернетика, 1976, йб, - с. 140-146.

18. Драммонд М. Методы оценки и измерений дискретных вычислительных систем. М.: Мир, 1977. - 381 с.

19. Ефимушкина Н.В. Обзор работ, посвященных методам, средствам и результатам оценки и классификации вычислительной нагрузки ЭВМ. Зарубежная радиоэлектроника, 1982, tè 12, - с. 40-55.

20. Кениг Д., Штоян Д. Методы теории массового обслуживания, -М.: Радио и связь, 1981. 128 с.

21. Казаков И.Е. Статистическая динамика систем с переменной структурой. М.: Наука, 1977. - 416 с.

22. Клейнрок JI. Вычислительные системы с очередями. Мир.: Мир, 1979. - 600 с.

23. Климов Г.П. Стохастические системы обслуживания. М.: Наука, 1966. - 243 с.

24. Коваленко И.Н. Исследования по анализу надежности сложных систем. К.: Навукова думка, 1975. - 209 с.

25. Королнж B.C., Турбин А.Ф. Анализ асимптотически укрупняемых сложных систем. В кн. Математизация знаний и научно-технический прогресс. - К.: Навукова думка, 1975. - с. 45-65.

26. Кругликов В.К., Тарасов В.Н. Анализ и расчет сетей массового обслуживания с использованием двумерной диффузионной аппроксимации. Автоматика и телемеханика, 1983, № 8, - с. 74-83.

27. Кульбак М.И., Пшоник А.Г. Полумарковские модели надежности технических средств вычислительной техники. В сб. Вопросы радиоэлектроники, серия "Электронная вычислительная техника", 1981, № 12, - с. 59-71.

28. Липаев В.В., Яшков С.Ф. Эффективность методов организации вычислительного процесса в АСУ. М.: Статистика, 1975.256 с.

29. Методика определения производительности ЭВМ общего назначения. Машины вычислительные электронные цифровые общего назначения. Общие технические требования: ГОСТ 16325-76.

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

31. Приблуда A.A. Разработка аппаратного монитора модульного типа и исследование на его основе характеристик функционирования ЕС ЭВМ: Дисс. на соиск. уч.степени канд.техн.наук. Л., 1981 г. -Z07 с.

32. Пугачёв В.И. Комбинированные методы получения вероятностных характеристик. М.: Сов.радио, 1973, - 256 с.

33. Семенков О.И., Валентейчик В.В., Вензель Е.Ф., Заблоцкий В.Н. Оценка структур систем графического обеспечения. В сб. Вычислительная техника в машиностроении. - 1973, 1Ь 29, - с. 96106.

34. Сигалов Г.Г., Николаева Г.В. Приближенный расчет систем массового обслуживания с абсолютными приоритетами методом моментов. В сб. Автоматика и вычислительная техника. Мн.: 1981, вып. II, с. 54-58.

35. Сигалов Г.Г., Николаева Г.В. Приближенный расчет систем массового обслуживания методом уравнения моментов. В кн.: Тез. докл. У Всесоюзного совещания по статистическим методам в процессах управления, М.: 1981, - с. I50-I5I.

36. Скляревич Ф.А. Учет изменяемости структуры вычислительных систем. Автоматика и вычислительная техника, 1980, $ 6, -с. 63-68.

37. Скляревич Ф.А. Метод исследования функционирования фрагментов вычислительных систем с переменным режимом. Автоматика и вычислительная техника, 1982, й б, - с. 66-72.

38. Тихонов В.И., Миронов М.А. Марковские процессы, М.: Сов.радио, 1977, - 485 с.

39. Феррари Д. Оценка производительности вычислительных систем. -М.:■ Мир, 1981, 576 с.

40. Хинчин А.Я. Математические методы теории массового обслуживания. М.: изд. АН СССР, 1955, - 123 с.

41. Хинчин А.Я. Работы по математической теории массового обслуживания. -М.: Физматгиз, 1963, 235 с.

42. Виъиг Я. Сотргс1аиша£ а/уепуЛАгпл. {роь с/мЫ. гиЖмочМл,шсЭД, Согпт. ¿М АС.М, у16,А/9-

43. АхциНу, К.М., Нельму и., Що РаллтЯЬис сиия/^М. сЦ- с^мтип^ пхЬмяЛл.-Ш р. Ц-Ы. агЛ уЛЬ} Л/1,-р 36-^2.

44. СК&пЛу' К.М., Нт/мд, и., М/<ю/. Аррьохьггиии о^- ^¿¿ше/д^.яе^/мт!^ ТЛДМ штаг. ¿ипл. &М оЦ* Им,.1. Ъ*м1.} \/Л% /М.-р.К-Ю. —

45. St ùmtoii fil. fraxmpvuMiíy^ uubMJJJju. cuufL uxÍujiclUoti in im^jitipo^oomru^ ъуАшл,. Comm. ofj-tAt ACM, 1v.lf, A/Jr1. P .m-m.

46. S2. Rzílai^i W(hzruxrufai ii.} Stwipum. P.Л ßauttwu. úi pwyuim uí^Jiawu.-IBM ^ of Ы.

47. Я- Gtwouî>. SfaJtöw-l. ir. hffnM¿mAÍJL mxrckí frob jñxxsbum. uJjJUriaLLcrn. üi rrwütiJpiсудштгтЛ сотрьсЫь ^ ojf- ldfyvl,1. Ni.-p. t$5~i°)Z.

48. Sí (kfadz £v 6: PbofaMuUc rnoélL 0{- tomfndvL n^UrwL.-Pantíi,fUffxnt ¿SL RsucOmcM pjitf, U&№L; fUrcymiLOiMit, Plastee ; 4 3?s~, 1Hamht/ 27.tt. (rdzfdt E. On. aj^yu)x¿mx(i£ urnipulai rruyMt.-^. of tfa ACM, 4975, vii, N2,-pUi~m.

49. S6. Gvuhm WI., Д/слл^£ ¿k F Cyctùc c^ujujjdn^ üjyAttmA- УгНА пелХ/щ:-buí htyíA cj^jumju.^OpVL. Rju. } -196?, v.lf, p.2£(/-2tö

50. SI ^X. bkJbwrfr&A. off \лгаШ{1^ tirvu.- Opere. Ru., f v. S,- p.SIS1. S2Í.

51. SI KJvyajJL H.} Orumtio У, ПиулА ъ. Art appnûxiirwuLe. mriJuré /fa ét-PÍffn сиъ& cuudtyUï of an ALOHA lodern,-IEE.E on Crnnmt)im, V.2f, NiçpAHS-lSJ. 5~3L Kota^Wu. H- Some, vua*£ pnotjwu. ¿n curuxiyiLc -i^dlùu. oft

52. Um р€л|югпг<хпсе.o¡j- tfi¿ £úia¿ LL$A- frfttn. Gmyo.

53. Ко^а^аДс H. A^ÎloojUoti of iAt cUffiuMm. CLpp*oxim<aÀLon to (fyuz-usuuruj, n£¿/wnJU.~P&jvLI.- B^Y^UxMiLi-m cjftuuM ctUfyil^Mm.-^,bht ACM, 19? V,

54. Й. Kofo-yWu. H. Afyf&cAÍLorri ofj-tkjL dXffauicrn. Offioxx.rnCLÍion to c^uuim^ YwUnfwJU.~ßani}.-Tixuienl ^jmll JUtUUutUrn^ o/j-tfa-ACtf, im, V.ï-i, Nl-p'hSb-hM.6Л- ¡QrrifuUm /\. (n /Vn Z&Mtrcbasuf. -Loíuium. vf tAe cj^M^Murup ^гХгпы.

55. S. Шлея M., Kdky/KAÁi H. Асаллоису, of tM сЩ^ьишп ajypwxirrw. -tùm fot WM ^иал^- г^ЫмлЯл-,-IBM ¡Ь of Rjll. &ru£ ЪшЛч mii)V^8) A/2.-p.ll0-12<i.