Algebraic automata specification of common and distributed memory parallel programs

Algebraic automata specification of common and distributed memory parallel programs

Issues of automata and algebraic research ascending to fundamental works of V.М. Glushkov are covered, the retrospective review of the basic results received in the given area is given and their internal interrelations and perspective directions of development are established. There are considered a...

Повний опис

Збережено в:
Бібліографічні деталі
Дата:2015
Автори: Doroshenko, A.Yu., Tseytlin, G.E.
Формат: Стаття
Мова:Ukrainian
Опубліковано: Інститут програмних систем НАН України 2015
Теми:
UDC 51:681.03
Онлайн доступ:https://pp.isofts.kiev.ua/index.php/ojs1/article/view/15
Теги: Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:Problems in programming

Репозитарії

Problems in programming
id pp_isofts_kiev_ua-article-15
record_format ojs
resource_txt_mv ppisoftskievua/0b/ce56741e13b630f15bc7af44c588eb0b.pdf
spelling pp_isofts_kiev_ua-article-152018-10-02T14:21:38Z Algebraic automata specification of common and distributed memory parallel programs Алгеброавтоматные спецификации параллельных программ над общей и распределенной памятью Doroshenko, A.Yu. Tseytlin, G.E. UDC 51:681.03 УДК 51:681.03 Issues of automata and algebraic research ascending to fundamental works of V.М. Glushkov are covered, the retrospective review of the basic results received in the given area is given and their internal interrelations and perspective directions of development are established. There are considered algebrai dynamic models of parallel interaction of the sequential programs and algebraic algorithmic specifications associated with these models. The questions of discrete transformers above internal memory and conveyor calculations are stated and also theory of clones and tool means of synthesis of parallel algorithms and programs are considered. Освещены вопросы теоретико-автоматных и алгебраических исследований, восходящих от фундаментальных работ В.М.Глушкова, приведен ретроспективный обзор основных результатов, полученных в данной области, а также установлены их внутренние взаимосвязи и перспективные направления развития. Рассмотрены алгебродинамические модели параллельного взаимодействия последовательных программ и алгеброалгоритмические спецификации, ассоциированные с этими моделями. Изложены вопросы дискретных преобразователей над внутренней памятью и конвейерные вычисления, а также теория клонов и инструментальные средства синтеза параллельных алгоритмов и программ. Інститут програмних систем НАН України 2015-07-01 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/15 PROBLEMS IN PROGRAMMING; No 3 (2003) ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 3 (2003) ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 3 (2003) 1727-4907 uk https://pp.isofts.kiev.ua/index.php/ojs1/article/view/15/19 Copyright (c) 2015 ПРОБЛЕМИ ПРОГРАМУВАННЯ
institution Problems in programming
baseUrl_str https://pp.isofts.kiev.ua/index.php/ojs1/oai
datestamp_date 2018-10-02T14:21:38Z
collection OJS
language Ukrainian
topic
UDC 51:681.03
spellingShingle
UDC 51:681.03
Doroshenko, A.Yu.
Tseytlin, G.E.
Algebraic automata specification of common and distributed memory parallel programs
topic_facet
UDC 51:681.03



