Норенков И.П. Основы автоматизированного проектирования

Подождите немного. Документ загружается.

3.5.

Математическое

обеспечение

анализа

на

функционально-логическом

уровне

Таблица

3.7

Значение

Исходное

Промежуточное

Итоговое

<8>

Для

простейшей схемы (рис. 3.15,

а)

результаты трехзначного моделирова-

ния

представлены

табл.

3.7.

Динамический риск сбоя иллюстрируют

схема

временные диаграммы

(рис.

3.16).

Сбой выражается

появлении вместо одного перепада

на

выходе,

что

имеет место

при

правильном функционировании, нескольких перепадов.

Об-

наружение

динамических

рисков

сбоя также выполняют

помощью двукратно-

го

решения уравнений модели,

но при

использовании пятизначного алфавита

множеством значений

{0,

<8>,

а,

Р),

где а

интерпретируется

как

положитель-

ный

перепад,

Р — как

отрицательный перепад, остальные символы имеют преж-

ний

смысл.

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

исходном,

промежуточном

итоговом состояниях

могут

быть такими:

0-0-0,

1-1-1,

0-a-l,

1-P-0.

Последовательности

0-<&-1

или

1-<8М)

указывают

на

динамичес-

кий

риск сбоя.

Трехзначный алфавит можно использовать

и в

асинхронных моделях. Пусть

модели

у (t +

)

=/(X(/))

момент времени

Г,

входы

Х(^)

таковы,

что в мо-

мент времени

происходит переключение выходного сигнала

д>.

Но

если

учитывать разброс задержек,

то

принимает некоторое случайное значение

диапазоне

^з

Д°

это

достигается

помощью трехзначного асинхронного моделирования

и,

следовательно,

модели

интервале времени

от

сигнал

должен иметь неопределенное значение

®.

Именно

Рис. 3.16.

Динамический

риск

сбоя:

а —

схема;

б—временные

диаграммы

123

Математическое

обеспечение

анализа проектных

решений

Методы

логического

моделирования

отношении асинхронных

моделей

возможны

два

метода

моделирова-

ния

—

пошаговый

(инкрементный)

событийный.

пошаговом

методе

время

дискретизируется

вычисления

по

выражени-

ям

модели

выполняются

дискретные моменты времени

,...

и т. д. Шаг

дискретизации

ограничен сверху значением допустимой погрешности определе-

ния

задержек

потому оказывается довольно малым,

время анализа

—

значи-

тельным.

Для

сокращения времени анализа используют

событийный

метод.

этом

методе событием называют изменение любой переменной модели. Событий-

ное

моделирование основано

на

следующем правиле: обращение

модели

ло-

гического

элемента происходит только

в том

случае, если

на

входах этого эле-

мента

произошло событие.

сложных логических

схемах

на

каждом такте

синхронизации обычно происходит переключение всего лишь

2...

3 %

логичес-

ких

элементов,

соответственно

событийном методе

несколько

раз

умень-

шаются

вычислительные

затраты

по

сравнению

пошаговым

моделировани-

ем.

Методы анализа синхронных моделей представляют собой методы реше-

ния

систем логических уравнений.

этим методам относятся

метод

простых

итераций

метод

Зейделя,

которые аналогичны одноименным методам

решения

систем алгебраических уравнений

непрерывной математике.

Применение этих методов

моделированию логических схем удобно про-

иллюстрировать

на

npmfepe

схемы триггера (см. рис.

3.14).

табл.

3.8

пред-

ставлены

значения

переменных

модели

исходном состоянии

после каждой

итерации

соответствии

методом простых итераций.

исходном состоянии

задают начальные (можно произвольные) значения промежуточных

выход-

ных

переменных,

данном примере

это

значения

переменных

В,

Q,P,A,

соот-

ветствующие предыдущему состоянию триггера. Новое состояние триггера

должно

соответствовать указанным

таблице изменившимся значениям вход-

ных

сигналов

S и С.

Вычисления заканчиваются, если

