Основной алгоритм

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

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

[ 0,1 ]

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

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

[ 0,T ], [ 1,T ],…, [ T-1,T ]. Всего отрезков: .

3.Для очередного интервала [ a,b ] вычислим , где - загрузка отрезка.

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

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

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

Лемма «Об оценке сверху требуемого количества процессоров для решения задачи за время Т». Минимальное количество однородных процессоров N, способных выполнить данный алгоритм за время , не превышает , где - число операторов, входящих в i-ое полное множество ВНО, полученное для информационного графа G, соответствующего исследуемому алгоритму. Следствие: При N=E время решения данного алгоритма Т=Т_кр Получаемое количество процессоров N на основании этой леммы является верхней оценкой требуемого количества процессоров (т.е. для решения данной задачи требуется не более N процессоров).

Утверждение «Об оценке снизу числа процессов, необходимых для решения задачи за время Т». Для того чтобы N процессоров было достаточно для выполнения заданного алгоритма за время Т необходимо, чтобы для отрезка выполнялось соотношение Утверждение «Об оценке снизу времени выполнения задачи при заданном количестве процессоров». Для того, чтобы время Т было наименьшим временем выполнения алгоритма вычислительной системой, состоящей из N процессоров, необходимо, чтобы для отрезка выполнялось соотношение Утверждение «Об уточнении оценки снизу времени выполнения задачи на N процессорах». Если T₁ – оценка снизу времени выполнения алгоритма, представленного ИГ со скалярными весами вершин, на ВС из N процессоров и на отрезке выполняется соотношение: , то наименьшее время реализации алгоритма .