Description of parallelism in algorithms of information management systems using algebraic apparatus
Prombles in programming 2013; 3: 13-21
Збережено в:
| Дата: | 2025 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
PROBLEMS IN PROGRAMMING
2025
|
| Теми: | |
| Онлайн доступ: | https://pp.isofts.kiev.ua/index.php/ojs1/article/view/749 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Problems in programming |
| Завантажити файл: |  |
Репозитарії
Problems in programming| id |
pp_isofts_kiev_ua-article-749 |
|---|---|
| record_format |
ojs |
| resource_txt_mv |
ppisoftskievua/49/46e8cf24bf048e39c30b777dd5df0449.pdf |
| spelling |
pp_isofts_kiev_ua-article-7492025-06-21T15:30:49Z Description of parallelism in algorithms of information management systems using algebraic apparatus Описание параллелизма в алгоритмах информационно-управляющих систем средствами алгебраического аппарата Akulovsky, V.G. Doroshenko, A.Yu. UDC 519.681 УДК 519.681 Prombles in programming 2013; 3: 13-21 Показана возможность описания в рамках алгебры алгоритмов с данными параллельных алгоритмов для класса информационно-управляющих систем. Введены средства синхронизации параллельно выполняемых ветвей алгоритма и продемонстрирована возможность построения производных средств синхронизации на основе введенных.Prombles in programming 2013; 3: 13-21 PROBLEMS IN PROGRAMMING ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ ПРОБЛЕМИ ПРОГРАМУВАННЯ 2025-06-21 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/749 PROBLEMS IN PROGRAMMING; No 3 (2013); 13-21 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 3 (2013); 13-21 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 3 (2013); 13-21 1727-4907 ru https://pp.isofts.kiev.ua/index.php/ojs1/article/view/749/801 Copyright (c) 2025 PROBLEMS IN PROGRAMMING |
| institution |
Problems in programming |
| baseUrl_str |
https://pp.isofts.kiev.ua/index.php/ojs1/oai |
| datestamp_date |
2025-06-21T15:30:49Z |
| collection |
OJS |
| language |
Russian |
| topic |
UDC 519.681 |
| spellingShingle |
UDC 519.681 Akulovsky, V.G. Doroshenko, A.Yu. Description of parallelism in algorithms of information management systems using algebraic apparatus |
| topic_facet |
UDC 519.681 УДК 519.681 |
| format |
Article |
| author |
Akulovsky, V.G. Doroshenko, A.Yu. |
| author_facet |
Akulovsky, V.G. Doroshenko, A.Yu. |
| author_sort |
Akulovsky, V.G. |
| title |
Description of parallelism in algorithms of information management systems using algebraic apparatus |
| title_short |
Description of parallelism in algorithms of information management systems using algebraic apparatus |
| title_full |
Description of parallelism in algorithms of information management systems using algebraic apparatus |
| title_fullStr |
Description of parallelism in algorithms of information management systems using algebraic apparatus |
| title_full_unstemmed |
Description of parallelism in algorithms of information management systems using algebraic apparatus |
| title_sort |
description of parallelism in algorithms of information management systems using algebraic apparatus |
| title_alt |
Описание параллелизма в алгоритмах информационно-управляющих систем средствами алгебраического аппарата |
| description |
Prombles in programming 2013; 3: 13-21 |
| publisher |
PROBLEMS IN PROGRAMMING |
| publishDate |
2025 |
| url |
https://pp.isofts.kiev.ua/index.php/ojs1/article/view/749 |
| work_keys_str_mv |
AT akulovskyvg descriptionofparallelisminalgorithmsofinformationmanagementsystemsusingalgebraicapparatus AT doroshenkoayu descriptionofparallelisminalgorithmsofinformationmanagementsystemsusingalgebraicapparatus AT akulovskyvg opisanieparallelizmavalgoritmahinformacionnoupravlâûŝihsistemsredstvamialgebraičeskogoapparata AT doroshenkoayu opisanieparallelizmavalgoritmahinformacionnoupravlâûŝihsistemsredstvamialgebraičeskogoapparata |
| first_indexed |
2025-07-17T09:48:18Z |
| last_indexed |
2025-07-17T09:48:18Z |
| _version_ |
1850409880039456768 |
| fulltext |
Теоретичні та методологічні основи програмування
© В.Г. Акуловский, А.Е. Дорошенко, 2013
ISSN 1727-4907. Проблеми програмування. 2013. № 3 13
УДК 519.681
В.Г. Акуловский, А.Е. Дорошенко
ОПИСАНИЕ ПАРАЛЛЕЛИЗМА В АЛГОРИТМАХ
ИНФОРМАЦИОННО-УПРАВЛЯЮЩИХ СИСТЕМ
СРЕДСТВАМИ АЛГЕБРАИЧЕСКОГО АППАРАТА
Показана возможность описания в рамках алгебры алгоритмов с данными параллельных алгоритмов
для класса информационно-управляющих систем. Введены средства синхронизации параллельно вы-
полняемых ветвей алгоритма и продемонстрирована возможность построения производных средств
синхронизации на основе введенных.
Введение
Широко распространенными в раз-
личных областях человеческой деятельно-
сти являются информационно-управляю-
щие системы (ИУС). Об этих системах,
исходя из многочисленных публикаций
(например, [1]) и не взирая на различные
классификации программных систем, мож-
но сказать, что они сочетают функции ав-
томатизированных систем управления
(АСУ) с функциями систем автоматиче-
ского управления (САУ). В силу специфи-
ки выполняемых функций, системы данно-
го класса обычно реализуются в виде мно-
гомашинных систем, часто иерархических,
подсистемы которых часто функциониру-
ют в многозадачном режиме.
Вопросы, связанные с описанием
алгоритмов данного класса систем, в част-
ности, связанные с описанием паралле-
лизма, в рамках алгебро-алгоритмического
подхода, рассмотрены недостаточно. Учи-
тывая важность роли, которую играют
ИУС в современном мире, рассмотрение
данных вопросов является актуальной за-
дачей.
Для решения данной задачи вос-
пользуемся алгебраическим аппаратом,
который построен в результате модифика-
ции известной модели ЭВМ Глушкова.
Модификация заключается в до-
полнении упомянутой модели внешней
средой (ВС), которая состоит из программ-
мной (ПС) и аппаратной (АС) составляю-
щих.
Первая обеспечивает взаимодей-
ствие между моделями, функционирую-
щими в различных ВС (многомашинная
организация), и между задачами в рамках
одной ВС (квазипараллельная, многоза-
дачная организация). Вторая – представля-
ет собой память и внешние устройства
(ВУ), включающие как устройства ввода-
вывода (УВВ), так и устройства связи с
объектом управления (УСО), и интерпре-
тируется как данные, формализованные
следующим образом [2].
Определение 1. Данными называ-
ется пара ЗND , , где N – носитель дан-
ных, З – кортеж значений, носителем ко-
торых является N . На каждом шаге вы-
числительного процесса носитель содер-
жит (хранит) некоторый (текущий) кортеж
значений данных, в частности, эти значе-
ния могут быть неопределенными.
С учетом определения 1, АС рас-
сматривается как множество данных
}}{},{{ П ВУAС DDD , где носитель ПD – па-
мять, а носитель
ВУD – ВУ. Эти данные,
характеризующиеся в каждый момент
времени некоторым множеством значений,
которые изменяются в ходе вычислитель-
ного процесса.
Такая модификация модели ЭВМ
позволила ввести Д-операторы вида
)()( DOD со специфицированными дан-
ными D и D , которые они обрабатыва-
ют, т. е. анализируют и преобразуют, из-
меняя их значения. Частным случаем
является Д-оператор )()( DZD , который
не изменяет данные, называется тожде-
ственным и в дальнейшем часто записы-
вается в виде Z.
Теоретичні та методологічні основи програмування
14
Заметим, что значения специфици-
руемых данных в общем случае изменяют-
ся в ходе вычислительного процесса, а на
некоторых его этапах могут быть не опре-
делены. Отсюда следует, что специфици-
руются, фактически, носители данных. По-
этому под теоретико-множественными
операциями, определенными на множе-
ствах данных, понимаются операции над
их носителями.
Специфицируемые данные, с уче-
том сделанного замечания, такие, что
AСDD и AСDD .
По поводу специфицируемых дан-
ных в [2] введено определение.
Определение 2. Данные, специфи-
цируемые на входе и выходе Д-оператора
)()( DOD , будем называть: D – входными
или обрабатываемыми, D – выходными
или продуцируемыми. Для множеств спе-
цифицируемых данных допустимо как
соотношение )( DD (в частности,
DD и DD ), при котором множе-
ство данных )( DDDD изменяет-
ся в результате обработки, так и
)( DD , когда множество данных
D остается неизменным. Специфициро-
ванные данные изменяются в результате
и только в результате их обработки
Д-операторами.
На основе модифицированной мо-
дели ЭВМ в работах [2–4] предложена си-
стема алгоритмических алгебр (САА/Д),
представляющая собой трехосновную ал-
гебраическую систему ,,, DLU , ос-
новами которой являются множество
Д-операторов U, множество логических
условий L и множество данных D, а – её
сигнатура, состоящая из 1 – операций,
принимающих значения на множестве U,
2 – логических операций, принимающих
значения на множестве L, 3 – операций,
принимающих значения на множестве
данных D.
Из всего многообразия операций
САА/Д, определенных на множестве
Д-операторов, в данной работе воспользу-
емся следующими:
– композиция Д-операторов
)()(*)()( 111 iiiiii DODDOD (операция
обозначается “*”) означает последова-
тельное выполнение сначала Д-оператора
)()( iii DOD и затем Д-оператора
)()( 111 iii DOD ;
– р-итерация })(){()()( π DODPD
состоит в вычислении предиката
)()( π PD , где πD – вектор заданного от-
ношения, и проверке логического усло-
вия }0,1{α , продуцируемого предика-
том. Если истинно, выполняется Д-
оператор )()( DOD и вновь вычисляется
предикат и проверяется условие . Цик-
лический процесс, состоящий в проверке
условия и выполнении Д-оператора,
осуществляется до тех пор, пока условие
1 в противном случае операция
р-итерации завершается.
В частном случае данная операция,
записана в виде
})(){(1 DOD , (1)
где 1 – тождественно истинное условие,
реализует “бесконечный” цикл.
Представление любого исходного
Д-оператора из U через образующие эле-
менты системы ,,, DLU называется
регулярной схемой данного Д-оператора
(РСД). В частном случае, когда использу-
ется единственная операция – композиция,
такое представление Д-оператора называ-
ется его композиционной схемой (КС).
Описанию параллелизма ИУС в
рамках предложенного алгебраического
аппарата и посвящена данная работа.
Описание параллелизма в
алгоритмах ИУС
Прежде чем начать рассмотрение
основного вопроса, определим алгоритм
ИУС. Для этого сначала определим алго-
ритм в общем случае.
Определение 3. Алгоритмом на-
зывается Д-оператор )()( DAD , на входе
которого специфицированы все необходи-
Теоретичні та методологічні основи програмування
15
мые для решения некоторой задачи гло-
бальные данные, а на выходе – все резуль-
тирующие глобальные данные.
При нисходящей стратегии проек-
тирования [5] данные D и D детализуют-
ся, а алгоритм декомпозируется и записы-
вается в виде РСД или КС. В последнем
случае это выглядит как
),()(*...*)()(*
*)()()(A)(
222
111
kkk DODDOD
DODDD
(2)
где kDDD ...1 , kDDD ...1 ,
)()(),...,()( 111 kkk DODDOD – производные
Д-операторы, полученные в результате де-
композиции. На следующем шаге деком-
позируются производные Д-операторы и
детализуются специфицированные у них
данные. Процесс продолжается до дости-
жения требуемого уровня подробности
описания алгоритма.
При этом производные Д-операто-
ры взаимодействуют в процессе обработки
данных. То есть, обработка множества
данных, начатая некоторым Д-операто-
ром )()( iii DOD , может продолжаться од-
ним или несколькими следующими за ним
Д-операторами.
Учитывая это введем понятия связи
между Д-операторами.
Определение 4. В РСД и КС Д-
операторы )()( iii DOD и )()( jjj DOD (j>i)
назовем информационно связанными (в
дальнейшем связанными), если для специ-
фицированных у них данных выполняется
соотношение ji DD , в противном слу-
чае эти Д-операторы не связаны. Данные
)( jiji DDD назовем связывающими и на
выходе i-го Д-оператора обозначим ji D
,
на входе j-го ji D
.
Известно, что управляющие систе-
мы, в силу своей специфики, обычно
функционируют неограниченное время
(см., например, [6]), т. е. их работа пре-
кращается только в случае отключения пи-
тания. Алгоритмы такого рода будем
называть непрерывными и, используя (1),
представим в виде РСД:
),()(1*)()(=
=)()(
тттппп DODDOD
DAD
(3)
где 1 – тождественно истинное логическое
условие, пO – выполняет подготовитель-
ные (стартовые) операции, тO – “тело” ал-
горитма.
С учетом (3), алгоритм ИУС
определим следующим образом.
Определение 5. Алгоритм ИУС со-
стоит из двух (или более) информационно
связанных подсистем, реализующихся в
виде непрерывного алгоритма и выполня-
ются параллельно (квазипараллельно) и
асинхронно. Под информационной связью
понимается двусторонняя связь, т. е. неко-
торое подмножество данных, продуцируе-
мых одной подсистемой, используется
второй и наоборот. По крайней мере, одна
из подсистем взаимодействует с УВВ, а
одна с УСО. Любая из подсистем в свою
очередь может состоять из параллельно
(квазипараллельно) и асинхронно выпол-
няемых подсистем (подзадач, процессов).
Дальше будем рассматривать, вари-
ант ИУС, когда она состоит из двух подси-
стем, каждая из которых функционирует в
собственной программно-аппаратной сре-
де (двухмашинный случай).
Для случаев, когда подсистемы
ИУС функционирует в различных про-
граммно-аппаратных средах, в сигнатуру
алгебры включим операцию асинхронная
дизъюнкция Д-операторов
)()( iii DOD )()( jjj DOD ,
состоящую в параллельном асинхронном
выполнении Д-операторов.
Архитектуру системы, исходя из
определения 5, используя (3) и введенную
операцию, опишем в виде следующей
РСД:
*)(П)((=)()( п_п_ АСУАСУАСУ DDDИУСD
))()(1* АСУАСУ DАСУD
п_ п_(( )П ( )*САУ САУ САУD D
1 ( ) ( )),САУ САУD САУ D
Теоретичні та методологічні основи програмування
16
где
САУСАУАСУАСУ DDDDD п_п_= ,
САУСАУАСУАСУ DDDDD п_п_= .
Чтобы отобразить двухсторонние
информационные связи между подсисте-
мами, ограничимся подсистемами АСУ и
САУ, которые, в соответствии с определе-
нием 4, запишем в виде следующего фраг-
мента алгоритма:
1 ( , ) ( ))САУ АСУ АСУ АСУ АСУ САУD D АСУ D , D
1 ( , ) ( , ).АСУ САУ САУ САУ САУ АСУD D САУ D D
Однако, полученная схема содер-
жит противоречие, так как соотношения
САУАСУ DD и САУАСУ DD не
выполняются из-за того, что подсистемы
функционируют в разных ВС.
Для того, чтобы устранить возник-
шее противоречие и решить проблему
синхронизации, позаимствуем идею син-
хронизации в работе [7] и модернизируем
её следующим образом. Полагая, что ВС
предоставляет необходимые сервисы,
построим механизм передачи сообщений
посредством следующих элементарных
Д-операторов:
– контрольная точка )()( STD
, где
D
– передаваемые данные, S – синхрони-
затор, которому эти данные передаются;
– синхронизатор )a()(
D
SD
такой,
что }{1)a()( ZSD
D
пока D
и
)a()a()(
DD
ZSD
в противном случае, где
Z – тождественный Д-оператор,
D
a – ука-
затель на полученные данные.
Неформально говоря, синхрониза-
тор задерживает вычислительный процесс,
до момента поступления связывающих
данных и передает адрес полученных дан-
ных следующему за ним Д-оператору по-
сле их поступления.
Введенные средства синхронизации
наряду с решением своей основной задачи
устраняют возникшее противоречие, путем
дополнения связывающих данных из
определения 4 передаваемыми.
Однако, при попытке их использо-
вания
*)a()((1*
АСУСАУ DАСУАСУСАУ SD
*()(* )DАСУD АСУАСУ
*( ) ( ))АСУ CАУ АСУD T САУ
1 (( ) (a )*
AСУ CАУ
АСУ CАУ САУ D
D S
*)(* )САУ(DD САУСАУ
)),()*( АСУTD САУАСУСАУ
сталкиваемся с ограничением, вызванным
тем, что подсистемы АСУ и САУ, в соот-
ветствии с определением 5, имеют двух-
сторонние связи. Из приведенной схемы
видно, что параллельное выполнение под-
систем невозможно, так как в результате
взаимной синхронизации каждая из подси-
стем ожидает выполнения другой, что по-
рождает “клинч”.
Ограничение снимается в результа-
те декомпозиции алгоритмов подсистем.
Поскольку вместе с декомпозицией осу-
ществляется детализация данных, в том
числе и связывающих, то при достаточной
степени декомпозиции для каждой из под-
систем будет получена такая детальность
описания, при которой любой из входящих
в это описание Д-операторов, имеет толь-
ко односторонние связи. С достижением
такого этапа проектирования средства
синхронизации могут вводиться в описа-
ние алгоритма, что изобразим в виде сле-
дующим фрагментом схемы алгоритма:
1 1
1 1
1
1
1
...*( ) (a )*
*( ) ( )*...
......................................................
...*( ) ( )
*( ) ( )*...,
c p САУ АСУc p
p p
c c
c p p
САУ АСУ p D
s s s
АСУ p АСУ
p p p
САУ c САУ
САУ АСУ c
D S
D АСУ D
D CАУ D *
D T S
где верхний левый индекс – номер шага
(уровня) декомпозиции алгоритма.
Достигнутая степень параллелизма
алгоритма, как правило, окажется недоста-
точной, так как подсистемы часто функци-
онируют в многозадачной ПС.
Теоретичні та методологічні основи програмування
17
Рассмотрим возможность распарал-
леливания для данного случая, т. е. воз-
можности распараллеливания алгоритмов
подсистем на некотором этапе их разра-
ботки. При этом будем учитывать, что для
параллельно и асинхронно выполняемых
Д-операторов ни продолжительность вы-
полнения каждого из них, ни очередность
начала и завершения этих Д-операторов не
определены.
Рассмотрение начнем с ограниче-
ний на параллельное выполнение Д-опера-
торов )()(*)()( 111 iiiiii DODDOD , входя-
щих в КС (2). Заметим при этом, что опре-
деление 4, распространяется и на этот слу-
чай, а 1ii D – связывающие данные.
Первым фактором, ограничиваю-
щим параллельное выполнение, являются
информационные связи, определяющие
жесткий порядок обработки данных, так
как при наличии такой связи Д-оператор
)()( 111 iii DOD продолжает обработку
данных, начатую Д-оператором
)()( iii DOD , и, таким образом, параллель-
ное их выполнение невозможно.
Для того чтобы учесть второй фак-
тор, введем следующее определение.
Определение 6. Д-операторы
)()(*)()( 111 iiiiii DODDOD имеют между
собой обратные связи, если выполняется
соотношение 1ii DD , что приводит
к изменению значений данных, специфи-
цированных на входе )()( iii DOD , соотно-
шение 1ii DD , выполнение которо-
го приводит к изменению значений дан-
ных iD , продуцируемых Д-оператором
)()( iii DOD .
Второй фактор вытекает из опреде-
ления 6, так как обратные связи обуслов-
ливают влияние одного Д-оператора на
результаты выполнения другого.
Для того чтобы рассмотреть третий
фактор вспомним, что в качестве носите-
лей данных могут выступать ВУ. Учиты-
вая это вводимые и выводимые данные
определим следующим образом, полагая,
что в нашем распоряжении имеется неко-
торые множества ВУ R и W.
Определение 7. Данные, носителем
которых являются некоторое ВУ RRi , с
которого хранимые значения переносятся
(копируются) в память, будем обозначать
R
iD и называть вводимыми, и некоторое
ВУ WWi , в которое хранимые значения
переносятся (копируются) из памяти, – W
iD
и выводимыми. Вводимые и выводимые
данные специфицируются, соответственно,
на входе и выходе произвольного Д-опера-
тора. Множества R
iD и\или W
iD могут быть
пустыми, т. е. вводимые и\или выводимые
данные могут отсутствовать.
При наличии, в соответствии с
определением 7, спецификаций вводимых
и выводимых данных, Д-оператор, очевид-
но, осуществляет операции ввода-вывода.
Это обусловливает наличие третьего фак-
тора, которым является строго заданная в
алгоритме последовательность операций
ввода-вывода. Асинхронное выполнение
Д-операторов, может привести к наруше-
нию этой последовательности. Заметим,
что в общем случае для произвольного ал-
горитма существует некоторое множество
корректных (допустимых) последователь-
ностей этих операций.
Будем полагать, что при параллель-
ном выполнении Д-операторов коррект-
ность последовательности операций ввода-
вывода в некоторых случаях будет сохра-
няться, а во многих случаях обеспечивать-
ся средствами синхронизации параллель-
ных процессов (средства синхронизации
будут ниже рассмотрены). Кроме того бу-
дем полагать, что существует возможность
проверки такой корректности, которая, в
связи с отсутствием формализации, реали-
зуется “вручную”.
Учитывая приведенные факторы,
определим условия, при котором возмож-
но параллельное выполнение Д-опера-
торов. Для этого введем операцию асин-
хронного параллельного выполнения Д-
операторов в многозадачном режиме в ви-
де .
Определение 8. Первым условием,
необходимым для параллельного выпол-
нения Д-операторов
Теоретичні та методологічні основи програмування
18
)()()()( 111 iiiiii DODDOD ,
является то, что в результате такого их вы-
полнения значения всех обрабатываемых
данных iD , iD , 1iD , 1iD , должны пол-
ностью совпадать со значениями тех же
данных, полученных в результате их по-
следовательной обработки композицией Д-
операторов )()(*)()( 111 iiiiii DODDOD .
Второе условие – допустимая последова-
тельность операций ввода-вывода при па-
раллельном выполнении Д-операторов.
Теперь докажем возможность па-
раллельного выполнения Д-операторов,
предварив это доказательство следую-
щей леммой.
Лемма. В композиции Д-операто-
ров )()(*)()( 111 iiiiii DODDOD , если
они не связаны и не имеют обратных свя-
зей, то результатом её выполнения явля-
ются значения данных iD , iD и 1iD ,
1iD , полученные после выполнения соот-
ветствующего Д-оператора ( iO и 1iO ) и
только этого Д-оператора.
Доказательство основывается на
определениях 6 и 7.
Результатом выполнения компози-
ции Д-операторов являются:
– значения данных iD , … , в силу
1i iD D ;
– значения данных iD , полученные
после выполнения iO и только iO , так как
эти значения не изменятся в результате
выполнения 1iO , в силу;
– значения данных 1iD , получен-
ные после выполнения 1iO и только 1iO ,
так как на эти значения, не зависят от ре-
зультатов выполнения iO , в силу
1ii DD ;
– значения данных iD и 1iD , кото-
рые, в соответствии с определением 2, из-
менятся или остаются неизменными в ре-
зультате выполнения Д-операторов, соот-
ветственно, iO и 1iO , но изменениям в
результате выполнения, соответственно,
1iO и iO не подвергаются в силу
1ii DD и ii DD 1 .
Лемма доказана.
Теорема. В КС два любых после-
довательно выполняющихся Д-оператора
могут выполняться параллельно
)()()()( 111 iiiiii DODDOD при тех усло-
виях, что эти Д-операторы не связаны, не
имеют обратных связей и последователь-
ность операций ввода-вывода, если они
имеют место, остается допустимой.
Доказательство основывается на
определениях 6 и 7.
При любой последовательности за-
пуска и завершения (последовательности
выполнения) Д-операторов
)()()()( 111 iiiiii DODDOD
результатом их параллельного выполнения
будут:
– значения данных iD и 1iD , про-
дуцируемые, соответственно, iO и 1iO ,
так как с одной стороны полученные зна-
чения не изменятся в результате выполне-
ния, соответственно, 1iO и iO , поскольку
ii DD 1 . С другой – значения дан-
ных iD и 1iD не влияют на выполнение
1iO и iO , поскольку 1ii DD и
ii DD 1 ;
– значения данных iD и 1iD , ко-
торые, в соответствии с определением
2, могут измениться или остаться
неизменными в результате выполнения,
соответственно iO и 1iO , но в результа-
те выполнения, соответственно, 1iO и iO
не изменятся, поскольку 1ii DD и
ii DD 1 .
Таким образом, результаты парал-
лельного выполнения Д-операторов
)()( iii DOD и )()( 111 iii DOD совпадают
с результатами их последовательного
выполнения, полученными в лемме, что
удовлетворяет первое условие из опре-
деления 8.
Если операции ввода-вывода от-
сутствуют или в результате проверки
Теоретичні та методологічні основи програмування
19
выяснилось, что последовательность этих
операций допустима, или в результате
синхронизации этих операций была обес-
печена такая последовательность, то, в
соответ-
ствии с определением 8, выполняется вто-
рое условие, необходимое для параллель-
ного выполнения Д-операторов.
Теорема доказана.
Следствие 1. Полученный резуль-
тат может быть обобщен на случай более
двух Д-операторов. Если условия теоремы
распространяются на композицию из трех
или более Д-операторов, то все они могут
выполняться параллельно.
Следствие 2. Полученный резуль-
тат может быть обобщен на случай после-
довательности Д-операторов
...*)()(*)()( 111 jjjjjj DODDOD
),()(*... ppp DOD
поскольку в работе [8] показана возмож-
ность объединения Д-операторов. Если в
результате объединения будет получен
Д-оператор
),()(*...*)()()()( pppjjj DODDODDOD
который удовлетворяет условиям теоре-
мы, то указанную последовательность
Д-операторов, очевидно, можно выпол-
нять параллельно как с Д-операторами,
так и с другими последовательностями
Д-операторов.
Из следствий к теореме видно, что
связанные и имеющие обратные связи Д-
операторы, которые не могут выполняться
параллельно, могут входить в параллельно
выполняемые последовательности Д-опе-
раторов. При этом число параллельно вы-
полняемых Д-операторов и их последова-
тельностей ограничивается только наличи-
ем связей между ними.
Очевидно, что и в рассматривае-
мом случае для распараллеливания алго-
ритма нужны средства синхронизации,
которые введем как частный случай вы-
шерассмотренных.
Синхронизатор – это элементарный
Д-оператор )()( S (где D
) такой,
что }{)()( ZS , где – условие
синхронизации истинное в исходном со-
стоянии, Z – тождественный Д-оператор. С
синхронизатором ассоциирована кон-
трольная точка – элементарный Д-опера-
тор )()( ST , где S – ассоциированный с
этой контрольной точкой синхронизатор.
При прохождении контрольной точки Д-
оператор оповещает об этом ВС, которая
передает ложное значение логического
условия синхронизатору. Синхрониза-
тор, реализующий операцию р-итерации,
получив ложное значение логического
условия, прерывает циклирование. Син-
хронизатор может быть ассоциирован с
несколькими контрольными точками
)()(),...,()( 1 ipi STST , в этом случае он
записывается в виде )()( ,...,1 ipS , а цик-
лирование прекращается после прохож-
дения всех контрольных точек.
Неформально говоря, синхрониза-
тор задерживает вычислительный процесс,
до момента прохождения вычислительным
процессом контрольной точки или не-
скольких контрольных точек.
Отметим, что на введенные сред-
ства накладывается ограничение на взаим-
ную синхронизацию аналогичное выше-
описанному, которое аналогично и пре-
одолевается.
Очевидно, что ограничения на ис-
пользование средств синхронизации при-
веденным случаем не исчерпываются.
Учитывая разнообразие архитектур
ИУС и специфичность решаемых ими за-
дач продемонстрируем возможность по-
строения производных средств синхрони-
зации.
Композиции Д-операторов
)()()()(*)()( 1 jjij TSSST
и
1( ) ( )*( ) ( ) ( ) ( , )i i j jS T S ST S
порождают производные средства синхро-
низации (производные Д-операторы), поз-
воляющие подтвердить факт получения
информации синхронизатором iS о про-
хождении контрольной точки jT путем
задержки вычислительный процесс в этой
контрольной точке, посредством синхро-
Теоретичні та методологічні основи програмування
20
низатора 1jS , до поступления такого под-
тверждения. Отметим, что возможности
построения производных средств синхро-
низации, рассмотренным случаем не ис-
черпываются.
Решив задачу распараллеливания
в общем виде, сделаем некоторые уточне-
ния, для чего, с учетом определений 2 и 7,
введем следующее определение.
Определение 9. Вводимые
rR DDD R и выводимые wW DDD W
данные делятся на глобальные
GWR DDD )( и локальные Lwr DDD )( .
Глобальные в КС специфицируются на
входе и выходе как исходного, так и
любого производного Д-оператора. Ло-
кальные Lw
i
r
i DDD , , специфицируются
только на входе и выходе производных
Д-операторов.
КС, с учетом введенного определе-
ния, будет записана в виде:
( , ) ( , )=
R W
D D O D D
...*,,),,( 1111111 )DDD(ODDD wWrR
).,,(),,(*... w
k
W
kkk
r
k
R
kk DDDODDD
Такая форма записи усложняет
процесс описания алгоритма. Однако, при
некоторой громоздкости, она обеспечивает
возможность синхронизации операций
ввода-вывода и контроль допустимости их
последовательности, что является необхо-
димым условием для распараллеливания
алгоритма. Кроме того, спецификация
вводимых и выводимых данных является
необходимой при детальном описании ал-
горитма.
Задачи распараллеливания и син-
хронизации подсистем и выполнения Д-
операторов, входящих в КС, решается
совместно. При этом как в первом, так и во
втором случае выбор момента введения
средств синхронизации в описание алго-
ритма влияет на гранулярность паралле-
лизма. Чем на более позднем этапе разра-
ботки это выполняется, тем большая мел-
козернистость параллелизма обеспечива-
ется.
Заключение
Показана возможность описания в
рамках алгебры алгоритмов с данными
параллельных алгоритмов для класса ин-
формационно-управляющих систем. Рас-
смотрены возможности распараллелива-
ния, как подсистем, так и фрагментов ал-
горитмов внутри подсистем. Первый слу-
чай рассмотрен для двухмашинной, вто-
рой для многозадачной реализации. Для
обоих случаев введены средства синхро-
низации параллельно выполняемых вет-
вей алгоритма.
Отметим, что передача сообщений
– наиболее общее средство синхрониза-
ции, остальные – являются её частными
случаями. При этом передача сообщений
может использоваться не только в том
случае, когда подсистемы функционируют
в различных ВС, а и в случае многозадач-
ной реализации в рамках одной ВС.
Продемонстрирована возможность
построения производных средств синхро-
низации.
Рассмотрение ИУС с различной ар-
хитектурой и разработка средств синхро-
низации, ориентированных на специфику
реализации таких систем, является бли-
жайшей перспективой развития получен-
ных результатов. Вопросы, связанные с
оптимизацией процесс распараллеливания
при ограничениях на степень зернистости
параллелизма – направление дальнейших
исследований.
1. Пьявченко Т.А., Финаев В.И. Автоматизи-
рованные информационно-управляющие
системы. – Таганpог: Изд-во ТРТУ, 2007. –
271 c.
2. Акуловский В.Г. Алгебра алгоритмов, бази-
рующаяся на данных // Кибернетика и си-
стемный анализ. – 2012. – № 2. –
С. 151–166.
3. Акуловский В.Г. Основы алгебры алгорит-
мов, базирующейся на данных // Проблеми
програмування. 2010. № 2 3.
С. 89 96.
4. Акуловский В.Г. Алгебра для описания
данных в композиционных схемах алго-
ритмов // Поблеми програмування. 2012.
№ 2 3. С. 234 240.
Теоретичні та методологічні основи програмування
21
5. Дорошенко А.Е., Акуловский В.Г. Нисхо-
дящее проектирование алгоритмов в рам-
ках алгероалгоритмического подхода //
Математические машины и системы. –
2012. – № 3. – С. 97–102.
6. Закревский А.Д. Параллельные алгоритмы
логического управления. – М.: Эдиториал
УРСС, 2012. – 200 с.
7. Ющенко Е.Л., Цейтлин Г.Е., Грицай В.П. и
др. Многоуровневое структурное проекти-
рование программ: Теоретические основы,
инструментарий. – М.: Финансы и стати-
стика, 1989. – 208 с.
8. Дорошенко А.Ю., Акуловський В.Г. Висхід-
не проектування алгоритмів при алгеброа-
лгоритмичному підході // Вісник Київсько-
го національного університету імені Тара-
са Шевченка. Серія фізико-математичні
науки, 2012. – Вип. 1. – С. 167–172.
Получено 11.01.2013
Об авторах:
Акуловский Валерий Григорьевич,
кандидат технических наук,
доцент кафедры информационных систем
и технологий,
Дорошенко Анатолий Ефимович,
доктор физико-математических наук,
профессор,
заведующий отделом
теории компьютерных вычислений.
Место работы авторов:
Академия таможенной службы Украины,
49000, г. Днепропетровск,
ул. Дзержинского 2\4.
E-mail: academy@amsu.dp.uа.
Тел. 050 941 05 66,
E-mail: valeryakulovskiy@rambler.ru
Институт программных
систем НАН Украины.
Тел. (044) 526 3559.
E-mail: dor@isofts.kiev.ua
http://opac.mpei.ru/notices/index/IdNotice:178164/index.php?url=/auteurs/view/27976/source:default
http://mail.rambler.ru/mail/mail.cgi?mode=compose;mailto=academy%40amsu.dp.u;83ec;enc=utf-8
http://mail.rambler.ru/mail/mail.cgi?mode=compose;mailto=valeryakulovskiy%40rambler.ru;83ec;enc=utf-8
mailto:dor@isofts.kiev.ua
|