Article

Free access

A new retiming-based technology mapping algorithm for LUT-based FPGAs

Authors:

Chih-Chang LinAuthors Info & Claims

FPGA '98: Proceedings of the 1998 ACM/SIGDA sixth international symposium on Field programmable gate arrays

Pages 35 - 42

https://doi.org/10.1145/275107.275118

Published: 01 March 1998 Publication History

Abstract

In this paper, w e presen t a new retiming-based technology mapping algorithm for look-up table-based field programmable gate arrays. The algorithm is based on a novel iterative procedure for computing all k-cuts of all nodes in a sequen tialcircuit, in the presence of retiming. The algorithm completely avoids flow computation whic his the bottleneck of previous algorithms. Due to the fact that k is very small in practice, the procedure for computing all k-cuts is v ery fast. Experimental results indicate the overall algorithm is very efficient in practice.

References

[1]

Altera. Data Book Altera, San Jose, CA, 1995.

[2]

N. Bhat and D. Hill. Routable technology mapping for FPGAs. ~ A CM/SIGDA ~~~ on ~~s, p~ 143-148, 1992.

[3]

3. ~ong ~d Y. D~g. ~M~: An ~gm~ te~n~o~ mapping ~goHthm ~r d~ ~~z~~ ~ lo~u~ tab~ b~ed FPGA d~i~s. ~ ~ns. on ~~e~ Aid~ Des~ 13:1-11, 1994.

[4]

3. Cong ~d ~ Din~ On ~e~de~h t~d~off ~ ~~ b~ed FPGA te~n~o~ m~p~ ~ ~~. on ~~ ~tem~ 2:13~148, 1994.

[5]

3. C~g ~d Y.-~ ~g. P~~~p~~ ~ tion~ d~ompo~t~n ~th ~~~ ~ FPGA ~ th~ ~d m~p~g. In A CM/SIGDA ~~. on ~eld ~m~ab~ Gate A~y~ 1997.

Digital Library

[6]

J. C~g ~d C. ~. An i~r~d ~~t~ ~ p~ ~~ce ~m~ te&n~o~ m~~g ~ ~t~g ~ ~~~ed FPGA d~. ~ ~c. ~ ~~ on ~mpurer Des~ pag~ 572-578, 1996.

[7]

3. Cong ~d G. ~. P~~~&~n FPGA ~h~ s~ ~th r~i~ng ~d p~~ng ~r se~e~i~ c~cu~s. ~ ~c. A~ D~n A~om~n ~~, 199Z

[8]

A. H. ~~ ~d M. S~~~. C~l~ ~ ~ ~u~t~ m~im~ion p~em ~r FPGA te~do~ m~p~g. ~ ~~. on ~~~A~d D~~ 13:1~I~2, 1994. -

[9]

R. ~. ~c~, ~. ~se, ~d K. C~g. Cho~: A te~~ m~p~g ~r ~okup ~~b~ed fidd pr~ ~~m~e g~e ~~. ~ ~c. A~ D~n A~om~n ~~, pag~ 613~619i 1990.

Digital Library

[10]

R. J. ~c~, J. ~se, ~d Z. %~~. ~~I~ ~t te~n~o~ m~p~g ~r ~up t~~~ed F~ GAs. ~ ~c. A~ D~n A u~m~n ~, p~ 22~233, 1991.

Digital Library

[11]

R. 3. ~c~, 3. ~se, ~d Z.~~~. ~~oN o~ m~ng ~r ~o~p t~l~b~ed FPGAs ~r p~~ m~ce. In D~est ~ ~ ~tL ~~ on ~~ut~ Aided D~n, pa~ 568-571, 1991.

[12]

K. K~~. Xm~: A te~n~o~m~p~ ~r t~l~ ~o~p FPGAs. ~ ~c. A~ D~n Autom~ t~on ~~, pag~ ~~3, 1991.

Digital Library

[13]

C. E. L~~~ ~d 3. B. S~e. ~t~ng ~n~~o~ ~c~t~ A~~hm~, 6:5~5, 1991.

[14]

A. M~~ ~d C. L. L~. ~~rm~ ~i~n te~N o~ m~p~g ~r ~u~~e b~ed FPG~ ~g ~e gener~ d~ mode. In A GM/SIGDA ~~h~ on ~eld ~~mab~ Gate A~y~ 1994.

[15]

~&T Mi~o~~o~. A~T ~~~~m~ Gate A~~ Data Boo~ ~&T Mi~o~~o~, 1995.

[16]

R. M~, R.K. ~~~, ~d A. S~~N ~~t~i. Se~~ ~h~ ~r t~le lo~ up ~ ~~m~e g~e ~~s. ~ ~c. A~ D~n Autom~n ~~, pag~ 22~29, 1993.

