Energy-Efficient Scheduling Of Stream Applications On Heterogeneous Multi-core Platform

Streaming applications are an important class of program in embedded systems, such as multimedia, digital signal processing applications. More and more devices use heterogeneous multi-core processors to improve the performance of these applications. Such applications are required to reach high throughput to run smoothly. Users who use such applications are not only interested in the implementation performance, but also the battery duration and heat dissipation of the device. Battery duration and heat dissipation are usually associated with the energy consuming by these applications. In order to meet the requirements of users, electronic system designers need to design schedules with high throughput and low energy consumption. But increasing complexities of systems make it a huge challenge for engineers.Model-based development method may help engineers to identify and solve performance problems at earlier stages of system development. It can reduce risks and cost of system development and effectively shorten the development cycle. Synchronous Data Flow Graphs(SDFG) are widely used to model streaming applications. The input model of this paper is called system model including an SDFG to model stream applications and a heterogeneous multi-core platform. The goal of this paper is to get static schedules with Pareto optimal throughput and energy consumption of the system model. It helps system designers to make trade-off between throughput and energy consumption.We propose a parallel based Pareto optimal scheduling(PPOS) algorithm to solve this problem. PPOS provides a procedure to construct a full space of schedules step by step and finally finds Pareto optimal schedules. In order to speed up, we prune the state space while ensuring the accuracy. And we parallelize the algorithm to further improve the ability to solve larger scale problems with a rational design of the data storage structure. PPOS is applicable for multi-objective optimization. We can get different approximation strategies by changing the pruning rules. It can provide a trade-off between accuracy and efficiency. We present two approximation algorithms, with look-back strategy and greedy strategy, respectively. We can solve small scale problems exactly and provide efficient solutions for larger problems. Experimental results show that the efficiency of the algorithm is better than the method based on model checking while guaranteeing the accuracy. Compared with genetic algorithms, PPOS is more accurate and can get more Pareto optimal schedules.