A Tabu Search Heuristic for Scratch-Pad Memory Management

Abstract—Reducing energy consumption of embedded systems re-quires careful memory management. It has been shown that Scratch-Pad Memories (SPMs) are low size, low cost, efficient (i.e. energy saving) data structures directly managed at the software level. In this paper, we focus on heuristic methods for SPMs management. A method is efficient if the number of accesses to SPM is as large as possible and if all available space (i.e. bits) is used. We propose a Tabu Search (TS) approach for memory management which is, to the best of our knowledge, a new original alternative to the best known existing heuristic (BEH). In fact, experimentations performed on our benchmarks show that our Tabu Search method is as efficient as BEH (in terms of energy consumption) but BEH requires a sorting which can be computationally expensive for a large amount of data. TS is easy to implement and since no sorting is necessary, unlike BEH, we save the corresponding sorting time. In addition to that, in a dynamic perspective where the maximum capacity of the SPM is not known in advance, our TS heuristic will perform better than BEH. Keywords—Energy consumption, memory allocation management, optimization, Tabu Search heuristic. I