Corolla based circuit partitioning and resynthesis

ABSTRACT

This paper introduces a circuit partitioning method based on analysis of reconvergent fanout. We consider a DAG model for a circuit. We define a corolla as a set of overlapping reconvergent fanout regions. We partition the DAG into a set of non-overlapping corollas and use the corollas to resynthesize the circuit. We show that resynthesis of large benchmark circuits consistently reduces transistor pairs and layout area while improving delay and testability.

REFERENCES

• 1: R. Brayton, R. Rudell, A. S&ngiovarmi-Vincentelll, and A. Wamg. MIS: A Multiple-Level Logic Optimization System. IEEE Transactions on Computer-Aided Design, cad- 6(6):1062- 1081, November 1987.
• 2: R. Lisanke, G. Kedem, and F. Brglez. DECAF: Decomposition and Factoring for Multi-Level Logic Synthesis. Technical report, Microelectronics Center of North Carolina, Research Triangle Park, NC, Augalst 1987.
• 3: J.A. Darringer, Jr. W.H.Joyner, C.L. Berman, and L. Trevillyan. Logic Synthesis Through Local Transformation. IBM Jornal of Research and Development, 25(4):272- 280, July 1981.
• 4: Daniel Brand. Redundancy and Don't Cares in Logic Synthesis. IEEE Trans. on Computers, C-32(10), October 1983.
• 5: Leonard Berman and Lousie Trevillyan. Improved Logic Optimization Using Global Flow Analysis. In IEEE International Con}erence on Computer-Aided Design, pages 102- 105, November 1988.
• 6: H. Cho, G. Hachtel, M. N&sh, and L. Setiono. BEAT_NP: A Tool for Partitioning Boolean Networks. In IEEE International ConJerence on Computer-Aided Design, pages 10- 13, November 1988.
• 7: R. Camposano and R. Brayton. PartitJioning before Logic Synthesis. In IEEE International Conference on Computer- Aided Design, pages 324 - 326, November 1987.
• 8: Fadi Ma&mari and Janusz Rajski. A Reconvergent Fanout Analysis for Efficient Exact Fault Simulation of Combinational Circuits. In 18th International Symposium on Fault Tolerant Computing, June 1988.
• 9: Sharad C. Seth , Vishwani D. Agrawal, A new model for computation of probabilistic testability in combinational circuits, Integration, the VLSI Journal, v.7 n.1, p.49-75, April 1989 [doi>10.1016/0167-9260(89)90059-X]
• 10: Thomas Lengauer , Robert Endre Tarjan, A fast algorithm for finding dominators in a flowgraph, ACM Transactions on Programming Languages and Systems (TOPLAS), v.1 n.1, p.121-141, July 1979 [doi>10.1145/357062.357071]
• 11: Sujit Dey, Franc Brglez, axtd Gershon Kedem. Corolla-based circuit partitioning and applications. Technical report, Microelectronics Center of North Carolina, Research Triangle Park, NC, May 1990.
• 12: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 13: R. Rudell. Multiple-ValuedLogic Minimization for PLA Synthesis. Technical report, University of California, Electronics Research Laboratory, Berkeley, CA, June 1986.
• 14: Robert Lisanke, Franc Brglez, and Gershon Kedem. McMAP: A Fast Technology Mapping Procedure for Multi- Level Logic Synthesis. In IEEE Int. Confi Computer Design, October 1988.
• 15: VPNR User Guide. Technical report, Microelectronics Center of North Carolina, Research Triangle Park, NC, 1988.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Automatic synthesis

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

General Terms:
Algorithms, Design