任务完成时间的差异如何影响makepan？

Question

假设我们有大量任务$ tau_1， tau_2，...， tau_n $和一系列相同的（在性能方面）处理器$ rho_1， rho_2，...， rho_m $完全并联运行。对于感兴趣的方案，我们可以假设$ m leq n $。每个$ tau_i $分配给处理器$ rho_j $，就需要一定的时间/周期才能完成，并且一旦分配，它就无法重新分配到完成（处理器始终最终完成分配的任务）。让我们假设每个$ tau_i $都需要大量的时间/循环$ x_i $，未提前从某些离散的随机分发中获取。对于这个问题，我们甚至可以假设一个简单的分布：$ p（x_i = 1）= p（x_i = 5）= 1/2 $，所有$ x_i $都是成对的。因此，$ mu_i = 3 $和$ sigma^2 = 4 $。

假设在静态上，在时间/周期0上，所有任务均应尽可能均匀地分配给所有处理器，并随机均匀地分配；因此，每个处理器$ rho_j $均分配$ n/m $任务（我们也可以假设$ m | n $出于问题的目的）。我们将MakePan称为最后一个处理器$ rho^*$完成其分配工作的时间/周期，完成了分配的工作。第一个问题：

作为$ m $，$ n $和$ x_i $的功能，什么是makepan $ m $？具体来说，$ e [m] $是什么？ $ var [m] $？

第二个问题：

假设$ p（x_i = 2）= p（x_i = 4）= 1/2 $，并且所有$ x_i $都是成对独立的，因此$ mu_i = 3 $和$ sigma^2 = 1 $。作为$ m $，$ n $的函数，这些新的$ x_i $，什么是makepan？更有趣的是，它与第一部分的答案相比如何？

一些简单的思想实验证明了后者的答案是makepan更长。但是如何量化呢？如果这是（a）有争议或（b）不清楚的话，我很乐意发布一个示例。根据这一成功的成功，我将在这些相同的假设下发布有关动态分配方案的后续问题。提前致谢！

简单案例的分析：$ M = 1 $

如果$ m = 1 $，则所有$ n $任务都安排到同一处理器。 Makepan $ m $只是以完整的顺序方式完成$ n $任务的时候。因此，$$ begin {align*} e [m]＆= e [x_1 + x_2 + ... + x_n] ＆= e [x_1] + e [x_2] + ... + ... + e [x_n] = mu + mu + ... + ＆= n mu end {align*} $$和$$ begin {align*} var [m]＆= var [x_1 + x_2 + ... + x_n] = var [x_1] + var [x_2] + ... + var [x_n] ＆= sigma^2 + sigma^2 + ... + sigma ^2 ＆= n sigma^2 end {align*} $$

似乎可以使用此结果来回答$ m> 1 $的问题；我们只需要找到$ max（y_1，y_2，...，...，y_m）$的表达式（或关闭近似），其中$ y_i = x_ = x_ {i frac {n} {n} {m} {m} + 1} + x_ {i {i {i {i {i frac {n} {m} + 2} + ... + x_ {i frac {n} {m} {m} + frac {n} {m}} $，一个随机变量，带有$ mu_y = frac { n} {m} mu_x $和$ sigma_y^2 = frac {n} {m} {m} sigma_x^2 $。这是朝正确的方向前进吗？

Answer 1

作为$ m = k times n $，我们可以用$ k $和$ n $而不是$ n $和$ m $来查看它。假设$ t_i $是需要$ i $ th处理器完成其工作的时间。

随着$ n $的成长，$ t_i $ = $ 5K $（仅分配了$ t = 5 $ tasks）的可能性，对于某些$ i $ theres $ 1 $，因此使pan被定义为$ mathrm {maxrm {max}（max}（ t_i）$，$ e [m] $接近$ 5K $。

在第二种情况下，这是$ 4K $，因此增加处理器的数量使4-2拆分更好。

$ k $呢 - 增加每个处理器的任务数？增加$ k $具有相反的效果，这使得拥有一套不幸任务的处理器的可能性较小。我现在要回家，但我稍后再回家。我的“直觉”是，随着$ k $的增长，4-2分和5-1拆分之间的$ e [m] $差异消失了，$ e [m] $都相同。因此，我认为4-2总是更好，除了某些特殊情况（如果那样的话，$ k $和$ n $的特定值很小）。

因此总结：

• 较低的差异更好，所有其他差异是平等的。
• 随着处理器数量的增长，较低的方差变得越来越重要。
• 随着每个处理器的任务数量的增长，较低的差异变得不那么重要。

Answer 2

我发现，在考虑任务调度（以及诸如bin包装之类的密切相关的问题）时，启发式论点通常会非常误导。可能发生违反直觉的事情。对于这样一个简单的情况，实际上值得做概率理论。

让$ n = km $带$ k $ a正整数。假设$ t_ {ij} $是完成处理器$ i $的$ j $ TH任务所花费的时间。这是一个随机变量，带有平均$ mu $和差异$ sigma^2 $。在第一种情况下，预期的makepan是$$ e [m] = e [ max left { sum_ {j = 1}^k t_ {ij} mid i = 1,2， dots，m right，m right }]。 $$总和是平均$ k mu $和差异$ k sigma^2 $，假设$ t_ {ij} $都是IID（这比成对独立性更强大）。

现在，为了获得最大值的期望，要么需要有关分销的更多信息，要么必须满足于无分配界限，例如：

• 彼得·唐尼， 根据调度申请的最大值的期望，无分销范围, ，运营研究信 9, 189–201, 1990. doi：10.1016/0167-6377（90）90018-Z

如果处理器的总和是IID，则可以应用。如果基本时间是既独立的，则不一定是这种情况。特别是，由定理1 $$ e [m] le k mu + sigma sqrt {k} frac {n-1} { sqrt {2n-1}}}。 $$ DOWNEY还提供了特定的分销，尽管分布的变化如$ n $，但并非完全自然。

请注意，BOUND表示，随着任何参数的增加，预期的MakePAN可以增加：差异$ sigma^2 $，处理器$ n $的数量或每个处理器$ k $的任务数。

对于您的第二个问题，低变化的情况导致 更大 MakePan似乎是思想实验的不可能的结果。令$ x = max_ {i = 1}^m x_i $代表第一个分发的makepan，而第二个分发$ y = max_ {i = 1}^m y_i $在第二个发行版中（所有其他参数相同）。在这里，$ x_i $和$ y_i $表示$ K $的任务持续时间的总和与处理器$ i $在两个分布中相对应。对于所有$ x ge k mu $，独立性产生$$ pr [x le x] = prod_ {i = 1}^m pr [x_i le x] le le prod_ = 1}^m pr [y_i le x] = pr [y le x]。 $$由于最大值的概率分布的大部分质量将高于其平均值，因此$ e [x] $往往大于$ e [y] $。这不是一个完全严格的答案，但简而言之，第二种情况似乎是可取的。