论文部分内容阅读
高性能应用,如高清数字信号处理(DSP)等对嵌入式系统有着严格的实时处理和低能耗等要求。便笺式存储器(Scratch Pad Memory, SPM)是一种软件控制的片上存储器。由于具有纯软件控制、占用芯片面积少、低能耗等优点,便笺式存储器作为一种片上存储器已经越来越广泛地应用在众多数字信号处理系统中。在这些嵌入式系统中,通常会使用多种具有不同性能和开销的存储介质组成多层存储子系统,从而提高整个系统的存储效率。因此,在基于便笺式存储器多层异质存储单元的嵌入式系统中,如何有效的进行数据分配是减少系统存储开销、提高程序性能的重要研究课题之一。近年来,学术界提出了许多不同的基于便笺式存储器的数据分配策略。然而,现有的研究大多是一些不能保证最优解的启发性算法。而本文致力于设计出能保证在多项式时间复杂度内找到解决多层便笺式存储嵌入式系统上的的数据分配问题的最优算法。对于程序区段内的标量数据,本文设计出一种基于动态规划的程序区段最优数据分配算法(RODP),该算法可以在多项式时间复杂度内得到最优解;对于全局标量数据的分配,本文用整数线性规划进行建模,并基于RODP算法,提出了全局数据分配算法(GDP),GDP算法能在多项式时间复杂度内快速地解决整个程序内标量数据的分配问题。最后,本文专门针对于程序循环体中的数组变量,设计出循环迭代最优数据分配算法(IODP),该算法可以保证循环中的数组数据在多层便笺式存储器上得到迭代级最优数据分配。仿真实验分别在两组基准程序上进行。实验结果表明对于所有的测试程序,本文提出的全局数据分配算法及循环迭代最优数据分配算法无论在访存延迟,还是系统能耗方面都优于已有的基于贪婪策略的数据分配算法。