Книга: Распараллеливание последовательных программ

Распознанный текст из изображения:

Распараллеливание в широком смысле включает разработку метода параллельного решения задачи и последующее его адекватное представление в виде программы средствами того или иного языка параллельного программирования, На практике программист может заранее пользоваться

предоставленным ему языком и средой программирования, будь то

параллельный Фортран, МР1, функциональный язык и т.п., и попытаться наилучшим образом отразить параллелизм в программе. При этом ограниченные средства языка часто будут сужать границы поиска

оптимальной параллельной программы, например, полностью сохраняющей параллелизм метода решения задачи. В эМом разделе мы рассмотрим

проблему абсолютного распараллеливания последовательных программ и се

решение, основанное на их трансляции в функциональные программы па

языке РРТ1..

4.1. Абсолютно параллельные программы

Обозначим А(р) множество всех историй или протоколов процессов ~3~

возможного параллельного выполнения программы р в соответствуюгцей

процессной модели, которой определяется операционная семантика языка.

Определение. Программа Я называется максимально или абсолютно

Р, если для любой пропэаммы

параллельной в множестве

р, е Р К(р,) ~:. Я р,.) .

Формализация процедуры поиска абсолютно параллельных программ, разработанных на конкретном языке, обычно базируется на использовании бинарного отношения «более параллельная» между программами..

Пусть Р = ~р, ~ ~ =1,2,...) - множество эквивалентных программ, представленных в сигнатуре одних и тех же операций композиции н оазисных компонентов языка.

Распознанный текст из изображения:

На рис 1. изображено множество всех протоколов максимального параллельного асинхронного выполнения условного операто

тора д р(х) Йеп ,~,(х) е/ье ~,(х). На этом рисунке состояние представляет множество одновременно выполняемых компонентов условного оператора, а переходы из одного состояния в другие состояния осуществляются но завершению выполнения соответствующих компонентов в исходном состоянии. Завершаемые одновременно свое выполнение компоненты на переходах заключены в угловые скобки на рис .1. Рис,1. Протоколы абсолютно параллельного асинхронного выполнения условно~ о

оператора

Предполагается, что выполнение условного оператора начинается из начального состояния >„ асинхронного автомата на рис.1 при переходе к одновременному вычислению значений р(х), Л(х), Ях) и заканчивается в состоянии 5'„завершения вычислений. Прерывисто указанные переходы на рис.1 отражают факт ложности условия р(х) при завершении его вычисления

Распознанный текст из изображения:

(в этом случае на переходе указывается вместо р символ р) и фиксируют

альтернативы возможных продолжений вычислений.

Абсолютно параллельное асинхронное выполнение означает, что по

завершению вычисления любого подмножества компонентов р(х),,~,(х),

,~,(х) условного оператора осуществляется переход в другое состояние и

инициализируются сразу все готовые для вычисления другие компоненты и, кроме того, прерываются вычисления компонентов, результаты которых

далее оказываются ненужными. Не завершившие выполнение компоненты

продолжают выполняться в новом состоянии. Часть историй вычисления условного оператора на рис. 1 опущена.

Можно проверить, что протоколы на рис, 1 отражают все варианты следования на временной оси событий одновременного начала и завершения вычисления значении р(х), .~(х), у2(х) при произвольном распределении длительности этих событий, что позволяет говорить об абсолютно параллельном асинхронном вычислении условного оператора.

Любая модель вычислений, которая ограничивает множество протоколов вычисления условного оператора, изображенных на рис. 1, является менее параллельной, чем рассмотренная.

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

действия или одновременного завершения нескольких действий. Если для

первого найдены приемлемые практические решения [18), то проблема

фиксации одновременности не имеет решения по принципиальным

