1 31 6 Типы операций:

Type(1) -> type(1)

Type(2)->type(2)

Type(3)->type(1)

21

41

Type(4)->type(2)

7 1

Type(5)->type(1)

Type(6)->type(1)

51

Type(7)->type(2)

Type(8)->type(1)

87 1

LS, На шаге 1 первого типа и один второго типа может планироваться

|1,3,6

6

5

Шаг 1

Шаг 2

Шаг 3

Шаг 4

3,6|2

|5,7

|8

1

212

3

4

Операции

Список

6|4

7

8

Шаг 5

|8

Билет №24

1. Стратегии планирования на графе задач. Планирование графа задач

Назначение задач на процессоры трансформирует граф задач в асинхронный план. Планирование задач может выполняться как при наличии, так и отсутствии ограничений на число процессоров. В отличие от стратегий планирования, рассмотренных ранее, применимые к графу задач стратегии не обязательно используют все имеющиеся процессоры для генерации самого быстрого плана. Это происходит в силу наличия накладных расходов на обмен данными между задачами. В предельном случае самым быстрым может оказаться план, использующий только один процессор.

Целью планирования является назначение задач на процессоры, минимизирующее длину плана при заданных ограничениях на число процессоров. Предполагается, что каждая из задач может решаться на каждом из процессоров. План рассматривается эффективным если длина его мала, а число используемых процессоров разумно.

Различные подходы возможны к решению задачи планирования. Стратегия спискового планирования базируется на построении упорядоченного списка задач путем присвоения задачам приоритета. Упорядочение задач в списке может быть статическим и динамическим. Статическое упорядочение выполняется перед началом планирования. Динамическое переупорядочение повторяется после каждой итерации планирования. Динамическое планирование выполняется в цикле, на каждой итерации которого:

4. определяются приоритеты и новый порядок задач в списке;

5. выбирается задача с наивысшим приоритетом;

6. выбирается процессор, на который задача назначается.

Основным критерием выбора процессора, на который назначается задача, является наиболее раннее время начала решения задачи.

Критический путь – важное понятие, используемое стратегиями планирования. Критический путь на графе задач есть множество узлов и дуг, формирующих путь от входного узла до выходного узла, для которого сумма времен решения задач и времен передачи данных является максимальной. Сумма времен решения задач, лежащих на критическом пути, дает нижнюю границу временной длины плана.

К известным стратегиям планирования относятся:

7. зануление дуг (Edge Zeroing - EZ);

8. модифицированный критический путь (Modified Critical Path - MCP);

9. управление мобильностью (Mobility Directed - MD);

10. наиболее ранняя задача первая (Earliest Task First - ETF);

11. планирование на основе динамических уровней (Dynamic Level Scheduling - DLS);

12. группировка доминирующей последовательности» (Dominant Sequence Clustering - DSC).