Research On Performance Driven Force-Directed Placement Algorithms

As VLSI technology advances into the nanometer era, it has become of a keyissue in the physical design that developing the high quality placer and how to handlethe problem of the multiobjectives optimization of placement such as wire-length,power, timing, clock and so on for the high performance circuits. In recent years, bythe analytical approaches, the quadratic force-directed placement algorithms arepopular in academic and industry research because they allow good quality results atlow CPU times. Based on these force-directed placers, this dissertation investigatesthe algorithms on performance driven placement about the model density smoothingmethod and the clock driven placement under timing constraint.The main works are as follows:1. A new model density smoothing method of placement is proposed. By thewirelength to be considered while moving the modesl for low overlap, this densitysmoothing method can maintain the relative coordination among models during theprocess of placement, relieve the forces unbalance of the models and reduce thedamage to the wirelength, moreover, the model moving distances are determined bycombination of the global density distribution and local density difference. Theexperiments results show that a better initial condition is built for the quadraticprogram and the placement quality is obviously improved.2. A clock driven placement algorithm based on the backbone of the clocknetwork is proposed. Firstly, a clock driven placement algorithm flow is proposed,and under the backbone of the clock network, the optimization measure for the clockis targeting on the future clock tree; then, based on this flow, additional forces areadded directed by Manhattan ring to influence the clock sink distribution, andconcurrently a timing driven placement algorithm by adjusting the net weight isproposed. The experiments results show that the clock network is greatly improved.3. A clock driven placement algorithm based on the dynamic topo of clock network is proposed. The clock topo is built by way of the top-down partitioning andthe bottom-up clustering and can be adjusted according to the distribution of the clocksinks; the pseudo nets are added to the bottom clusters in order to guide thedistribution of the clock sinks, the cluters and pseudo nets can also be adjustedaccording to the distribution of the clock sinks; concurrently, the models of theselected subcircuits are preassigned to the new locations for a good timing based onlinear programming. The experiments results show the clock network is improvedbetter than the last algorithm.