- 10 -

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

Покажем, что после ввода оператора x _k на временном интервале dT = ( u _s , u _{i j l} - t _{i l} ) будет выполняться не более N операторов. Доказательство проведём методом от противного. Пусть на временном интервале dT после ввода дополнительного оператора x _k, выполняется более N операторов. Так как на правой границе интервала dT выполняется не более N операторов, то интервалу dT принадлежит момент окончания выполнения некоторого оператора, что противоречит условию выбора u _s .

Итак, продолжив рассмотренную процедуру для всех таких операторов x _{i j l} , получим объединённый граф G*. При этом, алгоритм, соответствующий графу G*, выполняется на N процессорах однородной ВС и по предположению N, является минимальным числом для которого это возможно.

В соответствии с теоремой 1, план выполнения операторов, заданный графом G*, может быть полностью определён графом G', полученным из графа G* в результате введения дуг, отвечающим условиям теоремы 2.

Поскольку, построение графа G' не меняет плана выполнения операторов, то условие (3) на дополнительные операторы графа G* справедливо и для графа G'.

Достаточность. Доказательство достаточности проведём методом от противного. Пусть построен граф G' указанным в условии теоремы 2 способом и N наименьшее число для которого это возможно. Допустим, что существует план выполнения системы независимых алгоритмов на меньшем числе процессоров N'. Из доказательства необходимости следает, что в соответствии с условиями теоремы 2 может быть построен граф G', состоящий из N' путей не содержащих общих вершин, что противоречит предположению, что N наименьшее число для которого существует такой граф G'.

Теорема доказана.