Memory Hierarchy Code Optimization

Project Acronym
Project Title
Memory Hierarchy Code Optimization
Principal Investigator
Funding Program
NXP Semiconductors
Project Abstract
Modern real-time embedded systems are required to fulfill stringent timing constraints. But with the increasing complexity of such systems, it is necessary to consider not just execution times but other non-functional properties such as energy consumption, code size, etc. To perform optimizations for such non-functional properties, compilers can be the optimal middle ground.

Embedded systems can be equipped with sophisticated memory subsystems, featuring, among others, Flash memories, caches, tightly-coupled scratchpad memories (SPM), DRAM, DMA engines, etc. Principally, these memory subsystems play a vital role while optimizing these non-functional properties. Moreover, memory allocation for such elaborate architectures is a complex optimization problem to address. In the real-time community, the static assignment of memory objects to memories and address spaces typically is prevalent due to its inherent timing predictability. But this might lead to sub-optimal memory usage because of the lacking flexibility to adapt the memory allocation to the program's current state during execution. Therefore, this project will exploit compiler-based dynamic memory management for architectures with sophisticated memory hierarchies to design timing-, energy-, and code-size-efficient programs.

Dynamic memory allocation has been investigated in the past only for reasonably limited architectures. Moreover, the overhead imposed due to the copying of memory objects within the memory hierarchy is modeled accurately only in some cases. Lastly, until now, only dynamic memory allocation-based single-objective optimizations are considered. Therefore, currently, there is no comprehensive approach for performing compiler-based dynamic memory allocation for architectures with sophisticated memory hierarchy, under simultaneous consideration of multiple objectives, which accounts for the overheads imposed by the allocation's dynamic behavior.

To handle such multi-objective optimizations, this project aims to develop a generic framework based on Metaheuristic Algorithms and Integer Linear Programming (ILP) that performs dynamic memory allocation. As a kind of demonstration of our holistic approach, we will consider actual compiler-based optimizations like dynamic SPM allocation, cache locking, code compression, with and without DMA, etc. However, performing dynamic memory allocation is an NP-complete problem in itself. The design space within which the optimal solutions for such a problem lie, can be huge. Thus, performing multi-objective optimizations on such a huge problem, either by using the ILP- or Metaheuristics-based approach, is thus likely to have shortcomings in terms of complexity. Therefore, this project additionally aims to tackle the scalability issues by using hybrid combinations of these multi-objective optimization approaches.