The Research On Data Placement For Multiple Types Of Memory Units In Embedded Systems With Scratch-Pad Memories

Strict real time processing and energy efficiency are required byhigh performance Digital Signal Processing (DSP) applications. Scratch Pad Memory(SPM), a software controlled on chip memory with small area and low energyconsumption, has been widely adopted in many digital signal processing systems.Multiple types of memory units with varying performance and cost can be found inone system. The problem of how to optimally palce data on SPMs has become a keyproblem for achieving high performance and low energy consumption.Various data placement algorithms are proposed to effectively manage data onSPMs. However, most of them are heuristics which cannot provide optimal solution.In this paper, we design a polynomial time algorithm, the Regional Optimal DataPlacement (RODP) algorithm, using dynamic programming approach. It guaranteesoptimal data placement with minimal access cost for scalar data in a program region.For the global data placement problem, we present an ILP formulation to generateoptimal data placements for scalar data in the whole program. A polynomial timealgorithm, the Global Data Placement (GDP) algorithm, is proposed to reduce accesscost efficiently based on the RODP algorithm. For data placement problem of arraydata in loops, we design a greedy algorithm and a dynamic programming algorithm,iterational Optimal Data Placement (IODP), to solve data palcemtment problem forloops for processor architectures with multiple typs of memory units.The experimental results on two sets of benchmarks show that our technique，the GDP and IODP algorithms outperforms greedy algorithm in all the experimentalcases in terms of both memory access time and energy consumption.