论文部分内容阅读
随着超大规模集成电路和嵌入式计算技术的迅速发展,片上系统(System-on-Chip,SoC)集成的功能不断增加,在信息处理领域的应用也越来越广泛。采用多处理器SoC(multi-processor System-on-Chip,MPSoC)是应对信息处理复杂性、提高信息处理质量与效率的主要途径之一。MPSoC通常由一个通用的嵌入式RISC处理器核和多个同构/异构协处理器核,以及配套的内部存储器和输入输出设备等构成。应用映射是MPSoC设计过程中的重要步骤。其针对给定的MPSoC应用功能与MPSoC体系结构,在满足系统约束条件的前提下,将应用程序映射到MPSoC体系结构上,并获得满足需求的MPSoC系统处理性能与效率。MPSoC应用映射决定了应用功能在MPSoC体系结构上的实现方式,对MPSoC处理性能与效率有重要影响。目前,应用映射技术已经成为MPSoC设计方法学研究领域的研究热点与难点问题。本文研究MPSoC应用映射关键技术。首先分析了已有MPSoC应用映射方法及其存在的不足。在此基础上重点研究了面向MPSoC应用映射的程序特征分析方法、基于程序多级仿射划分的MPSoC并行任务生成方法、应用处理任务到MPSoC体系结构的高效分配与任务调度方法等。完成的主要工作和取得的创新性成果如下:(1)设计实现了一种基于仿真与解析方法相结合的程序特征分析方法。根据MPSoC应用映射对程序特征信息的需求,基于模拟器、程序中间表示和多面体模型等工具构建了程序特征分析框架,分别通过动态仿真、程序中间表示解析和多面体分析等方法,得到了各种程序特征,包括:程序结构特征、控制流/数据流特征、计算/操作数特征、存储需求特征、数据依赖关系、执行时间、核心循环特征等。实验表明:该方法可以为MPSoC应用映射提供较为全面的程序特征信息,为后续的MPSoC并行任务生成、任务分配与调度等过程提供了有效的程序特征信息支持。(2)提出了一种快速、多粒度的程序存储需求量分析方法。该方法分别在基本块、循环和函数粒度上,使用静态程序分析技术(包括:控制流分析、数据活跃性与数据依赖分析等)提取与存储需求量有关的信息(包括:控制流、数据活跃性与数据依赖关系等),并基于这些信息计算应用处理程序的存储需求量。多种粒度的程序存储需求量分析满足了应用映射空间探索对多粒度存储需求量的信息需求。对于比较耗时的循环存储需求量分析,引入了数组数据域划分的技巧,大幅度减少了循环的存储需求量分析时间。实验结果表明:该方法快速得到了较为准确的多粒度程序存储需求量信息,并可辅助MPSoC应用映射找到高质量的任务分配与调度方案,提高了MPSoC处理性能。(3)提出了一种基于程序多级仿射划分的MPSoC并行任务生成方法。该方法引入程序特征(如:数据依赖关系、各数据的使用频率等)和体系结构信息(如:计算能力特征、存储层次特征、并行处理能力等),使用整数线性规划方法,在程序仿射划分空间中探索高质量的划分方案,并将仿射划分结果转换为各个并行处理任务。该方法引入程序特征信息与体系结构信息,针对关键数据与存储层次进行数据局部性优化与自动并行转换,有利于重用已有串行程序资源与提高MPSoC系统性能。实验结果表明:该方法通过程序仿射划分技术进行程序并行转换与优化,可以在MPSoC体系结构上获得明显的性能提高。(4)提出了一种基于进化蚁群算法的高效MPSoC任务分配与调度方法。该方法使用图结点多着色模型描述MPSoC任务分配与调度问题,提出并使用高效的进化蚁群算法进行MPSoC任务分配与调度。进化蚁群算法利用了遗传算法在进化控制参数上的良好性能,对蚁群算法的重要配置参数(α、β、ρ和Q)进行自适应调节和优化,从而在任务分配与调度空间中实现高效、快速的全局寻优。另外,分析得到的程序特征信息,构成了任务分配与调度的目标函数与分配依据,有利于提高任务分配与调度的质量和效率。实验结果表明:相对于采用基本蚁群与遗传算法的任务分配与调度方法,该方法可以获得高质量的任务分配与调度方案,并较大幅度的加快了任务分配与调度空间探索的收敛速度,对提高MPSoC应用映射的质量和效率具有重要作用。基于上述研究成果,本文建立了MPSoC应用映射集成环境原型的总体框架,完成了该环境的总体操作界面设计,实现了其中的程序特征分析工具、MPSoC并行任务生成工具、MPSoC任务分配与调度工具,取得了良好的实验效果。