Logo GenDocs.ru

Поиск по сайту:  


Загрузка...

Лекции - файл 1.doc


Лекции
скачать (447.5 kb.)

Доступные файлы (1):

1.doc448kb.17.11.2011 07:07скачать

содержание
Загрузка...

1.doc

Реклама MarketGid:
Загрузка...




8.1. ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ

ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЫ


Основные этапы разработки имитационной модели вычислительной системы рассмотрим на примере:


1. Содержательное описание объекта (описание ВС)




Имеется часть ВС обработки заданий двух типов четырьмя устройствами

Задания 1-го типа обрабатываются строго последовательно устройствами УСТ1, УСТ2, УСТ3.

Выбор типа задания при его обработке на устройстве УСТ1 случайный.

Запрещена одновременная обработка заданий разных типов устройствами УСТ1 и УСТ2.

Обработка заданий 1-го и 2-го типов соответственно устройствами УСТ3 и УСТ4 осуществляется только в том случае, когда эти устройства свободны.

На каждом из устройств обработка заданий производится в порядке поступления заданий.

Показателями качества моделируемой системы будут выступать:

- интенсивность поступления заданий в ВС на загрузку устройств;

- пропускная способность ВС;

- среднее время полной обработки одного задания.

^ Управляемая переменная - интенсивность поступления заданий в ВС на обработку.

Контролируемые характеристики моделирования - статистики моделирования, позволяющие определить:

  • загрузку устройств (суммарное время обработки заданий каждым устройством);

  • пропускную способность ВС (количество заданий каждого типа, обрабатываемых ВС);

  • среднее время полной обработки одного задания (интервал от момента поступления задания в ВС на обработку до момента завершения его обработки в ВС).

Описание режимов функционирования сводится к следующим действиям:

- определяются выборки значений времен обработки заданий устройствами , где i - тип задания, j - устройство;

- известными статистическими методами по выборкам формируются соответствующие функции распределения времени обработки i-го задания j-ым устройством (аналитические или табличные).

Описание внешней среды сводится к указанию механизма выбора типа заданий i:

- задания 1-го типа поступают на обработку с вероятностью , а задания 2-го типа - с вероятностью ;

- интенсивность поступления заданий извне является общей для заданий обоих типов;

- поступление заданий в ВС не зависит от ситуации в ВС и от времени и продолжительности работы ВС.

2. Концептуальная модель

Декомпозиция модели осуществляется просто:

  • отдельными элементами данной системы (ВС) будут устройства;

  • параметры системы - интенсивности поступления заданий 1-го и 2-го типов ( и ). Для простоты допустим, что поступления заданий обоих типов подчиняется пуассоновскому закону;

  • переменные модели - это функции распределения длительностей обслуживания i-го задания j-ым устройством .

В качестве статистик моделирования будут выступать:

  • коэффициенты загрузки устройств ;

  • количество обработанных j-тым устройством заданий ;

  • размеры очередей к каждому из устройств ;

  • общее время обработки i-го задания в ВС .

Критерии эффективности:

  • коэффициенты загрузки ;

  • среднее значение времен обработки заданий .

В результате имитационного моделирования необходимо найти следующие функциональные зависимости:

; .

При задании функций распределения длительностей обслуживания задания на j-ом устройстве достаточна аппроксимация ступенчатыми функциями.

Выдвигается гипотеза, что и имеют вид полиномов, порядок которых и значения коэффициентов определяются в ходе имитационных экспериментов.

С помощью таких эмпирических зависимостей можно предсказать характеристики загрузки оборудования () и времена обслуживания заданий () в зависимости от при заданных .

Документация концептуальной модели:

  • схема;

  • текст содержательного описания;

  • список параметров и переменных ;

  • состав статистики моделирования ;

  • соотношения для критериев эффективности , ;

  • аппроксимирующие выражения для задаваемых переменных .



Формализация ВС как объекта моделирования


Составляется временнбя диаграмма взаимодействия устройств.

На диаграмму заносятся моменты начала и конца обработки i-го задания j-тым и длительности обработки заданий i-го типа j-тым ; h - порядковый номер, присваиваемый заданию любого типа при поступлении его на обработку к У1.