причинам. Поэтому в известных теоретических процессных моделях Милнера [5, б~, Сетях Петри [3], Хоара [) и др. одновременность событий не рассматривается, а возможность того, что несколько действий могут

Распознанный текст из изображения:

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

4.2. Абсолютное распараллеливание последовательных нрограмм Проблема максимального (абсолютного) распараллел ива~ ~ ия последовательных программ активно исследовалась в 70х годах, начиная с основополагающих работ Келлера ~61 и Вальковского (27].

Сама идея максимального распараллеливания операторной (т.е. представимой в виде блок-схемы) последовательной программы удивительно

проста и состоит в одновременном выполнении всех ее операторов по

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

Однако, необходимость в такой модели устранения зависимости между операторами по выходным данным (так называемой конкуренционной зависимости 121), реализация упреждающих вычислений для условных операторов, пример которых мы рассматривали в п. 4.1, настолько усложняет дело, что предложенные в 124,251 алгоритмы максимального распараллеливания теряют практическое значение. По этим причинам лишь локальное динамическое распараллеливание ограниченных участков последовательной программы реализовано в современных компьютерах.

Ниже мы опишем метод максимального распараллеливания

последовательных программ блочной структуры (с целью упрощения нс

рассматривается распараллеливание циклов и др.), который основан на

трансляции их в эквивалентные функциональные параллельные программы на языке гРТЕ, а затем представлении этих программ в виде специального

Распознанный текст из изображения:

вида сетей направленных функциональных отношений, описанного в разделе 3.

При этой трансляции автоматически устраняется несущественная конкуренционная зависимость между операторами последовательной программы по выходным данным (зависимость Оц1(0~) й Оп1(Оз)' -~ й) и

остаются явно отраженные в структуре сетевого представления

функциональной программы только существенные информационные связи между функциями, сопоставленными операторам транслируемой программы.

4.2.1. Сен~еаое представление схем функций

Язык сетевого представления программ разработан в 1дисс. Фалька) в связи с исследованием направленных отношений, частным случаем которых является функции. Сетевое представление является уникальным графическим представлением программных объектов, в котором связи между компонентами программы отражают явную информационную зависимость между ними (см. раздел 1),

Ниже мы введем язык сетевого представления схем функций в ГРТ1, предполагая, что для их построения используется множество символов базисных функций Г=~1~ ~ 1г=1,2, ...1, которое включает подмножество функций выбора аргумента к,, т > О, О < ~' < к и символ Я вЂ” всюду неопределенной функции. Каждая функция 1 из Г имеет арность (т„п,1, т,>0, п,>0 (арность функций выбора аргумента ю, равна (т,1)).

Как и ранее, мы используем общую формулу задания функций в ГРТ1. в виде системы функциональных уравнений х, = г„~' =1,2,...,п. Трансляция этой системы в сетевое представление состоит в приведении к ортогональному

разложению термов г,:г, О+ г, О+...О+г, и построении сетевой контекстносвободной грамматики, Язык этой грамматики порождает множество сетей, которое в интерпретации эквивалентно рассматриваемой системе функциональных уравнений. Множество правил грамматики задается в

Распознанный текст из изображения:

форме х, — +ю(х, ), ~'=1,2,...,н, ~'=1,2,...,й,, для каждого 1, а л(х,. ) — сеть,

являющаяся трансляцией терма х в сетевое представление. Множество

1(

термов грамматики образуют символы базисных функций, входящих в термы т,,~'=1,2,...,л, а множество нетерминалов включает все функциональные переменные системы уравнений.

Любая из переменных х„1=1,2,...,л, представляющая интересуюшую

нас функцию, может рассматриваться как аксиома грамматики.

Сетевое представление ю(г) терма т определяется индукцией по его

построению.

Базисная функция ~ «'"'и я Е имеет сетевое представление

и;

Сеть Л

При т„=О, к„=О соответствующие сети для~ приведены ниже

Сеть

Сеть ~~ "л~

О"":1.Ц вЂ” + ХАТ, лисса'": ХАТ вЂ” + МАТ и функциями деструкторами:

(О ')"'"': МАТ вЂ” > Я, (лисс ')"": ХАТ вЂ” + МАТ. Конструктор о и деструктор

Для примера определим в ЕРТЬ абстрактный тип, изоморфный

натуральному ряду: ХАТ~"'и = О~"'и ) ХАТ~" ~ лисс" и с конструкторами

Распознанный текст из изображения:

о

о являются частными функциями с графиками: о = ((А,О)) и о ~ = ~(О, 'ь))

соответственно.

Функция-конструктор о и деструктор о имеют следующее сетевое

-/

представление:

Сеть о ~

Сеть о

Отметим следующие важные особенности представления сетей, Все общие соединения между элементами сети, в качестве которых выступают представления базисных функций, должны проходить через одну явно указываемую в изображении сети точку. Каждая сеть, аналогично функции в ГРТЕ, имеет арность ~т, и), т>0, и>0 определенную количеством упорядоченных точек, от которых идут линии на ее входы и выходы — на левую и правую стороны сетевого изображения, По умолчанию левая и правая стороны прямоугольника в изображении сети и ее элементов соответствуют входам и выходам сети или элементов, что избавляет от необходимости использования направленных дуг в изображение сетей.

Для т и и равным нулю одновременно есть две сети: пустая сеть без входов и выходов, которая в интерпретации имеет график Я1,Л)), где л пустой кортеж, и сеть, представляющая всюду неопределенную функцию Я с пустым графиком. По умолчанию у Я - пустое множество сетей.

Функции выбора аргумента ю,"' О < ~' < т, изображаются в виде сетей

Распознанный текст из изображения:

Для представления л„вводится пустая сеть, не имеющая входов,

О выходов и элементов, а для ~г„"', т > 0 сеть

Напомним, что сеть Л~ имеет график ЯЛ,Л)), а ю,"', т>0, график ((а,а,...а.,) ~ а, е В), где Р— область значений, которые могут появляться на входах сети,

