Jarrod A. Roy and Igor L. Markov

Over the years, partitioning-based placement has seen many revisions and enhancements, but the underlying framework illustrated in Figures 15.1 and 15.2 remains much the same. Top-down partitioning-based placement algorithms seek to decompose a given placement instance into smaller instances by subdividing the placement region, assigning modules to subregions, and cutting the netlist hypergraph [7,19]. The top-down placement process can be viewed as a sequence of passes where each pass examines all bins and divides some of them into smaller bins. The division step is commonly accomplished with balanced mincut partitioning, which minimizes the number of signal nets connecting modules in multiple regions [7]. These techniques leverage well-understood and scalable algorithms for hypergraph partitioning and typically lead to routable placements [9]. Recent work offers extensions to block placement, large-scale mixed-size placement [15,18,31] and robust incremental placement [33].

Variables: queue of placement binsInitialize queue with top-level placement bin1  While (queue not empty)2    Dequeue a bin3    If (bin small enough)4      Process bin with end-case placer5    Else6      Choose a cut-line for the bin7      Build partitioning hypergraph from netlist and cells         contained in the bin8      Partition the bin into smaller bins (generally via min-cut         bisection or quadrisection)9   ...