多趟调度算法及其在图像处理中的应用研究

作     者：宋嘉明 

作者单位：西安电子科技大学 

学位级别：硕士

导师姓名：王晓丽

授予年度：2021年

学科分类：08[工学] 080203[工学-机械设计及理论] 0802[工学-机械工程] 

主      题：可分任务调度 多趟调度 图像处理 进化算法 

摘      要：分布式系统中存放图像时,会在多台处理机中放置备份,以防数据丢失。不过当图像需要传输或计算时,传统的分布式调度大多选择单趟调度。单趟调度的优点是模型简单、易于求解,但是各台处理机在开始任务前存在不短的空闲等待时间,因此不能充分利用分布式系统,而多趟调度恰好可以解决这个问题。鉴于此,本文利用多趟调度来优化分布式系统中的图像处理问题,建立了以最短任务完成时间为优化目标的多趟调度模型,并分别对同构与异构分布式系统的相关问题展开研究。主要研究成果包括:1.针对同构分布式系统,以任务的最短完成时间为目标,区别于已有的多趟调度模型中先传输数据再进行分布式计算的模式,采用备份处理机直接并行处理数据再统一回收结果的方式,建立了一个新的多趟调度模型。该模型更符合当今分布式系统执行大数据任务的特点。模型涉及两组变量:任务分配方案与调度趟数。为求解该模型,首先,分析了各处理机在各趟调度之间的约束关系,得到了最优任务分配方案的解析解。其次,通过严格的定理证明和公式推导,得到了最优调度趟数的解析解。最后,通过仿真实验再次验证了解的正确性。2.针对异构分布式系统,以任务的最短完成时间为目标,建立了可分任务的多趟调度模型。该模型涉及三组变量:处理机的调度顺序、任务分配方案和调度趟数。首先,在给定处理机调度顺序和调度趟数的情况下,通过公式推导得到了最优任务分配方案的解析解;然后,在给定处理机调度顺序的情况下,推导得到了最优调度趟数的解析解。接着,设计了一种有效的进化算法获取最优处理机调度顺序。最后,通过仿真实验表明所提算法能够求得最优的处理机调度顺序,且能获得最短的任务完成时间。此外,通过分析实验结果发现,处理机的通信速度降序排列的顺序可以作为处理机调度顺序的近似最优解。3.为了验证所提模型和算法的有效性,本文针对NASA发布的星云图像压缩问题进行了多趟调度实验。首先,根据所提模型和算法,计算得到最优的处理机调度顺序、调度趟数以及最优任务分配方案。然后,在分布式系统上执行多趟调度,同时监视并记录各处理机的执行过程。最后,实验结果验证了所提模型和算法的有效性。