分布式同构多任务调度问题研究

发布时间：2023-04-18 20:21

　　分布式任务调度问题在大数据时代具有重要的地位,同构处理器环境下的任务调度问题是此类复杂问题的基础。它所研究的是如何将多个具有先后顺序约束关系的任务分配到可用处理器上进行执行,达到最小化调度长度(Makespan)的目的。此问题是NP难度的,除非P=NP,否则在多项式时间内不能得到精确解。该问题得到了学者们的广泛研究,并致力于找到高效、简单且占用资源少的方法来解决该问题。国内外代表性的求解思路包括基于优先级列表、基于分簇、基于任务复制三种方向。将分簇思想和任务复制技术相结合被普遍认为是最佳的求解途径。分簇思想的核心是将具有约束关系的任务尽可能的放在同一台处理器上执行,以此来减少不同处理器之间的通信开销。任务复制技术的核心思想是将同一个任务复制到多台处理器上执行,以牺牲处理器计算资源的方式来换取更早的完工时间,简而言之是一种以空间换取时间的做法。本文结合分簇思想和任务复制技术,提出了基于转化树和任务复制的调度算法(Transformation Tree and Task Duplication(TTTD))。算法主要包含预处理、转化树、序列合并等三个重要步骤。针对实际工作中可能存在可用处理...

【文章页数】：66 页

【学位级别】：硕士

【文章目录】：
摘要
Abstract
1 绪论
    1.1 研究背景及意义
    1.2 国内外研究现状
    1.3 研究内容
    1.4 组织结构
2 问题模型和定义
    2.1 问题描述
    2.2 问题形式化定义
    2.3 本章小结
3 核心算法设计
    3.1 基于转化树和任务复制的调度算法
    3.2 考虑处理器数量约束的优化算法
    3.3 本章小结
4 实验与分析
    4.1 测试方法
    4.2 测试算例
    4.3 实验结果
    4.4 本章小结
5 总结与展望
    5.1 总结
    5.2 展望
致谢
参考文献



本文编号：3792967