BC/NW 2016 № 1 (28):9.1
МОДЕЛИРОВАНИЕ ПЕРЕСТРАИВАЕМЫХ СТРУКТУР
МНОГОПРОЦЕССОРНЫХ СИСТЕМ СРЕДСТВАМИ GPSS WORLD
Дорошенко А.Н.
Одной из характерных особенностей
структур и алгоритмов функционирования современных вычислительных устройств и
систем (ВС) является заложенная в них при разработке возможность изменения
конфигурации структуры, программной настройки системы на определенный режим
работы и выполнения определенного набора функций в зависимости от решаемой
задачи.
Идея перестраиваемых структур ВС
практически является сквозной на всех уровнях детализации вычислительного
процесса, то есть проявляется на уровне отдельной микросхемы, на уровне работыустройства,
ЭВМ, вычислительной системы или сети.
Так, например, уже микросхемы средней
интеграции, БИС и тем более СБИС, являются многофункциональными и режимы их
работы задаются с помощью, так называемых, управляющих слов (например, программируемый
контроллер прерываний, программируемые связной и параллельный адаптеры,
программируемый таймер).
В многопроцессорных системах при распараллеливании
задач (сегментировании) и назначении процессора на каждый сегмент задачи
возникает проблема определения состава процессоров, участвующих в решении
данной задачи. И тем более эта задача является важной для организации работы
локальной вычислительной сети, где по существу сервер распределяет ресурсы для
решения поступившей задачи, определяет пути приёма-передачи сообщений в сети.
Известно, что одним из универсальных методов
анализа и исследования структур вычислительных систем и алгоритмов их
функционирования является имитационное моделирование, основанное на применении
системы моделирования общего назначения GPSS.
Основные понятия и принципы имитационного
моделирования дискретных систем, заложенные ещё в 1961 году Дж. Гордоном,
впервые были им опубликованы в 1975 году [1], а первая публикация GPSS на русском языке
появилась в 1980 [2]. Идеи, заложенные в GPSS, оказались
настолько значимыми, что система, пройдя путь развития (а точнее – адаптации к
технической базе) одновременно с развитием вычислительной техники и технологий
программирования, остаётся одной из основных систем дискретного имитационного
моделирования, востребованной и в настоящее время [3 – 7].
Фирмой Wolverine
Software разработана версия языка
GPSS, называемая
GPSS/H+PROOF. В
этой версии добавлены графические средства манипулирования с блок-схемами,
возможность использования анимации и гибкий интерфейс связи с языком
программирования C++. Для учебных целей наиболее удобной,
привлекательной и широко используемой является «студенческая» версия системы – GPSS WORLD 4.2.1,
именуемая в [5 – 7] как GPSS WORLD или GPSS/ W в
других источниках.
В данной работе рассматриваются вопросы
применения заложенных в основу алгоритма имитационного моделирования механизмов
и средств языка GPSS для описания и моделирования
перестраиваемых структур дискретных устройств, вычислительных систем и сетей
телекоммуникаций.
Основная цель применения
перестраиваемых структур – минимизация и компактность представления аппаратных
средств при оптимальной реализации заданного набора функций, выполняемых этими
средствами. Для отображения свойства перестраиваемости структур имитационными
моделями язык моделирования должен содержать соответствующие средства
модификации моделей.
Анализ изобразительных средств
языка GPSS показывает, что
свойства модификации описаний дискретных процессов в GPSS-моделях могут
быть реализованы следующим образом:
·
во-первых,
применением механизма косвенной идентификации имён объектов (устройств,
памяти, буферных накопителей и других объектов) модели;
·
во-вторых,
расширением понятия функции, заключающемся в том, что значением
функции может быть не только числовое значение, соответствующее значению
аргумента функции, но и просто идентификатор (имя объекта), а также применением
табличной формы представления функции в модели на GPSS;
·
в-третьих,
расширенной интерпретацией объекта STORAGE (память,
накопитель ограниченной ёмкости, очередь ограниченной длины, однородная группа
устройств обработки или многоканальное устройство – в
терминологии систем массового обслуживания);
·
в
четвёртых, применением заложенной в GPSS возможностью
размножения и объединения транзактов – динамических объектов, перемещающихся
по модели, которые в зависимости от постановки задачи и цели моделирования
интерпретируются также достаточно широко;
·
в
пятых, применением объекта ARRAY (матрица),
позволяющего описывать регулярные структуры переменной (настраиваемой) длины типа ПЛМ,
матричные процессоры.
Чтобы раскрыть содержательно
указанные свойства GPSS, необходимо отметить концепции языка и принципы
работы алгоритма, заложенные в системе моделирования GPSS.
1.
GPSS– ЯЗЫК
БЛОК-ДИАГРАММ. Описание моделируемой системы (GPSS-модель) представляет
собой последовательность так называемых БЛОКОВ, каждый из которых соответствует
некоторому оператору (подпрограмме), имеющему определенный набор реквизитов–полей
(формальных параметров), причем каждое поле в блоке имеет своё специфическое
функциональное назначение и занимает строго фиксированную позицию в списке
полей данного блока.
2.
Статические
объекты в GPSS – это прежде
всего модельные аналоги одноканальных устройств обслуживания (FACILITY), многоканальных
устройств обслуживания (STORAGE), очередей (QUEUE), и объекты,
отображающие условия перемещения транзактов по блокам модели – логические
ключи (LOGIC). К статическим
типам относятся также средства представления и вычисления данных – целые,
вещественные и логические переменные (Variable, Fvariable, Bvariable), функции (Function), сохраняемые
величины (Savevalue), матрицы (Matrix) и средства сбора
и обработки статистических данных – (Table).
3.
Динамические
объекты в GPSS – ТРАНЗАКТЫ,
порождаемые, продвигаемые по блокам модели по определенным правилам в процессе
моделирования и удаляемые из модели. Транзакты в моделируемых процессах могут
соответствовать запросам на решение задачи (запуск программы), заявкам на
обслуживание, материальным объектам или субъектам, перемещающимся в системе.
4.
Событийное
моделирование – в GPSS реализуется следующим образом.
4.1.
Организация
МОДЕЛЬНОГО ВРЕМЕНИ. Одним из базовых понятий в СМО является событие,
определяемое как изменение состояния системы. Моделирование системы на GPSS по существу
представляет собой имитацию последовательности переходов системы из одного
состояния в другое в некоторые моменты времени. В GPSS-модели время
отображается в условных единицах, масштаб для которых подразумевается
исследователем модели. На каждом очередном шаге моделирования модельное время
увеличивается на случайную величину, равную интервалу времени между
последовательными событиями.
4.2.
Формирование
и обработка СПИСКОВ ТРАНЗАКТОВ – АЛГОРИТМ реализации принципа СОБЫТИЙНОГО
МОДЕЛИРОВАНИЯ. Для имитации процессов, протекающих в моделируемой системе, в GPSS предусмотрен
следующий механизм работы с транзактами.
Все транзакты,
порождаемые в процессе моделирования, образуют пять списков: список текущих
событий – содержит транзакты с минимальным (текущим) модельным временем и
выбираются для перемещения по блокам модели, при равенстве приоритетов, по
правилу FIFO, либо с учетом
уровня приоритета; в списке текущих событий остаются также транзакты,
перемещение которых по модели оказывается невозможно из-за блокировки – приостановки
перемещения, в одном из блоков SEIZE, ENTER, GATE, TEST; список
будущих событий, в который попадают транзакты, задерживаемые в блоках ADVANCE, GENERATE, и перемещение
которых планируется алгоритмом моделирования в будущие моменты времени; список
прерываний, в который попадают транзакты, прерванные блоком прерываний PREEMPT, имитирующим
обслуживание транзакта с абсолютным приоритетом, по правилу LIFO (last in – first out); список
синхронизации – содержит транзакты, ожидающие в блоках GATHER, ASSEMBLE объединения с
другими транзактами одного семейства или находящихся в блоках MATCH; список
пользователя – содержит транзакты, управление которыми происходит не
автоматически, а при участии пользователя с помощью блоков LINK, UNLINK.
5.
Моделирование
и синхронизация параллельных процессов – обеспечивается, во-первых,
механизмами и средствами продвижения транзактов по модели и, во-вторых,
дополнительными средствами – размножения транзактов – блок SPLIT и трёх видов
синхронизации транзактов во времени – блоки GATHER, ASSEMBLE, MATH.
5.1.
Программа
моделирования может состоять из нескольких сегментов, в каждом из которых
транзакты порождаются и перемещаются независимо от других сегментов; сегменты
имитируют соответствующие реальные независимые параллельные процессы
моделируемой системы, в частности, это могут быть параллельно выполняемые секции
одной программы.
5.2.
Средством
размножения транзактов (порождения семейства, имитирующего декомпозицию
реального процесса) является блок SPLIT A,B,C,D, где A – количество
копий текущего транзакта, входящего в блок, B – метка,
определяющая блок, в который входят все порожденные копии транзакта, C – параметр, в
котором хранятся номера копий транзактов, D – количество
параметров, задаваемых копиям транзактов. Порожденные транзакты совместно с
порождающим перемещаются по ветвям модели, имитирующим параллельные процессы,
и могут быть либо удалены (попадая в блок TERMINATE), имитируя
завершение процессов, либо попадают в один из блоков сборки: в блок GATHER Ag (Ag –количество
собираемых транзактов одного семейства) с последующим перемещением и
обслуживанием всех транзактов одного семейства по правилу FIFO – имитация
последовательного выполнения Ag процессов, или в блок ASSEMBLE Ag с объединением (слиянием)
всех Ag транзактов в
один транзакт – имитация слияния Ag процессов в один.
5.3.
Имитация
синхронизации двух процессов во времени реализуется в GPSS блоками MATCH А, где А –
метка, определяющая блок, сопряженный с данным блоком. Имитация синхронизации
состоит в задержке и ожидании транзакта в любом из блоков MATCH (например, в
блоке MATCH MET2) до тех пор, пока другой транзакт данного семейства не
достигнет сопряженного с ним блока MATCH (например,
блока MATCH MET1), где метки
в поле А (то есть метки MET2 и MET1) взаимно
связывают оба блока, обеспечивая таким образом синхронизацию перемещения
транзактов, попадающих в эти блоки:
MET1 MATCH
MET2
…………….
…………….
MET2 MATCH MET1
6.
Последовательное
перемещение транзакта по модели может быть нарушено блоком TRANSFER, определяющим
для вошедшего в него транзакта номер следующего блока в зависимости от
некоторого условия. При этом, существует восемь вариантов формирования этого
условия – от безусловного перехода (типа GOTO…) и чисто
условного (типа IF…THEN…) до перехода по вероятности, или перехода
на первое свободное устройство последовавтельным сканированием состояния ряда
устройств (например, устройств регулярной структуры), или, наконец, обращением
к некоторой подпрограмме, вычисляющей номер следующего блока (устройства), в
который будет перемещаться транзакт.
7.
Механизм
КОСВЕННОЙ ИДЕНТИФИКАЦИИ проявляется в том, что соответствующее поле блока содержит
идентификатор, значение которого определяет собственно имя (номер) объекта
(например, устройства) или этот идентификатор определяет способ указания на место
нахождения имени. Например, блок SEIZE P$3 означает
занятие одноканального устройства, имя которого хранится в параметре 3 текущего
транзакта. При этом значение P$3 может быть числом –номером устройства
или идентификатором (именем) устройства, заданном в разделе объявлений объектов
модели. При этом для задания значения параметра (например, P$3) транзакта
существует блок ASSIGN A,B , где А – номер
параметра транзакта, В – целое число. Примеры:
ASSIGN 3,5 ; параметру
3 присваивается значение 5: P$3:=5
ASSIGN 3,FN$STR1 ; параметру 3
присваивается значение дискретной функции STR1: P$3:= FN$STR1 .
Перечисленные средства реализации
косвенной идентификации позволяют задавать некоторое неограниченное
(перестраиваемое, адаптируемое) множество устройств (процссоров), входящих в
систему, и оперативно менять конфигурацию системы в зависимости от типа задачи,
поступающей в систему. Интерпретация объекта STORAGE позволяет
задавать компактное описание регулярных структур типа многопроцессорные
системы, где каждая позиция STORAGE имитирует один процессор.
Таким образом, GPSS-средства
описания структур дискретных систем и имитации происходящих в них дискретных
процессов позволяют строить и эффективно исследовать компактные представления
моделей сложных регулярных и перестраиваемых структур и алгоритмов выполнения
процессов в вычислительных устройствах, системах сбора, обработки и передачи данных
и сетях телекоммуникаций. Проблема состоит в правильной (адекватной)
семантической интерпретации средств языка GPSS и применении заложенных
в систему GPSS механизмов
событийного моделирования и имитации параллельных процессов реальных
моделируемых дискретных систем.
Литература
1. Gordon
G. The Application of GPSS V to Discrete System Simulation. – Prentice-Hall,
Englewood Cliffs, N. J. – 1975. – 389 pp.
2. Шрайбер
Т.
Дж.
Моделирование
на
GPSS = Schriber,
T. J.
Simulation
using GPSS.
New York,
1974, Wiley. —
М.:
Машиностроение,
1980. — 592 с
3. Дорошенко А.Н.,
Федоров В.Н. Моделирование дискретных систем. Метод. пособие. – М.: Изд-во МЭИ,
2001. – 44 с.
4. Рыжиков Ю.И.
Имитационное моделирование. Теории и технологии. – СПб.: КОРОНА принт; М.:
Альтекс-А, 2004, 384 с.
5. Варжапетян А.Г.
Имитационное моделирование на GPSS/H. – М.:
Вузовская книга, 2007. – 424 с.
6. Кудрявцев, Е.М.
GPSS Word : / Е.М.Кудрявцев. — Москва: ДМК Пресс, 2008. — 317 с
7. Сосновиков Г.К.
, Воробейчиков Л.А. Компьютерное моделирование. Практикум по имитационному
моделированию в среде GPSS World: Учебное пособие / Г. К. Сосновиков, Л. А.
Воробейчиков. — Москва: Инфра-М Форум, 2015. — 112 с