на

очередной итера-

ции

изменений переменных нет,

что и

наблюдается

данном примере

на

чет-

вертой итерации.

Согласно

методу простых итераций,

правые части уравнений модели

на

каждой

итерации подставляют значения переменных, полученные

на

предыду-

щей

итерации.

отличие

от

этого

методе Зейделя, если

некоторой пере-

менной

обновлено значение

на

текущей итерации, именно

его и

используют

дальнейших вычислениях

уже на

текущей итерации.

Метод

Зейделя позволяет

сократить число итераций,

но для

этого нужно предварительно упорядочить

уравнения

модели так, чтобы последовательность вычислений соответствова-

ла

последовательности прохождения сигналов

по

схеме.

Такое упорядочение

выполняют

помощью ранжирования.

124

3.6.

Математическое обеспечение анализа

на

системном уровне

Таблица

3.8

Итерация

Предыдущее состояние

Исходные

значения (итерация

Итерация

Ранжирование заключается

присвоении элементам

переменным моде-

ли

значений рангов

соответствии

со

следующими правилами:

1) в

схеме раз-

рываются

все

контуры обратной связи,

что

приводит

появлению дополни-

тельных входов схемы (псевдовходов);

2) все

внешние переменные

(в том

числе

на

псевдовходах) получают ранг

0; 3)

элемент

и его

выходные переменные

получают ранг

если

элемента

все

входы

проранжированы

старший среди

рангов

входов равен

k -

Так,

если

схеме

(см. рис.

3.14)

разорвать

имеющийся контур обратной связи

цепи

переменной

обозначить переменную

на

псевдовходе

Q,,

то

ранги переменных ока-

зываются

следующими:

S, С,

имеют

ранг

0,АиВ-

ранг

\,Р-

ранг

2 и

£>

ранг

соответствии

этим переупорядочивают уравнения

модели триггера:

= not (S and

С);В

= not (R and

С);

Р=not

and

Q);Q=not

(В and

P).

Теперь

уже на

первой итерации

(по

Зейделю) получаем требуемый результат.

Если

разорвать контур обратной связи

цепи переменной

Р, то

решение

данном

примере

будет получено после второй итерации,

но это все

равно заметно

быстрее,

чем при

использовании

метода

простой итерации.

Для

сокращения объема вычислений

синхронном моделировании возмож-

но

использование событийного подхода. По-прежнему обращение

модели эле-

мента

происходит, только если

на его

входах произошло событие.

Для

триггера (см. рис.

3.14)

применение событийности

рамках метода простых

итераций приводит

сокращению объема вычислений: вместо

16-кратных

обращений

моделям элементов,

как это

следует

из

табл.

3.8, происходит лишь пятикратное обра-

щение.

табл.

3.8

звездочками

помечены

значения

переменных,

вычисляемые

собы-

тийном методе. Так, например,

на

итерации

имеют

место

изменения переменных

С,

поэтому

на

следующей итерации обращения происходят только

моделям элемен-

тов

выходами

иВ.

3.6. Математическое обеспечение анализа

на

системном уровне

Основные

сведения

из

теории массового обслуживания

Объектами

проектирования

на

системном уровне являются такие слож-

ные

системы,

как

производственные предприятия, транспортные системы,

вы-

числительные

системы

сети, автоматизированные системы проектирования

управления

и т. п. В

этих приложениях анализ процессов функционирования

систем

связан

исследованием прохождения через систему потока заявок

(ина-

125

Математическое обеспечение анализа проектных

решений

че

называемых требованиями

или

транзактами).

Разработчиков подобных

сложных

систем интересуют прежде всего такие параметры,

как

производитель-

ность (пропускная способность) проектируемой системы, продолжительность

обслуживания

(задержки) заявок

системе, эффективность используемого

системе оборудования.

Заявками

могут быть заказы

на

производство изделий, задачи, решаемые

вычислительной

системе,

клиенты

банках,

грузы,

поступающие

на

транспор-

тировку,

и др.

