The Code Layout Strategies With Hybrid On-Chip Memories For Multi-Tasking Embedded Systems

Performance and energy consumption are usually the major non-functional concerns in design of contemporary embedded systems. Fast on-chip SRAMs including caches and scratchpad memories (SPMs) are widely used for bridging the widening speed gap between the CPU and the slow main memory. On the other hand, memory subsystems have been identified as the energy bottleneck for memory-intensive embedded applications, with a great portion of the energy consumed by the on-chip SRAMs. Therefore, on-chip memory management is of paramount importance in design and optimization of high performance and energy-efficient embedded systems.Hardware-controlled caches improve the performance of general-purpose applications by exploiting the temporal and spatial locality of the programs, which are transparent to system software and programmers. As an alternative, use of on-chip SPMs becomes increasingly popular in embedded systems. Compared with traditional caches, SPMs offer better timing predictability for real time system design since the allocation and replacement of memory objects in SPMs are explicitly controlled by the software. Furthermore, access to SPMs is slightly faster and consumes less energy due to the absence of the content-addressable memory (CAM) for tag storage and comparison in cache. Today, many off-the-shelf embedded processors employ a hybrid on-chip SRAM architecture that consists of both SPMs (a.k.a. the Tightly Coupled Memory in ARM processors) and caches, including ARM11, Cortex-R series, Analog Blackfin processors (e.g., the ADSP-BF539), and Freescale ColdFire MCF5 Processors. However, utilization of SPMs requires sophisticated allocation schemes in order to outperform the hardware controlled caches, which must be supported by the compilers and/or operating systems.In this work, we propose cache-aware static SPM allocation mechanisms for instruction memory subsystem with hybrid cache-SPM architecture in a multi-tasking environment. Based on the off-line profile information of individual tasks, we adopt and extend a fine-grained temporal cache conflict model to capture the intra-and inter-task cache behaviors. An integer linear programming (ILP) based function-level SPM allocation algorithm is presented, which considers access frequency as well as cache behaviors to obtain optimal overall memory subsystem latency or energy consumption (including both on-chip SRAMs and the off-chip main memory).Experimental results show that our allocation mechanism outperforms existing strategies on hybrid on-chip memory architecture in terms of overall performance, memory access latency, as well as energy consumption. Compared with the state-of-the-art static SPM allocation strategy in a multi-tasking environment, our SPM management scheme achieves 30.51% reduction in instruction memory subsystem access latency and up to 34.92% overall energy saving. Moreover, in order to improve the extendibility of our proposed allocation scheme for large task set, we propose polynomial-time heuristic algorithms for the static SPM allocation based on the approximate knapsack method for both function- and basic block-level allocation granularity. Compared with the ILP-based solution, our function-level allocation heuristic generates outstanding near-optimal allocation within substantially less time, which is practically useful in fast design space exploration. On the other hand, we show that basic block-level allocation heuristic leads to better resource utilization and overall performance/energy improvement at a reasonably higher analysis cost.