News and Announcements

Placement soluti used to generate benchmarks
placement_solution.tar.gz
gen_routing_benchmark.pl.gz
Final Results can be found here
Mar 30, 2007 (SUN): Added guideline for submissions. [link]
Mar 30, 2007 (SUN): Added information from /proc/cpuinfo. [link]
Mar 24, 2007 (MON): Rule clarification: Each team is allowed to submit one and only one binary for all benchmarks.
Mar 24, 2007 (MON): Evaluation script is updated with bug fixes. See the "Script" section.
Mar 24, 2007 (MON): Information of all teams is posted in "Join the Contest" section.
Mar 24, 2007 (MON): Details about out Linux box and runtime measurement are posted in Evaluation section.
Mar 24, 2007 (MON): New 8 benchmarks are posted in Benchmark section.
Mar 08, 2007 (SAT): 11 teams have confirmed participation. 8 new benchmarks have been released to all the teams. The benchmarks and the teams information will be posted shortly.
Mar 05, 2007 (WED): Final day to "submit binary for the global router, and routing results" is moved to March 31, 2008.
Mar 05, 2007 (WED): Added suggestions for beginners.
Mar 04, 2007 (TUE): Added details of the CPU time measurement. Parallel algorithms are allowed to speed up the router.
Mar 04, 2007 (TUE): Participation confirmation deadline is moved and now it is on March 7,2008. The day of the release of new 8 benchmarks is on March 8, 2008 (around 2am).
Feb 04, 2007 (MON): Webpage is created announcing new scoring function

Introduction

Continuing the tradition of spirited competition, the ISPD 2008 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 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.

Schedule

Feb 04, 2008: Announcement of the Contest
Feb 04, 2008: 8 ISPD07 benchmarks are posted. These benchmarks also will be used for evaluation.
Mar 07, 2008: Last day to confirm participation with Dr. Cliff Sze (csze@us.ibm.com).
Mar 08, 2008: 8 new contest benchmarks are released.
Mar 31, 2008: Final day to submit binary for the global router, and routing results. (Time: 23:59 CST w/ daylight saving, UTC-5)
Apr 15, 2008: ISPD 2008 results release and prizes giving

Input/Output Format

All benchmarks have multiple metal layers (three-dimensional), 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.
The choice of input/output format is intended to make it possible for many academic tools to participate in the contest, while writing a global router which uses this format is not exceptionally difficult.

Details of file formats

The input 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 congestion)
column row layer column row layer reduced_capacity_level
[repeat for the number of capacity adjustments]

There are a number of changes from the original Labyrinth format:

