malyshkin_ve_korneev_vd_-_parallelnoe_programmirovanie_multikompyuterov

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

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

На первом шаге конструирования ПП выбирается некоторый

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

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

множество операций, которые должны быть реализованы на нем.

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

318

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

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

Автоматически сконструированная ПП называется произвольной, это и есть оптимальная ПП относительно какого-

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

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

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

319

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

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

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

320

включении или не включении условных операций в Т, об

обеспечении требуемой степени надежности вычисления каких-

либо переменных и ПП в целом.

321

7.3. ВЫЧИСЛИТЕЛЬНЫЕ МОДЕЛИ С МАССИВАМИ

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

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

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

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

7.3.1.Упрощенные вычислительные модели с массивами

Пусть заданы следующие множества и функции.

1. Множество переменных Х=Х Y, где Х={х, у, ..., z} —

конечное множество, элементы Х называются простыми

322

переменными.

Множество Y — счетное либо пустое; непустое множество Y

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

Элементы массива x ={x1,...,xn,...} называются компонентами

символов (операций). Элемент (а,i)ÎF обозначается ai и

называется i-м экземпляром а. Операция а называется простой,

если Na={nÎN|(a,n)ÎF} — одноэлементное множество, и

массовой, если Na содержит более одного элемента. Функция In

сопоставляет каждому экземпляру ai единственное конечное множество входных in(аi)=In(a,i), а функция Out — единственное конечное множество выходных out(ai)=Out(a,i) переменных,

in(ai)Èout(ai)ÍX, in(ai)¹Æ, out(ai)¹Æ.

Если некоторое свойство выполняется для всех экземпляров операции а, то, скажем, что это свойство выполняется для операции а и наоборот. Будем также говорить, что операция применяется к переменным in(аi) для вычисления переменных out(ai). Индекс i в обозначениях далее будет опускаться в случаях, когда номер экземпляра несуществен.

На множества in(аi) и out(ai) накладываются обычные для

323

программных модулей ограничения, а именно:

1)in(ai)¹in(aj);

2)½in(ai)½=½in(aj)½Ù½out(ai)½=½out(aj)½;

3)множества in(ai) и in(aj), а также out(ai) и out(aj) могут

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

Здесь iÎN, jÎN, i¹j; запись ½in(ai)½ обозначает число элементов в множестве in(ai). Введенные определения формализуют обычный в модульном программировании прием,

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

Набор С=(X,F,In,Out) называется упрощенной вычислительной моделью с массивами. На С обычным образом определяются

понятия терма, множества термов TVW , которое в общем случае будет теперь потенциально бесконечным множеством, (V,W)-

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

V и W могут быть и бесконечными, например V может содержать все компоненты массива x с четными номерами, т. е.

324

{ x [2], x [4], ...}ÍV, VÍX, WÍX, VÇW=Æ.

При интерпретации I УВММ С в области D каждой переменной хÎХ сопоставляется единственный элемент dxÎD

(значение переменной х), а каждой операции aÎF1 — функция

fa=I(а), отображающая соответствующие входные множества в выходные. Рассматриваются лишь те интерпретации, которые удовлетворяют условию I(out(а))=fa(I(in(а))). Здесь I(in(а))

обозначает множество { d x1 , d x 2 , ... , d x m } значений,

сопоставленных в интерпретации I переменным in(a)={х1,...,xm}.

Таков же смысл обозначения I(out(а)). Таким образом,

переменным out(а)={y1, y2, ..., ym} присваивается значение

{ d y1 , d y2 , ..., d ym } терма t=a(t1, ..., tn), а множество термов TVW

определяет множество всех определенных на С алгоритмов вычисления значений переменных W из значений переменных V.

На рис. 7.28a приведен пример УВММ, эта же УВММ показана на рис. 7.28б, на котором массивы для наглядности представлены целостными объектами.

325

7.3.2. Динамические вычислительные модели с массивами

Понятно, что для ограничения вычислений нужны дополнительные средства, которые и вводятся в вычислительных моделях с массивами. Расширение УВММ делается в два шага.

Вначале определяются динамические вычислительные модели с массивами (ВММ), а затем итеративные.

326

Пусть заданы:

1. Множество переменных Х=XÈYÈZ, где Х и Y — те же

множества простых переменных и компонентов массивов, что и в УВММ, а Z — конечное множество переменных, называемых

счетчиками, ZÇХ=Æ, ZÇY=Æ; каждому массиву x Î Y

соответствует счетчик из Z, который обозначается nx .

2. Множество FÍF1´N экземпляров операций, оно определяется так же, как и в УВММ, с тем дополнением, что входные и выходные наборы экземпляров операций могут

" nx ÎZ( n x Ïout(a)& n x Îin(a).);

б) в множестве F существует только одна такая простая операции b, что n x Îout(b).

Счетчики являются особыми переменными, значение

справедливо и для W.

Понятие терма определяется обычным образом. В реализации

327