Scheduling Parallel Task Graphs on (Almost) Homogeneous Multicluster Platforms
Scheduling Parallel Task Graphs on (Almost) Homogeneous Multicluster Platforms
复制标题
DOI：
10.1109/tpds.2009.11
复制
发表时间：
2009-07
影响因子：
5.3
通讯作者：
P. Dutot;Tchimou N'Takpé;F. Suter;H. Casanova
中科院分区：
文献类型：
--
作者：
P. Dutot;Tchimou N'Takpé;F. Suter;H. Casanova
以并行任务图形式构建的应用程序同时展现出数据并行性和任务并行性，并出现在许多领域。在并行平台上高效地调度这些应用程序一直是一个长期的挑战。对于单一同构平台，比如集群，在理论上（即有保证的算法）和实践中（即实用的启发式方法）都取得了一些成果。由于任务并行性，这些应用程序非常适合在可能跨越多个机构的多个集群的分布式平台上执行。然而，在这种情况下，唯一可用的结果是无保证的启发式方法。在本文中，我们开发了一种调度算法MCGAS，它适用于几乎同构的多集群平台。这样的平台经常作为多集群平台的大子集出现。我们的新贡献在于MCGAS计算任务分配，从而提供了（可调节的）性能保证。由于性能保证在实践中不一定意味着良好的平均性能，我们还将MCGAS与一种最近提出的无保证算法进行了比较。通过在广泛的实验场景中进行模拟，我们发现MCGAS比其竞争对手能带来更好的平均应用程序完工时间。
Applications structured as parallel task graphs exhibit both data and task parallelism and arise in many domains. Scheduling these applications efficiently on parallel platforms has been a long-standing challenge. In the case of a single homogeneous platform, such as a cluster, results have been obtained both in theory, i.e., guaranteed algorithms, and, in practice, i.e., pragmatic heuristics. Due to task parallelism, these applications are well suited for execution on distributed platforms that span multiple clusters possibly in multiple institutions. However, the only available results in this context are nonguaranteed heuristics. In this paper, we develop a scheduling algorithm, MCGAS, which is applicable to multicluster platforms that are almost homogeneous. Such platforms are often found as large subsets of multicluster platforms. Our novel contribution is that MCGAS computes task allocations so that a (tunable) performance guarantee is provided. Since a performance guarantee does not necessarily imply good average performance in practice, we also compare MCGAS with a recently proposed nonguaranteed algorithm. Using simulation over a wide range of experimental scenarios, we find that MCGAS leads to better average application makespans than its competitor.