Timing variation-aware task scheduling and binding for MPSoC

ABSTRACT

This work addresses the new problem of timing variation-aware task scheduling and binding (TSB) for multiprocessor system-on-chip (MPSoC) architecture in the system-level design, where tasks have full flexibilities of resource (i.e., processor) sharing to meet the design constraints. With the timing variation of processors' clock speed, it has been observed that considering the effects of resource sharing on the resulting performance yield computation is critically important for accurate design space exploration and evaluation in the system-level design. Unfortunately previous statistical static timing analysis (SSTA) in the system-level has never considered resource sharing in computing the performance yield, or has overly simplified by employing the gate-level SSTAs. In this work, we overcome those limitations by proposing an effective SSTA technique called TSB-SSTA, which schedules and binds tasks to resources in the presence of resource sharing. We also propose a timing variation-aware (TV) framework, called TSB-TV, tightly integrating TSB-SSTA. We have tested the effectiveness of our approach through experimentation with benchmarks, which showed an average of 56.1% improvement in performance yield over conventional methods.

REFERENCES

• 1: Feng Wang , C. Nicopoulos , Xiaoxia Wu , Yuan Xie , N. Vijaykrishnan, Variation-aware task allocation and scheduling for MPSoC, Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design, November 05-08, 2007, San Jose, California
• 2: Sudarshan Banerjee , Nikil Dutt, Efficient search space exploration for HW-SW partitioning, Proceedings of the 2nd IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, September 08-10, 2004, Stockholm, Sweden [doi>10.1145/1016720.1016752]
• 3: 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]
• 4: 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]
• 5: R. P. Dick and N. K. Jha, "MOGAC: a multiobjective genetic algorithm for hardware-software cosynthesis of distributed embedded systems," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 17, No. 10, pp. 920--935, Oct. 1998.
• 6: 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]
• 7: 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]
• 8: 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
• 9: Jiong Luo , Niraj K. Jha, Power-conscious joint scheduling of periodic task graphs and aperiodic tasks in distributed real-time embedded systems, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 10: 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
• 11: 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]
• 12: 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]
• 13: Lerong Cheng , Jinjun Xiong , Lei He, Non-linear statistical static timing analysis for non-Gaussian variation sources, Proceedings of the 44th annual conference on Design automation, June 04-08, 2007, San Diego, California [doi>10.1145/1278480.1278541]
• 14: 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]
• 15: C. Visweswariah , K. Ravindran , K. Kalafala , S. G. Walker , S. Narayan, First-order incremental block-based statistical timing analysis, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996663]
• 16: A. Agarwal et al., "Statistical timing analysis using bounds and selective enumeration," IEEE Transactions on Computer-Aided Design, pp. 1243--1260, September 2003.
• 17: Anirudh Devgan , Chandramouli Kashyap, Block-based Static Timing Analysis with Uncertainty, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.607, November 09-13, 2003 [doi>10.1109/ICCAD.2003.41]
• 18: Michael Orshansky , Arnab Bandyopadhyay, Fast statistical timing analysis handling arbitrary delay correlations, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996664]
• 19: Rajeev Rao , Ashish Srivastava , David Blaauw , Dennis Sylvester, Statistical analysis of subthreshold leakage current for VLSI circuits, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.12 n.2, p.131-139, February 2004 [doi>10.1109/TVLSI.2003.821549]
• 20: Siva Narendra , Vivek De , Shekhar Borkar , Dimitri Antoniadis , Anantha Chandrakasan, Full-chip sub-threshold leakage power prediction model for sub-0.18 μm CMOS, Proceedings of the 2002 international symposium on Low power electronics and design, August 12-14, 2002, Monterey, California, USA [doi>10.1145/566408.566415]
• 21: Sreeja Raj , Sarma B. K. Vrudhula , Janet Wang, A methodology to improve timing yield in the presence of process variations, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996694]
• 22: Seung Hoon Choi , Bipul C. Paul , Kaushik Roy, Novel sizing algorithm for yield improvement under process variation in nanometer technology, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996695]
• 23: 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]
• 24: A. Davoodi , V. Khandelwal , A. Srivastava, Variability inspired implementation selection problem, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.423-427, November 07-11, 2004 [doi>10.1109/ICCAD.2004.1382612]
• 25: W.-L. Hung , Xiaoxia Wu , Yuan Xie, Guaranteeing performance yield in high-level synthesis, Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design, November 05-09, 2006, San Jose, California [doi>10.1145/1233501.1233561]
• 26: Feng Wang , Xiaoxia Wu , Yuan Xie, Variability-driven module selection with joint design time optimization and post-silicon tuning, Proceedings of the 2008 conference on Asia and South Pacific design automation, January 21-24, 2008, Seoul, Korea
• 27: Jongyoon Jung , Taewhan Kim, Timing variation-aware high-level synthesis, Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design, November 05-08, 2007, San Jose, California
• 28: 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
• 29: 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]
• 30: 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]
• 31: B. W. Kernighan and S. Lin, "An efficient heuristic procedure for partitioning graphs," Bell System Tech. Journal, April 1970.
• 32: Jing-Jia Liou , Kwang-Ting Cheng , Sandip Kundu , Angela Krstic, Fast statistical timing analysis by probabilistic event propagation, Proceedings of the 38th conference on Design automation, p.661-666, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.379043]
• 33: R. Dick, "Embedded systems synthesis benchmark suites (e3s)," http://www.ece.nothwestern.edu/.dickrp/e3s.
• 34: 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