close

Вход

Забыли?

вход по аккаунту

Ориентированным графом - Южно-Уральский государственный

код для вставкиСкачать
Формальная модель задания
в распределенных
вычислительных средах
А . В. ША МА К ИНА, Л. Б . СОК ОЛИ НСК И Й
Ю Ж НО - УР АЛЬСК ИЙ Г ОСУ Д А Р СТВЕННЫЙ У НИ ВЕ Р СИ Т ЕТ
Цель
Разработать алгоритм планирования
ресурсов в проблемноориентированных распределенных
вычислительных средах.
2
Алгоритмы планирования
ресурсов
1. Алгоритм доминирующей
последовательности (DSC)
2. Алгоритм Саркара
3. Алгоритм Кима и Брауна (KB/L)
3
Требования к модели
• Представление потока работ в виде размеченного
взвешенного ориентированного ациклического графа
• Возможность кластеризации вершин графа
• Возможность масштабирования отдельных задач
в задании
• Указание числа процессорных ядер для
вычислительных узлов
• Описание уже известных и новых алгоритмов
кластеризации
4
Ориентированный граф
Ориентированным графом называется четверка
 = , , ,  ,
где
 – множество вершин;
 – множество дуг;
:  →  – функция, определяющая начальную
вершину дуги;
:  →  – функция, определяющая конечную
вершину дуги.
5
Функции взвешивания и
разметки графа
Пусть задан ориентированный граф  = , , ,  .
• Функция взвешивания   дуги  определяет объем
данных, который необходимо передать по дуге  от
задачи, ассоциированной с вершиной () к задаче,
ассоциированной с вершиной ().
• Разметкой графа G будем называть функцию  :V  N 2
6
Граф задания
Графом задания называется размеченный взвешенный
ориентированный ациклический граф
 = , , , , ,  ,
где
 – множество вершин, соответствующих задачам,
 – множество дуг, соответствующих потокам данных.
7
Пример графа задания
Функция разметки
  =  ,  ,
где
 - максимальное количество
процессорных ядер, на которых
задача  имеет ускорение,
близкое к линейному,
 - время выполнения
задачи  на одном ядре
8
Вычислительная система
• Вычислительный узел  – это упорядоченное множество
процессорных ядер {0 , … , −1 }.
• Вычислительная система – это упорядоченное множество
вычислительных узлов  = {0 , … , −1 }.
9
Функция кластеризации
• Кластеризацией называется
однозначное отображение
:  → 
множества вершин  графа
задания  на множество
вычислительных узлов .
• Кластер  – это подмножество
всех вершин, отображаемых на
вычислительный узел  ∈ .
Вершина 
1
2
3
4
5
6
7
8
()
0
0
1
1
1
1
1
0
• Пример:
0 = 1 , 2 , 8 и
1 = 3 , 4 , 5 , 6 , 7 .
10
Пример кластеризованного графа
• Кластеры:
0 = 1 , 2 , 8 и
1 = 3 , 4 , 5 , 6 , 7 .
• Коммуникационная
стоимость – время передачи
данных по дуге e ∈ E.
• Функция, вычисляющая
коммуникационную
стоимость:
11
Расписание
Расписанием называется
отображение
:  → ℤ≥0 × ℕ,
которое произвольной
вершине  ∈  сопоставляет
двойку чисел
  = ( ,  ),
где  определяет время
запуска задачи ,  –
количество процессорных
ядер, выделяемых задаче .
Вершина

1
2
3
4
5
6
7
8
  =  , 
Время
Количество
запуска 
ядер 
0
2
1
2
3
2
7
2
7
2
7
2
10
1
15
2
12
Вычислительная стоимость
Вычислительная стоимость
 ,  задачи  на 
процессорных ядрах
определяется следующей
формулой:
Вершина 
1
2
3
4
5
6
7
8
 , 
1
3
4
3
3
2
4
2
13
План  = {0 , 1 }
выполнения расписания 
Отображение 0 : 0 → 0
Задача
1
2
8
Процессорные
ядра
{00 , 01 }
{00 , 01 }
{00 , 01 }
Отображение 1 : 1 → 1
Задача
3
4
5
6
7
Процессорные
ядра
{10 , 11 }
{10 , 11 }
{12 , 13 }
{14 , 15 }
{10 }
14
Распланированный граф
• Кластеризованный граф  с заданными
расписанием  и соответствующим планом 
будем называть распланированным.
15
Критический путь
• Пусть в распланированном графе  задан простой путь
 = 1 , 2 , … ,  . Стоимостью пути () называется
величина
• Пусть Y – множество всех простых путей в
распланированном графе . Простой путь  ∈ Y
называется критическим, если он обладает
максимальной стоимостью.
16
Диаграмма Ганта
Критический путь равен 17.
17
Алгоритм планирования POS
(Problem-Oriented Scheduling)
1. Построение начальной конфигураций графа
0 = , , , , , , 0 , 0 .
2. Найти критический путь y0 в 0 .
3.  ≔ 0.
4. Перейти от конфигурации  =
, , , , , ,  ,  к конфигурации +1 =
, , , , , , +1 , +1 , такой что (попутно
помечая рассмотренные дуги).
5. Если остались нерассмотренные дуги,  ≔  + 1 и
перейти на шаг 4.
6. Стоп.
18
Каноническая ярусно-параллельная форма
графа
19
Заключение
Разработана алгоритм планирования ресурсов в
проблемно-ориентированных распределенных
вычислительных средах.
21
1/--страниц
Пожаловаться на содержимое документа