A classification of algorithms used for placement in structured layout is proposed. The mathematicd roots of popular placement techniques are investigated and their relations with classical combinatorial problems established. New facts about hnown heuristics are proved and new heuristics introduced. //7 conclusion, a comparison of the performance of different heuristics is made for real designs and the application of several algorithms to the same problem recommended as a means for improving the quality of the results. VLSI design, olgorlthms, heuristics, placement, routing Most VLSI designs are currently implemented in a gate array or standard cell style 1'2. These styles are characterized by a row (column) organization of layout.
Traditionally, layout problems are decomposed into two distinct steps, namely, placement and routing. The placement step defines the positions of elements on the carrier and the routing step defines their interconnections. As an objective function for layout, either the resulting length of interconnections or the area required by layout is used.
Of the two steps in the layout process, routing has attracted more attention and has been developed more. The cause of this is partly rooted in the relative simplicity of the definition of the routing problem and the relative complexity of the formulations of the placement problem, which occupies a higher hierarchical level in the layout process.
But the optimal solution of the placement problem has a more significant effect on the resulting layout than the difference in routing techniques. In this paper, it is shown that the difference in placement may easily result in a variation of 40-60% in the chip size.
Several heuristic algorithms are widely applied for placement in a structured environment 1-4. But it has not been previously demonstrated how these heuristics can be derived from accurate models and what types of simplified assumptions were actually made for them.
A study of mathematical models for placement in a structured environment also reveals that one obvious group of heuristic methods is currently missing from the set of heuristic approaches. This heuristic is the direct counterpart of the min-cut algorithm. The authors named it max-con (which means maximum connectivity) and included it in the set of investigated heuristics. In this paper, the most popular heuristics are explained and some new ones introduced from the point of view of more general models.
Two series of experiments were conducted with real-life designs. Several different placement heuristics were used and the results compared. Recommendations are made derived from the results of the experiments.