More Web Proxy on the site http://driver.im/

Article

Board-level multiterminal net assignment

Authors:

William N. N. Hung,

Alan Mishchenko,

Malgorzata Chrzanowska-Jeske,

Andrew KenningsAuthors Info & Claims

GLSVLSI '02: Proceedings of the 12th ACM Great Lakes symposium on VLSI

Pages 130 - 135

https://doi.org/10.1145/505306.505335

Published: 18 April 2002 Publication History

Abstract

The paper presents a satisfiability-based method for solving the board-level multiterminal net routing problem in Clos-Folded FPGA based logic emulation systems. The approach transforms the FPGA board-level routing task into a single, large Boolean equation with the property that any assignment of input variables that satisfies the equation specifies a valid routing. The approach considers all nets simultaneously and the absence of a satisfying assignment implies that the layout is unroutable. We use two of the fastest SAT solvers: Chaff and DLM to perform our experiments. Empirical results show that the method is time-efficient and applicable to large layout problem instances.

References

[1]

M. Khalid and J. Rose, "A Hybrid Complete-Graph Partial- Crossbar Routing Architecture for Multi-FPGA Systems," Proc. ACM Symposium on FPGAs, Feb 1998, pp. 45-54.

Digital Library

[2]

S.D.Brown,R.J.Francis,J.Rose, and Z.G. Vranesic, Field Programmable Gate Arrays, Norwell, MA: Kluwer, 1992.

Digital Library

[3]

J. Varghese, M. Butts, and J. Baatcheller, "An efficient logic emulation system," IEEE Trans. VLSI Systems, Vol. 1(2), pp. 171- 174, 1993.

Digital Library

[4]

M. Slimane-Kadi, D. Brasen, and G. Saucier, "A fast FPGA prototyping system that uses inexpensive high-performance FPIC," Proc. ACM/SIGDA Int. Workshop FPGAs, 1994.

[5]

L. Maliniak, "Multiplexing enhances hardware emulation," Electronic Design, pp. 76-78, 1992.

[6]

S. Walters, "Computer-aided prototyping for ASIC-based systems," IEEE Design Test, pp. 4-10, 1991.

Digital Library

[7]

K. Yamada, H. Nakada, A. Tsutsui, and N. Ohta, "High-speed emulation of communication circuits on a multiple-FPGA system," Proc. ACM/SIGDA Int. Workshop FPGAs, 1994.

[8]

W.K. Mak, and D.F. Wong, "Board-Level Multi-Terminal Net Routing for FPGA-based Logic Emulation," Proc. International Conference on Computer Aided Design, pp. 339-344,1995.

Digital Library

[9]

W.K. Mak and D.F. Wong, "On optimal board-level routing for FPGA-based logic emulation," IEEE Trans. CAD, Vol. 16(3), 1997.

Digital Library

[10]

S. Lin, Y. Lin, and T. Hwang, "Net Assignment for the FPGA- Based Logic Emulation System in the Folded-Clos Network Structure," IEEE Trans. CAD, Vol. 16(3), 1997.

Digital Library

[11]

W.K. Mak, and D.F. Wong, "Performance-Driven Board Level Routing for FPGA-based LOgic Emulation," Proc. International Conference on Computer Design, pp. 199-201,1998.

Digital Library

[12]

N.C. Chou, L.T. Liu, C. K. Cheng, W.J. Dai, and R. Lindelof, "Circuit Partitioning for Huge Logic Emulation Systems," Proc. ACM/IEEE Design Automation Conference, pp. 244-249,1994.

Digital Library

[13]

P.K. Chan, and M.D.F. Schlag, "Architectural Trade-offs in Field-Programmable-Device Based Computing Systems," Proc. IEEE Workshop on FPGAs for Custom Computing Machines,pp. 138-141, April 1993.

[14]

S. Devadas, "Optimal layout via Boolean Satisfiability," Proc. ACM/IEEE ICCAD, 1989, pp. 294-297.

[15]

M. Gokhale, W. Holmes, A. Kopser, S. Lucas, R. Minnich, and D. Sweely, "Building and using a highly parallel programmable logic arrays," Computer, Vol. 24., pp. 81-89, Jan. 1991.

Digital Library

[16]

P. Berlin, D. Roncin, and J. Vuillemin, "Programmable active memories: A performance assessment," Proc. 1st International Workshop on FPGAs, Feb. 1992, pp. 57-59.

[17]

M.R. Garey, and D.S. Johnson, Computers and Intractability, A guide to the Theory of NP-completeness, W.H. Freeman, 1979.

Digital Library

[18]

Gi-Joon Nam, Karem A. Sakallah and Rob. A. Rutenbar, "Satisfiability-Based Layout Revisited: Detailed Routing of Complex FPGAs Via Search-Based Boolean SAT," Proc. ACM International Symposium on FPGAs, February 1999, Monterey.

