We study the problem of scheduling an arbitrary computational DAG on a fixed number of processors while minimizing the makespan. While previous works have mostly studied this problem in relatively restricted models, we define and analyze DAG scheduling in the Bulk Synchronous Parallel (BSP) model, which is a well-established parallel computing model that captures the communication cost between processors much more accurately. We provide a detailed taxonomy of simpler scheduling models that can be understood as variants or special cases of BSP, and discuss the properties of the problem and the optimum cost in these models, and how they differ from BSP. This essentially allows us to dissect the different building blocks of the BSP model, and gain insight into how each of these influences the scheduling problem. We then analyze the hardness of DAG scheduling in BSP in detail. We show that the problem is solvable in polynomial time for some very simple classes of DAGs, but it is already NP-hard for in-trees or DAGs of height 2. We also separately study the subproblem of scheduling communication steps, and we show that the NP-hardness of this problem can depend on the problem parameters and the communication rules within the BSP model. Finally, we present and analyze a natural formulation of our scheduling task as an Integer Linear Program.
翻译:我们研究了在固定的处理器数量上任意计算DAG,同时尽量减少化石板的问题。虽然以前的工作大多在相对有限的模型中研究这一问题,但我们在Bulk Synchronous平行模型中界定和分析DAG的时间安排,这是一个非常成熟的平行计算模型,可以更准确地捕捉处理器之间的通信成本。我们详细分类了可以被理解为BSP变异或特殊案例的更简单的列表模型,并讨论了问题的特点和这些模型的最佳成本,以及它们与BSP的不同之处。这基本上使我们能够分解BSP模型的不同建筑块,并深入了解这些模型对时间安排问题的影响。然后我们详细分析BSP中DAG的时间安排的严谨性。我们表明,对于一些非常简单的DAG的类别,这一问题在多式时间里是可以溶解的,但是对于在树内或高度的DAGs来说,它已经很硬,而且这些模型与BSP的不同之处。我们还可以分别研究如何分解BSP模型的子问题,并且我们展示了BSP的自然定位规则的特性。</s>