Подождите немного. Документ загружается.
8.1. ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ
ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЫ
Основные этапы разработки имитационной модели
вычислительной системы рассмотрим на примере:
1. Содержательное описание объекта (описание ВС)
Имеется часть ВС обработки заданий двух типов
четырьмя устройствами
Задания 1-го типа обрабатываются строго
последовательно устройствами УСТ
1
, УСТ
2
, УСТ
3
.
Выбор типа задания при его обработке на устройстве
УСТ
1
случайный.
Запрещена одновременная обработка заданий разных
типов устройствами УСТ
1
и УСТ
2
.
Обработка заданий 1-го и 2-го типов соответственно
устройствами УСТ
3
и УСТ
4
осуществляется только в том
случае, когда эти устройства свободны.
На каждом из устройств
УС Т
j
, j = 1, 4
обработка
заданий производится в порядке поступления заданий.
Показателями качества моделируемой системы будут
выступать:
- интенсивность поступления заданий в ВС на
загрузку устройств;
- пропускная способность ВС;
- среднее время полной обработки одного задания.
УС Т
1
УС Т
2
УС Т
3
УС Т
4
2-го типа
1-го типа
Поток заданий
на обработку
Поток заданий
1 - г о т и п а
после обработки
Поток заданий
2 - г о т и п а
после обработки
3
Управляемая переменная - интенсивность поступления
заданий в ВС на обработку.
Контролируемые характеристики моделирования -
статистики моделирования, позволяющие определить:
загрузку устройств (суммарное время обработки
заданий каждым устройством);
пропускную способность ВС (количество заданий
каждого типа, обрабатываемых ВС);
среднее время полной обработки одного задания
(интервал от момента поступления задания в ВС на
обработку до момента завершения его обработки в
ВС).
Описание режимов функционирования сводится к
следующим действиям:
- определяются выборки значений времен обработки
з а д а н и й ус т р о й с т в а м и
i j
, г д е i - т и п з а д а н и я ,
j - устройство;
- известными статистическими методами по выборкам
i j
формируются соответствующие функции распределения
времени обработки i-го задания j-ым устройством
F
i j
(аналитические или табличные).
Описание внешней среды сводится к указанию механизма
выбора типа заданий i:
- задания 1-го типа поступают на обработку с
вероятностью
p
1
, а задания 2-го типа - с вероятностью
p p
2 1
1
;
- интенсивность поступления заданий извне является
общей для заданий обоих типов;
- поступление заданий в ВС не зависит от ситуации в
ВС и от времени и продолжительности работы ВС.
2. Концептуальная модель
Декомпозиция модели осуществляется просто:
4
отдельными элементами данной системы (ВС) будут
устройства;
параметры системы - интенсивности поступления
заданий 1-го и 2-го типов (
1
и
2
). Для простоты
допустим, что поступления заданий обоих типов
подчиняется пуассоновскому закону;
переменные модели - это функции распределения
длительностей обслуживания i-го задания j-ым
устройством
F
i j
.
В качестве статистик моделирования будут выступать:
коэффициенты загрузки устройств
У
j
j
;
количество обработанных j-тым устройством заданий
j
;
размеры очередей к каждому из устройств
j
;
общее время обработки i-го задания в ВС
T
i
.
Критерии эффективности:
коэффициенты загрузки
j
;
среднее значение времен обработки заданий
T
i
.
В результате имитационного моделирования необходимо
найти следующие функциональные зависимости:
j i
i j
;
T
j i
i j
.
При задании функций распределения
F
i j
длительностей обслуживания задания на j-ом устройстве
достаточна аппроксимация ступенчатыми функциями.
Выдвигается гипотеза, что
i j
и
i j
имеют вид
полиномов, порядок которых и значения коэффициентов
определяются в ходе имитационных экспериментов.
С помощью таких эмпирических зависимостей можно
предсказать характеристики загрузки оборудования (
j
) и
времена обслуживания заданий (
T
i
) в зависимости от
i
при заданных
F
i j
.
Документация концептуальной модели:
схема;
текст содержательного описания;
список параметров и переменных
i i j
, , F
;
5
состав статистики моделирования
j j j i
, , , T
;
соотношения для критериев эффективности
i j
,
i j
;
а п п р о к с и м и р у ю щ и е в ы р а ж е н и я д л я
з а д а в а е м ы х переменных
F
i j
.
Формализация ВС как объекта моделирования
Составляется временнбя диаграмма взаимодействия
устройств.
На диаграмму заносятся моменты начала и конца
обработки i-го задания j-тым
У t
н i j h к i j h
, t
и длительности
обработки заданий i-го типа j-тым
У
i j
; h - порядковый
н о м е р , п р и с в а и в а е м ы й з а д а н и ю л ю б о г о т и п а п р и
поступлении его на обработку к У
1
.
На временнуй оси t
1
зафиксированы периоды обработки
заданий 1-го и 2-го типов первым устройством ( У
1
);
На оси t
2
- период обработки заданий 1-го и 2-го
типов вторым устройством ( У
2
);
На осях t
3
и t
4
- соответственно периоды обработки
заданий 1-го и 2-го типов устройствами У
3
и У
4
;
На оси t
0
- моменты q, соответствующие началу и концу
обработки любого задания любым устройством.
На временной диаграмме также указаны моменты
изменения значения признака
j
, где
j
- признаки
нахождения j-го устройства в состоянии обработки i-
го задания (
j
= 1 - У
j
занято,
j
= 0 - У
j
простаивает).
На диаграмме интервалы обработки заданий 1-го типа
заштрихованы линиями “накрест”, а интервалы обработки
устройствами заданий 2-го типа - параллельными косыми
линиями.
Входная информация: функции распределения
длительностей обслуживания заданий i-го типа j-м
6
устройством
F
i j
и вероятность p
1
поступления на первое
устройство заданий первого типа. Эта вероятность
вычисляется по интенсивностям поступлений заданий i-го
типа (
i
) следующим образом:
p
1
1
1 2
Критерии эффективности системы
j
и
T
i
вычисляются
по формулам:
j
к ijh н ijh
и
hi
t t
T
i j
11
2
,
где
j
- коэффициент загрузки У
j
;
i j
- количество обработанных заданий i-го типа j-м
устройством (в расчет берутся лишь задания, прошедшие
обработку на j-ом устройстве);
T
и
- календарный период исследования ВС.
T t t t t
к h н h
h
к h н h
h
1
13
13 11
1
2
24
24 21
1
1 1
13 24
; T
,
где
13
и
24
- число заданий, обработанных
соответственно третьим и четвертым устройствами (в
расчет берутся только задания, обработанные,
соответственно, третьим и четвертым устройствами).
В ходе имитационных экспериментов надо найти
функциональные зависимости
j i
i j
;
T
j i
i j
По гипотезе они имеют вид полиномов.
7
Временная диаграмма функционирования ВС
1
= 1
1
= 1
1
= 1
1
= 1
1
= 1
1
= 1
1
= 1
1
= 1
t
к222
t
к223
t
к124
t
к134
t
к225
t
к126
t
н118
t
н136
t
1
t
2
t
3
t
4
t
0
t
к111
t
к212
t
к213
t
к114
t
к215
t
к117
t
к116
t
к131
t
к243
t
к245
t
н131
21
2
= 1
2
= 1
2
= 1
2
= 1
2
= 1
2
= 1
3
=
1
4
= 1
4
=
0
2
= 0
4
= 0
4
= 1
3
= 1
3
= 1
3
= 0
3
= 0
1
= 0
1
= 0
1
= 0
1
= 0
1
= 0
1
= 0
1
= 0
2
= 0
2
= 0
2
= 0
2
= 0
2
= 0
4
= 0
4
= 0
t
н111
11
t
н121
12
t
н223
22
t
н134
13
t
н
124
22
t
н
225
22
t
н
126
12
t
н
243
24
t
н
245
24
t
н242
24
t
н222
22
t
н212
21
t
н213
21
t
н114
11
t
н116
11
t
н117
11
t
н215
21
q
0
q
1
q
2
q
3
q
4
q
5
q
6
q
8
q
9
q
10
q
12
q
18
q
15
q
16
q
17
q
14
q
13
q
11
q
7
8
Для начала предполагаем, что целевые функции имеют
вид линейных регрессионных зависимостей откликов ИМ от
параметров моделирования:
j j j j
i i i i
T
0 1 1 2 2
0 1 1 2 2
;
,
где
0 j
и
2i
- коэффициенты регрессионных зависимостей,
значения которых надо определить в ходе ИМ.
Глобальные переменные, характеризующие связи между
устройствами:
j
- счетчики числа заданий, находящихся в очереди
на обработку к
У
j
.
ОЧ
j
- очереди, содержащие номера типов заданий i на
обработку к
У
j
.
j
1
0
, если
У
j
занято
, если
У
j
пусто
9
8.2. ФОРМАЛИЗАЦИЯ ВЫЧИСЛИТЕЛЬНОЙ
СИСТЕМЫ АКТИВНОСТЯМИ
AK
11
УЗ
11
;
AK
11
УЗ
11
;
AK
12
УЗ
12
;
AK
13
УЗ
13
;
AK
14
УЗ
14
;
AK
20
УЗ
20
;
AK
21
УЗ
21
;
AK
22
УЗ
22
;
AK
23
УЗ
23
;
AK
24
УЗ
24
;
B
11
; B
21
;
B
31
; B
41
;
H
11
; H
21
; H
31
;
H
41
; H
51
; H
61
;
H
71
; H
81
;
H
12
; H
22
; H
32
;
H
42
; H
52
; H
62
;
H
72
; H
82
;
H
14
; H
24
; H
34
;
H
44
; H
54
; H
64
;
H
74
; H
84
;
H
13
; H
23
; H
33
;
H
43
; H
53
; H
63
;
H
73
; H
83
;
B
12
; B
22
;
B
32
; B
42
;
K
11
; K
21
;
K
31
; K
41
;
K
51
; K
61
;
K
12
; K
22
;
K
32
; K
42
;
K
52
; K
62
;
K
13
; K
23
;
K
33
; K
43
;
K
52
; K
63
;
K
14
; K
24
;
K
34
; K
44
;
K
54
; K
64
;
10
Переход устройства из простоя к занятости и обратно
будем отображать в модели соответствующей активностью
AK
ij
.
Индекс i у обозначения n/n, реализующих алгоритмы
активностей, соответствует стадии обработки заданий
(i=1 - начало обработки, i=2 - конец обработки).
Индекс j - номер У.
УЗ
i j
- условия инициализации (запуска) данной
активности.
Если УЗ
i j
выполняются, то УПМ включает
соответствующую активность AK
ij
в список
инициализируемых активностей.
При невыполнении УЗ
i j
УПМ данную активность
пропускает и меняет номер активности.
Активности AK
i0
моделируют процесс поступления
заданий i-го типа извне на обработку первому устройству.
УПМ включает в работу алгоритм AK
i0
при выполнении
условия Уз
i 0
, которое состоит в наступлении момента
поступления задания i-го типа (t
ia
) в очередь ОЧ
1
на
обработку
t t
ia
0
.
Операторы B
1i
записывают в очередь ОЧ
1
к У
1
очередной номер задания типа i.
Операторы B
2i
увеличивают значения счетчика числа
заданий в очередь ОЧ
1
к У
1
1 1
1
.
Операторы B
3i
формируют моменты t
ia
очередной
активности Ak
i0
,представляющие собой сумму текущего
значения модельного времени t
0
и интервала времени,
после которого новое задание i-го типа поступает в S:
t t
ia i
0
1
,
где
i
- значения интенсивностей поступления
заданий i-го типа для данного варианта моделирования.
11
Операторы B
4i
возвращают управление УПМ, которая
заносит очередное значение t
ia
в упорядоченный по
возрастанию список моментов инициализации активностей.
Алногритм выполнения AK
1j
и AK
2j
состоит из
операторов, соответственно, H
aj
и K
bj
a 1, 8 b 1, 6,
.
Активности AK
1j
инициализируются УПМ при совместном
наступлении двух событий:
- j-ое устройство свободно;
- имеются в ОЧ
j
к нему задания
УЗ
j j1
0 0 :
j
.
Активности AK
2j
инициализируются УПМ при наступлении
момента окончания обработки задания j-м устройством
УЗ t
j2 0
: t
ia
.
Операторы H
1j
и K
1j
обеспечивают фиксацию моментов,
соответственно, начала (t
нijh
) и конца (t
кijh
) обработки
заданий.
Алгоритм выполнения
AK
j1
j = 1, 4
:
1) С помощью операторов H
2j
устанавливаются признаки
занятости У
j
обработки задания
j
1
.
2) Операторы H
3j
организуют выбор из ОЧ
j
номера
задания i. Номер очередного задания i, обрабатываемого j-
м устройством в данный момент модельного времени,
содержится в глобальной переменной модели
j
.
3) Запоминание номера задания i в
j
обеспечивается
оператором H
4j
j
1
.
4) Уменьшение на 1 числа заданий, находящихся в
очереди к j-му устройству, выполняется оператором H
5j
j j
1
.
Для формирования моментов очередной инициализации
активностей используются функции распределения
длительностей обслуживания заданий
F
i j
.
12