Как разница во времени выполнения задачи влияет на продолжительность работы?

16

Давайте предположим , что у нас есть большой набор задач τ1,τ2,...,τn и сборник идентичны (с точки зрения производительности процессоров) ρ1,ρ2,...,ρm которые работают полностью параллельно. Для интересующих нас сценариев мы можем принять mn . Каждый τi занимает некоторое количество времени / циклов, чтобы завершиться, как только он назначен процессору ρjи после назначения он не может быть переназначен до завершения (процессоры всегда в конечном итоге выполняют назначенные задачи). Предположим, что каждый τi занимает некоторое количество неизвестных заранее циклов Xi , взятых из некоторого дискретного случайного распределения. Для этого вопроса, мы можем даже предположить , простое распределение: P(Xi=1)=P(Xi=5)=1/2 , и все Xi попарно независимы. Поэтому μi=3 и σ2=4 .

Предположим, что статически в момент времени / цикла 0 все задачи назначаются как можно более равномерно всем процессорам, равномерно случайным образом; поэтому каждому процессору ρj назначается n/m задач (мы также можем предположить, что m|n для целей вопроса). Мы называем временной интервал временем / циклом, в течение которого последний процессор ρ завершает свою назначенную работу, заканчивает работу, для которой он был назначен. Первый вопрос:

В зависимости от m , n и Xi , каков размер M ? В частности, что такое E[M] ? Var[M] ?

Второй вопрос:

Пусть , и все Х я попарно независимы, поэтому μ я = 3 и σ 2 = 1 . В зависимости от m , n и этих новых X i , каков состав? Интересно, как это соотносится с ответом из первой части?P(Xi=2)=P(Xi=4)=1/2Xiμi=3σ2=1mnXi

Некоторые простые мысленные эксперименты показывают, что ответ на последний вопрос заключается в том, что срок службы больше. Но как это можно определить количественно? Я буду рад опубликовать пример, если это либо (а) спорные или (б) неясно. В зависимости от успеха с этим, я опубликую последующий вопрос о динамической схеме назначения при тех же самых предположениях. Заранее спасибо!

Анализ простого случая: m=1

Если , то все n задач запланированы на один и тот же процессор. Makepan M - это просто время, чтобы выполнить n задач полностью последовательно. Следовательно, E [ M ]m=1nMn и V a r [ M ]

E[M]=E[X1+X2+...+Xn]=E[X1]+E[X2]+...+E[Xn]=μ+μ+...+μ=nμ
Var[M]=Var[X1+X2+...+Xn]=Var[X1]+Var[X2]+...+Var[Xn]=σ2+σ2+...+σ2=nσ2

Кажется, что можно использовать этот результат, чтобы ответить на вопрос при ; мы просто должны найти выражение (или близкое приближение) для макс ( Y 1 , Y 2 , . . . , У м ) , где Y я = Х я пm>1max(Y1,Y2,...,Ym) , случайная величина сμY=nYi=Xinm+1+Xinm+2+...+Xinm+nmиσ 2 Y =nμY=nmμX . Это направление в правильном направлении?σY2=nmσX2

Patrick87
источник
Хороший вопрос Если бы сегодня не было крайнего срока ...
Дэйв Кларк

Ответы:

8

Поскольку , мы можем рассматривать это в терминах k и n вместо n и m . Допустим, T i - это время, которое требуется i- му процессору для завершения своей работы.m=k×nknnmTii

По мере роста вероятность того, что T i = 5 k (процессору было назначено только T = 5 задач) для некоторого i, приближается к 1 , поэтому определяемый диапазон составляет m a x ( T i ) , E [ M ] приближается к 5 k .nTi5kT=5i1max(Ti)E[M]5k

Для второго сценария это Так что увеличение числа процессоров делает 4–2 разбиение лучше.4k

Как насчет - увеличение количества задач на процессор? Увеличение k имеет противоположный эффект, оно снижает вероятность того, что у процессора будет неудачный набор задач. Я сейчас иду домой, но вернусь к этому позже. Моя догадка заключается в том, что с ростом k разница в E [ M ] между 4–2 и 5–1 расщеплениями исчезает, E [ M ] становится одинаковым для обоих. Так что я бы предположил, что 4–2 всегда лучше, за исключением, может быть, некоторых особых случаев (очень маленьких конкретных значений k и n ), если даже этого.kkkE[M]E[M]kn

Итак, подведем итог:

  • Чем меньше дисперсия, тем лучше, при прочих равных условиях.
  • По мере роста числа процессоров, более низкая дисперсия становится более важной.
  • По мере роста числа задач на процессор, более низкая дисперсия становится менее важной.
svinja
источник
+1 Отличная интуиция, и это помогает прояснить мое мышление. Таким образом, увеличение числа процессоров приводит к увеличению рабочего времени при слабом допущении масштабирования; и увеличение количества задач имеет тенденцию к уменьшению рабочего периода при сильном допущении масштабирования (конечно, это занимает больше времени; я имею в виду, что соотношение работы / рабочего времени улучшается). Это интересные наблюдения, и они кажутся правдой;
Patrick87
1(1P(X=5)k)n1kn; the latter by the fact that Var[X+X]=Var[X]+Var[X]=2σ24σ2=4Var[X]=Var[2X]... so the variance doesn't increase linearly as a function of k. Is that compatible with your thinking (that's how I'm interpreting what you have so far)?
Patrick87
I don't know where the "hunch" came from; it is not consistent with the rest of the heuristic reasoning.
András Salamon
2

I find that heuristic arguments are often quite misleading when considering task scheduling (and closely related problems like bin packing). Things can happen that are counter-intuitive. For such a simple case, it is worthwhile actually doing the probability theory.

Let n=km with k a positive integer. Suppose Tij is the time taken to complete the j-th task given to processor i. This is a random variable with mean μ and variance σ2. The expected makespan in the first case is

E[M]=E[max{j=1kTiji=1,2,,m}].
The sums are all iid with mean kμ and variance kσ2, assuming that Tij are all iid (this is stronger than pairwise independence).

Now to obtain the expectation of a maximum, one either needs more information about the distribution, or one has to settle for distribution-free bounds, such as:

  • Peter J. Downey, Distribution-free bounds on the expectation of the maximum with scheduling applications, Operations Research Letters 9, 189–201, 1990. doi:10.1016/0167-6377(90)90018-Z

which can be applied if the processor-wise sums are iid. This would not necessarily be the case if the underlying times were just pairwise independent. In particular, by Theorem 1 the expected makespan is bounded above by

E[M]kμ+σkn12n1.
Downey also gives a particular distribution achieving this bound, although the distribution changes as n does, and is not exactly natural.

Note that the bound says that the expected makespan can increase as any of the parameters increase: the variance σ2, the number of processors n, or the number of tasks per processor k.

For your second question, the low-variance scenario resulting in a larger makespan seems to be an unlikely outcome of a thought experiment. Let X=maxi=1mXi denote the makespan for the first distribution, and Y=maxi=1mYi for the second (with all other parameters the same). Here Xi and Yi denote the sums of k task durations corresponding to processor i under the two distributions. For all xkμ, independence yields

Pr[Xx]=i=1mPr[Xix]i=1mPr[Yix]=Pr[Yx].
Since most of the mass of the probability distribution of the maximum will be above its mean, E[X] will therefore tend to be larger than E[Y]. This is not a completely rigorous answer, but in short, the second case seems preferable.
András Salamon
источник