malyshkin_ve_korneev_vd_-_parallelnoe_programmirovanie_multikompyuterov

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

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

288

7.2.3.Выбор алгоритма

Следующий после планирования этап - построение (V,W)-плана

Т. В параграфе 7.1. предложено несколько способов нахождения

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

Для более сложных функционалов следует использовать человеко-машинный алгоритм, с помощью которого человек сможет при необходимости управлять процессом построения Т либо целенаправленно модифицировать ранее сконструированный (V,W)-план. Такая необходимость возникает в тех случаях, когда автоматически синтезированная программа ПT не удовлетворяет человека по каким-либо причинам.

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

алгоритмом выбора.

1.Термы строятся из множества W, т. е. для каждой переменной х W выбирается из множества comp(х) одна из операций, которая вычисляет х, затем выбираются операции,

которые вычисляют те входные переменные ранее выбранной операции, которые не входят в V и т.д., пока не будет построен терм t, вычисляющий х, и in(t) V. Это случится обязательно в силу свойства ТХ и OП (планировщик уже удалил из ТХ и ОП операции, которые не используются для вычисления переменных из W). При выборе операции необходимо, конечно, следить за тем, чтобы построенный терм принадлежал множеству TVW.

2. Для выбора операции могут применяться следующие

289

стратегии.

А). Выбирается произвольная операция, если ее

использование в (V,W)-плане не запрещено человеком.

Построенный по этой стратегии (V,W)-план Т называется произвольным.

Б).Выбирается операция, для реализации которой в мультикомпьютере есть ресурсы. Здесь предполагается, что в ССПП может быть введена информация, описывающая как мультикомпьютер, так и свойства модулей, задающих интерпретацию операций ПВМ, к примеру, требуемый для выполнения модуля процессор. Возможен случай, когда сделать выбор операции не удается (ни одна операция из comp(x) не может быть выполнена на данном конкретном мультикомпьютере), и тогда нужно будет отменить сделанный ранее выбор операции и взять, если можно, другую. Чтобы избежать такой ситуации, исключение операций, для реализации которых в мультикомпьютере нет подходящих ресурсов, лучше делать на этапе трансляции (не включать их в ТХ и ОП).

В). Из всех операций, вычисляющих х, выбирается операция a Fi с минимальным номером i, а если таких несколько — то любая. В соответствии с этой стратегией строятся термы минимальной глубины. Такой выбор можно сделать всегда.

Г). Выбирается операция из comp(x), которая может быть выполнена на том же процессоре pi, что и некоторая другая

290

операция b, которая уже включена в конструируемый (V,W)-план и х in(b). Если такой операции не окажется в comp(x), то в comp(x) ищется операция, которая может быть выполнена на процессоре p2, связанном с p1 коммуникационным каналом, и т.

д. Если выбор операции сделать не удастся, придется отменить ранее сделанный выбор операции и попытаться выбрать другую.

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

Д). Если переменная х используется в одном из ранее построенных термов из Т, в котором она вычисляется операцией

а, то выбирается операция а, а если не используется, но в ранее построенных термах применяются операции b1, …, bn такие, что

х out(b1), i=1, 2, ..., п, то выбирается любая из них. Когда ни одно условие не выполнено — берется произвольная операция из comp(x). Применение этой стратегии приводит к тому, что переменная х всюду, где она используется в термах Т,

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

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

291

ПП, где оно должно быть использовано.

Е). Выбирается любая из операций, использование которых в

(V,W)-плане рекомендовано пользователем, а если таких нет в comp(x), то произвольная.

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

рекомендованных пользователем для использования в (V,W)-

плане .

3. Алгоритм завершает работу, когда построен (V,W)-план Т,

либо выбор операции сделать не удается.

Следующие два замечания дополняют описание этого алгоритма. В процессе построения терма t при выборе операции,

вычисляющей переменную х, алгоритм всегда пытается взять безусловную операцию. Если взять безусловную операцию невозможно, но есть условные операции b1, ..., bn, вычисляющие

