ISPD 2018 Contest on Initial Detailed Routing

Announcements

4/8/2018Presentation slide is released.
4/8/2018Detailed data is released.
1/18/2018One of the benchmark, ispd18_test2 and Evaluation program are updated with guide issue fixed.
1/8/2018Evaluation program is updated with a bug fix
1/4/2018Evaluation program is updated.
1/3/2018Released the evaluation program. Please refer to the README file for instruction.
12/26/2017Released three official benchmarks. Fixed route guide problem with ispd18_sample3
12/23/2017FAQ updated.
12/22/2017Released other two sample benchmakrs and updated the first sample.
12/16/2017Problem Introduction and Tutorial for the ISPD 2018 Contest
12/6/2017Contest schedule updated.
11/1/2017FAQ updated.
10/1/2017Contest topic announced.

Abstract

Detailed routing can be divided into two steps. First, an initial detailed routing step is used to generate a detailed routing solution while handling the major design rules. Then a detailed routing refinement is performed to fix the remaining design rule violations. This proposed contest focuses on the initial detailed routing step.

Assuming that a global routing result is already well optimized for certain metrics (e.g., timing), a detailed router needs to honor the global routing result as much as possible. In this way, the optimized metrics are kept meanwhile avoids design rule violations. For example, Fig. 1(a) shows a global routing result for a net with a source pin A and sink pins B, C, and D. Because the path from A to B is timing critical, a global router identifies a short path from A to B. However, the path passes a local wiring congestion region which is not seen by the global router. If the detailed router routes wires over that region as shown in Fig. 1 (b), it will have design rule violations. Fig. 1 (c) shows a routing result without short/spacing violations but it will have timing degradation for the path from A to B. On the other hand, Fig. 1 (d) shows a desired solution.


Fig. 1

To minimize the disturbance for net topology, initial detailed routing plays an important role. If the initial detailed routing result can meet the most common routing rules even it is not fully DRC clean, the later detailed routing refinement will have less chance to largely disturb the routing results.

Benchmarks

You can find the first released testcase for the contest, that is a sample benchmark, in the below link:

Instruction to Setup the Development Environment for the ISPD 2018 Contest

Benchmark Version #std #blk #net #pin #Layer Die size Tech. node Comments
ispd18_sample 3 22 0 11 0 9 0.017x0.01mm2 45nm This sample testcase is used for the tutorial purpose.
ispd18_sample2 2 22 1 16 0 9 0.017x0.01mm2 45nm This sample testcase has a block and nets connecting to the block.
ispd18_sample3 3 5 1 7 5 16 1.90x2.00mm2 45nm This sample testcase has IO pins, large die size and more metal layers.
ispd18_test1 4 8879 0 3153 0 9 0.20x0.19mm2 45nm Standard cell netlist only.
ispd18_test2 5 35913 0 36834 1211 9 0.65x0.57mm2 45nm Standard cell netlist with IO pins.
ispd18_test3 2 35973 4 36700 1211 9 0.99x0.70mm2 45nm Standard cell netlist with IO pins and block macros.
ispd18_test4 2 72094 0 72401 1211 9 0.89x0.61mm2 32nm Design has Metal2 OBS in some of its standard cells.
ispd18_test5 3 71954 0 72394 1211 9 0.93x0.92mm2 32nm Design has Metal2 OBS, Metal2 Power/Ground pins, and routing direction is reversed.
ispd18_test6 3 107919 0 107701 1211 9 0.86x0.53mm2 32nm Design has Metal2 OBS, Metal2 Power/Ground pins, and reversed routing direction, but without any block macro.
ispd18_test7 1 179865 16 179863 1211 9 1.36x1.33mm2 32nm Quad-core design with Metal2 OBS and Metal2 Power/Ground pins as blockage.
ispd18_test8 1 191987 16 179863 1211 9 1.36x1.33mm2 32nm Quad-core design with Metal2 to Metal3 OBS and Metal2 to Metal4 Power/Ground pins as blockage.
ispd18_test9 1 192911 0 178857 1211 9 0.91x0.78mm2 32nm Quad-core design with Metal2 to Metal3 OBS and Metal2 to Metal4 Power/Ground pins as blockage, no block macro, higher utilization.
ispd18_test10 1 290386 0 182000 1211 9 0.91x0.87mm2 32nm Quad-core design with Metal2 to Metal3 OBS and Metal2 to Metal4 Power/Ground pins as blockage, no block macro, extra congested area.

