Книга: Сложность и эквивалентные преобразования параллельных программ

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

3, я,ложность и эквивалентные преобразования параллельных

программ

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

Сложность метода и реализующей его параллельной программы характеризует время выполнения программы и определяется как функция от сложности данных [см. раздел 2), к которым применяется метод или программа, и для многих вычислительных задач [вычисление выражений, решение систем линейных уравнений и др.) такие функции построены. В приведенных в разделе 1 примерах сложность программы параллельного вычисления п1 ведет себя как 0[1оя[п)), сложность параллельного перемножения матриц легко определяется по степени распараллеливания и зависит от их размера. Гораздо сложнее дело обстоит с оцениванием сложности рекурсивных программ, реализующих вычисления по рекуррентным формулам и выполняющих обработку сложных структур данных и

др.

Однако «чистые» математические оценки сложности параллельных методов и программ решения задач не учитывают многие факторы их реализации в конкретной вычислительной среде, где определяющими факторами являются: интенсивность межкомпьютерных взаимодействий и интенсивность обменов между разли ~ными уровнями памяти, алгоритмы статического (предварительного) планирования выполнения параллельной программы и динамического управления процессами и загруженностью на ВС [11, 121.

В этом разделе мы рассмотрим, каким образом можно оценивать временную слоя<ность выполнения параллельных программ на примере их представления в виде функций на созданном нами языке функционального параллельного программирования РРТТ. 1уи»с>1опи! рата!1е! >ур111«г! 1апяис~ь>е) [111], который подробно описан в главе!!1.

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

В п. 3.1 приводится краткое описание основных конструкций, используемых для

представления функций в язьпге РРТ1..

*Пу>якт 3.2 посвящен описанию метода оценивания сложности параллельно~о

вычисления значений.

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

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

Пункт 3,4 посвящен оцениванию сложности параллельных программ путйм

моделирования процессов их выполнения.

3.1. Оценивание сложности параллельных программ, представленных иа

языке БРТД

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

3.1.1. Основные конструкции языка РРТЕ

В Е1>7Х используются четыре бинарные операции композиции, а также системы функциональных уравнений для определенля новых функций из известных функций, В РРП. рассматривщотся типизированные (щп)-арные, т>0, п>0 функции. отображающие кортежи типизированных элементов длины т в кортежи типизированных элементов длины и. Таким образом, любая (щ,п)-арная функция 1о">", имеющая тип 1,1,...1„, ->1',1' ...1,, есть однозначное в общем случае частичное отображение; Г: 13, х 13, х ..хр, -+ Вг хРп х...х 13, где О,

непустое множество элементов типа 1.

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

элементов. Для л> или и равным нулю вводится множество 13 =1,>, содержащее

(О>

единственный элемент, кортеж нулевой длины, обозначаемый й, который

удовлетворяет условию >.и = аХ = а для любого кортежа а .

Все функции в ГРТ~ являются строгими, т.е. значение функции не определено,

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

Неопределенное значе>ше функции в БРТД используется в двух смыслах: оно

:шбо отражает неограниченный процесс вычислений, либо является вычислимым и в

асс чь с~.Ась 94'ам

этом случае ось>рвэкдс';ся о>. Поэтому значение функции не определено, если

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

л ъч,О

неограниченно долго или хвзж-бы гдно из-эзлх лцавезцзй вычислено и имеет

значение с>. Таким образом, предполагается, что каждое множество данных О, типа 1

содержит неопределйнное значение о>.

В РРТТ используется четыре бинарных ассоциативных операции композиц>ш функций: я — последовательная композиция, — конкатенация кортежей — зна >они>3 функции, -> — условная композиция и 9 — объединение ортогональных функций.

Ниже, определяя синтаксис и семантику операций композиции функций. мы используем символы а,р,у, ..., возмо>кно с индексами, для обозначения кортежей; график функции Т обозначается 1': Г = Яа, Р) / Г(а) = р), где > (а) обозначает реэультат применения функции Г к кортежу сс. Мы опускаем указание арности функции там, где в том нет необходимости. Следующий порядок старшинства операций композиции функции: е, *, — >, 0ч-, убывающий слева направо, позволяет далее опускать ряд скобок в представлении функций.

1) Операция последователь>~ой композиции (~)

