Minimizing the booting time of an embedded system has become a major technical issue for the success of many consumer electronics. In this paper, the booting time minimization problem for real-time embedded systems with the joint consideration of DRAM and non-volatile memory is formally formulated. We show this is an NP-hard problem, and propose an optimal but pseudo-polynomial-time algorithm with dynamic programming techniques. In considering polynomial-time solutions, a 0.25-approximation greedy algorithm is provided, and a polynomial-time approximation scheme is developed to trade the optimality of the derived solution for the time complexity according to a user-specified error bound. The proposed algorithms can manage real-time embedded systems consisting of not only real-time tasks, but also initialization tasks that are executed only once during system booting. The proposed algorithms were then evaluated with 65 real benchmarks from the MRTC and DSPstone benchmark suites, and the results showed that all of the proposed algorithms can reduce booting time for each benchmark set by more than 29 percent. Moreover, extensive simulations were conducted to show the capability of the proposed approaches when used with various hardware resources and software workloads.

With the growing popularity of 3G-powered devices and their serious energy consumption problem, there are growing demands on energy-efficient data transmission strategies for various embedded systems. Different from the past work in energy-efficient real-time task scheduling, we explore strategies to maximize the amount of data transmitted by a 3G module under a given battery capacity. In particular, we present algorithms under different workload configurations with and without timing constraint considerations. Experiments were then conducted to verify the validity of the strategies and develop insights in energy-efficient data transmission.

With the strong demands in the fast start-up of many mobile devices, hibernation has shown its clear superiority in such system designs. Different from the past work, a methodology is proposed to downsize the hibernation image without sacrificing the user experience in the resuming procedure of hibernation. Two approximation algorithms with bounds are proposed to remove selected pages from the hibernation image and shift them to page-in activities. The proposed methodology was evaluated over a series of experiments, for which we had more than 10% of improvement on the resuming time for many system configurations.

Leakage power consumption contributes significantly to the overall power dissipation for systems that are manufactured in advanced deep sub-micron technology. Different from many previous results, this paper explores leakage-aware energy-efficient scheduling if leakage power consumption depends on temperature. We propose a pattern-based approach which divides a given time horizon into several time segments with the same length, where the processor is in the active (dormant, respectively) mode for a fixed amount of time at the beginning (end, respectively) of each time segment. Computation is advanced in the active mode, whereas the dormant mode helps reduce the temperature via cooling as well as the leakage power consumption. Since the pattern-based approach leads to a steady state with an equilibrium temperature, we develop a procedure to find the optimal pattern whose energy consumption in steady state is the minimum. Compared to existing work, our approach is more effective, has less run-time scheduling overhead, and requires only a simple scheduler to control the system mode periodically. The paper contains extensive simulation results which validate the new models and methods.

Virtualization provides an excellent solution to resolve the portability, maintainability, development, and utilization problems in many system designs. In this paper, we are interested in energy-efficient designs for platform virtualization. In particular, we explore the computing resource mapping and the energy consumption relationship between virtual cores and physical cores when timing constraints in task executions are considered. Real-time and non-real-time task workloads are both considered in the study, where the computing needs of each virtual core are modeled with a computing server. A prototype with dynamic-voltage-scaling support is implemented based on a μ-kernel architecture. The capability and overheads of the proposed design was evaluated, for which we have encouraging results.

In the past decade, energy-efficient real-time task scheduling has been widely explored in the form of various optimization problems. This paper considers energy-efficient real-time task synchronization protocols and the overhead of frequency switching in real systems design. We propose the concept of frequency locking to better manage the cost in frequency switching. To minimize the energy consumption and meet the timing constraints, algorithms are presented to assign tasks base frequencies under existing synchronization protocols which are then extended with the frequency locking concept. Finally, a series of extensive simulations is performed and a real case study is presented to evaluate the proposed methodology and obtain comparison studies using different workloads and protocols.

As application complexity increases, modern embedded systems have adopted heterogeneous processing elements to enhance the computing capability or to reduce the power consumption. The heterogeneity has introduced challenges for energy efficiency in hardware and software implementations. This paper studies how to partition real-time tasks on a platform with heterogeneous processing elements (processors) so that the energy consumption can be minimized. The power consumption models considered in this paper are very general by assuming that the energy consumption with higher workload is larger than that with lower workload, which is true for many systems. We propose an approximation scheme to derive near-optimal solutions for different hardware configurations in energy/power consumption. When the number of processors is a constant, the scheme is a fully polynomial time approximation scheme (FPTAS) to derive a solution with energy consumption very close to the optimal energy consumption in polynomial-time/space complexity. Experimental results reveal that the proposed scheme is very effective in energy efficiency with comparison to the state-of-the-art algorithm.

Dynamic voltage scaling (DVS) has been widely adopted to reduce the energy consumption resulting from the dynamic power of modern processors. However, while the leakage power resulting from the leakage current becomes significant, how to aggregate the idle time to turn processors to the sleep or dormant modes is crucial in reducing the overall energy consumption. Moreover, for systems with non-DVS components, the execution order of tasks also affects the system-wide energy consumption. With the consideration of the dynamic and leakage power of processors as well as the power consumption resulting from non-DVS components, this paper summarizes our work on energy-efficient real-time task scheduling for both uniprocessor and multiprocessor platforms through procrastination of task executions, preemption control, and proper task assignment.

