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

Лемма(об оценке сверху требуемого количества процессоров для решения задачи за время Т). Минимальное количество одно­родных процессоров N, способных выполнить данный алгоритм за время Т ≥ Т_кр, не превышает , где Ci — число операторов, которое входит в i-е полное множество ВНО, полученное для информационного графа G, соответствующе­го исследуемому алгоритму.

Следствие:При N = Е время решения данного алгоритма Т=Т_кр.

Примечание. Получаемое количество процессоров N на основании этой леммы является верхней оценкой требуемого количества процессо­ров (т. е. для решения данной задачи требуется не более N процессоров).

Теорема(об оценке снизу числа процессов, необходимых для решения задачи за время Т). Для того чтобы N процессоров бы­ло достаточно для выполнения заданного алгоритма, представлен­ного информационным графом со скалярными весами вершин за время Т, необходимо, чтобы для отрезка выполня­лось соотношение

, где — минимальная загрузка отрезка .

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

ОБ ОЦЕНКЕ СНИЗУ ВРЕМЕНИ ВЫПОЛНЕНИЯ ЗАДАЧИ ПРИ ЗАДАННОМ КОЛИЧЕСТВЕ ПРОЦЕССОРОВ.

УТОЧНЕНИЕ ОЦЕНКИ СНИЗУ ВРЕМЕНИ ВЫПОЛНЕНИЯ ЗАДАЧИ НА N ПРОЦЕССОРАХ.

Теорема (об оценке снизу времени выполнения задачи при заданном количестве процессоров). Для того чтобы Т было наименьшим временем выполнения алгоритма, представленно­го информационным графом со скалярными весами вершин, на ВС, состоящей из N процессоров, необходимо, чтобы для отрезка выполнялось соотношение

, где — минимальная загрузка отрезка .

Теорема (об уточнении оценки снизу времени выполне­ния задачи на N процессорах). Если Т₁ — оценка снизу времени выполнения алгоритма, представленного информационным гра­фом со скалярными весами вершин на ВС, имеющей N процес­соров, и если на отрезке выполняется соотношение , то наименьшее время Т реализации алгоритма удовлетворяет соотношению .

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

Алгоритм. Оценка минимального числа процессоров, необ­ходимого для выполнения алгоритма за время Т.

1. Положим N:= 0.

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

[0,1];

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

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

,,,

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

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

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

4. Если N₁ > N, то N := N₁.

5. После обработки всех интервалов получим требуемое N.
Конец алгоритма.