Russian Language English Language

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

10.1 СИСТЕМА АВТОМАТИЗИРОВАННОГО РАСЧЕТА ХАРАКТЕРИСТИК ТИПОВЫХ СХЕМ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ

10.2 ОСНОВЫ МЕТОДИКИ ПОСТРОЕНИЯ ИМИТАЦИОННЫХ GPSS-МОДЕЛЕЙ ПЕРЕСТРАИВАЕМЫХ СТРУКТУР ДИСКРЕТНЫХ ПРОЦЕССОВ И СИСТЕМ

10.3 ПРИМЕНЕНИЕ ГЕНЕТИЧЕСКОГО АЛГОРИТМА В НЕЙРОННЫХ СЕТЯХ СЕТИ

10.4 АНАЛИЗ ВОЗМОЖНОСТИ ИСПОЛЬЗОВАНИЯ СУЩЕСТВУЮЩИХ МЕТОДИК ОЦЕНКИ ИНФОРМАЦИОННЫХ РИСКОВ ДЛЯ ОБЛАЧНЫХ ВЫЧИСЛЕНИЙ

10.5 ИСПОЛЬЗОВАНИЕ ГЕОИНФОРМАЦИОННОЙ СИСТЕМЫ ZULUGIS ДЛЯ РАЗРАБОТКИ ЭЛЕКТРОННОЙ МОДЕЛИ СИСТЕМЫ ТЕПЛОСНАБЖЕНИЯ

10.6 ИССЛЕДОВАНИЕ СПЕЦИФИКИ ПОСТРОЕНИЯ МОДЕЛИ НАБЛЮДАЕМОСТИ ЦИФРОВОЙ ПОДСТАНЦИИ

10.7 . РЕАЛИЗАЦИЯ АЛГОРИТМА АДАПТИВНОГО МОДАЛЬНОГО УПРАВЛЕНИЯ МНОГОМЕРНЫМИ ОБЪЕКТАМИ В СРЕДЕ MATLAB/SIMULINK


Экспресс информация

Редколлегия журнала

Подписка на новости

Гостевая книга

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

Письмо в редакцию

На начало


2017, Номер 1 ( 30)



Place for sale

BC/NW 2017 № 1 (30)

ОСНОВЫ МЕТОДИКИ ПОСТРОЕНИЯ ИМИТАЦИОННЫХ GPSS-МОДЕЛЕЙ ПЕРЕСТРАИВАЕМЫХ СТРУКТУР ДИСКРЕТНЫХ ПРОЦЕССОВ И СИСТЕМ

Дорошенко А.Н.

В работе [1] кратко рассмотрены принципы, механизмы и операционные средства системы GPSS WORLD, позволяющие строить и исследовать компактные представления моделей сложных регулярных и перестраиваемых структур и алгоритмов выполнения процессов в вычислительных устройствах, системах сбора, обработки и передачи данных и сетях телекоммуникаций. Проблема состоит в правильной (адекватной) семантической интерпретации средств языка GPSS и применении заложенных в систему GPSS механизмов событийного моделирования и имитации параллельных процессов моделируемых дискретных систем. В данной работе делается попытка конкретизировать эти возможности на ряде примеров использования языковых средств, механизмов идентификации и косвенной адресации объектов GPSS.

Тема1: Идентификация параметров транзактов и элементов памяти

Задача 1. На вход многопроцессорной системы (МС) поступает два потока заявок, имеющих пуассоновское  распределение с интенсивностями Lp1 и Lp2 и требующих обработки на любом из процессоров.  Времена обработки заявок  tо1 и  tо2 - случайные величины с экспоненциальным распределением и параметрами 1/То1 и 1/То2. Построить GPSS-модель  работы МС, предусмотрев вычисление пропускной способности МС как количество обработанных заявок первого и второго потока за единицу времени.

Примечания.