Очевидно,

что

параметры заявок, поступающих

систему,

яв-

ляются случайными величинами

и при

проектировании могут быть известны

лишь

их

законы распределения

числовые характеристики этих распределе-

ний.

Поэтому анализ

функционирования

на

системном уровне,

как

правило, носит

статистический характер.

качестве математического аппарата моделирова-

ния

удобно принять теорию массового обслуживания,

а в

качестве моделей

систем

на

этом уровне использовать

системы

массового

обслуживания

(СМО).

Типичными выходными параметрами

в СМО

являются числовые характе-

ристики

таких

величин,

как

время обслуживания заявок

системе,

длины оче-

редей заявок

на

входах, время ожидания обслуживания

очередях, загрузка

устройств системы,

также вероятность обслуживания

заданные сроки

и т. п.

простейшем случае

СМО

представляет собой некоторое средство

(устройство),

называемое

обслуживающим

аппаратом (ОА), вместе

оче-

редями заявок

на

входах. Более сложные

СМО

состоят

из

многих взаимосвя-

занных

ОА.

Обслуживающие аппараты

СМО в

совокупности образуют ста-

тические

объекты

СМО, иначе называемые

ресурсами.

Например,

вычислительных сетях ресурсы представлены аппаратными

программными

средствами.

В СМО

кроме статических объектов фигурируют

динамические

объек-

ты —

транзакты.

Например,

вычислительных сетях динамическими объекта-

ми

являются решаемые задачи

запросы

на

информационные услуги.

Состояние

СМО

характеризуется состояниями составляющих

ее

объектов.

Например, состояния

ОА

выражаются булевыми величинами, значения кото-

рых

интерпретируются

как

true (занято)

false (свободно),

длинами очере-

дей на

входах

ОА,

принимающими неотрицательные целочисленные значения.

Переменные, характеризующие состояние СМО, будем называть переменны-

ми

состояния

или

фазовыми переменными.

Правило,

согласно которому заявки выбирают

из

очередей

на

обслужива-

ние,

называют

дисциплиной

обслуживания,

величину, выражающую пре-

имущественное право

на

обслуживание,

—

приоритетом.

бесприоритет-

ных

дисциплинах

все

транзакты

имеют

одинаковые приоритеты. Среди

бесприоритетных дисциплин наиболее популярны дисциплины

FIFO

(первым

пришел

—

первым обслужен), LIFO (последним пришел

—

первым обслужен)

со

случайным выбором

заявок

из

очередей.

126

3.6.

Математическое

обеспечение

анализа

на

системном

уровне

приоритетных дисциплинах

для

заявок каждого приоритета

на

входе

ОА

выделяется своя очередь.

Заявка

из

очереди

низким приоритетом поступает

на

обслуживание, если пусты очереди

более

высокими приоритетами. Разли-

чают приоритеты абсолютные, относительные

динамические. Заявка

из

оче-

реди

более высоким абсолютным приоритетом, поступая

на

вход занятого

ОА,

прерывает

уже

начатое обслуживание заявки более низкого приоритета.

случае относительного приоритета прерывания

не

происходит, более высоко-

приоритетная

заявка ждет окончания

уже

начатого обслуживания. Динамичес-

кие

приоритеты могут изменяться

во

время нахождения заявки

СМО.

Исследование поведения СМО,

т. е.

определение временных зависимостей

переменных, характеризующих состояние СМО,

при

подаче

на

входы

любых

требуемых

соответствии

заданием

на

эксперимент потоков заявок, называют

имитационным

моделированием

СМО. Имитационное моделирование про-

водят

путем воспроизведения событий, происходящих одновременно

или

после-

довательно

модельном времени.

При

этом

под

событием

понимают факт

изменения

значения любой фазовой переменной.

Подход, альтернативный имитационному моделированию, называют ана-

литическим

исследованием СМО. Аналитическое исследование заключается

получении формул

для

расчета

выходных параметров

СМО с

последующей

подстановкой

значений аргументов

