A new simultaneous circuit partitioning and chip placement approach based on simulated annealing

ABSTRACT

The problems of circuit partitioning and chip placement have been studied in the past. Given a circuit partitioned into chips, one can optimize the placement of the chips on a printed circuit board with regard to a given cost function. Conversely, given a placement of the chips on the board, one can optimize the partitioning of the circuit into the chips with regard to the same cost function. However, given neither the circuit partitioning nor the chip placement, we are faced with a difficult optimization problem. Our target technology is one in which the chips are unpackaged chips placed on a substrate, analogous to the printed circuit board and interconnected together with high density interconnect to realize a complex system. We propose a new approach in which the circuit is both partitioned and placed simultaneously by a simulated annealing based algorithm. Our approach is seen to yield excellent results in reasonable run times.

REFERENCES

• 1: S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, "Optimization by Simulated Annealing," Science 220 pp. 67t-680 (1983).
• 2: B. Kernighan and S. Lin, "An Efficient Heuristic for Partitioning Graphs," Bell System Technical Journal, pp. 291-307 (1970).
• 3: C. M. Fiduccia , R. M. Mattheyses, A linear-time heuristic for improving network partitions, Proceedings of the 19th conference on Design automation, p.175-181, January 1982
• 4: B. Krishnamurthy, "An improved Min-Cut Algorithm for Partitioning VLSI Networks," 1EEE Transactions on Computers, pp. 438-446 (1984).
• 5: C. Sechen, "VLSI Placement and Global Routing Using Simulated Annealing," Kluwer Academic Publishers, (1988).
• 6: D. F. Wong , H. W. Leong , C. L. Liu, Simulated annealing for VLSI design, Kluwer Academic Publishers, Norwell, MA, 1988
• 7: R. Hartley and J. R. Jasica, "Behavioral to Structural Translation in a Bit-Serial Silicon Compiler," IEEE Transactions on Computer-Aided Design 7, No 8pp. 877-886 (August 1988).
• 8: Richard I. Hartley , Peter F. Corbett, A digit-serial silicon compiler, Proceedings of the 25th ACM/IEEE conference on Design automation, p.646-649, June 12-15, 1988, Atlantic City, New Jersey, United States

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Layout

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

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

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

General Terms:
Design, Performance