• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Parallel and Distributed Systems, IEEE Transactions on >The Complexity of Optimal Job Co-Scheduling on Chip Multiprocessors and Heuristics-Based Solutions
【24h】

The Complexity of Optimal Job Co-Scheduling on Chip Multiprocessors and Heuristics-Based Solutions

机译：芯片多处理器上最优作业协同调度的复杂性和基于启发式的解决方案

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

摘要

In Chip Multiprocessors (CMPs) architecture, it is common that multiple cores share some on-chip cache. The sharing may cause cache thrashing and contention among co-running jobs. Job co-scheduling is an approach to tackling the problem by assigning jobs to cores appropriately so that the contention and consequent performance degradations are minimized. Job co-scheduling includes two tasks: the estimation of co-run performance, and the determination of suitable co-schedules. Most existing studies in job co-scheduling have concentrated on the first task but relies on simple techniques (e.g., trying different schedules) for the second. This paper presents a systematic exploration to the second task. The paper uncovers the computational complexity of the determination of optimal job co-schedules, proving its NP-completeness. It introduces a set of algorithms, based on graph theory and Integer/Linear Programming, for computing optimal co-schedules or their lower bounds in scenarios with or without job migrations. For complex cases, it empirically demonstrates the feasibility for approximating the optimal effectively by proposing several heuristics-based algorithms. These discoveries may facilitate the assessment of job co-schedulers by providing necessary baselines, as well as shed insights to the development of co-scheduling algorithms in practical systems.
机译：在芯片多处理器（CMP）架构中，常见的是多个内核共享一些片上缓存。共享可能导致共同运行的作业之间发生高速缓存抖动和争用。作业协同调度是一种通过适当地将作业分配给核心来解决问题的方法，以使竞争和随之而来的性能下降降到最低。作业协同调度包括两个任务：协同运行性能的估计，以及合适的协同调度的确定。现有的大多数工作联合调度研究都集中在第一个任务上，而第二个则依赖简单的技术（例如尝试不同的调度）。本文对第二个任务进行了系统的探索。本文揭示了确定最佳工作协同计划的计算复杂性，证明了其NP完备性。它介绍了一组基于图论和整数/线性规划的算法，用于在有或没有作业迁移的情况下计算最佳协同计划或其下限。对于复杂的情况，它通过提出几种基于启发式的算法，从经验上证明了有效逼近最优值的可行性。这些发现可能会通过提供必要的基准来促进对工作调度员的评估，并有助于洞察实际系统中的调度算法。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号