Digital Library

[19]

Gi-Joon Nam, Fadi Aloul, Karem A. Sakallah and Rob A. Rutenbar, "A Comparative Study of Two Boolean Formulations of FPGA Detailed Routing Constraints", Proc. International Symposium on Physical Design (ISPD), April 2001, Sonoma.

Digital Library

[20]

Y. Shang and B. W. Wah, "A Discrete Lagrangian-Based Global-Search Method for Solving Satisfiability Problems," Journal of Global Optimization, Kluwer, 12(1), 1998, pp. 61-99.

Digital Library

[21]

M.N. Velev, "Effective Use of Boolean Satisfiability Procedures in the Formal Verification of Superscalar and VLIW Microprocessors," Proc. ACM/IEEE Design Automation Conference, June 18-22, 2002, Las Vegas, Nevada, pp. 226-231.

Digital Library

[22]

L. Zhang, C. Madigan, M. Moskewicz, and S. Malik, "Efficient Conflict Driven Learning in a Boolean Satisfiability Solver," Proc. ACM/IEEE International Conference on Computer- Aided Design (ICCAD), San Jose, CA, November 2001.

Digital Library

[23]

A. Ejnioui and N. Ranganathan, "Multi-terminal net routing for partial crossbar-based multi-FPGA systems," Proc. ACM International Symposium on FPGA, 1999, Monterey, CA.

Digital Library

Cited By

Ramachandran DAmir E(2005)Compact propositional encoding of first-order theoriesProceedings of the 20th national conference on Artificial intelligence - Volume 110.5555/1619332.1619388(340-345)Online publication date: 9-Jul-2005
https://dl.acm.org/doi/10.5555/1619332.1619388
Hung WXiaoyu Song Coppola AKennings A(2002)On segmented channel routability2002 IEEE International Symposium on Circuits and Systems. Proceedings (Cat. No.02CH37353)10.1109/ISCAS.2002.1009804(I-169-I-172)Online publication date: 2002
https://doi.org/10.1109/ISCAS.2002.1009804

Index Terms

Board-level multiterminal net assignment
1. Hardware
  1. Electronic design automation
    1. Physical design (EDA)
      1. Placement
      2. Wire routing

Recommendations

Board-level multiterminal net assignment for the partial cross-bar architecture
Special section on the 2001 international conference on computer design (ICCD)

This paper presents a satisfiability-based method for solving the board-level multiterminal net routing problem in the digital design of clos-folded field-programmable gate array (FPGA) based logic emulation systems. The approach transforms the FPGA ...
Board-level multiterminal net routing for FPGA-based logic emulation

We consider a board-level routing problem applicable to FPGA-based logic emulation systems such as the Realizer System [Varghese et al. 1993] and the Enterprise Emulation System [Maliniak 1992] manufactured by Quickturn Design Systems. Optimal ...
Board-level multi-terminal net routing for FPGA-based logic emulation
ICCAD '95: Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design

We consider a board-level routing problem applicable to FPGA-based logic emulation systems such as the Realizer System [3] and the Enterprise Emulation System [5] manufactured by Quickturn Systems. Optimal algorithms have been proposed for the case ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GLSVLSI '02: Proceedings of the 12th ACM Great Lakes symposium on VLSI

April 2002

194 pages

ISBN:1581134622

DOI:10.1145/505306

General Chairs:
Kanad Ghose
State Univ. of New York, Binghamton
,
Patrick H. Madden
State Univ. of New York, Binghamton
,
Program Chairs:
Vivek De
Intel
,
Peter M. Kogge
Univ. of Notre Dame

Copyright © 2002 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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 18 April 2002

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

GLSVLSI02

Sponsor:

GLSVLSI02: Great Lakes Symposium on VLSI

April 18 - 19, 2002

New York, New York, USA

Acceptance Rates

Overall Acceptance Rate 312 of 1,156 submissions, 27%

Upcoming Conference

GLSVLSI '25

Sponsor:
sigda

Great Lakes Symposium on VLSI 2025

June 30 - July 2, 2025

New Orleans , LA , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
156
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 15 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Ramachandran DAmir E(2005)Compact propositional encoding of first-order theoriesProceedings of the 20th national conference on Artificial intelligence - Volume 110.5555/1619332.1619388(340-345)Online publication date: 9-Jul-2005
https://dl.acm.org/doi/10.5555/1619332.1619388
Hung WXiaoyu Song Coppola AKennings A(2002)On segmented channel routability2002 IEEE International Symposium on Circuits and Systems. Proceedings (Cat. No.02CH37353)10.1109/ISCAS.2002.1009804(I-169-I-172)Online publication date: 2002
https://doi.org/10.1109/ISCAS.2002.1009804

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 Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents