VLSI: placement based on routing and timing information

ABSTRACT

In this paper we propose a hierarchical placement procedure incorporating more and more detailed routing and timing information at increasing levels of the hierarchy. This procedure is based on the well-known min-cut method. A global routing and a timing analysis are computed after every cut and are used to guide the subsequent cell partitioning.

REFERENCES

• 1: M. Breuer: Min-cut placement, J. Design Automation and Fault Tolerant Computing, Vol.1, 1977, 343--362.
• 2: M. Burstein, S. J. Hong, and R. Pelavin: Hierarchical VLSI layout: Simultaneuos Placement and Wiring of Gate Arrays, Proc. IFIP VLSI-83, 1983.
• 3: Michael Burstein , Mary N. Youssef, Timing influenced layout design, Proceedings of the 22nd ACM/IEEE conference on Design automation, p.124-130, June 1985, Las Vegas, Nevada, United States [doi>10.1145/317825.317845]
• 4: A. E. Dunlop and B. W. Kernighan: A procedure for placement of standard cell VLSI circuits, IEEE Trans. Computer-Aided Design, vol. CAD-4, 1985, 92--98.
• 5: 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
• 6: R. B. Hitchcock, G. L. Smith, and D. D. Cheng: Timing analysis of computer hardware, IBM J. Res. Develop., vol. 26, 1982, 100--105.
• 7: B. W. Kernighan and S. Lin: An efficient heuristic procedure for partitioning graphs, Bell Syst. Tech. J., vol. 49, 1970, 291--307.
• 8: G. Koetzle: System implementation on a highly structured VLSI master image, In: W. E. Proebster and H. Reiner (eds.): Proceedings VLSI and Computers, IEEE, 1987, 604--609.
• 9: B. Korte, H. J. Prömel and A. Steger: Combining partitioning and global routing in sea-of-cells design, Proc. Int. Conf. Computer-Aided-Design, 1989, 98--101.
• 10: B. Korte, H. J. Prömel and A. Steger: Steiner trees in VLSI-layout, to appear in: Korte, Lovász, Prömel, Schrijver (eds.): Paths, Flows and VLSI-Layout. Algorithms and Combinatorics, Vol. 7, Springer Verlag, 1989.
• 11: D. La Potin and S. W. Director: Mason: A global floorplanning approach for VLSI design, IEEE Trans. Computer-Aided-Design, vol. CAD-5, 1986, 477--489.
• 12: U. Lauther: A min-cut placement algorithm for general cell assemblies based on a graph representation, Journal of Digital Systems, vol. IV, 1980, 21--34.
• 13: R. Nair, C. L. Berman, P. S. Hauge and E. J. Yoffa: Generation of performance constraints for layout, IEEE Trans. Computer-Aided-Design, vol. CAD-8, 1989, 860--874.
• 14: Wilhelm G. Spruth, The design of a microprocessor, Springer-Verlag New York, Inc., New York, NY, 1989
• 15: P. R. Suaris and G. Kedem: An algorithm for quadrisection and its application to standard cell placement, IEEE Trans. Circuits Syst., vol. 35, 1988, 294--303.
• 16: P. R. Suaris and G. Kedem: A quadrisection-based combined place and route scheme for standard cells, IEEE Trans. Computer-Aided-Design, vol. CAD-8, 1989, 234--244.