в эти

формулы

каждом отдельном экспери-

менте.

Модели СМО, используемые

при

имитационном

аналитическом модели-

ровании,

называются имитационными

аналитическими соответственно.

Аналитические модели удобны

использовании, поскольку

для

аналитичес-

кого

моделирования

не

требуются

сколько-нибудь значительные затраты

вы-

числительных ресурсов, часто

без

постановки специальных вычислительных

экспериментов

разработчик может оценить характер

влияния

аргументов

на

выходные параметры, выявить

те или

иные общие закономерности

поведе-

нии

системы.

Но, к

сожалению, аналитическое исследование удается реализо-

вать

только

для

частных случаев сравнительно несложных СМО.

Для

слож-

ных

СМО

аналитические модели

если

удается получить,

то

только

при

принятии

упрощающих допущений, ставящих

под

сомнение адекватность модели.

Поэтому основным подходом

анализу САПР

на

системном уровне проек-

тирования

считают имитационное моделирование,

аналитическое иссле-

дование

используют

при

предварительной оценке различных предлагаемых

ва-

риантов

систем.

Некоторые компоненты

СМО

характеризуются

более

чем

одним входным

(или) выходным потоками заявок. Правила выбора одного

из

возможных

направлений движения заявок входят

соответствующие модели компонен-

тов.

одних случаях такие правила относятся

исходным данным (например,

выбор

направления

по

вероятности),

но в

некоторых случаях желательно найти

оптимальное

управление потоками

узлах разветвления. Тогда задача моде-

лирования

становится более сложной задачей синтеза, характерными примера-

ми

являются маршрутизация заявок

или

синтез расписаний

планов.

127

Математическое

обеспечение

анализа

проектных

решений

Аналитические

модели

СМО

Как

отмечено выше, аналитические модели

СМО

удается получить

при

довольно

серьезных допущениях.

числу типичных допущений относятся сле-

дующие.

Во-первых,

как

правило, считают,

что

в СМО

используются бесприоритетные

дисциплины

обслуживания типа FIFO.

Во-вторых, времена обслуживания

заявок

устройствах выбираются

соот-

ветствии

экспоненциальным

законом

распределения.

В-третьих,

аналитических моделях

СМО

входные потоки заявок аппрокси-

мируются простейшими потоками,

т. е.

потоками, обладающими свойствами

стационарности, ординарности (невозможности одновременного поступления

двух заявок

на

вход СМО), отсутствия последействия.

большинстве случаев модели

СМО

отображают процессы

конечным

множеством

состояний

и с

отсутствием последействия. Такие процессы назы-

вают

конечными

марковскими

цепями.

Марковские

цепи характеризуются множеством состояний

матрицей

ве-

роятностей переходов

из

одного состояния

другое

начальными условиями

(начальным

состоянием).

Удобно

представлять марковскую цепь

виде графа,

котором вершины соответствуют состояниям цепи,

дуги

—

переходам, веса

дуг —

вероятностям переходов (если время дискретно)

или

интенсивностям

переходов (если время непрерывно).

Отметим,

что

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

=limP

