Article

Free access

Timing optimization for multi-level combinational networks

Authors:

Kuang-Chien Chen,

Saburo MurogaAuthors Info & Claims

DAC '90: Proceedings of the 27th ACM/IEEE Design Automation Conference

Pages 339 - 344

https://doi.org/10.1145/123186.105253

Published: 03 January 1991 Publication History

Abstract

This paper presents a timing optimization algorithm SDLR (acronym of SYLON-DREAM Level-Reduction), which is used in the SYLON-DREAM logic synthesizer for speeding up combinational multi-level networks. In SDLR, gates on critical paths are identified and their level numbers counted from the inputs of the network are maximally reduced by a level-reduction procedure. Gates which are not on the critical paths are processed by an area reduction procedure to reduce network area without increasing its maximum depth. SDLR uses the concept of permissible functions in both level and area reduction procedures, and it can directly process networks consisting of simple gates or negative gates (i.e., MOS cells). Experimental results obtained for benchmark functions show that SDLR is an effective algorithm which can reduce network delay with no or minimal area increase.

References

[1]

K. Bartlett, W. Cohen, A. de Geus, and G. H~chtel, "Synthesis and Optimization of Multi-level Logic Under Timing Constraints," IEEE TCAD, vol. CAD-5, Oct. 1985, p. 582-595.

[2]

R. Brayton, R. Camposauo, G. De Micheli, R. Often, and J. van Eijndhoven, "The York~wn Silicon Compiler System," in Silicon Compilation, D. Gaiskj, Ed. Reading, MA: Addison Wesley, 1987.

[3]

D. Bostick, G. D. Hachtel, R. Jacoby, M. R. Lightner, P. Moceyunas, C. R. Morrison, and Ravenscroft, "The Boulder Optimal Logic Design System," Proc. ICCAD, 1987, pp. 62-65.

[4]

R. K. Bray~n, R. Rudell, A. L. Sangiovanni-Vincentelli, and A. R. Wang, '~{IS: A Multiple-Level Logic Optimization," IEEE TCAD, Nov. 1987, pp. 1062-1081.

[5]

R. E. Bryant, "Graph Based Algorithms for Boolean Function Manipulation," IEEE TC, vol. C--35, no. 8, Aug. 1986, pp. 677-691.

Digital Library

[6]

J. N. Culliney, H. C. Lai, and Y. Kambayashi, ~Pruning Procedures for NOR Networks Using Permissible Functions (Principles of NOR Network Transduction Programs NETTRA-PGI, NETTRA-P1, and NETTRA-P2)," Dept. of Comput. Sci., UIUCDCS-R-74--690, Univ. of Ill., 1976.

[7]

H. Y. Chen and S. M. Kang, "iCOACH: A Circuit Optimization Aid for CMOS," Proc. ICCAD, 1988, pp. 372-375.

[8]

K. C. Chen and S. Muroga, "SYLON-DREAM: A Multi-Level Network Synthesizer," Proc. ICCAD, 1989.

[9]

J. A. Darringer, D. Brand, J. V. Gerbi, W. H. Joyner, and L. Trevillyan, '%SS: A System for Production Logic Synthesis," IBM J. Res. Dev., vol. 28, Sep. 1984, pp. 537- 545.

Digital Library

[10]

G. De Micheli, '~Performance-oriented Synthesis of Large-scale Domino CMOS circuits," IEEE TCAD, vol. CAD-6, Sep. 1987, pp. 751-765.

[11]

D. Gregory, K. Bartlett, A. de Gnus, and G. Hachtel, "SOCRATES: A System for Automatically Synthesizing and Optimizing Combinational Logic," Proc. DAC, 1986, pp. 79-85.

Digital Library

[12]

W. H. Joyner, L. H. Trevillyan, D. Brand, T. A. Nix, and S. C. Gundersen, "Technology Adaptation in Logic Synthesis," Proc. DAC, 1988, pp. 94-100.

Digital Library

[13]

Y. Kambayashi and J. N. Culliney, "NOR Network Transduction Procedures Based on Connectable and Disconnectable Conditions (Principles of NOR Network Transduction Programs NETTRA-GI and NETTRA-G2)," Dept. of Comput. Sci., UIUCDCS-R-76-841, Univ. of Ill., 1075.

