VLSI cell placement techniques

The VLSI cell placement problem is known to be NP-complete. This paper presents a survey of the various approaches and techniques for this problem. It also gives a comprehensive tutorial on the subject, providing an excellent introduction to the terminology and classification of placement algorithms. With the growing diversity of the terms appearing in the literature, I found the explicit warning about synonymous usage of words like module, cell, and element or net, wire, and interconnect to be helpful. The placement algorithms whose emphasis is on standard cell and macro placement fall into five groups, according to their underlying technique: (1) simulated annealing, (2) force-directed, (3) minimum-cut, (4) numerical optimization, and (5) evolution based. The origins of the first two are in physical laws.