Optimizations of energy, space and timing performance issues for embedded systems

Abstract

Since many embedded systems are real-time systems which are mainly powered 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 embedded 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 RAM (PRAM) to save energy dissipation. Compared to conventional memory technology Dynamic RAM (DRAM), PRAM has the advantage of excellent energy characteristic as well as disadvantage of short write endurance. We investigate task allocation problem in 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 embedded 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 performance. 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 design: (1) Task scheduling to minimize energy consumption of the processor; (2) Task allocation problem in hybrid memory to minimize energy dissipation, storage consumption and extend the lifetime of the memory; (3) Loop transformation to minimize storage consumption and improve timing performance of the memory. The problems and our contributions are summarized below: 1. Energy dissipation has become a major concern in embedded system design. The processor usually contributes to the largest portion of energy consumption in embedded systems without LCD displays. In this thesis, we explore task scheduling 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 mechanisms to minimize energy dissipation of the memory as the memory has become a main energy dissipator in modern embedded systems. In this thesis, 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 leakage power. However, PRAM comes with the disadvantages of much shorter write endurance and longer write latency as opposed to DRAM. The objectives 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 major 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 objectives of minimizing the storage consumption and data transfer time. We prove the NP-hardness of the problems and present polynomial time heuristic algorithms to improve the performance of stream processing system. The experimental results show significant improvement of space and timing performance of SRF when applying the proposed heuristic algorithms.

Date of Award	3 Oct 2012
Original language	English
Awarding Institution	City University of Hong Kong
Supervisor	Minming LI (Supervisor) & Chun Jason XUE (Co-supervisor)