1.     Схема рассматриваемой системы отличается от типовых СМО наличием  двух потоков заявок с различными интенсивностями входа в систему и различными интенсивностями обслуживания, поэтому оценка численных значений характеристик системы возможна только  имитационным моделированием.

2.     Рассматриваемая модель относится к классу многоканальных СМО с неограниченной очередью и для обеспечения требования стационарности случайных процессов  должно выполняться условие ненасыщенного  режима работы моделируемой системы:  (Lp1+Lp2)/[ (То1+То2)/(2*То1*То2)*N ] < 1, где N – количество процессоров в МС. С учётом этого условия в GPSS-модели задаём, например, следующие  значений исходных данных: Lp1=10 заявок в сек.; Lp2=15 заявок в сек ; To1= 18 сек; To2= 7сек;  N  >252, пусть N=256 процессоров.

*   объявление объектов

MC   equ 1

MC   storage 256 ; количество процессоров в МС

OCH equ 1

Lp1   equ 10

Lp2   equ 15

То1   equ 18

То2   equ 7

Tsim equ 86400 ; время моделирования (имитации работы МС) – в секундах

Simulate

*   генерация первого потока заявок

Generate (exponential (1,0,1/L1));  1/L1=0.1сек = Твх1

Assign 1,1; в первом параметре  транзакта идентифицируется номер потока 1

Transfer  ,proc; безусловное перемещение заявки в очередь  к процессорам

*    генерация второго потока заявок

Generate  (exponential (2,0, 1/L2)); 1/L2= Твх2

Assign 1,2; в первом параметре  транзакта идентифицируется номер потока 2

proc  Queue  OCH; занять очередь к процессорам

Enter MC; занять один из свободных процессоров

Depart OCH; выйти из очереди

Test  E  p1,1,potok2; проверка условия принадлежности заявки к потоку 1 или 2

Advance (exponential (3,0,To1));  время обработки t1 заявки потока 1

Savevalue  sch1+,1; счёт числа обработанных заявок потока 1

Transfer  ,vyhproc; безусловное перемещение заявки из процессора

potok2  Advance (exponential (3,0,To2));  время обработки t2 заявки потока 2

Savevalue  sch2+,1; счёт числа обработанных заявок потока 2

vyhproc Leave MC; освободить процессор

Savevalue  proizv1, sch1/Tsim;  вычисление доли производительности блока

*процессоров при обработке заявок первого потока

Savevalue  proizv2, sch2/Tsim;  вычисление доли производительности блока *процессоров при обработке заявок второго потока

Savevalue  proizv0, (sch1 + sch2 )/Tsim;  вычисление общей производительности *блока процессоров при обработке заявок первого и второго потока

Terminate; удаление заявки из системы

*     сегмент задаёт время  окончание процесса моделирования, равное 24 часам с                    *     точностью до 1 сек.

Generate  Tsim;

Terminate  1

Start 1

Примечание: получаемые  по результатам имитационного моделирования значения производительности МС следует скорректировать, разделив эти значения на среднее значение коэффициента занятости блока процессоров, формируемое системой GPSS в файле результатов.

Тема 2: Применение  расширенного понятия функции – FUNCTION 

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

Name  FUNCTION A,B

x1,y1/x2,y2/…xn,yn

где А – аргумент функции – может быть именем, целым положительным числом, строкой, выражением в скобках, СЧА, СЧА*параметр;  В – тип функции, состоящий из одной буквы, определяющей собственно тип, и числа, задающего количество пар значений  аргумента и функции{ хi,yi} – координат точек i=1..n на плоскости графика функции.

В GPSS существует пять типов функций: С – непрерывная, D – дискретная, L – списковая числовые функции и E и M – дискретная и списковая атрибутивные функции.

Для наших целей предпочтительными являются варианты применения функций типа D с аргументами имя и СЧА*параметр. Рассмотрим  варианты применения этих функций на примерах.

 Пример1. Пусть требуется входной поток заявок распределить случайным образом с заданными вероятностями 0.2, 015, 0.3, 0.25, 0.1на n=5 одноканальных устройств (OKU)некой системы. Положения устройств в модели системы не упорядочены, поэтому обращение к ним задается метками met1,…, met5. Тогда фрагмент модели будет иметь вид:

*объявление функции Rpd; аргументом функции является встроенная функция RN, *генерирующая числа  в  диапазоне (0,1), 29 –  начальное – произвольное положительное *целое число, задаваемое при написании программы

Rpd  FUNCTION  RN29,D5

.2,met1/.35,met2/.65,met3/.9,met4/1,met5

         Simulate

         Generate (Exponential(13,0,25))

         TRANSFER  FN,Rpd; блок изменения маршрута транзакта Transfer здесь *работает в режиме функции, которая реализует выборку меток в соответствии с *заданными вероятностями

         Met1 seize OKU1…………….

                   …

         Met2 seize OKU2……………

                   …

         Met3 seize OKU3…………….

                   …

         Met4 seize OKU4 …………….

                  

         Met5 seize OKU5…………….

Пример2. Пусть в одном и том же ОКУ требуется имитировать блоком ADVANCE  интервал времени обслуживание заявок с различными  средними значениями, задаваемыми функцией Tobsl. Тогда настройка на заданное время определяется этой функцией, аргументом которой назначается параметр Р1активного транзакта, поступающего в блок ADVANCE:

Rpd  FUNCTION  RN29,D5

.2,met1/.35,met2/.65,met3/.9,met4/1,met5

*объявление функции времени обслуживания; аргумент функции – первый параметр *транзакта

Tobsl  FUNCTION  P1,D5

1,4.5/2,2.7/3,2.5/4,0.7/5,3.3

         Simulate

         Generate (exponential(13,0,25))

        

Advance  (Exponential(17,0,FN$Tobsl)); среднее значение времени *обслуживания определяется первым параметром транзакта, поступающего в данный *блок

Идея косвенной адресации состоит в том, что каждый транзакт в некотором своем параметре содержит номер того или иного объекта, а в полях блоков соответствующих объектов записывается ссылка на этот параметр транзакта. При косвенной адресации СЧА определяются как СЧА*параметр, где  параметр - это номер или имя параметра активного транзакта, содержащего номер нужного блока. Например, Q*2 – текущее значение длины очереди, номер которой является значением второго параметра  активного транзакта, SR*Npm – коэффициент использования памяти (storage), номер которой содержится в параметре с именем Npm активного транзакта.

Пример 3.

Seize P*X1; Занять ОКУ, номер которого содержится в параметре, номер

*которого определяется значением ячейки Х1.

Пример 2.

Var1 Variable 1+RN1/250; переменная принимает случайные целые из 1..4

                   …

Assign  2,V$Var1; параметру 2 присваивается значение переменной Var1

Test  L  Q*2,10,UDAL; проверяется условие, меньше  ли числа 10 текущее

*значение длины очереди Q, номер которой является значением второго параметра  *активного транзакта.

Пример 3.

Savevalue 1, X*P3; поместить в ячейку с номером 1 значение, содержащееся в

*ячейке Х, номер которой определяется значением параметра 3 активного транзакта, *вошедшего в блок Savevalue.

Тема3: Применение SELECT – блока выбора направления перемещения транзакта по условию состояния отдельного устройства, памяти, очереди или по условию соотношения состояний этих объектов.

         Структура блока:  SELECT  условие  A,B,C,D,E,F, где  условие – это:

1) логическая переменная типа стандартный логический атрибут (СЛА):

·        объекта типа Facility: U –занято, NU – не занято, I – прервано, NI – не прервано устройство, номер j которого находится последовательным сканированием номеров из диапазона (В..С) номеров устройств Facility,

·        объекта типа Storage : SE – память пуста, SNE – память не пуста, SF – память заполнена,  SNF – не заполнена память, номер j которого находится последовательным сканированием номеров из диапазона (В..С) номеров устройств Storage,

