• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>8th World Multi-Conference on Systemics, Cybernetics and Informatics(SCI 2004) vol.2: Computing Techniques >An Exact Scheduling Algorithm for Two, Linear-Nonlinear Clusters
【24h】

An Exact Scheduling Algorithm for Two, Linear-Nonlinear Clusters

机译：两个线性非线性集群的精确调度算法

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

摘要

In parallel and distributed processing, tasks are ordinarily clustered and assigned to different processors before they are scheduled. The assignment of tasks to processors is called clustering. Within each cluster, the ordering of tasks for execution, including the specification of the starting time of each task, is called cluster scheduling. The set of tasks is typically modelled as a directed acyclic task graph, capturing the partial order relationship among the tasks. As a result of the clustering process, with respect to the DAG, the set of tasks in each cluster either forms a total ordering or it doesn't . A cluster is called linear if the tasks in it are totally ordered, otherwise it is called nonlinear. It has been shown that the problem of finding an optimal schedule for two clusters with one cluster being linear and the other nonlinear is strongly NP-hard. In this paper, we develop an exact, polynomial time algorithm to solve the above problem when tasks are restricted to unit tasks.
机译：在并行和分布式处理中，通常在计划任务之前将任务集群并分配给不同的处理器。将任务分配给处理器称为集群。在每个群集中，要执行的任务的顺序（包括每个任务的开始时间的规范）称为群集调度。通常将任务集建模为有向非循环任务图，以捕获任务之间的部分顺序关系。集群过程的结果是，相对于DAG，每个集群中的任务集要么形成总顺序，要么不形成总顺序。如果群集中的任务是完全有序的，则称为线性群集，否则称为非线性。已经显示出找到针对两个集群的最优调度的问题，其中一个集群是线性的而另一个非线性是强烈的NP-困难的。在本文中，我们开发了一种精确的多项式时间算法来解决当任务限于单元任务时的上述问题。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号