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.

REFERENCES

• 1: M. Mostofa Akbar , Eric G. Manning , Gholamali C. Shoja , Shahadat Khan, Heuristic Solutions for the Multiple-Choice Multi-dimension Knapsack Problem, Proceedings of the International Conference on Computational Science-Part II, p.659-668, May 28-30, 2001
• 2: A. Azevedo , I. Issenin , R. Cornea , R. Gupta , N. Dutt , A. Veidenbaum , A. Nicolau, Profile-Based Dynamic Voltage Scheduling Using Program Checkpoints, Proceedings of the conference on Design, automation and test in Europe, p.168, March 04-08, 2002
• 3: Eui-Young Chung , Giovanni De Micheli , Luca Benini, Contents provider-assisted dynamic voltage scaling for low energy multimedia applications, Proceedings of the 2002 international symposium on Low power electronics and design, August 12-14, 2002, Monterey, California, USA [doi>10.1145/566408.566420]
• 4: Abram P. Dancy , Rajeevan Amirtharajah , Anantha P. Chandrakasan, High-efficiency multiple-output DC-DC conversion for low-voltage systems, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.8 n.3, p.252-263, June 2000 [doi>10.1109/92.845892]
• 5: Robert P. Dick , David L. Rhodes , Wayne Wolf, TGFF: task graphs for free, Proceedings of the 6th international workshop on Hardware/software codesign, p.97-101, March 15-18, 1998, Seattle, Washington, United States
• 6: Tony Givargis , Frank Vahid , Jörg Henkel, System-level exploration for Pareto-optimal configurations in parameterized system-on-a-chip (December 2002), IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.10 n.4, p.416-422, August 2002 [doi>10.1109/TVLSI.2002.807764]
• 7: I. Hong et al. Power Optimization of Variable Voltage Core-Based Systems. IEEE Trans. Computer Aided Design, 18(12):1702--14, Dec. 1999.
• 8: Niraj K. Jha, Low power system scheduling and synthesis, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
• 9: Seongsoo Lee , Takayasu Sakurai, Run-time voltage hopping for low-power real-time systems, Proceedings of the 37th conference on Design automation, p.806-809, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337785]
• 10: Sunghyun Lee , Kiyoung Choi , Sungjoo Yoo, An intra-task dynamic voltage scaling method for SoC design with hierarchical FSM and synchronous dataflow model, Proceedings of the 2002 international symposium on Low power electronics and design, August 12-14, 2002, Monterey, California, USA [doi>10.1145/566408.566432]
• 11: C. L. Liu , James W. Layland, Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment, Journal of the ACM (JACM), v.20 n.1, p.46-61, Jan. 1973 [doi>10.1145/321738.321743]
• 12: Silvano Martello , Paolo Toth, Knapsack problems: algorithms and computer implementations, John Wiley & Sons, Inc., New York, NY, 1990
• 13: Pedro Mejia-Alvarez , Eugene Levner , Daniel Mossé, Power-Optimized Scheduling Server for Real-Time Tasks, Proceedings of the Eighth IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS'02), p.239, September 25-27, 2002
• 14: D. Pisinger. Algorithms for Knapsack Problems. PhD thesis, Dept. of Computer Science, University of Copenhagen, Denmark, 1995.
• 15: Johan Pouwelse , Koen Langendoen , Henk Sips, Energy priority scheduling for variable voltage processors, Proceedings of the 2001 international symposium on Low power electronics and design, p.28-33, August 2001, Huntington Beach, California, United States [doi>10.1145/383082.383089]
• 16: Gang Quan , Xiaobo Hu, Energy efficient fixed-priority scheduling for real-time systems on variable voltage processors, Proceedings of the 38th conference on Design automation, p.828-833, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.379074]
• 17: K. Ramamritham and J. A. Stankovic. Scheduling Algorithms and Operation Systems Support for Real-Time Systems. Proc. IEEE, 82(1):55--67, Jan. 1994.
• 18: Dongkun Shin , Jihong Kim , Seongsoo Lee, Low-energy intra-task voltage scheduling using static timing analysis, Proceedings of the 38th conference on Design automation, p.438-443, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.378551]
• 19: Youngsoo Shin , Kiyoung Choi, Power conscious fixed priority scheduling for hard real-time systems, Proceedings of the 36th ACM/IEEE conference on Design automation, p.134-139, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309901]
• 20: Youngsoo Shin , Kiyoung Choi , Takayasu Sakurai, Power optimization of real-time embedded systems on variable speed processors, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 21: Peng Yang , Paul Marchal , Chun Wong , Stefaan Himpe , Francky Catthoor , Patrick David , Johan Vounckx , Rudy Lauwereins, Managing dynamic concurrent tasks in embedded real-time multimedia systems, Proceedings of the 15th international symposium on System Synthesis, October 02-04, 2002, Kyoto, Japan [doi>10.1145/581199.581226]

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.7 Organization and Design
          Subjects: Real-time systems and embedded systems

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management

General Terms:
Algorithms, Design, Performance

Keywords:
Pareto optimization, embedded system, low-power, scheduling