Statistical Analysis and Process Variation-Aware Routing and Skew Assignment for FPGAs

ABSTRACT

With constant scaling of process technologies, chip design is becoming increasingly difficult due to process variations. The FPGA community has only recently started focusing on the effects of variations. In this work we present a statistical analysis to compare the effects of variations on designs mapped to FPGAs and ASICs. We also present CAD and architecture techniques to mitigate the impact of variations. First we present a variation-aware router that optimizes statistical criticality. We then propose a modification to the clock network to deliver programmable skews to different flip-flops. Finally, we combine the two techniques and the result is a 9x reduction in yield loss that translates to a 12% improvement in timing yield. When the desired timing yield is set to 99%, our combined statistical routing and skew assignment technique results in a delay improvement of about 10% over a purely deterministic approach.

REFERENCES

• 1: Charles J. Alpert , Jiang Hu , Sachin S. Sapatnekar , Paul Villarrubia, A practical methodology for early buffer and wire resource allocation, Proceedings of the 38th conference on Design automation, p.189-194, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.378461]
• 2: Berkeley-Device-Group. Predictive technology model. http://www.eas.asu.edu/ptm.
• 3: Vaughn Betz , Jonathan Rose , Alexander Marquardt, Architecture and CAD for Deep-Submicron FPGAs, Kluwer Academic Publishers, Norwell, MA, 1999
• 4: Capo. A large scale fixed-die placer from UCLA. http://vlsicad.ucsd.edu/GSRC/bookshelf/Slots/ Placement.
• 5: A. Chakraborty , K. Duraisami , A. Sathanur , P. Sithambaram , L. Benini , A. Macii , E. Macii , M. Poncino, Dynamic thermal clock skew compensation using tunable delay buffers, Proceedings of the 2006 international symposium on Low power electronics and design, October 04-06, 2006, Tegernsee, Bavaria, Germany [doi>10.1145/1165573.1165612]
• 6: Chang, H. and Sapatnekar, S. 2005. Statistical timing analysis under spatial correlations. IEEE Trans. Computer-Aid. Des. Integ. Circ. Syst. 24, 9, 1467--1482.
• 7: 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
• 8: Clark, C. 1961. The greatest of a finite set of random variables. Operations Research 9, 85--91.
• 9: Brian Cline , Kaviraj Chopra , David Blaauw , Yu Cao, Analysis and modeling of CD variation for statistical static timing, Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design, November 05-09, 2006, San Jose, California [doi>10.1145/1233501.1233514]
• 10: Paul Friedberg , Yu Cao , Jason Cain , Ruth Wang , Jan Rabaey , Costas Spanos, Modeling Within-Die Spatial Correlation Effects for Process-Design Co-Optimization, Proceedings of the 6th International Symposium on Quality of Electronic Design, p.516-521, March 21-23, 2005 [doi>10.1109/ISQED.2005.82]
• 11: M. R. Guthaus , N. Venkateswarant , C. Visweswariaht , V. Zolotov, Gate sizing using incremental parameterized statistical timing analysis, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.1029-1036, November 06-10, 2005, San Jose, CA
• 12: Krishnan, G. Low-cost easypath FPGAs offer promise to ASSP companies. www.xilinx.com/ publications/xcellonline/xcell_53/xc_easyassp53.htm.
• 13: Yan Lin , Lei He, Stochastic physical synthesis for FPGAs with pre-routing interconnect uncertainty and process variation, Proceedings of the 2007 ACM/SIGDA 15th international symposium on Field programmable gate arrays, February 18-20, 2007, Monterey, California, USA [doi>10.1145/1216919.1216931]
• 14: Lin, Y., Hutton, M., and Hei, L. 2006. Placement and timing for FPGAs considering variations. In Proceedings of the International Conference on Field Programmable Logic and Applications.
• 15: Mishchenko, A., Chatterjee, S., Brayton, R., and Ciesielski, M. 2005. An integrated technology mapping environment. In Proceedings of the International Workshop on Logic Synthesis.
• 16: Hushrav D Mogal , Haifeng Qian , Sachin S Sapatnekar , Kia Bazargan, Clustering based pruning for statistical criticality computation under process variations, Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design, November 05-08, 2007, San Jose, California
• 17: OpenAccess. Library core of EDA algorithms and infrastructure for openaccess. http://www. openedatools.org/projects/oagear.
• 18: Kara K. W. Poon , Steven J. E. Wilton , Andy Yan, A detailed power model for field-programmable gate arrays, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.10 n.2, p.279-302, April 2005 [doi>10.1145/1059876.1059881]
• 19: 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]
• 20: Rebonato, R., and Jackel, P. 1999. The most genereral methodology to create a valid correlation matrix for risk management and pricing purposes. J. Risk 2, 2.
• 21: Sachin Sapatnekar, Timing, Springer-Verlag New York, Inc., Secaucus, NJ, 2004
• 22: Sedcole, P. and Cheung, P. Y. K. 2006. Within-die delay variability in 90nm FPGAs and beyond. In Proceedings of the IEEE International Conference on Field Programmable Technology.
• 23: Deshanand P. Singh , Stephen D. Brown, Constrained clock shifting for field programmable gate arrays, Proceedings of the 2002 ACM/SIGDA tenth international symposium on Field-programmable gate arrays, February 24-26, 2002, Monterey, California, USA [doi>10.1145/503048.503067]
• 24: Sivaswamy, S. and Bazargan, K. 2007a. Statistical generic and chip-specific skew assignment for improving timing yield of FPGAs. In Proceedings of the International Conference on Field Programmable Logic and Its Applications.
• 25: Satish Sivaswamy , Kia Bazargan, Variation-aware routing for FPGAs, Proceedings of the 2007 ACM/SIGDA 15th international symposium on Field programmable gate arrays, February 18-20, 2007, Monterey, California, USA [doi>10.1145/1216919.1216930]
• 26: Jeng-Liang Tsai , DongHyun Baik , C. C. -P. Chen , K. K. Saluja, A yield improvement methodology using pre- and post-silicon statistical clock scheduling, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.611-618, November 07-11, 2004 [doi>10.1109/ICCAD.2004.1382649]
• 27: 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]
• 28: Wang, L. 2005. An energy-efficient skew compensation technique for high-speed skew sensitive signaling. In Proceedings of the International Symposium on Circuits and Systems.
• 29: Ho-Yan Wong , Lerong Cheng , Yan Lin , Lei He, FPGA device and architecture evaluation considering process variations, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.19-24, November 06-10, 2005, San Jose, CA
• 30: Chao-Yang Yeh , Malgorzata Marek-Sadowska, Skew-programmable clock design for FPGA and skew-aware placement, Proceedings of the 2005 ACM/SIGDA 13th international symposium on Field-programmable gate arrays, February 20-22, 2005, Monterey, California, USA [doi>10.1145/1046192.1046198]

INDEX TERMS

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

General Terms:
Algorithms, Design, Performance

Keywords:
Statistical timing analysis, routing, skew assignment