ACM Portal
  Subscribe (Full Service)    Register (Limited Service, Free)    Login
  Search:   The ACM Digital Library   The Guide
  
ACM Home Page
Please provide us with feedback. Feedback
Chortle-crf: Fast technology mapping for lookup table-based FPGAs
Full text PdfPdf (642 KB)
Source Annual ACM IEEE Design Automation Conference archive
Proceedings of the 28th ACM/IEEE Design Automation Conference table of contents
San Francisco, California, United States
Pages: 227 - 233  
Year of Publication: 1991
ISBN:0-89791-395-7
Authors
Robert Francis  Department of Electrical Engineering, University of Toronto, Canada
Jonathan Rose  Department of Electrical Engineering, University of Toronto, Canada
Zvonko Vranesic  Department of Electrical Engineering, University of Toronto, Canada
Sponsors
SIGDA: ACM Special Interest Group on Design Automation
IEEE-CS : Computer Society
Publisher
ACM  New York, NY, USA
Bibliometrics
Downloads (6 Weeks): 4,   Downloads (12 Months): 35,   Citation Count: 62
Additional Information:

references   cited by   index terms   collaborative colleagues  

Tools and Actions: Request Permissions Request Permissions    Review this Article  
DOI Bookmark: Use this link to bookmark this Article: http://doi.acm.org/10.1145/127601.127670
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.

 
Ahre90
M. Ahrens, et al., "An FPGA Family Optimized for High Densities and Reduced Routing Delay," Proc. 1990 CICC, May 1990, pp. 31.5.1-31.5.4.
 
Bray86
R. Brayton, et al., "Multiple-Level Logic Optimization System," Proc. IGCAD, Nov. 1986, pp. 356- 359.
 
Cart86
W. Carter et al., "A user Progranu~able reconfigurablc gate array," Proc. CICC, May 1986, pp 233- 235.
 
Detj87
E.Detjens et. al, "Technology Mapping in MIS", Proc. ICCAD 87, Nov 1987, pp. 116-119.
Fran90
Robert J. Francis , Jonathan Rose , Kevin Chung, Chortle: a technology mapping program for lookup table-based field programmable gate arrays, Proceedings of the 27th ACM/IEEE conference on Design automation, p.613-619, June 24-27, 1990, Orlando, Florida, United States  [doi>10.1145/123186.123418]
 
Fran91
R.J. Francis, "Technology Mapping for Lookup Table-Based FPGAs," Ph.D. Thesis in preparation, University of Toronto, Department of Electrical Engineering.
 
Gare79
Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
 
Gibb85
A. Gibbons, "Algorithmic Graph Theory," Cambridge University Press, 1985, pp. 125-133.
 
Greg86
David Gregory , Karen Bartlett , Aart de Geus , Gary Hachtel, SOCRATES: a system for automatically synthesizing and optimizing combinational logic, Proceedings of the 23rd ACM/IEEE conference on Design automation, p.79-85, July 1986, Las Vegas, Nevada, United States
 
Hsie88
H. Hsieh, et al., "A 9000-Gate User-Programmable Gate Array," Proc. 1988 CICC, May 1988, pp. 15.3.1 - 15.3.7.
 
Kahr86
M. Kahrs, "Matching a parts library in a silicon compiler," IEEE ICCAD, 1986, pp. 169-172.
Keut87
K. Keutzer, DAGON: technology binding and local optimization by DAG matching, Proceedings of the 24th ACM/IEEE conference on Design automation, p.341-347, June 28-July 01, 1987, Miami Beach, Florida, United States  [doi>10.1145/37888.37940]
 
