close

Вход

Забыли?

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

?

Эффективный план распределения неограниченно делимых заданий в среде MapReduce.

код для вставкиСкачать
Сер. 10. 2011. Вып. 2
ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА
УДК 519.687.1
М. А. Паньшенсков
ЭФФЕКТИВНЫЙ ПЛАН РАСПРЕДЕЛЕНИЯ
НЕОГРАНИЧЕННО ДЕЛИМЫХ ЗАДАНИЙ В СРЕДЕ MAPREDUCE
1. Введение. Вычислительная среда MapReduce была разработана сотрудниками компании Google для решения трудоемких прикладных задач с большим объемом
данных [1]. Как и вычислительная среда, основанная на интерфейсе MPI [2], среда
MapReduce не накладывает формальные ограничения на язык программирования [3,
4], впрочем, в отличие от среды с MPI, в ней есть ограничения на ход выполнения
задания и последовательность передачи входных/выходных данных между узлами вычислительной среды (подробнее см. в статье). Такие ограничения сужают класс решаемых задач, но в то же время снижают число строчек кода программы пользователя,
увеличивают переносимость программы и позволяют эффективно управлять вычислительным процессом в распределенной среде. Последнему пункту, конкретнее, эффективному планированию вычислений в среде MapReduce, посвящена данная статья.
Задача планирования вычислений представляется в виде классической задачи дискретной оптимизации [5, 6]. Для параллельной среды [7] такой задачей является поиск
экстремума некоторой целевой функции (например, времени исполнения) при условии
соблюдения ограничений, связанных с имеющимися ресурсами среды (процессорами,
памятью, каналами связи) – их параметры могут быть оценены специальными методами [8]. Решение такой задачи позволяет использовать имеющиеся ресурсы наиболее эффективно, позволяя получить минимальное время исполнения заданий, максимальную
загруженность ресурсов, минимальный расход электроэнергии в час и т. д. Впрочем,
в общем случае задачу оптимального планирования вычислений относят к классу трудноразрешимых, также известных как NP-трудных [9]. Поэтому придумано множество
быстроработающих эвристических алгоритмов [10–12]. Такие алгоритмы зачастую решают задачу планирования неоптимально и не гарантируют качества результата. Поэтому, чтобы продемонстрировать эффективность эвристических алгоритмов, многие
авторы реализуют их на реальных системах и показывают их эффективность на практических данных [10, 13, 14]. Другим классом алгоритмов, решающих поставленную
задачу, являются приближенные алгоритмы [15, 16]. Последние работают за полиномиальное время, но также гарантируют результат качества предоставляемого плана.
В данной статье рассматривается результат работы некоторого приближенного алгоритма и дается оценка его качества в зависимости от параметров среды.
Распределенная вычислительная среда MapReduce состоит из процессоров P. Вычислительное задание в такой среде реализовано в двух функциях Map и Reduce,
Паньшенсков Михаил Алексеевич – аспирант кафедры параллельных алгоритмов математикомеханического факультета Санкт-Петербургского государственного университета. Научный руководитель: доктор физико-математических наук, проф. Ю. К. Демьянович. Количество опубликованных
работ: 6. Научное направление: распределенные вычислительные системы. E-mail: mpansh@gmail.com.
c М. А. Паньшенсков, 2011
55
Схема потока данных в среде MapReduce
которые исполняются на процессорах P для разных данных (рисунок). Вычислительный процесс организован следующим образом. В начале процесса вычисления некоторого задания данные распределяются на доступные процессоры P M ⊆ P. Правила
разделения входных данных определяются функцией Divide. Затем каждый процессор
из P M исполняет функцию Map. Далее промежуточные данные по результату работы
Map пересылаются некоторым процессорам P R ⊆ P. При этом каждый процессор из
P M передает данные каждому процессору из P R , тем самым образуя полный граф
паросочетаний между процессорами. Правила распределения данных по процессорам
из P R определяется функцией Partition. Затем на каждом процессоре из P R исполняется функция Reduce. И наконец все результаты работы функции Reduce отправляются
c процессоров P R в некоторое хранилище (локальное или удаленное), завершая работу
задания.
Если считать, что функции Divide и Partition могут иметь разные реализации
для различных заданий, то есть возможность управлять размером входных данных
функций Map и Reduce в каждый момент времени для каждого процессора. Другими
словами, с этим допущением в среде MapReduce появляется возможность делить задания на подзадания произвольным образом. Это является ключевым фактом для исследований, демонстрируемых в настоящей статье.
Проблема эффективного планирования заданий в среде MapReduce является двухуровневой. На первом уровне планирования происходит разбиение заданий на подзадания (при помощи функций Divide и Partition), а на втором определяется порядок
выполнения подзаданий. Алгоритмы планирования, рассматриваемые в данной статье,
затрагивают оба уровня планирования. Разбираются два случая: среда без коммуникаций, среда с коммуникациями и задержками на создание соединения.
Статья организована следующим образом. В п. 2 описывается теоретическая
модель среды, включая модель заданий, модель планирования, описание целевой
56
функции и коммуникаций в среде, а также обсуждаются ограничения накладываемой модели. В п. 3 рассматривается проблема оптимального планирования в среде
MapReduce без коммуникаций, доказываются некоторые свойства оптимального плана. Центральным местом статьи является теорема 1, которая в сущности описывает
оптимальный план. В п. 4 для плана, предложенного в теореме 1, сделана оценка качества плана для случая, когда присутствует издержки на коммуникацию и создание
соединения. Заключает статью, подводя итоги, п. 5.
2. Модель. Опишем математическую модель среды MapReduce, для того чтобы
в дальнейшем наглядно продемонстрировать свойства планов исполнения заданий.
Модель заданий. Задача планирования в среде MapReduce состоит из множества
изолированных заданий J = {J1 , J2 , ..., J|J| }, распределяемых на P идентичных процессорах ∗) . В среде MapReduce каждое задание Ji состоит из части Mi , выполняющей
операцию Map, и части Ri , выполняющей операцию Reduce. Для каждой части известно общее время последовательного выполнения на одном процессоре, T1 (Mi ) и T1 (Ri )
соответственно. Задания Mi и Ri состоят из подзаданий {mi1 , mi2 , ...} и {ri1 , ri2 , ...} ∗∗) .
Подзадание ωi ∈ Ji = Mi ∪ Ri представляется как набор непараллелизуемых инструкций для решения на некотором процессоре Pj в интервал времени [b(ωi ), e(ωi )]. Отрезки времени решения подзаданий определяют интервал [b(Ji ), e(Ji )]. Задание Ji посту), после которого оно доступно для исполнения.
пает на систему в момент времени
r(Ji#
#
Для удобства введем Ωi = ( Mi ) ∪( Ri ) – множество всех подзаданий задания Ji
и Ω = ∪i Ωi – множество всех подзаданий J. Множества подзаданий Ωi и Ω отличны
от множества Ji и J лишь по своей структуре.
Модель планирования. Планирование осуществляется в моменты r(Ji ) доступности заданий и в моменты e(ωi ) окончания решения каждого подзадания ωi ∈ Ji .
Назовем планом s по выполнению работ J на процессорах P тройку (π, τb , τe ), где
τb , τe : Ω → {1, 2, ..., ∞} и π : Ω → {1, 2, ..., |P |} – сопоставляют каждому подзаданию
время начала/конца его выполнения и процессор для выполнения соответственно. План
x = (π, τb , τe ) называется корректным планом, если выполняются следующие критерии:
1. Отсутствие коллизий:
τb (ω2 ) τb (ω1 ) < τe (ω2 )
(2.1)
⇒ π(ω1 ) = π(ω2 ).
∀ω1 ω2 (ω1 = ω2 ) :
τb (ω2 ) < τe (ω1 ) τe (ω2 )
2. Сохранение объема вычислений:
⎧ ⎪
(τe (m) − τb (m))
⎨
m∈Mi
Mi ∈ Ji , Ri ∈ Ji ⇒
⎪
(τe (r) − τb (r))
⎩
= T1 (Mi ),
= T1 (Ri ).
(2.2)
r∈Ri
3. Зависимость между частями M ap и Reduce:
m ∈ Mi , r ∈ Ri ⇒ τb (r) τe (m).
(2.3)
Здесь и далее при использовании термина план по умолчанию подразумевается корректный план.
∗) Дальнейшие рассуждения можно провести и без этого ограничения, но доказательства существенно усложнятся.
∗∗) В действительности множества подзаданий M и R конечны.
i
i
57
Целевая функция. В качестве целевой функции для планирования вычислений
пакета заданий J по примеру [15, 17–20] выбираем R — среднее время нахождения
заданий в системе, или, короче, среднее время отклика. Для плана выполнения s общее
время отклика Rs (J) и среднее время отклика Rs (J) записываются в виде
Rs (J) =
(e(Ji ) − r(Ji )) =
(τe (Ji ) − r(Ji )),
(2.4)
Ji ∈J
Ji ∈J
Rs (J) =
Rs (J)
.
|J|
Коммуникация. В среде MapReduce после окончания исполнения задания Mi
и до начала исполнения Ri производится передача данных от узлов, исполняющих Map,
узлам, исполняющих Reduce. Предположим, что скорость передачи между различными
узлами сети постоянна. Обозначим T1 (Ji ) за время передачи промежуточных данных
задания Ji , как если бы они передавались только между двумя вычислительными узлами. Издержками на соединение считается время t на создание соединения между
двумя вычислительными узлами. Это время фиксировано для отдельно взятой среды
и не зависит от объема передаваемых данных.
В п. 3 будет продемонстрирован оптимальный план x для среды без задержек
на коммуникацию, где t = 0, и дана оценка оптимальности плана x для среды, в которой t = 0.
3. Оптимальный план в среде без задержек на соединения. Рассмотрим
оптимальное распределение в среде MapReduce в случае, когда задержки на передачу
данных равны нулю и время на создание соединения также нулевые, т. е. T (Ji ) = 0
и t = 0. В конце части опишем оптимальный план x. В следующей части будет показано, как влияет присутствие задержек на коммуникацию на качество плана x. Охарактеризуем некоторые свойства среды, позволяющие определить оптимальный план
в MapReduce. Первое свойство говорит о линейном ускорении от параллелизма при росте числа процессоров в среде MapReduce.
Лемма 1. Об оптимальном плане при изменении числа процессоров. Если план x
выполняется за время Tx на P одинаковых процессорах, тогда минимальный по времени план x на P + 1 процессоре будет выполняться за время
Tx P
· Tx .
P +1
Д о к а з а т е л ь с т в о. Пусть Ω – множество всех подзаданий, а Θ =
{τb (ω)}ω∈Ω ∪ {τe (ω)}ω∈Ω – множество начал и окончаний решения этих подзаданий.
Проиндексируем множество Θ натуральными числами в порядке увеличения значений
элементов, а именно
i j =⇒ Θi Θj .
Разобьем множество подзаданий Ω на более мелкие по сетке Θ, а именно, возьмем
Ω0 = Ω, K = 0 и выполним следующие шаги:
1. Если ∈ Θ, ω ∈ ΩK : τb (ω) < < τe (ω), завершаем процесс, определив
Ω ← ΩK .
58
2. Возьмем и ω, удовлетворяющие условию выше, разобьем подзадание ω на левое
ω l и правое ω r по отметке и обновим план:
⎧ K+1
Ω
= {ω r } ∪ {ω e } , ∪ ΩK \ {ω} ,
⎪
⎪
⎪
⎪
⎨ τb (ω l ) = τb (ω),
τe (ω l ) = τb (ω r ) = ,
⎪
⎪
τe (ω r ) = τe (ω),
⎪
⎪
⎩
π(ω l ) = π(ω r ) = π(ω).
3. Увеличим K на 1 и перейдем к шагу 1.
Процедура разбиения имеет конечное число шагов, так как существует конечное
сочетание элементов из множеств Θ и Ω (до разбиения). Составим план x, по которому
∀ω ∈ Ω (после разбиения):
P
τe (ω) − τb (ω)
.
τe (ω) − τb (ω)
P +1
Для каждого i ∈ [1..|Θ| − 1] и интервала [Θi , Θi+1 ] выберем ω из Ω:
τb (ω) = Θi ,
τe (ω) = Θi+1 .
Сгруппируем все такие ω во множество WiG . Заметим, что |WiG | P . Разобьем
каждое подзадание ωg ∈ Wig на две части ωgl и ωgr :
⎧
g
Wi =
⎪
⎪
⎪
⎪
⎨ τb (ωgl ) =
τe (ωgl ) =
⎪
⎪
r
⎪
⎪ τe (ωg ) =
⎩
π(ωgl ) =
r e
ωg ∪ ωg ∪ {Wig \ {ωg }} ,
τb (ωg ),
−Θi
τb (ωgr ) = τb (ωg ) + Θi+1
· P,
P +1
τe (ωg ),
π(ωgr ) = π(ωg ).
Переместим каждое ωgr на выполнение на новом P + 1-м процессоре:
⎧
Θi+1 −Θi l
⎪
π(ωgr ) − 1 + Θi ,
⎨ τb (ωg ) =
P +1
−Θi
τe (ωgr ) = τb (ωgr ) + Θi+1
P +1 ,
⎪
⎩ pi(ω r ) = P + 1.
g
Повторим процедуру разбиения для каждого интервала [Θi , Θi+1 ], где i ∈
[1..|Θ| − 1]. По построению тройка x = (τ b , τ e , π) является планом для J с новым разg
биением на подзадания ∪Wi , т. е. удовлетворяют критериям (2.1)–(2.3). Осталось за−Θi
метить, что в интервалах Θi+1 − Θi+1
P +1 ; Θi+1 , где i ∈ [1..|Θ| − 1], все процессоры
бездействуют. Стало быть, можно провести смещение всех заданий в неиспользуемый
−
интервал времени. Такое смещение даст новый план ←
x . Общее время выполнения такого плана
|Θ|−1
− =
T←
x
Θi+1 − Θi
P
P
·P =
· Θ|Θ| − Θ1 =
· Tx < Tx .
P
+
1
P
+
1
P
+1
i=1
59
Благодаря возможности произвольно делить задания Map и Reduce, для любого
набора заданий J можно построить такой план, при котором ни один процессор не будет
простаивать, пока другой процессор занимается выполнением заданий. В следующей
лемме покажем, что для оптимального плана такое свойство является необходимым.
Лемма 2. О непрерывном вычислении оптимального плана. Если оптимальный
план x = (π, τb , τe ),
τb (ω0 ) t0 τe (ω0 ),
∃ω0 ∈ Ω :
∀P0 ∀t0 ∈ min τb (ω), max τe (ω)
π(ω0 ) = P0 .
ω∈Ω
ω∈Ω
Д о к а з а т е л ь с т в о. Предположим противное, а именно:
⎡ 0
t
0
Пусть ∃P0 ∃t ∈ min τb (ω), max τe (ω) : ∀ω0 ∈ Ω ⎣ t0
ω∈Ω
ω∈Ω
π(ω)
>
<
=
τe (ω),
τb (ω),
P 0.
Тогда ∃δ > 0 ∀ω ∈ Ω
[tb (ω), te (ω)] t0 − δ, t0 + δ ,
π(ω) = P 0 ,
т. e. на интервале t0 − δ, t0 + δ один из P процессоров бездействует. Соответственно
−
для этого интервала можно применить лемму 1, получив более оптимальный план ←
x,
где
δ(P − 1)
−
Rx .
R←
x = Rx −
P
Имеем противоречие.
До этого момента говорилось о том, как в оптимальном случае подзадания распределяются в среде MapReduce. Другим важным свойством оптимального плана является
вид последовательности, в которой подзадания выполняются на системе. Оказывается,
что в оптимальном плане все подзадания ωi задания Ji располагаются одним блоком
в последовательности выполнения подзаданий. Это демонстрируется следующей леммой.
Лемма 3. О группировке по заданиям в оптимальном плане. Для оптимального
плана x = (π, τb , τe ) и i = j справедливо:
(1)
(2)
(3)
τe (Ri ) τe (Rj ) =⇒
τe (Ri ) τe (Rj ) =⇒
τe (Ri ) τe (Rj ) =⇒
∀ri ∈ Ri ∀rj ∈ Rj
∀ri ∈ Ri ∀mj ∈ Mj
∀ωi ∈ Ωi ∀ωj ∈ Ωj
τe (ri ) τb (rj ),
τe (ri ) τb (mj ),
τe (ωi ) τb (ωj ).
Д о к а з а т е л ь с т в о.
(1) Предположим противное, а именно:
Пусть ∃Ri Rj τe (Ri ) τe (Rj ) ∃ri ∈ Ri ∃ρ ∈ Rj : τe (ri ) > τb (ρ).
Отсюда следует, что
τb (ρ) < τe (Ri ).
Положим
τe (ρ) τe (Ri ).
60
(A)
Если это не так, то изменим исходный план, проведя сдвиг подзадания ρ на временной
отрезок [τb (ρ) + (τe (Ri ) − τe (ρ)), τe (Ri )]. При этом задания, выполняющиеся на том же
процессоре и находящиеся на временном отрезке [τe (ρ), τe (Ri )], перейдут на отрезок
[τb (ρ), τb (ρ) + (τe (Ri ) − τe (ρ))]. При таком изменении увеличивается только значение
τe (ρ) времен окончаний подзаданий. При этом τe (ρ) = τe (Ri ) τe (Rj ), следовательно,
при данном изменении не увеличилось τe (Rj ), потому не возросла целевая функция
Rx . Стало быть, допущение (A) может быть сделано без нарушения оптимальности
плана x.
Далее, чтобы продемонстрировать противоречие, из плана x построим более оптимальный x. Для этого определим время выполнения ρ до момента окончания выполнения Ri как
Δ = τe (Ri ) − τb (ρ).
Проведем разбиение подзаданий Ω по моменту времени Θ = {τe (Ri )}, как это было
сделано в лемме 1. Получим новое множество подзаданий Ω, где вместо ρ будут присутствовать ρl и ρr . Разобьем ρl на P − 1 равных частей, образуя новые подзадания
{ρ1 , ..., ρP −1 } и другое множество подзаданий Ω̃:
⎧
Ω̃ = {ρ1 , ..., ρP −1 } ∪ Ω \ ρl ,
⎪
⎪
⎪
⎪
τb (ρ1 ) = τb (ρl ) = τe (Ri ) − Δ,
⎨
τe (ρk ) = τb (ρk+1 ) = τb (ρk ) + PΔ
−1 , k ∈ [1, ..., P − 2],
⎪
l
⎪
⎪ τe (ρP −1 ) = τe (ρ ) = τe (Ri ),
⎪
⎩
π(ρk ) = π(ρl ).
Теперь изменим план x, получив план x̃, для которого время отклика R будет меньше. Для этого проведем следующие операции:
1. Для всех элементов Ω̃ определим x̃ = (π̃, τ˜b , τ˜e ) идентично x.
2. Для подзаданий Ωr = {ω ∈ Ω̃ : τb (ω) τe (Ri )} проведем временной сдвиг плана
на PΔ
−1 , а именно:
τ˜b (ω) = τb (ω) + PΔ
−1 ,
Δ
τ˜e (ω) = τe (ω) + P −1 .
3. Переместим подзадания {ρ1 , ..., ρP −1 } на освободившееся место
⎧
τ˜b (ρk ) = τe (Ri ), k ∈ [1, ..., P − 1],
⎪
⎪
⎨
τ˜e (ρk ) = τe (Ri ) + PΔ
−1 , k ∈ [1, ..., P − 1],
⎪
k,
k ∈ [1, ..., π(ρk ) − 1],
⎪
⎩ π̃(ρk ) =
k + 1, k ∈ [π(ρk ), ..., P − 1].
(B)
4. Заметим, что теперь процессор π(ρ) простаивает на временном интервале
[τe (Ri )−Δ, τe (Ri )+ PΔ
−1 ]. Соответственно выполняются условия леммы 1 для этого интервала. Применим лемму 1 для плана x̃, не изменяя обозначение полученного плана. По лемме в новом плане размер интервала выполнения заданий
уменьшается в PP−1 раз. То есть размер нового интервала будет
Δ
P −1
P
P −1
· Δ+
=
·Δ·
= Δ.
P
P −1
P
P −1
Получаем, что на интервале τe (Ri ), τe (Ri ) + PΔ
−1 все процессоры простаивают.
61
5. По утверждению шага 4 можно провести сдвиг, обратный тому, что был на шаге 2, не нарушая корректность плана. То есть для подзаданий Ωr = {ω ∈ Ω̃ :
τb (ω) τe (Ri )} проведем временной сдвиг плана по времени на PΔ
−1 , а именно:
τ˜b (ω) = τb (ω),
τ˜e (ω) = τe (ω).
Покажем, что для плана x̃: 1) τ̃e (Rk ) τe (Rk ) ∀k; 2) τ̃e (Ri ) < τe (Ri ).
Действительно,
1. По построению плана x̃ можно заметить, что ∀ω ∈ Ω̃ τ̃e (ω) τe (ω). Отсюда
следует, что ∀ri ∈ R̃i τ̃e (ri ) τe (ri ). Поэтому
∀Ri τ̃e (Ri ) τe (Ri ).
2. Пусть r ∈ R̃i : τe (ri ) = τe (Ri ), тогда после применения леммы 1 на шаге 4 все
вычисления на интервале [τe (Ri ) − Δ, τe (Ri )] сократятся в PP−1 раз. Тогда
τ̃e (Ri ) = τ̃e (r) = τe (r) −
P −1
· (τe (r) − max{τb (r); τe (Ri ) − Δ}) < τe (r) = τe (Ri ).
P
По определению целевой функции (2.4) получаем
τ̃e (Rk ) −
r(Rk ) < τe (Ri ) +
τ̃e (Rk ) −
r(Rk ) Rx ,
Rx̃ = τ̃e (Ri ) +
k=i
k=i
k
k
что противоречит оптимальности x!
(2) С точки зрения плана выполнения вычислений разница между подзаданием
rj ∈ Rj и mj ∈ Mj состоит лишь в том, что на mj ∈ Mj накладывается дополнительное
ограничение (2.3): ∀m ∈ Mj , ∀r ∈ Rj , τb (r) τe (m). То есть при изменении плана,
в котором τe (m) увеличивается, оно может привести к нарушению корректности плана. Такие изменения плана в доказательстве (1) выделены как (A), (B). Заметим, что
в обоих случаях при переходе к новому плану выполняется ограничение
τe (mj ) τe (Ri ).
Применив результат пункта (1), получим
τe (mj ) τe (Ri ) τe (rj ).
Соответственно корректность плана выполняется, и доказательство можно повторить
для (2).
(3) Здесь требуется лишь заметить, что (1), (2) =⇒ (3).
Следующая теорема определяет оптимальный план в среде без коммуникаций.
Теорема 1. Об оптимальном плане в среде без коммуникаций. Для оптимального
плана x = (π, τb , τe ) в среде MapReduce без коммуникаций верно, что
(1) в каждый момент вычислений все процессоры обрабатывают ровно одно задание:
⎧
∀k ∈ [1..P ],
⎨ ω k ∈ Ωi ,
t0 ∈ [τb (ωk ), τe (ωk )], ∀k ∈ [1..P ],
∃Ωi ∃{ω1 , ..., ωP } :
∀t0 ∈ min τb (ω), max τe (ω)
ω∈Ω
ω∈Ω
⎩
∀k ∈ [1..P ].
π(ωk ) = k,
62
(2) задания исполняются в порядке возрастания их общего времени исполнения:
τe (Ji ) τe (Jj ) ⇐⇒ T1 (Ji ) T1 (Jj ).
Д о к а з а т е л ь с т в о.
(1) Из лемм 2 и 3 непосредственно следует утверждение (1).
(2) Продемонстрируем, как последовательность исполнения заданий может повлиять на целевую функцию – время отклика Rx .
Определим перестановку κ : [1..|J|] −→ [1..|J|]. Найдем такую перестановку исполнения заданий κ, при которой оптимальный план, построенный на κ, давал бы минимальное время отклика Rκ . Удовлетворяя условиям лемм 2 и 3, для оптимального плана
по заданной перестановке κ можно однозначно определить время окончания работы
каждого задания, а именно
i=s
TP (Jκi ),
(3.1)
τe (Jκs ) =
i=1
где TP – оптимальное время вычисления задания на системе из P процессоров. Для задания Ji ∈ J
T1 (Ji )
.
(3.2)
TP (Ji ) =
P
Тогда из (2.4) и (3.1) получаем
Rκ =
|J|
i=1
(τe (Jκi ) − r(Jκi )) =
|J|
i=1
(N − i + 1)TP (Jκi ) −
|J|
r(Ji ).
i=1
Наблюдая первое слагаемое выражения (3.2), можно заметить, что
κ = argmin Rκ ⇐⇒ κ : TP (Jκi+1 ) T (Jκi ) ∀i ∈ [1..|J| − 1].
Это означает выполнение заданий в порядке возрастания общего времени их исполнения T1 = P · TP , что соответствует условию (2).
4. Оценка эффективности плана в среде с задержками на коммуникацию.
Задержки на коммуникацию можно разделить на зависимые от объема передаваемых
данных и независимые. Следуя линейной модели передачи данных [21], общее время
передачи
Sdata
+ Δt ,
T =
Bchannel
где Bchannel – ширина (скорость) канала передачи; Sdata – размер передаваемых данных; Δt – независимая задержка на коммуникацию.
Проведенные ранее в п. 3 рассуждения могут быть повторены для случая c ненулевой общей коммуникацией и нулевой независимой задержкой на коммуникацию, т. е. где
T1 (Ji ) = 0 и Δt = 0 . В этом случае задание Ji будет представлено как объединение заданий выполнения Map, передачи данных и выполнения Reduce, т. е. Ji = Mi ∪ Ti ∪ Ri .
Тогда в пункт (2.3) определения корректности плана будут добавлены зависимости
между заданиями Mi , Ti и Ti , Ri соответственно. В остальном изменений нет и соответственно принцип доказательства теоремы 1 и сопутствующих лемм останется прежним.
63
В случае ненулевой общей коммуникации и ненулевой независимой задержкой
на коммуникацию, т. е. где T1 (Ji ) = 0 и Δt = 0, рассуждения предыдущей части повторены быть не могут. В этом случае время отклика для некоторого плана z в условиях,
когда все задания поступают на систему в момент времени 0, может быть выражено
следующим образом:
Rz =
|J|
(|J| − i + 1)
i=1
T1 (Ji )
+ Δt Kz (i) ,
Kz (i)
(4.1)
где Kz (i) – среднее число машин, обрабатываемых задание Ji . В рассматриваемом более общем случае может существовать план, более оптимальный, чем предлагаемый
ранее план x. Следующая теорема оценивает относительное отклонение плана x от оптимального.
Теорема 2. Оценка эффективности плана:
P2
T1 (Ji )
ΔR
, L = min
2
.
Ji ∈J
Rx
P +L
Δt
Д о к а з а т е л ь с т в о. Положим N = |J|, тогда
⎡
N
ΔR (2.4) ⎢
i=1
= ⎢
⎣
Rx
τe (Ji ) −
N
i=1
N
⎡
N
⎤
τe (Jpi )
(τe (Ji ))
(Ji )
(N − i + 1)( T1K
−
⎥ (4.1) ⎢ i=1
⎥ = ⎢
⎣
⎦
N
i=1
⎡
N
⎢ i=1
=⎢
⎣
i=1
(Ji )
(N − i + 1) T1K
−
N
(N − i + 1)
i=1
T1 (Jpi )
K(pi )
(...)
⎤
T1 (Jpi )
K(pi )
+ Δt (K − K(pi )))
(Ji )
(N − i + 1)( T1K
+ Δt K)
⎡
N
⎥ ⎢ i=1
⎥+⎢
⎦ ⎣
N
(N − i + 1)Δt (K − K(pi ))
i=1
(Ji )
(N − i + 1)( T1K
+ Δt K)
⎤
⎥
⎥ ...
⎦
По теореме 1 для случая Δt = 0 имеем
N
T1 (Jpi ) T1 (Ji )
,
(N − i + 1)
K(pi )
K
i=1
N
(N − i + 1)
i=1
поэтому числитель первого слагаемого можно оценить сверху нулем. Для второго слагаемого заметим, что
Δt (K − K(pi )) Δt (K − 1),
так как K(pi ) 1.
Продолжая цепочку неравенств, получаем
N
... 0 +
i=1
N
(N − i +
i=1
64
(N − i + 1)Δt (K − 1)
N
j=N −i+1
=
(Ji )
1)( T1K
+ Δt K)
jΔt (K − 1)
i=1
N
j=1
T (J
)
j( 1 NK−j+1
+ Δt K)
⎤
⎥
⎥=
⎦
N
N
j=1
⎛
E=⎝
jΔt K
j=1
2
N (N + 1)K 2
j(
T1 (JN −j+1 )
K
N
j=1
= ⎛
N
+ Δt K)
⎝ j=1
⎞
j
1
j
T1 (JN −j+1 )
K
N
j=1
⎞ =
1
,
E
+ 1⎠
jΔt K
L
T1 (JN −j+1 )
2
N (N + 1)L
= 2 + 1. (4.2)
+ 1⎠ Δt
N (N + 1)K 2
2
K
Из оценки (4.2) окончательно имеем
K2
1
.
E
L + K2
5. Заключение. В статье была предложена теоретическая модель вычислений
в среде MapReduce. На базе модели был показан оптимальный план решения заданий
в среде MapReduce в условиях отсутствия коммуникаций, который был использован
и для случая с коммуникациями. Была проведена оценка его эффективности.
При подстановке реальных цифр сделанная оценка эффективности показала, что
для локальной сети из порядка 5000 процессоров предлагаемый в статье план будет
отличен от оптимального не более чем на 50% по величине целевой функции – среднее
время нахождения заданий в системе. При этом для сетей с высокими задержками,
такими как в сети из компьютеров, соединенных через Интернет, уже для при 100 вычислительных узлах возможно 50%-ное отклонение от оптимального плана. Соответственно в случае использования MapReduce в сетях с большой задержкой необходим
особый алгоритм, учитывающий неоднородность сети, и возможно асинхронное выполнение заданий.
Рассматриваемая теоретическая модель накладывает существенное ограничение,
полагая, что задания могут делиться произвольным образом. На практике возникают
ситуации, когда задание может делиться лишь на весьма ограниченное число подзаданий для исполнения функции Map или Reduce. В общем случае задача отыскания
оптимального плана с указанными ограничениями является NP-трудной [9]. Впрочем,
и в этом случае может существовать алгоритм отыскания плана, близкого к оптимуму.
Поиск такого алгоритма может быть целью дальнейших исследований.
Автор благодарит своего научного руководителя проф. Ю. К. Демьяновича и рецензента проф. И. В. Романовского за помощь в работе и конструктивные замечания.
Литература
1. Ghemawat S., Dean J. MapReduce: Simplified Data Processing on Large Clusters // Proc. of the
Sixth Symposium on Operating System Design and Implementation. San Francisco, USA, 2004. Vol. 6, N 10.
P. 137–150.
2. Немнюгин С. А. Основы параллельного программирования с использованием MPI. URL:
http://www.intuit.ru.
3. Jin C., Buyya R. MapReduce programming model for .NET-based distributed computing: Technical
Report GRIDS-TR-2008-15. The University of Melbourne, Australia: Grid Computing and Distributed
Systems Laboratory, 2008. 10 p.
4. Berthold J., Dieterle M., Loogen R. Implementing parallel google map-reduce in eden // eds: H. Sips,
D. Epema, H. Lin. Lecture Notes in Computer Science: Springer-Verlag, 2009. Vol. 5704. P. 990–1002.
65
5. Pinedo M. Scheduling: Theory, Algorithms, and Systems. Prentice Hall: Englewood Cliffs. NJ, USA,
1995. 678 p.
6. Романовский И. В. Субоптимальные решения. Петрозаводск: Изд-во Петрозаводск. гос. ун-та,
1998. 97 с.
7. Демьянович Ю. К., Бурова И. Г. Алгоритмы параллельных вычислений и программирование
(курс лекций). СПб.: Изд-во С-Петерб. ун-та, 1995. 207 с.
8. Вахитов А. Т., Граничин О. Н., Паньшенсков М. А. Методы оценивания пропускной способности каналов данных в распределенных системах // Нейрокомпьютеры: разработка, применение. 2009.
Вып. 11. С. 45–52.
9. Clyde L. Monma, Chris N. Potts. On the Complexity of Scheduling with Batch Setup Times //
Operations Research. 1989. Vol. 37, N 5. P. 798–804.
10. Yu Jia, Buyya Rajkumar. Workflow Scheduling Algorithms for Grid Computing // Studies in
Computational Intelligence. 2008. Vol. 146. P. 173–214.
11. Паньшенсков М. А. Адаптивный метод управления потоком решения изолированных заданий
в параллельной вычислительной среде // Стохастическая оптимизация в информатике. 2008. Вып. 4.
C. 185–195.
12. Паньшенсков М. А. Динамическое планирование коммуникаций и методы оценивания пропускной способности каналов данных в грид // Труды конференции «Научный сервис в сети Интернет:
масштабируемость, параллельность, эффективность». 2009. С. 403–408.
13. Xhafa F., Carretero J., Barolli L., Durresi A. Immediate mode scheduling in grid systems // Intern.
J. Web and Grid Services. 2007. Vol. 3, N 2. P. 219–236.
14. Xiaoshan He, Sun Xian-He, von Laszewski Gregor. QoS Guided Min-Min Heuristic for Grid Task
Scheduling // Computer Science and Technology. 2003. Vol. 18, Issue 4. P. 442–451.
15. Hef Yuxiong, Jing Hsu Wen, Leiserson Charles E. Provably Efficient Online Non-clairvoyant
Adaptive Scheduling // IEEE Transactions on Parallel and Distributed Systems archive. 2008. Vol. 19,
Issue 9. P. 1263–1279.
16. Agrawal Kunal, He Yuxiong, Jing Hsu Wen, Leiserson Charles E. Adaptive task scheduling with
parallelism feedback // PPoPP (New York, USA). 2006. P. 100–109.
17. Eisenbrand F., Rothvo T. Static-priority Real-time Scheduling: Response Time Computation
is NP-hard // IEEE Real-Time Systems Symposium (RTSS). 2008. P. 397–406.
18. Hall Leslie A., Shmoys David B., Wein Joel. Scheduling to minimize average completion time: off-line
and on-line algorithms // SODA. Society for Industrial and Applied Mathematics. 1996. P. 142–151.
19. Chekuri C., Motwani R., Natarajan B., Stien C. Approximation techniques for average completion
time scheduling // SODA. Society for Industrial and Applied Mathematics. 1997. P. 609–618.
20. Turek John, Ludwig Walter, Wolf Joel et al. Scheduling parallelizable tasks to minimize average
response time // SPAA. 1994. P. 200–209.
21. Panshenskov M., Vakhitov A. Transfer Speed Estimation for Adaptive Scheduling in the Data
Grid // IEEE. Workshops at the Grid and Pervasive Computing Conference. 2009. P. 58–63.
Статья рекомендована к печати проф. Л. А. Петросяном.
Статья принята к печати 16 декабря 2010 г.
Документ
Категория
Без категории
Просмотров
5
Размер файла
392 Кб
Теги
mapreduce, задание, среды, неограниченных, делимых, план, эффективные, распределение
1/--страниц
Пожаловаться на содержимое документа