Metrics for structural logic synthesis

ABSTRACT

Routability or wiring congestion in a VLSI chip is becoming increasingly important as chip complexity increases. Congestion has a significant impact on performance, yield and chip area. Although advances in placement algorithms have attempted to alleviate this problem, the inherent structure of the logic netlist has a significant impact on the routability irrespective of the placement algorithm used. Placement algorithms find optimal assignment of locations to the logic and do not have the ability to change the netlist structure. Significant decisions regarding the circuit structure are made early in synthesis such as during the technology independent logic optimization step. Optimizations in this step use literal count as a metric for optimization and do not adequately capture the intrinsic entanglement of the netlist. Two circuits with identical literal counts may have significantly different congestion characteristics post placement. In this paper, we motivate that a property of the network structure called adhesion can make a significant contribution to routing congestion. We then provide a metric to measure this property. We also show that adhesion as measured by this metric can be used in addition to literal counts to estimate and optimize post routing congestion early in the design flow.

REFERENCES

• 1: ALPERT, C., CHAN, T., A.B. KAHNG, MARKOV, I., AND MULET, P. Faster minimization of linear wirelength for global placement. IEEE Transactions on Computer-Aided Design 17, 1 (Jan. 1998).
• 2: ARIKATI, S. R., CHAUDHURI, S., AND ZAROLIAGIS, C. D. All-pairs min-cut in sparse networks. Research Report MPI-I-96-1-007, Max-Planck-Institut für Informatik, Im Stadtwald, D-66123 Saarbrücken, Germany, March 1996.
• 3: DONATH, W. E. Equivalence of memory to random logic. IBM Journal of Research and Development (September 1974), 401--407.
• 4: Andrew V. Goldberg , Kostas Tsioutsiouliklis, Cut tree algorithms, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.376-385, January 17-19, 1999, Baltimore, Maryland, United States
• 5: Wilsin Gosti , Amit Narayan , Robert K. Brayton , Alberto L. Sangiovanni-Vincentelli, Wireplanning in logic synthesis, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.26-33, November 08-12, 1998, San Jose, California, United States [doi>10.1145/288548.288556]
• 6: HARARY, F. Graph Theory. Addison Wesley, 1969.
• 7: George Karypis , Rajat Aggarwal , Vipin Kumar , Shashi Shekhar, Multilevel hypergraph partitioning: application in VLSI domain, Proceedings of the 34th annual conference on Design automation, p.526-529, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266273]
• 8: Thomas Kutzschebauch , Leon Stok, Congestion aware layout driven logic synthesis, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
• 9: MOODY, J., AND WHITE, D. R. Social cohesion and embeddedness: A hierarchical conception of social groups. Sociological Methodology (2002).
• 10: P. Abouzeid , K. Sakouti , G. Saucier , F. Poirot, Multilevel synthesis minimizing the routing factor, Proceedings of the 27th ACM/IEEE conference on Design automation, p.365-368, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123307]
• 11: PEDRAM, M., AND BHAT, N. Layout driven logic restructuring/decomposition. In Proc. International Conf. Computer-Aided Design (ICCAD) (Nov. 1991), IEEE Computer Society Press, pp. 134--137.
• 12: R.E. GOMORY, AND T.C. HU. Multi-terminal network flows. J. SIAM 9 (1961), 551--570.
• 13: L. Stok , D. S. Kung , D. Brand , A. D. Drumm , L. N. Reddy , N. Hieter , D. J. Geiger , H. H. Chao , P. J. Osler , A. J. Sullivan, BooleDozer: logic synthesis for ASICs, IBM Journal of Research and Development, v.40 n.4, p.407-430, July 1996
• 14: VASUDEVAMURTHY, J., AND RAJSKI, J. A method for concurrent decomposition and factorization of boolean expressions. In Proc. International Conf. Computer-Aided Design (ICCAD) (Nov. 1990), IEEE Computer Society Press, pp. 510--513.
• 15: WHITE, D. R., AND HARARY, F. The cohesiveness of blocks in social networks: Node connectivity and conditional density. Sociological Methodology 31, 1 (2001), 305--359.
• 16: WHITE, D. R., AND NEWMAN, M. Fast approximation algorithms for finding node-independent paths in networks. Research Report 01-07-035, Santa Fe Institute, March 2001.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: VLSI (very large scale integration)

Additional Classification:
  B. Hardware
  B.1 CONTROL STRUCTURES AND MICROPROGRAMMING
      B.1.4 Microprogram Design Aids
          Subjects: Optimization

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms

General Terms:
Algorithms, Design, Theory