论文部分内容阅读
随着FPGA容量的与日俱增以及自动设计技术的迅猛发展,基于可重构逻辑器件的可重构计算技术正迅速地成熟起来。可重构计算结合了传统硬件和软件实现方案的优点,既具有硬件并行计算的高性能,又具有软件的灵活性,是实现高性能计算的一个创新性的途径,已成为业界的研究热点。它在高性能计算领域具有非常好的应用前景,但也带来了许多新的挑战,包括可重构系统上应用的软/硬功能划分、软/硬任务调度、硬件任务布局和可重构资源管理等。针对可重构系统面临的挑战,本文开展的主要工作包括如下几个方面:1、提出了一种面向动态可重构系统的基于配置预取和任务重用的混合任务调度算法CTHTSA。传统任务调度算法(包括单CPU上的任务调度和多CPU上的并行任务调度)为可重构系统上的软硬任务调度研究提供了一定的参考,但是不能满足可重构计算系统的需要。而目前的可重构系统的任务调度研究大部分没有考虑CPU和FPGA的协同执行或针对硬件任务的配置时间因素,只单独运用了某一种优化手段,优化效果有限。针对这种情况,CTHTSA算法充分利用目前可重构系统中丰富的CPU核和FPGA资源,实现软件任务和硬件任务的并行执行,并通过配置预取和任务重用来隐藏硬件任务的配置开销,以进一步减少程序执行时间。实验结果表明该算法能有效提高系统的执行性能。2、提出了一种基于改进遗传算法和配置预取调度的软硬功能划分算法IGCPSPA。该算法将程序的划分和调度结合起来,首先对问题进行编码,完成问题域向解空间的映射,然后在进化过程中采用赌轮和精英保留的选择策略、自适应交叉和变异策略对个体进行优化,进化到中后期时采用爬山算法对个体进行邻域优化搜索,最终获得了一个较优的软硬功能划分方案。采用基于配置预取的调度算法对划分方案进行评价,调度算法充分利用CPU核与FPGA并行工作,并在调度过程中采用配置预取策略以隐藏系统的重构开销,从而提高了系统整体的执行性能。实验结果表明了相对于现有的软硬件自动划分方法,本文提出的划分方法的有效性。3、提出了一种基于任务紧迫度和布局紧密度的在线任务调度算法TUPC。与现有调度算法的FCFS调度方式不同,该算法综合考虑相邻任务的相关特征,选取任务紧迫度高的任务优先进行调度,同时在调度过程中选择布局紧密度高的区域对硬件任务进行布局。实验结果表明,该算法能够有效提高任务调度和布局的质量,调度成功率优于目前的主流调度算法。4、构建了异质可重构器件模型和任务模型,并提出了芯片负载率(Chip Load, CL)和特殊负载率(Special Load, SL)的概念,通过HM-FF和HT-FF算法测试证明了CL和SL对调度性能的影响。在分析HT-FF算法性能瓶颈的基础上,提出了基于区域划分布局的调度算法SARP,并进一步提出了一种改进的区域划分布局调度算法——基于区域划分布局共享的调度算法SARSP。实验结果表明SARSP算法能够有效地降低异质可重构结构下任务调度的拒绝率。