[14]

Y. Kambayashi, H. C. Lai, J. N. Culliney, and S. Muroga, "NOR Network Transduction Based on Error- Compensation (Principles of NOR Network Transduction Programs NETTRA-EI, NETTRA-E2 and NETTRA-E3)," Dept. of Comput. Sci., UIUCDCS-R-75-737, Univ. of ill., 1975.

[15]

Y. Kambayashi and S. Muroga, "Network Transduction Based on Permissible Functions (General Principles of NOR Network Transduction NETTRA Programs)," Dept. of Comput. Sci., UIUCDCS-R-76-804, Univ. of Ill., 1976.

[16]

R. Lisanke, '%ogic Synthesis and Optimization Benchmarks User Guide Ver. 2.0", Technical Report, Microelectronics Center of North Carolina, Research Triangle Park, NC, Dec. 1988.

[17]

H. C. Lai and Y. Kambayashi, "NOR Network Transduction by Generalir, ed Gate Merging and Substitution Procedures (Principles of NOR Network Transduction Programs NETTRA-G3 and NETTRA-G4)," Dept. of Comput. Sci., UIUCDCS-R-75-728, Univ. of III., 1975.

[18]

S. Muroga, Y. Kambayashi, H. C. Lai, and J. N. Culliney, "The Transduction Method w Design of Logic Networks based on Permissible Functions," IEEE TC, Oct. 1980.

Digital Library

[19]

S. Muroga, "Logic Design and Switching Theory," John Wiley & Sons, Inc., 1979, 617 pp.

Digital Library

[20]

S. Muroga, X. Q. Xiang, J. Limqueco, L. P. Lin, and K. C. Chen, "A Logic Network Synthesis System, SYLON," Proc. ICCD, 1989, pp. 324-328.

[21]

P. G. Paulin and F. J. Poirot, "Logic Decomposition Algorithms for the Timing Optimization of Multi-Level Logic," Proc. ICCD, 1989, pp. 329-333.

[22]

K. J. Singh, A. R. Wang, R. K. Bray~n, and A. S angiovsnni-~rm centelli, "Timing Optimization of Combinational Logic," Proc. ICCAD, 1988, pp. 282-285.

[23]

X. ~ang and S. Muroga, "Synthesis of Multilevel Networks with Simple Gates," Proc. IWLS, North Carolina, May 1989.

Cited By

Choudhury MMohanram K(2009)Timing-driven optimization using lookahead logic circuitsProceedings of the 46th Annual Design Automation Conference10.1145/1629911.1630015(390-395)Online publication date: 26-Jul-2009
https://dl.acm.org/doi/10.1145/1629911.1630015
Bañeres DCortadella JKishinevsky MQu GIsmail YNarayanan VZhou H(2006)Dominator-based partitioning for delay optimizationProceedings of the 16th ACM Great Lakes symposium on VLSI10.1145/1127908.1127927(67-72)Online publication date: 30-Apr-2006
https://dl.acm.org/doi/10.1145/1127908.1127927
Srivastava AKastner RChen CSarrafzadeh M(2004)Timing driven gate duplicationIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.5555/986333.98633712:1(42-51)Online publication date: 1-Jan-2004
https://dl.acm.org/doi/10.5555/986333.986337
Show More Cited By

Index Terms

Timing optimization for multi-level combinational networks

Recommendations

Computer-Aided Logic Design of Two-Level MOS Combinational Networks with Statistical Results

Metal-oxide-semiconductor (MOS) logic elements offer advantages over bipolar logic elements, such as smaller size, complexity, and power consumption, as well as more flexibility and versatility. Since MOS is playing a major role in large-scale ...
Study of timing verification and timing optimization of combinational circuits
Optimization of Multi-Valued Multi-Level Networks
ISMVL '02: Proceedings of the 32nd International Symposium on Multiple-Valued Logic

A program called MVSIS has been developed which optimizesmulti-level multi-valued networks (MV networks).We describe what such a network is and the capabilitiescontained in MVSIS. MVSIS is modeled after SIS, whichsynthesizes binary multi-level networks, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