1оын = 1","л> в1„цл> Г = 1(а, 13) ! ВУ((а, У) ~ Г> ж(У, Р) е Г>)),11а) = 1;(1',(а)).

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

2) Операция конкатенации кортежей-значений функций (я):

!ч""'"ч "'""-'' = ! "" " ' я Г„'"и"-'! à —. ((а Ц),) ! (а (3 ) и Г, л

(сс,/Зе) и Г,); Г(а) = Г (а)Гз(и).

3) Операция условной композиции;

Го"'"' = 1","""" — ь Г,'"'"',Г = ((а,!э) ! (о.,р) и Г, л Зу((а,у) и Г)),Г(а) = Г(а), если значение Г (а) определено; если Г (а) или Г,(а) = оз, то Г(а) = со, если процесс вычислений Г,(а) или Г,(а)длится бесконечно, то вычисление значения Г(а) также продолжается бесконе шо.

4) Операция объединения графиков ортогональных функций (0ь):

Г'"'"' =Г,'"'"~ Оь Г„"'"',Г(а) = Г(а)нГ,(а);Г(а) = Г(а) или !(а) = !(а) в

зависимости оттого, определено ли значение Г,(сх) или Гя(а) соответственно.

Напомним, что две функции Г~ и Гз ортогональные, если пересечение их графиков

пусто.

С вычислительной точки зрения только для операции последовательной композиции требуется строго последовательное вычисление значений функций, к которым она применена. Для операций я и — ь значения функций могут вычисляться в любом порядке, в том числе параллельно. Для операции О+ вычисление значений соединяемых ею функций должно осуществляться параллельно или квазипараллельно, т.е, вычисление последовательно значений функций Г,(а) и Гз(сс) не гарантирует получение результата. Е!апример, если процесс вычислений Гз(а) длится неограниченно, а значение Г,(а) определено, то, начав с вычисления Гз(сс), мы не сможем получить ожидаемый результат (некоммутативный параллелизм, см. раздел 1). Такие функции называет параллельными (21], и вычисление их значений требует применения изощренной техники при построении последовательной программы.

ТРТТ. досчагочно выразителен, чтобы в нем можно было представлять параллельные функции. Например, известная в телефонии функция голосования Г(хн х, хз), которая определена в том и только том случае, если определена любая пара ее аргументов и они равны, является параллельной и имеет следующее представление в гТТТл (дз яд„') яес) -+ дз О+(д,э ~~тз) еео — + ж, О~(дз *тз) вес( — э д,',

3 3

где д,,ггз,п, - функции выбора аргумента: д, (х„х„,...,х,„) = х„и ец(х, у)— предикат, который определен, если х = у, и не определен в противном случае.

Интересно провести параллель между понятием информационной независимости

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

ГРТТ..

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

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

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

Общей формой задания функций 'в РР77 являются системы функциональных уравнений: (*) х, = т,,1=1,2,...,п, где х, — функциональная переменная, т, — терм той же арности. что и х, .

Пусть Х и à — множества символов функциональных переменных и базисных функций соответственно. Для их обозначения используются символы х и 1' с возможным их индексированием, приписываемым снизу или сверху. Неявно предло:шгается, что каждая функциональная переменная или базисная функция имеет заданную арность.

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

При любой интерпретации функциональных переменных как строгих функций. термы одной и той >ке арности образуют частично упорядоченное множество относительно операции включения их графиков, и каждая цепь функций в этом множестве имеет точную верхнюю грань. Наименьшим элементом этого множества являешься нигде не определенная функция, которую мы обозначаем 9'"'"', т>0, п>0. При этом условии и предполагаемом упорядочении данных: о> < с1 и г( < г) для любого г( Е П (Р— непустое множество данных) операции композиции функций являются монотонными и, оолее того, непрерывными относительно введенного частичного порядка (14, 15). Как следствие, любая система функциональных уравнений (*) всегда имеет наименьшее решение, которое может быть определено явно, как точная верхняя грань цепи функций: х~~ '> = гх>~~~ ! х, ~) = 1,2,.,п)т, ([х>~~~ ! х,

1,2,.0р>1т, — результат одновременной подстановки термов х>~ ~, 1 = 1,2,...,п, вместо всех вхождений переменных х„в терм т,). Этот результат мы используем далее в п. 3.2 для определения сложности параллельного вычисления значений функций.

