Моделирование сложных дискретных систем
Предложена новая версия формального описания сложных дискретных систем – APRO-сети. Изложены структурные иалгоритмические особенности APRO-сетей. Приведен пример описания модели распределенной вычислительной системы,ориентированной на обработку реальной рабочей нагрузки. Табл.: 1. Ил.: 3. Библиогр.:...
Gespeichert in:
| Datum: | 2007 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут проблем математичних машин і систем НАН України
2007
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/777 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Моделирование сложных дискретных систем / Нестеренко Б.Б., Новотарский М.А. // Математические машины и системы. – 2007. – № 3, 4. – С. 111 – 121. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-777 |
|---|---|
| record_format |
dspace |
| spelling |
Нестеренко, Б.Б. Новотарский, М.А. 2008-06-27T11:38:34Z 2008-06-27T11:38:34Z 2007 Моделирование сложных дискретных систем / Нестеренко Б.Б., Новотарский М.А. // Математические машины и системы. – 2007. – № 3, 4. – С. 111 – 121. 1028-9763 https://nasplib.isofts.kiev.ua/handle/123456789/777 681.3 Предложена новая версия формального описания сложных дискретных систем – APRO-сети. Изложены структурные иалгоритмические особенности APRO-сетей. Приведен пример описания модели распределенной вычислительной системы,ориентированной на обработку реальной рабочей нагрузки. Табл.: 1. Ил.: 3. Библиогр.: 10 назв. Запропонована нова версія формального опису складних дискретних систем – APRO-мережі. Викладено структурні йалгоритмічні особливості APRO-мереж. Наведено приклад опису моделі розподіленої обчислювальної системи, орієнтованоїна обробку реального робочого навантаження. Табл.: 1. Іл.: 3. Бібліогр.: 10 назв. New version of formal description for complex discrete systems (APRO-nets) Is offered. Structural and algorithmic features of APROnetsare stated. The example of model description for distributed computing system focused on processing of real working load isadduced. Tabl.: 1. Figs.: 3. Refs.: 10 titles. ru Інститут проблем математичних машин і систем НАН України Моделювання і управління великими системами Моделирование сложных дискретных систем Моделювання складних дискретних систем Complex discrete system simulations Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Моделирование сложных дискретных систем |
| spellingShingle |
Моделирование сложных дискретных систем Нестеренко, Б.Б. Новотарский, М.А. Моделювання і управління великими системами |
| title_short |
Моделирование сложных дискретных систем |
| title_full |
Моделирование сложных дискретных систем |
| title_fullStr |
Моделирование сложных дискретных систем |
| title_full_unstemmed |
Моделирование сложных дискретных систем |
| title_sort |
моделирование сложных дискретных систем |
| author |
Нестеренко, Б.Б. Новотарский, М.А. |
| author_facet |
Нестеренко, Б.Б. Новотарский, М.А. |
| topic |
Моделювання і управління великими системами |
| topic_facet |
Моделювання і управління великими системами |
| publishDate |
2007 |
| language |
Russian |
| publisher |
Інститут проблем математичних машин і систем НАН України |
| format |
Article |
| title_alt |
Моделювання складних дискретних систем Complex discrete system simulations |
| description |
Предложена новая версия формального описания сложных дискретных систем – APRO-сети. Изложены структурные иалгоритмические особенности APRO-сетей. Приведен пример описания модели распределенной вычислительной системы,ориентированной на обработку реальной рабочей нагрузки. Табл.: 1. Ил.: 3. Библиогр.: 10 назв.
Запропонована нова версія формального опису складних дискретних систем – APRO-мережі. Викладено структурні йалгоритмічні особливості APRO-мереж. Наведено приклад опису моделі розподіленої обчислювальної системи, орієнтованоїна обробку реального робочого навантаження. Табл.: 1. Іл.: 3. Бібліогр.: 10 назв.
New version of formal description for complex discrete systems (APRO-nets) Is offered. Structural and algorithmic features of APROnetsare stated. The example of model description for distributed computing system focused on processing of real working load isadduced. Tabl.: 1. Figs.: 3. Refs.: 10 titles.
|
| issn |
1028-9763 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/777 |
| citation_txt |
Моделирование сложных дискретных систем / Нестеренко Б.Б., Новотарский М.А. // Математические машины и системы. – 2007. – № 3, 4. – С. 111 – 121. |
| work_keys_str_mv |
AT nesterenkobb modelirovaniesložnyhdiskretnyhsistem AT novotarskiima modelirovaniesložnyhdiskretnyhsistem AT nesterenkobb modelûvannâskladnihdiskretnihsistem AT novotarskiima modelûvannâskladnihdiskretnihsistem AT nesterenkobb complexdiscretesystemsimulations AT novotarskiima complexdiscretesystemsimulations |
| first_indexed |
2025-11-26T15:08:32Z |
| last_indexed |
2025-11-26T15:08:32Z |
| _version_ |
1850625759374213120 |
| fulltext |
ISSN 1028-9763. Математичні машини і системи, 2007, № 3, 4 111
УДК 681.3
Б.Б. НЕСТЕРЕНКО, М.А. НОВОТАРСКИЙ
МОДЕЛИРОВАНИЕ СЛОЖНЫХ ДИСКРЕТНЫХ СИСТЕМ
Abstract: New version of formal description for complex discrete systems (APRO-nets) is offered. Structural and
algorithmic features of APRO-nets are stated. The example of model description for distributed computing system
focused on processing of real working load is adduced.
Key words: APRO-net, position, simple transition, operational transition, token, action, process.
Анотація: Запропонована нова версія формального опису складних дискретних систем – APRO-мережі.
Викладено структурні й алгоритмічні особливості APRO-мереж. Наведено приклад опису моделі
розподіленої обчислювальної системи, орієнтованої на обробку реального робочого навантаження.
Ключові слова: APRO-мережа, позиція, простий перехід, операторний перехід, мітка, активність, процес.
Аннотация: Предложена новая версия формального описания сложных дискретных систем – APRO-сети.
Изложены структурные и алгоритмические особенности APRO-сетей. Приведен пример описания модели
распределенной вычислительной системы, ориентированной на обработку реальной рабочей нагрузки.
Ключевые слова: APRO-сеть, позиция, простой переход, операторный переход, метка, активность,
процесс.
1. Введение
За последние десятилетия существенное развитие получили дискретные системы [1, 2], то есть
такие системы, функционирование которых может быть представлено совокупностью состояний,
модифицируемых путем свершения событий [3]. Постоянное усложнение этих систем ведет к
возникновению существенных проблем на этапе тестирования и настройки, что может послужить
причиной снижения надежности, производительности или других эксплуатационных показателей.
Поэтому весьма актуальными стали вопросы развития формальных средств, позволяющих
адекватно описывать и исследовать упомянутые системы в виде моделей. Движущей силой к
развитию формальных средств является противоречивость предъявляемых к ним требований. С
одной стороны, упомянутые формальные средства должны допускать высокую степень
абстрагирования от второстепенных свойств объекта с целью упрощения работы с моделью. С
другой стороны, они должны быть достаточно мощными для обеспечения адекватности
представления свойств и аспектов системы, существенных на этапах разработки или оценки.
Современные формальные средства, кроме описания состояний и архитектуры системы, также
должны включать операционную семантику, задающую правила поведения ее компонент. Исходя
из указанной противоречивости требований к формальному описанию, высокой степени
адекватности можно достичь, только если для каждого конкретного случая создать семантические
правила, учитывающие требования, предъявляемые к модели, и особенности моделируемой
системы.
Формальные средства для создания моделей последовательных систем хорошо изучены.
Например, теория конечных автоматов [4] и дальнейшее ее развитие в виде теории агрегативных
систем [5] позволяют исчерпывающим образом описывать детерминированные модели систем,
функционирование которых может быть задано в виде единого процесса. Стохастические модели
систем подобного типа хорошо представляет теория массового обслуживания [6]. Однако для
адекватного представления параллельных или распределенных систем семантические правила
формального описания должны учитывать существенно больше информации об организации
ISSN 1028-9763. Математичні машини і системи, 2007, № 3, 4 112
вычислений. Полезными могут оказаться данные о том, какие процессы развиваются независимо,
когда необходимо учитывать причинно-следственные связи или производить выбор между
альтернативными вариантами. В этом случае семантика носит композиционный характер, то есть
позволяет построить глобальную модель системы путем установления взаимосвязей между
локальными моделями ее компонент.
На сегодня наиболее развитым и хорошо разработанным средством формального описания
параллельных и распределенных систем являются сети Петри [7], привлекающие к себе
пристальное внимание как теоретиков, так и практических пользователей. За более чем
сорокалетнюю историю своего развития сети Петри получили хорошую семантику, достаточно
корректно отображающую естественные свойства их параллельности. Однако простота сетей
Петри, являющаяся одной из причин их успеха, несет в себе ограничения для адекватного
представления сложных систем. Если необходимо более детально описать структуру состояния
системы, а также в случае, когда последовательность шагов невозможно свести к простой
причинной зависимости или конфликту, сети Петри в большинстве случаев теряют свою
адекватность.
Упомянутые ограничения стали одной из причин дальнейшего развития параллельных
средств формального описания, расширяющих возможности сетей Петри и получивших название
PRO-сетей [8]. Суть данного подхода состоит в отказе от задания жестких правил
функционирования переходов за счет введения специальных процедур, управляющих режимами
работы переходов и обработкой информации.
Асинхронные PRO-сети или APRO-сети являются новым шагом в развитии PRO-сетей и
ориентированы на описание параллельных вычислительных асинхронных структур.
2. Структура APRO-сети
Представим APRO-сеть в виде кортежа:
( )VMFTP ,,,,=Φ , (1)
где { }n
iipP 1== – конечное множество позиций;
{ }m
jjtT
1=
= – конечное множество переходов;
( ) ( )PTTPF ××= U – множество ребер между переходами и позициями;
{ }( ){ }n
k
pMax
llk
kpM
1
_
1,
=== µ – конечное множество маркирований;
( )ΛΨ∆= ,,V – множество глобальных переменных.
Графические элементы APRO-сети представлены в табл. 1. Подобно графическим
обозначениям сетей Петри, позиция APRO-сетей обозначается кружком, простой переход –
линией, связи – линиями со стрелками, а метка – точкой. Дополнительно введены обозначения,
связанные с элементами операторного перехода. Сам операторный переход изображается в виде
прямоугольника, а входы и выходы операторного перехода представлены в виде правого и левого
полукругов.
ISSN 1028-9763. Математичні машини і системи, 2007, № 3, 4 113
Позиции APRO-сети: { }iii qdp ,= , где { }iiiiii ppMaxpCurppIdd _,_,_,_,_ δϕ= –
множество параметров позиции, содержащее такие элементы: ipId _ – идентификатор позиции,
ip_ϕ – множество допустимых типов меток, ipCur _ – текущее количество меток на позиции,
ipMax _ – максимально допустимое количество меток, ip_δ – локальный счетчик времени
позиции, iq – множество меток, размещенных на данной позиции.
Переходы APRO-сети включают два класса переходов: { }θτ ,=t , где τ – класс простых
переходов, θ – класс операторных переходов. Простой переход описывает множество элементов:
{ }jjj Nx ,=τ , где { }jjjjj LevelIdx τττδτ _,_,_,_ ∆= – множество параметров перехода,
состоящее из таких элементов: jId τ_ – идентификатор перехода, jτδ _ – локальный счетчик
времени перехода, jτ_∆ – период простоя, jLevel τ_ – уровень перехода.
Функциональное ядро перехода: { }jjjjjjj OAN ,,,,, ωγπρ= , где jρ – процедура
активации перехода, jπ – процедура обслуживания перехода, jγ – процедура деактивации
перехода, jω – процедура ожидания, jA – частично упорядоченная последовательность
активностей, jO – частично упорядоченная последовательность выходных меток.
Класс переходов θ обеспечивает композиционные свойства сети и представляет собой
множество
( )θθθθθθ FXETP ,,,,= , (2)
где ( ) ( ){ }appP θθθ L,1= , Na ∈ – множество позиций;
Таблица 1. Графические элементы APRO-сети
Обозначение
Графическое
изображение
Название
Pp ∈
Позиция
τ
Простой переход
θ
Операторный переход
θe
Вход операторного перехода
Tt ∈
θ
θx
Выход операторного перехода
( ) ( ) Fpttp ∈,;, Ребро
M∈µ Метка
ISSN 1028-9763. Математичні машини і системи, 2007, № 3, 4 114
( ) ( ){ }bT θθθ ττ L,1= , Nb∈ , ∅≠θT – непустое множество переходов;
( ) ( ){ }ceeE θθθ L,1= , Nc ∈ , ∅≠θE – непустое множество входов;
( ) ( ){ }dxxX θθθ L,1= , Nd ∈ , ∅≠θX – непустое множество выходов;
( ) ( ) ( ) ( )θθθθθθθθθ XTTEPTTPF ×∪×∪×∪×= – множество ребер.
Таким образом, операторный переход θ содержит APRO-сеть θΦ , определяемую как сеть нижнего
уровня по отношению к сети Φ . Переходы сети θΦ также могут быть операторными переходами,
что позволяет строить вертикально стратифицированные модели с неограниченным количеством
уровней.
Во избежание путаницы, элементы операторного перехода будем отмечать индексом с его
наименованием. Формальное описание произвольной внутренней позиции ( ) θθ Φ∈ip
операторного перехода θ соответствует формальному описанию произвольной позиции верхнего
уровня Φ∈ip . Внутренние переходы ( ) θθτ Φ∈j также имеют идентичное формальное описание
с простыми переходами верхнего уровня Φ∈jτ .
Входы операторного перехода: ( ) ( ) ( ){ }θθθθ µη ,, j
e
jj Ne = ,
где ( ) ( ) ( ) ( ) ( ){ }jjjjθj eLevel∆_eeId_e θθθθ δη _,,_,= – множество параметров входа перехода
θ , включающее такие элементы: ( ) jeId θ_ – идентификатор входа, ( ) jeθδ _ – локальный счетчик
времени, ( ) jeθ_∆ – период простоя, ( ) jLevel_eθ – уровень представления θe .
Ядро входа: ( ) ( ){ }jj
e wN θθθ ρ ,= , где ( ) jθρ – процедура активации входа, ( ) jwθ –
процедура ожидания, θµ – текущая входная метка операторного перехода θ .
Выходы операторного перехода: ( ) ( ) ( ) ( ){ }i
x
i
x
iθi qNοx θθθ ,,= , где
( ) ( ) ( ) ( ) ( ){ }iθiθiii Max_x,Cur_x,_x,Id_xo θθθ ϕ= – множество параметров выхода перехода θ ,
включающее такие элементы: ( )ixId θ_ – идентификатор выхода, ( )ixθϕ _ – множество
допустимых типов меток, ( )ixCur θ_ – текущее количество меток, ( )ixMax θ_ – максимально
допустимое количество меток.
Ядро выхода: ( ) ( ){ }iiN θθ γ= , где ( )iθγ – процедура деактивации выхода, ( )ixqθ –
множество меток на выходе операторного перехода θ .
Ребра сети задают матрицей инцидентности H с элементами
ISSN 1028-9763. Математичні машини і системи, 2007, № 3, 4 115
( )
( )
( )
( ) ( )
∉∉
∈+
∈−
=
−
−
,,,,,0
,,,1
,,,1
,
1
1
FF
F
F
jiji
ji
ji
ji
tptp
tp
tp
tpH
.1
,1
mj
ni
≤≤
≤≤
Метки APRO-сети: { }kkk αλµ ,= , где { }kkkk Id µϕµδµλ _,_,_= – множество
параметров метки, включающее такие элементы: kId µ_ – идентификатор метки, kµδ _ – время
создания метки, kµϕ _ – тип метки, kα – множество атрибутов метки.
Множество глобальных переменных: ( )ΛΨ∆= ,,V , где ∆ – подмножество показателей
продуктивности, Ψ – подмножество показателей реактивности, Λ – подмножество показателей
использования.
3. Алгоритмические аспекты функционирования APRO-сети
Рассмотрим основные аспекты семантики APRO-сети, базирующиеся на процессах, активностях и
событиях. Активности APRO-сети выражают совокупность типичных действий перехода на
заданном уровне описания. При условии одновременного использования операторных и простых
переходов сеть будет содержать активности верхнего уровня и внутренние активности
операторных переходов, образуя двухуровневую структуру активностей. Если операторный
переход нижнего уровня также содержит операторные переходы, то количество уровней
активностей увеличивается на единицу. Таким образом, получаем древовидную структуру
активностей. Логическая последовательность активностей объединяется в процесс. Любой из
процессов, существующих в сети, может входить в процесс более высокого уровня в качестве
субпроцесса.
Будем рассматривать множество активностей A , включающее такие подмножества:
{ }waitdeactivateactivatecomputeA ,,,= . Подмножество compute содержит активности,
выполняющие действия, связанные с обработкой информации во время работы перехода.
Подмножество activate представляет активности, реализующие действия перехода по его
активации, активности подмножества deactivate завершают работу перехода. Активности,
заданные подмножеством wait , отображают действия перехода в режиме ожидания.
Упорядоченная последовательность активностей может образовывать процесс.
Определение 1. Пусть для простого перехода jt задано множество активностей jA и три
произвольных элемента этого множества: jAaaa ∈221 ,, . Множество jA будем называть частично
упорядоченной последовательностью, если для ее элементов задано отношение «p » (« 21 aa p » –
1a равняется или предшествует 2a ) в соответствии со свойствами:
– если 21 aa p и 32 aa p то 31 aa p (транзитивность);
– если 21 aa p и 12 aa p то 21 aa = (асимметричность);
– 11 aa p (рефлексивность).
ISSN 1028-9763. Математичні машини і системи, 2007, № 3, 4 116
Множеству переходов { }mj tttT ,,,,1 LL= поставим в соответствие множество процессов
{ }mj PrPrPr LL ,,,1=Pr и зададим подмножества активностей { }m
jjaactivate
1
:
=
= ,
{ }m
jjccompute
1
:
=
= , { }m
jjddeactivate
1
:
=
= и { }m
jjwwait
1
:
=
= . Тогда процесс jPr перехода jt
можно представить последовательностью активностей jjjjj wdcaPr ppp=: . Процесс jPr
отображает типичный процесс работы перехода, который сначала активируется, выполняет
обработку информации, а потом завершается и переходит в режим ожидания.
Рождение и исчезновение активностей происходит путем свершения событий, любая из
которых представляет собой мгновенное изменение состояния APRO-сети. Будем рассматривать
только события start и stop , обеспечивающие рождение и завершение активностей. Тогда
процесс jPr может быть записан с учетом данных событий:
.........: startwstopdstartdstopcstartcstopastartastopwPr jjjjjjjjj ppppppp=
Совокупный процесс jPr всегда однозначно задает текущее состояние соответствующего
перехода jt . Поэтому в качестве общего признака упорядочения последовательности jPr
выступает время возникновения активностей, входящих в данную последовательность.
На рис. 1 показана структура APRO-сети, состоящей из простого перехода jt , входных
позиций ba pp , и выходных позиций dc pp , .
В соответствии с описанием структуры основными элементами позиций APRO-сети являются
параметры состояния и список активных меток. Простой переход содержит параметры состояния,
процедуры перехода, управляющий процесс и выходную очередь меток. Последовательное
развитие процесса jPr происходит за счет того, что свершение текущего события сопровождается
созданием нового события с новым временем выполнения. Стартовое событие всегда запускает
новую активность посредством выполнения соответствующей процедуры перехода. Структура
логических связей процедур перехода показана на рис. 2.
Рис. 1. Структура простого перехода APRO-сети
ISSN 1028-9763. Математичні машини і системи, 2007, № 3, 4 117
Процедура активации ( )inj µρ обеспечивает выполнение комплекса операций,
соответствующих активности ja , и состоит из процедур Choose, Select и Tіmіng. Процедура Choose
предназначена для выполнения действий, связанных с анализом меток, размещенных на входных
позициях перехода jt . Процедура Select реализует алгоритм проверки метки, выбранной с
помощью процедуры Choose. Одно из важных условий проверки заключается в сохранении
временной целостности модели путем сравнения локального времени перехода и времени
создания метки.
Эту функцию выполняет отдельная процедура Tіmіng. Запуск процедуры ( )inj µρ
происходит в момент завершения активности jw и начала активности ja . Механизм этого
изменения состоит в том, что завершающее событие stopw j . активности jw порождает стартовое
событие starta j . активности ja .
Существуют четыре возможных завершения процедуры ( )inj µρ в зависимости от
результатов анализа входной метки inµ :
1. Если поиск активной метки на входных позициях завершился безрезультатно, то событие
завершения активности ja порождает событие startw j . .
2. Если активная метка inµ найдена процедурой Choose, но значение атрибутов этой метки
не разрешает запустить процедуру обработки ( )inj µπ , то событие завершения активности ja
также порождает событие startw j . .
Рис. 2. Структура процедур ( )inj µρ , ( )inj µπ , ( )outj µγ и jω
ISSN 1028-9763. Математичні машини і системи, 2007, № 3, 4 118
3. Если активная метка inµ найдена процедурой Choose и имеет корректные параметры, то
событие завершения активности ja порождает событие startc j . .
4. Если активная метка inµ найдена процедурой Choose и является транзитной меткой, то
событие завершения активности ja порождает событие startd j . .
Процедура ( )inj µπ реализует совокупность операций, соответствующих активности jc
перехода jt и состоит из процедуры Analyze и множества процедур ( ){ }k
iiB
1=∈ µαα . Запуск этой
процедуры происходит в случае, если метка корректна и может быть обработана в данном
переходе, что подтверждается созданием события startc j . . Процедура Analyze обеспечивает
оценку параметра inµϕ _ текущей метки inµ с целью выбора соответствующей процедуры
( )
inkB µαα ∈ . Работу процедуры Analyze завершает событие stopc j . , порождающее событие
startd j . .
Процедура ( )outj µγ включает операции вывода меток из простого перехода jt . В ее состав
входят процедуры Transmit и Out. Существуют два варианта запуска процедуры ( )outj µγ , каждый
из которых инициируется соответствующим событием startd j . . Процедура Transmіt формирует
параметры и атрибуты выходной метки и размещает их в очереди выходных меток. Процедура Out
выбирает первую в очереди выходную метку outµ и пытается установить ее на соответствующую
выходную позицию. Если метка по тем или иным причинам не установлена на указанной выходной
позиции, то она снова возвращается в очередь выходных меток. При условии пустоты очереди
выходных меток jO работа процедуры ( )outj µγ завершается, о чем свидетельствует событие
stopd j . , свершение которого порождает событие startw j . .
В соответствии с рис. 2 существуют три возможных причины возникновения события
startw j . , запускающего процедуру ожидания jω . Основной составляющей данной процедуры
является процедура Set_idle, устанавливающая действия перехода после завершения полного
цикла обработки информации. Управление частично упорядоченной последовательностью
активностей в рамках перехода выполняет процедура Make_lіst обслуживания
последовательности, входящей в состав ядра jN перехода jt .
Для формирования следующего цикла активности перехода необходимо выбрать способ
продвижения сетевого времени. Этот способ должен быть согласован с обусловленным
механизмом имитационного моделирования сети. Поэтому решение проблемы продвижения
сетевого времени лежит в плоскости практической реализации алгоритмов функционирования
APRO-сети. Формальное описание APRO-сети допускает использование как последовательных, так
и параллельных методов продвижения модельного времени.
ISSN 1028-9763. Математичні машини і системи, 2007, № 3, 4 119
Наиболее полно разработан метод продвижения сетевого времени с помощью управления
частично упорядоченной последовательностью меток, являющийся вариантом подхода, который
базируется на продвижении сетевого времени, управляемого списком событий [9]. Этот вариант
может быть использован для организации вычислительного процесса в мультипроцессорной
вычислительной структуре. Особенность такой структуры состоит в наличии управляющего центра,
обеспечивающего поддержку процедур работы с единой, частично упорядоченной,
последовательностью меток. Следует отметить, что реализация данного подхода для
иерархических сетей вызывает ряд проблем, связанных с осложнениями обслуживания общей
последовательности меток для таких сетей. А именно: использование единого списка значительно
увеличивает его размер и количество сопроводительной информации. Для решения этой
проблемы необходимо обеспечить формирование иерархической последовательности меток, но
такой подход усложняет процессы управления сетью. Данный алгоритм продвижения сетевого
времени также может вызвать зацикливание в случае, если на сети существуют циклические связи
между переходами и время прохождения таких циклов меньше времени срабатывания других
переходов сети. Для преодоления упомянутых недостатков в последнее десятилетие активно
развиваются подходы к построению локальных последовательностей меток, которые могли бы
функционировать без использования глобальных ресурсов при реализации сетевой модели на
мультипроцессорной системе [10].
4. Пример описания APRO-сети
Рассмотрим пример композиционного построения APRO-сетевой модели распределенной
вычислительной системы с использованием операторных переходов (рис. 3).
Объект моделирования представлен простым переходом «distribution», выполняющим
функции распределения вычислительной нагрузки между N узлами, заданными с помощью
Рис. 3. Модель распределенной вычислительной системы
ISSN 1028-9763. Математичні машини і системи, 2007, № 3, 4 120
множества операторных переходов { }Niinode ≤≤1 . Формирование общего результата из
частичных результатов вычислений в узлах выполняет простой переход «collection». Переходы
«distribution» и «collection» реализуют обмен данными между узлами путем использования связей
через позиции «straight» и «back». В функции перехода «collection» также входит завершение
процесса моделирования и установление состояния «stop».
Структурно APRO-сеть ( )VMFTPd ,,,,=Φ включает такие элементы:
{ }4221 ,, += NpppP L ,
{ } { }{ }111 ,_,,1,, µµδNdatastartp = ,
{ }{ },,0,1,0,,12 ∅= datainputp …, { }{ },,0,1,0,,2 ∅= dataNinputp N
{ }{ },,0,1,0,,13 ∅= dataoutputp …, { }{ },,0,1,0,,12 ∅=+ dataNoutputp N
{ }{ },,0,,0,,22 ∅=+ Ndatastraightp N { }{ },,0,,0,,32 ∅=+ Ndatastopp N
{ }{ },,0,,0,,42 ∅=+ Ndatabackp N
{ }NT θθττ L,,, 121= ,
{ }{ }11 ,0,0,0, Nondistributi=τ , { }{ }22 ,0,0,0, Ncollection=τ .
Операторные переходы ( )
iiiii
FXETPi θθθθθθ ,,,,= , Ni ≤≤1 содержат следующие элементы:
( ) ( ){ }
21
,
iii
ppP θθθ = , ( ) { }{ },,0,1,0,,
1
∅= dataCPUp
iθ ( ) { }{ },,0,1,0,,
2
∅= datamemoryp
iθ
( ) ( ){ }
21
,
iii
T θθθ ττ= , ( ) { } ( ){ }
11
,1,0,0,1
ii
Ncontr θθτ = , ( ) { } ( ){ }
22
,1,0,0,2
ii
Ncontr θθτ = ,
( ){ }
1ii
eE θθ = , ( ) { } ( ){ }∅= ,,1,10,0,0,0,
11
e
ii
Nqueueinpute θθ ,
( ){ }
1ii
xX θθ = , ( ) { } ( ){ }∅= ,,10,0,,
11
x
ii
Ndataqueueoutputx θθ ,
( ) ( ) ( ) ( )
( )
( )
−
−−=
1110
0111
2
1
1211
i
i
iiii
i
xppe
F
θ
θ
θθθθ
θ
τ
τ ,
−
−
−−−
−−
=
++++
00011000
00000110
11110100
10101011
1
2
1
423222122321
L
LLLLLLLLLL
L
L
L
L
N
NNNNN pppppppp
F
θ
θ
τ
τ
.
Предложенная APRO-сетевая модель описывает дискретную распределенную систему
обработки данных. Особенность данного подхода состоит в возможности имитационного
ISSN 1028-9763. Математичні машини і системи, 2007, № 3, 4 121
моделирования систем с реальной рабочей нагрузкой, что обусловлено использованием
произвольных структур данных в качестве атрибутов меток и реализацией произвольных
алгоритмов обработки этих данных с помощью процедур обработки переходов. APRO-сетевое
описание является основой входного языка задания параметров моделей для моделирующего
комплекса APRO_Simulator. С помощью формирования массивов статистических данных в
соответствии с показателями, объединенными во множество глобальных переменных V , данный
комплекс позволяет производить анализ различных характеристик сложных дискретных систем как
на этапе их разработки, так и на этапе эксплуатации.
5. Выводы
Стремительное усложнение дискретных систем стимулирует поиск новых подходов к созданию их
формальных описаний, лежащих в основе построения различного рода моделей. С одной стороны,
такие описания должны обладать высокой степенью абстрагирования с целью упрощения модели,
а, с другой стороны, они должны обладать высокой адекватностью описания объектов
моделирования для обеспечения корректности полученных результатов. С учетом данных
требований разработан инструмент формального описания сложных дискретных систем – APRO-
сети.
Научная новизна предлагаемой версии сетевого формального описания сложных
дискретных систем состоит в наличии совокупности таких свойств:
– гибкого механизма иерархического представления моделей;
– возможности описания параллельно функционирующих и асинхронно взаимодействующих
процессов с использованием современных подходов к продвижению модельного времени;
– возможности построения имитационных моделей с использованием реальной рабочей
нагрузки.
Практическая ценность работы обусловлена построением программного комплекса,
представляющего собой среду моделирования, в которой входной язык для описания моделей
построен с использованием синтаксиса и семантических правил APRO-сетей.
СПИСОК ЛИТЕРАТУРЫ
1. Rosenberg R.M. Analytical Dynamics of Discrete Systems. – New York: Plenum Pub. Corp., 1977. – 424 p.
2. Робертс Ф.С. Дискретные математические модели с приложениями к социальным, биологическим и
экологическим задачам. – М.: Наука, 1986. – 496 с.
3. Cassandras C.G., Lafortune S. Introduction to Discrete Event Systems. – New York: Springer, 2006. – 904 p.
4. Баранов С.И. Синтез микропрограммных автоматов. – Л.: Энергия, 1979. – 232 с.
5. Бусленко Н.П. Моделирование сложных систем.– М.: Наука, 1978. – 400 с.
6. Гнеденко Б.В., Коваленко И.Н. Введение в теорию массового обслуживания. – М.: Наука, 1987.– 336 с.
7. Питерсон Дж. Теория сетей Петри и моделирование систем. – М.: Мир, 1984. – 264 с.
8. Нестеренко Б.Б., Новотарский М.А. Мультипроцессорные системы. − К.: Институт математики АН Украины,
1995. − 408 с.
9. Нестеренко Б.Б. Моделювання паралельних процесів: від мереж Петрі до нейронних мереж / Б.Б.
Нестеренко, М.А. Новотарський. – К.: 2004. – 66 с. (Препринт / НАН України. Ін-т математики; 2004-2).
10. Fujimoto R.M. Parallel Discrete Event Simulation // Communication of the ACM. – 1990. – Vol. 33, N 10. – P. 30–
53.
Стаття надійшла до редакції 11.05.2007
|