• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>8th International Euro-Par Conference on Euro-Par 2002 Parallel Processing, Aug 27-30, 2002, Paderborn, Germany >A Semi-dynamic Multiprocessor Scheduling Algorithm with an Asymptotically Optimal Competitive Ratio
【24h】

A Semi-dynamic Multiprocessor Scheduling Algorithm with an Asymptotically Optimal Competitive Ratio

机译：具有渐近最优竞争比的半动态多处理器调度算法

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

摘要

In this paper, we consider the problem of assigning a set of n independent tasks onto a set of m identical processors in such a way that the overall execution time is minimized provided that the precise task execution times are not known a priori. In the following, we first provide a theoretical analysis of several conventional scheduling policies in terms of the worst case slowdown compared with the outcome of an optimal scheduling policy. It is shown that the best known algorithm in the literature achieves a worst case competitive ratio of 1 + 1/f(n) where f(n) = O(n~(2/3)) for any fixed m, that approaches to one by increasing n to the infinity. We then propose a new scheme that achieves a better worst case ratio of 1 + 1/g(n) where g(n) = Θ(n/log n) for any fixed m, that approaches to one more quickly than the other schemes.
机译：在本文中，我们考虑将n个独立任务的集合分配给m个相同处理器的集合的问题，以使总执行时间最小化（前提是事先不知道精确的任务执行时间）。在下文中，我们首先根据最坏情况下的速度降低与最佳调度策略的结果进行比较，对几种常规调度策略进行理论分析。结果表明，文献中最著名的算法实现了最坏情况下竞争比为1 + 1 / f（n），其中对于任何固定m，f（n）= O（n〜（2/3））通过将n增加到无穷大。然后，我们提出了一种新方案，该方案可实现更好的最坏情况比率1 + 1 / g（n），其中对于任何固定m，g（n）=Θ（n / log n），比其他方案更快地接近。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号