Н.Б. Толпинская
2
родная. В последнем случае вес вершины — это множество времен
выполнения оператора на процессорах соответствующего типа.
При выполнении распараллеливания специально оговаривается
логическая структура задач. В частности, будем считать, что если ал-
горитм содержит циклы, то либо для рабочей части цикла вопрос рас-
параллеливания решается отдельно, либо цикл должен быть развернут.
Кроме того, можно предположить отсутствие в схеме алгоритма логи-
ческих операторов, так как статическое распараллеливание чаще всего
выполняется для множества крупных взаимосвязанных задач, состав
которых не меняется в течение длительного периода времени. Тогда
схема алгоритма, где эти задачи фигурируют как отдельные операто-
ры, может иметь малое количество ветвей или вообще одну ветвь.
К тому же, при поиске точных планов параллельной реализации опе-
раторов необходимо оценить все действительные варианты совмест-
ного выполнения операторов, т. е. предусмотреть все значения логи-
ческих переменных.
При указанных выше ограничениях проблема распараллеливания
сводится к одной из двух задач:
1) для заданного комплекса информационно взаимосвязанных
работ, представленного графом
G
= (
X
,
P
,
Г
), и для заданного ограни-
чения на время выполнения этих работ
T
(
T
≥
T
кр
, где
Т
кр
— критиче-
ский путь в графе
G
) выбрать комплектацию вычислительной систе-
мы (в случае однородной системы задача сводится к поиску мини-
мального количества решающих устройств);
2) найти план выполнения заданного комплекса взаимосвязанных
работ за минимальное время на заданной вычислительной системе.
Решение первой задачи для однородной вычислительной системы
и множества работ, заданных графом
G
= (
X
,
P
,
Г
), сводится к рас-
пределению множества взаимно независимых операторов по процес-
сорам и закреплению их во времени. Взаимная независимость опера-
торов определяется, исходя из информационного графа
G
с учетом
задающих связей, определяющих передачу данных между операто-
рами, и транзитивных связей. Транзитивные связи введены направ-
ленно между всеми парами операторов, не объединенными задаю-
щими связями и входящими в один путь в графе
G
. Транзитивные
связи полностью определяются задающими связями.
Множество взаимно независимых операторов (ВНО) включает
группу операторов, которые потенциально можно выполнять одно-
временно, т.е. параллельно. Однако временные характеристики части
операторов, входящих в одно множество ВНО, могут не допустить
параллельного их выполнения. Кроме того, разные множества ВНО
могут иметь непустое пересечение. Значит, возникает вопрос: с опе-
раторами какого множества ВНО эффективнее выполнять операторы,