На временнуй оси t1 зафиксированы периоды обработки заданий 1-го и 2-го типов первым устройством ( У1);

На оси t2 - период обработки заданий 1-го и 2-го типов вторым устройством ( У2);

На осях t3 и t4 - соответственно периоды обработки заданий 1-го и 2-го типов устройствами У3 и У4;

На оси t0 - моменты q, соответствующие началу и концу обработки любого задания любым устройством.

На временной диаграмме также указаны моменты изменения значения признака j, где j - признаки нахождения j-го устройства в состоянии обработки i-го задания (j = 1 - Уj занято, j = 0 - Уj простаивает).

На диаграмме интервалы обработки заданий 1-го типа заштрихованы линиями “накрест”, а интервалы обработки устройствами заданий 2-го типа - параллельными косыми линиями.

Входная информация: функции распределения длительностей обслуживания заданий i-го типа j-м устройством и вероятность p1 поступления на первое устройство заданий первого типа. Эта вероятность вычисляется по интенсивностям поступлений заданий i-го типа () следующим образом:



Критерии эффективности системы и вычисляются по формулам:

,

где - коэффициент загрузки Уj;

- количество обработанных заданий i-го типа j-м устройством (в расчет берутся лишь задания, прошедшие обработку на j-ом устройстве);

- календарный период исследования ВС.

,

где и - число заданий, обработанных соответственно третьим и четвертым устройствами (в расчет берутся только задания, обработанные, соответственно, третьим и четвертым устройствами).

В ходе имитационных экспериментов надо найти функциональные зависимости

;

По гипотезе они имеют вид полиномов.


^ Временная диаграмма функционирования ВС




Для начала предполагаем, что целевые функции имеют вид линейных регрессионных зависимостей откликов ИМ от параметров моделирования:



где и - коэффициенты регрессионных зависимостей, значения которых надо определить в ходе ИМ.





, если занято

, если пусто
Глобальные переменные, характеризующие связи между устройствами:

- счетчики числа заданий, находящихся в очереди на обработку к .

ОЧj - очереди, содержащие номера типов заданий i на обработку к .

^ 8.2. ФОРМАЛИЗАЦИЯ ВЫЧИСЛИТЕЛЬНОЙ




СИСТЕМЫ АКТИВНОСТЯМИ


Переход устройства из простоя к занятости и обратно будем отображать в модели соответствующей активностью AKij.

Индекс i у обозначения n/n, реализующих алгоритмы активностей, соответствует стадии обработки заданий (i=1 - начало обработки, i=2 - конец обработки).

Индекс j - номер У.

УЗij - условия инициализации (запуска) данной активности.

Если УЗij выполняются, то УПМ включает соответствующую активность AKij в список инициализируемых активностей.

При невыполнении УЗij УПМ данную активность пропускает и меняет номер активности.

Активности AKi0 моделируют процесс поступления заданий i-го типа извне на обработку первому устройству.

УПМ включает в работу алгоритм AKi0 при выполнении условия Узi0, которое состоит в наступлении момента поступления задания i-го типа (tia) в очередь ОЧ1 на обработку .

Операторы B1i записывают в очередь ОЧ1 к У1 очередной номер задания типа i.

Операторы B2i увеличивают значения счетчика числа заданий в очередь ОЧ1 к У1 .

Операторы B3i формируют моменты tia очередной активности Aki0,представляющие собой сумму текущего значения модельного времени t0 и интервала времени, после которого новое задание i-го типа поступает в S:

,

где - значения интенсивностей поступления заданий i-го типа для данного варианта моделирования.

Операторы B4i возвращают управление УПМ, которая заносит очередное значение tia в упорядоченный по возрастанию список моментов инициализации активностей.

Алногритм выполнения AK1j и AK2j состоит из операторов, соответственно, Haj и Kbj . Активности AK1j инициализируются УПМ при совместном наступлении двух событий:

- j-ое устройство свободно;

- имеются в ОЧj к нему задания

.

Активности AK2j инициализируются УПМ при наступлении момента окончания обработки задания j-м устройством .

Операторы H1j и K1j обеспечивают фиксацию моментов, соответственно, начала (tнijh) и конца (tкijh) обработки заданий.