Сети переменных, входящих в термы, изображаются так же, как и сети базисных функций ~ ~"""', с тем лишь отличием, что в качестве единственного их элемента является представление переменной.

Для функций, построенных путем применения операций композиции ~. ~, — > к другим функциям, их сети строятся как е, ~, — > — композиции этих сетей. Для обозначения операций композиции сетей, соответствующих операциям композиции функций, *, — > мы используем те же самые обозначения.

Последовательная композиция сетей 51' '~ и 5,'"'~ выполняется путем устранения правой и левой граней у прямоугольников изображений сетей 5~ и 5 и соединения одноименных выходов сети 5~ со входами сети 5. с последующим стягиванием в одну точку всех точек на общих соединительных линиях.

На рис. 2 приведем пример последовательной композиции сетей 5~ и 5:

Распознанный текст из изображения:

5, е 5,

Рис. 2. Последовательная композиция сетей Б~ и Я.

Параллельная композиция сетей 5~ и 52 (5, ~5,) выполняется путем МА--Ос,а.к.с.исс., а с ь-'72чч ОАЗ, 52. ~= еалсс 'ъз , соединения одноименных входов 5~ и 5з на левой грани результирующей сети и конкатенации кортежей выходов сетей 5~ и 5; на правой грани результирующей сети с последующим устранением нижней и верхней граней прямоугольников в изображении сетей 5~ и 52 стягиванием в одну точку точек, лежащих на соединительных линиях.

Сеть 5, ~5,

Рис. 3. Пример параллельной композиции сетей.

Распознанный текст из изображения:

При выполнении -+ — композиции сетей 5~ '"'~ и 5~1""'~ аналогично "— композиции соединяются одноименные входы сетей 5~ и 5з, а выходами новой сети становятся выходы сети 5, При этом выходы сети 5~ устраняются при оставлении в результирующей сети выходных точек сети 5ь

Сеть 52 Сеть Я~

Сеть 5, — > 5

Рис. 4. Пример -+ - композиции сетей

Сеть 5~ в — + - композиции представляет условие в -+ — композиции функций, которйе в простейшем случае, как в этом примере, задает функция предикат .~~"~. Далее приведем пример сетевой грамматики (рис. 5) для схемы функции параллельного вычисления и!, приведенной в разделе 3:

Р + у~ О+ Р + НУ "3) х ~ ( ~4 ~ Я х)

Распознанный текст из изображения:

11

Рис. 5. Продукции сетевой грамматики для х

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

Пример ниже иллюстрирует выполнение подстановки сети Ь', вместо элемента, представляющего переменную к в сети 52.

Рис. 6, Подстановка сети о, вместо элементах в сети о.

Несложно проверить, что между множеством порох енных сетей в терминальном базисе, порожденных для любого х; в сетевой грамматике для х, =" т„1=1,2,...,и, и множеством функций в ортогональном разложении к'" при й стремящемся к бесконечности существует взаимно однозначное соответствие. Это позволяет установить равенство графиков функций--

4 наименьшего решения для х,,1 = 1,2,...,п, приведенном уравнении и функции,

Распознанный текст из изображения:

]7

полученной объединением графиков всех функций, сопоставляемых в интерпретации сетям, порожденным грамматикой для х, в качестве аксиомы.

Интерпретация сети, не содержащей функциональных переменных, совпадает с интерпретацией схемы функции, которую она представляет, при условии одинаковой интерпретации символов базисных функций, входя]цих в схему, и элементов, которые представляют эти функции в сети.

Интерпретация 1 сети 5 совпадает с интерпретацией функции, которую

она представляет, и может быть определена в следующей форме [26~:

1(5<™) = Яа, 1э) ! (Л ср: Р— + Р )(а = гр(1п(Я)) л,О = гр(Ои~(5)) л '~',1,ф

((~0(Ь7Я )),(~)(О~и1(1; )) е 1(1; )))

Здесь р;Р— +Π— функция, сопоставляющая каждой точке сети,Р

::'Р

й

Р

с,

значение из не уулевой области О, т(А) и ои1(А) — кортежи значений на

входных и выходных точках сети или элемента сети А, а квантор

означает, что рассматриваются все вхождения 1; элегле]г] ов,

представляющих 1; в сети 5 для всех ~.

Л

При ]том предполагается, что расширение р на кортежи точек

выполняется поэлементным применением д к каждой точке кортежа: ~р(х,х,...х„) = гр(х,)со(х,)...ср(х„). В вышеприведенном определении

интерпретации сети предполагается, что если при заданных функцией р

'3]~']

значениях точек сети хотя у одного элемента, представляющего в этой сети

предикат на его выходе оказывается значение «ложь», оно трактуется как неопределенное значение, в . При этом значение сети считается

неопределенным, если хотя бы одной из ее точек присвоено неопределенное значение в.

' Пусть Л(6,х,) — множество сетей в терминальном базисе, порожден]ых из аксиомы к сетевой грамматики 6, представляющей систем~ функциональных уравнений х, = г, ] = 1,2,...п. Верна следующая теорема,

Распознанный текст из изображения:

14

которые без задержек пробегают по соединительным линиям

соответствующих сетей,

1т,,п,1

2) Элемент сети, представляющий,1, ' ', считается готовым

для выполнения, если на все его входы поступили данные, то есть

означены все его входные точки. Для такого элемента без задержек

начинается вычисление значения ~ (а а ...а ), для кортежа

л ь ь»,

а а ...а. на его входе. После завершения вычислений и получения

л д д, 1

элементы этого кортежа без задержек

результата ф,.,9, ...ф,

.1т,,п, )

передаются на выходы элемента, представляющего Г ' ', и

распространяется по соединительным линиям к другим элементам или

выходам сети. Если результатом вычислений элемента является неопределенное значение о, то значение сети полагается неопределенным. Более

того, с целью экономии ресурсов все вычисления, связанные с данной сетью, и сетями, которые были порождены из нее в связи с

выполнением подстановок, приостанавливаются.

сетей, являющихся правыми частями продукций для х~ в системе

продукций. Порожденные таким образом сети без задержек включаются в процесс вычислений.

5) Процесс вычислений заканчивается результативно, ес.~и всем выходными точкам хотя бы одной сети, участвующей в

3) Поступающие на конечные точки сети (точки, из которых не исходит соединительных линий) значения, отличные от ж, трансформируются в кортежи нулевой длины, присвоенные в качестве значений этим точкам.

4) При поступлении значения хотя бы на один вход элемента сети, представляющего функциональную переменную х~, 1 = К з, я, выполняются все возможные подстановки, вместо этого элемента

Распознанный текст из изображения:

13

Теорема. Для любой одной и той же интерпретации 1 базисных

функций и представляющих их в сетях элементов выполняется равенство:

0 '- 1(5) = 1(зорких, ),1с > О)), зцр(х) — точная верхняя грань х.

ьеай,к, )

Можно легко проверить, что аксиомы 18, 19 и 20 исчисления

эквивалентности функциональных схем, рассмотренного в разделе 3, которые изменяют вычислительную сложность функций, при переходе к сетевому представлению оказываются излишними.

4.3. Модель сетевого асинхронного абсолютно параллельного

вычисления значений функции

Как и при построении модели параллельного вычисления значений

функций, описанной в разделе 3, базисные функции могут иметь неопределенное вычислимое значение в. Например, конструктор о ь

примере определения ХАТ (п. 4.2) получает неопределенное вычислимое значение о на всех элементах МАТ, отличных от О. Поскольку в ГРТ1 рассматриваются только строгие функции, то появление на выходе хотя бы одного из ее элементов сети значения о при вычислениях считается, что выходное значение сети не определено. Также условимся, что если на выходе элемента сети, представляющего предикат, появляется значение «ложьк то

оно трактуется как неопределенное значение и выходное значение сети

считается также неопределенным.

Пусть в системе продукций грамматики, представляющей в сетевой

форме систему функциональных уравнений х, = т, ~' =1,2,...п, нас интересует

процесс вычисления значений функции х~ ""~ для входного кортежа а '=. а,а,...а„, Следующие правила определяют модель абсолютно параллельного асинхронного вычисления значения х,""'" (а) .

1) На все входы всех сетей, являютцихся правыми частями

продукций для х,, поступают одновременно значения а а,,а,,

Распознанный текст из изображения:

15 Г

вычислениях, были присвоены значения в-=-нроцессе=еьвычзислений., х отличные от в.~-,Кортеж выходных значений этой сети является результатом вычисления значения функции. Если процесс вычислений длится неограниченно или если хотя бы одно выходное значение всех сетей, участвующих в вычислениях, оказалось неопределенным, процесс вычисления х,(а) считается безрезультатным (функция х,. не применима к входному кортежу значений).

Требование п.4. данных правил'существенно для достижения абсолютно параллельного вычисления х.(а), поскольку опережающая подстановка сети

! вместо элемента, представляющего функциональную переменную, при поступлении хотя бы одного значения на один из его входов может инициировать новые вычисления.

Пример ниже демонстрирует этот случай, где в сети о на первый вход поступило значение а,, а одна из продукций для х имеет указанный вид, Сеть о'

Продукция дяя х

теореме. Оп~еенный працеаа аетееото еычиапения значении зрун~пнй является абсолютно параллельным, т.е. в нем без задержек реализуется любая возможность выполнения вычислительных актов независимо от длительности вычисления значений элементами, представляющими базисные функции. Для доказательства этого утверждения приведем следующие аргументы.

1) Процесс вычислений является асинхронным, поскольку оы

не зависит от длительности вычисления значений базисных функций и

Распознанный текст из изображения:

16

выполнения подстановок, и эти операции реализуются без задержек,

если есть условие для их выполнения.

2) Вычисление значений базисных функций, представляющих

1 ь

их элементБ~~ реализуется по готовности данных их входах, а,

следовательно, независимо и параллельно.

3) Выполнение опережающих подстановок при поступлении

хотя бы одного данного на вход элемента сети, представляющего функциональную переменную, исключает любые задержки в

«развитии» вычислений на сети.

Для доказательства этого проследим вычисление х;(а) . Если х,.(а) = ф,

то существует наименьшее Й такое, что ~~~(а) = л, причем х, не содержит

~ф ®

вхождений функциональных переменных. Для ортогонального разложения

х =х О+х ~0+...О+к" только одно из О+ - слагаемых определено для а и

~! ~2 ' " 6г

его значение равно 9 . Рассматривая сетевое представление для этого 63-

слагаемого можно осуществить процесс сетевого вычисления для кортежа а на входе этой сети и воссоздать подстановки, которые пришлось бы

осуществить при вычислении значения х,(а). Исключая время, затра ~енное

на подстановки и принимая во внимание, что для любого элемента,

представляющего х., на вход которого поступило хотя бы одно значение,

осуществляется одновременное порождение всех сетей путем осуществления

подстановок вместо к. сетей в продукциях для к., можно увидеть, что этот

./

процесс является полной аналогией процесса вычисления х,(а) для

соответствующей сети, представляющей О+ - слагаемое в ортогональном

разложении х,(а), которое определено для а.

4) При сетевом вычислении х,(а) все фрагменты сети, представляющие

условия, вычисляются с упреждением и параллельно с вычислениями,

необходимость использования результата которых они определяют.

Распознанный текст из изображения:

17

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

4;4. Аосолитное распараллеливание последовательных программ, основанное на их трансляции в функциональные программы

Ниже мы рассмотрим простой случай последовательных программ, представимых в виде блок-схем. Его легко можно модифицировать для случая рекурсивных программ. Однако, программы, грамматики которых являются контекстно-связанными, которые допускают побочные эффекты и др., требуют особого рассмотрения.

Трансляция блок-схем программы осуществляется в два этапа. На первом этапе для блок-схемы строится система функциональных уравнений, по которым затем выполняется построение сетевой грамматики.

Напомним, что блок-схемы программ представляют собой "вязанные графы, построенные из операторов присваивания значений и предикатов, блоки которых изображены на рис. 7. Для простоты мы используем ненаправленные связи, «движение» по которым очевидно:

Рис. 7.

,мхй.

Здесь ' и Р— (т, 1) — арная функция и (и, 1) — арный предикат соответственно. Переменные у; в обозначении функций и предикатов принадлежат множеству всех предметных переменных блок-схемы:

Распознанный текст из изображения:

18 ~ = ~у1,у~,...,уД. Вместо предметных переменных в операторах присваивания и предикатах допускается использование констант.

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

Рис. 8. Пример блок-схемы программы.

Упорядочим все предметные переменные блок-схемы и будем это упорядочение представлять в виде кортежа длины У. Трансляция блок-схемы программы в функциональную схему выполняется путем однозначного сопоставления вводимым на соединительных линиях блок-схемы то ~кам

С~л-» ~,~г~ функциональных переменных х., ~'= 1,2...п, арности (Х, Ж), входному блоку по умолчанию сопоставляется функциональная переменная х„той же

Распознанный текст из изображения:

арности. Операторному блоку (рис. 7) при трансляции сопоставляется

д1~ г'ь ~Щ

~,„=(г, г, ...*г, (г „*...*г ч ~'*~„) ° ~,.„., а~

'1,

функциональные переменные, приписанные входной и выходной то ~кам

функциональное уравнение

блока; гг,, г'= 1,2...М вЂ” сокращенное обозначений функции выбора элемен ге

у, из кортежа у,у,...у, ,. Ц~—

Предикатный блок (см. рис. 7) транслируется в функциональное

уравнение с двумя ортогональными функциями в его правой части,

ч

соответствующи~~ двум взаимоисключающим выходам х,',„и х,"„„из блока:

х,„=(гг, "гг *...~гг .~) р-+х,'„,О+(гг, *гг,, *...*гг~,4) р-+х,','„„..

'2 'н~юю ю '2 ю~у~

Для начального блока входной переменной является х„, для выходного

хю = (ггю ' а * гг, ) ' х!

('гу г" ю ' 'г) '.хг

'Х ' -)'хг

р, — +х, О+гг, р, -+х,

*л ~,) х,

р, — эх„.О+гг р, — +х,

х, =(гг,

к — гг

х,=(~, гг )

Здесь ггю сокращенное обозначение функции ггю. После выполнения

г

ю,ои

ряда подстановок получим упорядоыенн. ю функциональную схему:

х, = (ггю а " гг ) (гг, ггю Ь) °

х, =(:т,,~~гг,) (т,' р, — +х, О+ю, р — +х,)

блока выходная переменная отсутствует,

Рассмотрим пример трансляции блок-схемы на рис. 7 в сетевое представление. Напомним, что константы а и Ь представляются в ЕР77 в виде функций (О, 1) — арных функций,

Построим систему функциональных уравнений для данной блок-схемы. упорядочив предметные переменные в виде кортежа уа:

Распознанный текст из изображения:

20 х4 — (ю:к к /;) ~л' .р, — +х4 ® к р, — +(к ~ Д), Все функциональные переменные имеют арность (2, 2) и функции, которые они представляют, отображают О, х4' ' — +.О, х.0,, где В~ и !Э области значений, которые пробегают предметные переменные у и соответственно,

Сетевое представление данной системы функциональных уравнений приведено на рис. 9.

Рис. 9. Сетевое представлейе блок-схемы программы

Распознанный текст из изображения:

21

При трансляции блок-схем в сетевое представление устраняется конкуренционная зависимость между операторами блок-схем по их выходным данным. Рассмотрим для примера блок-схему программы рис, 10. 01 02 Рис. 10. Пример блок-схемы программы с конкуренционной зависимое ~ вк В этой блок-схеме программы только между операторами О и О, существует непосредственная информационная зависимость, а между операторами О., и О, аааиеимооть конкуренционнаат Фа~а

~а"с~ркуьц 1 а ййс ~ р р тт.Б Ыу-ву р р. с)Чи-

После упрощения системы ункциональных уравнений, полученной при ~.„, трансляции блок-схемы программы, имеем уравнение: лв — (Л ~~К ~К ) (2Г: т ~:к2Г ) (УГ:кК ~К ~) (К:РК ~ т Сетевое представление этого уравнения приведено на рис. 11.

Рис. 11. Сетевое представление.

Распознанный текст из изображения:

22

Из сетевого представления следует, что результат вычисления функции ~,'(у,) несущественен в программе, представленной блок-схемой, однако, если ~г,(уз) окажется неопределенным, результат выполнения программгл также будет неопределенным. Это ясно отражено в сетевом представлении.

Кроме того, из сетевого представления ясно следует, какие операторы в

данной программе независимы и могут выполняться одновременно.

Теорема. Трансляция блок-схемы программы является ее абсолютно— и араллельным представлением.

Это утверждение следует их факта устранения несущественных зависимостей между функциями, представляющими операторы блок-схемы

программы, и оставлении только явно заданных существенных информационных связей, а такие из ранее доказанной теорем ы,

устанавливающей абсолютно — параллельное вычисление значений функций

по их сетевому представлению.