Digital Library

[17]

R. Murg~, Y. Nishizaki, N. Shenoy, R.K. Brayton, and A. San~ovanni-Vincentelli. Lo~c synth~is ~gofithms ~r table look up pro~ammable gate ~rays. In P~c. A CM/IBBE Des~n A~om~n Conf., pages 620-625, 1990.

Digital Library

[18]

~ Pan. Continuous ~tim~ ~gofithms and ap~N c~ns. In IntL Conf. on Computer Des~n ~CCD), pag~ 116-121, 199L

[19]

L Pan and C. L. Liu. Op~m~ dock period FPGA technMogy mapp~g ~r sequenfi~ ekeu~s. In A GM/1BEE Desert A~om~n Conf. (DA G), pag~ 720-725, 1996.

Digital Library

[20]

~ Pan and C. L. Liu. Techndogy mapping of sequenti~ ckcu~s ~r LUT-b~ed FPGAs ~r performance. In A GM/SIGDA IntL Sympos~m on Fiel$Programmab~ Gate A~a~, pag~ 58-64, 1996.

Digital Library

[21]

~ Pan and C.L. Liu. Optim~ dock p~iod FPGA teehndogy reaping for sequenti~ eirc~ts with retiming. A GM Trans. on D~n AuWm~n of El~twn~ System~ ~o appear).

Digital Library

[22]

~ Sawkar and D. Thom~. Area and dday mapping for tabl~look-up b~ed fidd pro~ammable gate arrays. In Proc. ACId/IEEE Des~n A~om~n Conf., pages 368-373, 1992.,

Digital Library

[23]

E Sawkar and D. Thom~. P~rmance dire~ed techn~ogy mapp~g ~r lookup table b~ed FPGAs. In Proc. A CM/IEEE D~n Au~m~n Conf., pages 208-212, 1993.

Digital Library

[24]

M. Schla~ J. Kon~ and EK. Chan. RoutabiHty-driven techn~ogy mapp~g ~r lookup tabl~b~ed FPGA~. IEEE Trans. on Compute~Aided Des~ 13:13-26, 1994.

[25]

U. We~mann and W. R~ns~. Techn~ogy mapping ~r sequentiM c~c&ts b~ed on ~fiming tech~qu~, in Proc. Europ~n Des~n A~om~n Conf., pages 318- 323, 1993.

[26]

N.-S. Woo. A heur~fiC m~hod ~r FPGA technoN ogy mapp~g b~ed on .the edge ~sibility. In Proc. ACM/IEEE D~n Au~m~n Conf., pag~ 248-251, 1991.

Digital Library

[27]

XiHn.x. The Prog~mmable Gate A~a~ Data Book. XiN lax, San Jose, CA, 1993.

[28]

H. Yang and D. F. Wong. Edg~Map: Optim~ pe~ ~rmance driven techndogy mapp~g ~r it~ive LUT b~ed FPGA deigns. In D~t IEEE/A CM IntL Conf. on Compeer-Aided D~n, pag~ 150--155, 1994.

Digital Library

Cited By

Konrad AScholl CMahzoon AGroße DDrechsler R(2024)Divider verification using symbolic computer algebra and delayed don’t care optimization: theory and practical implementationFormal Methods in System Design10.1007/s10703-024-00452-3Online publication date: 24-May-2024
https://doi.org/10.1007/s10703-024-00452-3
Barzen BReais-Parsi AHung EKang MMishchenko AGreene JWawrzynek J(2023)Narrowing the Synthesis Gap: Academic FPGA Synthesis is Catching Up With the Industry2023 Design, Automation & Test in Europe Conference & Exhibition (DATE)10.23919/DATE56975.2023.10137310(1-6)Online publication date: Apr-2023
https://doi.org/10.23919/DATE56975.2023.10137310
GE XKIMURA S(2023)Theory and Application of Topology-Based Exact Synthesis for Majority-Inverter GraphsIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences10.1587/transfun.2022EAP1103E106.A:9(1241-1250)Online publication date: 1-Sep-2023
https://doi.org/10.1587/transfun.2022EAP1103
Show More Cited By

Index Terms

A new retiming-based technology mapping algorithm for LUT-based FPGAs

Recommendations

Improvements to technology mapping for LUT-based FPGAs
FPGA '06: Proceedings of the 2006 ACM/SIGDA 14th international symposium on Field programmable gate arrays

