Содержание к диссертации
Введение
1. Анализ состояния проблемы и постановка задачи 13
1.1. Методы оценки параметров последовательных вычислительных процессов в проблеме создания сложных систем . 13
1.2. Ретроспективный обзор методов моделирования и оценивания параметров последовательных вычислительных процессов 21
1.3. Постановка задачи и цели исследования . 28
2. Синтез алгоритмов топологического анализа граф-моделей вп 37
2.1. Методологические особенности использования топологических и детерминированных граф-моделей 37
2.2. Алгоритм обнаружения топологических некорректностей 46
2.3. Алгоритм топологической декомпозиции граф-моделей большой размерности 49
2.4. Алгоритм топологического анализа циклических граф-моделей 55
2.5. Выводы 63
3. Разработка методов и алгоритмов оценки параметров на детер минированных граф-моделях ВП 66
3.1. Методика расчета экстремальных значений параметров на детерминированных граф-моделях, содержащих циклические подграфы 66
3.2. Алгоритм приведения детерминированных граф-моделей к ациклическому виду 73
3.3. Критерий и алгоритм проверки целесообразности вероятностного моделирования ВП 76
3.4. Анализ чувствительности вероятностных граф-моделей ВП к вариациям вероятностей передач управления 85
3.5. Выводы 94
4. Синтез методов и алгоритмов оценки вероятностных харак теристик параметров ВП 97
4.1. Вероятностные граф-модели элементарного вычислительного процесса и вычислительного процесса в укрупненных состояниях 97
4.2. Методы оценки вероятностных характеристик параметров вычислительных процессов 103
4.3. Метод укрупнения состояний и алгоритм синтеза вероятностной граф-модели вычислительного процесса
в .укрупненных состояниях 114
4.4. Алгоритм оценки стационарных вероятностей состояний ВП 122
4.5. Выводы 127
5. Экспериментальная проверка методов и алгоритмов априорной оценки параметров последовательных ВП 128
5.1. Топологический анализ и оценка экстремальных значений времени реализации реального ВП 128
5.2. Анализ чувствительности и оценка вероятностных характеристик времени реализации реального ВП 137
5.3. Экспериментальная проверка работоспособности алгоритма топологической декомпозиции граф-моделей большой размерности 146
5.4. Программная реализация методов и алгоритмов априорной оценки параметров последовательных ВП 152
5.5. Выводы 157
Заключение 160
Список использованных источников
- Методы оценки параметров последовательных вычислительных процессов в проблеме создания сложных систем
- Методологические особенности использования топологических и детерминированных граф-моделей
- Методика расчета экстремальных значений параметров на детерминированных граф-моделях, содержащих циклические подграфы
- Вероятностные граф-модели элементарного вычислительного процесса и вычислительного процесса в укрупненных состояниях
Методы оценки параметров последовательных вычислительных процессов в проблеме создания сложных систем
Сложные системы управления промышленными, технологическими и социально-экономическими объектами имеют структуру, представляемую обычно в виде нескольких взаимодействующих подсистем, основными среди которых являются: - подсистема сбора и первичной переработки информации об управляемом объекте (информационная подсистема); - подсистема принятия решений и формирования команд управления (управляющая подсистема); - сеть каналов передачи данных (подсистема связи); - подсистема реализации исполнения команд управления на объекте (исполнительная подсистема); - объект управления.
Рост сложности объектов управления и повышение требований к эффективности их функционирования привели к необходимости использования вычислительной техники в управляющих подсистемах. Основой управляющих подсистем сложных систем управления являются, как известно, вычислительные системы (ВС), синтезируемые на базе цифровых вычислительных устройств (микропроцессоры, цифровые электронно-вычислительные машины, мультипроцессорные ВС, многомашинные ВС, распределенные микропроцессорные ВС и т.д.). В настоящее время наблюдается тенденция резкого роста стоимости разработки и внедрения программного обеспечения вычислительных систем. Например, если в 1970 г. на разработку и внедрение программного обеспечения ВС в США было затрачено около 20 млрд. долларов, то по оценкам экспертов в 1985 году затраты на эти цели составят порядка 200 млрд. долларов. Затраты же на аппаратуру при этом за тот же период возрастут с 5 млрд. долларов до 20 млрд.долларов /13/. Эта тенденция привела к возникновению ряда технологий программирования и связанных с ними направлений и подходов к созданию систем автоматизации программирования и отладки сложных комплексов программ /42/. Технология программирования независимо от ее типа содержит три этапа - проектирование алгоритма, кодирование алгоритма (составление программы) и отладка программы. Распределение затрат по этапам соответственно - 40$, 20$, 40$ от общей суммы затрат на получение готового программного продукта /45/. Общая же сумма затрат на программирование во многом определяется количеством алгоритмических ошибок в программах. Алгоритмические ошибки характеризуются особой сложностью их обнаружения методами формального автоматического контроля. В работе /45/ отмечается, что трудности обнаружения ошибок этого типа определяются, в основном, некорректностью постановок задач управления, вызываемой отсутствием для большинства алгоритмов строго формализованных постановок, и значительной степенью неопределенности при проектирований алгоритмов. Значительную часть алгоритмических ошибок составляют просчеты в оценках использования алгоритмами ресурсов ВС. Последствия таких просчетов обнаруживаются, как правило, на завершающих этапах работ по проектированию и внедрению сложных систем управления и ВС, а их устранение требует дополнительных материальных, трудовых и финансовых затрат и приводит к срыву сроков ввода систем в эксп луатапию. Основной причиной появления просчетов в оценках использования алгоритмами ресурсов ВС является субъективность таких оценок, обусловленная оцениванием по отдельным реализациям программ. Субъективность оценивания усугубляется еще и тем, что разработка алгоритмов и программ, реализующих эти алгоритмы зачастую ведется в различных организациях или в одной организации различными специалистами. Кроме того, отладка программ, реализующих алгоритмы управляющей подсистемы, в большинстве случаев производится на ВС, характеристики аппаратных средств я структура которой не совпадают с характеристиками аппаратных средств и структурой гипотетической ВС проектируемой сложной системы управления.
К настоящему времени известен ряд методов оценивания ресурсов ВС, необходимых для реализации вычислительных процессов, порождаемых алгоритмами /6,8,9,10,13,16,22,30,32,33,44,57,67,77,81/.
Основу этих методов составляет вероятностное моделирование алгоритмов с учетом характеристик аппаратных средств и структуры гипотетической ВС. Вероятностный характер моделей алгоритмов объясняется тем, что программы, являющиеся закодированной формой представления алгоритма и порождающие вычислительный процесс в ВС, обычно содержат команды передачи управления по условию. Наличие таких команд в программе создает неопределенность в выборе направления развития вычислительного процесса, а так как ресурсы (время, память, каналы,передачи данных и др.), необходимые для продолжения вычислительного процесса по различным направлениям, и вероятности передач управления неодинаковы, то при многократном выполнении программы значения требуемых ресурсов ВС являются случайными величинами.
Методологические особенности использования топологических и детерминированных граф-моделей
Как отмечалось в 1.3, в процессе решения задачи оценивания параметров, разработчик граф-модели должен учитывать следующие три аспекта моделирования: топологический, детерминированный и вероятностный.
Анализ существующих методов показал, что они не в полной мере учитывают особенности методологии использования топологических и детерминированных граф-моделей в процессе решения задачи. Из-за этого, в основном, и возникают трудности в практическом применении данных методов, вызываемые необходимостью ручного эквивалентного преобразования топологии и параметров граф-моделей.
Стратегия и последовательность этапов решения задачи оценивания, изображенная на обобщенной схеме, приведенной на рис.1.2, предполагает, что на первом этапе разработчик имеет топологичео кую граф-модель ВП, полученную вручную по блок-схеме алгоритма или автоматически по синтаксически правильному тексту программы. На этом этапе уже имеется возможность обнаружения и локализации топологических некорректностей следующих типов: изолированные, тупиковые, лишние участки rpa v-модели и ложные пути реализации моделируемого ВП. Первые три типа некорректностей хорошо известны и существуют алгоритмы их поиска и локализации. Методика устранения некорректностей последнего типа также известна /45/, но для ее применения необходимо либо знать ложные пути, либо иметь какие-то признаки, по которым их можно обнаружить.
Количество состояний на полученной разработчиком граф-модели может превышать значение tfmax. т.е. граф-модель может иметь такую размерность, при которой невозможно применение методов и алгоритмов оценивания параметров ВП на детерминированных и вероятностных граф-моделях. В то же время топологическая граф-модель, методы и алгоритмы анализа топологии позволяют эффективно решать задачи, размерность которых значительно превышает Мюос Для методов оценивания параметров на & С ,17,Я) и Gst(S,U,) Следовательно, необходима декомпозиция грайнмоделей большой размерности на этапе моделирования топологии ВП.
Для рассмотрения методологических особенностей использования детерминированных граф-моделей рассмотрим сначала методику определения детерминированных оценок параметров состояний ВП. - коэффициент учитывающий возможность параллельного выполнения команд h, -го типа с другими типами команд; 8 - быстродействие ВС по командам 4ь -го типа, или по выражению если известны коэффициенты еС = 6 /8 » т.е. отношения длительностей операций А -го типа ( /3 ) к длительности самой короткой операции (4/3 ) .
Количество информации, передаваемое во внешнюю среду или принимаемое из нее, определяется простым суммированием количества информационных единиц, передаваемых или принимаемых за время пребывания в состоянии Si . В качестве примера рассмотрим типичную конструкцию организации ввода информации в алгоритмическом языке ФСРЗРАН-ІУ:
В данном примере цифра І в операторе READ означает логический номер устройства ввода информации с перфокарт, приведенная здесь конструкция оператора ввода информации означает ввод одной перфокарты, на которой набито б чисел по формату F Стандартная перфокарта рассчитана на 80 колонок, каждая из которых соответствует 1-му байту информации (для ЭВМ серии ЕС). Таким образом, для определения 3-L необходимо подсчитать количество колонок на перфокарте, занимаемое данными и воспользоваться выражением
Методика расчета экстремальных значений параметров на детерминированных граф-моделях, содержащих циклические подграфы
В подразделе 2.4. отмечалось, что с топологической точки зрения расчет экстремальных значений параметров ВП сводится к определению простых путей ациклической грайьмодели Q(StU) . Известные методы приведения исходных граф-моделей к ациклическому виду, предложенные в работах /II, 45, 67, 77/, позволяют решать задачу только для простых циклов, а также для узкого класса рассмотренных в данных работах сложных циклических подграфов, что приводит к известным трудностям в применении этих методов на практике. В связи с этим задачу автоматизации процедуры удаления циклов нельзя считать решенной.
Рассмотрим некоторые особенности расчета экстремальных значений параметров на примере сложного циклического подграфа, изображенного на рис.3.1. Из рисунка видно, что данный подграф содержит k зацепленных цикла:
Кроме того, данный циклический участок имеет Ц выхода из вершин Sj , S? , 4» » &а Пусть задано множество . весов вершин Л , состоящее из элементов fit с Я ( « 1,13), и известны числа А а , Клин. » представдяющие собой максимальное и минимальное количество повторений циклов Ц8 , #1 , Z5, #1 . Если поло-жить ,,- = 0, то очевидна эквивалентная схема возможных реализаций ВП, представленная ациклическим подграфом, изображенным на рис.2.б. Нетрудно заметить, что на данном подграфе 8 путей. Пунктиром на рисунке помечены дуги, реализация которых невозможна при нулевых JCmin . Здесь следует отметить, что рассмотренный выше случай нулевых Кт;л является предельным, т.к. на практике эти числа могут быть отличными от нуля, что объясняется влиянием исходных данных на динамику прохождения циклических участков. Значение же К, , в общем случае, может быть любым положительным целым числом отличным от нуля. Тогда очевидным является тот факт, что числа Кл„л і Кніл не являются достаточными для описания динамики прохождения сложных циклических участков на граф-моделях. Эти числа характеризуют лишь экстремальные количества попаданий процесса в вершины se , sa , & s , т.к. эти вершины являются вершинами, лежащими на участках путей замыкающих циклы. Для простых (правильных) циклов, определение которых дано в работе /48/, эта особенность не характерна и, следовательно, задания -fCnax и Kmi достаточно для решения задачи, которое является тривиальным.
Таким образом, для решения задачи расчета экстремальных значений параметров для сложных циклических участков необходима детализация описания динамики прохождения циклов. Практически это можно реализовать путем задания для каждой вершины && чисел ЪтъхСО » nmin.C ) характеризующих максимальное и минимальное количество попаданий процесса в StS . Эти числа задаются, исходя из известных разработчику граф-модели чисел KmtKX , fm i и представления разработчика о динамике прохождения сложного циклического участка. При заданных «««/ , Н/п п.С ) задача расчета экстремальных значений параметров сводится к удалению замыкающих циклы дуг и вычислению этих значений по выражениям вида: ) где ej , Ять. - экстремальные значения параметра 2 каждого пь -го пути реализации ВП, образовавшегося после приведения подграфа к ациклическому виду; Ї - подмножество вершин s eS , входящих в /72 -й путь реализации ВП (/я = l,/f ), М - количество путей.
Наличие в обратных связях, замыкающих циклы, вершин, как например, в случае, изображенном на рис.3.2, приводит к некоторому усложнению процедуры расчета, т.к , возникает вопрос принадлежности этих вершин путям реализации и учета их весов 2.А.
При решении данного вопроса будем исходить из следующих предположений: - вершины &1 » лежащие на обратных связях, замыкающих циклит принадлежат всем jm , получаемым после приведения сложного циклического подграфа к ациклическому виду; - для завершения сложного цикла необязательно завершение простых циклов, составляющих данный сложный цикл.
Первое предположение непосредственно вытекает из требования единственности начальной вершины и общепринятого запрета вхождения извне в циклы любого типа. Второе объясняется наличием в сложном цикле нескольких выходов.
Вероятностные граф-модели элементарного вычислительного процесса и вычислительного процесса в укрупненных состояниях
Разработке методов и алгоритмов априорной оценки вероятностных характеристик последовательных ВП посвящен ряд работ /4,9,10, 17,23,27,33,34,39,44,64,70/ и др. Вероятностная модель в виде однородной поглощающей цепи Маркова, как показали авторы, с достаточной степенью адекватности описывает класс процессов, определенный в 2.1 как ЭВП. Несмотря на наличие, к моменту появления этих работ, мощного универсального численного метода расчета характеристик цепей Маркова упомянутого выше класса /35/, по ряду причин авторы отказывались от применения данного метода. Это привело к появлению инженерных методов и методик, изложенных в отмеченных выше работах.
Одной из основных причин, вызвавших необходимость разработки этих методов, является, по мнению авторов большинства работ в этой области, слишком большая трудоемкость расчета характеристик на мо делях большой размерности, связанная с необходимостью решения систем жнеиных уравнений высокого порядка. В то же время, как уже отмечалось в 1.2, предложенные в качестве альтернативы существующим методы потребоваж.сложных эквивалентных преобразований циклических подграфов на вероятностных граф-моделях, что привело к снижению их практической ценности по известным уже причинам. Данное обстоятельство, в частности, отмечено в работе /41/.
В то же время, в работах /56,57,63/ отмечалось, что метод расчета характеристик на однородных поглощающих цепях Маркова, предложенный в работе /35/, позволяет эффективно рассчитывать на современных ЭВМ серии ЕС вероятностные характеристики на цепях Маркова с кожчеством состояний 100. Если же учесть, что в соответствии с правилами модульного программирования программные модули, порождающие модежруемые ЭВП, имеют размеры, ограниченные 30-100 операторами на языках высокого уровня им 100-500 операторами мнемокода /41/ при 10-12 % команд условной или безусловной передач управления, то становится ясным, что кожчество состояний для реальных ВП не превышает 100. Это непосредственно следует из определения линейного участка ВП и приведенных выше данных.
Учтем также то, что нами в разделе 3 уже рассмотрены методы оценки экстремальных значений параметров на детерминированных граф-моделях и выбранный метод расчета вероятностных характеристик параметров ВП не требует никаких эквивалентных преобразований исходной вероятностной граф-модели. Последнее обстоятельство существенно, так как позволяет избавить разработчика вероятностной граф-модели ЭВП от необходимости знать метод расчета при решении задачи на ЭВМ.
Под состоянием ЭШ понимается линейный участок Ш, определение которого дано в 1.3. Параметры Зс& Л состояния S/ детерминированные оценки величин ti , ъ , %- , Уг , методика расчета которых приведена в 2.1. Очевидно, что вероятностная граф-модель GtfC&tU y&y для ЭВП получается из детерминированной граф-модели путем задания вероятностей, входящих в выражения (4.1), (4.2), для которых должны выполняться условия нормировки S/e=/ п. & и Ilfiy i Характерной особенностью поглощающей цепи является наличие в ней поглощающих состояний, для которых должно выполняться равенство /&=1 . Таким состояниям на &&(,& &) соответствует петля с единичной вероятностью возврата, что соответствует завершению (поглощению) процесса в данном состоянии & .
Таким образом, нами выбран метод расчета вероятностных характеристик параметров ЭШ и, с точки зрения излагавшегося в предыдущих главах материала, формализована вероятностная граф-модель ВП этого класса.
Рассмотрим теперь вычислительные процессы в укрупненных состояниях, определение которых было дано в подразделе 2.1.
С целью снижения размерности рассматриваемой граф-модели в 2.2 был разработан алгоритм декомпозиции, позволяющий топологичес 100 ки свести исходную граф-модель ЭШ большой размерности к граф-модели ШУС, размерность которой не превышает допустимую M ax .
В то же время известно, что при проектировании программного обеспечения используются принципы модульно-иерархического построения сложных комплексов программ /41,45/. Это обстоятельство обусловливает естественную декомпозицию сложного ЭВП на подпроцессы, число состояний в которых не превышает 100, что уже отмечалось выше. Поскольку метод расчета и модель для таких процессов определены, ниже остановимся на выборе метода расчета и формализации связанной с ним вероятностной граф-модели ШУС.
При этом будем считать, что состояния Ф на граф-модели Cyst(S ,U R) представляют собой ЭШ, для которых заданы Мг( ) , Д-fee) то есть математические ожидания и дисперсии, интересующих разработчика граф-модели, параметров ЕП. Таким образом, вероятностная граф-модель ШУС - &(& & &) отличается от вероятностной граф-модели ЭВП - G&t(Stt/9R) векторами параметров состояний. Если для ЭВП это детерминированные оценки, то для ШУС -вероятностные. Впервые такое представление вероятностной модели Ш, очевидно, было использовано в работе /8/ и были отмечены ее полумарковские свойства. Однако наиболее эффективным методом расчета вероятностных характеристик параметров Ш на моделях этого класса считается метод, именуемый как "преобразование звезда-ячейка", детально описанный в работах /6,71/ и развитый в работе /16/. В основу данного метода положена граф-модель в виде полумарковской однородной поглощающей цепи, которую и будем в дальнейшем считать вероятностной граф-моделью ВПУС - G-stC yVl ) .
