ABSTRACT

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]. Top-down partitioning-based placement. https://s3-euw1-ap-pe-df-pch-content-public-u.s3.eu-west-1.amazonaws.com/9780429118173/8c5a6a55-2dd0-4f2d-82ee-b1dca6fa602d/content/fig15_1.tif" xmlns:xlink="https://www.w3.org/1999/xlink"/> The overall process of top-down placement is shown on the left. The placement area and netlist are successively divided into placement bins until the bins are small enough for end-case placement. One important enhancement to top-down placement is terminal propagation, shown on the right. The net in question has five fixed terminals: four above and one below the cutline. It also has movable cells, which are represented by the cell with a dashed outline. The four fixed terminals above the cutline are propagated to the black circle at the top of the bin while the one fixed terminal below the cutline is propagated to the black circle below the cutline. The movable cells remain unpropagated. Note that the net is inessential because terminals are propagated to both sides of the cutline. https://s3-euw1-ap-pe-df-pch-content-public-u.s3.eu-west-1.amazonaws.com/9780429118173/8c5a6a55-2dd0-4f2d-82ee-b1dca6fa602d/content/fig15_2.tif" xmlns:xlink="https://www.w3.org/1999/xlink"/> (From Roy, J. A. and Markov, I. L., IEEE Trans. CAD, 26, 632, 2007.)