HGCOTS：一种全局优化的静态任务调度算法

"一种全局较优的静态任务调度算法，针对现有任务调度算法的局限性，提出了HGCOTS算法，该算法结合分层和分支策略确定任务优先级，考虑通信开销和冗余任务影响，利用区间插入和任务复制技术减少通信成本，删除冗余任务，提高调度效率。通过模拟实验，HGCOTS算法在调度长度上优于其他算法。" 本文探讨的是在多核计算环境中，如何改进任务调度算法以实现全局最优。现有的任务调度算法往往存在优先级选取单一的问题，导致调度结果可能只是局部最优而非全局最优。为解决这一问题，研究者提出了HGCOTS（Hierarchical and Global Comparative Optimal Task Scheduling）算法。该算法的设计思路是首先将任务分层，然后基于分层结果进行分支决策，以确定任务的执行优先级。这样做的目的是从全局角度优化任务的调度顺序，避免因优先级选取不当造成的局部优化。 在HGCOTS算法中，特别考虑了两个关键因素：任务间的通信开销和冗余任务的存在。通信开销是多核系统中影响性能的重要因素，特别是对于异构CMP（Computing Modules）环境，大通信开销可能导致性能瓶颈。为此，HGCOTS引入了区间插入和任务复制技术，旨在最小化任务间的通信需求，从而提高整体调度效率。同时，算法还识别并删除冗余任务，进一步优化了资源利用率和调度效率。 为了验证HGCOTS算法的有效性，研究人员使用随机生成的任务图进行了模拟实验，并将其结果与其它常见调度算法进行了对比。实验结果显示，HGCOTS算法的调度长度显著小于其他算法，这表明它在寻找全局最优调度方案方面表现更优。 这项研究由多项科研基金支持，包括国家自然科学基金和黑龙江省的自然科学基金等。研究团队成员包括李静梅教授，孙冬微硕士，以及吴艳霞副教授，他们在计算机体系结构和多核处理器性能优化领域有着深入的研究。 HGCOTS算法提供了一种新的方法来改善静态任务调度，它通过全局优化和针对性的技术手段，有效地减少了通信开销，提升了调度效率，对于多核计算环境下的任务调度具有重要的理论和实践意义。