Cluster-cover: a theoretical framework for a class of VLSI-CAD optimization problems

ABSTRACT

This article introduces a mathematical framework called cluster-cover. We show that this framework captures the combinatorial structure of a class of VLSI design optimization problems, including two-level logic minimization, constrained encoding, multilayer topological planar routing, application timing assignment for delay-fault testing, and minimization of monitoring logic for BIST enchancement. These apparently unrelated problems can all be cast into two metaproblems in our framework: finding a maximum cluster and finding a minimum cover. We describe paradigms for developing algorithms for these problems. First, a simple heuristic called greedy peeling is presented and characterized. We derive sufficient conditions that guarantee optimum solutions by greedy peeling. We generalize the performance analysis of a multilayer topological planar routing heuristic to greedy peeling for the general cluster-cover problems. We propose a performance bound of greedy set covering that can be computed efficiently for a given problem instance; this bound is much tighter than the previously known bounds. Second, prime covering—orignally developed for logic minimization—is generalized to finding exact solutions for cluster-cover problems. Previously, only the connection between logic minimizaton and constrained encoding was known.

REFERENCES

• 1: Robert King Brayton , Alberto L. Sangiovanni-Vincentelli , Curtis T. McMullen , Gary D. Hachtel, Logic Minimization Algorithms for VLSI Synthesis, Kluwer Academic Publishers, Norwell, MA, 1984
• 2: CHVATAL, V.1979. A greedy heuristic for the set covering problem. Math. Oper. Res. 4, 233-235.
• 3: CONG, J., HOSSAIN, M., AND SHERWANI, N.A. 1993. A provably good multilayer topological planar routing algorithm in IC layout designs. IEEE Trans. Comput. Aided Des. 12, 1 (Jan.), 70-78.
• 4: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 5: O. Coudert , J. C. Madre, Implicit and incremental computation of primes and essential primes of Boolean functions, Proceedings of the 29th ACM/IEEE conference on Design automation, p.36-39, June 08-12, 1992, Anaheim, California, United States
• 6: Olivier Coudert , Jean Chritophe Madre, New ideas for solving covering problems, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.641-646, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217603]
• 7: COUDERT, O. AND SHI, C.-J. 1996a. Exact multi-layer topological planar routing. In Proceedings of the IEEE Custom Integrated Circuit Conference (CICC'96) (San Diego, CA, May 5-8), 179-182.
• 8: Olivier Coudert , C.-J. Richard Shi, Exact Dichotomy-based Constrained Encodi, Proceedings of the 1996 International Conference on Computer Design, VLSI in Computers and Processors, p.426-431, October 07-09, 1996
• 9: FAIGLE, U. 1979. The greedy algorithm for partially ordered sets. Discrete Math. 28, 153-159.
• 10: G(~SSEL, M. AND JURGENSEN, H. 1993. Monitoring BIST by covers. In Proceedings of Euro- DAC'93--European Design Automation Conference (Hamburg, Germany, Sept.) 208-213.
• 11: IYENGAR, V. S. AND VIJAYAN, G. 1992. Optimized test application timing for AC test. IEEE Trans. Comput. Aided Des. 11, 11 (Nov.), 1439-1449.
• 12: JOHNSON, D. S. 1974. Approximating algorithms for combinatorial problems. J. Comput. Syst. Sci. 9, 256-278.
• 13: Zvi Kohavi , Richard W. Hamming , Edward A. Feigenbaum, Switching and Finite Automata Theory: Computer Science Series, McGraw-Hill Higher Education, 1990
• 14: KORTE, B. AND LOVASZ, L. 1984. Greedoids--A structural framework for the greedy algorithm. In Progress in Combinatorial Optimization, W. Pulleyblank, Ed., Academic Press, New York, NY, 221-243.
• 15: B. Lin , O. Coudert , J. C. Madre, Symbolic prime generation for multiple-valued functions, Proceedings of the 29th ACM/IEEE conference on Design automation, p.40-44, June 08-12, 1992, Anaheim, California, United States
• 16: LOVASZ, L. 1975. On the ratio of optimal integral and fractional covers. Discrete Math. 13, 383-390.
• 17: Carsten Lund , Mihalis Yannakakis, On the hardness of approximating minimization problems, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.286-293, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167172]
• 18: Patrick McGeer , Jagesh Sanghavi , Robert Brayton , Alberto Sangiovanni Vincentelli, Espresso-signature: a new exact minimizer for logic functions, Proceedings of the 30th international conference on Design automation, p.618-624, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.165069]
• 19: Shin-ichi Minato, Zero-suppressed BDDs for set manipulation in combinatorial problems, Proceedings of the 30th international conference on Design automation, p.272-277, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.164890]
• 20: NOWICK, S. M. AND DILL, D.D. 1995. Exact two-level minimization of hazard-free logic with multiple-input changes. IEEE Trans. Comput. Aided Des. 14, 8 (Sept.), 986-997.
• 21: RUDELL, R. L. AND SANGIOVANNI-VINCENTELLI, A.L. 1987. Multiple-valued minimization for PLA optimization. IEEE Trans. Comput. Aided Des. 6, 5 (Sept.), 727-750.
• 22: Alexander Saldanha , Tiziano Villa , Robert K. Brayton , Alberto L. Sangiovanni-Vincentelli, A framework for satisfying input and output encoding constraints, Proceedings of the 28th conference on ACM/IEEE design automation, p.170-175, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127656]
• 23: Chuan-Jin Shi, Optimum logic encoding and layout wiring for vlsi design: a graph-theoretic approach, 1994
• 24: SHI, C.-J. 1997. Block-level fault isolation using partition theory and logic minimization techniques. In Proceedings of the Asia and South Pacific Design Automation Conference (ASP-DAC'97) (Chiba, Japan, Jan.), 319-324.
• 25: SHI, C.-J. AND BRZOZOWSKI, J.A. 1993. An efficient algorithm for constrained encoding and its applications. IEEE Trans. Comput. Aided Des. 13, 12 (Dec.), 1813-1826.
• 26: C.-J. Shi , J. A. Brzozowski, A framework for the analysis and design of algorithms for a class of VLSI-CAD optimization problems, Proceedings of the 1995 conference on Asia Pacific design automation (CD-ROM), p.12-es, August 29-September 01, 1995, Makuhari, Massa, Chiba, Japan [doi>10.1145/224818.224843]
• 27: TRACEY, g.H. 1966. Internal state assignment for asynchronous sequential machines. IEEE Trans. Electron. Comput. (Aug.), 551-560.
• 28: Stephen H. Unger, Asynchronous Sequential Switching Circuit, Krieger Publishing Co., Inc., Melbourne, FL, 1983
• 29: YANG, S. AND CIESIELSKI, M. g. 1991. Optimum and suboptimum algorithms for input encoding and its relationship to logic minimization. IEEE Trans. Comput. Aided Des. 10, 1 (Jan.), 4-12.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Design, Theory

Keywords:
NP-completeness, cluster-cover, logic minimizaiton, self-checking logic design, state assignment, topological routing