• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文学位 >Task Scheduling on Parallel Processors: Semi-Online Settings and Job Placement Constraints
【24h】

Task Scheduling on Parallel Processors: Semi-Online Settings and Job Placement Constraints

机译：并行处理器上的任务计划：半在线设置和作业放置约束

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

摘要

Scheduling tasks/jobs on parallel processors/machines is a classical scheduling problem that is well studied in the literature due to its applicability in parallel computing systems and operations research. Even though it is a well studied problem, new scheduling models that consider the emerging aspects in the continuously evolving parallel computing systems are required to analyze and improve their performance.;In this thesis we initially study scheduling on parallel processors under three new semi-online paradigms with motivations from computational offloading systems (e.g. mobile cloud computing, mobile edge computing, hybrid cloud, etc.), where only partial information about the tasks is available. First, we study makespan minimization on a set of local processors and a set of remote processors under the semi-online setting where the task processing times on the local processors are known a priori, but are unknown on the remote processors. Second, considering that each offloaded task incurs a cost, we study makespan-plus-weighted-offloading-cost minimization when the task processing times are not known a priori, but their offloading costs are known. Third, we consider the scenario where offloaded task incurs non-negligible communication overhead and study makespan minimization under the semi-online setting where task communication overheads are known a priori, but their processing times are not known. For each of the above problems we propose efficient algorithms, analyze their performance in the worst case, by deriving competitive ratios, and study their average performance using simulation.;Finally, we identity a new job model in scheduling on parallel processors, where a job has placement constraints and multi-processor requirement. Under the job placement constraints we solve a problem of assigning identical jobs to machines. We establish novel results for this problem under generalized objective functions. We propose a new algorithm and analyze its runtime complexity. Further, using benchmark input instances we show that the proposed algorithm has orders of magnitude lower runtime than the existing algorithms.
机译：在并行处理器/机器上调度任务/作业是一个经典的调度问题，由于其在并行计算系统和运筹学中的适用性，在文献中得到了很好的研究。尽管这是一个经过充分研究的问题，但仍需要考虑到不断发展的并行计算系统中新兴方面的新调度模型来分析和提高其性能。来自计算卸载系统（例如，移动云计算，移动边缘计算，混合云等）的动机的范例，其中仅有关任务的部分信息可用。首先，我们研究半在线设置下一组本地处理器和一组远程处理器上的makepan最小化，其中先验已知本地处理器上的任务处理时间，而远程处理器上未知。其次，考虑到每个卸载任务都会产生成本，我们研究了在事先不知道任务处理时间但知道其卸载成本的情况下使panpan加加权卸载成本最小化的问题。第三，我们考虑了卸载的任务导致不可忽略的通信开销的情况，并研究了半在线设置下的跨度最小化，其中先验已知任务通信开销，但其处理时间未知。对于上述每个问题，我们提出了有效的算法，通过推导竞争比分析了最坏情况下的性能，并通过仿真研究了它们的平均性能。最后，我们在并行处理器上的调度中确定了一个新的作业模型，其中有一个作业有放置限制和多处理器要求。在作业放置约束下，我们解决了将相同作业分配给机器的问题。我们在广义目标函数下为这个问题建立了新颖的结果。我们提出一种新算法并分析其运行时复杂性。此外，使用基准输入实例，我们证明了所提出的算法比现有算法的运行时间低几个数量级。

著录项

  • 作者

    Champati, Jaya Prakash Varma.;

  • 作者单位

    University of Toronto (Canada).;

  • 授予单位 University of Toronto (Canada).;
  • 学科 Computer engineering.;Operations research.
  • 学位 Ph.D.
  • 年度 2017
  • 页码 111 p.
  • 总页数 111
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类
  • 关键词

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号