Lisa87
R. Lisanke, F. Brglez, G. Kedem, "McMAP: A Fast Technology Mapping Procedure for Multi-Level Logic Synthesis," Proc. ICCD, Oct. 1988, pp. 252- 256.
Murg90a
Rajeev Murgai , Yoshihito Nishizaki , Narendra Shenoy , Robert K. Brayton , Alberto Sangiovanni-Vincentelli, Logic synthesis for programmable gate arrays, Proceedings of the 27th ACM/IEEE conference on Design automation, p.620-625, June 24-27, 1990, Orlando, Florida, United States  [doi>10.1145/123186.123421]
 
Murg90b
R. Murgai, private correspondence.
 
Rose90
J. Rose, R. J. Francis, D. Lewis, P. Chow, "Architectures of Field-Programmable Gate Arrays: The effect of Logic Block Functionality of Area Efficiency," IEEE Journal of Solid-State Circuits, Vol. 25, No. 5, Oct. 1990, pp. 1217-1225.
 
Xili89
XACT LCA Development System, Vol. Ii, Xilinx Inc., 1989.

CITED BY  62
Amit Chowdhary , John P. Hayes, Technology mapping for field-programmable gate arrays using integer programming, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.346-352, November 05-09, 1995, San Jose, California, United States
Jason Cong , Yuzheng Ding, Beyond the combinatorial limit in depth minimization for LUT-based FPGA designs, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.110-114, November 07-11, 1993, Santa Clara, California, United States
Chi-Chou Kao , Yen-Tai Lai, An efficient algorithm for finding the minimal-area FPGA technology mapping, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.10 n.1, p.168-186, January 2005
Jason Cong , Yuzheng Ding, An optimal technology mapping algorithm for delay optimization in lookup-table based FPGA designs, Proceedings of the 1992 IEEE/ACM international conference on Computer-aided design, p.48-53, November 1992, Santa Clara, California, United States
Yung-Te Lai , Massoud Pedram , Sarma B. K. Vrudhula, BDD based decomposition of logic functions with application to FPGA synthesis, Proceedings of the 30th international conference on Design automation, p.642-647, June 14-18, 1993, Dallas, Texas, United States
Jason Cong , Yuzheng Ding, An optimal technology mapping algorithm for delay optimization in lookup-table based FPGA designs, Proceedings of the 1992 IEEE/ACM international conference on Computer-aided design, p.48-53, November 1992, Santa Clara, California, United States
Hiroshi Sawada , Takayuki Suyama , Akira Nagoya, Logic synthesis for look-up table based FPGAs using functional decomposition and support minimization, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.353-358, November 05-09, 1995, San Jose, California, United States
Rajeev Murgai , Robert K. Brayton , Albert Sangiovanni-Vincentelli, Sequential synthesis for table look up programmable gate arrays, Proceedings of the 30th international conference on Design automation, p.224-229, June 14-18, 1993, Dallas, Texas, United States
P. Sawkar , D. Thomas, Area and delay mapping for table-look-up based field programmable gate arrays, Proceedings of the 29th ACM/IEEE conference on Design automation, p.368-373, June 08-12, 1992, Anaheim, California, United States
K. Chung , J. Rose, TEMPT: technology mapping for the exploration of FPGA architectures with hard-wired connections, Proceedings of the 29th ACM/IEEE conference on Design automation, p.361-367, June 08-12, 1992, Anaheim, California, United States
Jason Cong , Hui Huang, Depth optimal incremental mapping for field programmable gate arrays, Proceedings of the 37th conference on Design automation, p.290-293, June 05-09, 2000, Los Angeles, California, United States
Jason Cong , Yuzheng Ding, On nominal delay minimization in LUT-based FPGA technology mapping, Proceedings of the 1995 ACM third international symposium on Field-programmable gate arrays, p.82-88, February 12-14, 1995, Monterey, California, United States
Jason Cong , Yuzheng Ding, On area/depth trade-off in LUT-based FPGA technology mapping, Proceedings of the 30th international conference on Design automation, p.213-218, June 14-18, 1993, Dallas, Texas, United States
Shih-Chieh Chang , Kwang-Ting Cheng , Nam-Sung Woo , Malgorzata Marek-Sadowska, Layout driven logic synthesis for FPGAs, Proceedings of the 31st annual conference on Design automation, p.308-313, June 06-10, 1994, San Diego, California, United States
Jae-Jin Kim , Hi-Seok Kim , Chi-Ho Lin, A new techology mapping for CPLD under the time constraint, Proceedings of the 2001 conference on Asia South Pacific design automation, p.235-238, January 2001, Yokohama, Japan
Deming Chen , Jason Cong , Milos D. Ercegovac , Zhijun Huang, Performance-driven mapping for CPLD architectures, Proceedings of the 2001 ACM/SIGDA ninth international symposium on Field programmable gate arrays, p.39-47, February 2001, Monterey, California, United States
Jason Cong , Songjie Xu, Technology mapping for FPGAs with embedded memory blocks, Proceedings of the 1998 ACM/SIGDA sixth international symposium on Field programmable gate arrays, p.179-188, February 22-25, 1998, Monterey, California, United States
Zhi-Hong Wang , En-Cheng Liu , Jianbang Lai , Ting-Chi Wang, Power minization in LUT-based FPGA technology mapping, Proceedings of the 2001 conference on Asia South Pacific design automation, p.635-640, January 2001, Yokohama, Japan
Jason Helge Anderson , Stephen Dean Brown, Technology mapping for large complex PLDs, Proceedings of the 35th annual conference on Design automation, p.698-703, June 15-19, 1998, San Francisco, California, United States
Wen-Zen Shen , Juinn-Dar Huang , Shih-Min Chao, Lambda set selection in Roth-Karp decomposition for LUT-based FPGA technology mapping, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.65-69, June 12-16, 1995, San Francisco, California, United States
Peichen Pan , Chih-Chang Lin, A new retiming-based technology mapping algorithm for LUT-based FPGAs, Proceedings of the 1998 ACM/SIGDA sixth international symposium on Field programmable gate arrays, p.35-42, February 22-25, 1998, Monterey, California, United States
Shigeru Yamashita , Hiroshi Sawada , Akira Nagoya, A new method to express functional permissibilities for LUT based FPGAs and its applications, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.254-261, November 10-14, 1996, San Jose, California, United States
Jason Cong , Yuzheng Ding, Combinational logic synthesis for LUT based field programmable gate arrays, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.1 n.2, p.145-204, April 1996
Peichen Pan , C. L. Liu, Technology mapping of sequential circuits for LUT-based FPGAs for performance, Proceedings of the 1996 ACM fourth international symposium on Field-programmable gate arrays, p.58-64, February 11-13, 1996, Monterey, California, United States
Chau-Shen Chen , Yu-Wen Tsay , TingTing Hwang , Allen C. H. Wu , Youn-Long Lin, Combining technology mapping and placement for delay-optimization in FPGA designs, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.123-127, November 07-11, 1993, Santa Clara, California, United States
Rajeev Murgai , Robert K. Brayton , Alberto Sangiovanni-Vincentelli, Cube-packing and two-level minimization, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.115-122, November 07-11, 1993, Santa Clara, California, United States
S. Höreth, Compilation of optimized OBDD-algorithms, Proceedings of the conference on European design automation, p.152-157, September 1996, Geneva, Switzerland
Wei Wan , Marek A. Perkowski, A new approach to the decomposition of incompletely specified multi-output functions based on graph coloring and local transformations and its application to FPGA mapping, Proceedings of the conference on European design automation, p.230-235, November 1992, Congress Centrum Hamburg, Hamburg, Germany
Jason Cong , Hui Huang , Xin Yuan, Technology mapping for k/m-macrocell based FPGAs, Proceedings of the 2000 ACM/SIGDA eighth international symposium on Field programmable gate arrays, p.51-59, February 10-11, 2000, Monterey, California, United States
Marc Wendling , Wolfgang Rosenstiel, A hardware environment for prototyping and partitioning based on multiple FPGAs, Proceedings of the conference on European design automation, p.77-82, September 19-23, 1994, Grenoble, France
Peichen Pan , C. L. Liu, Optimal clock period FPGA technology mapping for sequential circuits, Proceedings of the 33rd annual conference on Design automation, p.720-725, June 03-07, 1996, Las Vegas, Nevada, United States
Yuji Kukimoto , Masahiro Fujita, Rectification method for lookup-table type FPGA's, Proceedings of the 1992 IEEE/ACM international conference on Computer-aided design, p.54-61, November 1992, Santa Clara, California, United States
Jason Cong , Yean-Yow Hwang, Structural gate decomposition for depth-optimal technology mapping in LUT-based FPGA designs, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.5 n.2, p.193-225, April 2000
Peichen Pan , C. L. Liu, Optimal clock period FPGA technology mapping for sequential circuits, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.3 n.3, p.437-462, July 1998
Robert J. Francis, A tutorial on logic synthesis for lookup-table based FPGAs, Proceedings of the 1992 IEEE/ACM international conference on Computer-aided design, p.40-47, November 1992, Santa Clara, California, United States
Jason Cong , Chang Wu , Yuzheng Ding, Cut ranking and pruning: enabling a general and efficient FPGA mapping solution, Proceedings of the 1999 ACM/SIGDA seventh international symposium on Field programmable gate arrays, p.29-35, February 21-23, 1999, Monterey, California, United States
Nozomu Togawa , Masao Sato , Tatsuo Ohtsuki, A simultaneous technology mapping, placement, and global routing algorithm for field-programmable gate arrays, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.156-163, November 06-10, 1994, San Jose, California, United States
Peter Suaris , Lungtien Liu , Yuzheng Ding , Nanchi Chou, Incremental physical resynthesis for timing optimization, Proceedings of the 2004 ACM/SIGDA 12th international symposium on Field programmable gate arrays, February 22-24, 2004, Monterey, California, USA
Chi-Chou Kao , Yen-Tai Lai, Area-minimal algorithm for LUT-based FPGA technology mapping with duplication-free restriction, Proceedings of the 2004 conference on Asia South Pacific design automation: electronic design and solution fair, p.719-724, January 27-30, 2004, Yokohama, Japan
Juinn-Dar Huang , Jing-Yang Jou , Wen-Zen Shen, An iterative area/performance trade-off algorithm for LUT-based FPGA technology mapping, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.13-17, November 10-14, 1996, San Jose, California, United States
Juinn-Dar Huang , Jing-Yang Jou , Wen-Zen Shen, Compatible class encoding in Roth-Karp decomposition for two-output LUT architecture, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.359-363, November 05-09, 1995, San Jose, California, United States
Kuang-Chien Chen , Jason Cong, Maximal reduction of lookup-table based FPGAs, Proceedings of the conference on European design automation, p.224-229, November 1992, Congress Centrum Hamburg, Hamburg, Germany
Vi Cuong Chan , David M. Lewis, Area-speed tradeoffs for hierarchical field-programmable gate arrays, Proceedings of the 1996 ACM fourth international symposium on Field-programmable gate arrays, p.51-57, February 11-13, 1996, Monterey, California, United States
Madhukar R. Korupolu , K. K. Lee , D. F. Wong, Exact tree-based FPGA technology mapping for logic blocks with independent LUTs, Proceedings of the 35th annual conference on Design automation, p.708-711, June 15-19, 1998, San Francisco, California, United States
Bernd Wurth , Ulf Schlichtmann , Klaus Eckl , Kurt J. Antreich, Functional multiple-output decomposition with application to technology mapping for lookup table-based FPGAs, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.4 n.3, p.313-350, July 1999
Kuang-Chien Chen , Jason Cong , Yuzheng Ding , Andrew B. Kahng , Peter Trajmar, DAG-Map: Graph-Based FPGA Technology Mapping for Delay Optimization, IEEE Design & Test, v.9 n.3, p.7-20, July 1992
Hao Li , Srinivas Katkoori , Wai-Kei Mak, Power minimization algorithms for LUT-based FPGA technology mapping, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.9 n.1, p.33-51, January 2004
Tomasz S. Czajkowski , Jonathan Rose, A synthesis oriented omniscient manual editor, Proceedings of the 2004 ACM/SIGDA 12th international symposium on Field programmable gate arrays, February 22-24, 2004, Monterey, California, USA
Jason Cong , Hui Huang , Xin Yuan, Technology mapping and architecture evalution for k/m-macrocell-based FPGAs, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.10 n.1, p.3-23, January 2005
Jason Cong , Hui Huang , Xin Yuan, Technology mapping and architecture evalution for k/m-macrocell-based FPGAs, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.10 n.1, p.3-23, January 2005
Hao Li , Wai-Kei Mak , Srinivas Katkoori, Efficient LUT-based FPGA technology mapping for power minimization, Proceedings of the 2003 conference on Asia South Pacific design automation, January 21-24, 2003, Kitakyushu, Japan
Jason Cong , Kirill Minkovich, Optimality study of logic synthesis for LUT-based FPGAs, Proceedings of the internation symposium on Field programmable gate arrays, February 22-24, 2006, Monterey, California, USA
Chi-Chou Kao , Yen-Tai Lai, A technology mapping algorithm for heterogeneous FPGAs, Proceedings of the 2003 conference on Asia South Pacific design automation, January 21-24, 2003, Kitakyushu, Japan
Joey Y. Lin , Deming Chen , Jason Cong, Optimal simultaneous mapping and clustering for FPGA delay optimization, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, CA, USA
Steven J. E. Wilton, SMAP: heterogeneous technology mapping for area reduction in FPGAs with embedded memory arrays, Proceedings of the 1998 ACM/SIGDA sixth international symposium on Field programmable gate arrays, p.171-178, February 22-25, 1998, Monterey, California, United States
Lei Cheng , Deming Chen , Martin D. F. Wong, GlitchMap: an FPGA technology mapper for low power considering glitches, Proceedings of the 44th annual conference on Design automation, June 04-08, 2007, San Diego, California
Lei Cheng , M. D. F. Wong, Floorplan design for multi-million gate FPGAs, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.292-299, November 07-11, 2004
M. Teslenko , E. Dubrova, Hermes: LUT FPGA technology mapping algorithm for area minimization with optimum depth, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.748-751, November 07-11, 2004
D. Chen , J. Cong, DAOmap: a depth-optimal area optimization mapping algorithm for FPGA designs, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.752-759, November 07-11, 2004
Manoj A. Kumar , Jayaram Bobba , V Kamakoti, MemMap: Technology Mapping Algorithm for Area Reduction in FPGAs with Embedded Memory Arrays Using Reconvergence Analysis, Proceedings of the conference on Design, automation and test in Europe, p.20922, February 16-20, 2004
Hosung (Leo) Kim , John Lillis, A framework for layout-level logic restructuring, Proceedings of the 2008 international symposium on Physical design, April 13-16, 2008, Portland, Oregon, USA
Deming Chen , Jason Cong , Peichen Pan, FPGA Design Automation: A Survey, Foundations and Trends® in Electronic Design Automation, v.1 n.3, p.139-169, January 2006

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Gate arrays

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Automatic synthesis
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids

  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)


General Terms:
Algorithms, Design, Performance, Theory

Collaborative Colleagues:
Robert Francis: colleagues
Jonathan Rose: colleagues
Zvonko Vranesic: colleagues

The ACM Portal is published by the Association for Computing Machinery. Copyright © 2009 ACM, Inc.
Terms of Usage   Privacy Policy   Code of Ethics   Contact Us

Useful downloads: Adobe Acrobat    QuickTime    Windows Media Player    Real Player