|
 ABSTRACT
Technology binding is the process of mapping a technology independent description of a circuit into a particular technology. This paper outlines a formalism of this problem and offers a solution to the problem in terms of matching patterns, describing technology specific cells and optimizations, against a technology independent circuit represented as a directed acyclic graph. This solution is implemented in DAGON. DAGON rests on a firm algorithmic foundation, and is able to guarantee locally optimal matches against a set of over three thousand patterns. DAGON is an integral part of a synthesis system that has been found to provide industrial quality solutions to real circuit design problems.
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.
| |
AHU76
|
A. Aho, J. Hopcroft, J. Ullman, Addison-Wesley Publishing Company, Third Edition pp. 186-194.
|
| |
ASU86
|
A. Aho, R. Sethi, J. Ullman, Addison-Wesley Publishing Company, pp.557-584.
|
 |
AhGa85
|
|
| |
AhJo76
|
|
| |
AJU77
|
|
| |
BrMc84
|
R. Brayton, C. McMullen, ~Synthesis and Optimization of Multi-Stage Logic", "Proc. of the ICCDn, October 84, 23-28,
|
| |
BDKM86
|
R. Brayton, E. Detjens, S. Krishna, T. Ma, et. al., "Multiple-Level Logic Optimization System~, "Proc. of the ICCAD~, November 1986.
|
| |
BrSe76
|
|
| |
Ch87
|
|
| |
DJBT81
|
J. Darringer, W. oroyner, C. L. Berman, L. Trevillyan, "Logic Synthesis Through Local Transformations", 25, 4, 272-280 (1981)."
|
| |
DBGJ84
|
John A. Darringer , Daniel Brand , John V. Gerbi , William H. Joyner, Jr. , Louise Trevillyan, LSS: a system for production logic synthesis, IBM Journal of Research and Development, v.28 n.5, p.537-545, September 1984
|
| |
DLT84
|
Jean Dussault , Chi-Chang Liaw , Michael M. Tong, A high level synthesis tool for MOS chip design, Proceedings of the 21st conference on Design automation, p.308-314, June 25-27, 1984, Albuquerque, New Mexico, United States
|
| |
Fr84
|
E. Frey, "ESIM: A functional level simulation tool", "Proc. of the ICCAD", November 84, 48-53.
|
| |
Ge86
|
|
| |
GeCo85
|
A. J. de Geus, W. Cohen, "A Rule Based System for Optimizing Combinational Logic" 2, 4, 22-32 (1985).
|
| |
GBGH86
|
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
|
| |
Hi85
|
D. D. Hill, "Sc2: A Hybrid Automatic Layout System", "Proc. of the ICCAD", November 85, 172-174.
|
| |
HoOD82
|
|
| |
Jo83
|
|
| |
JTB86
|
William H. Joyner, Jr. , Louise H. Trevillyan , Daniel Brand , Theresa A. Nix , Steven C. Gundersen, Technology adaption in logic synthesis, Proceedings of the 23rd ACM/IEEE conference on Design automation, p.94-100, July 1986, Las Vegas, Nevada, United States
|
| |
Ka86
|
M. Kahrs, "Matching a parts library in a silicon compiler", "Proc. of the ICCAD", November 1986.
|
| |
KL87
|
K. Keutzer, M. Lega, M. Vancura, "A Multi-Level Synthesis Methodology", to be presented "International Workshop on Logic Synthesis", North Carolina,May 87.
|
| |
SMP86
|
C. Stroud, R. Munoz, D. Pierce, ~CONES: A System of Automated Synthesis of VLSI and Programmable Logic from Behavioral Models", "Proc. of the ICCAD", November 1986.
|
| |
Tj86
|
S. Tjiang, "Twig Reference Manual", January 1986.
|
| |
TJB86
|
L. Trevillyan, W. Joyner, L. Berman, "Global Flow Analysis in Automatic Logic Design~, C35, 1, 77-81 (1986).
|
CITED BY 140
|
|
|
|
|
|
|
|
Rob A. Rutenbar , L. Richard Carley , Roberto Zafalon , Nicola Dragone, Low-power technology mapping for mixed-swing logic, Proceedings of the 2001 international symposium on Low power electronics and design, p.291-294, August 2001, Huntington Beach, California, United States
|
|
|
|
|
|
|
|
|
Dirk-Jan Jongeneel , Yosinori Watanbe , Robert K. Brayton , Ralph Otten, Area and search space control for technology mapping, Proceedings of the 37th conference on Design automation, p.86-91, June 05-09, 2000, Los Angeles, California, United States
|
|
|
|
|
|
Joel Grodstein , Eric Lehman , Heather Harkness , Bill Grundmann , Yosinatori Watanabe, A delay model for logic synthesis of continuously-sized networks, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.458-462, November 05-09, 1995, San Jose, California, United States
|
|
|
|
|
|
Aiguo Lu , Guenter Stenz , Frank M. Johannes, Technology mapping for minimizing gate and routing area, Proceedings of the conference on Design, automation and test in Europe, p.664-669, February 23-26, 1998, Le Palais des Congrés de Paris, France
|
|
|
|
|
|
|
|
|
|
|
|
W. N. Li , A. Lim , P. Agrawal , S. Sahni, On the circuit implementation problem, Proceedings of the 29th ACM/IEEE conference on Design automation, p.478-483, June 08-12, 1992, Anaheim, California, United States
|
|
|
|
|
|
|
|
|
|
|
|
R. Murgai , R. K. Brayton , A. L. Sangiovanni-Vincentelli, An improved synthesis algorithm for multiplexor-based PGA's, Proceedings of the 29th ACM/IEEE conference on Design automation, p.380-386, June 08-12, 1992, Anaheim, California, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
D. S. Kung , R. F. Damiano , T. A. Nix , D. J. Geiger, BDDMAP: a technology mapper based on a new covering algorithm, Proceedings of the 29th ACM/IEEE conference on Design automation, p.484-487, June 08-12, 1992, Anaheim, California, United States
|
|
|
T.-T. Hwang , R. M. Owens , M. J. Irwin, Multi-level logic synthesis using communication complexity, Proceedings of the 26th ACM/IEEE conference on Design automation, p.215-220, June 25-28, 1989, Las Vegas, Nevada, United States
|
|
|
|
|
|
Jinan Lou , Amir H. Salek , Massoud Pedram, An exact solution to simultaneous technology mapping and linear placement problem, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.671-675, November 09-13, 1997, San Jose, California, United States
|
|
|
Ruey-Sing Wei , Steven Rothweiler , Jing-Yang Jou, BECOME: behavior level circuit synthesis based on structure mapping, Proceedings of the 25th ACM/IEEE conference on Design automation, p.409-414, June 12-15, 1988, Atlantic City, New Jersey, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Eric Lehman , Yosinori Watanabe , Joel Grodstein , Heather Harkness, Logic decomposition during technology mapping, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.264-271, November 05-09, 1995, San Jose, California, United States
|
|
|
Amit Chowdhary , Sudhakar Kale , Phani Saripella , Naresh Sehgal , Rajesh Gupta, A general approach for regularity extraction in datapath circuits, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.332-339, November 08-12, 1998, San Jose, California, United States
|
|
|
Hamid Savoj , Mário J. Silva , Robert K. Brayton , Alberto Sangiovanni-Vincentelli, Boolean matching in logic synthesis, Proceedings of the conference on European design automation, p.168-174, November 1992, Congress Centrum Hamburg, Hamburg, Germany
|
|
|
Timothy J. Callahan , Philip Chong , André DeHon , John Wawrzynek, Fast module mapping and placement for datapaths in FPGAs, Proceedings of the 1998 ACM/SIGDA sixth international symposium on Field programmable gate arrays, p.123-132, February 22-25, 1998, Monterey, California, United States
|
|
|
|
|
|
Andrew B. Kahng , Darko Kirovski , Stefanus Mantik , Miodrag Potkonjak , Jennifer L. Wong, Copy detection for intellectual property protection of VLSI designs, Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, p.600-605, November 07-11, 1999, San Jose, California, United States
|
|
|
|
|
|
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
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Robert Francis , Jonathan Rose , Zvonko Vranesic, Chortle-crf: Fast technology mapping for lookup table-based FPGAs, Proceedings of the 28th conference on ACM/IEEE design automation, p.227-233, June 17-22, 1991, San Francisco, California, United States
|
|
|
|
|
|
Polly Siegel , Giovanni De Micheli , David Dill, Automatic technology mapping for generalized fundamental-mode asynchronous designs, Proceedings of the 30th international conference on Design automation, p.61-67, June 14-18, 1993, Dallas, Texas, United States
|
|
|
Ko Yoshikawa , Hiroshi Ichiryu , Hisato Tanishita , Sigenobu Suzuki , Nobuyoshi Nomizu , Akira Kondoh, Timing optimization on mapped circuits, Proceedings of the 28th conference on ACM/IEEE design automation, p.112-117, June 17-22, 1991, San Francisco, California, United States
|
|
|
|
|
|
|
|
|
|
|
|
U. Schlichtmann , F. Brglez , M. Hermann, Characterization of Boolean functions for rapid matching in FPGA technology mapping, Proceedings of the 29th ACM/IEEE conference on Design automation, p.374-379, June 08-12, 1992, Anaheim, California, United States
|
|
|
M. Crastes , K. Sakouti , G. Saucier, A technology mapping method based on perfect and semi-perfect matchings, Proceedings of the 28th conference on ACM/IEEE design automation, p.93-98, June 17-22, 1991, San Francisco, California, United States
|
|
|
Shashidhar Thakur , D. F. Wong , Shankar Krishnamoorthy, Delay minimal decomposition of multiplexers in technology mapping, Proceedings of the 33rd annual conference on Design automation, p.254-257, June 03-07, 1996, Las Vegas, Nevada, United States
|
|
|
|
|
|
Yutaka Tamiya , Yusuke Matsunaga , Masahiro Fujita, LP based cell selection with constraints of timing, area, and power consumption, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.378-381, November 06-10, 1994, San Jose, California, United States
|
|
|
Wayne Wolf , Kurt Keutzer , Janaki Akella, A kernel-finding state assignment algorithm for multi-level logic, Proceedings of the 25th ACM/IEEE conference on Design automation, p.433-438, June 12-15, 1988, Atlantic City, New Jersey, United States
|
|
|
|
|
|
|
|
|
Sumit Roy , Krishna Belkhale , Prithviraj Banerjee, An &agr;-approxmimate algorithm for delay-constraint technology mapping, Proceedings of the 36th ACM/IEEE conference on Design automation, p.367-372, June 21-25, 1999, New Orleans, Louisiana, United States
|
|
|
Yuji Kukimoto , Robert K. Brayton , Prashant Sawkar, Delay-optimal technology mapping by DAG covering, Proceedings of the 35th annual conference on Design automation, p.348-351, June 15-19, 1998, San Francisco, California, United States
|
|
|
|
|
|
|
|
|
|
|
|
Amir H. Salek , Jinan Lou , Massoud Pedram, A DSM design flow: putting floorplanning, technology-mapping, and gate-placement together, Proceedings of the 35th annual conference on Design automation, p.128-134, June 15-19, 1998, San Francisco, California, United States
|
|
|
Patrick Vuillod , Luca Benini , Giovanni De Micheli, Generalized matching from theory to application, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.13-20, November 09-13, 1997, San Jose, California, United States
|
|
|
|
|
|
Kurt Keutzer , A. Richard Newton , Narendra Shenoy, The future of logic synthesis and physical design in deep-submicron process geometries, Proceedings of the 1997 international symposium on Physical design, p.218-224, April 14-16, 1997, Napa Valley, California, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Jason Cong , Yiping Fan , Guoling Han , Zhiru Zhang, Application-specific instruction generation for configurable processor architectures, Proceedings of the 2004 ACM/SIGDA 12th international symposium on Field programmable gate arrays, February 22-24, 2004, Monterey, California, USA
|
|
|
|
|
|
|
|
|
|
|
|
K. Kodandapani , J. Grodstein , A. Domic , H. Touati, A simple algorithm for fanout optimization using high-performance buffer libraries, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.466-471, November 07-11, 1993, Santa Clara, California, United States
|
|
|
|
|
|
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
|
|
|
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
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Chang Woo Kang , Ali Iranli , Massoud Pedram, Technology mapping and packing for coarse-grained, anti-fuse based FPGAs, Proceedings of the 2004 conference on Asia South Pacific design automation: electronic design and solution fair, p.209-211, January 27-30, 2004, Yokohama, Japan
|
|
|
Rupesh S. Shelar , Sachin S. Sachin S. Sapatnekar , Prashant Saxena , Xinning Wang, A predictive distributed congestion metric and its application to technology mapping, Proceedings of the 2004 international symposium on Physical design, April 18-21, 2004, Phoenix, Arizona, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Rupesh S. Shelar , Prashant Saxena , Xinning Wang , Sachin S. Sapatnekar, An efficient technology mapping algorithm targeting routing congestion under delay constraints, Proceedings of the 2005 international symposium on Physical design, April 03-06, 2005, San Francisco, California, USA
|
|
|
|
|
|
|
|
|
|
|
|
Bo Hu , Yosinori Watanabe , Alex Kondratyev , Malgorzata Marek-Sadowska, Gain-based technology mapping for discrete-size cell libraries, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA
|
|
|
|
|
|
|
|
|
Ashish Kumar Singh , Murari Mani , Ruchir Puri , Michael Orshansky, Gain-based technology mapping for minimum runtime leakage under input vector uncertainty, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, CA, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Hosung (Leo) Kim , John Lillis , Miloš Hrkić , Miloš Hrkić, Techniques for improved placement-coupled logic replication, Proceedings of the 16th ACM Great Lakes symposium on VLSI, April 30-May 01, 2006, Philadelphia, PA, USA
|
|
|
Sean Safarpour , Andreas Veneris , Gregg Baeckler , Richard Yuan, Efficient SAT-based Boolean matching for FPGA technology mapping, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, CA, USA
|
|
|
F. S. Marques , L. S. Rosa, Jr. , R. P. Ribas , S. S. Sapatnekar , A. I. Reis, DAG based library-free technology mapping, Proceedings of the 17th great lakes symposium on Great lakes symposium on VLSI, March 11-13, 2007, Stresa-Lago Maggiore, Italy
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
S. Chatterjee , A. Mishchenko , R. Brayton , X. Wang , T. Kam, Reducing structural bias in technology mapping, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.519-526, November 06-10, 2005, San Jose, CA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Kingshuk Karuri , Anupam Chattopadhyay , Xiaolin Chen , David Kammler , Ling Hao , Rainer Leupers , Heinrich Meyr , Gerd Ascheid, A design flow for architecture exploration and implementation of partially reconfigurable processors, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.16 n.10, p.1281-1294, October 2008
|
|
|
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf
J.6