A variation-tolerant scheduler for better than worst-case behavioral synthesis

ABSTRACT

There has been a recent shift in design paradigms, with many turning towards yield-driven approaches to synthesize and design systems. A major cause of this shift is the continual scaling of transistors, making process variation impossible to ignore. Better than worst-case (BTW) designs also exploit these variation effects, while also addressing performance limits due to worst-case analysis. In this paper we first present the variation-tolerant stallable-FSM architecture, which provides fault detection and recovery, allowing circuits to be clocked at better than worst-case delays. Then we propose the BTW scheduler, a 0-1 integer linear programming (ILP) scheduling algorithm with the objective of minimizing the expected latency, to provide a high-level synthesis aid for the stallable-FSM architecture. We implemented the algorithm and ran it through many benchmarks, comparing the results with scheduling algorithms based on worst-case analysis. Our results were promising, showing up to 41% latency reduction for the BTW scheduler, and up to 43% latency reduction when combined with the variation-tolerant architecture.

REFERENCES

• 1: Altera DE2 Board, http://www.altera.com/education /univ/materials /boards/unv-de2-board.html#boardinfo.
• 2: S. Nassif, V. Pitchumani, N. Rodriguez, D. Sylvester, C. Bittlestone, R. Radojcic, "Variation-Aware Analysis: Savior of the Nanometer Era?" Proc. Design Automation Conf. 2006, pp. 411--412.
• 3: D. Chen, J. Cong, Y. Fan, G. Han, W. Jiang, Z. Zhang, "xPilot: A Platform-Based Behavioral Synthesis System," SRC TechCon, 2005.
• 4: J. Jung, T. Kim, "Timing Variation-Aware High-Level Synthesis", Proc. Int. Conf. Computer-Aided Design, 2007, pp. 424--428.
• 5: F. Wang, G. Sun, Y. Xie, "A Variation Aware High Level Synthesis Framework," Proc. Deisng Automation & Test Europe, 2008, pp.1063--1068.
• 6: W.L. Hung, X. Wu, Y. Xie, "Guaranteeing Performance Yield in High-Level Synthesis," Proc. Int. Conf. Computer-Aided Design, 2006, pp.303--309.
• 7: J. Cong, K. Minkovich, "Mapping for better than worst-case delays in LUT-based FPGA designs," Proc. Int. Symp. Field-Programmable Gate Arrays, 2008, pp. 56--64.
• 8: S. Suhaib, D. Mathaikutty, S. Shukla. "Dataflow Architectures for GALS." Electron. Notes Theor. Comput. Sci., Feb. 2008, pp. 33--50.
• 9: J. Cong, Z. Zhang, "An efficient and versatile scheduling algorithm based on SDC formulation," Proc. Design Automation Conf., 2006, pp.433--438.
• 10: D. Ernst, N. S. Kim, S. Das, S. Pant, T. Pham, R. Rao, C. Ziesler, D. Blaauw, T. Austin, T. Mudge, K. Flautner, "Razor: A Low-Power Pipeline Based on Circuit-Level Timing Speculation," Proc. Int. Symp. Microarchitecture, 2003.
• 11: L. Carloni, K. McMillan, A. Sangiovanni-Vincentelli, "Latency Insensitive Protocols," Proc. Intl. Conf. Computer-Aided Verification, July, 1999.
• 12: Z. Wo; I. Koren, M. Ciesielski, "An ILP formulation for yield-driven architectural synthesis," Proc. Int. Symp. Defect and Fault Tolerance in VLSI Systems, 2005, pp. 12--20.
• 13: S. Tosun, O. Ozturk , N. Mansouri , E. Arvas , M. Kandemir , Y. Xie , W-L. Hung, "An ILP Formulation for Reliability-Oriented High--Level Synthesis", Proc. Int. Symp. Quality Electronic Design, 2005, pp.364--369.
• 14: Y. Chen, J. Ouyang, Y. Xie, "ILP-based scheme for timing variation-aware scheduling and resource binding," Proc. Int. SOC Conference, 2008, pp.27--30.
• 15: L. Carloni, K. McMillan, A. Sangiovanni-Vincentelli, "Theory of Latency-Insensitive Design," IEEE Trans. Computer--Aided Design of Integrated Circuits and Systems, vol. 20, no. 9, Sept. 2001, pp. 1059--1076.
• 16: M. Singh, M. Theobald, "Generalized Latency-Insensitive Systems for Single-Clock and Multi-Clock Architectures," Proc. Design, Automation and Test in Europe, 2004.
• 17: T. Austin, V. Bertacco, D. Blaauw, T. Mudge, "Opportunities and challenges for better than worst-case design," Proc. Asia South Pacifica Design Automation Conf., 2005, pp. 18--21.
• 18: A.J. Martin, "Asynchronous Datapaths and the Design of an Asynchronous Adder", Formal Methods in System Design, volume 1:1, July 1992, pp. 119--137.
• 19: M.E. Dean, D.L. Dill, M. Horowitz, "Self-Timed Logic Using Current-Sensing Completion Detection", Proc. Int. Conf. Computer Design, 1991.
• 20: S.M. Nowick, K.Y. Yun, A.E. Dooply, P.A. Beerel, "Speculative Completion for the Design of High-Performance Asynchronous Dynamic Adders," Proc. Int. Symp. Advanced Research in Asynchronous Circuits and Systems, 1997, pp. 210--223.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids

General Terms:
Algorithms, Experimentation, Reliability

Keywords:
behavioral synthesis, scheduling, variation