Exact and Heuristic Algorithms for Low-Energy Code Compression in Performance and Memory Constrained Embedded Systems

Code compression has proved to be a viable solution to the problem of minimizing energy in core-based embedded systems. Normally, energy reduction is achieved by limiting the dynamic size of the program being executed. However, an increase of static code size is often observed as a result of compression, and this effect may not be acceptable in memory-constrained systems. Furthermore, nonnegligible hardware overhead may be needed to implement compression schemes that guarantee high dynamic size reduction, thus introducing potential performance penalties (on-the-fly instruction decompression during program execution may be slow). In this paper, we present exact and heuristic compression algorithms that reduce energy consumption under tight code size and decompressor complexity constraints. The proposed solutions are basic block oriented; they guarantee that static code size never increases with respect to the original, uncompressed code, and allow us to finely trade energy reduction for decompressor complexity. The achieved energy savings, evaluated on a number of benchmarks, range from 48% to 54%, depending on the technology used for code memory realization (on-chip ROM vs. off-chip flash)