便笺存储嵌入式系统中多层存储上的数据分配算法研究

发布时间：2018-03-19 16:53

本文选题：数据分配　切入点：便笺式存储器　出处：《湖南大学》2013年硕士论文　论文类型：学位论文

【摘要】：高性能应用，如高清数字信号处理(DSP)等对嵌入式系统有着严格的实时处理和低能耗等要求。便笺式存储器(Scratch Pad Memory, SPM)是一种软件控制的片上存储器。由于具有纯软件控制、占用芯片面积少、低能耗等优点，便笺式存储器作为一种片上存储器已经越来越广泛地应用在众多数字信号处理系统中。在这些嵌入式系统中，通常会使用多种具有不同性能和开销的存储介质组成多层存储子系统，从而提高整个系统的存储效率。因此，在基于便笺式存储器多层异质存储单元的嵌入式系统中，如何有效的进行数据分配是减少系统存储开销、提高程序性能的重要研究课题之一。近年来，学术界提出了许多不同的基于便笺式存储器的数据分配策略。然而，现有的研究大多是一些不能保证最优解的启发性算法。而本文致力于设计出能保证在多项式时间复杂度内找到解决多层便笺式存储嵌入式系统上的的数据分配问题的最优算法。对于程序区段内的标量数据，本文设计出一种基于动态规划的程序区段最优数据分配算法(RODP)，该算法可以在多项式时间复杂度内得到最优解；对于全局标量数据的分配，，本文用整数线性规划进行建模，并基于RODP算法，提出了全局数据分配算法(GDP)，GDP算法能在多项式时间复杂度内快速地解决整个程序内标量数据的分配问题。最后，本文专门针对于程序循环体中的数组变量，设计出循环迭代最优数据分配算法(IODP)，该算法可以保证循环中的数组数据在多层便笺式存储器上得到迭代级最优数据分配。仿真实验分别在两组基准程序上进行。实验结果表明对于所有的测试程序，本文提出的全局数据分配算法及循环迭代最优数据分配算法无论在访存延迟，还是系统能耗方面都优于已有的基于贪婪策略的数据分配算法。
[Abstract]:High-performance applications, such as high-definition digital signal processing (DSP), have strict real-time processing and low energy consumption requirements for embedded systems. Scratch Pad memory (SPMs) is a kind of software controlled on-chip memory. As a kind of on-chip memory, notepad memory has been widely used in many digital signal processing systems. In order to improve the storage efficiency of the whole system, the storage efficiency of the whole system can be improved by using a variety of storage media with different performance and overhead. How to allocate data effectively is one of the important research topics to reduce system storage overhead and improve program performance. In recent years, many different data allocation strategies based on notepad memory have been proposed by the academic community. However, Most of the existing researches are heuristic algorithms which can not guarantee the optimal solution. However, this paper is devoted to designing a solution to the problem of data allocation on multi-layer note storage embedded system in polynomial time complexity. For scalar data in a program section, In this paper, a program segment optimal data allocation algorithm based on dynamic programming is designed, which can obtain the optimal solution in polynomial time complexity, and the integer linear programming is used to model the global scalar data allocation. Based on the RODP algorithm, a global data allocation algorithm is proposed, which can quickly solve the problem of scalar data allocation in the polynomial time complexity. Finally, this paper focuses on the array variables in the program loop. A cyclic iterative optimal data allocation algorithm is designed, which can ensure that the array data in the loop can be allocated at the iterative level on a multi-layer pad memory. The simulation results show that for all the test programs, the global data allocation algorithm and the cyclic iterative optimal data allocation algorithm are proposed in this paper, regardless of the memory access delay. The system energy consumption is better than the existing greedy strategy based data allocation algorithm.
【学位授予单位】：湖南大学
【学位级别】：硕士
【学位授予年份】：2013
【分类号】：TP333

【相似文献】