- 7 -

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

Теорема I. (Барский) ( [1], стр.54 ).

Для того, чтобы значение n, являлось наименьшим числом процессоров однородной ВС, которая выполняет алгоритм, представленный информационным графом G=(X, P, Г) со скалярными весами вершин, за время, не превышающее заданное значение Т, необходимо и достаточно, чтобы n было наименьшим числом, для которого можно построить граф G'=(X, P, Г'), объединив вершины, соответствующие операторам каждого полного множества ВНО, содержащего r > n операторов, r - n ориентированными дугами в n путей, не содержащих общих вершин. При этом длина критического пути в графе G' не должна превышать значение T.

Перейдём теперь к формулировке и доказательству теоремы о наименьшем числе процессоров, необходимых для решения системы независимых алгоритмов.

Теорема 2. Для того, чтобы число N являлось наименьшим числом процессоров однородной ВС, которая выполняет систему независимых алгоритмов (1), удовлетворяя временным ограничениям (2), необходимо и достаточно, чтобы N было наименьшим числом, для которого можно вводом дополнительных операторов, удовлетворяющих условию (3) построить граф G', объединив вершины, соответствующие операторам каждого полного множества ВНО, содержащего R > N операторов, R - N ориентированными дугами в N путей, не содержащих общих вершин. При этом должны выполняться временные ограничения (2).