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

В этом случае совокупность уравнений ограничений

Последняя группа m неравенств определяет условие согласования загрузок.

Проведём сравнительный анализ приближённого алгоритма распределения для графа G_A на рис.3.5а.

Имеем n = 4; m = 2.

Зададим начальное распределение:

• Примем , поэтому

Новые значения переменных

• Примем , поэтому

Так как произошло увеличение , то следует сохранить прежнее предыдущее положение переменной x₃.

• Примем , поэтому

Так как значение , то также сохраняем распределение на 1-ой итерации.

• Примем , поэтому

Новые значения переменных

Таким образом, после 4-ой итерации, когда были проварьированы все 4 компоненты графа G_A , получено окончательное решение по распределению.

Матрица распределения S:

Полученному решению по распределению соответствует, например, линейный порядок и исполняемый граф на рис.3.5 и, к, л.

Как уже было отмечено ранее окончательное решение получено после n = 4 итераций.

Воспользуемся теперь для нахождения решения по распределению компонент графа-алгоритма G_A (рис.3.5а) симплекс-методом с тем же начальным распределением компонент в постановке (25) с  = 0.

Система уравнений начального распределения:

Из анализа выражения для выбираем для варьирования переменную , и переменная переходит в число свободных.

• Система уравнений после 1-ой итерации:

Из анализа выражения для выбираем для варьирования переменную , и переменная переходит в число свободных.

• Система уравнений после 2-ой итерации:

Анализ выражения для показывает, что больше нет варьируемых переменных, т.е. решение найдено.

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

и значение показателя .

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

4. Программная реализация и сравнение параллельных алгоритмов.

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

Первый из них сугубо конкретный, и связан с выбором языка параллельного программирования и технологическими аспектами программирования. Сам переход к программной форме представления алгоритма зависит от субъективных и объективных моментов (например, топология вычислительной сети), и особенно, ограниченного числа каналов ввода-вывода. Так, например, для транспьютеров число внешних каналов-линков равно 4. Поэтому, в общем случае, переход к программе может составить значительные трудности и привести к модификации алгоритма обработки.

Второй путь, более универсальный и трудоёмкий - связан с построением проблемно-ориентированной системы сравнительного исследования различных вариантов реализации параллельных алгоритмов с последующей генерацией параллельной программы и её оценкой. Предметом исследования здесь является вид показателя функционирования, топология вычислительной сети, характер разбиения алгоритма обработки на компоненты, алгоритмы решения, параметры ограничений(например, параметр ) и т.п. Но только, конечно, получаемая программа окончательно даёт ответ о пригодности результата и степени отклонения расчётных и реальных параметров, так как многие особенности функционирования сети и программы принципиально не отражаются в модельном представлении, например, наличие приоритетов, статистическая природа оценок параметров алгоритмов (компонент) обработки, технология программирования.

60