Energy-efficiency has been an important system issue in hardware and software designs for both real-time embedded systems and server systems. This research explores systems with probabilistic distribution on the execution time of realtime tasks on homogeneous multiprocessor platforms with the capability of dynamic voltage scaling (DVS). The objective is to derive a task partition which minimizes the expected energy consumption for completing all the given tasks in time. We give an efficient 1.13-approximation algorithm and a polynomial-time approximation scheme (PTAS) to provide worst-case guarantees for the strongly NP-hard problem. Experimental results show that the algorithms can effectively minimize the expected energy consumption.

Dynamic voltage scaling (DVS) circuits have been widely adopted in many computing systems to provide tradeoff between performance and power consumption. The effective use of energy could not only extend operation duration for hand-held devices but also cut down power bills of server systems. Moreover, while many chip makers are releasing multi-core chips and multiprocessor system-on-a-chips (SoCs), multiprocessor platforms for different applications become even more popular. Multiprocessor platforms could improve the system performance and accommodate the growing demand of computing power and the variety of application functionality. This paper summarizes our work on several important issues in energy-efficient scheduling for real-time tasks in multiprocessor DVS systems. Distinct from most previous work based on heuristics, we aim at the provision of approximated solutions with worst-case guarantees. The proposed algorithms are evaluated by a series of experiments to provide insights in system designs.

Dynamic voltage scaling (DVS) has been adopted in many computing systems to reduce the energy consumption of the processor by slowing down the processor speed. However, for system devices without DVS capability, the longer a task executes, the more energy the task consumes in the required system devices. This paper explores energy-efficient scheduling for periodic hard real-time tasks in a system consisted of a DVS processor and multiple non-DVS system devices. We propose an algorithm for static scheduling which minimizes the system energy consumption of a given set of real-time tasks, provided that each task executes in its worst case. For systems in which some tasks might complete earlier than its estimated worst-case execution time, we develop on-line algorithms to reclaim the slack time to reduce the energy consumption. Compared to existing algorithms, our proposed algorithm can reduce the energy consumption both in the CPU and system devices

Multiprocessor platforms have been widely adopted in both embedded and server systems. In addition to the performance improvement, multiprocessor systems could have the flexibility in tolerating processor failures via task replication. This paper considers the replication of periodic hard real-time tasks in identical multiprocessor environments. Each task is replicated on K distinct processors, where K is a user-determined integer for fault tolerance to improve system reliability. When the objective is to minimize the maximum utilization in a system with a specified number of processors, we present a greedy algorithm with a 2-approximation ratio, and a polynomial-time approximation scheme is developed. For the minimization of the number of processors required to derive feasible schedules with task replication, we develop greedy algorithms with a 2-approximation ratio and an asymptotic polynomial-time approximation scheme

In the past decade, energy-efficient real-time task scheduling has been widely explored in terms of various optimization problems. With a very different goal, this paper considers real-time task synchronization protocols with the minimization of energy consumption. We propose the concept of frequency locking and extend the priority ceiling protocol by locking the processor frequency in a restricted way so that the cost in frequency switching is better managed. Algorithms are proposed to assign tasks base frequencies in the minimization of the energy consumption and with the consideration of schedulability tests. The capability of the proposed methodology is evaluated by a series of experiments, for which encouraging results were presented.

In reality, peripheral devices often make a significant contribution to the power consumption of the entire system. An effective energy-efficient scheduling algorithm should consider not only the energy consumption of the processor but also the usages of devices. In this paper, we explore energy-efficient scheduling of periodic real-time tasks in a system with a dynamic-voltage-scaling (DVS) processor and multiple non-DVS system devices. We consider systems that any device used by a task remains operating while the task is active. We propose scheduling algorithms in the management of task preemption to reduce the energy consumption of devices. Simulation results show that our proposed algorithms could not only reduce the number of task preemption significantly but also minimize the energy consumption, compared to earliest-deadline-first scheduling.

This work is motivated by the needs of energy-efficient designs for multi-context FPGAs. Dynamic-voltage-scaling-based algorithms are proposed to schedule loading and executing of tasks in a multi-context FPGA. When a task partition over contexts is given, two optimal scheduling algorithms are proposed in minimizing the energy consumption and the maximum time span of task executions. When no task partition is given, two approximation algorithms with approximation ratios 2.371 and 1.540 are presented in the energy-consumption minimization and the maximum-time-span minimization, respectively.

In the recent decade, voltage scaling has become an attractive feature for many system component designs. In this paper we consider energy-efficient real-time task scheduling over a chip multiprocessor architecture. The objective is to schedule a set of frame-based tasks with the minimum energy consumption, where all tasks are ready at time 0 and share a common deadline. We show that such a minimization problem is NP-hard and then propose a 2.371-approximation algorithm. The strength of the proposed algorithm was demonstrated by a series of simulations, for which near optimal results were obtained.

Strong connectivity has been an important feature explored in many network applications, such as sensor networks. This research focuses on a dual power assignment problem, where each sensor node has two transmission power levels. The objective is to minimize the number of wireless sensor nodes assigned to transmit messages at the high transmission power level, while the resulting sensor network is strongly connected. We propose an efficient 1.75-approximation algorithm for this challenging problem. We not only show that the approximation ratio of the proposed algorithm is tight but also demonstrate the capability of the proposed algorithm in terms of simulation experiments.