Data Recomputation Based Optimizations in Embedded Systems

Recent advancements in embedded systems have brought new challenges for industry and academia. In order to meet the demand for the computational power required by the today's applications with large data set sizes, the trend in computing systems is to design fast architectures that accommodate large on-chip memories and consume less power. Unlike high-end computing systems where the performance is the only dominant metric, embedded systems have several (sometimes equally important) metrics of interest. Therefore, in addition to targeting one optimization parameter for a given system, an embedded system designer may need to perform several tradeoffs among these metrics to generate an acceptable output. Among these metrics are performance, power, energy, memory space consumption, and reliability. In this dissertation, we propose data recomputation in order to optimize the design metrics, namely performance, power/energy utilization, and memory space consumption in single and multi-core embedded systems running data-intensive applications. The proposed approach is based on recomputing the value of a data element by using other available data elements, if it is beneficial in terms of the target optimization metric, instead of explicitly accessing the requested data. As an example, the proposed data recomputation based approach in Chapter 5 aims at improving the performance of chip multi-processors by reducing the number of off-chip memory accesses, which is a major contributor to the total execution time. Specifically, the approach tries to compute the value of an off-chip data using the available on-chip data elements, if it is beneficial for performance, instead of performing an off-chip memory access. As today's embedded applications typically process large data-set sizes, we specifically target data-intensive applications in this dissertation. We study not only single-processor based embedded systems but also multi-core architectures. In addition to traditional hardware-controlled memory structures, we also propose novel memory utilization techniques for software-managed memory architectures, such as Scratch-Pad Memory, which are widely used in embedded systems. The proposed approach also performs various tradeoffs such as performance/memory space consumption and energy/performance for a given embedded architecture. The effectiveness of the proposed approach is tested and the experimental evaluation is presented in the context of various architectural setups. The experimental results collected using data-intensive benchmarks clearly show the effectiveness of the data recomputation.