Модельным временем в имитационной модели называется воспроизведение физического времени в модели. Соотношение физического и модельного времени определяется спецификой модели и задается диапазоном физического времени, принимаемого за единицу модельного времени. Сущностью имитационного моделирования является продвижение модельного времени и выполнение событий, связанных с определенными значениями модельного времени. Событие в модели это программный модельный образ значимого, с точки зрения разработчика модели, изменения в моделируемой системе.
Основной задачей имитационного моделирования является правильное отображение порядка и временных отношений между изменениями в моделируемой системе на порядок выполнения событий в модели.
Сжатие временной шкалы в непрерывном времени невозможно, поэтому в имитационном моделировании время изменяется скачкообразно. На оси модельного времени моменты наступления событий составляют дискретное множество. В дискретном имитационном моделировании используются два способа управления продвижением модельного времени:
- событийный (Event Driven), при котором в качестве следующего значения модельного времени выбирается минимальное время наступления события из списка будущих событий;
- пошаговый (Time Stepped), при котором значение модельного времени увеличивается на постоянную фиксированную величину – шаг модельного времени.
ПРИМЕРЫ соотношения физического и модельного времени при пошаговом и событийном управлении.
Пошаговый подход удобен при наличии условных событий, т. е. событий, для выполнения которых требуется истинность некоторого логического условия. В этом случае на каждом шаге требуется вычислять логические условия и выполнять соответствующие события. При событийном способе управления временем можно «проскочить» момент времени, при котором условие стало истинным.
Однако пошаговое управление значительно менее эффективно – для обеспечения удовлетворительной точности шаг приращения времени должен быть минимальным, а в этом случае »95% обращений к элементам имитационной модели – лишние и много процессорного времени тратится на обработку «пустых» интервалов. При этом пошаговое управление не позволяет указать истинное положение событий внутри шага модельного времени (такта). Поэтому принимается соглашение переносить их на начало (или на конец) того такта, в пределах которого они в действительности произошли. При этом искажается реальная картина событий, теряются причинно-следственные связи, последовательно протекающие события становятся параллельными, задержки распространения сигналов в структурных элементах не отображаются. Этих недостатков лишено событийное управление модельным временем [2, 29].
3.4.3. Алгоритмы имитационного моделирования для событийного управления модельным временем
Отличие имитационного моделирования от объектно-ориентированного программирования заключается в том, что объект имитационной модели может не только выполнить некоторое событие в момент своей активности, но и запланировать выполнение своего события или события другого объекта в будущем, т. е. на момент модельного времени, больший или равный текущему значению модельного времени. Для реализации выполнения будущих событий и упорядочивания их в хронологическом порядке необходимо использование управляющей программы – планировщика. Алгоритм работы планировщика состоит в выполнении следующих действий:
1) активизация объектов для выполнения событий, запланированных на текущее значение модельного времени и удаление выполненных событий из списка;
2) включение в список новых событий, запланированных активными объектами, вместе со значениями моментов модельного времени, в которые каждое из этих событий должно быть выполнено;
3) увеличение значения модельного времени, если на текущий момент времени невыполненных событий не осталось, и переход на п.1).
Понятно, что при такой организации моделирования события в модели выполняются последовательно, даже если они относятся к одному моменту модельного времени. Однако, поскольку продвижение модельного времени на время моделирования параллельных событий приостанавливается, говорят, что процессы выполняются квазипараллельно.
В алгоритме имитационного моделирования СМО при событийном управлении модельным временем используется несколько информационных массивов: списки текущих (СТС) и будущих (СБС) событий, массив заявок (МЗ) – хранит имя, тип, приоритет, время, местонахождение заявки в системе, и очередей (МО) – хранит информацию о заявках в очереди, упорядочен по ОА. Моделирование начинается с просмотра операторов генерирования заявок, т. е. с обращений к моделям источников заявок. Для каждого независимого источника такое обращение позволяет рассчитать момент генерации первой заявки. Этот момент вместе с ссылкой на заявку заносится в СБС, а сведения о заявке – в МЗ (имя, значения параметров, место появления или нахождения заявки в системе). В СБС события упорядочиваются по возрастанию времен совершения. Далее из СБС выбирается совокупность событий, относящихся к наиболее раннему моменту модельного времени. Эта совокупность переносится в СТС и начинается моделирование событий, отмеченных в СТС (см. рис. 29).
Выбирается ссылка на событие, по ней в МЗ определяется соответствующая заявка и ее место в системе, моделируется продвижение по системе по маршруту, определяемому программой моделирования, до тех пор, пока заявка не придет на вход некоторого ОА. Тогда обращение к модели ОА позволяет определить длительность задержки на обслуживание и момент наступления события, связанного в выходом заявки из ОА. Корректируется местонахождение заявки в МЗ. Ссылка на новое предвидимое событие заносится в СБС так, чтобы сохранилась упорядоченность списка по моментам наступления событий. Программа моделирования приступает к выбору очередной ссылки на СТС.
После имитации всех событий из СТС в него переносится очередная совокупность событий из СБС, относящихся к ближайшему моменту модельного времени ti+1, текущее модельное время принимает это значение.
Если при моделировании движения заявки она придет на вход занятого ОА (устройства или накопителя), то вместо расчета длительности обслуживания имя заявки заносится в МО. При моделировании события, связанного с освобождением ОА заявкой а, проверяется состояние очереди к освобождающемуся ОА. Если имеется очередь, то в соответствии с дисциплиной обслуживания из очереди выбирается заявка b и входит на обслуживание ОА. Обращение к модели обслуживающего аппарата дает значение освобождения ОА заявкой b и соответствующая ссылка заносится в СБС. Затем программа производит моделирование продвижения заявки a до того момента, когда произойдет ее выход из системы или задержка в очереди к новому ОА [1, 28, 29].
3.4.4. Алгоритмы имитационного моделирования для пошагового управления модельным временем
При пошаговом управлении модельным временем трудоемкость анализа имитационной модели определяется количеством уравнений в итоговой системе и количеством тактов, на которое разделен моделируемый интервал времени. Для моделирования в этом случае используются итерационные алгоритмы функционального моделирования дискретных систем.
Для решения систем уравнений вида V=y(V,X), где V – вектор базисных переменных; X – вектор входных переменных модели; y – оператор преобразования дискретных переменных, применяются итерационные алгоритмы. Анализ начинается с задания вектора входных воздействий X и вектора начального приближения V0для искомого вектора V.
ПРИМЕРЫ синхронного анализа логической схемы с использованием итерационных алгоритмов.
Алгоритм простой итерации состоит в выполнении итераций по следующей формуле:
Vi=y (Vi-1, X),
(10)
где Vi - значение вектора V на i-й итерации. Если Vi=Vi-1, то решение найдено; если Vi¹Vi-1, то выполняется новая итерация; если итерационный процесс не сходится, то это свидетельствует об ошибках моделирования или реального объекта, вызывающих неустойчивость состояния. Практически считается, что процесс не сходится, если условие Vi=Vi-1 не достигается на заранее заданном количестве итераций.
Рассмотрим постановку задачи моделирования СМО с ОА типа G/G/1 (см. рис. 30) для пошагового управления модельным временем.
Вектор входных переменных модели для СМО, представленной на рис. 30, имеет вид:
={tвх1, tвх2},
где tвх1и tвх2 – время поступления заявок входных потоков на обслуживание в очередь ОА1 и ОА2 соответственно. Вектор базисных координат может быть определен как:
={t2, t3, tвых, L1, L2, L3},
где t2 – время поступления заявки из рецикла на повторное обслуживание в очередь ОА2; t3 – время поступления заявки на обслуживание в очередь ОА3; tвых – время выхода заявки из системы; L1, L2, L3– длины очередей соответствующих ОА.
Пусть на k-тый момент модельного времени значение вектора базисных координат известно и может быть использовано в качестве начального приближения для расчетов в следующем такте модельного времени:
Пусть в k+1 момент модельного времени значение вектора входных переменных составило:
Требуется определить значение вектора базисных координат в k+1 такте модельного времени. В отсутствии обратных связей (рециклов) в схеме СМО такой расчет потребовал бы однократного пересчета всех базисных координат с учетом нового значения вектора входных переменных, т. е. с учетом значений времен поступления очередных заявок входного потока, округленных до целого числа тактов модельного времени, и времен обслуживания в ОА СМО. При наличии обратных связей, как в заданной СМО, вычисление окончательного значения вектора базисных координат потребует нескольких итераций, так как переменные t2 и tвых взаимосвязаны. Система уравнений модели заданной СМО имеет вид:
где yi – функции, зависящие от закона распределения времени обслуживания в АО и дисциплины очереди.
Согласно формуле (10) в правые части уравнений модели на каждой итерации в этом алгоритме подставляются значения базисных координат, полученных на предыдущей итерации. На первой итерации такими значениями являются значения базисных координат из начального приближения вектора, следовательно:
и так далее. Следует обратить внимание, что, например, для расчета базисной координаты в правую часть соответствующего уравнения подставляется значение несмотря на то, что к моменту расчета уже известно и значение . Такая организация расчетов потребует, очевидно, большего количества итераций, но, при этом, в алгоритме нет необходимости выполнять проверку: определено ли значение очередной базисной координаты уже на этой итерации, или еще нет.
Признаком того, что решение найдено, в этом итерационном метода, как и во всех прочих, является совпадение результата последней итерации с предыдущей.
Уменьшить количество вычислений удается при построении итерационного процесса с использованием алгоритма Зейделя, в котором при вычислении очередного из элементов вектора Vi в правую часть уравнений системы там, где это возможно, подставляются не элементы вектора Vi-1, а те элементы вектора Vi, которые уже вычислены к данному моменту, т. е. итерации выполняются по формуле:
Vi=y (Vi,Vi-1, X).
Количество итераций в алгоритме Зейделя существенно зависит от порядка, в котором реализуются уравнения модели. В алгоритме Зейделя без ранжирования уравнения модели перечисляются в произвольном порядке. В алгоритме Зейделя с ранжированием уравнения располагаются в том порядке, в каком соответствующие уравнениям элементы схемы образуют путь прохождения заявок. Тогда для анализа схем без обратных связей потребуется всего одна итерация. В схемах с обратной связью метод Зейделя с ранжированием уравнений порождает несколько итераций, но их количество существенно меньше, чем в методе простой итерации.
Ранжирование уравнений производится следующим образом: уравнение модели (элемент СМО) получает ранг j, если все аргументы этого уравнения (входы элемента) ранжированы и максимальный среди рангов аргументов (входов) равен j-1. Переменная модели получает ранг j, если она является левой частью уравнения (является выходом элемента), имеющего ранг j. Выполнение алгоритма начинается с того, что всем входным переменным присваивается ранг j=0. Если в схеме имеются контуры ОС, одна из цепей каждого контура должна быть предварительно разорвана и части разорванных цепей, подключенные к входам элементов, получают ранг j=0. Затем определяют уравнения первого ранга, переменные первого ранга, элементы второго ранга и т. д. В итоге уравнения располагаются в порядке возрастания рангов.
Выполним ранжирование уравнений системы, описывающей СМО, приведенную на рис. 30 и рассмотренную выше, в примере моделирования по методу простой итерации. Присвоим нулевой ранг входным переменным:
Как видно, в четвертом уравнении теперь фигурирует единственная непроранжированная переменная: L1, которая фигурирует и в правой, и в левой части. Ей присваивается ранг, на 1 больший минимального в уравнении, т. е. в данном случае равный 1. Этим же рангом помечаются все вхождения переменной L1 в другие уравнения:
Как видно, после выполнения последнего шага дальнейшее ранжирование становиться невозможным без условного разрыва обратной связи. Условный разрыв позволяет отнести переменную tвых к нулевому рангу. В результате в первом уравнении все переменные в правой части оказываются проранжированными, поэтому t2в этом уравнении, а также в правых частях второго и пятого уравнений, получает ранг 1:
В пятом уравнении теперь фигурирует единственная непроранжированная переменная: L2, которая фигурирует и в правой, и в левой части. Ей присваивается ранг, на 1 больший минимального в уравнении, т. е. в данном случае равный 2. Этим же рангом помечаются все вхождения переменной L2 в другие уравнения, что позволяет определить ранг переменной t3 равным 3. С учетом вхождений этой переменной получим:
В шестом уравнении теперь фигурирует единственная непроранжированная переменная: L3, которая фигурирует и в правой, и в левой части. Ей присваивается ранг, на 1 больший минимального в уравнении, т. е. в данном случае равный 4. Этим же рангом помечаются вхождение переменной L3 в третье уравнение, что позволяет определить действительный (без условного разрыва обратной связи) ранг переменной tвых равным 5. Окончательный результат ранжирования имеет вид:
Расположим уравнения по возрастанию рангов:
Если сопоставить ранжированный порядок уравнений со схемой на рис. 30, легко убедиться, что порядок вычислений в этом случае соответствует логике прохождения заявок по СМО и порядку изменения переменных модели. Понятно, что для такой простой схемы расположить уравнения в правильном порядке можно и без процедуры ранжирования. Однако в сложных схемах с большим количеством ОА и обратных связей эта задача не тривиальна, и приходиться прибегать к ранжированию.
Наименьший объем вычислений обеспечивает событийный алгоритм. Основная идея событийного метода заключается в выполнении вычислений по уравнениям только активизированных элементов, т. е. элементов, у которых хотя бы на одном входе произошло событие (изменилась входная переменная). В алгоритме событийного метода на каждой итерации имеется своя группа активизированных элементов. Использование метода позволяет существенно сократить затраты машинного времени при анализе имитационных моделей СМО [3, 10, 29].
={tвх1, tвх2},
={t2, t3, tвых, L1, L2, L3},
в правую часть соответствующего уравнения подставляется значение 
несмотря на то, что к моменту расчета 
. Такая организация расчетов потребует, очевидно, большего количества итераций, но, при этом, в алгоритме нет необходимости выполнять проверку: определено ли значение очередной базисной координаты уже на этой итерации, или еще нет.
