...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Annals of Operations Research >Scheduling Malleable Tasks on Parallel Processors to Minimize the Makespan
【24h】

Scheduling Malleable Tasks on Parallel Processors to Minimize the Makespan

机译：在并行处理器上安排可延展的任务，以最大程度地缩短制造时间

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

摘要

The problem of optimal scheduling n tasks in a parallel processor system is studied. The tasks are malleable, i.e., a task may be executed by several processors simultaneously and the processing speed of a task is a nonlinear function of the number of processors allocated to it. The total number of processors is m and it is an upper bound on the number of processors that can be used by all the tasks simultaneously. It is assumed that the number of processors is sufficient to process all the tasks simultaneously, i.e. n ≤ m. The objective is to find a task schedule and a processor allocation such that the overall task completion time, i.e. the makespan, is minimized. The problem is motivated by real-life applications of parallel computer systems in scientific computing of highly parallelizable tasks. An O(n) algorithm is presented to solve this problem when all the processing speed functions are convex. If these functions are all concave and the number of tasks is a constant, the problem can be solved in polynomial time. A relaxed problem, in which the number of processors allocated to each task is not required to be integer, can be solved in O(n max{m, n log~2 m}) time. It is proved that the minimum makespan values for the original and relaxed problems coincide. For n = 2 or n = 3, an optimal solution for the relaxed problem can be converted into an optimal solution for the original problem in a constant time.
机译：研究了并行处理器系统中n个任务的最优调度问题。任务是可延展的，即，任务可以同时由多个处理器执行，并且任务的处理速度是分配给它的处理器数量的非线性函数。处理器总数为m，它是所有任务可同时使用的处理器数量的上限。假定处理器的数量足以同时处理所有任务，即n≤m。目的是找到任务时间表和处理器分配，以使总的任务完成时间，即制造时间最小化。该问题是由并行计算机系统在高度可并行化任务的科学计算中的实际应用引起的。当所有处理速度函数都是凸的时，提出了一种O（n）算法来解决这个问题。如果这些函数都是凹函数并且任务数是常数，则可以在多项式时间内解决问题。可以在O（n max {m，n log〜2 m}）的时间内解决一个轻松的问题，其中分配给每个任务的处理器数量不需要为整数。事实证明，原始问题和松弛问题的最小makepan值一致。对于n = 2或n = 3，可以在恒定时间内将松弛问题的最优解转换为原始问题的最优解。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号