Optimizations Of Energy, Space And Timing Performance Issues For Embedded Systems

Since many embedded systems are real-time systems which are mainly pow-ered by battery and the memory size is small, designing algorithms to save energy, space and improve timing performance are critical issues for embedded systems. Optimizations of these issues can remarkably improve the performance of embed-ded systems. This thesis investigates some new technologies to optimize these issues. Particularly, we propose two solutions to minimize energy consumption. The first solution is via task scheduling, which is well studied in the literature. We theoretically study a special kind of task scheduling problem to optimize the energy usage in a single-processor system. The other method we apply is using emerging memory technology Phase Change Random Access Memory (PRAM) to save energy dissipation. Compared to conventional memory technology Dy-namic Random Access Memory (DRAM), PRAM has the advantage of excellent energy characteristic as well as disadvantage of short write endurance. We inves-tigate task allocation problem on the new hybrid memory composed of DRAM and PRAM. The objectives are to optimize the energy dissipation, minimize write operations on PRAM to extend the lifetime and minimize the used PRAM size. To optimize space and timing performance, we study a a specific type of em-bedded system-stream processing system which is gaining popularity in many multi-media and scientific applications recently. Stream Register File (SRF) is a critical resource in the system. The storage consumption and data transfer time of SRF are two important factors which could greatly impact the system perfor-mance. Loop transformation techniques are applied to minimize the cost which consists of the two factors.In all, this work focuses on the following hot topics in embedded system de-sign:(1) Minimize energy consumption of the processor via task scheduling;(2) Minimizing energy dissipation, storage consumption and extending the lifetime of the memory via task allocation;(3) Minimizing storage consumption and improv-ing timing performance of the memory via loop transformation. The problems and our contributions are summarized below:1. Energy dissipation has become a major concern in embedded system de-sign. The processor usually contributes to the largest portion of energy consumption in embedded systems. In this thesis, we explore task schedul-ing technique to optimize energy consumption of the processor. Each task in the problem instance has n (n≥1) disjoint active time intervals where it can be executed and a workload characterized by the required number of CPU cycles. Tasks are preemptive. The processor is capable of running at a speed of any value and changing the speed instantaneously with no delay. Previously, people studied multiple-interval task scheduling problem where each task must be assigned enough CPU cycles in one of its active intervals. We study a different practical version where the partial work done by the end of an interval remains valid and each task is considered finished if total CPU cycles assigned to it in all its active intervals reach the requirement. The goal is to find a feasible schedule that minimizes energy consumption. We present polynomial time algorithm and prove its optimality.2. To optimize energy consumption of embedded systems, we explore mech-anisms to minimize energy dissipation of the memory as the memory has become a main energy dissipator in modern embedded systems. In this the-sis, we consider task allocation problem on hybrid main memory composed of DRAM and PRAM. Compared to the conventional memory technology DRAM, PRAM has excellent energy performance due to the ultra low leak-age power. However, PRAM comes with the disadvantages of much shorter write endurance and longer write latency as opposed to DRAM. The ob-jectives of task allocation problem include minimizing energy consumption, extending the lifetime and minimizing the storage consumption of PRAM. We design Integer Linear Programming (ILP) formulations that can solve different objectives optimally. We then propose three effective polynomial time heuristic algorithms. The experimental results show that compared to the optimal ILP solutions, the proposed heuristic algorithms generate near-optimal results but can be finished in negligible time.3. Besides energy consumption, space and timing performance are also ma-jor concerns in embedded system design as many embedded systems are real-time and have small chip size. In this thesis, we study a specific type of embedded system-stream processing system which is gaining popularity and getting deployed in many multi-media and scientific applications. Stream Register File (SRF) is a critical resource in stream processing system since all data should be stored in it for execution. It is a non-bypassing software-managed on-chip memory with a limited size and a small bandwidth to off-chip memory. When loading a program from the off-chip memory into SRF for execution, the storage consumption and the data transfer time are two key factors which affect the system performance. This work applies loop transformation to programs for SRF optimization. We consider two objec-tives of minimizing the storage consumption and data transfer time. We prove the NP-hardness of the problems and present polynomial time heuris-tic algorithms to improve the performance of stream processing system. The experimental results show significant improvement of space and timing per-formance of SRF when applying the proposed heuristic algorithms.