Update history:

Evaluation

Downloads:

Evaluation kit (latest update: 1/18/2018 , version: 4)
Evaluation metric and ranking method (latest update: 1/4/2018)

Evaluation kit includes:
README - instruction of running evaluation
ispd18eval.sh - evaluation script
ispd18eval.tcl - supporting script for Innovus for design rules and connectivity checking
ispd18eval - evaluation binary for guide and track obedience checking and score calculation
ispd18eval.w - weights information for score calculation

Evaluation Script (ispd18eval.sh)

The evaluation script manages the whole evaluation process. It performs the following tasks:
1. Starts Innovus to perform design rule and connectivity checking.
2. Generates design rule violation and connectivity reports.
3. Starts evaluation program to perform guide and track obedience checking, read the Innovus reports, and calculate the final score.
4. Generates the score table as output.

Usage:
./ispd18eval.sh -lef <input LEF> -guide <input guide> -def <solution DEF> [-keep]

-lef : the input LEF file
-guide : the input route guide file
-def : the routed DEF file
-keep : when it is specified, the intermediate files (logs, reports, scripts, etc.) will not be cleaned after evaluation.

Example:
./ispd18eval.sh -lef sample/ispd18_sample.input.lef -guide sample/ispd18_sample.input.guide -def sample/ispd18_sample.output.def

Evaluation Program (optional)

If you already have design rule and connectivity reports generated by Innovus. You could use the evaluation program directly without using the evaluation script.

Usage:
./ispd18eval -lef <input LEF> -def <solution DEF> -guide <input guide> -georpt <design rule violation report> -conrpt <connectivity report>

-lef : the input LEF file
-guide : the input route guide file
-def : the routed DEF file
-georpt : the design rule violation report generated by Innovus
-conrpt : the connectivity report generated by Innovus

Contest Result

1st Place:
-TritonRoute
University of California, San Diego
Andrew B. Kahng, Lutong Wang, Bangqi Xu

2nd Place:
–Dr. CU
The Chinese University of Hong Kong
Gengjie Chen, Chak-Wa Pui, Haocheng Li, Jingsong Chen, Bentian Jiang, Evangeline F.Y. Young

3rd Place*:
–LuLuRoute
National Taiwan University
Hao Chen, Chen-Hao Hsu, Fan-Keng Sun, Ching-Yu Chen, and Yao-Wen Chang
–NTHU-DR
National Tsing Hua University and Fuzhou University
Chein-Hao Tsou, Chia-Chun Chung, Chao-Yuan Huang, Wang-Yang Li, Zhuang Zhen, Genggeng Liu, Wenzhong Guo, Ting-Chi Wang

4th Place:
–UFRGS-Brazil
Universidade Federal do Rio Grande do Sul
Mateus Fogaca, Jucemar Monteiro, Henrique Placido, Andre Oliveira, Isadora Oliveira, Eder Matheus Monteiro, Marcelo Johann, Ricardo Reis

5th Place:
-NCTUdr
National Chiao Tung University
Shih-Ting Lin, Ming-Jie Fong, Ching-Hsi Chen, Wei-Ren Lai, He-Cheng Tsai, Yih-Lang Li

* According to the contest ranking policy, LuLuRoute win the 3rd place. However, NTHU-DR’s result is tie for the LuLuRoute, so we rank them both at 3rd place.

Schedule

November 01, 2017Contest topic announced.
December 15, 2017Sample benchmark suite released.
December 20, 2017Deadline for contest registration. (closed)
December 31, 2017Benchmark suite released.
February 15, 2018Deadline to receive alpha router executable submissions from all teams.
March 01, 2018Deadline to receive beta router executable submissions from all teams.
March 11, 2018Deadline to receive final router executable submissions from all teams at 2:00pm (PST).
March 25-28, 2018Contest results will be announced at the symposium.

Contest Organizers

Wen-Hao Liu Cadence Design Systems
Stefanus MantikCadence Design Systems
William Chow Cadence Design Systems
Gracieli PosserCadence Design Systems
Yixiao Ding Cadence Design Systems

