feng shui 5.0: Placement Engine

Feng Shui supports two main placement approaches: a recursive bisection method, and a new "beacon" technique that is optimized for circuits with a great deal of structure. The bisection based tool is stable, and is suitable for most standard cell designs; the beacon technique is being actively developed, and currently only performs well on the PEKO benchmarks produced at UCLA. Details of the placement approaches can be found in our technical papers.

Usage:

To perform placement using the GUI version of the tool, simply load in a design (using the buttons in the I/O toolbox), then apply the type of placement approach desired using the buttons in the placement toolbox. While the placement tool is running, details are logged to a scrolling window. Cell movement can be observed by selecting the features you wish to display, and periodically refreshing the display window. Feng Shui is multi-threaded; thus, the display is "live," and you can track cell motion while the tool runs. For some machines (particularly slower ones), it's possible for the display to freeze. There appears to be an issue with X11 events getting handled correctly, especially when the machine is heavily loaded. The command line version supports a larger range of options. Commonly used ones are as follows.

-aux bookshelf.aux
The command line version only supports Bookshelf format input files.
-aspect #
A floating point number to control the aspect ratio used during bisection. Please see our paper on cut sequences for more detail.
-cdr
Turns on congestion driven placement. This is in beta mode, and is not fully supported.
-hm_group #
Defines the number of random starts of hMetis each time a partition is required. By default, this is 10.
-hm_passes #
Defines the number of passes of partitioning; this is similar to the "cycles" idea used in the QUAD placement tool from Huang and Kahng, or the Feedback idea added to Capo by Reda and Kahng. By default, this is 3.
-nosoftcut
Turns off fractional cut lines; regions are aligned to rows as is done in traditional bisection based tools. This results in a roughly 5% degredation in results, and is not recommended. Details of this technique are given in our ICCAD fractional cut paper.
-legal string

Post Processing Tools

Feng Shui can be used as a stand-alone placement legalizer and detailed placement engine. Two main legalization techniques are currently supported.

For standard cell designs, we use a dynamic programming based technique that extends the method described in our ICCAD fractional cut paper. Details of this method have not been published.
For designs with a mix of macro blocks and standard cells, we use the method described in our ISPD mixed size placement paper. Note: for standard cells, the technique is similar to a method developed by Dwight Hill, and patented by Synopsys; for this reason, we do not use it for standard cell designs. Mixed size designs were not considered within the Synopsys patent.

For historical reasons, the string used to legalize both types of placements is "M,-1,1". The capitalization, commas, and so on, are significant. Our detailed placement engine parses this string, and uses the letters to select specific algorithms to apply. Feng Shui also supports single and multi-row branch-and-bound window based optimization. A small sliding window passes over the design, performing brute force local optimization for wire length minimization. For historical reasons, the string used to perform detail placement improvement is "r,#,#." The first number indicates the total number of cells within an optimization window, while the second indicates the number of rows to consider in the window. To legalize or improve a placement in the file sample.pl, one could apply the following:

fs50placer -aux bookshelf.aux -loadpl sample.pl -postproc -reorder "M,-1,1"
This loads in the circuit net list from bookshelf.aux, followed by loading in the non-legalized placement in sample.pl. The -postproc flag indicates that bisection is not to be used: instead, only the detail placement engine is called. It applies the appropriate legalization step, and saves the resulting placement in "bookshelf_fs50.pl".
fs50placer -aux bookshelf.aux -loadpl sample.pl -postproc -reorder "r,6,2"
If the placement is legalized, wire length can be improved by performing a single pass of branch-and-bound optimization. This example loads in the circuit net list from bookshelf.aux and then reads sample.pl. The optimization window considers 6 standard cells at a time, two rows at a time--on average, there will be three cells in each row, but this can vary if cell sizes differ.
fs50placer -aux bookshelf.aux -loadpl sample.pl -postproc -reorder "M,-1,1:r,6,3:r,6,3:r,6,2:r,6,2:r,6,1:r,6,1"
Commands to the detail placement engine can be separated by colons; this example first applies placement legalization, and then a number of passes of detail placement improvement, with changing window sizes.