A timing-driven data path layout synthesis with integer programming

ABSTRACT

We propose an efficient data path synthesis algorithm which generates bit-sliced layouts. Since data path circuits have special characteristics which are different from those of random logic circuits, the dedicated synthesis system is required for efficient layouts. Our main goal in the data path synthesis is to satisfy the timing constraints of circuits as well as to reduce layout areas. Timing-driven placement and over-the-cell routing techniques are developed to generate data path modules. Also, signal interfaces between bit-slices are carefully considered to further reduce layout areas. Our synthesis techniques take advantage of the common characteristics of data path structures under timing constraints and applies mixed integer linear programming approach to solve the problem. The superior results from our data path synthesis system are demonstrated through comparison with the layout results with the simulated annealing technique.

REFERENCES

• 1: H. Cai , S. Note , P. Six , H. De Man, A data path layout assembler for high performance DSP circuits, Proceedings of the 27th ACM/IEEE conference on Design automation, p.306-311, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123284]
• 2: M. Shiochi et al., ~New design approach for configurable data-path," Proc. 1990 CICC, pp. 14.5.1-4, 1990.
• 3: Y. Tsujihashi et al.,~A high-density data-path generator with switchable cells," IEEE Y. Solid-State Circuits, pp. 2-8, Jan. 1994.
• 4: T. Gao , P. M. Vaidya , C. L. Liu, A performance driven macro-cell placement algorithm, Proceedings of the 29th ACM/IEEE conference on Design automation, p.147-152, June 08-12, 1992, Anaheim, California, United States
• 5: S. M. Kang and Y. Leblebichi, ~CMOS digital integreated circuits: analysis and design," McGraw Hill, 1995.
• 6: W. C. Elmore, ~The transient response of damped linear networks with particular regard to wideband amplifier," Y. Applied Physics, vol. 19, Jan. 1948.
• 7: M. A. B. Jackson , E. S. Kuh, Performance-driven placement of cell based IC's, Proceedings of the 26th ACM/IEEE conference on Design automation, p.370-375, June 25-28, 1989, Las Vegas, Nevada, United States [doi>10.1145/74382.74444]

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Integer programming

General Terms:
Measurement, Performance, Theory

Keywords:
data path, bit-slice, timing-driven placement, routing, integer programming