УДК 51:681.03
format Article
author Doroshenko, A.Yu.
Tseytlin, G.E.
author_facet Doroshenko, A.Yu.
Tseytlin, G.E.
author_sort Doroshenko, A.Yu.
title Algebraic automata specification of common and distributed memory parallel programs
title_short Algebraic automata specification of common and distributed memory parallel programs
title_full Algebraic automata specification of common and distributed memory parallel programs
title_fullStr Algebraic automata specification of common and distributed memory parallel programs
title_full_unstemmed Algebraic automata specification of common and distributed memory parallel programs
title_sort algebraic automata specification of common and distributed memory parallel programs
title_alt Алгеброавтоматные спецификации параллельных программ над общей и распределенной памятью
description Issues of automata and algebraic research ascending to fundamental works of V.М. Glushkov are covered, the retrospective review of the basic results received in the given area is given and their internal interrelations and perspective directions of development are established. There are considered algebrai dynamic models of parallel interaction of the sequential programs and algebraic algorithmic specifications associated with these models. The questions of discrete transformers above internal memory and conveyor calculations are stated and also theory of clones and tool means of synthesis of parallel algorithms and programs are considered.
publisher Інститут програмних систем НАН України
publishDate 2015
url https://pp.isofts.kiev.ua/index.php/ojs1/article/view/15
work_keys_str_mv AT doroshenkoayu algebraicautomataspecificationofcommonanddistributedmemoryparallelprograms
AT tseytlinge algebraicautomataspecificationofcommonanddistributedmemoryparallelprograms
AT doroshenkoayu algebroavtomatnyespecifikaciiparallelʹnyhprogrammnadobŝejiraspredelennojpamâtʹû
AT tseytlinge algebroavtomatnyespecifikaciiparallelʹnyhprogrammnadobŝejiraspredelennojpamâtʹû
first_indexed 2025-07-17T10:04:19Z
last_indexed 2025-07-17T10:04:19Z
_version_ 1837888081668079616
fulltext Теоретические и методологические основы программирования © А.Е. Дорошенко, Г.Е. Цейтлин, 2003 ISSN 1727-4907. Проблемы программирования. 2003. № 3 5 УДК 51:681.03 А.Е. Дорошенко, Г.Е. Цейтлин АЛГЕБРОАВТОМАТНЫЕ СПЕЦИФИКАЦИИ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ НАД ОБЩЕЙ И РАСПРЕДЕЛЕННОЙ ПАМЯТЬЮ Освещены вопросы теоретико-автоматных и алгебраических исследований, вос- ходящих от фундаментальных работ В.М.Глушкова, приведен ретроспективный обзор основных результатов, полученных в данной области, а также установлены их внут- ренние взаимосвязи и перспективные направления развития. Рассмотрены алгебро- динамические модели параллельного взаимодействия последовательных программ и алгеброалгоритмические спецификации, ассоциированные с этими моделями. Изло- жены вопросы дискретных преобразователей над внутренней памятью и конвейер- ные вычисления, а также теория клонов и инструментальные средства синтеза парал- лельных алгоритмов и программ. Введение Как известно, человеческие кол- лективы способны эффективно решать сложные задачи посредством разделе- ния на более простые подзадачи с их распределением между исполнителями, входящими в состав коллектива, и ор- ганизацией взаимодействия между ис- полнителями (обмена промежуточными результатами, временного согласова- ния этапов разработки в соответствии с общим планом решения поставлен- ной задачи и др.). По аналогии со ска- занным современные компьютерные системы параллельного действия (мно- гопроцессорные системы, распреде- ленные вычислительные сети и среды) можно рассматривать как коллективы вычислителей, ориентированные на решение сложных задач при жестких ограничениях на допустимое время решения и другие ресурсы. Параллельные вычисления в на- стоящее время являются одной из главных парадигм современного про- граммирования и охватывают чрезвы- чайно широкий круг вопросов разра- ботки программ. Ввиду значительно более сложной природы параллельных вычислений по сравнению с последо- вательными большое значение приоб- ретают методы автоматизации разра- ботки параллельного программного обеспечения, основанные на примене- нии техники формальных моделей, спецификаций и преобразований па- раллельных программ. Фундаменталь- ными проблемами организации парал- лельных вычислений являются две сле- дующие [1]: • проблема увеличения произво- дительности и эффективности исполь- зования многопроцессорных и распре- деленных вычислительных систем; • проблема повышения уровня интеллектуализации программирования параллельных систем. Они не являются независимыми, ибо организация высокопроизводи- тельных вычислений в многопроцес- сорной системе современной архитек- туры оказывается слишком сложной для попыток ее решения без средств интеллектуализации программирования в такой системе. Трудность решения вопросов программирования парал- лельных систем определяется тем об- стоятельством, что вопросы организа- ции взаимодействий и синхронизации параллельных процессов существенно усложняют разработку параллельных алгоритмов и программ по сравнению с их традиционными, последователь- ными, вариантами. Имеющиеся сред- ства автоматизации программирования многопроцессорных систем, в основ- ном для языков семейства FORTRAN и C, не могут удовлетворить потребности все возрастающего количества пользо- вателей, так как имеют ограниченные возможности как по предоставляемым средствам параллельного программи- рования, так и по кругу решаемых за- дач, характеризуемых в основном ре- гулярными схемами вычислений. Теоретические и методологические основы программирования 6 Мощный поток исследований, особенно последнего десятилетия, по созданию языков параллельного про- граммирования высокого уровня, дек- ларативных средств описания и реали- зации параллельных вычислений, инте- грации различных парадигм програм- мирования – функциональной, проце- дурной, логической, объектно-ориенти- рованной, алгебраической – для про- ектирования параллельных вычислений привел к созданию целого ряда экспе- риментальных разработок, технологий и интерфейсов, значительно расши- ряющих возможности пользователей и разработчиков. Следствием интенсив- ности исследований в этой области и важности для промышленности стало появление стандарта де-факто на ин- терфейс параллельного программиро- вания под названием MPI (Message Passing Interface) для архитектуры с распределенной памятью, ориентиро- ванной на передачу сообщений. Этот факт характеризует важное направле- ние современного развития параллель- ных вычислений в сторону их незави- симости от архитектуры мультипро- цессорной платформы, на которую они первоначально намечались к реализа- ции, от топологии связей процессоров и их количества, других особенностей конкретных параллельных систем. Таким образом, основное назна- чение современной технологии проек- тирования программного обеспечения для параллельных систем – способст- вовать существенному повышению их производительности, надежности, со- кращению сроков разработки, облег- чению процесса сопровождения про- грамм, их модифицируемости в соот- ветствии с изменчивостью окружаю- щей программной среды и пр. Решение этих и других важных задач методоло- гии и технологии современного парал- лельного программирования сопряже- но с построением моделей, ориентиро- ванных на описание (спецификацию) параллельных вычислений, а также на реализацию (синтез) параллельных программ над различными видами па- мяти. Такие модели обычно представ- ляют собой многокомпонентные фор- мализмы, которые могут охватывать несколько парадигм не только собст- венно вычислений, но и других аспек- тов функционирования современных компьютерных систем. В данной статье освещены во- просы теоретико-автоматных и алгеб- раических исследований, восходящих от фундаментальных работ В.М. Глуш- кова по автоматизации проектирова- ния логических структур ЭВМ и про- граммирования [2, 3]. Целью работы является ретроспективный обзор ос- новных результатов, полученных в данной области, а также установление их внутренних взаимосвязей и пер- спективных направлений развития. Изложение материала осуществляется по мере повышения уровня абстракции в соответствии с принципом "снизу вверх". В разделе 1 обсуждается ряд важных аспектов, определяющих сущ- ность алгебродинамического подхода к формализации семантики параллель- ной программы. В разделе 2 приводят- ся основные понятия и результаты по построению аппарата систем алгорит- мических алгебр (САА) Глушкова и их модификаций, ориентированных на проектирование и синтез параллель- ных регулярных схем (ПРС). Особое внимание уделено построению алгеб- родинамических ПРС, базирующихся на механизмах координации парал- лельных ветвей с использованием ап- парата синхронизаторов и событий, а также РС последовательных компо- нент. В разделе 3 и 4 рассматриваются вопросы использования автоматных структур с внутренней памятью и кон- цепции двухуровневости алгебры алго- ритмики. 1. Алгебродинамические модели параллельных вычислений Как уже было отмечено во вве- дении, в настоящее время модели па- раллельных вычислений являются мно- гокомпонентными формализмами, ко- торые могут охватывать несколько па- радигм описания не только собственно вычислений, но и других аспектов функционирования многопроцессор- Теоретические и методологические основы программирования 7 ных систем [1]. Примерами тому явля- ются так называемые "практические" модели вычислений [4, 5], в которых присутствуют средства трех компо- нент: алгоритмической, определяющей распараллеливание собственно вычи- слительных операций; программной, определяющей особенности работы параллельных компонент с представ- ленными в модели различными видами памяти многопроцессорной системы; и координационной, отражающей свой- ства средств синхронизации и обменов между процессорами, которые могут существенно влиять на принципы ор- ганизации мультипроцессорной обра- ботки и производительность парал- лельной системы в целом. В настоящем разделе описан алгебродинамический подход к описанию параллельных вы- числений, разработанный в [6], кото- рый характеризуется следующими важными достоинствами: • задание динамической (опера- ционной) семантики вычислений, ко- торая собственно и является наиболее общим интерфейсом для разработчи- ков и пользователей параллельных систем; • использование в качестве кон- цептуальной основы абстрактного по- нятия дискретной динамической сис- темы [7], которая имеет естественную меру сложности своих процессов, а именно их длину; • локальность изменений и взаи- модействий, задаваемых в определении дискретных систем переходов, проис- ходящих в параллельной системе, что облегчает верификацию моделей и на- правлено на получение эффективных реализаций в распределенных мульти- процессорных системах и компьютер- ных сетях; • сохранение характера исчис- ления, присущего декларативным мо- делям (алгебрам) вычислений, что по- зволяет вести разработку параллель- ных систем в трансформационном сти- ле от начальных спецификаций до ко- нечной реализации, соблюдая кор- ректность и отслеживая эффектив- ность промежуточных преобразований. 1.1. Основные понятия и опре- деления алгебродинамической модели. В основу определения алгебрадинами- ческих моделей параллельных программ положены алгебра алгоритмов Глушко- ва и теория дискретных динамических систем [1, 2, 7]. Пусть V – множество переменных, а D – область значений переменных. Для простоты будем пола- гать, что все переменные из V – про- стые, т. е. их значения являются ска- лярными. Множество частичных ото- бражений В = {b: V → D}, называемых состояниями памяти, образует инфор- мационную среду. Алгебра алгоритмов является двухосновной алгеброй А(Y, U), где Y – алгебра операторов, состоящая из частичных преобразова- ний y : B → B информационной среды; U – алгебра условий, состоящая из частичных предикатов u : B → {0, 1}, за- данных на В. Операции алгебры опера- торов принимают значения в алгебре операторов. Таких операций три: • последовательная композиция PQ операторов P и Q: (PQ)(b) = (P(Q(b)); • ветвление u → (P else Q), где P, Q – операторы, u – условие; значе- ние операции ветвления определяется условным выражением: u → (P else Q) = = eсли u(b) = 1 то P(b) иначе если u(b) = 0 то Q(b) иначе не определено; • итерация while(u, P), где u – ус- ловие, P – оператор; по определению while(u, P)(b) = eсли u(b) = 0 то b иначе ес- ли u(b) = 1 то while(u, P)(P(b)) иначе не оп- ределено. Пусть n > 0 – наименьшее целое число такое, что u(Pn(b)) = 1 и u(Pk(b)) = 0 для всех k = 1, …, n – 1. Если такое n су- ществует, то операция итерации опре- делена и ее значение может быть вы- числено while(u, P)(b) = Pn(b). Алгебра операторов содержит константы: ε – тождественный опера- тор и ∅ – пустой оператор. В алгебре условий имеются константы: 0 – тож- дественно ложное и 1 – тождественно истинное условие; булевы операции, а также операция умножения Pu опера- тора на условие. По определению Теоретические и методологические основы программирования 8 Pu(b) = u(P(b)), и тем самым Pu есть ус- ловие "u после Р ". Таким образом, ал- гебра алгоритмов есть множество опе- раторов и условий, замкнутое относи- тельно операций алгебры алгоритмов. Если в алгебре операторов выделено множество базовых операторов, а в ал- гебре условий – множество базовых условий таким образом, что они поро- ждают всю алгебру алгоритмов, то ка- ждый элемент алгебры может быть представлен регулярным выражением из элементов выделенного базиса и операций алгебры алгоритмов. Регу- лярные выражения алгебры операто- ров называются регулярными програм- мами. Регулярную программу будем на- зывать программой с двухуровневой памятью, если множество ее перемен- ных состоит из двух непересекающих- ся подмножеств: V = I ∪ E, где I – мно- жество внутренних, Е – множество внешних переменных программы, а среди базовых операторов определены операторы чтения из внешней памяти x: ← e и записи во внешнюю память х: → e, x∈I, e∈E. Операторы чтения и записи называются операторами внешнего обмена и имеют смысл, ана- логичный оператору присваивания: при выполнении оператора записи значение внутренней переменной ста- новится значением внешней, а при вы- полнении оператора чтения – наобо- рот: внутренняя переменная становит- ся обладателем значения внешней пе- ременной. Если Р = {Pi} – множество регу- лярных программ и Ii – множество внутренних переменных программы Рi, то будем говорить, что память I = ∪Ii является распределенной, если множе- ства Ii попарно не пересекаются. Пусть теперь Р = {Pi} – конечное множество регулярных программ с распределенной памятью, К – множество имен, конеч- ное или бесконечное, и t : К → P – сюръективное отображение именова- ния. Программы из Р называются со- общающимися в К, если в их базисе операторов имеются операторы прямо- го обмена данными: оператор передачи вида х → k и оператор приема вида х ← k, где х – внутренняя переменная, k – имя, отличное от имени програм- мы, в которой выполняется данный оператор прямого обмена. Операторы прямого обмена являются парными. При выполнении в программе t(ki) пе- редачи вида х → kj в программе t(kj) од- новременно должен выполняться при- ем вида y ← k. Обмен данными проис- ходит по правилам присваивания y := x. Будем считать, что базис операторов алгебры алгоритмов содержит кроме обычных конструкций последователь- ных программ указанные выше опе- раторы прямого и внешнего обмена, а также оператор независимого (парал- лельного) вызова программ вида (y1, …, ym) ← F(x1, …, xn), где F есть имя независимо вызываемой программы, а x1, …, xn и y1, …, ym – coответственно ее фактические входные параметры и результаты. Операторы, не являющие- ся операторами обмена и независимо- го вызова программ, будем называть элементарными. Определение. Параллельной про- граммой называется набор p = (P, K, t, E), где P = {Pi} – множество сообщаю- щихся в K регулярных программ с двухуровневой памятью, внутренняя память которых распределена, а внеш- няя память E является общей. Имена из K называются именами элементов, программы из P – элементными про- граммами или просто элементами, а частичное отображение t : K → P – кон- фигурацией программы. Определенная таким образом параллельная программа представляет собой весьма общую модель парал- лельных вычислений для системы взаимодействующих регулярных по- следовательных программ над двух- уровневой памятью. Такое определе- ние охватывает все три известных спо- соба взаимодействия в параллельных программах: через общую память, пе- редачей сообщений и с помощью неза- висимого вызова программ. Такое оп- ределение параллельной программы Теоретические и методологические основы программирования 9 также обобщает, в смысле допущения динамической конфигурации парал- лельной программы, известные общие формализмы параллелизма, ставшие уже классическими, такие, как взаимо- действующие процессы Хоора [8], рас- пределенные процессы Хансена [9] и другие. Конфигурация программы в общем случае зависит от времени и характеризует текущую актуализацию элементных программ, т.е. состояние их активности. Элементы начальной конфигурации, которая может быть не всюду неопределенной, начинают вы- полняться непосредственно после за- пуска параллельной программы. В дальнейшем конфигурация может из- меняться под воздействием самих эле- ментных программ: при выполнении независимых вызовов новые элементы добавляются в конфигурацию, а по за- вершении вызванной программы – из конфигурации удаляются. Выполнение параллельной программы начинается запуском элементов из начальной конфигурации и заканчивается по за- вершении всех вызванных элементных программ. Предполагается, что вход- ные и выходные данные программы находятся во внешней памяти. Для описания семантики парал- лельных программ будем использовать общие понятия дискретных динамиче- ских систем (называемых по-другому и транзиционными системами [10]). Дис- кретная динамическая система (ДДС) есть тройка (S0, S, d), где S – множест- во, называемое пространством состоя- ний; S0 ⊆ S – множество начальных со- стояний; d – бинарное отношение пе- реходов в пространстве состояний. Ес- ли обозначить Р(S0) множество всех конечных процессов, т.е. последова- тельностей состояний р = s0, s1, …, sn,…, начинающихся в S0, s0∈S0, n ≥ 1, то d можно представить как отношение d ⊆ Р(S0) × S такое, что d(s, S) = ∅ для всех s∉S. Отношение переходов и множество начальных состояний одно- значно определяют множество допус- тимых процессов F системы как объе- динение ∪ ∞ = = 0t tFF , где Ft есть множест- во допустимых процессов длительно- стью t. Здесь F0 – множество началь- ных состояний, а для t > 0 имеет место ps ∈ Ft ⇔ p ∈ Ft–1 и ps ∈ d(p), где d рас- сматривается как многозначное ото- бражение d: P(S) → S. Поэтому систему (S0, S, d) можно задавать и альтернатив- ным способом в виде пары (S, F). Для обозначения ДДС будем использовать, если это не приводит к двусмысленно- сти, тот же символ, что и для множест- ва ее состояний. Здесь рассматриваются детерми- нированные автоматные ДДС. Система (S0, S, d) называется автоматной, если (ps, s')∈d ⇔ (s, s')∈d. В таком случае пару (p, s)∈d, где р∈Р(S0), s∈S, естественно записывать р s, если S фиксировано. Система называется детерминирован- ной, если отношение переходов d можно отождествить с отображением d : Р(S0) → S. В автоматных детермини- рованных системах переходы не зави- сят от предысторий и поэтому их мож- но изображать в виде следования s s'. В пространстве состояний может быть выделено подмножество S* ⊆ S, назы- ваемое множеством заключительных состояний, такое, что процессы, прохо- дящие через S*, обязательно заверша- ются. Такие процессы будем называть финальными. Процесс может завер- шаться также ввиду неопределенности отношения переходов в состояниях, не являющихся заключительными. Такие процессы называются тупиковыми, а состояния – тупиками. ДДС называ- ется многокомпонентной, если множе- ство ее состояний S содержится в де- картовом произведении S ⊆ S1 ×…× Sm. Множества S1 … Sm, которые составля- ют наименьшее декартово произведе- ние, содержащее S, называются ком- понентами системы. Если компоненты системы сами являются многокомпо- нентными ДДС, то система называется многоуровневой. Многокомпонентные многоуровневые дискретные динами- ческие системы в дальнейшем исполь- Теоретические и методологические основы программирования 10 зуются в качестве моделей параллель- ных программ для определения их операционной семантики. В соответствии с введенным вы- ше определением параллельная про- грамма определяет объект последова- тельно-параллельных вычислений, в котором последовательное управление вычислениями внутри элементов соче- тается с параллелизмом вычислений на межэлементном уровне, задаваемом конфигурацией параллельной про- граммы. Построение агебродинамиче- ской модели проводится в два этапа. Сначала строится базовая дискретная динамическая система C0, в терминах которой определяется концептуально более прозрачная, но зато более огра- ничительная синхронная операционная семантика взаимодействий параллель- ных программ. Затем путем преобразо- ваний базовой модели получается ос- новная модель, в которой взаимодейст- вия параллельных элементов реализу- ются асинхронным способом. 1.2. Базовая алгебродинамиче- ская модель параллельных программ. Ключевым в определении общей ал- гебродинамической модели паралле- лизма вычислений является случай двухуровневой параллельной програм- мы (который будем называть базовым) – нижний уровень элементов и верх- ний уровень управления элементами. Базовый уровень является основным для изучения, поскольку к нему может быть сведен общий случай многоуров- невых программ [7]. Динамический ха- рактер вычислений базовой модели определяется только возможностями независимого вызова программ. Общая память при этом остается одноуровне- вой, доступной для использования все- ми компонентами параллельной про- граммы статически определенными и динамически порожденными. Базовая дискретная динамическая система, в терминах которой задается операцион- ная семантика параллельных программ, детально описана в [6] и выглядит сле- дующим образом. Пусть p = (P, K, t, E) – параллель- ная программа в смысле данного выше определения. Будем считать, что внут- ренние переменные Ii элементов Pi∈P и внешние переменные E программы яв- ляются скалярными и принимают зна- чения в некотором универсальном бес- типовом множестве данных D. Состоя- ния системы определим как векторы ((k1, b1, R1), …, (km, bm, Rm), M), где bi : Ii → D – состояния памяти элементных про- грамм Рi; Ri – состояния управления тех же программ (остаточные про- граммы при их выполнении методом интерпретации); {k1, …, km}⊆ K – мно- жество имен элементов текущей кон- фигурации, задающей соответствие t(ki) = Pi; М : Е → D – состояние внеш- ней памяти. Ко множеству начальных состояний системы отнесем все такие состояния, в которых Ri = Рi и bi = ∅, i = 1, …, m, т.е. остаточные программы представляют собой исходные эле- ментные программы, а значения всех внутренних переменных неопределе- ны. В заключительных состояниях имеет место Ri = ε, i = 1, …, m. Заметим, что внешнюю память также можно считать элементом, но с пустой про- граммой. Отношения переходов на множе- стве состояний базовой системы C0 оп- ределяются правилами переходов. Для примера в табл. 1 представлены прави- ла переходов А1—А4, описывающие выполнение операторов прямого обме- на данными и основных управляющих конструкций (для удобства представле- ния в правилах фиксируются только изменяемые или используемые состав- ляющие векторов состояний). В системе C0 правила переходов состояний представлены с точностью до неэлементарных операторов (обме- нов и независимого вызова). Непосред- ственно из определения правил пере- ходов следует, что система является ав- томатной и недетерминированной [7]. Параллелизм выполнения параллель- ной программы моделируется недетер- минированностью порядка, в котором совершаются переходы внутри различ- ных элементов программы. Выполне- ние всех операторов элементов, вклю- Теоретические и методологические основы программирования 11 чая неэлементарные, является син- хронным в том смысле, что в элемент- ной программе, выполняющей данный оператор, не может происходить ника- ких других вычислений до тех пор, по- ка данный оператор не будет завершен. Например, для прямых обменов это оз- начает так называемое рандеву (тер- мин, предложенный авторами языка Ада). Именно соответствующие один другому операторы приема и передачи данных согласно правилу А4 могут вы- полняться только одновременно, а в элементе, где готовность к обмену бы- ла достигнута раньше, должно насту- пить ожидание обоюдной готовности к обмену. Достоинства такого определе- ния семантики обменов заключаются в простоте модели и надежности реали- зации. Однако простота модели обора- чивается потерей эффективности па- раллельных программ ввиду неконтро- лируемости ожиданий синхронизации и сложностью программирования для достижения этой эффективности в процессе проектирования. 1.3. Алгебродинамическая мо- дель асинхронных вычислений. В [6] предложена общая схема расширения алгебродинамических моделей путем построения отображений реализации в модели параллельных программ с до- полнительными возможностями дина- мического распараллеливания за счет асинхронных вычислений внутри эле- ментных программ, предназначенных для сглаживания возможных неравно- мерностей вычислений обмениваю- щихся компонент и повышения таким способом эффективности распаралле- ливания. Такие возможности динами- ческого совмещения вычислений раз- личных элементов появляются при ос- лаблении требования строго синхрон- ных вычислений по отношению к па- мяти. Техника построения такого рода модели продемонстрирована ниже на примере построения модели С1 с ло- кально-асинхронными обменами. Суть введения асинхронности при выполнении неэлементарного опе- ратора в элементной программе состо- ит в том, чтобы в случае невозможно- сти немедленного выполнения опера- тор мог бы быть отложен до момента готовности его входных данных в рас- пределенной памяти элемента, а в про- межутке тем временем вычисления могли бы быть продолжены в элементе до тех пор, пока не нарушаются ин- формационные связи отложенного оператора. Например, при откладыва- нии оператора передачи x → k (приема x ← k) возможно продолжение вычис- лений вплоть до момента изменения (использования) значения переменной х. Таким образом, готовность к обмену можно проверять не в точке, а в неко- тором интервале, величина которого определяется объемом вычислений в информационно независимых от не- элементарного оператора фрагментах элементной программы. Чем больше величина такого интервала, тем выше асинхронность оператора обмена и тем меньше потери времени на ожидания синхронизации. Если при этом интер- валы готовности обменивающихся эле- ментов перекрываются во времени, то ожидания могут не появляться вовсе. Подходы к определению такого рода моделей асинхронной памяти могут Таблица 1. Примеры правил переходов состояний в базовой системе C0 A1. Если y – элементарный опе- ратор, то (bi, yRi) (y(bi), Ri). A2. (bi,(u → (R else Q))T) ( , ) ( , ) i ι i ι b RT , u(b b QT , u b ) =  ( ) = 1 0 если ; если . A3. (bi, while(u, R)Q) ( , ), ( , ; ( , ) ), i ι i ι b Q u(b b R while u R Q u b ) =  ( ) = 0 1 если ; если . A4. ((ki, bi, (x → kj)R), (kj, bj, (y ← ki Q))) ((ki, bi, R), (kj, b'j, Q)), где b'j(r) = ( ( ), ( ( ) i j b x r y b r =   если ; иначе. Теоретические и методологические основы программирования 12 гут быть различными в зависимости от глубины анализа информационных связей операторов элементной про- граммы. Для точного формулирования новой модели C1 с асинхронной рас- пределенной памятью в терминах дис- кретных динамических систем понятие состояния системы расширяется путем добавления к нему новых составляю- щих, отражающих состояния обменов и вызовов в параллельной программе. Состояниями в C1 являются век- торы ((k1, b1, R1), …, (km, bm, Rm), H, M, τ, µ, λ), где bi, Ri и М обозначают то же, что и в модели C0, Нi есть множество отло- женных неэлементарных операторов в элементе ki; Н = ∪ m i iH 1= , Нi ∩ Hj = ∅, i ≠ j, τ и µ  пара матриц порядка m(m + 1), характеризующая состояния обменов. Элемент матрицы τij, 1 ≤ i, j ≤ m, представляет собой очередь перемен- ных на передачу данных из элемента ki в kj, а µij, 1 ≤ i, j ≤ m, есть очередь пере- менных на прием значений в ki из kj. Очереди последнего столбца в матри- цах τ и µ аналогично представляют со- стояния обменов с внешней памятью с той лишь разницей, что элементами этих очередей являются пары (x, e), где х  внутренняя, е  внешняя пере- менная элементной программы. Диаго- нальные элементы этих матриц не ис- пользуются, так как автопередача и ав- топрием данных в элементах не допус- каются. Операцию постановки в оче- редь будем изображать конкатенацией * справа, а операцию взятия из очере- ди – сокращением очереди на один элемент слева. Отметим различие в на- значении очередей в матрицах τ и µ, отражающих состояния прямых и внешних обменов параллельной про- граммы. Если очереди τij и µij, 1 ≤ i, j ≤ m, предназначены сглаживать возможную несогласованность моментов прямых обменов элементов, то очереди послед- него столбца этих матриц должны служить буфером для предотвращения ожиданий из-за различия скоростей внутренней и внешней памяти про- граммы. При таком определении состоя- ний системы C1 начальными в ней бу- дут такие состояния, в которых bi = Hi = = τij = µij = ∅, Ri = Pi для всех ki, kj∈K, а за- ключительными – такие, где Ri = ε, Hi = = τij = µij = ∅. Для задания правил пере- ходов в системе C1 введем несколько дополнительных определений. Для ка- ждого элементарного оператора у зада- дим множества его входных in(y) и вы- ходных out(y) переменных. Значения переменных из in(y) используются, а из out(y)  изменяются при вычислении преобразования состояния памяти у : В → В. Для каждого элементарного условия u∈U будем считать заданным множество in(u) его входных перемен- ных, значения которых используются при вычислении предиката u : B → {1, 0}. Например, для операторов обмена мно- жества in и out описываются следующим образом: in(x → k) = {x, k}, out(x → k) = ∅, in(x ← k) = {k}, out(x ← k) = {x}, in(x :→ e) = = {x, e}, out(x :→ e) = ∅, in(x :← e) = {e}, out(x :← e) = {x}. Понятие множеств in и out может быть естественным образом распространено на произвольные опе- раторы элементных программ – вы- ражения в алгебре операторов. Для не- элементарных операторов определяе- мые ниже множества In и Out совпада- ют соответственно с множествами in и out этих операторов, а для элементар- ных операторов будем считать их из- вестными: In(P; Q) = In(P) ∪ (In(Q)\Out(P)), Out(P; Q) = Out(P) ∪ Out(Q), In(u → (P~else~Q)) = In(u)∪ In(P) ∪ In(Q), Out(u→(P else Q)) = Out(P) ∪ Out(Q), In(while(u, P)) = In(u) ∪ In(P)), Out(while(u, P)) = Out(P). Операторы P и Q, как обычно, будем называть информационно неза- висимыми, если In(P) ∩ Out(Q) = In(Q) ∩ ∩ Out(P) = Out(Q) ∩ Out(P) = ∅. Аналогич- Теоретические и методологические основы программирования 13 но условие u считается информацион- но независимым от оператора Р в слу- чае in(u) ∩ Out(P) = ∅. Если Р  опера- тор, u  условие и S  множество операторов, информационно незави- симых от Р и u, то будем обозначать та- кое отношение соответственно ind(P, S) и ind(u, S). С учетом введенных обозна- чений правила переходов в модели C1, соответствующие указанным в табл. 1 примерам правил системы С0, приве- дены в табл. 2. Как видно из табл. 2, обмен дан- ными, который был специфицирован в системе С0 единственным правилом А4, в новой системе теперь определя- ется тремя: В4, В5 и В6. Тем самым асинхронность работы с памятью в мо- дели C1 достигается за счет разбиения единого, в случае синхронного режима базовой модели, акта выполнения взаимодействия на две фазы: иниции- рования и завершения. Инициирова- ние состоит в превращении неэлемен- тарного оператора в отложенный (опе- ратор попадает во множество Н) и по- становке в очередь (в список) соот- ветствующих элементов сигнатуры этого оператора. Состояния, в которые приходит система C1 после выполне- ния перехода по правилам В4, В5, на- зываются состояниями инициирования. Завершение обмена или независимого вызова происходит при условии вза- имной готовности взаимодействующих элементов и заключается в передаче данных или возвращению результатов, приводящих к изменению состояния памяти элементов и сокращению оче- редей переменных, списков состояния вызовов и множества Н. В промежутке между инициированием и завершени- ем, называемом интервалом готовно- сти к взаимодействию, в элементе мо- гут проводиться вычисления операто- ров, информационно независимых от оператора обмена или независимого вызова. Если время выполнения этих вычислений меньше интервала готов- ности к взаимодействию, то в элемен- те, пришедшем в состояние готовности раньше элемента-партнера, наступит ожидание. В противном случае элемен- ты взаимодействуют без ожиданий. Увеличение интервалов готовности для повышения асинхронности памяти при фиксированной элементной программе возможно только путем искусственно- го разрыва информационных связей неэлементарных операторов взаимо- действия. Другие возможные усиления модели вычислений в этом направле- нии разрабатывались в [6]. Асинхронность выполнения не- элементарных операторов по отноше- нию к распределенной памяти в по- строенных моделях является важным источником повышения эффективно- сти параллельных программ. Однако Таблица 2. Примеры правил переходов состояний системы C1 B1. Если y элементарный опера- тор и ind(y, Hi), то (bi,yRi) (y(bi),Ri). B2. Если u есть условие и ind(u, Hi), то (bi, (u → (R else Q))T) ( , ), ( ) ( , ), i i ι b RT u b b QT u b ι =  ( ) = 1 0 если ; если . B3. Если u есть условие и ind(u, Hi), то (bi, while(u, R)Q) ( , ), ( , ; ( , ) ), i ι i ι b Q u(b b R while u R Q u b ) =  ( ) = 0 1 если ; если . B4. Если ind(x → kj, Hi), то ((bi, (x → kj)R, Hi, τij ((bi, R, Hi ∪ {x → kj}, τij*x). B5. Если ind(x ← kj, Hi), то ((bi, (x ← kj)R, Hi, µ ij ((bi, R, Hi ∪ {x ← kj}, µij*x). B6. Если τij = x*τ'ij и µ ij = z*µ' ij, то ((bj,Rj),Hi,Hj, τij, µ ji) ((b'j, Rj), Hi \ {x → kj}, Hj \ {x ← ki}, τ'ij, µ'ji), где b'j(r) = ( ( ), ( ( ) i j b x r z b r =   если ; иначе. Теоретические и методологические основы программирования 14 правильность функционирования про- грамм при этом нуждается в обоснова- нии. Вопросы корректности рассмот- ренной модели асинхронных обменов сводятся к исследованию свойства гло- бальной детерминированности (кон- флюэнтности) [7]. Хотя элементы па- раллельных программ являются детер- минированными динамическими сис- темами, построенные модели асин- хронных взаимодействий порождают недетерминированные процессы вы- числений. Источником недетерминиз- ма является общая внешняя память элементов. Однако если ограничить обмены с внешней памятью только чтениями значений входных перемен- ных (назовем такие параллельные про- граммы простыми), то процесс вычис- лений определяется однозначно его начальным состоянием. Это утвержда- ет следующая теорема, являющаяся обобщением теоремы о глобальной де- термиированности асинхронных вы- числений в [6] (идею доказательства и некоторые дополнительные понятия можно найти там же). Теорема 1. Пусть С есть модель простых параллельных программ. Пусть также р – финальный (тупико- вый) процесс в С с начальным состоя- нием s0 и заключительным (тупиковым) состоянием s*. Тогда любой другой процесс р' = r(p) в системе С’, получен- ный при неукорачивающем реализую- щем отображении r: C' → C и начи- нающийся в r(s0), также является фи- нальным (тупиковым) и заканчивается в r(s*) или может быть продолжен до такового. Результат этой теоремы аналоги- чен полученному в [10] в терминах транзиционных систем и дает возмож- ность строить путем неукорачивающих (т.е. таких, при которых длины процес- сов-образов могут только увеличивать- ся) реализующих отображений все бо- лее ”тонкие”, в смысле совмещения вычислений и обменов, алгебродинами- ческие модели параллельных программ, в которых, например, можно автомати- чески разрешать некоторые классы коммуникационных тупиков [11]. 2. Регулярные схемы алгоритмов в алгебрах Глушкова Рассмотрим ряд результатов, от- носящихся к описанию алгебродина- мических моделей средствами струк- турных (регулярных) схем в алгебрах Глушкова. Особенность функционирования достаточно сложной кибернетической системы, состоящей из управляющего U и операционного O объектов, заклю- чается в наличии наряду с прямым и обратного канала связи между упомя- нутыми объектами, которые, как пра- вило, представлены в автоматной фор- ме (рисунок). U O Рисунок По прямому каналу (от U к O) выполняются операторы A – действия для целенаправленного изменения со- стояния автомата O (объекта, подле- жащего управлению). В то же время управляющий автомат U по каналу об- ратной связи получает информацию о текущем состоянии автомата O (управ- ляемого объекта). Эта информация по- ступает в виде значений логических условий u, с требуемой степенью пол- ноты отражающих состояние объекта O. При этом в классической версии [13] автомат U конечен, тогда как, автомат O бесконечен в силу, обычно, высокой степени сложности объекта O. В соот- ветствии с итеративным взаимодейст- вием с O управляющий автомат U либо переходит в заключительное состоя- ние, завершая процесс управления, ли- бо продолжает взаимодействие с объ- ектом O. В литературе управляющий ав- томат был назван дискретным преоб- разователем (ДП) [12]. В рамках приве- денной модели ДП получены следую- щие фундаментальные результаты: • произвольно выбранная ки- бернетическая система представима в форме ДП; Теоретические и методологические основы программирования 15 • использование в ДП недетер- минированных переходов и выходов приводит к моделированию недетер- минированных процессов; • модель ДП положена в основу алгебродинамических и ряда других известных моделей и обеспечивает возможность многоаспектного интегри- рованного описания исследуемых про- цессов [6, 13]. В табл. 3 приведены основные конструкции входящие в сигнатуру САА и их модификаций (САА-М), впо- следствии получивших название ал- гебр Глушкова (АГ) [14]. Под регуляр- ными (структурными) схемами (РС) понимаются представления последова- тельных алгоритмов в САА; в тоже время параллельные алгоритмы пред- ставимы в САА-М в форме параллель- ных РС (ПРС). В качестве базиса зафиксируем совокупность I – операторных и U – логических переменных. Справедливы следующие утверждения. Теорема 2 (о регуляризации – теорема Глушкова [САА,16]). Произ- вольный алгоритм (программа или микропрограмма) F представим в САА и САА-М эквивалентной интерпрети- рованной РС F = FI; разработана кон- структивная процедура регуляризации (сведения к РС FI) произвольного алго- ритма. Следствие 1. Поведение произ- вольно выбранного ДП, описанного в алгебродинамической форме, предста- вимо посредством РС в САА. Следствие 2. В рамках САА осу- ществимо прогнозирование процесса управления представленного ДП, а также обоснование проверки правиль- ности его функционирования. Справедливость данного следст- вия вытекает из наличия в сигнатуре САА операции прогнозирования, а также из двухосновности данной сис- темы. Таким образом, АГ совпадают по своей порождающей мощности с из- вестными алгоритмическими система- ми [17]. Теорема 3 [18, 19]. Пусть |А| – совокупность операторов, порожден- ных алгеброй А, тогда справедливы следующие строгие включения: |АД| ⊂ ⊂ |АЯ| ⊂ |АГ|, где АД – алгебра Дейкст- ры; АЯ – алгебра Янова. Доказательства теорем 2 и 3 ба- зируются на принадлежности операции прогнозирования сигнатуре АГ и про- изводности в АЯ основных операций АД. Важно также отметить трансфор- мационную сводимость неструктурных схем АЯ к эквивалентным РС [18]. К числу распространенных средств алгоритмических специфика- ций относятся граф-схемы алгоритмов. Проблема построения соответствую- щей алгебры алгоритмов была постав- лена в [19] и решена в [21, 20]. Пусть АГС – алгебра граф-схем, сигнатура операций которой состоит из графо- вых представлений операций, входя- щих в сигнатуру АГ (см. табл. 3). Теорема 4 [19—21]. АГС изо- морфна АГ и любой алгоритм А пред- ставим эквивалентной интерпретиро- ванной граф-схемой G1, А = G1. На построенную в [20] АГС мо- гут быть распространены результаты структурной схематологии [22]. Взаимодействие автоматов U и O может носить распределенный харак- тер. Такое разбиение среды предста- вимо в форме распределенной сети ДП, обеспечивающих систематический контроль и реакцию на изменения со- стояний среды. В результате приходим к распределенным многопроцессорным моделям, а также ассоциированным с ними алгеброавтоматным параллельно взаимодействующим компонентам, рассмотренным в предыдущем разделе. В терминах аппарата САА-М могут быть формализованы приведенные там построения, так что справедливо сле- дующее утверждение. Теорема 5. Алгебродинамические модели С0 и С1 над общей и распреде- ленной памятью представимы в АГ по- средством ПРС. Теоретические и методологические основы программирования 16 Таблица 3. Основные операции модифицированных систем алгоритмических алгебр (САА-М) Тип Название операции Форма аналити- ческая естественно- лингвистическая графовая Логические Конъюнкция u ∧ u’ u . u’ u И u’ Дизъюнкция u ∨ u’ u + u’ u ИЛИ u’ Отрицание u НЕ(u) Прогнозирова- ние (левое ум- ножение условия на оператор) A • u ПОСЛЕ A условие u Композиция A * B A ЗАТЕМ B Альтернатива ([u] A, B) ЕСЛИ u ТО A ИНАЧЕ B Цикл {[u] A} ПОКА НЕ u ЦИКЛ A Фильтр u ФИЛЬТР(u) Асинхронная дизъюнкция A ∨ B A // B A ПАРАЛЛЕЛЬНО B Контрольная точка T(u) КТ u Операторные Синхронизатор S(u) ЖДАТЬ(u) Теоретические и методологические основы программирования 17 Действительно, последователь- ные ветви введенных выше параллель- ных программ представимы в РС САА (см. теорему 2), а обмен данными меж- ду элементными программами возмо- жен двух видов: прямыми обменами между областями локальной памяти двух последовательных компонент и внешними – через общую внешнюю память. На уровне ПРС подобные об- мены реализуемы в терминах синхро- низаторов и контрольных точек, т.е. событийных средств, входящих в сиг- натуру САА-М. 3. Дискретные преобразователи с внутренней памятью и асинхронные конвейерные вычисления К структурному параллельному программированию наряду с обычны- ми программными конструкциями (по- следовательной, альтернативной, цик- лической и др.) следует отнести и ос- новные структуры организации парал- лельных вычислений: конвейер, кару- сель, стапель и их разнообразные со- четания. Перечисленные основные па- раллельные структуры концентриру- ются по двойственным стратегиям мультиобработки: синхронной и асин- хронной [13, 23]. Сущность синхронной обработки состоит в разделении времени на рав- ные интервалы (квантование) и в од- новременном выполнении за один временной интервал (квант) ряда дей- ствий (однотипных или разнотипных) над потоком данных, например одно- временное умножение каждого эле- мента вектора или матрицы на некото- рую константу. В случае асинхронной обработки несколько взаимодейст- вующих параллельных ветвей функ- ционируют на распределенных между ними потоках данных, осуществляя в процессе взаимодействия обмены про- межуточными результатами и синхро- низацию в определенные моменты времени. Рассмотрим известные разно- видности структур памяти: магазин, стек, очередь и их разнообразные со- четания в качестве разновидностей общего понятия эластичная лента [15, 16, 20], которое ориентировано на плотное хранение и обработку данных при проектировании различных про- цессов, в том числе и динамических, относящихся к асинхронному конвей- еру, стапелю и др. [23]. В процессе функционирования конвейерных вы- числений для снятия временных огра- ничений на квант синхронного выпол- нения команд, свойственного типовому конвейеру, введём в рассмотрение асинхронную модель конвейера Ка, в которой применяется структура памяти типа очередь для передачи данных ме- жду соседними процессами [23]. Пусть дана упорядоченная по- следовательность в общем случае раз- нотипных процессов А1, А2, ..., Аk, кото- рые выполняются над потоком перера- батываемых данных М = (m1, m2, ..., mc) так что результат обработки q-го про- цесса поступает в q-ю очередь (память типа FIFO), работающую по принципу "последним пришел, последним ушел", из вершины которой элементы переда- ются на обработку (q + 1)-му процессу: где R – поток результирующих дан- ных. Процессы A1, A2, ..., Ak по мере поступления к ним на вход данных ра- ботают одновременно и асинхронно так, что Ai передает свои выходные данные на вход соседу справа процессу Ai+1, используя очередь БСi. Посредст- входной поток mc, mc-1, ..., m2, m1⇒A1| ⇒q1 ⇒ A2| ⇒q2 ⇒A2, ..., qk-1 ⇒Ak| ⇒ r1 ⇒ R, Теоретические и методологические основы программирования 18 вом процесса Ak формируется поток R результирующих данных. Использова- ние очередей обеспечивает независи- мую по времени параллельную работу процессов Ai, входящих в Ка. Проиллю- стрируем САА-М спецификации по- следовательных и параллельных алго- ритмов символьной обработки данных на примерах сортировки. С этой целью в терминах разметки [20] формализу- ются средства доступа – концепция абстрактного типа данных (АТД). Под разметкой понимается последователь- ность m: НУ2У1 а1 а2 ... аn К, где Н, К – маркеры, фиксирующие соответствен- но начало и конец сортируемого мас- сива; У1, У2 – указатели, переме- щающиеся по массиву а1 а2 ... аn вправо или влево на указанное количество символов ai (i = 1, 2, ..., n). На размечен- ном массиве m определяются базисные предикатные и операторные интерпре- тации РС, характеризующие доступ к массиву в процессе его сортировки. Предикатные интерпретации: l > r по У2 – логическое условие, истинное, если указанное отношение выполняет- ся для элементов l и r, расположенных непосредственно слева, справа от ука- зателя У2; d(У1, К) – логическое усло- вие, истинное, когда указатель У1 дос- тиг маркера К. В остальных случаях приведенные предикатные интерпре- тации ложны. Операторные интерпре- тации: P(У2, У1) – сдвиг указателей У2 и У1 на один символ вправо по масси- ву m; L(У2) – сдвиг У2 на один символ влево по массиву m; ТРАНСП(l, r|У2) – перестановка элементов l и r, соседних с указателем У2; УСТ(У2 на У1) – уста- новка указателя У2 на У1. Пример 1. Алгоритм ЧЕЛНОК, в терминологии Д.Кнута – "прямые вставки" [24], использует описанные выше средства доступа к сортируемым данным: ЧЕЛНОК ::= {[d(У1, К)] P(У2, У1) * {[l > r по У2] ТРАНСП(l, r|У2) * * L(У2)} * УСТ(У2 на У1) }. Суть алгоритма состоит в том, что пара указателей перемещается вправо по массиву до обнаружения первой неупорядоченной пары, затем во вложенном цикле элемент r пере- мещается влево, пока он не будет ус- тановлен на место с последующим воз- вратом У2 к У1. Продолжая в цикле данный процесс, вплоть до перемеще- ния указателей к маркеру К, заверша- ем процесс последовательной сорти- ровки массива. Пример 2. Конвейерная сорти- ровка альтернативными вставками [23]. Реализуем на Ка алгоритм АЛЬТа – параллельная модификация сортировки альтернативными вставками. Пусть М0: НУ2У1a1 a2 ... anК – начальная раз- метка массива. С указателями У1 и У2 связаны два асинхронных процесса: 1) посредством левостороннего скани- рования У1 осуществляется поиск эле- ментов, стоящих "не на месте", кото- рые засылаются в очередь БС; 2) одно- временно посредством У2 осуществля- ется поиск в уже отсортированном фрагменте массива "места" для вставки элемента из вершины БС. АЛЬТа ::= [{[d(У1, К) . ('БС= ∅)] (['БС ≠ ≠∅] ВСТАВКА, E )} * ТК1 * C(ТК2) // //{[d(У1,К)] ([i >c] ЗАП(c,БС) , P(У1) ) } * * КТ2 * C(КТ1) ] * ИСК(У1,У2), где 'БС ≠ ∅ – предикат, истинный, если содержимое очереди не пусто; i и c – элементы непосредственно слева и справа от У1; ЗАП(c, БС) – оператор записи элемента c в основание очереди БС; ВСТАВКА – циклический оператор поиска (посредством перемещения У2 влево или вправо по уже отсортиро- ванному фрагменту массива) места вставки элемента из вершины БС с ус- тановкой его в найденную позицию. Приведенная ПРС представляет асинхронное взаимодействие двух вет- вей так, что по правой ветви находятся элементы массива, стоящие не на мес- те. Эти элементы загружаются в оче- редь. Параллельно по левой ветви оче- редь опустошается в результате рас- Теоретические и методологические основы программирования 19 становки находящихся в ней элементов по местам в уже отсортированной час- ти массива. Мультиобработка продол- жается вплоть до выполнения конъ- юнктивного циклического условия ле- вого процесса; один из сомножителей этого условия истинен при достижении указателем У1 маркера К по правому процессу. Взаимодействие параллель- ных ветвей осуществляется посредст- вом синхронизаторов и контрольных точек (событий), что обеспечивает синхронное завершение мультиобра- ботки массива. Посредством ПРС мо- гут быть представлены и другие алго- ритмы символьной мультиобработки: конвейерное слияние отсортированных подмассивов, асинхронный распреде- ленный поиск по системам файлов и пр. [20, 23]. 4. Алгебра алгоритмики и инструментальные средства синтеза параллельных алгоритмов Алгебра алгоритмики представ- ляет собой двухуровневую систему. Верхний уровень соответствует неин- терпретированным схемам, а нижний – интерпретациям, ассоциированным с разнообразными приложениями [20]. В зависимости от поставленной задачи, выбранного метода разработки классов алгоритмов, технологической среды программирования осуществля- ется построение требуемой алгебры алгоритмов (АА) из семейства алгебро- алгоритмических спецификаций, по- добных САА-М. Такие семейства опи- сываются в терминах теории алгорит- мических клонов [14]. Сигнатура САА из подобного семейства удовлетворяет теореме о функциональной полноте для данного клона, являясь тем самым, его системой образующих (СО). По- строенная АА может быть исследована на предмет аксиоматизации, разработ- ки систем оптимизирующих транс- формаций, канонизации аналитических представлений и пр. Следующие основные результаты по теории клонов, относящиеся к полу- групповым грамматическим и алгорит- мическим клонам, соответствуют из- вестным семействам АА [25]: • исследованные клоны являют- ся алгебрами континуального типа; • каждый из них включает бес- конечно порожденные подалгебры (с бесконечным базисом и без базиса); • для клона Клини и его обоб- щений построены семейства макси- мальных подалгебр и решена проблема функциональной полноты; • построена поверхность клона Дейкстры и его обобщений, имеющих q выходов из цикла (q = 1, 2, ...); • описана совокупность макси- мальных подалгебр клона Янова, кано- нический представитель которого − ал- гебра Янова; • установлено, что клон Янова − теоретико-множественный предел ис- следованных обобщений клона Дейк- стры; • описана совокупность макси- мальных подалгебр для клона Глушкова и его логической компоненты, система образующих которой включает опера- цию прогнозирования. Важность распространения пере- численных результатов на алгоритмиче- ские клоны граф-схем и их обобщения определяется приложениями теории граф-схем при визуализации объектно- ориентированного программирования [26, 27]. Установлены критерии функ- циональной полноты и выразимости схем в построенных клонах. Получение таких критериев имеет важное практи- ческое значение для реализации инст- рументальных (программных и аппа- ратных) средств проектирования и син- теза алгоритмов и программ, а также их классов, ассоциированных с актуаль- ными предметными областями [20]. Следует заметить также, что приведенные результаты по итератив- ным алгоритмическим алгебрам и их семействам (клонам) ограничиваются двухосновным случаем, сопряженным с анализом операторных и логических конструкций. Вместе с тем имеется возможность их распространения на многосортные клоны, ассоциирован- ные с описанием структур данных [28]. Теоретические и методологические основы программирования 20 Разработанный формализм является универсальным в связи с возможно- стью его применения для проектиро- вания самых различных алгоритмиче- ских моделей предметных областей, в частности при решении задач сим- вольной мультиобработки, а также со- ответствующих языковых и инстру- ментальных средств [26, 27]. Заключение В данной статье была затронута только часть результатов, возникших под влиянием фундаментальных работ В.М. Глушкова по системам алгорит- мических алгебр, которые касаются развития техники алгеброалгоритми- ческих спецификаций для параллель- ных вычислений. Весомость вклада ис- следований академика В.М. Глушкова в развитие компьютерной науки трудно переоценить [29] и со временем она будет только возрастать. Об этом сви- детельствуют тенденции развития ис- следований по теоретическим и при- кладным аспектам алгоритмики по- следних лет [30], а также повышенный интерес к применению автоматно- алгебраических методов к автоматиза- ции проектирования и разработки схемного и программного обеспечения компьютерных систем (см., например, [31—33]). Нет сомнения, что завет В.М. Глушкова поверить алгеброй гар- монию алгоримики будет находить все новые и новые воплощения в будущих трудах отечественных и зарубежных ученых. 1. Дорошенко А.Е., Структура и средства со- временных моделей параллельных вычис- лений // Пробл. программирования. – 1999. – N 1. – С. 38—52. 2. Глушков В.М. Теория автоматов и вопросы проектирования структур цифровых ма- шин // Кибернетика. – 1965. – №1. – C. 3—11. 3. Глушков В.М. Теория автоматов и формаль- ные преобразования микропрограмм // Там же. – №5. – C. 1—10. 4. LogP: Towards a realistic model of parallel computation / D. Culler, R. Karp, D. Patter- son, A. Sahay, K.E. Schauser, E. Santos, R. Subramonian, T. von Eicken // 4-th ACM SIGPLAN Symp. on Principles and Practices of Parallel Programming (PPoPP), SIGPLAN Notices. – 1993. – 28, N 7. – P. 1—12. 5. Valiant L.G. A bridging model for parallel computation // Commun. ACM. – 1990. – 33, N 8. – P. 103 —111. 6. Дорошенко А.Е. Математические модели и методы организации высокопроизводи- тельных параллельных вычислений. Алгеб- родинамический подход. – Киев: Наук. думка, 2000. – 177 с. 7. Капитонова Ю.В., Летичевский А.А. Матема- тическая теория проектирования вычисли- тельных систем. – М.: Наука, 1988. – 296 с. 8. Hoare C.A.R. Сommunicating sequential proc- esses // Commun. ACM. – 1978. – 21, N 8. – P. 666—677. 9. Hansen P.B. Distributed processes: A concur- rent programming concept // ibid. – 21, N 11. – P. 934—941. 10. Keller R.M. A fundamental theorem of asyn- chronous parallel computation // Lect. Notes Comput. Sci. – 1975. – 24. – P. 102—112. 11. Doroshenko A.E. On asynchronous avoidance of deadlocks in parallel programs // Parallel Processing Letters. – 1992. – 2, N 2—3. – P. 291 —297. 12. Глушков В.М., Летичевский А.А. Теория дискретных преобразователей // Избран- ные вопросы алгебры и логики. – Новоси- бирск: Наука, 1973. – С. 5—39. 13. Глушков В.М., Цейтлин Г.Е., Ющенко Е.Л. Методы символьной мультиобработки. – Киев: Наук. думка, 1980. – 252 с. 14. Цейтлин Г.Е. Алгебраическая алгоритмика: теория и применения // Кибернетика и системный анализ. – 2003. – № 1. – С. 8—18. 15. Гладкий А.В. Формальные грамматики и языки. – М.: Наука, 1973. – 368 с. 16. Глушков В.М., Цейтлин Г.Е., Ющенко Е.Л. Алгебра. Языки. Программирование. – Киев: Наук. думка. – 1-е изд. – 1974, 327с.; 2-е изд., перераб. – 1978, 318 с.; 3-е изд., перераб. и доп. – 1989, 376 с. 17. Колмогоров А.Н., Успенский В.А. К опреде- лению алгоритма // УМН. – Т. 13, вып. 4 (82). – C. 3—28. 18. Цейтлин Г.Е. Формальные аспекты струк- турного программирования с GO TO // Про- граммирование. – 1984, – № 1. – С. 3—11. 19. Калужнин Л.А. Об алгоритмизации матема- тических задач // Пробл. кибернетики. – 1959. – № 2. – С. 51—69. 20. Цейтлин Г.Е. Введение в алгоритмику. – Киев: Сфера, 1998. – 310 с. 21. Цейтлин Г.Е., Ющенко Е.Л., Алгебра алго- ритмов и граф-схемы Калужнина // Ки- бернетика и системный анализ. – 1994, № 2. – С. 3—17. 22. Цейтлин Г.Е. Проблема тождественных преобразований схем структурированных программ с замкнутыми логическими усло- виями: ч. 1—3 // Кибернетика. – 1979. – № 3. – С. 50—57; №4. – С. 10—18; – № 5. – С. 44—51. Теоретические и методологические основы программирования 21 23. Цейтлин Г.Е. Языковые структуры и про- цессоры. – М.: Моск. энергет. ин-т, 1979. – 73 с. 24. Кнут Д. Искусство программирования для ЭВМ.– М.: Мир, 1978. – Т. 3. – 843 с. 25. Цейтлин Г.Е. Алгебры Глушкова и теория клонов // Кибернетика и системный ана- лиз. – 2003 – № 4. – С. 48—58. 26. Цейтлин Г.Е., Теленик С.Ф., Амонс А.А. Ал- гебро-логическая формализация в объектно- ориентированных технологиях // Пробл. программирования. – 2002. – № 1—2. – С. 136—146. 27. Цейтлин Г.Е., Яценко Е.А. Элементы алгеб- раической алгоритмики и объектно ориен- тированный синтез параллельных про- грамм // Математические машины и сис- темы. – 2003. – №2. – С. 56—67. 28. Редько В.Н., Гришко И.В., Редько И.В. Деск- риптологическая среда программирования // Пробл. программирования. – 2002. – № 1—2. – С. 7—14. 29. Сергієнко І.В. Інформатика в Україні: ста- новлення, розвиток, проблеми. – Київ: На- ук. думка, 1999. – 354 с. 30. Ноден П., Китте К. Алгебраическая алго- ритмика. – М.: Мир, 1999. – 720 с. 31. Alur R., Dill D.L. A theory of timed automata // Theoretical Computer Sci. – 1994. – 235. – P. 126—183. 32. Generating an Action Notation environment from montages descriptions / M. Anlauff, S. Chakraborty, P. Kutter, A. Pierantonio, L. Thiele // Software Tools and Technology Transfer. – 2001. – N 3. – P. 431 — 455. 33. Gurevich Y. Evolving Algebras 1993: Lipari Guide // Specifcation and Validation Meth- ods / Ed. E. Boerger. – Oxford: Oxford Uni- versity Press, 1995. – P. 9—36. Получено 26.08.03 Об авторах Дорошенко Анатолий Ефимович, доктор физ.-мат.наук, профессор, заместитель директора по научной работе Место работы автора Институт программных систем НАН Украины, просп. Академика Глушкова, 40, Киев-187, 03680, Украина Тел. 266 1538 E-mail: dor@isofts.kiev.ua Цейтлин Георгий Евсеевич, доктор тех. наук, профессор, заведую- щий кафедрой программного обеспече- ния автоматизированных систем Место работы автора Международный Соломонов университет, Киев, Украина Тел. 257 4374 E-mail: tseytlin@vikno.relc.com

Схожі ресурси