Variation-aware task allocation and scheduling for MPSoC

ABSTRACT

As technology scales, the delay uncertainty caused by process variations has become increasingly pronounced in deep submicron designs. As a result, a paradigm shift from deterministic to statistical design methodology at all levels of the design hierarchy is inevitable [1]. In this paper, we propose a variation-aware task allocation and scheduling algorithm for Multiprocessor System-on-Chip (MPSoC) architectures to mitigate the impact of parameter variations. A new design metric, called performance yield and defined as the probability of the assigned schedule meeting the predefined performance constraints, is used to guide the task allocation and scheduling procedure. An efficient yield computation method for task scheduling complements and significantly improves the effectiveness of the proposed variation-aware scheduling algorithm. Experimental results show that our variation-aware scheduler achieves significant yield improvements. On average, 45% and 34% yield improvements over worst-case and nominal-case deterministic schedulers, respectively, can be obtained across the benchmarks by using the proposed variation-aware scheduler.

REFERENCES

• 1: Shekhar Borkar, Designing Reliable Systems from Unreliable Components: The Challenges of Transistor Variability and Degradation, IEEE Micro, v.25 n.6, p.10-16, November 2005 [doi>10.1109/MM.2005.110]
• 2: A. Jerraya and W. Wolf. Multiprocessor systems-on-chips. Morgan Kaufmann Publishers, 2005.
• 3: 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 ]
• 4: Wayne H. Wolf, An architectural co-synthesis algorithm for distributed, embedded computing systems, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.5 n.2, p.218-229, June 1997 [doi>10.1109/92.585225 ]
• 5: 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]
• 6: 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
• 7: Jingcao Hu , Radu Marculescu, Energy-Aware Communication and Task Scheduling for Network-on-Chip Architectures under Real-Time Constraints, Proceedings of the conference on Design, automation and test in Europe, p.10234, February 16-20, 2004
• 8: Hongliang Chang , Sachin S. Sapatnekar, Statistical Timing Analysis Considering Spatial Correlations using a Single Pert-Like Traversal, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.621, November 09-13, 2003 [doi>10.1109/ICCAD.2003.129]
• 9: Aseem Agarwal , David Blaauw , Vladimir Zolotov, Statistical Timing Analysis for Intra-Die Process Variations with Spatial Correlations, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.900, November 09-13, 2003 [doi>10.1109/ICCAD.2003.130]
• 10: D. Sinha , N. V. Shenoy , Hai Zhou, Statistical gate sizing for timing yield optimization, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.1037-1041, November 06-10, 2005, San Jose, CA
• 11: K. Chopra , S. Shah , A. Srivastava , D. Blaauw , D. Sylvester, Parametric yield maximization using gate sizing based on efficient statistical power and delay gradient computation, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.1023-1028, November 06-10, 2005, San Jose, CA
• 12: K. A. Bowman, S. G. Duvall, and J. D. Meindl. Impact of Die-to-Die and Within Die Parameter Fluctuations on the Maximum Clock Frequency Distribution for Gigascale Integration. Journal of Solid-State Circuits, pages 183--190, February 2002.
• 13: T.-S. Tia , Z. Deng , M. Shankar , M. Storch , J. Sun , L.-C. Wu , J. W.-S. Liu, Probabilistic performance guarantee for real-time tasks with varying computation times, Proceedings of the Real-Time Technology and Applications Symposium, p.164, May 15-17, 1995
• 14: Xiaobo Sharon Hu , Tao Zhou , Edwin H.-M. Sha, Estimating probabilistic timing performance for real-time embedded systems, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.9 n.6, p.833-844, 12/1/2001 [doi>10.1109/92.974897 ]
• 15: G. de Veciana , M. Jacome , J.-H. Guo, Hierarchical algorithms for assessing probabilistic constraints on system performance, Proceedings of the 35th annual conference on Design automation, p.251-256, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277113]
• 16: C. Clark. The greatest of a finite set of random variables. Operations Research, pages 145--162, 1961.
• 17: Yanbing Li , Jörg Henkel, A framework for estimation and minimizing energy dissipation of embedded HW/SW systems, Proceedings of the 35th annual conference on Design automation, p.188-193, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277097]
• 18: R. Dick. Embedded systems synthesis benchmarks suite (e3s). http://www.ece.northwestern.edu/dickrp/e3s/.
• 19: Yuan Xie , Wei-Lun Hung, Temperature-Aware Task Allocation and Scheduling for Embedded Multiprocessor Systems-on-Chip (MPSoC) Design, Journal of VLSI Signal Processing Systems, v.45 n.3, p.177-189, December 2006 [doi>10.1007/s11265-006-9760-y]