Давайте предположим , что у нас есть большой набор задач и сборник идентичны (с точки зрения производительности процессоров) которые работают полностью параллельно. Для интересующих нас сценариев мы можем принять . Каждый занимает некоторое количество времени / циклов, чтобы завершиться, как только он назначен процессору и после назначения он не может быть переназначен до завершения (процессоры всегда в конечном итоге выполняют назначенные задачи). Предположим, что каждый занимает некоторое количество неизвестных заранее циклов , взятых из некоторого дискретного случайного распределения. Для этого вопроса, мы можем даже предположить , простое распределение: , и все попарно независимы. Поэтому и .
Предположим, что статически в момент времени / цикла 0 все задачи назначаются как можно более равномерно всем процессорам, равномерно случайным образом; поэтому каждому процессору назначается задач (мы также можем предположить, что для целей вопроса). Мы называем временной интервал временем / циклом, в течение которого последний процессор завершает свою назначенную работу, заканчивает работу, для которой он был назначен. Первый вопрос:
В зависимости от , и , каков размер ? В частности, что такое ? ?
Второй вопрос:
Пусть , и все Х я попарно независимы, поэтому μ я = 3 и σ 2 = 1 . В зависимости от m , n и этих новых X i , каков состав? Интересно, как это соотносится с ответом из первой части?
Некоторые простые мысленные эксперименты показывают, что ответ на последний вопрос заключается в том, что срок службы больше. Но как это можно определить количественно? Я буду рад опубликовать пример, если это либо (а) спорные или (б) неясно. В зависимости от успеха с этим, я опубликую последующий вопрос о динамической схеме назначения при тех же самых предположениях. Заранее спасибо!
Анализ простого случая:
Если , то все n задач запланированы на один и тот же процессор. Makepan M - это просто время, чтобы выполнить n задач полностью последовательно. Следовательно, E [ M ] и V a r [ M ]
Кажется, что можно использовать этот результат, чтобы ответить на вопрос при ; мы просто должны найти выражение (или близкое приближение) для макс ( Y 1 , Y 2 , . . . , У м ) , где Y я = Х я п , случайная величина сμY=nиσ 2 Y =n . Это направление в правильном направлении?
Ответы:
Поскольку , мы можем рассматривать это в терминах k и n вместо n и m . Допустим, T i - это время, которое требуется i- му процессору для завершения своей работы.m=k×n k n n m Ti i
По мере роста вероятность того, что T i = 5 k (процессору было назначено только T = 5 задач) для некоторого i, приближается к 1 , поэтому определяемый диапазон составляет m a x ( T i ) , E [ M ] приближается к 5 k .n Ti 5k T=5 i 1 max(Ti) E[M] 5k
Для второго сценария это Так что увеличение числа процессоров делает 4–2 разбиение лучше.4k
Как насчет - увеличение количества задач на процессор? Увеличение k имеет противоположный эффект, оно снижает вероятность того, что у процессора будет неудачный набор задач. Я сейчас иду домой, но вернусь к этому позже. Моя догадка заключается в том, что с ростом k разница в E [ M ] между 4–2 и 5–1 расщеплениями исчезает, E [ M ] становится одинаковым для обоих. Так что я бы предположил, что 4–2 всегда лучше, за исключением, может быть, некоторых особых случаев (очень маленьких конкретных значений k и n ), если даже этого.k k k E[M] E[M] k n
Итак, подведем итог:
источник
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.
Letn=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
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:
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
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. LetX=maxmi=1Xi denote the makespan for the first distribution, and Y=maxmi=1Yi 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 x≥kμ , independence yields
источник