Алгоритм выполнения :

1) С помощью операторов H2j устанавливаются признаки занятости Уj обработки задания .

2) Операторы H3j организуют выбор из ОЧj номера задания i. Номер очередного задания i, обрабатываемого j-м устройством в данный момент модельного времени, содержится в глобальной переменной модели .

3) Запоминание номера задания i в обеспечивается оператором H4j .

4) Уменьшение на 1 числа заданий, находящихся в очереди к j-му устройству, выполняется оператором H5j .

Для формирования моментов очередной инициализации активностей используются функции распределения длительностей обслуживания заданий .

5) Оператор H6j по номеру задания и формирует очередное значение интервала обработки заданий i j-ым устройством .

6) С помощью операторов H7j формируются запланированные моменты очередной инициализации AK2j, представляющие собой сумму текущего значения модельного времени и :

.

7) Операторы H8j возвращают управление УПМ.


При выполнении алгоритмов активностей AK2j реализуется следующая последовательность операторов:

1) Операторы K2j сбрасывают признак занятости Уj .

2) Операторы K3j обеспечивают извлечение номера задания i из формирования по нему номера очереди , куда поступает задание i-го типа после завершения обработки на Уj.

3) Операторы K4j записывают номер задания типа i в ОЧ.

4) Увеличение на 1 значения счетчиков числа заданий в очередях осуществляется оператором K5j .

^ 5) Операторы K6j обеспечивают возврат на УПМ.

Формализация вычислительной системы при

событийном способе имитации.



Анализ алгоритмов выполнения активностей, аппроксимирующих процесс обработки заданий устройствами, показывает, что их можно объединить по группам.

^ Объединим в один тип событий:

C3 - все запуски устройств на обработку заданий;

С4 - все окончания обработки заданий на устройствах.

Обозначим алгоритмы активностей AK1j в виде п/п обслуживания событий C3 ( ПО C3 ), а алгоритмы активностей AK2j в виде п/п обслуживания событий C4( ПО C4 ).

Сохраняется состав алгоритмов активностей AKi0, моделирующих процесс поступления извне на обработку заданий i-го типа к первому устройству и условия их запуска УПМ (УЗi0).

Считаем, что поступление на обработку заданий i-го типа означает появление событий Ci (i=1, 2).

Алгоритмы активностей AKi0 также назовем п/п обслуживания событий С1 и С2 ( ПОС1 и ПОС2).

Блоки проверки условий инициализации любой из активностей назовем п/п проверки выполнения событий.

Количество блоков проверки выполнимости условий инициализации активностей (УЗij) с восьми сократится до двух. Однако сами алгоритмы проверки условий увеличатся в размере.

П/п (УЗij) обслуживания события С3 инициируется УПМ, когда j-ое устройство свободно и к нему в ОЧj имеются задания:



Аналогично п/п (УЗ2j) обслуживания события С4 инициируется УПМ при наступлении окончания обработки заданий любым j-м устройством:



Алгоритмы AK1j и AK2j увеличатся на один оператор ФО. С помощью этого оператора определяется номер устройства j, начало или завершения работы которого обслуживает в данный момент п/п обслуживания события ПОС3 или ПОС4.

Как видно из схемы (стр. 14), число блоков проверки выполнимости условий, просматриваемых УПМ, сократилось вдвое.

Зато увеличились сами алгоритмы проверки выполнимости условий.

Практически проверка УЗ1j и УЗ2j требует одного и того же ресурса ЭВМ при обоих способах формализации.

Увеличение алгоритмов AK1j и AK2j на один оператор при общем уменьшении их количества дает вдвое экономию памяти ЭВМ, отводимой под модель.

Рекомендуется при простом алгоритме обслуживания событий предпочесть событийный способ, т.к. возможна экономия памяти.

Кроме того, при большом числе активностей, имеющих одинаковые алгоритмы определения условий инициализации и обслуживания активностей, возможна экономия машинного времени моделирования за счет сокращения общего времени работы УПМ при уменьшении размеров списков событий.


Скачать файл (447.5 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации
Рейтинг@Mail.ru