Minimizing access cost for multiple types of memory units in embedded systems through data allocation and scheduling

Software-controlled memories, such as scratch-pad memory (SPM), have been widely adopted in many digital signal processors to achieve high performance with low cost. Multiple types of memory units with varying performance and cost can be found in one system. In this paper, we design a polynomial-time algorithm, the regional optimal data allocation (RODA) algorithm, using dynamic programming approach. It guarantees optimal data allocation with minimal access cost for a program region. A polynomial-time algorithm, the global data allocation (GDA) algorithm, is proposed to reduce access cost efficiently based on regional results generated by the RODA algorithm. A heuristic, the maximal similarity scheduling (MSS) algorithm, is also developed to find an execution sequence of program regions with maximal similarity of accessed data items for consecutive regions in order to reduce memory traffic. The experimental results on a set of benchmarks show that our technique that combines the GDA and the MSS algorithms outperforms greedy algorithm in all the experimental cases.