A neural network design for circuit partitioning

ABSTRACT

This paper proposes a neural network model for circuit bipartitioning. The massive parallelism of neural nets has been successfully exploited to balance the partitions of a circuit and to reduce the external wiring between the partitions. The experimental results obtained by neural nets are found to be comparable with that achieved by Fiduccia and Mattheyses algorithm.

References

1. 1.S. B. Akers, "Clustering techniques for VLSI," int. Symp. Circuit and Systems, pp. 472-476, 1982.
2. 2.M. A. Breuer, "A class of min-eut placement algorithms,'" Design Automation Conf., pp. 284-290, 1977.
3. 3.L. I. Corrigan, "'A placement capability based on partitionhag,'" Design Automation Conf., pp. 406---413, 1979.
4. 4.C. M. Fiduccia and R. M. Mattheyses, "A linear heuristic for improving network partitions," Design Automation Conf., pp. 175-181, 1982.
5. 5.H. P. Graf et al., "VLSI implementation of a neural network memory with several hundreds of neurons," Proceedings of the Conference on Neural Networks for Computing, Amer. Inst. of Phys., pp. 182-187, 1986.
6. 6.W.R. Heller, G. Sorkin, and K. Maling, "The planar package planner for system designers," Design Automation Conf., pp. 253-260, 1982.
7. 7.J. J. Hopfield, "Neural networks and physical systems with emergent collective computational abilities," Proc. Natl. Acad. Sci. USA, pp. 2554--2558, April 1982.
8. 8.J.J. Hopfield and D. W. Tank, "Neural computation of decisions in optimization problems," Biol. Cybern., pp. 141-152, 1985.
9. 9.B. W. Kernighan and S. Lin, "An efficient heuristic procedure for partitioning graphs," Bell System Technical Journal, vol. 49, pp. 291-307, February 1970.
10. 10.U. R. Kodres, "Partitioning and card selection," In Design Automation of Digital Systems, M. A. Breuer, editor, pp. 173-212, Prentice-Hall, 1972.
11. 11.B. Krishnamurthy, "An improved rain-cut algorithm for partitioning VLSI networks," IEEE Trans. Comput., vol. c-33, pp. 438-446, May 1984.
12. 12.W. S. McCulloch and W. H. Pitts, "A logical calculus of ideas immanent in nervous activity," Bulletin of Mathematical Biology, pp. 115-133, 1943.
13. 13.A. F~ Murry and A. V. W. Smith, "Asynchronous VLSI neural networks using pulse-stream arithmetic," IEEE J. Solid- State Circuits, vol. 23, no. 3, pp. 688-697, 1988.
14. 14.D. G. Schweikert and B. W. Kernighan, "A proper model for the partitioning of electrical circuits," Proc. 9th Design Automation Workshop, Dallas, pp. 57-62, 1979.
15. 15.M. A. Sivilotti, M. R. Emerling, and C. A. Mead, "VLSI architectures for implementation of neural networks," Proceedings of the Conference on Neural Networks for Computing, Amer. Inst. of Phys., pp. 408-413, 1986.

Index Terms

• Computer systems organization

  • Architectures

    • Parallel architectures

• Computing methodologies

  • Artificial intelligence

    • Knowledge representation and reasoning

  • Machine learning

• Hardware

  • Electronic design automation

    • Physical design (EDA)

  • Very large scale integration design

• Theory of computation

  • Logic