Effective algorithms for partitioned memory hierarchies in embedded systems

Many architectures today, especially embedded systems, have multiple memory partitions, each with potentially different performance and energy characteristics. To meet the strict time-to-market requirements of systems containing these chips, compilers require retargetable algorithms for effectively assigning values to the memory partitions. Furthermore, embedded system designers need a methodology for quickly evaluating the performance of a candidate memory hierarchy on an application without relying on time-consuming simulation.; This dissertation presents algorithms and techniques to effectively meet these needs. First, EMBARC is presented. EMBARC is the first algorithm to realize a comprehensive, retargetable algorithm for effective partition assignment of variables in an arbitrary memory hierarchy. It supports a wide variety of memory models including on-chip SRAMs, multiple layers of caches, and even uncached DRAM partitions. Even though it is designed to handle a wide range of memory hierarchies, EMBARC is capable of generating partition assignments of similar quality to algorithms designed for specific memory hierarchies. A large range of benchmarks and memory models is used to demonstrate the effectiveness of the EMBARC algorithm. Experiments show optimal or near-optimal results for every category of memory hierarchy tested.; This dissertation also presents MPRES. MPRES is an algorithm to estimate the effectiveness of the memory hierarchy for a given application without requiring time-consuming simulations. To show that MPRES generates accurate performance estimates, MPRES performance estimates are compared to detailed simulation results. Experiments show performance estimations trend the same as values obtained via simulation. Furthermore, MPRES is significantly faster than simulation, requiring two orders of magnitude less time.; Together, MPRES, EMBARC, and their supporting framework provide a comprehensive solution for embedded software designers who must choose a suitable partitioned memory hierarchy and application programers who rely on the compiler to automatically assign variables to memory partitions.