Scheduling task dependence graphs with variable task execution times onto heterogeneous multiprocessors

ABSTRACT

We present a statistical optimization approach for scheduling a task dependence graph with variable task execution times onto a heterogeneous multiprocessor system. Scheduling methods in the presence of variations typically rely on worst-case timing estimates for hard real-time applications, or average-case analysis for other applications. However, a large class of soft real-time applications require only statistical guarantees on latency and throughput. We present a general statistical model that captures the probability distributions of task execution times as well as the correlations of execution times of different tasks. We use a Monte Carlo based technique to perform makespan analysis of different schedules based on this model. This approach can be used to analyze the variability present in a variety of soft real-time applications, including a H.264 video processing application.

We present two scheduling algorithms based on statistical makespan analysis. The first is a heuristic based on a critical path analysis of the task dependence graph. The other is a simulated annealing algorithm using incremental timing analysis. Both algorithms take as input the required statistical guarantee, and can thus be easily re-used for different required guarantees. We show that optimization methods based on statistical analysis show a 25-30% improvement in makespan over methods based on static worst-case analysis.

REFERENCES

• 1: J. C. Beck and N. Wilson. Proactive Algorithms for Job Shop Scheduling with Probabilistic Durations. Journal of Artificial Intelligence Research, 28:183--232, 2007.
• 2: Giorgio C. Buttazzo, Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications, Kluwer Academic Publishers, Norwell, MA, 1997
• 3: Chandra Sekhar Chekuri , Rajeev Motwani, Approximation algorithms for scheduling problems, Stanford University, Stanford, CA, 1998
• 4: William Y. Chen , Scott A. Mahlke , Nancy J. Warter , Sadun Anik , Wen-mei W. Hwu, Profile-assisted instruction scheduling, International Journal of Parallel Programming, v.22 n.2, p.151-181, April 1994 [doi>10.1007/BF02577873]
• 5: J. Chong, N. R. Satish, B. Catanzaro, K. Ravindran, and K. Keutzer. Efficient Parallelization of H.264 Decoding with Macro Block Level Scheduling. In 2007 Intl. Conference on Multimedia and Expo, pages 1874--1877, July 2007.
• 6: Tatjana Davidović , Teodor Gabriel Crainic, Benchmark-problem instances for static scheduling of task graphs with communication delays on homogeneous multiprocessor systems, Computers and Operations Research, v.33 n.8, p.2155-2177, August 2006 [doi>10.1016/j.cor.2005.01.005]
• 7: M. Drake, W. Thies, and S. Amarasinghe. MPEG Coding in StreamIt. http://www.cag.csail.mit.edu/streamit/mpeg/.
• 8: C. V. et al. First-Order Incremental Block-Based Statistical Timing Analysis. IEEE Trans. on Computer-Aided Design, 25(10):2170--2180, October 2006.
• 9: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 10: Hasyim Gautama , Arjan J. C. van Gemund, Static performance prediction of data-dependent programs, Proceedings of the 2nd international workshop on Software and performance, p.216-226, September 2000, Ottawa, Ontario, Canada [doi>10.1145/350391.350435]
• 11: Matthias Gries, Methods for evaluating and covering the design space during early design development, Integration, the VLSI Journal, v.38 n.2, p.131-183, December 2004 [doi>10.1016/j.vlsi.2004.06.001]
• 12: T. Hu. Parallel Sequencing and Assembly Line Problems. Oper. Res., 19(6):841--848, Nov 1961.
• 13: H. Kasahara , S. Narita, Practical Multiprocessor Scheduling Algorithms for Efficient Parallel Processing, IEEE Transactions on Computers, v.33 n.11, p.1023-1029, November 1984 [doi>10.1109/TC.1984.1676376]
• 14: S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi. Optimization by Simulated Annealing. Science, 220(4598):498--516, May 1983.
• 15: P. Koch. Strategies for Realistic and Efficient Static Scheduling of Data Ind. Algorithms onto Multiple Digital Signal Processors. PhD thesis, Aalborg University, 1995.
• 16: Yu-Kwong Kwok , Ishfaq Ahmad, Static scheduling algorithms for allocating directed task graphs to multiprocessors, ACM Computing Surveys (CSUR), v.31 n.4, p.406-471, Dec. 1999 [doi>10.1145/344588.344618]
• 17: Edward Ashford Lee , David G. Messerschmitt, Static scheduling of synchronous data flow programs for digital signal processing, IEEE Transactions on Computers, v.36 n.1, p.24-35, Jan. 1987 [doi>10.1109/TC.1987.5009446]
• 18: Murari Mani , Michael Orshansky, A New Statistical Optimization Algorithm for Gate Sizing, Proceedings of the IEEE International Conference on Computer Design, p.272-277, October 11-13, 2004
• 19: Sorin Manolache , Petru Eles , Zebo Peng, Real-Time Applications with Stochastic Task Execution Times: Analysis and Optimisation, Springer-Verlag New York, Inc., Secaucus, NJ, 2007
• 20: Asawaree Kalavade , Pratyush Moghé, A tool for performance estimation of networked embedded end-systems, Proceedings of the 35th annual conference on Design automation, p.257-262, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277116]
• 21: H. Orsila, T. Kangas, E. Salminen, and T. D. Hamalainen. Parameterizing Simulated Annealing for Distributing Task Graphs on Multiprocessor Socs. In Proc. of the Intl. Symposium on System-on-chip, pages 1--4, Nov 2006.
• 22: K. Ravindran. Task Allocation and Scheduling of Concurrent Applications to Multiprocessor Systems. PhD thesis, University of California, Berkeley, Nov 2007.
• 23: G. C. Sih , E. A. Lee, A Compile-Time Scheduling Heuristic for Interconnection-Constrained Heterogeneous Processor Architectures, IEEE Transactions on Parallel and Distributed Systems, v.4 n.2, p.175-187, February 1993 [doi>10.1109/71.207593]
• 24: Ashish Srivastava , Dennis Sylvester , David Blaauw, Statistical optimization of leakage power considering process variations using dual-Vth and sizing, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996775]
• 25: Lothar Thiele, Resource constrained scheduling of uniform algorithms, Journal of VLSI Signal Processing Systems, v.10 n.3, p.295-310, Aug. 1995 [doi>10.1007/BF02120034]
• 26: A. J. C. van Gemund. Performance Modeling of Parallel Systems. PhD thesis, Delft University of Technology, 1996.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Scheduling

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.8 Performance
          Subjects: Stochastic analysis

General Terms:
Algorithms, Design, Performance, Reliability

Keywords:
list-scheduling, scheduling, simulated annealing, statistical scheduling, variability