Лабораторная работа 1

Срок сдачи лабораторной работы: 04.10.2010.

Задание

Имеется распределенная вычислительная система (ВС) укомплектованная ($n$) элементарными машинами (ЭМ). Задан набор из ($m$) параллельных задач. Каждая задача ($j \in J = \{1, 2, ..., m\}$) характеризуется временем ($t_j$) решения и количеством ($r_j$) элементарных машин необходимых для неё.

Требуется построить расписание ($S$) решения параллельных задач на распределенной ВС. Для каждой задачи необходимо определить момент времени ($\tau_j$) начала решения её ветвей и их распределение по элементарным машинам. Пусть ($x_{ji} \in C = \{1,2,...,n\}$) – номер ЭМ, на которую распределена ветвь ($i \in \{1,2,...,r_j\}$) задачи ($j \in J$).

Обозначим через ($J(t) = \{j \in J | \tau_j \le t \le \tau_j + t_j\}$) множество задач, решаемых на распределенной ВС в момент времени ($t$).

Будем называть расписание ($S = (\tau_1,\tau_2,...,\tau_m; x_{11},x_{12},...,x_{1r_1},...,x_{m1}, x_{m2}, ..., x_{mr_m})$) допустимым, если оно удовлетворяет ограничениям.

1. В любой момент времени на ресурсах распределенной ВС решается не более ($n$) ветвей параллельных задач:

($\displaystyle\sum\limits_{j \in J(t)} r_j \le n, \forall t \in \mathbf{R}.$)

2. Ветви параллельных задач решаются на разных элементарных машинах:

($\displaystyle\prod_{j \in J(t)} \prod_{j' \in J(t) \setminus \{j\}} (x_{ji} - x_{j'i'}) = 0 , \forall t \in \mathbf{R}, i = 1, 2, ..., r_j, i' = 1, 2, ..., r_{j'}.$)

Обозначим через ($\Omega$) множество допустимых расписаний. В качестве показателя оптимальности расписаний будем использовать время ($T(S)$) окончания решения последней задачи

($T(S) = \displaystyle\max_{j \in J}\{\tau_j + t_j\}.$)

Итак, требуется найти допустимое расписание ($S \in \Omega$), доставляющее минимум целевой функции ($T(S)$). Формально

($T(S) = \displaystyle\max_{j \in J}\{\tau_j + t_j\} \to \displaystyle\min_{S \in \Omega}$)

при ограничениях:

($\displaystyle\sum\limits_{j \in J(t)} r_j \le n, \forall t \in \mathbf{R},$)

($\displaystyle\prod_{j \in J(t)} \prod_{j' \in J(t) \setminus \{j\}} (x_{ji} - x_{j'i'}) = 0, \forall t \in \mathbf{R}, i = 1, 2, ..., r_j, i' = 1, 2, ..., r_{j'},$)

($x_{ji} \in C, j = 1, 2, ..., m, i = 1, 2, ..., r_j,$)

($\tau_j \in \mathbf{R}, j = 1, 2, ..., m$).

Описанная задача относится к дискретной оптимизации и является трудноразрешимой. Один из подходов к приближенному решению рассмотренной задачи основан на её сведении к задаче двумерной упаковки прямоугольников в полуограниченную полосу (2D Strip Packing, 2DSP). Параллельная задача ($j \in J$) представляется в виде прямоугольника шириной ($r_j$) и высотой ($t_j$) условных единиц. Ширина полосы – ($n$) условных единиц, высота не ограничена. Требуется упаковать прямоугольники без их вращений и пересечений в полосу так, чтобы высота упаковки была минимальной. На рис. 1 приведен пример упаковки 5 прямоугольников (задач) в полосу шириной 10 условных единиц (элементарных машин). Задача 1 запускается на решение в нулевой момент времени и использует элементарные машины 1 - 5, задача 4 начинает решаться в момент времени 2 и использует ЭМ 8, 9, 10. Значение целевой функции ($T(S) = 8$).

Рис. 1. Пример упаковки прямоугольников в полуограниченную полосу: ($m = 5; n = 10; T(S) = 8$)

В рамках лабораторной работы требуется выполнить нижеследующие задания.

1. Написать программу, реализующую алгоритмы NFDH и FFDH [1, 2] для приближенного решения задачи.

В качестве входных параметров программа получает имя файла с набором задач, количество ($n$) ЭМ в системе и название алгоритма (NFDH или FFDH). Результат работы программы: расписание ($S$) решения задач, значение ($T(S)$) целевой функции, отклонение ($\epsilon$) значения целевой функции от её нижней границы ($T'$), время ($t$) выполнения алгоритма в секундах.

($\epsilon = \frac{T(S) - T'}{T'}, T' = \frac{1}{n}\displaystyle\sum_{j \in J}r_jt_j.$)

2. Исследовать время выполнения алгоритмов в зависимости от количества ($m$) задач в наборе.

Сформировать ($k$) наборов задач с ($m = 100, 500, ..., 5000$); параметры задач генерировать как равномерно распределенные псевдослучайные числа ($r_j \in \{1, 2, ..., n\}$), ($t_j \in \{1, 2, ..., 100\}$). Рассмотреть случаи ($n = 1024, 4096$). Ответить на вопросы:

  • Какова вычислительная сложность алгоритмов?
  • Как зависит время работы алгоритмов от значения параметра ($m$)?
  • Как зависит время работы алгоритмов от значения параметра ($n$)?

3. Провести сравнительный анализ значений целевой функции от расписаний, формируемых алгоритмами.

Сформировать ($k$) наборов задач с ($m = 100, 500, ..., 5000$); параметры задач генерировать как равномерно распределенные псевдослучайные числа ($r_j \in \{1, 2, ..., n\}$), ($t_j \in \{1, 2, ..., 100\}$). Во всех ($k$) экспериментах ($n = 1024$). По результатам экспериментов построить оценки математического ожидания и среднеквадратического отклонения случайной величины ($\epsilon$). Ответить на вопрос: какой из алгоритмов, на рассмотренных наборах задач, формировал более точные расписания?

4. Провести сравнительный анализ значений целевой функции от расписаний, формируемых алгоритмами.

На основе протоколов решения параллельных задач на промышленных распределенных ВС [3] сформировать наборы задач с ($ m = 100, 500, 1000 $) для любой из систем: LLNL uBGL, LLNL Atlas, LLNL Thunder. По результатам экспериментов построить оценки математического ожидания и среднеквадратического отклонения случайной величины ($ \epsilon $).

Ответить на вопрос: какой из алгоритмов, на рассмотренных наборах задач, формировал более точные расписания?

Контрольные вопросы

  1. Дать определение мультипрограммного режима функционирования распределённых ВС.
  2. Пояснить содержательный смысл целевой функции ($T(S)$).
  3. Пояснить смысл ограничений.
  4. Объяснить, почему рассмотренная задача относится к трудноразрешимым задачам дискретной оптимизации.

Литература

  1. Heidi Smith. Level Algorithms and Shelf Algorithms
  2. Jan H van Vuuren. 2D Strip Packing Problem
  3. Logs of Real Parallel Workloads from Production Systems