IEEE Transactions on Signal Processing · 2012 · 28 citations · 40 references
EngineeringComputer EngineeringComputer ScienceComputer ArchitectureEmbedded SystemsHardware-software Co-designData Locality OptimizationEmbedded Memory BlocksMemory HierarchyMemory ManagementMemory Subsystem DesignPerformance OptimizationAccessExecution UnitsGreedy HeuristicsMemory Access SchedulingMemory Management UnitsMemory Traffic ReductionOptimal AllocationPolynomial-time Algorithms
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.
40
MiBench: A free, commercially representative embedded benchmark suite
Matthew R. Guthaus, Jeffrey Ringenberg, Daniel Ernst et al. · 2001 · 3.1K citations
A study of replacement algorithms for a virtual-storage computer
L. A. Belady · IBM Systems Journal · 1966 · 1.7K citations
Dynamic Warp Formation and Scheduling for Efficient GPU Control Flow
Wilson Wai Lun Fung, Ivan Sham, George L. Yuan et al. · 2007 · 727 citations
R. M. Banakar, Stefan Steinke, Bo-Sik Lee et al. · 2002 · 661 citations