(*,)/*,

при

(

—>

0, где

{

(fj)

вероятность перехода

из

состояния

состояние

за

время

Обычно используют условие

и'

что

эквивалентно

(3.44)

где

N—число

состояний.

На

рис.

3.17

приведен пример марковской цепи

в ви-

де

графа

состояниями

,,...,

а в

табл.

3.9

представлена матрица

интенсив-

ностей переходов

для

этого примера.

Таблица

3.9

Состояние

5з

-Ki2-Ki3-Ki4

V21

-Vi\

K42

5з

-F34

Км

F34

-F42

128

Математическое обеспечение анализа

на

системном уровне

Большинство выходных параметров

СМО

можно

определить, используя информацию

о по-

ведении

СМО,

т. е.

информацию

состояниях

СМО

установившихся (стационарных) режи-

мах

и об их

изменениях

переходных процес-

сах.

Эта

информация имеет вероятностную при-

роду,

что

обусловливает описание поведения

Рис.

3.17.

Пример

СМО

терминах вероятностей нахождения

сие-

марковской

цепи

темы

различных состояниях. Основой такого описания,

следовательно,

многих

аналитических моделей

СМО

являются

уравнения

Колмогорова.

Уравнения

Колмогорова можно получить следующим образом.

Изменение

вероятности

нахождения системы

состоянии

за

время

}

есть

вероятность перехода системы

состояние

из

любых

других

состоя-

ний

за

вычетом вероятности перехода

из

состояния

другие

состояния

за

время

f,,

т. е.

Р(0

Р(ж,)

Р(0

,(gp

(О

ЕР„(ОР,(0,

(3.45)

,/eJ

*еК

где

P(t)

P(f)

вероятности нахождения системы

состояниях

и S

соот-

ветственно

момент времени

t, а

Р,(^,)

РД?,)

—

вероятности изменения

состояний

течение времени

?,;

произведение вида

,(f,)P

есть безусловная

вероятность

перехода

из

равная условной вероятности перехода, умно-

женной

на

вероятность условия;

J и К —

множества индексов инцидентных

вершин

по

отношению

вершине

по

входящим

исходящим дугам

на

графе

состояний

соответственно.

Разделив

выражение

(3.45)

на

перейдя

пределу

при t

—>

О,

получим

откуда

следуют

уравнения Колмогорова

*L(V

Р)-Р

стационарном состоянии

dP/dt

= 0 и

уравнения Колмогорова составляют

систему

алгебраических уравнений,

которой

/-и

узел представлен уравнени-

ем

Z(F

,P)

PZF

(3.46)

Прибавляя

(

левой

правой частям уравнения

.46)

учитывая

.44),

получаем

N N

J '

;=1

t-1

Основы

автоматизированного

проектирования

129

Математическое обеспечение анализа

проектных

решений

т.

е.

где Р —

финальные вероятности.

Пример

аналитической

модели

Примером

СМО,

которой можно применить аналитические методы иссле-

дования, является одноканальная

СМО с

простейшим входным потоком интен-

сивностью

А и

длительностью обслуживания, подчиняющейся экспоненциаль-

ному закону обслуживания интенсивностью

ц. Для

этой

СМО

нужно получить

аналитические зависимости среднего числа

заявок, находящихся

системе,

среднюю длину

очереди

к ОА,

время

пребывания заявки

системе,

время

ожидания

очереди.

На

рис.

3.18

представлен

граф состояний рассматриваемой СМО,

где

—

состояние

заявками

системе. Матрица

интенсивностей

представлена

табл.

ЗЛО.

Уравнения Колмогорова

для

установившегося режима

имеют

вид

Используя

уравнения Колмогорова, можно выразить

все

1,2,3,...,

через

Получим

Р^Щц^аР^

((А

ц)/»,

АР

)/ц

= (1 +

я)Р,

аР

<ЛР

;

(1 +

а)Р

}

с?Р

и т. д.

Здесь введено обозначение

А.

/ц.

Отметим также,

что

установившийся

ре-

жим

возможен только

при а <

Так

как

= 1, то

1/(1

+ а +

+а

+...)

=1-а.

Рис. 3.18. Граф состояний

130

3.6.

Математическое

обеспечение

анализа

на

системном

уровне

Таблица

3.10

Состояние

5г

-К

-Х.-Д

-Х-ц

5з

-Х-

А.

-Х-ц

Теперь нетрудно получить

остальные требуемые результаты:

Р,+

2Р

ЗР

+ ... =

а\\

а);

2Р

...

(k-

\)P

Р^

Времена пребывания

системе

очереди определяются соотношениями:

^Т

av av

2av

которые

называют формулами

Литтла:

Имитационное

моделирование

СМО

Для

представления имитационных моделей можно использовать языки про-

граммирования общего применения, однако такие представления оказываются

довольно

громоздкими. Поэтому обычно используют специальные языки имита-

ционного

моделирования

на

системном уровне. Среди языков имитационного

моделирования

различают языки, ориентированные

на

описание событий,

средств обслуживания

или

маршрутов движения

заявок

(процессов). Выбор

языка

моделирования определяет структуру модели

методику

ее

построения.

Ориентация

на

устройства характерна

для

функционально-логического

и бо-

лее

детальных иерархических уровней описания объектов.

Для

описания имитационных моделей

на

системном уровне (иногда

их на-

зывают

сетевыми

имитационными

моделями

—

СИМ) чаще используют

языки,

ориентированные

на

события

или

процессы. Примерами первых

могут

служить

языки

Симскрипт,

SMPL

и ряд

других.

числу вторых относятся язы-

ки

Симула,

SOL,

также популярный

язык

GPSS.

Языки

имитационного моделирования реализуются

программно-методи-

ческих

комплексах моделирования СМО, имеющих

ту

или

иную степень специа-

лизации.

Так, комплексы

на

базе языка GPSS можно использовать

во

многих

приложениях,

но

есть специализированные комплексы

для

моделирования

вы-

числительных сетей, систем управления предприятиями

и т. п.

131

Математическое

обеспечение

анализа проектных

решений

При

использовании языков, ориентированных

на

процессы,

составе

СИМ

выделяются элементарные части

и ими

могут

быть источники входных пото-

ков

заявок, устройства, накопители

узлы.

Источник входного потока заявок представляет собой алгоритм,

соответ-

ствии

которым вычисляются моменты

появления заявок

на

выходе источ-

ника.

Источники

могут

быть

зависимыми

независимыми.

зависимых

ис-

точниках моменты появления заявок связаны

наступлением определенных

событий, например

приходом другой заявки

на

вход некоторого устройства.

Типичным независимым источником является алгоритм выработки значений

случайной величины

заданным законом распределения.

Устройства

имитационной модели представлены алгоритмами выработки

значений

интервалов (длительностей) обслуживания. Чаще всего

это

алгоритмы

генерации значений случайных величин

заданным законом распределения.

Но

могут

быть устройства

детерминированным временем обслуживания

или

временем, определяемым событиями

других частях СИМ. Модель устройства

отображает также заданную дисциплину обслуживания, поскольку

модель

входит алгоритм, управляющий очередями

на

входах устройства.

Накопители моделируются алгоритмами определения объемов памяти,

занимаемых заявками, приходящими

на

вход накопителя. Обычно объем памя-

ти,

занимаемый заявкой, вычисляется

как

значение случайной величины,

за-

кон

(или) числовые характеристики распределения

могут

зависеть

от

типа

заявки.

Узлы

выполняют связующие, управляющие

вспомогательные функции

имитационной

модели, например,

для

выбора направлений движения заявок

СИМ,

изменения

их

параметров

приоритета, разделения заявок

на

части,

их

объединения

и т. п.

Обычно каждому типу элементарной модели,

за

исключением лишь неко-

торых узлов,

программной системе

соответствует

определенная процедура

(подпрограмма). Тогда

СИМ

можно представить

как

алгоритм, состоящий

из

упорядоченных обращений

этим процедурам, отражающим поведение моде-

лируемой системы.

процессе моделирования происходят изменения модельного времени, кото-

рое

чаще всего принимается дискретным, измеряемым

тактах.

Время изме-

няется

после

того,

как

закончена имитация очередной группы

событий,

относя-

щихся

текущему моменту времени

Имитация сопровождается накоплением

отдельном файле статистики таких данных,

как

количества заявок, вышедших

из

системы обслуженными

необслуженными, суммарное время занятого

состояния

для

каждого

из

устройств, средние длины очередей

и т. п.

Имита-

ция

заканчивается, когда текущее время превысит заданный отрезок времени

или

когда входные источники выработают заданное число заявок. После это-

го

производят обработку накопленных

файле статистики данных,

что

позво-

ляет получить значения требуемых выходных параметров.

132