research-article

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

Authors:

Satish Sivaswamy,

Kia BazarganAuthors Info & Claims

ACM Transactions on Reconfigurable Technology and Systems (TRETS), Volume 1, Issue 1

Article No.: 4, Pages 1 - 35

https://doi.org/10.1145/1331897.1331900

Published: 17 March 2008 Publication History

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]

Alpert, C., Hu, J., Sapatnekar, S., and Villarubia, P. 2001. A practical methodology for early buffer and wire resource allocation. In Proceedings of the Design Automation Conference. 189--194.

Digital Library

[2]

Berkeley-Device-Group. Predictive technology model. http://www.eas.asu.edu/ptm.

[3]

Betz, V., Rose, J., and Marquardt, A. 1999. Architecture and CAD for Deep-Submicron FPGAs. Kluwer Academic Publishers.

Digital Library

[4]

Capo. A large scale fixed-die placer from UCLA. http://vlsicad.ucsd.edu/GSRC/bookshelf/Slots/ Placement.

[5]

Chakraborty, A., Duraisami, K., Sathanur, A., Sithambaram, P., Benini, L., Macii, A., Macii, E., and Poncino, M. 2006. Dynamic thermal clock skew compensation using tunable delay buffers. In Proceedings of the International Symposium on Low Power Electronics and Design.

Digital Library

[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.

Digital Library

[7]

Chopra, K., Shah, S., Srivastava, A., Blaauw, D., and Sylvester, D. 2005. Parametric yield maximization using gate sizing based on efficient statistical power and delay gradient computation. In Proceedings of the International Conference on Computer-Aided-Design.

Digital Library

[8]

Clark, C. 1961. The greatest of a finite set of random variables. Operations Research 9, 85--91.

Digital Library

[9]

Cline, B., Chopra, K., Blaauw, D., and Cao, Y. 2006. Analysis and modeling of CD variation for statistical timing. In Proceeding of the International Conference on Computer-Aided Design.

Digital Library

[10]

Froedberg, P., Cao, Y., Cain, J., Wang, R., Rabaey, J., and Spanos, C. 2005. Modeling within-die spatial correlation effects for process-design co-optimization. In Proceedings of the International Symposium on Quality of Electronic Design. 516--521.

Digital Library

[11]

Guthaus, M., Venkateswaran, N., Viswesariah, C., and Zolotov, V. 2005. Gate sizing using incremental parameterized statistical timing analysis. In Proceedings of the International Conference on Computer-Aided-Design.

Digital Library

[12]

Krishnan, G. Low-cost easypath FPGAs offer promise to ASSP companies. www.xilinx.com/ publications/xcellonline/xcell_53/xc_easyassp53.htm.

[13]

Lin, Y. and Hei, L. 2007. Stochastic physical synthesis for FPGAs with pre-routing interconnect uncertainty and process variation. In Proceedings of the International Symposium on Field Programmable Gate Arrays.

Digital Library

[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]

Moghal, H., Qian, H., Sapatnekar, S., and Bazargan, K. 2007. Clustering based pruning for statistical criticality computation under process variations. In Proceedings of the International Conference on Computer-Aided Design.

Digital Library

[17]

OpenAccess. Library core of EDA algorithms and infrastructure for openaccess. http://www. openedatools.org/projects/oagear.

[18]

Poon, K. K. W., Wilton, S. J. E., and Yan, A. 2005. A detailed power model for field-programmable gate arrays. ACM Trans. Des. Automat. Electron. Systs. 10, 2, 279--302.

Digital Library

[19]

Raj, S., Vrudhala, S., and Wang, J. 2004. A methodology to improve timing yield in the presence of process variations. In Proceedings of the Design Automation Conference.

Digital Library

[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]

Sapatnekar, S. 2004. Timing. Springer-Verlag, New York.

Digital Library

[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]

Singh, D. and Brown, S. 2002. Constrained clock shifting for field programmable gate arrays. In Proceedings of the International Symposium on Field Programmable Gate Arrays.

Digital Library

[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]

Sivaswamy, S. and Bazargan, K. 2007b. Variation-aware routing for FPGAs. In Proceedings of the International Symposium on Field Programmable Gate Arrays.

Digital Library

[26]

Tsai, J., Baik, D., Chen, C., and Saluja, K. 2004. An yield improvement methodology using pre- and post-silicon statistical clock scheduling. In Proceedings of the International Conference on Computer Aided Design.

Digital Library

[27]

Visweswariah, C., Ravindran, K., Kalafala, K., Walker, S., and Narayan, S. 2004. First-order incremental block-based statistical timing analysis. In Proceedings of the Design Automation Conference.

Digital Library

[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]

Wong, H. Y., Cheng, L., Lin, Y., and Hei, L. 2005. FPGA device and architecture evalutaion considering process variations. In Proceedings of the International Conference on Computer-Aided-Design.

Digital Library

[30]

Yeh, C.-Y. and Marek-Sadowska, M. 2005. Skew programmable clock design for FPGA and skew-aware placement. In Proceedings of the International Symposium on Field Programmable Gate Arrays.

Digital Library

Cited By

Siozios KSavidis ISoudris D(2016)A framework for exploring alternative fault-tolerant schemes targeting 3-D reconfigurable architectures2016 International Conference on Embedded Computer Systems: Architectures, Modeling and Simulation (SAMOS)10.1109/SAMOS.2016.7818369(336-341)Online publication date: Jul-2016
https://doi.org/10.1109/SAMOS.2016.7818369
Wainberg MBetz V(2015)Robust Optimization of Multiple Timing ConstraintsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2015.244031634:12(1942-1953)Online publication date: Dec-2015
https://doi.org/10.1109/TCAD.2015.2440316
Siozios KSoudris DHübner M(2014)A Framework for Supporting Adaptive Fault-Tolerant SolutionsACM Transactions on Embedded Computing Systems10.1145/262947313:5s(1-22)Online publication date: 15-Dec-2014
https://dl.acm.org/doi/10.1145/2629473
Show More Cited By

Index Terms

Statistical Analysis and Process Variation-Aware Routing and Skew Assignment for FPGAs
1. Hardware
  1. Electronic design automation
    1. Physical design (EDA)

Recommendations

Variation-aware routing for FPGAs
FPGA '07: Proceedings of the 2007 ACM/SIGDA 15th international symposium on Field programmable gate arrays

Chip design in the nanometer regime is becoming increasingly difficult due to process variations. ASIC designers have adopted statistical optimization techniques to mitigate the effects of variations. The FPGA community on the other hand, has only ...
Statistical clock skew analysis considering intradie-process variations

With shrinking cycle times, clock skew has become an increasingly difficult and important problem for high performance designs. Traditionally, clock skew has been analyzed using case-files which cannot model intradie-process variations and hence result ...
Statistical clock tree routing for robustness to process variations
ISPD '06: Proceedings of the 2006 international symposium on Physical design

Advances in VLSI technology make clock skew more susceptible to process variations. Notwithstanding efficient zero skew routing algorithms, clock skew still limits post-manufacturing performance. Process-induced skew presents an ever-growing limitation ...

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Reconfigurable Technology and Systems

ACM Transactions on Reconfigurable Technology and Systems Volume 1, Issue 1

Special edition on the 15th international symposium on FPGAs

March 2008

139 pages

ISSN:1936-7406

EISSN:1936-7414

DOI:10.1145/1331897

Issue’s Table of Contents

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 17 March 2008

Accepted: 01 December 2007

Revised: 01 October 2007

Received: 01 May 2007

Published in TRETS Volume 1, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Division of Computing and Communication Foundations

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
584
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)2

