• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>IEEE Transactions on Parallel and Distributed Systems >Optimal scheduling algorithm for distributed-memory machines
【24h】

Optimal scheduling algorithm for distributed-memory machines

机译：分布式内存机器的优化调度算法

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Task Scheduling is one of the key elements in any distributed-memory machine (DMM), and an efficient algorithm can help reduce the interprocessor communication time. As optimal scheduling of tasks to DMMs is a strong NP-hard problem, many heuristic algorithms have been introduced in the literature. This paper presents a Task Duplication based Scheduling (TDS) algorithm which can schedule directed acyclic graphs (DAGs) with a complexity of O(|V|/sup 2/), where |V| is the number of tasks in the DAG. This algorithm generates an optimal schedule for a class of DAGs which satisfy a simple cost relationship. The performance of the algorithm has been observed by its application to some practical DAGs, and by comparing it with other existing scheduling schemes in terms of the schedule length and algorithm complexity.
机译：任务调度是任何分布式内存机器（DMM）的关键要素之一，高效的算法可以帮助减少处理器间的通信时间。由于对DMM的最佳任务调度是一个强大的NP难题，因此文献中引入了许多启发式算法。本文提出了一种基于任务复制的调度（TDS）算法，该算法可以调度复杂度为O（| V | / sup 2 /）的有向无环图（DAG），其中| V |。是DAG中的任务数。该算法为满足简单成本关系的一类DAG生成最佳计划。通过将算法应用于一些实际的DAG并将其与其他现有调度方案进行比较，可以观察到该算法的性能，包括调度长度和算法复杂性。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号