Практическая работа №5: Структурная оптимизация многопроцессорной системы обработки данных

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

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

Модель, описывающая информационные связи между задачами $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 $-ой задачи.

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

Определить оптимальное число процессов $ K_{пр} $ для МПСОД, граф решения ЗНЗ которой приведен на рис. 1, и построить график загрузки каждого процессора, чтобы достигнуть значения $ T_{кр} $. Значения $ \tau_i$, $i = 1..m $, выбираются студентами самостоятельно в диапазоне 10 ÷ 100 условных единиц.

1. С помощью метода динамического программирования определить критическое значение $T_{кр}$.
2. Определить количество процессоров, необходимое для выполнения задач в многопроцессорной системе.
3. Построить график загрузки всех процессоров, учитывая, что приступить к новой задаче можно только в том случае, если выполнены все работы, лежащие на пути к выбранной задаче.

• Цель работы.
• Краткое изложение основных теоретических понятий.
• Постановка задачи с кратким описанием порядка выполнения работы.
• Рассчёт оптимального числа процессов.
• График загрузки каждого процесса с пояснениями.
• Общий вывод по проделанной работе.
• Код программы.

Дана МПСОД, граф решения ЗНЗ которой приведен на рис. 2. Очевидно, что критическим путем будет $X_2 \to X_3 \to X_5$ и $$ T_{кр} = 20 + 30 + 30 = 80. $$ Тогда оптимальное число процессоров в системе составит $$ K_{кр} = \left\lceil\frac{T_о}{T_{кр}}\right\rceil = \left\lceil\frac{10 + 30 + 20 + 20 + 10 + 30}{80}\right\rceil = \left\lceil\frac{120}{80}\right\rceil = 2. $$ График загрузки процессоров будет выглядеть следующим образом: