This shows you the differences between two versions of the page.
courses:system_analysis_modeling_and_optimization:task5 [2019/07/16 09:10] andrey.suchkov [Постановка задачи] |
courses:system_analysis_modeling_and_optimization:task5 [2022/12/10 09:08] |
||
---|---|---|---|
Line 1: | Line 1: | ||
- | ====== Практическая работа №5: Структурная оптимизация многопроцессорной системы обработки данных ====== | ||
- | ===== Цель работы ===== | ||
- | Освоение навыков распределения нагрузки в многопроцессорной вычислительной системе. | ||
- | ===== Основные теоретические положения ===== | ||
- | Многопроцессорная вычислительная система обработки данных (МПСОД), состоящая из однотипных процессов, предназначена для решения заданного набора задач (ЗНЗ) обработки связанных между собой данных. | ||
- | Модель, описывающая информационные связи между задачами $X_i$, $i = 1..m$, задана в виде группы в ярусно-параллельной форме и представлена на рис. 1. | ||
- | {{ :courses:system_analysis_modeling_and_optimization:task5.png?nolink |Рисунок 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_{кр}$. | ||
- | ===== Порядок выполнения работы ===== | ||
- | - С помощью метода динамического программирования определить критическое значение $T_{кр}$. | ||
- | - Определить количество процессоров, необходимое для выполнения задач в многопроцессорной системе. | ||
- | - Построить график загрузки всех процессоров, учитывая, что приступить к новой задаче можно только в том случае, если выполнены все работы, лежащие на пути к выбранной задаче. | ||
- | ===== Содержание отчёта ===== | ||
- | * Цель работы. | ||
- | * Краткое изложение основных теоретических понятий. | ||
- | * Постановка задачи с кратким описанием порядка выполнения работы. | ||
- | * Рассчёт оптимального числа процессов. | ||
- | * График загрузки каждого процесса с пояснениями. | ||
- | * Общий вывод по проделанной работе. | ||
- | * Код программы. | ||
- | ===== Пример выполнения задания ===== | ||
- | Дана МПСОД, граф решения ЗНЗ которой приведен на рис. 2. | ||
- | {{ :courses:system_analysis_modeling_and_optimization:task5_eg.png?nolink&300 |Рисунок 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 | | ::: | ::: | |