Язык РРТИ создавался с целью формализации общепринятой математической нотации задания функций и одновременно явного отражения параллелизма вычислений в этом задании на основе свойств операций композиции функций. Следующий пример иллюстрирует типичное задание рекурсивной функции:

1Г р, (х, у) 11>еп Г, (Г(х, у), 1; (у)), Р(х, у) = 1Г р,(х, у) 11>еп Г,(х, у),

1Г рз(х, у) 11>еп Р(Г, (х, у), у),

которое имеет следующее схемное представление в РРТТ: Р (Р~ +(Г*п, 1„) Г,)б (Р +1>)О+(Р> +(Г4 ~л> )~Г) при той >ке интерпретации символов базисных функций, что и в исходном задании функции. Схема функции позволяет не только наглядно отобразить структуру функции, но и параллелизм вычислений ее значений, являющийся следствием аппликативных сйойств операций композиции.

Несколько слов необходимо сказать о задании в БРТД базисных функций. Для

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

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

функции-конструкторы и функции-деструкторы (обратные функции), вводимые при определении абстрактного типа. Например, мы можем определить в РРТЕ как абстрактный тип данных множество для представления натуральных чисел ь)АТ:

, где введены конструкторы О ' и зпсс ' '

<о и )а,)) )а,)),, пш )а,п

указанных арностей, так чтоф(2) = О, зцсс(х) х з"сс. Одновременно [й- неявно'~-

вводятся сопровождающие их функции-деструкторы; (О )' ' ' и зцсс ' ' такие, что

-) п,о)

О (х) = )., если х = О и О ) (х) ='аэ в противном случае; ь асс )(х) = у, если х .= у о

зпсс и ьцсс (х) = аа, я противном случае.

Множество, содержащее введенные при определении абстрактного типа данных

А)АТ конструкторы и обратные к ним функции-деструкторы, а также всегда

о~

включаемые в это множество неявно функции выбора аргумента

О < ) ( т, образуют полное множество базисных функций в том смысле, что любая

вычислимая на ХАТ функция может быть определена в РРТЕ [14,! 5,281.

В РРТЕ символы а) и ). используются также для представления истинностных

значений кистю)а» и вложь» соответственно, что легко объясняет интерпретацию

предиката еа) в рассмотренном выше примере.

Например, функция факториал на Л)АТ может быть определена в следующей форме: х =О О зцссОч-()г) озг)сс х) Г„„, гдето(х,у) = хху (мы не раскрываем далее рекурсивное определение функции 1;,„,).

3.1.2. Модель параллельного вычисления значений функций в РРТЕ

Мы рассмотрим модель параллельного вычисления значений функций, которая впервые была описана в [12) и которая была положена в основу одной из параллельных реализаций РРТЕ на кластерах [14, 15]. Эта модель основана на определенных правилах свертывания и развертывания деревьев, которые представляют состояния вычислительного процесса. Модель отличается от модели абсолютно параллельного вычисления значений функций, которую мы рассмотрим в разделе 4 и которая позволяет осуществлять опережающие подстановки вместо функциональных переменных при вычислениях.

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

