Алгоритмы параллельных вычислений и программирование. Бурова И.Г - 86 стр.

UptoLike

ВУЗ: 

СПбГУ | Санкт-Петербург

Составители: 

Рубрика: 

алгоритма. Дополнительные условия, связанные с вычислительной
системой, следует добавить в (2.1). Например, ограничения на чис-
ло каналов связи, на количество типов функциональных устройств
и т.п. накладываются на функции (2.3), (2.4).
Таким образом, задача отображения алгоритмов на вычисли-
тельные системы может быть описана как задача минимизации
функционала T(t), определяемого формулой (2.2) на множестве ре-
шений системы (2.1) с упомянутыми дополнительными ограниче-
ниями.
Обычно это задача гигантской сложности.
Отметим следующие трудности:
— написание дополнительных ограничений вида (2.3), (2.4);
— написание матрицы инциденций;
— решение результирующей экстремальной задачи.
Перечисленные трудности располагаются в порядке возраста-
ния. Матрица инциденций алгоритма практически никогда не при-
водится: ее размеры огромны. Ограничения обычно носят нелиней-
ный характер и невыпуклы. Поставленная задача относится к за-
дачам нелинейного программирования и очень сложна.
Рассмотрим случай, когда не учитываются никакие допол-
нительные ограничения, т.е. предполагается, что система имеет
неограниченные ресурсы и возможности (нечто вроде концепции
неограниченного параллелизма). Тогда задача сводится к миними-
зации функционала (2.2) на множестве, описываемом неравенством
(2.1).
Фактически эта задача эквивалентна отысканию максималь-
ной параллельной формы алгоритма или критического пути графа;
она представляет собой задачу линейного программирования. Дей-
ствительно, добавим к графу G две условные вершины v
0
и v
n+1
. Из
вершины v
0
проведем дуги во все начальные вершины графа, а из
всех конечных вершин графа проведем дуги в вершину v
n+1
. Будем
считать, что операции, соответствующие вершинам v
0
и v
n+1
вы-
полняются мгновенно. Модифицировав соответствующим образом
матрицу инциденций A и вектор реализации h, получим аналогич-
ную задачу, но для линейного функционала T (t),
T (t) = t
n+1
− t
0
.
Теорема 2.2. Пусть задана некоторая вычислительная си-
стема. Если при временной развертке t алгоритм реализуется за
87

Страницы