• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>IEEE Transactions on Parallel and Distributed Systems >An improved duplication strategy for scheduling precedence constrained graphs in multiprocessor systems
【24h】

An improved duplication strategy for scheduling precedence constrained graphs in multiprocessor systems

机译：一种用于在多处理器系统中调度优先约束图的改进复制策略

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

摘要

Scheduling precedence constrained task graphs, with or without duplication, is one of the most challenging NP-complete problems in parallel and distributed computing systems. Duplication heuristics are more effective, in general, for fine grain task graphs and for networks with high communication latencies. However, most of the available duplication algorithms are designed under the assumption of unbounded availability of fully connected processors, and lie in a high complexity range. Low complexity optimal duplication algorithms work under restricted cost and/or shape parameters for the task graphs. Further, the required number of processors grows in proportion to the task-graph size significantly. An improved duplication strategy is proposed that works for arbitrary task graphs, with a limited number of interconnection-constrained processors. Unlike most other algorithms that replicate all possible parents/ancestors of a given task, the proposed algorithm tends to avoid redundant duplications and duplicates the nodes selectively, only if it helps in improving the performance. This results in lower duplications and also lower time and space complexity. Simulation results are presented for clique and an interconnection-constrained network topology with random and regular benchmark task graph suites, representing a variety of parallel numerical applications. Performance, in terms of normalized schedule length and efficiency, is compared with some of the well-known and recently proposed algorithms. The suggested algorithm turns out to be most efficient, as it generates better or comparable schedules with remarkably less processor consumption.
机译：在并行和分布式计算系统中，调度优先约束的任务图（有无重复）是最具挑战性的NP完全问题之一。通常，对于细粒度的任务图和具有高通信延迟的网络，重复启发式方法更为有效。但是，大多数可用的复制算法都是在完全连接的处理器无限制的可用性的前提下设计的，并且其复杂度很高。低复杂度的最佳复制算法在任务图的受限成本和/或形状参数下工作。此外，所需的处理器数量与任务图的大小成比例地增加。提出了一种改进的复制策略，该策略适用于具有有限数量的受互连约束的处理器的任意任务图。与大多数复制给定任务的所有可能的父代/祖先的算法不同，所提出的算法倾向于避免冗余重复并有选择地复制节点，除非它有助于提高性能。这导致重复次数减少，时间和空间复杂度也降低。给出了针对集团和具有随机和常规基准任务图套件的受互连约束的网络拓扑的仿真结果，代表了多种并行数值应用。将性能（根据标准化的调度长度和效率）与某些众所周知的和最近提出的算法进行比较。所提出的算法被证明是最有效的，因为它可以产生更好的或可比的时间表，而处理器的消耗却明显更少。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号