DAC '90: Proceedings of the 27th ACM/IEEE Design Automation Conference

January 1991

742 pages

ISBN:0897913639

DOI:10.1145/123186

Chairman:
Richard C. Smith

Copyright © 1991 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
IEEE-CS: Computer Society

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 03 January 1991

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

DAC90

Sponsor:

SIGDA
IEEE-CS

DAC90: The 27th ACM/IEEE-CS Design Automation Conference

June 24 - 27, 1990

Florida, Orlando, USA

Acceptance Rates

DAC '90 Paper Acceptance Rate 125 of 427 submissions, 29%;

Overall Acceptance Rate 1,770 of 5,499 submissions, 32%

Upcoming Conference

DAC '25

Sponsor:
sigda

62nd ACM/IEEE Design Automation Conference

June 22 - 26, 2025

San Francisco , CA , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
605
Total Downloads

Downloads (Last 12 months)28
Downloads (Last 6 weeks)10

Reflects downloads up to 02 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Choudhury MMohanram K(2009)Timing-driven optimization using lookahead logic circuitsProceedings of the 46th Annual Design Automation Conference10.1145/1629911.1630015(390-395)Online publication date: 26-Jul-2009
https://dl.acm.org/doi/10.1145/1629911.1630015
Bañeres DCortadella JKishinevsky MQu GIsmail YNarayanan VZhou H(2006)Dominator-based partitioning for delay optimizationProceedings of the 16th ACM Great Lakes symposium on VLSI10.1145/1127908.1127927(67-72)Online publication date: 30-Apr-2006
https://dl.acm.org/doi/10.1145/1127908.1127927
Srivastava AKastner RChen CSarrafzadeh M(2004)Timing driven gate duplicationIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.5555/986333.98633712:1(42-51)Online publication date: 1-Jan-2004
https://dl.acm.org/doi/10.5555/986333.986337
Gunther WDrechsler R(2001)Performance driven optimization for MUX based FPGAsVLSI Design 2001. Fourteenth International Conference on VLSI Design10.1109/ICVD.2001.902678(311-316)Online publication date: 2001
https://doi.org/10.1109/ICVD.2001.902678
Günther WDrechsler R(2000)ACTionJournal of Systems Architecture: the EUROMICRO Journal10.1016/S1383-7621(00)00027-846:14(1321-1334)Online publication date: 1-Dec-2000
https://dl.acm.org/doi/10.1016/S1383-7621%2800%2900027-8
Pan P(1999)Performance-driven integration of retiming and resynthesisProceedings of the 36th annual ACM/IEEE Design Automation Conference10.1145/309847.309921(243-246)Online publication date: 1-Jun-1999
https://dl.acm.org/doi/10.1145/309847.309921
Peichen Pan (1999)Performance-driven integration of retiming and resynthesisProceedings 1999 Design Automation Conference (Cat. No. 99CH36361)10.1109/DAC.1999.781319(243-246)Online publication date: 1999
https://doi.org/10.1109/DAC.1999.781319
Aiguo Lu Eisenmann HStenz GJohannes F(1998)Combining technology mapping with post-placement resynthesis for performance optimizationProceedings International Conference on Computer Design. VLSI in Computers and Processors (Cat. No.98CB36273)10.1109/ICCD.1998.727128(616-621)Online publication date: 1998
https://doi.org/10.1109/ICCD.1998.727128
Aggarwal RMurgai RFujita MOtten RYasuura H(1997)Speeding up technology-independent timing optimization by network partitioningProceedings of the 1997 IEEE/ACM international conference on Computer-aided design10.5555/266388.266431(83-90)Online publication date: 13-Nov-1997
https://dl.acm.org/doi/10.5555/266388.266431
Entrena LOlías EUceda JEspejo JSymonds GNebel W(1996)Timing optimization by an improved redundancy addition and removal techniqueProceedings of the conference on European design automation10.5555/252471.252531(342-347)Online publication date: 20-Sep-1996
https://dl.acm.org/doi/10.5555/252471.252531
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

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