FAQ

  1. Q: Will global routing input be provided?

    A: Yes. Global routing results will be provided by Cadence's tool.

  2. Q: Can we apply track assignment technique for this contest?

    A: Yes. It is welcomed to have track assignment stage.

  3. Q: Can we assume that only the routing rules have listed in the ispd18_sample.input.lef file will be used in the contest?

    A: Yes, you can have this assumption. This contest will only consider the rules listed in ispd18_sample.input.lef. No more other rules. However, the value of the spacing distance may be different for different designs.

  4. Q: Can we assume that only cells in the ispd18_sample.input.lef will be used in the contest? Will there be more cell types?

    A: Different designs may have different LEF files with different cell types and different layer configuration.

  5. Q5: Can we route wires/vias outside of guides to avoid short/spacing violations?

    A: Yes. Routing guide is a soft rule while violation is a harder rule. So, a DRC-free solution is usually considered as a better solution compared to the solution with DRC violations. Namely, for DRC resolving, routing wires out of guide may be necessary for some situations.

  6. Q: For the gate macro defined in the .lef file, is the pin located at all the rectangles define? For example, for pin A0 in AOI221X2 in ispd18_sample.input.lef, are all the four rectangles defined in metal1 alltogether constitute the pin A0?

    A: Yes, the four rectangles represent the pin A0. A single pin, such as A0 in this example, can have multiple rectangles. The connection to this pin can be made at any point inside any of the defined rectangles and only one connection is needed. However, some pins may have multiple rectangles on multiple routing layers, which is a typical scenario of a pin inside a BLOCK macro. When the pin has multiple rectangles on multiple layers, connection to any one of the given layer is sufficient.

  7. Q: What are the parameters for TRACKS and ROW meaning? Any introduction documents?

    A: Please search "TRACKS" and "ROW" in the following document: lef_def_ref.pdf

  8. Q: Does cut spacing mean the minimum spacing between vias on same net or different nets? Is there any example?

    A: Yes, cut spacing means the minimum spacing between the cut rectangle of the vias that applies to both same net and different net. For example, there is a via metal (x1, y1, x2, y2) on a cut layer where the cut spacing is S, and there is another object whose dimension is (x3, y3, x4, y4) on the same cut layer. The cut spacing violation will happen when the following equations hold.

      x_dist = max(0, max(x1, x3) - min(x2, x4));
      y_dist = max(0, max(y1, y3) - min(y2, y4));
      x_dist^2 + y_dist^2 < S^2

    Note that the cut rectangle can be a cut from a via (either same-net via or different-net via), a cut blockage, or a cut from pin.

  9. Q: Does pin shapes in component are only formed by rectangles, or other shapes of polygon?

    A: In general case, pin shapes are not necessary to always be rectangles. However, for simplification, this contest always represents pin shapes by one or multiple rectangles.

  10. Q: Is it allowed to put more than 1 via on a pin? For example, the net below connects pins a, b, c (in blue color), and Metal2 is horizontal. Could we just use two short Metal2 wires to connect the net? (As shown in the picture, there is just one net in the pciture below)


    A: This is what we call "using pin as a feedthrough". Electrically, it is the equivalent whether we use pins as feedthrough or not. However, in general, this is not preferred (or even discouraged) because that will create weakly connected nets. For simplification, this contest allows "using pin as a feedthrough" and does not apply penalty for that.

  11. Q: Does WIDTH keyword matters for cut layers?

    A: No. Because this contest provide the via library in lef file, you don’t really need the WIDTH information from cut layers. Namely, you can ignore WIDTH keyword for cut layers.

  12. Q: Is it possible to see a routing guide overlap with another routing guide of the same net?

    A: We had routing guide overlapping issue before, and it is fixed. If you see routing guides overlap, please let the contest organizer know.

  13. Q: Does route guides imply a connected tree structure rather than just rectangles?

    A: The route guides on a layer should be seen as rectilinear polygons composes of rectangles. It doesn’t imply any routing direction or routing topology, so the merging direction does not matter.

  14. Q: Does rectangle width imply gcell size? We would like to know a reasonable assumption of the range of rectangle width.

    A: The route guide width may vary for different benchmarks or even different nets. The routing guides of a net mostly represent the gcells passed by the global routing solution for that net. However, for some cases, the routing guides can be defined by users or the third-party tools in order to control the routing solution for certain nets. For this contest, you can assume guide width is around 1-row-height to 3-row-height, but the guide width may not be always uniform.

  15. Q: Should we expect to see the cases where long detours occur due to large global routing overflow? Could you elaborate more about the global routing overflow from the given route guide file?

    A: Yes. You may see long detour due to the global routing overflow in the official benchmarks. However, you cannot assume that the route guides always give you overflow-free / congestion-free input. In this contest, the route guides come from the global routing solution with the reasonable congestion, but the congestion level may vary in order to test the robustness of the proposed detailed routers.

  16. Q: There are some nets with only one pin. What should we do with them?

    A: You can just leave those one-pin net unrouted. However you should still write them to output DEF file even there is no wire.

  17. Q: We found the PITCH value in LEF files is not the same to the TRACK STEP in DEF files. Why this happens?

    A: PITCH value defined in LEF is a reference, which considers wire width, wire spacing, via width, via-to-wire spacing, and via-to-via spacing etc. TRACK STEP is a design-specified or user-specified value. This contest will provide TRACK STEP in DEF file for every benchmark, so you can ignore PITCH value in LEF file and only pay attention to TRACK STEP.

  18. Q: In file "ispd18eval.w", both OffTrackWire and Wire have the same weight of 0.5. Does it mean that off-track wires is the same as on-track wire in terms of score?

    A: No. Off-track wire cost is the "extra" cost. Say, if you have a wire which is off-track and in wrong-way, the cost of the wire includes the basic wire cost, off-track cost and wrong-way cost.

  19. Q: We found that there exist "SPECIALNETS" keyword in the def file of ispd_test1, ispd_test2, ispd_test3, however this keyword does not exist in the sample benchmarks. Do we need to deal with "SPECIALNETS" in this contest?

    A: No. This contest will not consider special nets, so you can ignore special nets in this contest.

  20. Q: According to the description of documents "lefdefref.pdf" and "Introduction_of_ISPD18_Contest_Problem.pdf", ENDOFLINE indicates that an edge that is shorter than eolWidth. I am a little confused on the word "edge", what does it represent?

    A: "Edge" corresponds to the edge of the metal rectangle. One metal rectangle consist of four edges: top and bottom edges where the length is equal to the width of the rectangle, and left and right edges where the length is equal to the height of the rectangle. If the length of the edge is less than the eolWidth, then eolSpace is required.

  21. Q: a) For the MIN AREA rule, if we add possible patch metal to satisfy min area rule, how do we represent the patch in the output file? b) The following information is contained in the "ispd18_sample.solution.good.def" file:

      - net1238
        ( inst3428 A ) ( inst3444 Y )
        + ROUTED Metal2 ( 97400 83790 ) RECT ( -70 -442 70 70 )
        NEW Metal2 ( 87800 83790 ) RECT ( -70 -442 70 70 )
        NEW Metal3 ( 87800 83790 ) ( 97400 * ) VIA23_1C
        NEW Metal2 ( 97400 83790 ) VIA12_1C
    I was wondering what does the "RECT ( -70 -442 70 70 )" represent?

    A: Patch rectangle is represented by "NEW ( )" followed by "RECT ( )". The coordinate represented by RECT statement is relative to the (x,y) point described before that. So, "Metal2 ( 1000 2000 ) RECT ( -50 -50 100 50 )" indicates that we have a patch metal on Metal2 layer with the rect geometry at: ( 950 1950 1100 2050 ).

  22. Q: How could we calculate the score since the units of length (of wires) and number (of vias, etc.) are different?

    A: The unit of wire length is in number of Metal2 pitches. For example, if wire length is 213160 unit and Metal2 pitch is 400 unit, the wire length will be 532.9. As the weight for wire length is 0.5, the resulting score for wire length is 213160 / 400 * 0.5 = 266.45. The unit of via is just number of vias and the weight for via score is 2. For example, if there are 54 vias, the resulting score for via is 54 * 2 = 108.


  23. Q: In the released benchmark comments of "ispd_test4-6" benchmarks on the website, what does "M2" stand for? Does it stand for "Metal 2"? We found that OBS in macro not only in the Metal2 layer but also in other layers (e.g. in the "ispd_test4" benchmark, an OBS of macro "MEM2" exists in the Metal1-6 layers.)?

    A: Yes. M2 means "Metal 2". OBS can exist on any layer. Because the cell library used for this design has Metal2 OBS, this design will have more Metal2 blockages.

    We do have OBS on Metal1-6 for MACRO BLOCK MEM1 and MEM2, but no OBS on Metal2 or above for MACRO CORE (i.e. standard cell) for test1-3. Test4-6 has OBS on Metal2 for MACRO CORE in addition to the ones in MACRO BLOCK. Some explanation on how to access pins on MACRO BLOCK as those pins are overlapping with OBS has been documented in LEEFDEF manual page 136. Basically, pins from MACRO BLOCK (or referred as BLOCK pins) can only be connected with planar routing (through wire) from the direction that is perpendicular to the side where the corresponding pin is located. For example, if pin A is located on the right side of the BLOCK, then it can only be connected with a horizontal wire coming from the right of the BLOCK. The wire connection has to be enclosed inside pin geometry. In addition, a via can also be used to make a connection to a BLOCK pin if-and-only-if the pin is at the topmost layer and there is no any other metal (pin or OBS) on the layer directly above the current layer. For example, if pin A is located on Metal6 and OBS also exists on the same layer but not on Metal7, then a via can be used to connect to pin A. On the other hand, if OBS on Metal7 exist (and/or another pin geometry on Metal7 that is at the same location), then via access cannot be used. No routing is allowed at any time inside MACRO BLOCK on the layer that has OBS.

  24. Q: In evaluation metrics (file "ISPD18 Contest: Evaluation Metrics and Ranking Method" page 4), what does "The wirelength unit here is the number of M2 pitches" mean? Is pitch a length of something provided in lef file?

    A: M2 (or Metal2) pitch is the value of distance between neighboring track location on the second metal layer. It can be read in both DEF and LEF files. In LEF file, you could see layer definition like this:

      LAYER Metal2
        TYPE ROUTING ;
        DIRECTION VERTICAL ;
        PITCH 0.10 0.10 ;
    The first 0.10 is the pitch of vertical wire and second 0.10 is for horizontal wires. Since Metal2 is vertical, we take the first 0.1 as "M2 (Metal2) pitch".

  25. Q: How many threads exactly would be used in the final score evaluation?

    A: We will use 8 threads for the score evaluation.

  26. Q: Is it allowed to route wires on the metal1? I noticed there are no wires on metal1 in the "ispd18_sample.solution.good.def" file, but there are routing guides on metal1 in the "ispd18_sample.input.guide" file.

    A: Yes. It's allowed to route wires on M1..

  27. Q: The following information is contained in the "ispd18_sample2.solution.good.def" file:

      - netMQ1
        ( inst5821 A ) ( blk Q[1] )
        + ROUTED Metal3 ( 82420 83410 0 ) ( 85000 * ) VIA23_1C
    What does the red "0" in ( 82420 83410 0 ) represent?

    A: "0" here is wire extension. By default, every wire is extended with half of the wire width. By specifying the third number, wire is extended with custom length. ( 82420 83410 0 ) means that the wire's end-of-line edge is exactly at 82420 83410. You can see an example below:


  28. Q: How to determine if a net is connected or open?

    A: We use the following connectivity model to determine if a net is connected or open: A net is considered open if at least one of its pin is left unconnected to the rest of the pins according to the connectivity criteria described as follows:

    1 - Two wires are considered connected if the end points of their center line are connected (i.e., the end points from both wires landed on the same coordinate). For any other configuration, the wires are considered unconnected ("open").

    2 - A via is considered connected to a wire if the origin of that via landed exactly at the end point of the wire’s center line. Otherwise, they are considered unconnected ("open").

    3 - Two vias are considered connected if the origin of both vias landed on the same coordinate. For any other configuration, these two vias are considered unconnected ("open").

    4 - A wire is considered connected to a pin if and only if one end point of the wire’s center line is inside any of the pin geometry (pin's boundary is included). For any other location, even if wire side touches pin geometry, they are considered unconnected ("open").

    5 - A via is considered connected to a pin if and only if the origin of the via is inside any of the pin geometry (pin’s boundary is included). For any other location, even if via side touches pin geometry, they are considered unconnected ("open").

    6 - A patch metal can be used to fix violation, however it cannot be used as a bridge for connectivity.

    7 - A net is considered ΄fully connected‘ if any pin in the net is connected to any other pin when traced using the connected object (wires and vias).

    The following figures show some sample valid and invalid connections.


Contact

For registration or inquiry, please send emails to ispd2018contest@gmail.com.