Инструменты пользователя

Инструменты сайта


courses:system_analysis_modeling_and_optimization:task5

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

Цель работы

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

Основные теоретические положения

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

Модель, описывающая информационные связи между задачами $X_i$, $i = 1..m$, задана в виде группы в ярусно-параллельной форме и представлена на рис. 1. Рисунок 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. Рисунок 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. $$ График загрузки процессоров будет выглядеть следующим образом:

Время Доступные задачи Процессор 1 Процессор 2
0-10 $X_1$, $X_2$ $X_2$ $X_1$
10-20 Простой процессора
20-30 $X_3$, $X_4$ $X_3$ $X_4$
30-40 Простой процессора
40-50
50-60 $X_5$ $X_5$
60-70
70-80