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

Многопроцессорная вычислительная система обработки данных (МПСОД), состоящая из однотипных процессов, предназначена для решения заданного набора задач (ЗНЗ) обработки связанных между собой данных.

Модель, описывающая информационные связи между задачами $X_i$, $i = 1..m$, задана в виде группы в ярусно-параллельной форме и представлена на рис. 1. Время решения ЗНЗ при параллельно-последовательной обработке данных в МПСОД, как это следует из графа (см. рис. 1), ограничено сверху некоторыми пороговым критическим значением $T_{кр}$ и определяется длиной критического пути графа.

Таким образом, оптимальное число процессов МПСОД можно определить из соотношения: $$ K_{пр} \leqslant \left\lceil\frac{T_о}{T_{кр}}\right\rceil, $$ где $T_о$ – время решения ЗНЗ с использованием одного процессора: $$ T_о = \sum\limits_{i=1}^m\tau_i, $$ где $\tau_i$ – время решения $i$-ой задачи.

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