Choose-your-own-adventure routing

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Choose-your-own-adventure routing: lightweight load-time defect avoidance

Full text

Pdf (526 KB)

Source

International Symposium on Field Programmable Gate Arrays archive
Proceeding of the ACM/SIGDA international symposium on Field programmable gate arrays table of contents

Monterey, California, USA

SESSION: CAD tools 1 table of contents

Pages 23-32

Year of Publication: 2009

ISBN:978-1-60558-410-2

Authors

Raphael Rubin	University of Pennsylvania, Philadelphia, PA, USA
André DeHon	University of Pennsylvania, Philadelphia, PA, USA

Sponsors

SIGDA: ACM Special Interest Group on Design Automation
ACM: Association for Computing Machinery

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 11, Downloads (12 Months): 86, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1508128.1508133 What is a DOI?

ABSTRACT

Aggressive scaling increases the number of devices we can integrate per square millimeter but makes it increasingly difficult to guarantee that each device fabricated has the intended operational characteristics. Without careful mitigation, component yield rates will fall, potentially negating the economic benefits of scaling. The fine-grained reconfigurability inherent in FPGAs is a powerful tool that can allow us to drop the stringent requirement that every device be fabricated perfectly in order for a component to be useful. To exploit inherent FPGA reconfigurability while avoiding full CAD mapping, we propose lightweight techniques compatible with the current single bitstream model that can avoid defective devices, reducing yield loss at high defect rates. In particular, by embedding testing operations and alternative path configurations into the bitstream, each FPGA can avoid defects by making only simple, greedy decisions at bitstream load time. With 20% additional tracks above the minimum routable channel width, routes can tolerate 0.01% switch defect rates, raising yield from essentially 0% to near 100%.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	International technology roadmap for semiconductors. http://www.itrs.net/Links/2005ITRS/Home2005.htm, 2005.
	2	R. Amerson , R. Carter , W. Culbertson , P. Kuekes , G. Snider , Lyle Albertson, Plasma: an FPGA for million gate systems, Proceedings of the 1996 ACM fourth international symposium on Field-programmable gate arrays, p.10-16, February 11-13, 1996, Monterey, California, United States [doi>10.1145/228370.228372]
	3	Todd Austin , David Blaauw , Trevor Mudge , Krisztián Flautner, Making Typical Silicon Matter with Razor, Computer, v.37 n.3, p.57-65, March 2004 [doi>10.1109/MC.2004.1274005]
	4	K. Bernstein , D. J. Frank , A. E. Gattiker , W. Haensch , B. L. Ji , S. R. Nassif , E. J. Nowak , D. J. Pearson , N. J. Rohrer, High-performance CMOS variability in the 65-nm regime and beyond, IBM Journal of Research and Development, v.50 n.4/5, p.433-449, July 2006
	5	V. Betz. VPR and T-VPack: Versatile Packing, Placement and Routing for FPGAs. http://www.eecg.toronto.edu/~vaughn/vpr/vpr.html, March 27 1999. Version 4.30.
	6	V. Betz and J. Rose. FPGA Place-and-Route Challenge. http://www.eecg.toronto.edu/~vaughn/challenge/challenge.html, 1999.
	7	Shekhar Borkar, Microarchitecture and Design Challenges for Gigascale Integration, Proceedings of the 37th annual IEEE/ACM International Symposium on Microarchitecture, p.3-3, December 04-08, 2004, Portland, Oregon [doi>10.1109/MICRO.2004.24]
	8	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]
	9	N. Campregher, P. Y. K. Cheung, G. A. Constantinides, and M. Vasilko. Yield modelling and yield enhancement for FPGAs using fault tolerance schemes. In FPL, 2005.
	10	N. Campregher, P. Y. K. Cheung, G. A. Constantinides, and M. Vasilko. Reconfiguration and fine-grained redundancy for fault tolerance in FPGAs. In FPL, 2006.
	11	R. G. Cliff, R. Raman, and S. T. Reddy. Programmable logic devices with spare circuits for replacement of defects. United States Patent Number: 5,434,514, July 18 1995.
	12	W. B. Culbertson , R. Amerson , R. J. Carter , P. Kuekes , G. Snider, Defect tolerance on the Teramac custom computer, Proceedings of the 5th IEEE Symposium on FPGA-Based Custom Computing Machines, p.116, April 16-18, 1997
	13	S. Guccione, D. Levi, and P. Sundararajan. JBits: Java based interface for reconfigurable computing. In Proc. MAPLD, 1999.
	14	K. Katsuki, M. Kotani, K. Kobayashi, and H. Onodera. A yield and speed enhancement scheme under within-die variations on 90nm LUT array. In CICC, pages 601--604, 2005.
	15	John Lach , William H. Mangione-Smith , Miodrag Potkonjak, Efficiently supporting fault-tolerance in FPGAs, Proceedings of the 1998 ACM/SIGDA sixth international symposium on Field programmable gate arrays, p.105-115, February 22-25, 1998, Monterey, California, United States [doi>10.1145/275107.275125]
	16	Vijay Lakamraju , Russell Tessier, Tolerating operational faults in cluster-based FPGAs, Proceedings of the 2000 ACM/SIGDA eighth international symposium on Field programmable gate arrays, p.187-194, February 10-11, 2000, Monterey, California, United States [doi>10.1145/329166.329205]
	17	Alexander Marquardt , Vaughn Betz , Jonathan Rose, Timing-driven placement for FPGAs, Proceedings of the 2000 ACM/SIGDA eighth international symposium on Field programmable gate arrays, p.203-213, February 10-11, 2000, Monterey, California, United States [doi>10.1145/329166.329208]
	18	Yohei Matsumoto , Masakazu Hioki , Takashi Kawanami , Hanpei Koike , Toshiyuki Tsutsumi , Tadashi Nakagawa , Toshihiro Sekigawa, Suppression of Intrinsic Delay Variation in FPGAs using Multiple Configurations, ACM Transactions on Reconfigurable Technology and Systems (TRETS), v.1 n.1, p.1-31, March 2008 [doi>10.1145/1331897.1331899]
	19	C. McClintock, A. L. Lee, and R. G. Cliff. Redundancy circuitry for logic circuits. United States Patent Number: 6,034,536, March 7 2000.
	20	Larry McMurchie , Carl Ebeling, PathFinder: a negotiation-based performance-driven router for FPGAs, Proceedings of the 1995 ACM third international symposium on Field-programmable gate arrays, p.111-117, February 12-14, 1995, Monterey, California, United States [doi>10.1145/201310.201328]
	21	E. Packard. The Cave of Time. Bantam Books, 1979.
	22	Jayashree Saxena , Kenneth M. Butler , John Gatt , R Raghuraman , Sudheendra Phani Kumar , Supatra Basu , David J. Campbell , John Berech, Scan-Based Transition Fault Testing " Implementation and Low Cost Test Challenges, Proceedings of the 2002 IEEE International Test Conference, p.1120, October 07-10, 2002
	23	Pete Sedcole , Peter Y. K. Cheung, Parametric Yield Modeling and Simulations of FPGA Circuits Considering Within-Die Delay Variations, ACM Transactions on Reconfigurable Technology and Systems (TRETS), v.1 n.2, p.1-28, June 2008 [doi>10.1145/1371579.1371582]
	24	Keith So, Enforcing long-path timing closure for FPGA routing with path searches on clamped lexicographic spirals, Proceedings of the 16th international ACM/SIGDA symposium on Field programmable gate arrays, February 24-26, 2008, Monterey, California, USA [doi>10.1145/1344671.1344677]
	25	Suresh Srinivasan , Ramakrishnan Krishnan , Prasanth Mangalagiri , Yuan Xie , Vijaykrishnan Narayanan , Mary Jane Irwin , Karthik Sarpatwari, Toward Increasing FPGA Lifetime, IEEE Transactions on Dependable and Secure Computing, v.5 n.2, p.115-127, April 2008 [doi>10.1109/TDSC.2007.70235]
	26	Jordan S. Swartz , Vaughn Betz , Jonathan Rose, A fast routability-driven router for FPGAs, Proceedings of the 1998 ACM/SIGDA sixth international symposium on Field programmable gate arrays, p.140-149, February 22-25, 1998, Monterey, California, United States [doi>10.1145/275107.275134]
	27	S. M. Trimberger. Structures and methods of overcoming localized defects in programmable integrated circuits by routing during the programming thereof. United States Patent Number: 7,251,804, July 31 2007.
	28	S. M. Trimberger. Utilizing multiple test bitstreams to avoid localized defects in partially defective programmable integrated circuits. United States Patent Number: 7,424,655, September 9 2008.
	29	R. W. Wells, Z.-M. Ling, R. D. Patrie, V. L. Tong, J. Cho, and S. Toutounchi. Application-specific testing methods for programmable logic devices. United States Patent Number: 6,817,006, November 9 2004.
	30	Y.-L. Wu, S. Tsukiyama, and M. Marek-Sadowska. Graph based analysis of 2-D FPGA routing. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 15(1):33--44, January 1996.
	31	Xilinx, Inc., 2100 Logic Drive, San Jose, CA 95124. XC6200 FPGA Advanced Product Specification, version 1.0 edition, June 1996.
	32	Xilinx, Inc., 2100 Logic Drive, San Jose, CA 95124. Xilinx Virtex-II 1.5V Platform FPGAs Data Sheet, July 2002. DS031 http://www.xilinx.com/partinfo/ds031.pdf.
	33	Xilinx, Inc., 2100 Logic Drive, San Jose, CA 95124. Xilinx Virtex-4 Family Overview, June 2005. DS112 http://direct.xilinx.com/bvdocs/publications/ds112.pdf.
	34	Xilinx, Inc., 2100 Logic Drive, San Jose, CA 95124. Virtex FPGA Series Configuration and Readback, March 2005. XAPP 138 http://www.xilinx.com/bvdocs/appnotes/xapp138.pdf.
	35	Xilinx, Inc., 2100 Logic Drive, San Jose, CA 95124. Virtex-5 FPGA Configuration User Guide, September 2008. UG191 http://www.xilinx.com/bvdocs/userguides/ug191.pdf.
	36	A. J. Yu and G. G. Lemieux. Defect-tolerant FPGA switch block and connection block with fine-grain redundancy for yield enhancement. In FPL, pages 255--262, 2005.