[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.1145/258305.258311acmconferencesArticle/Chapter ViewAbstractPublication PagesfpgaConference Proceedingsconference-collections
Article
Free access

General modeling and technology-mapping technique for LUT-based FPGAs

Published: 09 February 1997 Publication History

Abstract

We present a general approach to the FPGA technology mapping problem that applies to any logic block composed of lookup tables (LUTs) and can yield optimal solutions. The connections between LUTs of a logic block are modeled by virtual switches, which define a set of multiple-LUT blocks (MLBs) called an MLB-basis. We identify the MLB-bases for various commercial logic blocks. Given a n MLB-basis, we formulate FPGA mapping as a mixed integer linear programming (MILP) problem to achieve both the generality and the optimality objectives. We solve the MILP models using a general-purpose MILP solver, and present the results of mapping some ISCAS.85 benchmark circuits with a variety of commercial FPGAs. Circuits of a few hundred gates can be mapped in reasonable time using the MILP approach directly. Larger circuits can be handled by partitioning them prior to technology mapping. We show that optimal or provably near-optimal solutions can be obtained for the large ISCAS.85 benchmark circuits using partitions defined by their high-level functions.

References

[1]
Altera Inc. The Altera FPGA Data Book, Sunnyvale, CaliL, 1993.
[2]
AT&T Inc. The AT~4T FPGA Data Book, Allentown, Pa., 1995.
[3]
P. Barth. Logic Based 0-1 Constraint Programming. Kluwer, Boston, 1995.
[4]
A. Chowdhary and J. P. Hayes. Technology mapping for fieldprogrammable gate arrays using integer programming. Proc. Int'l Conj. on CAD, pp. 346-352, 1995.
[5]
J. Cong and Y. Ding. FlowMap: An Optimal Technology Mapping Algorithm for Delay Optimization in Lookup-Table Based FPGA Designs. IEEE Trans. on CAD, 13(1):1-11, Jan. 1994.
[6]
CPLEX Optimization Inc. CPLEX documentation, 1990.
[7]
E. Detjens et ak Technology mapping in MIS. Proc. Int'l Conf. on CAD, pp. 116-119, 1987.
[8]
R. J. Francis, J. Rose, and Z. Vranesic. Chortle-crf: Fast technology mapping for lookup table based field programmable gate arrays. Proc. 28th Design Automation Conf., pp. 613- 619, 1991.
[9]
M.C. Hausen and J. P. Hayes. High-level test generation using physically-induced faults. Proc. of VLSI Test Symposium, pp. 20--28,1995.
[10]
A. Sangiovanni-Vincentelli, A. El Carnal, and J. Rose. Synthesis methods for field programmable gate arrays. Proc. of IEEE, pp. 1057-1083, July 1993.
[11]
XiHnx Inc. The Programmable Logic Data Book, Santa Clara, Calif., 1994.

Cited By

View all
  • (2006)Boolean matching for LUT-based logic blocks with applications to architecture evaluation and technology mappingIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/43.94530320:9(1077-1090)Online publication date: 1-Nov-2006
  • (1999)An exact tree-based structural technology mapping algorithm for configurable logic blocks in FPGAsProceedings 1999 IEEE International Conference on Computer Design: VLSI in Computers and Processors (Cat. No.99CB37040)10.1109/ICCD.1999.808428(216-221)Online publication date: 1999
  • (1999)Unveiling the ISCAS-85 BenchmarksIEEE Design & Test10.1109/54.78583816:3(72-80)Online publication date: 1-Jul-1999

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences
FPGA '97: Proceedings of the 1997 ACM fifth international symposium on Field-programmable gate arrays
February 1997
174 pages
ISBN:0897918010
DOI:10.1145/258305
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: 09 February 1997

Permissions

Request permissions for this article.

Check for updates

Qualifiers

  • Article

Conference

FPGA97
Sponsor:

Acceptance Rates

Overall Acceptance Rate 125 of 627 submissions, 20%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)74
  • Downloads (Last 6 weeks)7
Reflects downloads up to 18 Dec 2024

Other Metrics

Citations

Cited By

View all
  • (2006)Boolean matching for LUT-based logic blocks with applications to architecture evaluation and technology mappingIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/43.94530320:9(1077-1090)Online publication date: 1-Nov-2006
  • (1999)An exact tree-based structural technology mapping algorithm for configurable logic blocks in FPGAsProceedings 1999 IEEE International Conference on Computer Design: VLSI in Computers and Processors (Cat. No.99CB37040)10.1109/ICCD.1999.808428(216-221)Online publication date: 1999
  • (1999)Unveiling the ISCAS-85 BenchmarksIEEE Design & Test10.1109/54.78583816:3(72-80)Online publication date: 1-Jul-1999

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media