Feature Benchmarks for Placement

fixed terminals are placed on the periphery of the core area. A movable cell is tied via a two-pin edge to each fixed terminal along the boundaries of the core area. The unique optimal solution entails placing each movable cell directly adjacent to the terminal it is tied to. This optimal solution is unique because every net achieves minimum possible wirelength, and one end of the net is fixed. The simple strategy of placing every cell, one by one, so as to minimize the total length (linear or squared) of adjacent nets will find the optimal placement in one linear-time pass. However, we are going to show that existing VLSI placers are less successful. In principle, a poor global placement of this benchmark may be vastly improved by a detail placer that moves one cell at a time, but the success somewhat depends on the given global placement. This benchmark is parameterized by the height and width of the core area, and optimal wirelength is given by 2*(height+width).

is constructed similarly to (a), only now the fixed I/O pads are arranged in an array throughout the core area. Cells cannot be rotated/flipped, and non-trivial pin offsets force a unique optimal solution in which each net achieves minimum possible wirelength. This benchmark checks placers for compatibility with flip-chip packaging and is parameterized by the height and the width of the I/O array, the optimal wirelength is given by 1.5*height*width, due to pin offsets.

is designed to force optimal solutions to the boundary of the core area. There are only four fixed terminals, one in each corner. Each movable cell is assigned to one of the four edges of the core area by being connected to each corner adjacent to that edge. Note that any position along that edge is equally good from the HPWL perspective, and all optimal solutions place cells along their respective edges. Optimality can be proven by demonstrating achieved lower bounds for pairs of nets connected to a given cell --- the total length of such a pair cannot be shorter than the distance between the two fixed terminals. This benchmark is parameterized by the height and width of the core area, as well as the number of inputs on each side of the core area. The optimal wirelength, in HPWL, is given by (top+bottom)*(width+3) + (left+right)*(height+3).

is a large cross connecting four groups of fixed peripheral terminals. The cells are arranged and connected as a grid. This design typically has a great deal of whitespace, optimally placed in the corners of the core area. Every net in this design achieves minimum possible wirelength, making the placement optimal. Uniqueness can be proven by considering lower bounds for paths or nets that are entirely vertical or entirely horizontal in this optimal placement --- any other placement would not match some of these lower bounds. This design is parameterized by the height and width of the core area, the height and width of the arms of the cross, and the horizontal and vertical offset for the arms of the cross. The optimal wirelength is given by cross_height*(width+1)+cross_width*(height+1)+(height-cross_height)*(cross_width-1)+(width-cross_width)*(cross_height-1).

is similar to the cross, but now we only keep the intersection of the two arms of the cross. The movable cells are tied to the boundaries of the core area in the center by long nets. The cells in the center are placed optimally, because every net in the center has minimum possible wirelength. In both the vertical and horizontal directions paths of nets connect top to bottom, and left to right. In any other placement, a path is no shorter than the distance between fixed end-terminals of the path. A placement that achieves all these lower bounds must be optimal, and it is easy to see that there is only one such placement. This design is parameterized by height and width of the core area, height and width of the blob, and vertical and horizontal offset for the blob. The optimal wirelength can be given by (1+height)*blob_width+(width+1)*blob_height.

is a somewhat larger and more difficult version of (a) that adds four-pin hyperedges and non-trivial pin offsets. Each terminal is connected by one two-pin edge to a group of four movable cells (kite), connected to each other by a four-pin hyperedge. Non-trivial pin offsets force a unique optimal relative placement of each four-cell group. In a unique overall optimal placement, every net achieves its minimum possible wirelength. While the PerifIO is intuitively easy for a move-based detail placer, a poorly-placed kite cannot be relocated by single-cell moves each of which improves wirelength. This benchmark is parameterized by the number of kites in the vertical and horizontal directions (height and width). The optimal wirelength is given by 4*(height+width)-4.

is a design with 15% whitespace and a large fixed obstacle in the center. The specification leaves out the sites which are covered by the obstracle, making it easier to prevent overlaps. This benchmark tests if a placer can handle non-trivial obstacle shapes and dimensions. Every legal placement is optimal because the benchmark has no wires.

is a combination of (e) and (g), where the obstacle forces the blob to be placed off the center. This benchmark challenges the placer to find legal sites without losing much wirelength. Optimal solutions are in a central vertical band, with smallest offsets from the center. Depending on whether the obstacle is interpreted as porous or not (i.e., allowing transit wires to be routed through it), some placements may incur a greater wirelength after routing. If the porous case, the blob may be split vertically and placed above and below the obstacle. The optimal wirelength is then given by (height+1)*blob_width.

is constructed from a 0%-whitespace regular grid shown in the Introduction by merging random pairs of neighboring cells and removing connecting wires. This produces cells of varying sizes, but a more controlled construction produces regular brickwalls with identical 1xN bricks. We use irregular brickwalls in which two-pin nets connect neighboring bricks horizontally and vertically. These benchmarks test the placement of densely-packed layouts where cells are not 1x1 (as assumed by early versions of several academic placers). Additionally, irregular brickwalls drastically reduce the possibility of permuting cells to improve wirelengths --- a straightforward optimization technique that does not apply to realistic netlists. Brickwalls tend to have unique solutions up to symmetry (because fixed pads are disconnected), but can also test if a placer respects cell orientation constraints specified in DEF or the GSRC Bookshelf format. While the optimality of constructed placements is due to each net's achieving optimal length, our randomized construction prevents exact analytical formulas for optimal wirelength.