Interconnect prediction for programmable logic devices

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Interconnect prediction for programmable logic devices

Full text

Pdf (288 KB)

Source

International Workshop on System-Level Interconnect Prediction archive
Proceedings of the 2001 international workshop on System-level interconnect prediction table of contents

Sonoma, California, United States

Pages: 125 - 131

Year of Publication: 2001

ISBN:1-58113-315-4

Author

Michael Hutton

Altera Corporation, San Jose, CA

Sponsor

SIGDA: ACM Special Interest Group on Design Automation

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 12, Citation Count: 5

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions 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/368640.368816 What is a DOI?

ABSTRACT

Classical interconnect prediction would seem to be a perfect fit for the design of programmable logic architectures (PLDs). Yet theoretical models such as those based on Rent's Rule are usually only used for rough estimates in the early stages of an architecture development. In practice, empirical methods (evaluation via many test designs) dominate the evaluation of fitting and performance for PLD architectures.The primary reasons for this gap between theory and practice are that the models are difficult to extend to fixed architectures with hierarchy and heterogeneous resources and that many of the cost metrics are different between gate-arrays and PLDs.In this paper and the accompanying talk I will survey some of the issues with line-count estimation for the design of PLDs. I will point out some of the inherent differences between the way interconnect is used in PLDs and gate arrays which lead to new opportunities in the development of the theory. Some previous results will show how interconnect is typically researched in the PLD community. For an idealized PLD architecture, I will attempt to define a simple line-count estimation model using the classical theory and compare it to results in practice. I will also present some empirical and anecdotal data useful for understanding the issues and pitfalls involved in architecture evaluation.The primary goal of this work is to motivate new directions in the theory of interconnect prediction and interconnect prediction specifically for PLDs.

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	Elias Ahmed , Jonathan Rose, The effect of LUT and cluster size on deep-submicron FPGA performance and density, Proceedings of the 2000 ACM/SIGDA eighth international symposium on Field programmable gate arrays, p.3-12, February 10-11, 2000, Monterey, California, United States [doi>10.1145/329166.329171]
	2	Altera Corp. Device Data Book, 2000.
	3	Vaughn Betz , Jonathan Rose , Alexander Marquardt, Architecture and CAD for Deep-Submicron FPGAs, Kluwer Academic Publishers, Norwell, MA, 1999
	4	V. Betz and J.S. Rose, "Effect of the Prefabricated Routing Track Distribution on FPGA Area Efficiency", IEEE Trans. VLSI, Sept 1998, pp. 445-456.
	5	B.K. Britton et. al. "Second Generation ORCA Architecture using 0.5m Process Enhances the Speed and Usable Gate Capacity of FPGAs", in Proc. IEEE Int. ASIC Conf., Sept 1994, pp. 474-478.
	6	Stephen Dean Brown, Routing algorithms and architectures for field-programmable gate arrays, 1992
	7	Stephen D. Brown , Robert J. Francis , Jonathan Rose , Zvonko G. Vranesic, Field-programmable gate arrays, Kluwer Academic Publishers, Norwell, MA, 1992
	8	A.E. Caldwell, A.B. Kahng, S. Mantik, I.L. Markov and A. Zelikovsky, "On Wirelength Estimations for Row-Based Placement", IEEE Trans. CAD 18(9), 1999. pp. 1265-1278.
	9	Pak K. Chan , Martine D. F. Schlag , Jason Y. Zien, On routability prediction for field-programmable gate arrays, Proceedings of the 30th international conference on Design automation, p.326-330, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.164915]
	10	Philip Christie , Dirk Stroobandt, The interpretation and application of Rent's rule, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.8 n.6, p.639-648, Dec. 2000 [doi>10.1109/92.902258]
	11	André DeHon, Balancing interconnect and computation in a reconfigurable computing array (or, why you don't really want 100% LUT utilization), Proceedings of the 1999 ACM/SIGDA seventh international symposium on Field programmable gate arrays, p.69-78, February 21-23, 1999, Monterey, California, United States [doi>10.1145/296399.296431]
	12	W.E. Donath. "Placement and Average Interconnection Lengths of Computer Logic." IEEE Trans. Circuits and Systems 26(4), (April, 1979) pp 272-277.
	13	A.A. El Gamal. "Two-dimensional stochastic model for interconnections in master-slice integrated circuits." IEEE Trans. On Circuits and Systems, 28(2), (Feb 1981) pp. 127- 138.
	14	M. Feuer. "Connectivity of Random Logic." IEEE Trans. Computers, 31(1), (1982), pp. 29-33.
	15	L. Hagen, A.B. Kahng, F.J. Kurdahi and C. Ramachandran. "On the Intrinsic Rent Parameter and Spectra-Based Partitioning Methodologies." IEEE Trans. CAD, 13 (1994), pp 27-37.
	16	Scott Hauck , Matthew M. Hosler , Thomas W. Fry, High-performance carry chains for FPGAs, Proceedings of the 1998 ACM/SIGDA sixth international symposium on Field programmable gate arrays, p.223-233, February 22-25, 1998, Monterey, California, United States [doi>10.1145/275107.275142]
	17	W.R. Heller, W.F. Mikhail and W.E. Donath, "Prediction of Wiring Space Requirements for LSI". Journal of Design Automation and Fault Tolerant Computing, May 1978, pp. 117-144.
	18	Frank Heile , Andrew Leaver, Hybrid product term and LUT based architectures using embedded memory blocks, Proceedings of the 1999 ACM/SIGDA seventh international symposium on Field programmable gate arrays, p.13-16, February 21-23, 1999, Monterey, California, United States [doi>10.1145/296399.296415]
	19	Michael Hutton , Khosrow Adibsamii , Andrew Leaver, Timing-driven placement for hierarchical programmable logic devices, Proceedings of the 2001 ACM/SIGDA ninth international symposium on Field programmable gate arrays, p.3-11, February 2001, Monterey, California, United States [doi>10.1145/360276.360286]
	20	M. Khalid and J. Rose. "The Effect of Fixed IO Posititioning on the Routability and Speed of FPGAs", in Proc. Canadian Workshop on Field-Programmable Devices, 1995, pp. 474-478.
	21	Sinan Kaptanoglu , Greg Bakker , Arun Kundu , Ivan Corneillet , Ben Ting, A new high density and very low cost reprogrammable FPGA architecture, Proceedings of the 1999 ACM/SIGDA seventh international symposium on Field programmable gate arrays, p.3-12, February 21-23, 1999, Monterey, California, United States [doi>10.1145/296399.296405]
	22	J. Schleicher and B. Pedersen. Personal communication.
	23	Steve Trimberger , Khue Duong , Bob Conn, Architecture issues and solutions for a high-capacity FPGA, Proceedings of the 1997 ACM fifth international symposium on Field-programmable gate arrays, p.3-9, February 09-11, 1997, Monterey, California, United States [doi>10.1145/258305.258306]
	24	Xilinx Corp. The Programmable Logic Data Book, 1996.
	25	S. Yang, "Logic Synthesis and Optimization Benchmarks User Guide", Version 3.0, Microelectronics Center of North Carolina, January 1991.

CITED BY 5

	Michael Hutton , Vinson Chan , Peter Kazarian , Victor Maruri , Tony Ngai , Jim Park , Rakesh Patel , Bruce Pedersen , Jay Schleicher , Sergey Shumarayev, Interconnect enhancements for a high-speed PLD architecture, Proceedings of the 2002 ACM/SIGDA tenth international symposium on Field-programmable gate arrays, February 24-26, 2002, Monterey, California, USA
	Joachim Pistorius , Mike Hutton, Placement rent exponent calculation methods, temporal behaviour and FPGA architecture evaluation, Proceedings of the 2003 international workshop on System-level interconnect prediction, April 05-06, 2003, Monterey, CA, USA
	Wenyi Feng , Sinan Kaptanoglu, Designing efficient input interconnect blocks for LUT clusters using counting and entropy, Proceedings of the 2007 ACM/SIGDA 15th international symposium on Field programmable gate arrays, February 18-20, 2007, Monterey, California, USA
	Wenyi Feng , Sinan Kaptanoglu, Designing Efficient Input Interconnect Blocks for LUT Clusters Using Counting and Entropy, ACM Transactions on Reconfigurable Technology and Systems (TRETS), v.1 n.1, p.1-28, March 2008
	Wu Fang , Zhang Huowen , Duan Lei , Lai Jinmei , Wang Yuan , Tong Jiarong, A delay-optimized universal FPGA routing architecture, Proceedings of the 2009 Conference on Asia and South Pacific Design Automation, January 19-22, 2009, Yokohama, Japan