2)или логическое выражение типа отношения: E – равно, NE – не равно,  G – больше, GE – больше или равно, L – меньше, LE – меньше или равно величине D значение некоторого стандартного  числового атрибута (СЧА), указываемого в поле Е блока SELECT,

3) или MIN, MAX – операции поиска номера j из диапазона номеров (B..С) объектов с минимальным или максимальным значением СЧА (в поле Е).

В поле А блока SELECT записывается номер параметра транзакта, в который заносится номер объекта, удовлетворяющего  заданному условию.

Таким образом, если при поступлении текущего активного транзакта в результате выполнения подпрограммы блока SELECT  находится устройство, для которого выполняется условие, то параметру А этого транзакта присваивается значение номера соответствующего объекта (устройства или памяти или очереди), а сам транзакт перемещается в следующий блок GPSS-модели.

Если условие не выполняется, то текущий транзакт перемещается по метке в поле F блока SELECT, а при отсутствии метки транзакт переходит в следующий блок модели.

Рассмотрим варианты применения блока SELECT для имитации работы перестраиваемой структуры МС на конкретном примере.

Пример 4. Пусть  вычислительная система представлена совокупностью m процессорных блоков, каждый из которых содержит некоторое число N1,N2,…,Nm процессорных модулей (процессоров).  В процессе моделирования в текущий момент работы ВС требуется найти процессорный блок по одному из признаков:

1.     процессорный блок с максимальным числом свободных процессоров;

2.     процессорный блок с количеством свободных процессоров не менее 3;

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

Процессорный блок в модели представим многоканальным устройством (МКУ) (по терминологии GPSS это объект Storage) и в i-том блоке задаём Ni – количество параллельно работающих  процессорных модулей. В модели нумерация процессорных блоков должна быть сквозная от 1 до m.

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

Решение варианта 1 (пусть m=16):

             

SELECT max  4,1,16,,R; поле F в этом режиме не требуется

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

* (из диапазона 1..16), в котором наибольшее количество свободных процессорных *модулей, где R – СЧА – количество свободных элементов памяти (storage) и каждый из *элементов имитирует процессорный модуль выбранного процессорного блока.

Решение варианта 2:

             

     SELECT GE 4,1,16,3,R,?

*комментарий: в четвёртый параметр транзакта заносится номер первого процессорного *блока (из диапазона 1..16), в котором не менее трёх свободных процессорных модулей, *если же такой процессорный блок не найден, то если поле F=? пустое, то транзакт *переходит  в блок модели, следующий за блоком SELECT, иначе по метке F.

Решение варианта 3:

SELECT min  2,1,16,,Q; поле F в этом режиме не требуется

*комментарий: во второй параметр транзакта заносится номер той очереди, в которой в *данный момент находится наименьшее количество запросов на выполнение задания, где *Q – СЧА – текущая длина очереди (queue).

Рассмотрим  применение блока SELECT на примере следующей задачи.

Задача 2. На вход вычислительной сети (ВС), содержащей m независимых и равнозначных по характеристикам узлов (одноканальных устройств ОКУ) обслуживания заявок, поступает пуассоновский поток заявок с интенсивностью Lam. Заявки по некоторому признаку делятся на три группы и  поступают в сеть с вероятностями 0.25, 0.6 и 0.15. Любая заявка поступает на любой свободный узел ОКУi, i=1..m на обслуживание, а если нет свободного, то к тому узлу, к которому очередь заявок, ожидающих обслуживание, меньше. Время обслуживания – экспоненциальное с заданным средним Tobs. Очереди к узлам не ограничены . После завершения обслуживания   заявки первой группы удаляются, а заявки второй и третьей группы требуют обращения к серверу, время обслуживания на котором имеет нормальное распределение с заданными средним Ts временем и стандартным отклонением Dn.  Разработать GPSS-модель функционирования ВС, предусмотрев, кроме типовой статистики, предусмотренной в системе GPSS,  вычисление количества заявок, обслуженных каждым узлом ВС за сутки.