Пусть задана система функциональных уравнений (о) х, =т,,) =1,2,...,п, и пусть нас интересует процесс вычисления х,"""(а) для некоторого кортежа и, где х, )-я координата кортежа — наименьшего решения системы уравнений (о).

"Процесс вычисления значения функции представляет собой конечную или бесконечную последовательность изменения состояний, каждое из которых является размеченным деревом, листья которого помечены символами кортежей данных или символом неопределенного значения а), а другие вершины дерева помечены сь(мволами операций композиции функций или термами. Деревья, состоящие из двух вершин, у которых лист помечен некоторым кортежем данных а, а вершина— символом одной из переменных х„[=1,2,...,п, ассоциируются с начальными

состояниями, отража)ощими первое состояние в вычислительном процессе значения

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

х(и). Одновершинные деревья, помеченные символом одного из кортежей данных

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

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

х, т,

грт2

о

т~ Лт, Де!*,— ~,О~-)

отз

Т а

Рис. 3. !. Правила развертывания деревьев

2. о

о

3.

с е

„о~ о»

в б.

Рис. 3.2. Правила свертывания деревьев

На этих рисунках ц обозначает произвольное дерево — состояние вычислений.

' о !3, если 1(а )= ~3

::Э (, : опэ,иначе

Р

оп а о~ ц

7 ДЕ (»: — «!

Р,

о го

" оз

— > (

ао оп

О+

.!Х

ась оп

у'

-) .ПО,

ао сиз

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

Параллелизм вычислений в данной модели заключается в возмо>кности применения сразу нескольких правил к неявным поддеревьям дерева — состояния вычислений.

Уточним асинхронный параллельный характер модели вычисления значений функций, для чего рассмотрим моделирование свертывания и развертывания деревьев на идеализированной ВС с неограниченным количеством вычислительных узлов — компьютеров в ней. Все компьютеры системы работают по одной и той же программе интерпретатора, получая задания на вычисление друг от друга и применяя к соответствующим состояниям правила свертывания и развертывания деревьев. Каждый компьютер находится в одном из трех состояний: свободном, ожидания результата и активном — выполнения вычислений. Вычисление значения х(а) начинается направлением этого задания одному из свободных компьютеров ВС (начальному компьютеру). Вначале все компьютеры находятся в свободном состоянии. Действия компьютеров состоят в следующем. Если компьютер получаег задание х,(и), он переходит в активное состояние и выполняет правило 1) развертывания дерева вычислений и переходит к выполнению задания х,(а). Если т, имеет вид, указанный в правиле 2), то компьютер формирует задание т>(а) и передает его для выполнения одному из свободных компьютеров ВС, а сам продолжает выполнения задания т>(а). При этом при отправлении на другой компьютер задания оно однозначно идентифицируется, и на отсылаемом задание компьютере сохраняется контекст — дерево-состояние вычислений и место на эгом дереве, куда должен быть помещен результат выполнения ранее отосланного задания.

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

Если компьютер получает задание т(и), где т = т, ° т,, то он применяет правило 3)

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

его результата — к выполнению т (а).

Процесс вычисления значения х,(а) считается успешным„если на начальном

компьютере получен результат — одновершинное дерево, помеченное кортежем

Р(х (а) = Р)

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

Гакил> образом, в описанной модели вычислений значений функций параллелизм операций композиции функций: *, ->, и Оч. реализуется путем одновременного вычисления на разных компьютерах ВС значений термов, соединяемых этими оцерациями. Кроме того, не откладывается любая возможность применения любого ~>равила свертывания и развертывания деревьев, при этом не накладываются какие- либо ограничения на длительность применения любого правила (асинхронность модели).

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

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

3.1.3. Сложность параллельного вычисления значений функций

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

вычисления значений функций, заданных на РРТ/.

Будем исходить из общей формы задания функций в РРТЕ в виде сне~ем

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

построения наименьшего решения системы уравнений (*) как точной верхней ~рани

последовательности функций-приближений х~ ',1=1,2,..., и, к > О, где х, ' = 0 (нигде

ьэ зп

неопределенная функция) и х~~'' =[к~~'!х,))=1,2,...,п)т„1=1,2,...,п, где правая

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

вместо вхождений переменных хл ) = 1,2,...,и, в терм тп

Представим хоо в эквивалентной форме в виде ортогонального разложения;

х,'~' = х'~~ Ое х~~ О ... Оч- х~~~, где термы х, не содержат вхождений операции

'3 ч,

композиции Ое.

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

п, 3.2):

А е (В Оч- С) = А е В Оч- А е С,

( В Оч- С) е А = В е А О С е А,

А ~(ВЗС) = А ' ВОе А еС,

(В О+ С) е А = В * А Ое С * А,

А — +(ВОч-С)=А — >ВОА — +С,

(ВОч- С) — э А = В-+ А ОС-+ А.

Здесь А, В, С вЂ” произвольные схемы функций. Заменяя последовательно в любом терме т вхождения левых частей этих аксиом на их правые части, мы получим ортогональное представление т .

Определим сложность параллельного вычисления значений функций х,~~ в этом разложении, полагая, что сложность с11) любой базисной функции Т задана. Эта сложность характеризует время вычисления значения функции Г, которое считается одинаковым при применении функции к любому ее аргументу из области ее определения. Для всюду неопределенной функции 0 С(0) положим равным О.

Следующие формулы позволяют определить' время параллельного вычисления

любой функции, построенной композицие1й ее базе)вых функций:

!

В 1151 вместо операций композиции — э иОе была введена тернарная операция. эквивалентная традиционному способу задания условного оператора. Хотя это уменьшает выразительную силу языка с позиций представления параллельных функций, тем не менее, позволяет ввести простые формы схемного представления функций, существенно упрощающие реализацию языка на многопроцессорных ВС с общей памятью. Описанный процесс параллельного вычисления значений функций достаточно просзо описать средствами нитевого (пш1111геайпд) параллельного программирования, что, в принципе, мы использовали при реализации языка ГРТТ на многоядерных компьютерах ~15).

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

1. С(т~ т> ) = с(т ~ ) -«с(т> )

2.с(т, ' т,) = >пах(с(т,),с(т>))

3. с(т, — «т> ) = шах(с(т, ), с(т> )).

Здесь т, и т> — произвольные термы, построенные из базисных функций путем

применения операций композиции»,» и — «.

Рассмотрим пример функции вычисления и! елением отрезка (1, и] пополам,

которую мы уже приводили в разделе 1.

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

х =(р — + Г,) О«р — «((Г> »1,)»х»(Г»»Г>) х)»Г»,где

Г,(х, у) =

2

р (х, у)=-х = у,

Г(х,у)=1,

Г,(х, у) = у,

Г>(х, у) = х, 16(х,у)= хху.

1 ° (

Г>(х, у) =

2

:1 = Ф-~

Легко проверить, что х = р — + Г, Ю р — «((Г> » Гз)» Я *(Г4 * Г,)» к> )» Гь,

>~ и>

х =р — +1, От р — +((1, »1.)»(р — +Г )»(Г~ »Г,)»(р — «Г ))»Гь Оьр — «((Г, »Г>)»

(Р + Г>)* (Г» *Г>)»(Р «(Г> "Гз)» к> *(Г4 *Г>)» и> )» Гь)» Гь О«Р +ИГ "1>) '(Р

((Гз *Гз)' Я»(Г> »Г>)» Я )'1»)»(Г, ° Г>)»(Р-+ Г,))'Г, О+(Р-«(1> *Г-)'(Р-«И1 "

1;)» О '" (Г> "1> )» О )» Г»)» (Р «(Г» *1> )» ИГ> » Г>)» ~ "(Г4» 15)» ~ )» Гб)» Гб.

Рассмотрим, каким образом можно на основе этих формул определить среднее

время вычисления значений определяемых системой уравнений (») функций >ш

области их определения. Сначала рассмотрим случай определения времени

параллельного вычисления значения функции — наименьшего решения для х„(.=

1,2...п в (») на заданном кортеже а а Р(х,), где 0(х,) — область определения х,.

)

Очевидно, что в последовательности приближений хио должно существовать

зс»1) 2.,

ав»>

такое минимальное К»»„, зависящее от и, что значение х, "'"'(а) определено и

х~~~(а) для к<1с»»» не определено. Это следует из того, что последовательность

приближений' х~",)с й О, образует цепь неубывающих функций относительно

отношения включения графиков функций; х~~> ~х~ь'Л для любого1>0. Также

очевидно, что в ортогональном разложении х~ """' =хги»» О«х~ """' О«...О«х~ """'

только одно из О«-слагаемых определено на а и сложность его вычисления для и

можно определить по приведенным формулам. Эта сложность является нижней

гранью сложности параллельного вычисления х,(а). Из этого следует, что всегда

можно на конструктивно заданной области определения любой функции определить

верхнюю и нижнюю границы ее параллельного вычисления, что часто является

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

временным ограничениям.

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

к

19 ОСР) =:

Сложность вычисления х(1, 1) определяется по формуле: С(р — +1, ) = и!ах 1С(р), С11!)); сложность вы !исления х(1,2) — по формуле: 3г, ЕЗ) = 3с [2,) =

с2э

С (р — +((1з *1з) е 1р — + Г )* (1я ~Гз)~(р-+т!))~1ь) = и!ах 1С(р), и!ах 1(гпах»С(Я, С(1з)) ' !пах (С(р), С!1!))), ~!пах»СГ1;), С(1з)) ч- гпах 1С!'р), С(Г!)))) т С(1ь).

Если задано распределение вероятностей 9(а), о. е Р(х,), вытекающее из частоты применения х, к а, то среднее время т!'х,) вычисления значений функции х, на Р(х,) можно определить по формуле: цх, ) = 2»1»гь) х ~(й(х,, а));

аео(ч ~

где а(х,,а) — функция, которая опреде ет для заданного а указанное ранее Ож— слагаемое в ортогональном разложении х„которое определено на а .

Возможен другой, вероятно; более практичный способ определения среднего времени параллельного вычисления значений функцйй, который был разработан для оценки среднего времени выполнения последовательных программ и который основан на знании вероятности истинности условий, определяющих разветвления и циклы в программе 129). Для примера рассмотрим блок-схему программы вычисления у =',! а, на рис. 3.3.

~=! Оь

и Рг!с. 3 3 Блок-схема программы вычисления у = ,'! а,

!=!

Очевидно, что для любого и >1 условие ! > и выполняется один раз, а ! < п — и

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

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

11

! и

и — соответственно. Если задана область значений, которую

пь1 пь1

пробегает и при выполнении данной программы и распределение вероятностей

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

истинности предикатов|> и и 1< и.

равны

Ч, х(14+1,-ь1,

Слагаемое ' ' ' ' +г, есть результат вычисления ряда

! — Ч,

~ с1, х(! — с~~х((14 - 14+ с,.)х !с чс,),определяющего среднее время

с=о

выполнения программы, начиная из точки хз. Это время получается

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

начинающегося в хз и заканчивающегося оператором Оы и вероятности

прохождения по этому пути при выполнении программы.

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

3. ! легко построить следуюцсую систему автоматных уравнений:

х, =О,;х,, х, =О,;х„

Х4 =04',х4

х, =О,;х„ х, =О,.

г,

здесь сэупредйкаг ! > 4ь-и О, 1<п;х~ — неявно вводимая функциональная

переменная для начального блока блок-схемы программы, О+ выполняет роль операции обьединения нет~рай ~ыпо~~ения программы, ; — последовательная композиция (операция следования в языке регулярных выражений). Разрешая эту систему уравнений относительно х„ мы получим регулярное выражение, задающее ьсно>кество всех путей, которые фиксируют истории выполнения блок-схемы йрограммьс на рис. 3.3.

Однако процесс определения среднего времени выполнения программы можно

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

Например, если данная программа применяется 25 раз к и, равному 5, и 30 раз к

и, равному 6, и 0 раз к остальным и, то вероятность нахождения в цикле прп

5х254-6х30 41

выполнении программы равна Ч, = = —, а вероятность выхода из

бх25ь7х30 52

11

цикла равна Ч, = —. Задав время 1„1 = 1,2,...,6, выполнения каждого оператора О, в

52

этой программе (1, = С(О,)), мы можем определить среднее время ее выполнения при

41, х(сз +14 4-14)

заДанных УсловиЯх по фоРмУле С,, =1, +14 +

ьс

Ч~

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

12

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

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

Упростим вышеприведенную систему

рассматриваемо~ о примера блок-с

автоматных уравнений для

хс — — О,;О>,'х,,

х„= О„'О, Оч О,:О,.;О;;х,.

олнения начать

из точки х, ее блок-схемы.

1(х,) =1, Ч-1, Ч. 1(х„)

) 1(О )х(1 )ьг)(О )х(1

где ц(О) — вероятность истинности предиката О.

Разрешая эту систему относительно 1(х,), получим среднее время выполнения

программы.

Программа на рис. 3.3 может быть преобразована в эквивалентную параллельную

программу на языке ГРТЕ (см. раздел 4):

х, =(1, *Г>) ~ х,,

х =(я> я Р— >(1> "14)) я х, Оэ тс> Р— «я>,

где>,(х,,х,)=0,>з(х,,х,)=1;>,(х„х,) =х, +а(х,),14(х,,х,) =х, +1,

р(х) -=х < и, р(х) =-х > и.

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

1(х,) = шах(С(Т, ), С(Г, )) -ь С(х, ),

1(х, ) = г)(р) х (>пах(С(л', ) ь С(р)), шах(С(Г,), С(Г„)) ч- С(х, )) ь ч(Р) х глах((С(л ) ч

С(р), С(л, ) ) .

Однако рассмотренный метод пригоден для определения среднего времени

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

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

Пусть снова рассматривается общая форма задания функций в виде системы в

общем случае рекурсивных уравнений х, = т„1 = 1,2,...,п. Заметим, что любая

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

форме. Точная верхняя грань цепи функций (хоо ~ 'к>0 ) определяет наименьшее

!

решение для х, относительно включения графиков функций. Как уже

рассматривалось, хоп можно представить в виде ортогонального разло>кения),

х Г" = х"' Ог х'" О ... Оэ х~", где г,(1с) — неубывающая функция от 1с.

и ',по

Перейдем от системы автоматных уравнений к системе числовых линейных

уравнений

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

14

значение р(а) истинно, и ложно в противном случае. Напомним, что значение

нложь» предиката обозначается в РРТЕ как ш.

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

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

3.2. Сложность и эквивалентные преобразования параллельных программ

Формализация последовательных программ, начатая Ляпуновым А.А. и его

коллегами и учениками в 60-х годах прошлого столетия, дала мощный импульс как

становлению теории, программирования, так и практике построения оптимизации

программ. При этом время выполнения и требуемая память являлись (и продолжают

0 являться) основными критериями оптимальности программы. Школами Ершова

1»)з ~." А.П, и Потосина 13,4) была проделана огромная теоретическая работа по созданию

0

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

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

Полученные в этих исследованиях результаты не утратили своего значения и

сегодня и активно используются при компиляции и оптимизации, в том числе параллельных программ. вЧистка» циклов, вынесение общей части вычислений в ветвях условного оператора за его пределы, преобразование рекурсивной программы в итеративную циклическую форму и др. — хорошо известные любому программисту приемы оптимизирующих преобразований последовательных программ. Есть и более изощренные оптимизирующие преобразования, выполняемые компилятором и скрытые от программиста.

Сохранение наследия последовательного программирования заставляе~ искать

эффективные методы распараллеливания последовательных программ. В разделе 4

мы рассмотрим, какой ценой оборачивается попытка абсолютного

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

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

распараллеливание выражений и регулярных циклов 1) 91, в которых, как показывает

статистика, сосредоточена большая часть параллелизма и для которых сегодня

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

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

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

компилятор мог выполнить распараллеливание. Мы уже приводили пример

и

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

~ы

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

параллелизм, анализируя информационную зависимость между операторами,

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

!5

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

Нужны более изощренные приемы вычисления 2'а, путем разбиения интервала

и п~ пэ и

[1+п~ на подынтервалы ,'~ =~а, ч- 2 а, +...+ ,'~а,, отраженные

~=пни

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

С формальной точки зрения любое преобразование программы логично

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

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

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

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

3.2.1. Исчисление эквивалентности функциональных схем

Напомним, что две функциональных схемы А и В эквивалентны, если для любой интерпретации ир входящих в них символов функций, рассматриваемых как функциональные переменные графики функций пд(А) и д(В) равны. Для обозначения эквивалентности А и В используется запись А = В. Построение исчислений эквивалентности функциональных схем имеет свою историю развития, начиная с формализации эквивалентности итеративных функциональных схем 1301 и заканчивая рекурсивными определениями функций в виде систем функциональных уравнений [31].

Следующие аксиомы имеют в некотором смысле фундаментальный характер; в

них А, В, С вЂ” произвольные схемы; Π— символ всюду неопределенной функции;

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

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

1б

1.А.(В.С) =(А. В).С

2. А е О = 0 е А = О

3. А е е = е е А, где е = л '," * л'„" е ... е л'„",, гп > 0

4. (А Оч- В) Оч- С = А О (В Оч- С)

5.(А»В)»С=А ' (В»С)

б. (А -+ В) -+ С = А -+ (В -э С)

7,А» О =бе А= О

8. А — э 0 = О -+ Л == О

9.АОч- О = ООч- А = 0

10.А — + А =А

11. А е (В ОЧ. С) = А е В ОЧ- А е С

12. (В Оч- С) е Л = В е А Оч- С е Л

13. А — э (В Оч- С) = А -+ В Оь А — х С

14. (В Оч- С) — э А =  — э А Оь С -+ А

15. А е (В Оч- С) = А е В Оч- А е С

! б, (В О» С) е А = В е А Оч- С е А

17 Ае( — эС) =А»  — эА»С

18,(А — эВ) »С =А — >В еС

20.(А~'"''ч' » А~в»з~) е(л"+"з е В »лч'"з е В,) =А е В »А, ° В,.

При доказательстве эквивалентности схем используется правило замены:

А=В

, где [Х/У~У обозначает результат замены вхождения схемы т' в

[А, (3)С = [В113]С '

схему 2 на схему Х.

Свойство ортогональности функций А и В имеет место, если А — э В =О. Для ортогональных схем А и В верна также эквивалентность А е В = О, которая может рассматриваться как другой способ формального определения ортогональности. Предполагается, что функция О ортогональна по отношению к любой другой функции. Конструктивно отношение ортогональности можно определить в языке, включив в множество базисных функций некоторое подмножество базисных ортогональных функций, обозначая (' и Г базисную функцию (' и ортогональную к ней функцию 1, Ясно, что предикаты р и р могут рассматриваться как о)этогональные функции, если значение аложьв обозначать символом неопределенно~о значения ж .

На основе этого можно определить достаточно представительный класс ортогональных функций следующим образом, Если А и  — ортогональные схемы (функции), то АеС и ВеС, Се А и С»В, А»С и В»С, С»А и С*В, А — эС и В -+ С, С вЂ” э А и С -+  — пары ортогональных схем (функций).

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

!7

Используя дополнительно аксиомы А — + В = 6 и А а В = 6, как выражение отношения ортогональности А и В, можно упрощать схемы функций, приводя их к оптимальной форме. Однако принципиальное значение для приведения схемы функции к минимальной форме с точки зрения параллельных вычислений значений функции имеют аксиомы 17-20, при этом их правые части не более сложны, чем левые.

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

Гр, -+Г )е(р, — эГ, Оч- р, ' — х1',)Оч-1р, -+(Г як,')) (я, 'Г, як',). Применяя аксиомы 11, 17, 18, 20 и правило замены, получим эквивалентную схему с минимальным временем вычисления значений сопоставляемых ей в интерпретации функций:

Р~ э Г~ ~ Р— > Г~ е Г, Оч Р~ + Г~ Я Рз -+ Г, ~ Гз Оч Р~ +1, ~ Г4.

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