A negative reinforcement method for PGA routing

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A negative reinforcement method for PGA routing

Full text

Pdf (614 KB)

Source

Annual ACM IEEE Design Automation Conference archive
Proceedings of the 30th international Design Automation Conference table of contents

Dallas, Texas, United States

Pages: 601 - 605

Year of Publication: 1993

ISBN:0-89791-577-1

Authors

F. D. Lewis
Wang Chia-Chi Pong

Sponsors

EDAC : Electronic Design Automation Consortium
IEEE-CAS : Circuits & Systems
SIGDA: ACM Special Interest Group on Design Automation

Publisher

ACM New York, NY, USA

Bibliometrics

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

Additional Information:

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/157485.165064 What is a DOI?

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	G. D. Adams , C. H. Séquin, Template style considerations for sea-of-gates layout generation, Proceedings of the 26th ACM/IEEE conference on Design automation, p.31-36, June 25-28, 1989, Las Vegas, Nevada, United States [doi>10.1145/74382.74389]
	2	Marshall Bern , Marcio de Carvalho, A Greedy Heuristic for the Rectilinear Steiner Tree Problem, University of California at Berkeley, Berkeley, CA, 1986
	3	Stephen D. Brown , Robert J. Francis , Jonathan Rose , Zvonko G. Vranesic, Field-programmable gate arrays, Kluwer Academic Publishers, Norwell, MA, 1992
	4	Brown, S. D., Rose, L, and Vranesic, Z.G. "A Detailed Router for Field. Programmable Crate Arrays." Proc. ~ICCAD, 1990, 382-385.
	5	Atreyi Chakraverti , Moon Jung Chung, Routing algorithm for gate array macro cells, Proceedings of the 25th ACM/IEEE conference on Design automation, p.658-662, June 12-15, 1988, Atlantic City, New Jersey, United States
	6	Chiang, C., Sarrafzadeh, M., and Wang, C. K. "A Powerful Global Router Based on Steiner Min-Max Trees," Proc. ~ ICCAD, 1989, 2- 5.
	7	Garey, M.R, and Johnson, D.S. "The Rectilinear ~ Problem is NP- Con~lete." SIAMd. AppL Math., voL 32, 1977, 826-834.
	8	Hamn, M. "On Steinees Problem with Rectilinear Distance."SIAM J. Appl.Math., voL 14, no. 2, 1966, 255-265.
	9	Hwang, F. K. "On Steiner Minimal Trees with Rectilinear Distatme." SIAMd. Appl. Math., vol. 30, 1976, 104-114.
	10	Hwang, 1;'. K., Ridmtds, D. S~ and Winter, P. The Steiner Tree Problem. Annals of Discrete Mathematwa, no. 53, North itolland, 1992.
	11	KmskaL J. B. "On the Shortest Spanning Subtree of a C_naOt and the Traveling Salesman Problenx" Proc. oftheAMS, vol. 7, 1956, 48-50.
	12	Lee, C. Y. "An Algorithm for Path Connections aad Its Applic,,~dons." 1RE Trans. on Electromc Computers, vol. EC-10, Sept 1961, 346-365.
	13	Lee, J. H., Bose, N. I~, and Hwang F.K. "Use of Steiner's Problem in Suboptimal Routing in Rectilinear Metric." ~ Trans. on Circuits Syst., vol. CAS-23, I976, 470-476.
	14	Forbes D. Lewis , N. Van Cleave, Correct and Provably Efficient Methods for Rectilinear Steiner Spanning Tree Generation, Proceedings of the The First Great Lakes Computer Science Conference on Computing in the 90's, p.329-335, October 18-20, 1989
	15	Nair, It. "A Simple Yet Effective Technique for Global Wiring." IF~E Trans. on CAD, vol. CAD-6, no. 2, Mm~ 1987, 165-172.
	16	Antony P.-C Ng , Clark D. Thompson , Prabhakar Raghavan, A language for describing rectilinear Steiner tree configurations, Proceedings of the 23rd ACM/IEEE conference on Design automation, p.659-662, July 1986, Las Vegas, Nevada, United States
	17	R. Okuda , S. Oguri, An efficient routing algorithm for SOG cell generation on a dense gate-isolated layout style, Proceedings of the 29th ACM/IEEE conference on Design automation, p.676-681, June 08-12, 1992, Anaheim, California, United States
	18	M. Palczewski, Plane parallel a maze router and its application to FPGAs, Proceedings of the 29th ACM/IEEE conference on Design automation, p.691-697, June 08-12, 1992, Anaheim, California, United States
	19	Wang Chia-Chi Pong, Steiner trees and CAD algorithms for VLSI systems, University of Kentucky, Lexington, KY, 1993
	20	Raghavan, P., and Thomson, C. D. "Multitenninal Global Routing: A Deterministic Approximation Scheme". Algorithmica, vol. 6, 11991, 73- 82.
	21	Rezende, P. J., Lee, D. T., and Wu, Y. F. "Rectilinear Shortest Paths in the Presetx~ of Rectangular Barriers," Discrete & Comput. Geom., vol. 4, 1989, 41-53.
	22	Rose, J. aad Brown, S. "The Effect of Switch Box Flexibility on Routability of Field Programmable Gate Arrays," Proc. 1990 CICC, 1990, 27.5.1-27.5.4.
	23	Rose, J. and Brown, S. "Flexibility of Interconnection Structures in Field-Programmable Crate Arrays." ~ d. of Solid State Circ., voL 26, no. 3, March 1991, 277-282.
	24	Rowsoit, J. and Trimberger, S. "Gate Array Macro Layout AmomafiorL" Proc. 1986 ~ ICCAD, 1986, 448-451.
	25	Shin, H. and 8angiovanni-V~Ui, A. "A Detailed Router Based on Ineremem~ Routing Modifumtiom: MJshty." IF, F,E Trans. on CAD, vol. CAD-6, no. 6, November 1987, 942-955.
	26	Suzuki, K., Matmtmga, Y., Tachilmm, M. and ~, T. "A Hardware Maze Router with Application to Intera~ve Rip-Up and Reroute," tEEE Trans. on CAD, vol. CAD-5, no. 4, ~ 1986, 466-476.
	27	Tzeng, P. and S&luin, C. H. "Codar: A Congestion-DireOed General Area Router." Pro~. of 1988 I~ST_.EICCAD, 1988, 30-33.
	28	Yang~ Y. Y. and Wing, O. "On a Multinet Wiring Problenx" IEEE Trans. Circuit Theory, vol. CT-20, 1973, 250-252.
	29	Ying-Fung Wu , Peter Widmayer , Martine D. F. Schlag , C. K. Wong, Rectilinear shortest paths and minimum spanning trees in the presence of rectilinear obstacles, IEEE Transactions on Computers, v.36 n.3, p.321-331, March 1987 [doi>10.1109/TC.1987.1676904]

CITED BY 5

	Michael J. Alexander , James P. Cohoon , Joseph L. Ganley , Gabriel Robins, An architecture-independent approach to FPGA routing based on multi-weighted graphs, Proceedings of the conference on European design automation, p.259-264, September 19-23, 1994, Grenoble, France
	Yuh-sheng Lee , Allen C.-H. Wu, A performance and routablity driven router for FPGAs considering path delays, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.557-561, June 12-16, 1995, San Francisco, California, United States
	Nak-Woong Eum , Taewhan Kim , Chong-Min Kyung, An accurate evaluation of routing density for symmetrical FPGAs, Proceedings of the 11th Great Lakes symposium on VLSI, p.51-55, March 2001, West Lafayette, Indiana, United States
	Nak Woong Eum , Taewhan Kim , Chong Min Kyung, A router for symmetrical FPGAs based on exact routing density evaluation, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
	CeRA: A Router for Symmetrical FPGAs Based on Exact Routing Density Evaluation, IEEE Transactions on Computers, v.53 n.7, p.829-842, July 2004