АЛГОРИТМ ОПРЕДЕЛЕНИЯ ОЦЕНКИ МИНИМАЛЬНОГО ВРЕМЕНИ T ВЫПОЛНЕНИЯ ЗАДАННОГО АЛГОРИТМА НА ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЕ, СОДЕРЖАЩЕЙ N ПРОЦЕССОРОВ.

Алгоритм. Оценка минимального времени Т выполнения заданного алгоритма на ВС, содержащей N процессоров.

1. Вычислим , где — ближай­шее к х целое число, не меньшее х, p_i — вес i-го оператора.

2. Просмотрим интервалы в по­рядке

[0,1];

[0,2]; [1,2];

[0,3]; [1,3]; [2,3];

,,,

[0, Т]; [1, Т]; ... [Т–1, Т].

Всего отрезков .

Примечание.При таком выборе последовательности отрезков значе­ние Т можно увеличивать, не пересчитывая при этом ранее вычисленные значения d.

3. Для очередного интервала вычислим значение , где величина вычисляется по известному алгоритму.

4. Если d > 0, вычислим .

5. Вычислим .

6. После обработки всех интервалов вычислим значение Т — нижнюю оценку минимального времени выполнения данного алго­ритма на данной ВС.

Конец алгоритма.

АЛГОРИТМ ОЦЕНКИ МИНИМАЛЬНО НЕОБХОДИМОГО КОЛИЧЕСТВА ПРОЦЕССОРОВ ДЛЯ ЗАДАЧИ, ПРЕДСТАВЛЕННОЙ ИНФОРМАЦИОННО-ЛОГИЧЕСКИМ ГРАФОМ.

Если n – количество логических операторов в графе, то - число образованных информационных связей.

Перенумеруем логические операторы «сверху вниз, слева на право».

Для построения алгоритма преобразование информационно-логического графа в информационный граф, обозначим или , через jTF, будем считать при этом

Если , то ;

Если , то .

Алгоритм

1. Просматриваем матрицу S_T по столбцам слева на право, находим столбец, где имеется значение , предполагаем, что уровень этого логического оператора k:=1. Вводим вспомогательную переменную FLAG:=True, f:=1. Если просмотрены все столбцы, то конец алгоритма.

2. Выбираем связь и преобразуем ее в информационную. Если FLAG:=True, то связь временно исключаем из рассмотрения, вместе со всеми вершинами, доступными через эту связь. При том полагается, что исключаемые вершины образуют неориентированный граф. Иначе (FLAG:=False) эта связь больше не рассматривается.

3. В столбце j проверяем есть ли значение , где i – номер строки. Если да, то полагаем k++, j:=i. Столбец исключаем из рассмотрения и идем на шаг 2. Иначе формируем информационный граф.

Если f=k или k=1, то идем на шаг 1. иначе полагаем f:=k

4. На уровне k полагаем , FLAG:=False и идем на шаг 2.

Алгоритм. (для оценки минимального числа процессоров для ИЛГ)

1.

2. Используя предыдущий алгоритм, находим очередной информационный граф.

3. Для найденного ИГ, используя алгоритм в вопросе №35, получим нижнюю оценку числа процессоров N.

4. Если , то полагаем

5. Если обработаны все ИГ, то получается, что значение минимальная оценка числа процессоров, необходимого для решения задачи, представленной ИЛГ.

Конец алгоритма.