The Research Of Data Allocation Algorithm With Hybrid On-Chip High-Speed Memories

With the advantage of the Internet of Things and embedded smart devices, the embedded system is developing rapidly in recent years. More and more embedded technology widely applied to wireless communication, smart phone, medical technology and intelligent building which deeply affect people’s daily life. The new embedded equipment requires higher performance, longer working hours and higher stability, thus the computational efficiency and energy consumption have been the main consideration of embedded system design.On-chip SRAMs including scratchpad memories (SPM) and caches are widely used in embedded systems to narrow the speed gap between CPU and memory. The memory subsystem is the performance and energy bottleneck in data intensive applications, which makes it a key consideration in high-performance and energy-efficient system optimization. However, many existing SPM data allocation algorithms are designed for architectures with pure SPM as on-chip SRAM. As a result, for off-the-shelf embedded processors with hybrid on-chip scratchpad and caches, these algorithms may not lead to an optimal performance and energy saving due to the lack of consideration for cache behaviors. Centered on this theme, my work in this thesis focused on a data allocation framework basic on cache behaviors analysis with hybrid on-chip high-speed SPMs and caches.The main works and contributions are presented in the following aspects:(1) We study the SPM data allocation problem on hybrid on-chip SRAM architecture for performance and energy optimization. We propose an optimal ILP-based solution that considers data access frequency as well as the temporal cache conflict behaviors, including both scalar data and arrays. Experiments show that our scheme leads to better utilization of the hybrid on-chip SRAMs compared with the pure cache or SPM architecture.(2) This thesis puts forward a cache behaviors analysis model basic on data cache trace. We adopt and extend the Temporal Conflict Set (TCS) for accurate cache conflict modeling. Compared with cache conflict graph based analysis, TCS provides sequence of memory references leading to each cache miss. This information is utilized in our ILP formulation to capture the impact on the cache behaviors if a memory block is allocated into SPM.(3) We integrate our optimization scheme with a general compilation framework. The data allocation obtained from ILP-based optimizer is converted into a link script file, which is then fed back to the compiler to generate the optimal executables. We have extended the SimpleScalar tool set with the proposed workflow.(4) Our proposed algorithm allows a fine-grained data object allocation at memory block boundaries for maximal SPM utilization. As a result, each data array can be partitioned into arbitrary number of regions, where each region can be accessed either from the SPM or the main memory. We have explicitly modeled and measured the timing and energy overhead due to the array partitioning in our ILP formulation and experiments.