Differences

This shows you the differences between two versions of the page.

--- courses:system_analysis_modeling_and_optimization:task5 [2019/06/29 14:22]
andrey.suchkov [Цель работы]
+++ courses:system_analysis_modeling_and_optimization:task5 [2022/12/10 09:08] (current)
@@ Line 6: / Line 6: @@
 Модель, описывающая информационные связи между задачами $X_i$, $i = 1..m$, задана в виде группы в ярусно-параллельной форме и представлена на рис. 1.
-{{ :courses:system_analysis_modeling_and_optimization:task5.png?nolink&300 |Рисунок 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_{кр} $. Значения $ \tau_i$, $i = 1..m $, выбираются студентами самостоятельно в диапазоне 10 ÷ 100 условных единиц.
+===== Порядок выполнения работы =====
+  - С помощью метода динамического программирования определить критическое значение $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  |    |  :::  |  :::  |

se.moevm.info

User Tools

Site Tools

Differences

Page Tools