The number of routing layers is specified while the original 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 floor(pin_x - lower_left_x)/tile_width and floor (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 the capacity, as higher utilization can be more difficult for detail routers to complete.

Small sample input/output files

Here are a sample input file and a sample output routing file of a simple two layer routing problem, with illustrations. [Input] [Output] [Description(pdf)].

Router Evaluation and Ranking

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

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 (TOF) of one's global routing solutions. In other words, TOF is used as a representative congestion metric of a given global routing solution. If there is a tie in TOF, the max overflow (MOF) of a solution is used to break the tie. Note that if an edge's capacity is 0, the overflow of an edge is simply the actual usage.
If there are multiple global routing solutions with 0 total overflow, which means they have 0 maximum overflow, the 2nd tie-breaker rule will be enforced consisting of the routed wire length and runtime. The exact quality metric for 2nd tie-breaker is the_routed_wire_length * (1 + CPU_time_factor) where CPU_time_factor = 0.04 * log_2( router_cpu_time / median_cpu_time). CPU_time_factor will range from -0.1 to 0.1 (i.e., max 10% routed_wire_length advantage or disadvantage). Note that this metric is similar to the one used in the ISPD 2006 Placement Contest. The routed wire length is based on tile-to-tile distance, not coordinate-to-coordinate distance.
Each via-to-via connection, you should add the constant k units of wire length (the resistance ratio between via and one unit of wire in one g-cell). 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 4*k units of wire length to your calculation. After reviewing the data of several technology generations, we set k = 1 for this global routing contest. In other words, for each via, we're adding one *tile* penalty to the wire length calculation.
Via-blockage and usage are implicitly modeled by edge capacity, because we assume that a via size/spacing stays the same with those of wire usage. Also, since no track assignment is required for this global routing contest, no further detailed via modeling is required.
If a net has more than 1000 sinks (i.e., #pins > 1000), you don't have to route it.
If all pins of a net fall in the same tile, you don't have to route it.
In terms of CPU_time_factor, the equation looks like the following figure, and if a router is 2x faster/slower, the router gets about 4% routed wire length advantage/disadvantage. If a router is 4x faster/slower, the advantage/disadvantage factor will be approximately 8%, The maximum factor is set to 10%.
Since we may not be able to obtain the source codes of all the participating router, we will use WALL time as a measurement of a router's CPU time. All submission will be run on a dedicated Linux machine with single job running. The Linux machine will have 4 CPUs.
Let us emphasize that the most important metric (i.e., objective function) should be the congestion factor that is captured by the total overflow and max overflow. If router A produces more total overflows (congestion) than router B, regardless of routed wirelength and runtime, a router A's global routing solution is regarded inferior to router B's solution. If two routers produce the exactly same total overflow, the max overflow will break the tie.
Each team is allowed to submit one and only one binary for all benchmarks. In other words, for each team, the same settings/parameters must be applied to all benchmarks.

Remarks regarding CPU runtime:

You are welcome to use parallel algorithm to improve the runtime of your router. Your algorithm is allowed to use up to 4 CPU in parallel. The runtime will be measured by the runtime (=elapsed real time between invocation and termination) of our dedicated Linux machine.
The directory will be wiped clean every time to prevent saving precomputed information.
Our Linux machine has 8 cpus running at 2.8 GHz. It will have more than 16GB of memory.
gcc information
gcc version 4.1.2 20070626 (Red Hat 4.1.2-14)
x86_64-redhat-linux
Since we only have 2 weeks to run all routers and we have more than 10 participating teams. The runtime limit is set to 24 hours. If a router takes more than 24 hours to route a benchmark, it is consider to be failed in routing.

information from /proc/cpuinfo

    CPU information:-
    This is the CPU information I got from /proc/cpuinfo
    processor       : 0
    vendor_id       : AuthenticAMD
    cpu family      : 15
    model           : 65
    model name      : Dual-Core AMD Opteron(tm) Processor 8220
    stepping        : 3
    cpu MHz         : 2800.258
    cache size      : 1024 KB
    physical id     : 0
    siblings        : 2
    core id         : 0
    cpu cores       : 2
    fpu             : yes
    fpu_exception   : yes
    cpuid level     : 1
    wp              : yes
    flags           : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca
    cmov pat pse36 clflush mmx fxsr sse sse2 ht syscall nx mmxext fxsr_opt
    rdtscp lm 3dnowext 3dnow pni cx16 lahf_lm cmp_legacy svm extapic
    cr8_legacy
    bogomips        : 5602.42
    TLB size        : 1024 4K pages
    clflush size    : 64
    cache_alignment : 64
    address sizes   : 40 bits physical, 48 bits virtual
    power management: ts fid vid ttp tm stc

Evaluation Script

The solution evaluation Perl script is available for reference: zipped perl script with example Special thanks to Dr. Philip Chong from Cadence Berkeley Lab and Dr. Mehmet Yildiz from IBM Corporation for their contributions.

Benchmarks

ISPD08 Routing Contest will use 16 benchmarks from industrial ASIC designs to evaluate all the contest submissions. All benchmarks consist of multi-metal layers (i.e., multiple horizontal/vertical layers). Note that 8 of the 16 benchmarks are from ISPD 2007 Global Routing Contest ("the 3D benchmarks"). If your router can generate solutions successfully on these benchmarks, it should work well on new benchmarks too. On March 8, 2008, additional 8 benchmarks will be released.

Join the Contest

If you are interested in participating in the contest, or even if you have any question, please feel free to send an email to Dr. Cliff Sze (csze@us.ibm.com). To ensure prompt response, please start with "2008ISPD-RC" in the subject of your email.

For beginners, here are some suggestions.

CONTESTANTS

ID	Team Name	Affiliation	Contact Author	Other Authors
1	FastRoute 3.0	Iowa State University VLSI CAD LAB	Yanheng Zhang	Yue Xu
2	FGR	Univ of Michigan	Jarrod Roy
3	NTUGR	National Taiwan University	Huang-Yu Chen	Chin-Hsiung Hsu
4	NCTU	NCTU, Taiwan	Wen-Hao Liu	GKe-Ren Dai
5	BoxRouter	Univ of Texas	Minsik Cho
6	NTHU-Route	National Tsing Hua University, Taiwan	Yen-Jung Chang	Yu-Ting Lee, Tsung-Hsien Lee
7	IMS GlObal Router (IGOR)	Institute of Microelectronic Systems(IMS), Hannover, Germany	Artur Quiring	Philipp Panitz, Ole Ohlendorf
8	USC	University of Southern California	Zhiyang Ong
9	HSR (heuristically statistical router)	Dept of EE, National Chiao Tung University, Hsinchu, Taiwan	Hung-Ming Chen	Sean Liu, Jerry Lee,Po-Cheng Pan, Ching-Yu Chin, Yi-Hung Chen
10	HKPU	Dept of Electronic&Information Engineering, Polytechnic University of Hong Kong	Jingwei Lu
11	CUHK	Chinese University of Hong Kong	Zaichen Qian

Submission Guideline

Final submission time is set to (Mar 31) 11:59pm CST with daylight saving, which is in different time zone as,

9:59pm ( Mar 31) in California,
12:59pm (Apr 1) in Beijing,Taipei and Hong Kong,
6:59am (Apr 1) in Hannover, Germany.

You can send me an http-link such that I can download your binary (or source files) and routing result files from the link. Please zipped or gtar all files.
Since I will be running all the router by myself, if you don't have enough time to generate all routing results files, you can submit just a couple of them. I just want to make sure my execution of your binary generates exactly the same as your execution.
You can ask me to use a non-open-source but faster solver (e.g. ILP, SAT) to run with your router for contest ranking. However, we have to make sure I can run it in my Linux machine. When you release your source code for "Openly Available Tools", you can switch to an open-source solver.

Terms and Conditions

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.