片上多处理器通信结构中的多任务调度研究

发布时间：2020-03-18 17:25

【摘要】：为解决单处理器系统的功耗和散热等问题,采用以多处理器为代表的先进体系结构逐渐成为未来处理器性能提升的主要技术途径,并受到了学术界和工业界的广泛关注。超大规模集成电路和制造工艺技术的不断发展,使得单芯片上集成的处理器数目越来越多。当芯片上集成的处理器数量达到数十个或数百个,甚至上千时,芯片内部采用什么通信结构就变得越来越重要。处理器之间的信息交换能否正确、可靠地完成完全取决于片上处理器之间的通信互连技术,尤其是在超亚微米技术条件下,处理器的运算速度已经不再是制约整个系统快速发展的瓶颈,相反,处理器之间的互连方式却成为了多处理器系统向更大规模和更复杂化发展所亟待解决的问题,因此,片上多处理器系统通信结构的设计往往成为影响整个系统性能的瓶颈。而且,芯片上集成的处理器越多,通信结构越庞大,占用芯片的面积越多,通信功耗随着片上处理器的增加成超线性的增长,所以,如何设计一个快速、紧凑和低功耗的通信体系结构,已经成为当前研究的热点和难点。多任务调度问题一直是并行系统的长久研究领域,而且此类问题大多数情况下是NP完全问题,因此对该类问题的研究大多数侧重于利用启发式算法获取近似最优解。即使是其近似算法的求解也非常困难,求解过程中需要考虑的因素非常多。这类问题是调度理论中的经典问题,也是并行计算中的核心问题,得到了广泛和深入的研究。随着半导体技术的发展促使更多的处理器集成到单个芯片上,如何充分利用片上多处理器系统提供的强大计算资源,成为了并行系统中研究的热点和难点问题。虽然已经存在大量的多任务调度的启发式算法,但是传统的多任务调度方案没有考虑片上系统独有的特点和性能要求,因此迫切需要设计适应片上多处理器系统的多任务调度算法。各国学者针对片上多处理器系统的任务调度技术已经开展了一些相关研究,但仍然存在许多问题有待解决。如有些算法没有考虑系统可靠性等因素会导致运行过程中计算资源的可变性问题,有些算法没有考虑到通信功耗的影响等,因此,多任务调度问题是当前片上多处理器系统研究的关键问题之一。本文主要围绕片上多处理器系统的通信体系结构和多任务调度问题,开展了以下研究工作： 1.针对环状通信体系结构的任务迁移敏感和可容错的多任务调度算法传统的静态调度算法主要通过冗余和备份两种方式实现容错。为适应片上多处理器系统的特点和解决传统静态容错算法的开销,提出了片上环状通信体系结构,并在此结构基础上,设计了任务迁移敏感和可容错的静态多任务调度算法。在环状的通信体系结构中,当有处理器失效时,可通过把失效处理器上的任务迁移到其邻居处理器去完成。但过量的任务迁移不仅提高了通信功耗,还会增加访存操作等,而这些因素反过来又会影响任务的调度长度,甚至引起任务时序错误。为减少处理器之间任务迁移造成的通信开销和对系统性能的影响,提出了基于two-line的任务迁移方法。为减少因负载过重可能会导致的处理器过热失效问题,以及进一步减少处理器失效时任务迁移的数目,在基于two-line任务迁移方法基础上,设计了一种同时考虑任务迁移数目和负载平衡的多任务调度方法,即任务迁移敏感和可容错的多任务调度算法MNTM。MNTM算法通过实现负载平衡不仅能减少处理器失效时任务迁移的数目,实现高度有规则的任务迁移,而且可充分利用片上的计算资源。仿真实验结果表明了所提出的算法能够有效减少处理器失效时任务迁移的数目,而且以合理的调度长度代价,取得了处理器失效时高度有规则的和可预测的任务迁移和快速重构。 2.针对基于分段总线通信体系结构的优化通信功耗的多任务调度算法随着半导体技术向着超亚微米不断扩展,通信功耗占整个系统功耗的比例越来越大,如何设计低功耗高性能的通信体系结构是当今研究的热点和难点。为解决当片上处理器数目增多时,共享总线结构性能急剧下降而通信功耗却增长的问题,提出了低功耗高性能的基于分段总线的线性通信体系结构。该结构利用交换开关,隔离不在数据传输路径上的分段总线,从而减少通信总线的长度,进而降低通信功耗。同时,多个分段总线可实现无重叠路径的多个数据传输,提高了总线带宽,进而提高系统的性能。在此通信结构基础上,设计了优化通信功耗的多任务调度算法。算法通过建立任务的通信结构图,分析虚拟处理器之间的通信频率,利用遗传算法搜索虚拟处理器到物理处理器的最优映射,从而在基于分段总线的通信结构基础上,进一步减少了通信功耗。模拟实验结果表明所提出的遗传算法在不影响任务调度长度的前提下,有效的减少了通信功耗。 3.针对类似于片上网络的类二维网格通信体系结构的综合贪心策略和遗传思想的混合调度算法随着片上处理器数目的增多,通信体系结构对系统的影响将越来越大,特别是对芯片面积、性能和功耗等方面的影响。对于片上拥有众多处理器系统的互连方式,借鉴并行领域计算机网络的研究成果,片上网络NoC的理念应运而生。由于片上网络技术还很不成熟,有很多需要进一步解决的问题,因此目前主要处在理论研究和实验阶段。为解决拥有众多处理器的片上系统对通信结构低功耗和高性能的要求,提出了类似于片上网络的基于分段总线的类二维网格通信体系结构。通过对称地设置交换开关,该通信结构可综合利用片上网络有规则性的连接方式和总线资源丰富等优点。在系统运行过程中通过动态设置交换开关状态,可实现广播或是路径不重叠的数据同时传播。针对此结构,提出了两种不同的基于列表调度的扩展算法,即基于遗传思想的混合贪心算法和基于贪心策略的混合遗传算法。在不影响基础算法调度长度的前提下,算法通过调整任务簇到处理器的映射关系,进一步减少了因处理器之间信息交换而引起的通信功耗。实验结果表明两种混合算法都能有效减少通信功耗,且通信功耗的降低随着片上处理器数目的增多而提高。
【图文】：

任务调度,算法,测试任务,阈值

w_?Ce)和w,,_(r)分别表示测试任务图DAG的平均11信7B肖和平均计算7T阈位STDvalue的值可通过选择不同的￠7值进行微调。设桻cr=0. 5和Nutifrhresho时得到的比较结果如图3-15、图3-16和图3-17所示。阈值取其他同值时对性能响将在这一节后面详细讨论。
【学位授予单位】：武汉大学
【学位级别】：博士
【学位授予年份】：2011
【分类号】：TP332

【相似文献】