Примечание:  Для запуска программы следует задать числовые значения исходных данных. По умолчанию предполагается сквозная нумерация объектов каждого типа, например, всем ОКУ автоматически системой моделирования присваиваются номера 1..m, очереди к этим устройствам также имеют номера 1..m.  Число m должно быть задано – в данной программе – в блоках SELECT.

Grup FUNCTION  Rn555, D3

0.25,1/0.85,2/1,3

              Simulate

Generate (Exponential(1,0,1/Lam);

Assign 1,FN$Grup;

SELECT NU 2,1,m,,,vibor_och;выбор одного из 1..m  свободных устройств (ОКУ)

* и запись его номера в параметр 2 транзакта, поступившего в данный блок; при

*отсутствии свободного ОКУ транзакт передается по метке на блок выбора очереди

Transfer  ,Obsl;передача транзакта на обслуживание

vibor_och SELECT min  2,1,m,,Q; выбор очереди с минимальной длиной

Obsl Queue P2;транзакт поступает в очередь с номером, содержащемся в параметре 2 *транзакта

Seize P2; транзакт пытается войти в ОКУ с номером, содержащемся в параметре 2

 

Depart  P2; транзакт освобождает очередь с номером, содержащемся в параметре 2 *транзакта

Advance (exponential(2,0,Tobs)); имитируется время обслуживания

Release P2; освобождается ОКУ с номером, содержащемся в параметре 2

Savevalue P2+,1;подсчитывается количество заявок, обслуженных каждым узлом ВС

Test  NE  P1,1,Vyhod;отбираются заявки второго и третьего типа для обработки в *сервере: ниже – постановка в очередь к серверу и обработка

Queue  Och_Serv;

Seize Server;

Depart  Och_Serv;

Advance (Normal (3,Ts,Dn));

Relese Server;

Terminate; удаление из модели заявок второго и третьего типа

Vyhod  Terminate; удаление из модели заявок первого типа

Generate 24*60*60*1000; время моделирования задано с точностью до ms

Terminate 1;

Start 1

Примечание. Применение косвенной адресации в этой модели позволяет имитировать  одной парой  блоков Queue и Depart не одну, а  m очередей, в блоках Seize и Releasem устройств ОКУ (узлов ВС), в блоке Savevaluem переменных – сохраняемых величин (по терминологии GPSS), в которых подсчитывается количество заявок, обработанных каждым из m узлов.

 

Литература

1.  Дорошенко А.Н. Моделирование перестраиваемых структур многопроцессорных систем средствами GPSS WORLD.  Электронный журнал «Вычислительные сети. Теория и практика».  BC/NW, 2016,  № 1 (28):9.1. – 7 с.

2.  Дорошенко А.Н., Федоров В.Н. Моделирование дискретных систем. Метод. пособие. – М.: Изд-во МЭИ, 2001. – 44 с.

3.  Рыжиков Ю.И. Имитационное моделирование. Теории и технологии. – СПб.: КОРОНА принт; М.: Альтекс-А, 2004, 384 с.

4.  Боев В.Д. Моделирование систем. Инструментальные средства GPSS WORLD: Учеб. Пособие. – СПб.: БХВ-Петербур, 2004. – 368 с.

5.  Варжапетян А.Г. Имитационное моделирование на GPSS/H. – М.: Вузовская книга, 2007. – 424 с.

6.  Кудрявцев, Е.М. GPSS Word : / Е.М.Кудрявцев. — Москва: ДМК Пресс, 2008. — 317 с

7.  Сосновиков Г.К. , Воробейчиков Л.А. Компьютерное моделирование. Практикум по имитационному моделированию в среде GPSS World:  Учебное пособие / Г. К. Сосновиков, Л. А. Воробейчиков. — Москва: Инфра-М Форум, 2015. — 112 с