Описание параллелизма в алгоритмах информационно-управляющих систем средствами алгебраического аппарата

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

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2013
Hauptverfasser:	Акуловский, В.Г., Дорошенко, А.Е.
Sprache:	Russian
Veröffentlicht:	Інститут програмних систем НАН України 2013
Schriftenreihe:	Проблеми програмування
Schlagworte:	Теоретичні та методологічні основи програмування
Online Zugang:	https://nasplib.isofts.kiev.ua/handle/123456789/86674
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:	Описание параллелизма в алгоритмах информационно-управляющих систем средствами алгебраического аппарата / В.Г. Акуловский, А.Е. Дорошенко // Проблеми програмування. — 2013. — № 3. — С. 13-21. — Бібліогр.: 8 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-86674
record_format	dspace
spelling	nasplib_isofts_kiev_ua-123456789-866742025-02-09T22:42:48Z Описание параллелизма в алгоритмах информационно-управляющих систем средствами алгебраического аппарата Акуловский, В.Г. Дорошенко, А.Е. Теоретичні та методологічні основи програмування Показана возможность описания в рамках алгебры алгоритмов с данными параллельных алгоритмов для класса информационно-управляющих систем. Введены средства синхронизации параллельно выполняемых ветвей алгоритма и продемонстрирована возможность построения производных средств синхронизации на основе введенных. 2013 Описание параллелизма в алгоритмах информационно-управляющих систем средствами алгебраического аппарата / В.Г. Акуловский, А.Е. Дорошенко // Проблеми програмування. — 2013. — № 3. — С. 13-21. — Бібліогр.: 8 назв. — рос. 1727-4907 https://nasplib.isofts.kiev.ua/handle/123456789/86674 519.681 ru Проблеми програмування application/pdf Інститут програмних систем НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Теоретичні та методологічні основи програмування Теоретичні та методологічні основи програмування
spellingShingle	Теоретичні та методологічні основи програмування Теоретичні та методологічні основи програмування Акуловский, В.Г. Дорошенко, А.Е. Описание параллелизма в алгоритмах информационно-управляющих систем средствами алгебраического аппарата Проблеми програмування
description	Показана возможность описания в рамках алгебры алгоритмов с данными параллельных алгоритмов для класса информационно-управляющих систем. Введены средства синхронизации параллельно выполняемых ветвей алгоритма и продемонстрирована возможность построения производных средств синхронизации на основе введенных.
author	Акуловский, В.Г. Дорошенко, А.Е.
author_facet	Акуловский, В.Г. Дорошенко, А.Е.
author_sort	Акуловский, В.Г.
title	Описание параллелизма в алгоритмах информационно-управляющих систем средствами алгебраического аппарата
title_short	Описание параллелизма в алгоритмах информационно-управляющих систем средствами алгебраического аппарата
title_full	Описание параллелизма в алгоритмах информационно-управляющих систем средствами алгебраического аппарата
title_fullStr	Описание параллелизма в алгоритмах информационно-управляющих систем средствами алгебраического аппарата
title_full_unstemmed	Описание параллелизма в алгоритмах информационно-управляющих систем средствами алгебраического аппарата
title_sort	описание параллелизма в алгоритмах информационно-управляющих систем средствами алгебраического аппарата
publisher	Інститут програмних систем НАН України
publishDate	2013
topic_facet	Теоретичні та методологічні основи програмування
url	https://nasplib.isofts.kiev.ua/handle/123456789/86674
citation_txt	Описание параллелизма в алгоритмах информационно-управляющих систем средствами алгебраического аппарата / В.Г. Акуловский, А.Е. Дорошенко // Проблеми програмування. — 2013. — № 3. — С. 13-21. — Бібліогр.: 8 назв. — рос.
series	Проблеми програмування
work_keys_str_mv	AT akulovskiivg opisanieparallelizmavalgoritmahinformacionnoupravlâûŝihsistemsredstvamialgebraičeskogoapparata AT dorošenkoae opisanieparallelizmavalgoritmahinformacionnoupravlâûŝihsistemsredstvamialgebraičeskogoapparata
first_indexed	2025-12-01T13:06:39Z
last_indexed	2025-12-01T13:06:39Z
_version_	1850311337074229248
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

Описание параллелизма в алгоритмах информационно-управляющих систем средствами алгебраического аппарата

Institution

Ähnliche Einträge