Power-aware scheduling of conditional task graphs in real-time multiprocessor systems

ABSTRACT

We propose a novel power-aware task scheduling algorithm for DVS-enabled real-time multiprocessor systems. Unlike the existing algorithms, the proposed DVS algorithm can handle conditional task graphs (CTGs) which model more complex precedence constraints. We first propose a condition-unaware task scheduling algorithm integrating the task ordering algorithm for CTGs and the task stretching algorithm for unconditional task graphs. We then describe a condition-aware task scheduling algorithm which assigns to each task the start time and the clock speed, taking account of the condition matching and task execution profiles. Experimental results show that the proposed condition-aware task scheduling algorithm can reduce the energy consumption by 50% on average over the non-DVS task scheduling algorithm.

REFERENCES

• 1: 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
• 2: P. Eles , K. Kuchcinski , Z. Peng , A. Doboli , P. Pop, Scheduling of conditional process graphs for the synthesis of embedded systems, Proceedings of the conference on Design, automation and test in Europe, p.132-139, February 23-26, 1998, Le Palais des Congrés de Paris, France
• 3: G. A. Gabriele and K. M. Ragsdell. The generalized gradient method: a reliable tool for optimal design. ASME Journal of Engineering and Industry, Series B, Vol. 99, No. 2, pp. 394, 1977.
• 4: Woonseok Kim , Dongkun Shin , Han-Saem Yun , Jihong Kim , Sang Lyul Min, Performance Comparison of Dynamic Voltage Scaling Algorithms for Hard Real-Time Systems, Proceedings of the Eighth IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS'02), p.219, September 25-27, 2002
• 5: Jiong Luo , Niraj K. Jha, Static and Dynamic Variable Voltage Scheduling Algorithms for Real-Time Heterogeneous Distributed Embedded Systems, Proceedings of the 2002 conference on Asia South Pacific design automation/VLSI Design, p.719, January 07-11, 2002
• 6: Marcus T. Schmitz , Bashir M. Al-Hashimi, Considering power variations of DVS processing elements for energy minimisation in distributed systems, Proceedings of the 14th international symposium on Systems synthesis, September 30-October 03, 2001, Montréal, P.Q., Canada [doi>10.1145/500001.500060]
• 7: M. Schmitz , B. Al-Hashimi , P. Eles, Energy-Efficient Mapping and Scheduling for DVS Enabled Distributed Embedded Systems, Proceedings of the conference on Design, automation and test in Europe, p.514, March 04-08, 2002
• 8: Y. Xie , W. Wolf, Allocation and scheduling of conditional task graph in hardware/software co-synthesis, Proceedings of the conference on Design, automation and test in Europe, p.620-625, March 2001, Munich, Germany
• 9: Yumin Zhang , Xiaobo Sharon Hu , Danny Z. Chen, Task scheduling and voltage selection for energy minimization, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA [doi>10.1145/513918.513966]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

General Terms:
Algorithms, Design

Keywords:
conditional task graph, dynamic voltage scaling, multiprocessor, real-time systems