A timing-driven floorplanning algorithm with the Elmore delay model for building block layout

This paper presents a timing-driven floorplanning algorithm for building block layout. As the interconnection delay model, the proposed algorithm adopts the Elmore delay model. The algorithm consists of two phases. In the first phase, a timing-driven topological arrangement of blocks is generated with the resolution of overlap among blocks using nonlinear programming under the timing constraints. In the second one, the algorithm performs floorplan sizing which determines the sizes and the shapes of blocks based on the topological arrangement obtained in the first phase so as to minimize the chip area, and obtains a legal floorplan. This phase is based on the topological constraint manipulation. Through the experimental results, the proposed algorithm can produce results without any timing violations within a practical computation time. (C) 1999 Elsevier Science B.V. All rights reserved.