In this paper we present a novel formulation for the net-based timing-driven placement problem. The new formulation performs budgeting #net delay upper bounds# and placement modi#cation simultaneously thus alleviates the problem of going back-and-forth between budgeting and placement. An algorithm to accomplished the proposed task is presented. The proposed algorithm uses a simulated annealing approach and a modi#ed graph-based simplex method. A general formulation of timing-sriven placement is presented. It is proved that both net-based and path-based approaches to timing-driven placement are special cases of a more general formulation. The proposed algorithm has been incorporated into a #timing-driven# placement package. Experiments on MCNC benchmarks show strong results. The proposed algorithm o#ers 54# to 68# reduction over the longest path compared with the existing algorithms. 1. INTRODUCTION Timing-driven placement is a problem that is becoming increasingly important in VLSI d...

In this paper, we present a new, general approach to the problem of computing upper bounds on net delays. The upper bounds on net delays are computed so that timing constraints between input and output signals are satisfied. The set of delay upper bounds is called a delay budget. The objective of this work is to compute a delay budget that will lead to timing feasible circuit placement and routing. In our formulation, we find a delay budget so that the placement phase has "maximum flexibility." We formulate this problem as a convex programming problem and prove that it has a special structure. We utilize the special structure of the problem to propose an efficient graph-based algorithm. We present experimental results for our algorithms with the MCNC placement benchmarks. Our experiments use budgeting results as net length constraints for the TimberWolf placement program, which we use to evaluate the budgeting algorithms. We obtain an average of 50% reduction in net length constraint violations over the well-known zero-slack algorithm (ZSA). We also study different delay budgeting objective functions, which yield 2/spl times/ performance improvements without loss of solution quality. Our results and graph-based formulation show that our proposed algorithm is suitable for modern large-scale budgeting problems.