FlowPlace: A Timing-Driven Incremental Placer
Using A Network-Flow Based Approach
Shantanu Dutt, Huan Ren DART Lab @ECE Dept. UIC
This material is based upon work supported by the National Science Foundation under Grant No. 0204097
This web site is for publishing latest benchmarks and placement results of our timing-driven incremental placement algorithm for standard cell placement. This web is currently maintained by Huan Ren (email@example.com). If you have any questions or suggestions, please contact him.
The use of codes, benchmarks, results of this site are given under the following agreement:
1) Only non-commercial, not-for-profit use of this software is permitted. The benchmark and program here should not be
commercially used without the written agreement and consent of Professor Shantanu Dutt (firstname.lastname@example.org)
2) None of the codes shall be disassembled or any attemps made to extract their source in any way.
3) All users who download the benchmarks or codes agree not to redistribute their copy to anyone or anywhere
4) Any report or paper that makes use of these benchmarks and/or codes are requested to cite both
this website and the reference papers  listed below which further explain the techniques and benchmarks.
◆ Benchmarks and Results
There are two sets of benchmarks here: IBM and Faraday. These two benchmarks can not be used in timing-driven placement directly because they did not specify Flip-Flop. There will be cycles when doing STA. To cope with this problem, we artificially identify a suitable number of flip-flops. The choosing of Flip-Flops is based on two criteria:
1. Breaking all cycles with as few number of FFs as possible
2. There should not be too long path.
The FF determination is a two step procedure.
a) Identify cycles in a circuit using DFS, find the cell that belongs to max number of cycles, mark it as a register. Then identify cycles again, mark another cells that belongs to max number of cycles. Do this until all cycles are broken.
Do a DFS on the cycle free circuit. Check length of each path.
When it exceeds 180 cells, begin to look for potential FFs (e.g. cells with
aspect ratio bigger than one and no more than three inputs) as DFS continues on
the path. If any is found along the path, mark it as registers. If no potential
FFs are found till the 220th cell, mark that cell as register. This
ensures that the longest path won’t exceed 220, but not all long paths
have 220 cells (
Since our program can only deal with standard cell placement, we also substitute the macros in the two benchmarks with cells of standard height and an aspect ratio of 4:1. This change makes the layout of the new benchmarks much smaller than the original ones, so the original fixed I/O pin positions in the layout are not suitable here. Therefore, these pins are removed in our benchmarks. (The Dragon version of the IBM benchmark removes both the pin and macro cells, which results in many nets with more than one driving pin, so we do not use their benchmarks.)
Each benchmark has four files .nodes file, .nets file, .par file and two .pl files.
.nodes: contains the size of each cell, the total number of cells and information of whether a cell is a FF or not (“FF” after cell size means Flip-Flop, “nFF” means not Flip-Flop).
.nets: specify the input and out cells of each nets and total number of nets.
.par: specify the technical parameters for STA, including: driving resistance (Rd), load capacitance (Cg), unit wire resistance (r), unit wire capacitance (c) and length unit which explains unit length of the benchmark is how many micro meters (unit).
.pl: specify the (x. y) coordinates of each cell. There are two .pl file: one is the placement results of Dragon (has “Dragon” in its name); one is our incremental placement results.
Please read the above agreement before downloading.
Click here to download benchmarks and results .
The original Faraday and IBM benchmarks and the papers that present them are available here:
If you are using the above benchmarks please also cite the following papers:
◆ STA Tool
The STA tools can output both the critical
path delay and cells along the most and second most critical path. It will
generate two files: placefilename_p1.txt
and placefilename_p2.txt for the two
paths respectively. In each file, (cell
name, latest signal arrival time of
the cell) will be given according to the order of cells in critical paths.
The delay model used here is the same as specified in our paper:
A Network-Flow Approach to Timing-Driven Incremental Placement, ICCAD 2006.
Here is a detailed explanation of the delay model.
The command format is:
In the .aux file, the .nodes, .nets, .pl and .par (optional) should be given. Here is a sample .aux file for ibm01 with Dragon placement. If the .par file is not specified, the program will use default values as in the paper. Sample .par for IBM and Faraday benchmarks are given here: ibm.par, faraday.par
◆ Free Offer to Industry
At this time we offer free, on a limited basis, to run FlowPlace on
your placed circuits if you can provide them to us in LEF/DEF or
Bookshelf formats. We will provide you with FlowPlace's placed output.
be useful if you provide us the cell-timing files in order to obtain
accurate timing-optimized layouts. Otherwise, we can use the default
parameters for Rd, Cg, r and c (or you can provide these also; the Rd
and Cg values will then be used uniformly for all cells). Please also
provide us information on what the unit length of your circuit
placement files in microns are, as this is also needed to get an
accurate TD placement (see, e.g., above .par files).
This offer will allow us to whet our tools on industrial circuoits and will give you some indication how useful Flowplace can be for your CAD and VLSI design efforts. If interested, please contact Prof. Shantanu Dutt (email@example.com) for this purpose.
 Shantanu Dutt, Huan Ren, Fenghua Yuan and
“ A Network-Flow Approach to Timing-Driven Incremental Placement
for ASICs, ICCAD 2006, accepted for publication.