ISPD 2007 Global Routing Contest Announcements

• New global routing contest benchmarks are posted on 03/02
• adaptec1 2d
• adaptec2 2d
• adaptec3 2d
• adaptec4 2d
• adaptec5 2d
• newblue1 2d
• newblue2 2d
• newblue3 2d
• adaptec1 3d
• adaptec2 3d
• adaptec3 3d
• adaptec4 3d
• adaptec5 3d
• newblue1 3d
• newblue2 3d
• newblue3 3d
• Solution evaluation perl script is available: gzipped perl script - updated March 15, 2007
• Low memory version: gzipped perl script - updated March 15, 2007
- use "-nr number_of_nets_to_read" option to arrange your memory usage. Unfortunately, run time will increase because the solution file will be read several times.
• Solution scoring function
• The final rank of a global router will be determined by the sum of individual ranks of circuits. The smallest rank number wins the contest.
• The individual rank per circuit is determined by the total overflow of your global routing solution. Tie is broken by the max overflow value. The 2nd tie-breaker is the routed wire length.
• If an edge's capacity is 0, the overflow of an edge is simply the actual usage.
• Each via-to-via connection, you should add 3 units of wire length. If you have a (M1->M5) metal layer change, it is considered as (M1->M2), (M2->M3), (M3->M4), (M4->M5), thus you should add 12 units of wire length to your calculation.
• Wire length is based on tile-to-tile distance, not coordinate-to-coordinate distance.
• If a net has more than 1000 sinks (i.e., #pins > 1000), you don't have to route it.
• If all sinks of a net fall into a same tile, you don't have to route it.
• New Submission deadline: March 15th, 2007 (Thurs)

ISPD 2007 Global Routing Contest

Continuing the tradition of spirited competition, the ISPD 2007 Steering Committee is pleased to announce a global routing contest, sponsored by SRC and IEEE-CEDA. Like the prior placement contests, a set of benchmarks will be released; teams are invited to produce global routing solutions, with the best results winning fame, recognition, and a grand prize. There will be an additional prize awarded by the IEEE Council of EDA (CEDA) for the best results on the multi-layer examples by a router openly available to all research groups. If the best results overall are obtained by an openly available router, it will win both the prizes.

The global routing solutions will be evaluated on the following metrics:

• Minimum total overflow for all benchmarks. Each benchmark will have a number of edges between global routing tiles; each of these edges will have a capacity. All nets must be routed within the global routing graph, ideally with no graph edge exceeding the specified capacity.

• Minimum wire length. If two routing solutions achieve the same capacity constraint, wire length will break ties.
• While exact pin positions will be given, the wire length will be measured based on the number of tile-to-tile connections are made.  Think of each crossing between tiles (horizontal, vertical, or with a via) as counting as one "unit" of wiring.  When detail routing is added to the contest, the wire length metric will be made more exact.
• Run time will not be a factor for this year (although it may be included in future contests).

There will be two sets of benchmarks.

• The first set of benchmarks will consist of a planar routing graph, using the Labyrinth format.  This format should make it possible for many academic tools to participate in the contest, and writing a global router which uses the format is not exceptionally difficult.  The output file format will be the BoxRouter format.

• The second set of benchmarks will be three-dimensional versions of the first set, with additional congestion information.  The input file format  is a variation on the Labyrinth format. The files will be ordinary ASCII text, specifying the size and shape of the global routing graph, the capacity on edges of the graph, the number of signal nets, and the number of pins and their positions within each net. The file format has been designed to make parsing easy. The output file format will be a variation of the BoxRouter format.

There will be separate prizes for each set of benchmarks (and it is entirely possible that one global router could win both groups).

REGISTRATION: If you are interested in participating in the contest, please send email to Dr. Gi-Joon Nam (gnam@us.ibm.com).  

CONTEST SCHEDULE:

• January 8th: Announcement of the Contest

• January 12th: Training benchmarks released.

• January 28th: Last day to confirm participation with Dr. Nam.

• February 12th: Contest benchmarks released.

• March 11th: Final day to submit binary for the global router, and routing results.

FILE FORMAT for Three Dimensional Benchmarks

The file format for the global routing contest is illustrated, with comments in italics (these will not be in actual input files). This example illustrates a problem with five routing layers (note the number of # marks on the vertical and horizontal capacity lines).

grid # # # (x grids, y grids, number of layers)
vertical capacity # # # # # (vertical capacity by default on each layer)
horizontal capacity # # # # #
minimum width # # # # #
minimum spacing # # # # #
via spacing # # # # #
lower_left_x lower_left_y tile_width tile_height

num net #
netname id_# number_of_pins minimum_width
x y layer
x y layer
...
[repeat for the appropriate number of nets]

# capacity adjustments (to model contestion)
column row layer column row layer reduced_capacity_level
[repeat for the number of capacity adjustments]

There are a number of changes from the Labyrinth format:

• The number of routing layers is specified; the Labyrinth format assumes a single routing plane. This change was made to allow layer assignment to be performed during global routing.
• Each layer may have a unique capacity in each direction per global routing tile, and it may be different for horizontal and vertical directions. Preferred routing directions will be given by having a zero capacity in the non-preferred direction. In the vertical and horizontal capacity lines, the first number indicates the capacity on the first layer, the second number the second layer, and so on. Minimum wire widths and minimum wire spacings are also specified; this impacts capacity calculations.
• The lower left corner (minimum X and Y) of the global routing region is specified, as well as the width (X dimension) and height (Y dimension) of each tile. Additionally, pin positions are given as XY locations, rather than tile locations. This change was motivated so that a detail routing contest based on these benchmarks could be performed in the future. Conversion from pin positions to tile numbers can be done with (pin_x - lower_left_x)/tile_width and (pin_y - lower_left_y)/tile_height. Pins will not be on the borders of global routing cells, so there should be no ambiguity. All pins will be within the specified global routing region.
• Each net will have a minimum routed width; this width will span all layers. When routing, compute the utilization of a global routing graph edge by adding the widths of all nets crossing and edge, plus the minimum spacing multiplied by the number of nets. This is more complex than the Labyrinth model, but more accurately reflects modern routing challenges. Each wire will require spacing between it's neighbors; think of this as having one-half of the minimum spacing reserved on each side of a wire.
• Congestion is modeled by including capacity adjustments. In the global routing benchmarks, there may be obstacles, or pre-routed wires. To communicate this to the global router, pairs of (adjacent) global routing tiles may have a capacity that is different from the default values specified at the start of a benchmark file.

Calculation of capacity is more complex than is done in typical academic global routing tools; our objective is to raise the bar slightly. Each global routing tile will have a capacity; this is a measure of the available space, not the number of global routing tracks. If the minimum wire width is 20, the minimum spacing 10, and the capacity of a tile is given as 450, this corresponds to 15 minimum width tracks (15 * (20 + 10)) . The capacity specified as the default value may be different than the width or height of a tile: in general, it is desirable to have routing utilization of a tile be below 70% of capacity, as higher values are difficult for detail routers to complete.

SAMPLE FILES

A simple 2-d routing problem, with illustrations.  Input.  Output.  Description.

A simple 3-d routing problem, with illustrations.  Input.  Output.  Description.

CONTESTANTS

Openly Available Tools

What does "openly available for research" mean?  In this case, the intent is to foster an academic infrastructure where all the necessary pieces are easily available to those who wish to do research on EDA algorithms and flows.  So by openly available we mean (a) the source code is freely available, along with make files and some examples with known results, all capable of running on a stock Linux system, and (b) the licensing terms, if any, are appropriate for research.  

Note that (b) applies not only to the global router itself, but any code it requires.  For example, if your global router needs a SAT solver from another group, the SAT solver must in turn be easily available for research for your entry to qualify.  IEEE/CEDA will test (a) and be the final judge of (b) before awarding the prize.

Sponsors