Содержание к диссертации
Введение
ГЛАВА 1. Анализ методов моделирования процессов обработки информации в АСУ 20
1.1. Определение класса анализируемых методов 20
1.2. Точные методы анализа 23
1.3. Приближенные методы анализа 28
1.4. Декомпозиционный метод вложенных процессов 35
1.5. Имитационные и гибридные модели 38
1.6. Заключение по главе 44
ГЛАВА 2. Теоретические основы описания процессов функционирования и имитации
2.1. Формализация описания процесса функционирования системы 48
2.1.1. Основные понятия 48
2.1.2. Система, объекты, задание процесса 54
2.1.3. Алгоритмическая модель процесса 57
2.1.4. Понятие структуры 60
2.1.5. Описание подобных процессов 63
2.1.6. Обобщенные операторы, вложенность, блоки 66
2.1.7. Конфликты на ресурсах 71
2.1.8. Схемы описаний функционирования системы 74
2.2. Псевдоязык описания сцепленных процессов 77
2.2.1. Объекты языка, описания 78
2.2.2. Операции над объектами 82
2.2.3. Подпроцессный граф состояний 85
2.2.4. Примеры типовых конструкций 86
2.2.5. Макрорасширения 91
2.3. Теоретические основы построения имитационного процесса 93
2.3.1. Основные положения 93
2.3.2. Классы одновременных событий 98
2.3.3. Моделирующий алгоритм сканирующего типа 103
2.3.4. Моделирующий алгоритм линейного типа 109
2.4. Заключение по главе 112
ГЛАВА 3. Исследование декомпозиционного метода вложенных процессов
3.1. Формирование вложенных процессов 114
3.2. Структура декомпозиционного метода вложенных процессов 121
3.3. Модель исследования ДМВП 127
3.4. Анализ характеристик прямого и обратного интерфейса 131
3.5. Представление вложенного уровня разомкнутыми СМО 134
3.5.1. Выявление значимых факторов 134
3.5.2. Влияние загрузки на погрешность вложенной модели 136
3.5.3. Влияние вида ФРВ времени пребывания во вложенной модели 140
3.6. Представление вложенного уровня замкнутыми СМО 142
3.6.1. Выявление значимых факторов 142
3.6.2. Влияние вида ФРВ времени пребывания в источнике 145
3.7. Заключение по главе 146
ГЛАВА 4. Статистические аспекты имитационного моделирования
4.1. Характер выходных процессов имитации 150
4.1.1. Экспериментальный анализ автоковариационной функции 151
4.1.2. Аналитические модели АКФ 153
4.1.3. Дисперсия среднеинтегральной оценки 155
4.1.4. Тренды переходных режимов имитационных процессов 157
4.2. Классификация процессов по виду тренда 159
4.3. Модель авторегрессии 160
4.4. Анализ гауссовских условно нестационарных процессов 163
4.4.1. Характеристики условно нестационарного процесса 164
4.4.2. Характеристики среднеинтегральной оценки 167
4.5. Исследование начального периода моделирования 171
4.5.1. Характеристики оценки при наличии сброса 172
4.5.2. Вероятность принадлежности интервалу погрешности 176
4.6. Заключение по главе 180
ГЛАВА 5. Управляемый имитационный эксперимент 184
5.1. Формализованное описание управляемой имитационной модели 185
5.1.1. Принципы построения и определения 185
5.1.2. Алгоритм управления 187
5.1.3. Алгоритм построения управляемого имитационного процесса 189
5.2. Анализ алгоритма управления 190
5.2.1. Рекуррентный анализ сходимости 191
5.2.2. Анализ поведения алгоритма при постоянной длине шага 195
5.2.3. Анализ поведения алгоритма при переменной длине шага 197
5.3. Исследование управляемого имитационного процесса 198
5.3.1. Оценка градиента на переходном периоде 199
5.3.2. Эффективность восстановления состояния 202
5.3.3. Выбор длительности интервала управления 204
5.4. Включение имитации во вложенный уровень 208
5.4.1. Построение процедуры стохастической аппроксимации 209
5.4.2. Анализ сходимости процедуры Роббинса-Монро 211
5.5. Заключение по главе 214
ГЛАВА 6 Система имитационного моделирования СТАМ - КЛАСС
6.1. Принципы построения системы моделирования СТАМ-КЛАСС 217
6.1.1 .Отображение процессного описания на агрегативное. 217
6.1.2.Взаимодействие блоков 220
6.1.3. Задание структуры сети 221
6.2. Элементы языка СТАМ-КЛАСС 223
6.3. Описание операторов языка 226
6.3.1. Операторы части ОПИСАНИЕ 227
6.3.2. Операторы части СТРУКТУРА 229
6.3.3. Операторы части УПРАВЛЕНИЕ 229
6.4. Пример программы имитационной модели 232
6.5. Заключение по главе 237
ГЛАВА 7. Практическое использование результатов диссертации
7.1. Экспериментальная проверка гибридного декомпозиционного метода вложенных процессов 239
7.1.1. Структура модели функционирования ИСС 239
7.1.2. Результаты моделирования системы 246
7.2. Моделирование автоматизированной системы управления газопроводом "Уренгой-Ужгород" 249
7.2.1. Состав и архитектура вычислительной сети системы управления газопроводом "Уренгой - Ужгород" 249
7.2.2. Параметрическая имитационная модель. 254
7.2.3. Результаты моделирования вычислительной сети 255
7.3. Оптимизация параметров вычислительного комплекса АСУТП транспортировки газа 261
7.3.1. Структура ВК АСУТП 261
7.3.2. Формализованная модель функционирования АСУТП 262
7.3.3. Результаты моделирования 265
7.3.4. Анализ характеристик процедуры оптимизации 268
7.4. Заключение по главе 270
Заключение по диссертации 274
Литература 277
- Определение класса анализируемых методов
- Система, объекты, задание процесса
- Структура декомпозиционного метода вложенных процессов
- Характеристики среднеинтегральной оценки
Определение класса анализируемых методов
Система обработки информации (СОИ) в составе АСУ относится к классу сложных систем, эффективность функционирования которых в процессе проектирования оценивается методами математического моделирования.
Моделирование СОИ преследует следующие цели [91, 115, 121, 220]: анализ возможностей вычислительных средств (базируется на исследовании выполняемых работ в соответствие с предлагаемой рабочей нагрузкой); обоснование выбора конкретной СОИ (связано с проведением сравнительного анализа одной или нескольких СОИ со специфической рабочей нагрузкой); обеспечение разработок СОИ (определяется целесообразностью использования различных конструктивных решений и возможных модернизаций системы); определение производительности СОИ (для перспективных разработок - определение производительности СОИ при различной конфигурации системы, для существующих СОИ - определение производительности в случае специфических нагрузок, отличных от имеющихся); улучшение характеристик СОИ (расширение вычислительных возможностей систем путем устранения наиболее "узких мест" в аппаратных и программных средствах СОИ). Задачи создания и изучения поведения СОИ требуют разработки и использования таких методов проектирования и исследования, которые позволяли бы наиболее полно учитывать основные особенности, характеризующие систему обработки информации, как большую и сложную [5,28,30,204]: наличие взаимосвязей между большим числом факторов, определяющих свойства и поведение рассматриваемой системы; неопределенность поведения системы в целом и ее составных частей. Методы анализа процессов функционирования СОИ охватывают широкий спектр традиционных и глубоко проработанных математических моделей обработки данных таких, как системы и сети массового обслуживания, системы автоматического управления, модели цифровой обработки сигналов, теория графов, теория автоматов и т.д. Каждая из этих моделей охватывает процессы, происходящие в СОИ с учетом весьма жестких ограничений и позволяет исследовать эти процессы в категориях строго определенных математических предположений [89, 90, 208, 209]. Задачей диссертации является разработка методов моделирования процессов обработки информации в АСУ с целью получения временных характеристик: загруженности, производительности, пропускной способности, времен ожидания, пребывания и обработки, необходимых и достаточных объемов буферов, количества обрабатывающих средств, конфигурации и характеристик телекоммуникационных ресурсов и т.д. При анализе указанных характеристик в классе аналитических моделей сети и системы массового обслуживания (СеМО и СМО) получили наибольшее распространение в силу следующих причин: широкое использование принципов модульности и системного подхода при проектировании СОИ позволяет рассматривать ее как совокупность отдельных аппаратных и программных модулей и дает возможность каждому процессу обработки информации поставить в соответствие процедуру занятия совокупности необходимых для его выполнения ресурсов системы; функционирование СОИ характеризуется стохастической природой информационных потоков и процессов обслуживания; представление процесса обработки информации в СОИ может быть представлено в виде последовательности шагов обслуживания заявок ресурсами системы. Используя терминологию теории массового обслуживания (ТМО), модель анализа СОИ в общем случае можно представить в виде замкнутой или разомкнутой сети массового обслуживания с произвольными законами поступления и обслуживания заявок в узлах сети, наличием логических условий (блокировок) с различными дисциплинами обслуживания. Такая модель анализа производительности задается кортежем: где:О - множество узлов сети; /={1,00} - емкости источников заявок; Р ={Р1} - множество стохастических матриц перехода заявок в сети; - множество типов заявок; множества допустимых типов СМО в узлах сети; J:QxL— B, В = {ЬІ(Г), СТІ2(/)} - множество, определяющее для заявок типа / характеристики обслуживания в узлах сети, где - среднее значение и дисперсия времени обслуживания заявки /-го типа в і-м узле; определяет наличие или отсутствие в сети логических условий - блокировок: 0 - отсутствие блокировки; 1 - блокировка, вызванная наличием буфера ограниченного размера; 2 - блокировка, вызванная одновременным занятием заявкой нескольких ресурсов сети; 3 - блокировка, вызванная ограничением количества заявок в некотором фрагменте сети; ...- другие виды блокировок. Методы анализа такой модели в рамках ТМО подразделяются на точные, приближенные, имитационные, гибридные. Применение того или другого метода определяется выбором случайных процессов, используемых для описания и анализа системы, ее структурой и типом, предположением о независимости или зависимости случайных величин, видом функций распределений.
Система, объекты, задание процесса
На рис.2.12. приведен пример построения блока. На рис.2.12 а. показана операторно-параметрическая схема трека элементарных операторов. На этой схеме выполнено разбиение на два блока В\ и Bi. Как видно из рис.2.12 в., к блоку В\ отнесены операторы h\ и hi, а также параметры Ъ, с, г. К блоку Вг относятся операторы /г3, Ы и параметры d, h, /(рис. 2.12 г.). Параметры а и g не принадлежат ни одному из блоков. Любой параметр по отношению к заданному блоку может быть внутренним, если включен в состав блока, либо внешним, если не принадлежит блоку. Так , параметр а - внешний по отношению к блоку В і. Внутренние параметры, в свою очередь, могут быть входными (параметр d блока Вг), рабочими (параметры h, / блока Вг и параметр b блока В\) и выходными (параметр є блокаді). В результате разбиения операторно-параметрической схемы и последующей операции свертки в блоки получим блочную схему (рис.2.12 б). Выполним классификацию блоков, опираясь на способы генерации процессов, рассмотренные ранее. Агрегат. Блок, в котором развивается один единственный процесс, называется агрегатом или І-блоком. Это означает, что агрегат содержит единственный инициатор, и трек элементарных операторов замкнут внутри блока. Будем обозначать агрегат на схемах в виде (рис.2.13 а). Поскольку инициатор не покидает пределы блока, то его локальная среда (если она существует) недоступна другим блокам и обмен между агрегатом и другими блоками возможен исключительно посредством параметров. По определению в агрегат невозможно поступление других инициаторов. По этой же причине в агрегате нет необходимости использовать объединенные элементарные операторы и организовывать локальную среду процесса. Агрегат, по сути, представляет собой машину по переработке значений параметров в соответствии с собственным алгоритмом функционирования, заданным внутренним процессом. Процессор. Блок, предназначенный для генерации подобных процессов, инициаторы которых являются внешними по отношению к блоку, называется процессором или 77-блоком. Из определения следует, что внутренних локальных процессов блок не имеет, инициаторы извне сцепляются с блоком, порождая подпроцессы, и затем покидают его. Поскольку процессор генерирует подобные процессы, то в нем используются исключительно объединенные элементарные операторы, а инициаторы должны содержать локальные среды. Таким образом, процессор порождает параллельно протекающие во времени подобные процессы. Будем обозначать процессор на схемах в виде (рис.2.13 б). Контроллер. Рассмотрим вновь блок типа агрегат. Как было показано выше, он не имеет возможности взаимодействовать с внешними инициаторами. Чтобы снять это ограничение, введем над инициаторами операции пассивизации и активизации. Операция пассивизации переводит инициатор в класс обычных параметров. Операция активизации, наоборот, обычный параметр переводит в класс инициаторов. Если агрегат содержит операторы, выполняющие указанные операции, то такой агрегат назовем контроллером, или /Г-блоком. Контроллер, таким образом, представляет собой агрегат, выполняющий операции над внешними инициаторами в соответствии с собственным алгоритмом функционирования. Операции над инициаторами суть операции над процессами. Таким образом, контроллер исполняет роль управляющего звена в некоторой блочной схеме. Будем обозначать контроллер на схемах как (рис.2.13.в). Процессы Z[ в системе О развиваются параллельно. Это значит, что они изменяют значения параметров системы в течение одного и того же интервала времени. Достаточно типичны ситуации, когда по логике функционирования системы накладываются ограничения на изменение некоторых параметров несколькими процессами одновременно в течение заданного либо обусловленного интервала времени. Совокупность параметров системы, на изменение которых сформулированы некоторые ограничивающие условия, называется ресурсом R. Таким образом, RcO. Если объект Ok изменяет параметры ресурса R, то RcDk. Захват ресурса R процессом Z означает получение разрешения процессу Z изменять значения параметров q eR. Конфликт на ресурсе - возникновение ситуации, когда тому или иному процессу отказано в захвате ресурса до момента выполнения некоторого наперед заданного условия. Из определения ресурса следует, что конфликт на ресурсе возможен лишь для пересекающихся объектов. Таким образом, необходимо добиться согласования процессов в этих объектах. Для этого должны быть выполнены условия теоремы 2 о признаке согласованности процессов. Рассмотрим следующие способы разрешения конфликтных ситуаций.
Структура декомпозиционного метода вложенных процессов
А. В соответствии с выводом главы 1 в качестве наиболее перспективного метода получения оценок производительности систем обработки информации в АСУ выбран декомпозиционный метод вложенных процессов (ДМВП). Показано, что этот метод позволяет использовать на вложенных уровнях имитационные модели наряду с аналитическими. Это дает возможность моделировать практически любые конфигурации вычислительных сетей в составе систем обработки информации с высокой вычислительной эффективностью.
Включение имитационных моделей в ДМВП потребовало уточнения исходных постановок метода, определения области применимости аналитических и имитационных моделей, анализа точностных характеристик, разработки новых процедур использования имитационных моделей.
В рамках общей схемы применения ДМВП определены основные источники погрешности, включающие ошибки: методические, возникающие в результате использования той или иной методической схемы; корреляционные, возникающие из-за неучета коррелированности потоков при передаче параметров с верхних уровней на нижние и наоборот; аппроксимационные, связанные с аппроксимацией функций распределения интерфейсных переменных в процессе расчета. Для анализа указанных погрешностей ДМВП выбран типовой фрагмент структуры информационных систем, обладающий рядом настраиваемых параметров таких, как количество фаз обслуживания на верхнем уровне, характеристики входных информационных потоков, тип модели нижнего уровня, количественные характеристики обслуживания и др. Созданы имитационные модели, описывающие функционирование указанного структурного фрагмента в полном и декомпозированном вариантах.
В. Проведена серия имитационных экспериментов с целью определения влияния вида функции распределения входного потока на среднее время пребывания заявки в контуре нижнего уровня. Показано, что для широкого спектра изменения управляемых параметров старшие моменты распределения входного потока заявок в нижний контур мало влияют на среднее время пребывания заявки в нем. Таким образом, входной поток в блокированный контур может быть аппроксимирован пуассоновским. В то же время коэффициент вариации времен пребывания в нижнем уровне при различных значениях управляемых параметров колеблется в широких пределах.
Г. Рассмотрена схема декомпозиции, при которой нижний уровень описан разомкнутыми моделями. В этом случае общая погрешность времен пребывания в системе определяется погрешностями коррелированности потоков, времен пребывания в нижнем контуре и погрешностью отсутствия блокировки в нижнем уровне, поскольку поток от составных ресурсов не ограничен единичностью источников поступления. Результаты моделирования показали, что при увеличении коэффициента загрузки хотя бы в одном приборе нижнего контура до 0.8 и выше погрешность превышает 100%. То же происходит и при достижении средних загрузок значения 0.5. При рср выше 0.8 погрешность превышает 300%. Таким образом, следует применять разомкнутую схему нижнего уровня при небольших ( 0.5) значениях средних и максимальных загрузках приборов нижнего контура.
Д. Рассмотрена схема декомпозиции, при которой нижний уровень описан замкнутыми моделями. В этом случае общая погрешность времени пребывания в системе определяется лишь погрешностями корреляций. Погрешность блокировки отсутствует, поскольку замкнутая схема нижнего уровня обеспечивает единичность каждого источника. Показано, что погрешность не превышает 15% и не зависит от коэффициента загрузки. Таким образом, схема с замкнутыми моделями нижнего уровня предпочтительна при всех значениях загрузки приборов нижнего уровня.
Е. Проведены эксперименты определения погрешности пребывания в системе при аппроксимации функции распределения времени пребывания в контуре нижнего уровня экспоненциальным и детерминированным законами в случае декомпозиции нижнего уровня на разомкнутые сети. Показано, что при малых значениях загрузок допустима указанная аппроксимация, при больших загрузках функция распределения существенно отличается от экспоненциальной, и значения погрешностей резко возрастают.
Ж. Проведены эксперименты определения погрешности пребывания в системе при аппроксимации функции распределения времени пребывания в источнике экспоненциальным и детерминированным законами в случае декомпозиции нижнего уровня на замкнутые сети. Показано, что возможна аппроксимация экспоненциальным распределением в широком диапазоне значений загрузок.
Характеристики среднеинтегральной оценки
Анализ предложенной функции показал, что, варьируя параметры с і и сг, можно описать особенности поведения экспериментально полученных автокорреляционных функций. Так, минимум из параметров С\ и с2, определяет длину интервала, на котором корреляция существенна, а сі-с2 определяет степень «затянутости» автокорреляционной функции в начале координат. Таким образом, можно произвести классификацию автокорреляционной функции на сильнокоррелированные, слабокоррелированные, с запаздыванием, без запаздывания. В. Для предложенной автокорреляционной функции стационарного выходного процесса получено аналитическое выражение дисперсии среднеинтегральной оценки. Показано, что на дисперсию оказывают существенное влияние параметры автокорреляционной функции, а также степень ее «затянутости». Г. Для целей дальнейших статистических исследований предлагается использовать в качестве моделей выходных имитационных процессов последовательности, генерируемые моделями авторегрессии 2-го порядка: Статистический анализ показал, что процессы авторегрессии хорошо моделируют характер тренда и автокорреляционной функции, позволяют генерировать все вышеуказанные типов трендов, имеют нестационарный начальный этап, регулируемый заданием начальных значений в моменты времени. В результате предложена статистическая модель выходного имитационного процесса, которая: обладает высокой вычислительной эффективностью; позволяет задавать различные автокорреляционные зависимости в заданном классе; дает возможность имитировать нестационарность на начальном этапе; строить все типы трендов, указанные в классификации. Д. Для целей аналитического исследования начального этапа моделирования в главе исследуется условно нестационарный гауссовский процесс, рассматриваемый как стационарный гауссовский процесс с заданной предысторией в моменты времени, меньшие нуля, и автокорреляционной функцией, определенной в этой главе.
Получены выражения для дисперсии и тренда условно нестационарного процесса в зависимости от параметров автокоррелляционной функции, начальных условий. Показано, что возможно описание в этом классе различного вида монотонных трендов, а, при сильной автокорреляции и далеких начальных условиях, возможно описание и немонотонного тренда. Показано, что характер дисперсии соответствует экспериментальным результатам, полученным ранее, и не зависит от начальных значений.
Е. Получены аналитические выражения тренда и дисперсии среднеинтегральной оценки. Проведено исследование зависимости среднеинтегральной оценки от различных факторов. Показано, что тренд среднеинтегральной оценки имеет затянутый характер, содержит существенную систематическую погрешность на начальном этапе, зависит от коррелированности процесса, начальных значений, длительности моделирования. Показано, что дисперсия среднеинтегральной оценки имеет унимодальный характер с максимумом на начальном этапе моделирования и не зависит от начальных значений процесса.
Ж. Проведен анализ математического ожидания среднеинтегральной оценки условно нестационарного процесса при условии сброса статистики, накопленной на начальном интервале моделирования, равном А. Получены аналитические выражения математического ожидания и дисперсии среднеинтегральной оценки в зависимости от величины Д. В результате дальнейших исследований показано, что увеличение А уменьшает систематическую погрешность, но увеличивает дисперсию оценки. В силу этого в главе предложено выполнить свертку обоих показателей посредством определения вероятности того, что значение оценки в результате моделирования и сброса начальной статистики будет лежать в 5 -окрестности стационарного значения. Проведена серия экспериментов с целью выявления факторов, влияющих на этот показатель. Показано, что определяющим фактором является степень коррелированности процесса: при сильной коррелированности сброс необходим, однако при широком доверительном интервале и слабой коррелированности нет необходимости производить сброс статистики. При малых значениях корреляции оптимум интервала сброса начальной статистики лежит в окрестности нуля.
Таким образом, выполненное в главе исследование позволяет оценить влияние автокорреляционных свойств выходных процессов, начальных значений, длительности моделирования, длительности интервала сброса начальной статистики на точность результатов, получаемых в процессе моделирования, и разработать практические рекомендации по обработке выходного имитационного процесса с целью повышения точности и сокращения сроков моделирования
Статистические и аналитические модели выходных имитационных процессов, предложенные в главе, позволяют существенно расширить сферу исследований различных процедур организации имитационного моделирования, построения управляющих и оптимизирующих алгоритмов.
