Об оценке сверху и снизу необходимого числа процессоров для решения поставленной задачи

Алгоритм вычисления функции . Для составления алгоритма вычисления данной функции введем функцию .

1. Вычисляются ранние и поздние сроки окончания выполнения операторов.

2.Полагаем .

3.Анализируем последовательность оператора

4.Вычислим

5.После перебора всех операторов получаем значение

Утверждение «Об оценке снизу времени выполнения задачи при заданном количестве процессоров».

Для того, чтобы время Т было наименьшим временем выполнения алгоритма вычислительной системой, состоящей из N процессоров, необходимо, чтобы для отрезка выполнялось соотношение:

Утверждение «Об уточнении оценки снизу времени выполнения задачи на N процессорах».

Если T₁ – оценка снизу времени выполнения алгоритма, представленного ИГ со скалярными весами вершин, на ВС из N процессоров и на отрезке выполняется соотношение:

,то наименьшее время реализации алгоритма

Дополнение:

Лемма «Об оценке сверху требуемого количества процессоров для решения задачи за время Т».

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

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

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

Утверждение «Об оценке снизу числа процессов, необходимых для решения задачи за время Т».

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