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

◆ Introduction

  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 (hren2@uic.edu). If you have any questions or suggestions, please contact him.

 

Note: Agreement
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 (dutt@ece.uic.edu)

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 [1] 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.

b)      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 (Normal circuits with less than 200k cells will not have path longer than 200 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:

IBM:     http://vlsicad.eecs.umich.edu/BK/ISPD02bench/

Faraday:  http://vlsicad.eecs.umich.edu/BK/ICCAD04bench/

If you are using the above benchmarks please also cite the following papers:

S. N. Adya, I. L. Markov, "Consistent Placement of Macro-Blocks using Floorplanning and Standard-Cell Placement", International Symposium of Physical Design (ISPD), San Diego,2002.

S. N. Adya, I. L. Markov, "Combinatorial Techniques for Mixed-size Placement", to appear in ACM Trans. on Design Automation of Electronic Systems, 2004

 

◆ STA Tool

Here is a simple STA tool for unrouted circuits (Please read the above agreement before downloading) (for PC, for Linux (w/ a Pentium processor) , for Solaris).

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:

STA *.aux

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. It will 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 (dutt@ece.uic.edu) for this purpose.

 

 

Refs:

[1] Shantanu Dutt, Huan Ren, Fenghua Yuan and Vishal Suthar,  “ A Network-Flow Approach to Timing-Driven Incremental Placement for ASICs, ICCAD 2006, accepted for publication.