Reflects downloads up to 08 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Siozios KSavidis ISoudris D(2016)A framework for exploring alternative fault-tolerant schemes targeting 3-D reconfigurable architectures2016 International Conference on Embedded Computer Systems: Architectures, Modeling and Simulation (SAMOS)10.1109/SAMOS.2016.7818369(336-341)Online publication date: Jul-2016
https://doi.org/10.1109/SAMOS.2016.7818369
Wainberg MBetz V(2015)Robust Optimization of Multiple Timing ConstraintsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2015.244031634:12(1942-1953)Online publication date: Dec-2015
https://doi.org/10.1109/TCAD.2015.2440316
Siozios KSoudris DHübner M(2014)A Framework for Supporting Adaptive Fault-Tolerant SolutionsACM Transactions on Embedded Computing Systems10.1145/262947313:5s(1-22)Online publication date: 15-Dec-2014
https://dl.acm.org/doi/10.1145/2629473
MOHAMMADI-ARFA ZJAHANIAN A(2014)IMPROVED DELAY AND PROCESS VARIATION TOLERANT CLOCK TREE NETWORK IN ULTRA-LARGE CIRCUITS USING HYBRID RF/METAL CLOCK ROUTINGJournal of Circuits, Systems and Computers10.1142/S021812661450050923:04(1450050)Online publication date: Apr-2014
https://doi.org/10.1142/S0218126614500509
Low HShang DXia FYakovlev A(2014)Asynchronously assisted FPGA for variability2014 24th International Conference on Field Programmable Logic and Applications (FPL)10.1109/FPL.2014.6927398(1-4)Online publication date: Sep-2014
https://doi.org/10.1109/FPL.2014.6927398
Gawish EEl-Kharashi MAbu-Elyazeed M(2014)Variability-tolerant routing algorithms for Networks-on-ChipMicroprocessors & Microsystems10.1016/j.micpro.2014.08.00238:8(1037-1045)Online publication date: 1-Nov-2014
https://dl.acm.org/doi/10.1016/j.micpro.2014.08.002
Siozios KSoudris D(2012)A low-cost fault tolerant solution targeting to commercial FPGA devices2012 NASA/ESA Conference on Adaptive Hardware and Systems (AHS)10.1109/AHS.2012.6268668(46-53)Online publication date: Jun-2012
https://doi.org/10.1109/AHS.2012.6268668
Low HShang DXia FYakovlev A(2011)Variation Tolerant AFPGA ArchitectureProceedings of the 2011 17th IEEE International Symposium on Asynchronous Circuits and Systems10.1109/ASYNC.2011.17(77-86)Online publication date: 27-Apr-2011
https://dl.acm.org/doi/10.1109/ASYNC.2011.17
Lucas GDong CChen DCheung PWawrzynek J(2010)Variation-aware placement for FPGAs with multi-cycle statistical timing analysisProceedings of the 18th annual ACM/SIGDA international symposium on Field programmable gate arrays10.1145/1723112.1723143(177-180)Online publication date: 21-Feb-2010
https://dl.acm.org/doi/10.1145/1723112.1723143
Lucas GDong CChen D(2010)Variation-aware placement with multi-cycle statistical timing analysis for FPGAsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2010.205641129:11(1818-1822)Online publication date: 1-Nov-2010
https://dl.acm.org/doi/10.1109/TCAD.2010.2056411
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents