This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision Next revision Both sides next revision | ||
courses:system_analysis_modeling_and_optimization:task5 [2019/06/29 14:23] andrey.suchkov [Основные теоретические положения] |
courses:system_analysis_modeling_and_optimization:task5 [2019/06/30 09:53] andrey.suchkov [Пример выполнения задания] |
||
---|---|---|---|
Line 7: | Line 7: | ||
Модель, описывающая информационные связи между задачами $X_i$, $i = 1..m$, задана в виде группы в ярусно-параллельной форме и представлена на рис. 1. | Модель, описывающая информационные связи между задачами $X_i$, $i = 1..m$, задана в виде группы в ярусно-параллельной форме и представлена на рис. 1. | ||
{{ :courses:system_analysis_modeling_and_optimization:task5.png?nolink |Рисунок 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. | ||
+ | {{ :undefined:task5_eg.png?nolink |}} |