courses:system_analysis_modeling_and_optimization:task5
Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision | ||
|
courses:system_analysis_modeling_and_optimization:task5 [2019/06/30 10:06] andrey.suchkov [Пример выполнения задания] |
courses:system_analysis_modeling_and_optimization:task5 [2022/12/10 09:08] (current) |
||
|---|---|---|---|
| Line 10: | Line 10: | ||
| Таким образом, оптимальное число процессов МПСОД можно определить из соотношения: | Таким образом, оптимальное число процессов МПСОД можно определить из соотношения: | ||
| - | $$ | + | \[ |
| - | K_{пр} \leqslant \left\lceil\frac{T_о}{T_{кр}}\right\rceil, | + | K_{пр} \leqslant \left\lceil\frac{T_о}{T_{кр}}\right\rceil, |
| - | $$ | + | \] |
| - | где $T_о$ -- время решения ЗНЗ с использованием одного процессора: | + | где $ T_о $ -- время решения ЗНЗ с использованием одного процессора: |
| - | $$ | + | \[ |
| - | T_о = \sum\limits_{i=1}^m\tau_i, | + | T_о = \sum\limits_{i=1}^m\tau_i, |
| - | $$ | + | \] |
| - | где $\tau_i$ -- время решения $i$-ой задачи. | + | где $ \tau_i $ -- время решения $ i $-ой задачи. |
| Сложность и трудоемкость решения задач структурной оптимизации зависит от размерности графа (числа вершин). В случае не высокой размерности может быть использован метод полного перебора путей в графе. При большом числе вершин графа используют, как правило, метод динамического программирования. | Сложность и трудоемкость решения задач структурной оптимизации зависит от размерности графа (числа вершин). В случае не высокой размерности может быть использован метод полного перебора путей в графе. При большом числе вершин графа используют, как правило, метод динамического программирования. | ||
| ===== Постановка задачи ===== | ===== Постановка задачи ===== | ||
| - | * Определить оптимальное число процессов $K_{пр}$ для МПСОД, граф решения ЗНЗ которой приведен на рис. 1. | + | Определить оптимальное число процессов $ K_{пр} $ для МПСОД, граф решения ЗНЗ которой приведен на рис. 1, и построить график загрузки каждого процессора, чтобы достигнуть значения $ T_{кр} $. Значения $ \tau_i$, $i = 1..m $, выбираются студентами самостоятельно в диапазоне 10 ÷ 100 условных единиц. |
| - | * Построить график загрузки каждого процессора, чтобы достигнуть значения $T_{кр}$. | + | |
| ===== Порядок выполнения работы ===== | ===== Порядок выполнения работы ===== | ||
| - С помощью метода динамического программирования определить критическое значение $T_{кр}$. | - С помощью метода динамического программирования определить критическое значение $T_{кр}$. | ||
| Line 37: | Line 36: | ||
| ===== Пример выполнения задания ===== | ===== Пример выполнения задания ===== | ||
| Дана МПСОД, граф решения ЗНЗ которой приведен на рис. 2. | Дана МПСОД, граф решения ЗНЗ которой приведен на рис. 2. | ||
| - | {{ :courses:system_analysis_modeling_and_optimization:task5_eg.png?nolink&300 |Рисунок 2 - Пример системы}} | + | {{ :courses:system_analysis_modeling_and_optimization:task5_eg.png?nolink&300 |Рисунок 2 – Пример системы}} |
| Очевидно, что критическим путем будет $X_2 \to X_3 \to X_5$ и | Очевидно, что критическим путем будет $X_2 \to X_3 \to X_5$ и | ||
| $$ | $$ | ||
| Line 44: | Line 43: | ||
| Тогда оптимальное число процессоров в системе составит | Тогда оптимальное число процессоров в системе составит | ||
| $$ | $$ | ||
| - | K_{кр} = \left\lceil\frac{T_о}{T_{кр}}\right\rceil = \left\lceil\frac{10 + 30 + 20 + 20 + 10 + 30}{80}\right\rceil = \left\lceil\frac{100}{80}\right\rceil = 2. | + | 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. |
| $$ | $$ | ||
| График загрузки процессоров будет выглядеть следующим образом: | График загрузки процессоров будет выглядеть следующим образом: | ||
| Line 50: | Line 49: | ||
| | 0-10 | $X_1$, $X_2$ | $X_2$ | $X_1$ | | | 0-10 | $X_1$, $X_2$ | $X_2$ | $X_1$ | | ||
| | 10-20 | | ::: | Простой процессора | | | 10-20 | | ::: | Простой процессора | | ||
| - | | 20-30 | $X_3$, $X_4$ | $X_3$ | X_4 | | + | | 20-30 | $X_3$, $X_4$ | $X_3$ | $X_4$ | |
| | 30-40 | | ::: | Простой процессора | | | 30-40 | | ::: | Простой процессора | | ||
| | 40-50 | | ::: | ::: | | | 40-50 | | ::: | ::: | | ||
courses/system_analysis_modeling_and_optimization/task5.1561889167.txt.gz · Last modified: 2022/12/10 09:08 (external edit)
Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Share Alike 4.0 International