The paper presents several improvements to state-of-the-art in FPGA technology mapping exemplified by a recent advanced technology mapper DAOmap [Chen and Cong, ICCAD '04]. Improved cut enumeration computes all K-feasible cuts without pruning for up to ...
Placement-driven technology mapping for LUT-based FPGAs
FPGA '03: Proceedings of the 2003 ACM/SIGDA eleventh international symposium on Field programmable gate arrays

In this paper, we study the problem of placement-driven technology mapping for table-lookup based FPGA architectures to optimize circuit performance. Early work on technology mapping for FPGAs such as Chortle-d[14] and Flowmap[3] aim to optimize the ...
Complexity issues and algorithms for LUT-based FPGA technology mapping

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

FPGA '98: Proceedings of the 1998 ACM/SIGDA sixth international symposium on Field programmable gate arrays

March 1998

262 pages

ISBN:0897919785

DOI:10.1145/275107

Chairmen:
Jason Cong
Univ. of California, Los Angeles
,
Sinan Kaptanoglu
Actel Corp.

Copyright © 1998 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

SIGDA: ACM Special Interest Group on Design Automation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 March 1998

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

FPGA98

Sponsor:

SIGDA

FPGA98: 1998 International Symposium on Field Programmable Gate Arrays

February 22 - 25, 1998

California, Monterey, USA

Acceptance Rates

Overall Acceptance Rate 125 of 627 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

73
Total Citations
View Citations
1,338
Total Downloads

Downloads (Last 12 months)140
Downloads (Last 6 weeks)17

Reflects downloads up to 17 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Konrad AScholl CMahzoon AGroße DDrechsler R(2024)Divider verification using symbolic computer algebra and delayed don’t care optimization: theory and practical implementationFormal Methods in System Design10.1007/s10703-024-00452-3Online publication date: 24-May-2024
https://doi.org/10.1007/s10703-024-00452-3
Barzen BReais-Parsi AHung EKang MMishchenko AGreene JWawrzynek J(2023)Narrowing the Synthesis Gap: Academic FPGA Synthesis is Catching Up With the Industry2023 Design, Automation & Test in Europe Conference & Exhibition (DATE)10.23919/DATE56975.2023.10137310(1-6)Online publication date: Apr-2023
https://doi.org/10.23919/DATE56975.2023.10137310
GE XKIMURA S(2023)Theory and Application of Topology-Based Exact Synthesis for Majority-Inverter GraphsIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences10.1587/transfun.2022EAP1103E106.A:9(1241-1250)Online publication date: 1-Sep-2023
https://doi.org/10.1587/transfun.2022EAP1103
Calvino ADe Micheli G(2023)Technology Mapping Using Multi-Output Library Cells2023 IEEE/ACM International Conference on Computer Aided Design (ICCAD)10.1109/ICCAD57390.2023.10323999(1-9)Online publication date: 28-Oct-2023
https://doi.org/10.1109/ICCAD57390.2023.10323999
Wang HRizzi CJosipović L(2023)MapBuf: Simultaneous Technology Mapping and Buffer Insertion for HLS Performance Optimization2023 IEEE/ACM International Conference on Computer Aided Design (ICCAD)10.1109/ICCAD57390.2023.10323639(1-9)Online publication date: 28-Oct-2023
https://doi.org/10.1109/ICCAD57390.2023.10323639
Calvino AMishchenko ASchmit HMahintorabi EMicheli GXu X(2023)Improving Standard-Cell Design Flow using Factored Form Optimization2023 60th ACM/IEEE Design Automation Conference (DAC)10.1109/DAC56929.2023.10247905(1-6)Online publication date: 9-Jul-2023
https://doi.org/10.1109/DAC56929.2023.10247905
Mahzoon AGroße DDrechsler RMahzoon AGroße DDrechsler R(2023)BackgroundFormal Verification of Structurally Complex Multipliers10.1007/978-3-031-24571-8_2(9-28)Online publication date: 15-Feb-2023
https://doi.org/10.1007/978-3-031-24571-8_2
Mahzoon AGroBe DDrechsler R(2022)RevSCA-2.0: SCA-Based Formal Verification of Nontrivial Multipliers Using Reverse Engineering and Local Vanishing RemovalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2021.308368241:5(1573-1586)Online publication date: May-2022
https://doi.org/10.1109/TCAD.2021.3083682
Mahzoon AGroße DDrechsler RMahzoon AGroße DDrechsler R(2022)SCA-Based Verifier RevSCA-2.0Formal Verification of Structurally Complex Multipliers10.1007/978-3-031-24571-8_7(75-99)Online publication date: 20-Dec-2022
https://doi.org/10.1007/978-3-031-24571-8_7
Amaru LPossani VTesta EMarranghello FCasares CLuo JVuillod PMishchenko ADe Micheli G(2021)LUT-Based Optimization For ASIC Design Flow2021 58th ACM/IEEE Design Automation Conference (DAC)10.1109/DAC18074.2021.9586132(871-876)Online publication date: 5-Dec-2021
https://doi.org/10.1109/DAC18074.2021.9586132
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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

Media

Figures

Other

Tables

View Table of Contents