Degree Type


Date of Award


Degree Name

Master of Science


Electrical and Computer Engineering

First Advisor

Chris Chu


Placement is a very important and critical procedure during VLSI design. In this thesis, we propose a new force-directed quadratic placement algorithm called Minimum Cost Flow Based Fast Placement Algorithm(MCFPlace) for large-scale circuits. We mainly have three contributions:

(1) In this thesis, we propose a novel flow for global placement. The main idea is to generate a relatively good placement at very early stage during the iterations of quadratic program and addition of move force. After quadratic program, we apply a rough legalization technique to spread out the cells and some refinement techniques to generate a placement of good quality. We then use this placement as target positions and add move force to more effectively guide the movement of cells.

(2) In order to generate target positions of cells with very good quality, we first perform a rough legalization. we propose a new Minimum Cost Flow (MCF) based approach for rough legalization which spread the cell evenly over the whole placement region at a global level. The approach not only spreads cells at a global level, but also takes the wirelength into consideration.

(3) Furthermore, we incorporate some refinement techniques after Minimum Cost Flow based approach. We propose a novel slice based refinement technique and incorporate the iterative local refinement(ILR) technique to further improve the quality of

placement of target positions of cells. By doing this, we can have a more accurate move force to more effectively guide the cell movements at the very early stage which will have a great impact on the final quality of placement.

Our placer is 1% better than RQL, 1:35% better than SimPL, 3:5% better than mPL6, 4% better than FastPlace3 in terms of wirelength for ISPD05 benchmark suites. On runtime our placer is 1.5 times faster than RQL and 4.4 times faster than mPL6. Though we are 1.3 percent worse than the current best placer Maple in terms of wirelength, our algorithm is 4 times faster than Maple.

Copyright Owner

Enlai Xu



File Format


File Size

55 pages