Paper Info
Title
Pareto-optimization-based run-time task scheduling for embedded systems
Abstract
Pareto-set-based optimization can be found in several different areas of embedded system design. One example is task scheduling, where different task mapping and ordering choices for a target platform will lead to different performance/cost tradeoffs. To explore this design space at run-time, a fast and effective heuristic is needed. We have modeled the problem as the well known Multiple Choice Knapsack Problem(MCKP) and have developed a fast greedy heuristic for the run-time task scheduling. To show the effectiveness of our algorithm, examples from randomly generated task graphs and realistic applications are studied. Compared to the optimal dynamic programming solver, the heuristic is more than ten times faster while the result is less than 5\% away from the optimum. Moreover, due to its iterative feature, the algorithm is well suitable to be used as an on-line algorithm.
Year
DOI
Venue
2003
10.1145/944645.944680
CODES+ISSS
Keywords
Field
DocType
fast greedy heuristic,effective heuristic,task scheduling,design space,run-time task scheduling,on-line algorithm,task graph,different task mapping,pareto-optimization-based run-time task scheduling,different performance,embedded system,different area,pareto optimization,online algorithm,scheduling,greedy heuristic
Design space,Dynamic programming,Graph,Heuristic,Mathematical optimization,Scheduling (computing),Computer science,Greedy algorithm,Multi-objective optimization,Solver
Conference
ISBN
Citations 
PageRank 
1-58113-742-7
31
2.56
References 
Authors
22
2
Name
Order
Citations
PageRank
Peng Yang119213.90
Francky Catthoor23932423.30