Gate sizing for cell library-based designs

ABSTRACT

With increasing time-to-market pressure and shortening semiconductor product cycles, more and more chips are being designed with library-based methodologies. In spite of this shift, the problem of discrete gate sizing has received significantly less attention than its continuous counterpart. On the other hand, cell sizes of many realistic libraries are sparse, for example, geometrically spaced, which makes the nearest rounding approach inapplicable as large timing violations may be introduced. Therefore, it is highly desirable to design an effective algorithm to handle this discrete gate sizing problem.

Such an algorithm is proposed in this paper. The algorithm is a continuous solution guided dynamic programming approach. A set of novel techniques, such as Locality Sensitive Hashing based solution selection and stage pruning, are also proposed to accelerate the algorithm and improve the solution quality. Our experimental results demonstrate that (1) nearest rounding approach often leads to large timing violations and (2) compared to the well-known Coudert's approach, the new algorithm saves 9% -- 31% in area cost while still satisfying the timing constraint.

REFERENCES

• 1: J. Fishburn and A. Dunlop, "Tilos: A posynomial programming approach to transistor sizing," in ICCAD, pp. 326--328, 1985.
• 2: C.-P. Chen, C. Chu, and D. Wong, "Fast and exact simultaneous gate and wire sizing by lagrangian relaxation," TCAD, vol. 18, no. 7, pp. 1014--1025, 1999.
• 3: Olivier Coudert, Gate sizing for constrained delay/power/area optimization, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.5 n.4, p.465-472, Dec. 1997 [doi>10.1109/92.645073]
• 4: W. Chuang, S. Sapatnekar, and I. Hajj, "Delay and area optimization for discrete gate sizes under double-sided timing constraints," CICC, 1993.
• 5: Frederik Beeftink , Prabhakar Kudva , David Kung , Leon Stok, Gate-size selection for standard cell libraries, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.545-550, November 08-12, 1998, San Jose, California, United States [doi>10.1145/288548.289084]
• 6: Aristides Gionis , Piotr Indyk , Rajeev Motwani, Similarity Search in High Dimensions via Hashing, Proceedings of the 25th International Conference on Very Large Data Bases, p.518-529, September 07-10, 1999
• 7: K. Kasamasetty, M. Ketkar, and S. S. Sapatnekar, "A new class of convex functions for delay modeling and its application to the transistor sizing problem," TCAD, vol. 19, no. 7, pp. 779--788, 2000.
• 8: J. Buhler, "Efficient large-scale sequence comparison by locality-sensitive hashing," Bioinformatics, vol. 17, no. 5, pp. 419--428, 2001.

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING

General Terms:
Algorithms, Design, Performance

Keywords:
dynamic programming, gate sizing