首页> 外文会议>IEEE International Parallel Distributed Processing Symposium >Scheduling Tree-Shaped Task Graphs to Minimize Memory and Makespan
【24h】

Scheduling Tree-Shaped Task Graphs to Minimize Memory and Makespan

机译:计划树形任务图以最小化内存和Makespan

获取原文

摘要

This paper investigates the execution of tree-shaped task graphs using multiple processors. Each edge of such a tree represents a large IO file. A task can only be executed if all input and output files fit into memory, and a file can only be removed from memory after it has been consumed. Such trees arise, for instance, in the multifrontal method of sparse matrix factorization. The maximum amount of memory needed depends on the execution order of the tasks. With one processor the objective of the tree traversal is to minimize the required memory. This problem was well studied and optimal polynomial algorithms were proposed. Here, we extend the problem by considering multiple processors, which is of obvious interest in the application area of matrix factorization. With the multiple processors comes the additional objective to minimize the time needed to traverse the tree, i.e., to minimize the make span. Not surprisingly, this problem proves to be much harder than the sequential one. We study the computational complexity of this problem and provide an inapproximability result even for unit weight trees. Several heuristics are proposed, each with a different optimization focus, and they are analyzed in an extensive experimental evaluation using realistic trees.
机译:本文研究了使用多个处理器执行树形任务图的情况。这样一棵树的每个边缘代表一个大的IO文件。仅当所有输入和输出文件都适合内存时才能执行任务,并且仅在使用完文件后才能将其从内存中删除。例如,这种树出现在稀疏矩阵分解的多面方法中。所需的最大内存量取决于任务的执行顺序。使用一个处理器,树遍历的目的是使所需的内存最小化。对该问题进行了深入研究,并提出了最佳多项式算法。在这里,我们通过考虑多个处理器来扩展问题,这在矩阵分解的应用领域中具有明显的意义。带有多个处理器的另一个目标是最小化遍历树所需的时间,即最小化制造跨度。毫不奇怪,事实证明,这个问题比顺序问题要难得多。我们研究了此问题的计算复杂性,甚至对于单位权重树也提供了不可逼近的结果。提出了几种启发式算法,每种算法都有不同的优化重点,并使用现实树在广泛的实验评估中对其进行了分析。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号