х, то для вычисления х в терме t строятся п подтермов t1, ..., tn , top(ti)=bi, i=1, ..., п. Таким образом, в построенном (V, W)-плане будет п термов, которые отличаются друг от друга подтермами,

вычисляющими в них переменную х.

При реализации алгоритма термы следует строить не сверху

— вниз, а, напротив, слева — направо, т. е. строить полностью одну (самую левую) ветвь дерева, представляющего терм t, и

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

292

незапланированных дублирующих вычислений. Предложенный алгоритм, естественно, не гарантирует построения такого (V,W)-

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

1)указать список операций, употребление которых в (V,W)-

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

(V,W)-плане;

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

4)указать переменные и операции, использование которых в

(V,W)-плане желательно;

5)указать стратегию выбора операции;

6)запретить использование каких-либо процессоров мультикомпьютера, т. е. требуется не использовать в (V,W)-плане операций, которые могут быть выполнены только на запрещенных процессорах;

7)потребовать n-кратного дублирования вычисления некоторой переменной х для повышения надежности ПП. В (V,W)-плане по этой директиве появится п подтермов,

293

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

либо модули содержат ошибку, о чем ПП должна выдать сообщение;

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

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

безусловную операции, если из анализа входных данных следует,

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

y

x

294

Рис. 7.20

На рис. 7.20 показана ПВМ. Пусть модуль вычисляющий функцию fа=I(a), вырабатывает логическое значение y=true, если значение х равно 7, в противном случае false, а универсальный модуль moda1 вырабатывает значение

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

иначе false. Операция а описана как условная, т.е., if x=7 then

а(x); Множество TWV, V={х}, W={у}, содержит два терма а(х) и a1(x), могут быть построены два ({х},{y})-плана: T1={а1(x)} и

Т2={a(x),a1(x)}. Тогда программа ПT2 вида

if x=7 then (у:=а(x); go to L); у:=а1(x); L: ...

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

и называть порядок их выполнения в ПП.

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

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

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

295

выбора, а это означает, что надо иметь возможность так локализовать применение этих стратегий (строить с их помощью не весь (V,W)-план, а только, например, некоторый подтерм),

чтобы это не приводило к неприемлемо большому перебору.

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

Для того чтобы можно было реализовать в ССПП группу директив, требующих обязательного использования в конструируемом (V,W)-плане Т некоторых переменных и операций, необходимо несколько модифицировать алгоритмы планирования и выбора. Эти модификации рассмотрим на примере построения (V,W)-плана Т, в котором требуется использовать переменную x.

Пусть в восходящей части алгоритма планирования обнаружилось, что x Vi при некотором i<k (обозначения те же,

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

Невыполнение этого условия означает, что требуемый (V,W)-план

Т просто не существует и ни в одном терме из TVW не используется переменная x. Далее, в восходящей части алгоритма планирования наряду с множеством Fi строится множество

296

Fix ={aÎFi½xÎin(a)}={aÎA(x)½in(a)ÍVi},

затем Vi+1 и Vix+1 ={yÎX½yÎout(a)ÙaÎ Fix },

¹Æ} и т. д. Ясно теперь, что алгоритмом выбора требуемый (V,W)-план Т будет построен, если при выборе операции предпочтение отдавать операциям из множества

F x = Fjx j {i,..., k}

7.2.4.Структурированные операции и их преобразования

В предыдущем разделе рассмотрены основные алгоритмы конструирования (V,W)-плана Т. С их помощью уже можно автоматически либо в интерактивном режиме строить и целенаправленно модифицировать план Т, если реализующая его ПП будет признана неудовлетворительной по результатам тестовых испытаний. Заметим, что эти модификации будут носить “ внешний” характер, позволяя запрещать либо требовать использовать в Т те или иные операции. Изменить же

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

Отметим прежде всего, что для конструирования качественных ПП в ССПП нужно уметь выбирать наиболее подходящий в каждом конкретном случае алгоритм вычисления функции fa=I(а), а не фиксировать его, используя для вычисления

297