- 4 -

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Преобразование, связанное с исключением цикла может состоять, либо в "разворачивании" цикла, если параметр, задающий число выполнений цикла, является константой, либо в объявлении цикла сегментом, вес которого определяется при максимально возможном значении параметра цикла. Из отсутствия циклов в преобразованном алгоритме следует, что в соответствующем ему графе нет контуров (путей, начинающихся и заканчивающихся в одной вершине). Логические операторы определяют переходы на взаимоисключающие ветви программы и задача распараллеливания может быть решена для каждого такого варианта в отдельности. Если время выполнения каждой из ветвей мало, то целесообразно объединить логический оператор и ветви программы, порождённые им, в один сегмент, вес которого определяется исходя из максимального времени его выполнения.

Предположим, что имеется n независимых алгоритмов, заданных графами G_i =(X_i , P_i , Г_i ), выполнение которых должно осуществляться с временными тактами T_i =K_i ^.T, где Т - минимальный временной такт. Требуется найти наименьшее необходимое число N процессоров, входящих в состав однородной ВС, и план выполнения операторов на них, для решения данной системы независимых алгоритмов. Заметим, что если решение задачи найдено на отрезке времени [0 , Т* ], где Т* = К* ^. Т , К* = Н0К { К i }, i = 1, . . n, то оно может быть периодически продолжено на всю временную ось.

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