ICCAD 2017 Contest

I. Abstract

    In the place and route (P&R) flow, a router might still leave some nets open after routing is done. These opens are usually caused by ECO (Engineering Change Order) or some user changed design. Thus it is very helpful to have an automatic tool to detect if a net is still open after routing. Also, a tool should indicate the (shortest) paths to reconnect existing net shapes to resolve the open. Furthermore, the indicated paths must be obstacle-aware for that a path overlap with obstacles is not legitimate in a real case.

II. Problem Description

• This problem focuses on a single net with large scattered routed net shapes. The contestants are requested to generate paths to connect all these routed net shapes and vias while having minimum line length/via cost.
• Given a set of routed net shapes $R = \{R_1,R_2,…,R_j\}$, a set of routed net vias $V = \{v_1,v_2,…,v_k\}$, a set of obstacles $O = \{O_1,O_2,…,O_m\}$ on routing layers $L = \{M_1,V_1,M_2,V_2,…,V_{n-1},M_n\}$, with a design boundary $B$, spacing $S$ and via cost $C_v$
• Contestants are requested to find a set of paths $p = \{p_1, p_2,…,p_l\}$ to connect all routed net shapes $R$ and routed net vias $V$ together.
• Each path $p_i$ can be an H-line, a V-line or a via. Steiner points are allowed.
• Examples:
  
  

  Figure1. Paths generated to fix the opens

• As shown in Figure 1, the blue rectangles are the routed net shapes $R$ of a net containing some opens. Your goal is to output a set of paths to connect the existing net shapes to form a single connected component.
• The path set $p$ consists of red lines and orange vias. The path set in this figure is one of the valid outputs that contestants could generate.
• The gray rectangles are the obstacles $O$. The paths (line/via) should always keep a minimum spacing $S$ to these obstacles.
• The outmost rectangle is the design boundary $B$. The paths (line/via) should always keep a minimum spacing $S$ to it as well.
• Detailed Rules:
  
  • Format of Shapes/Lines/Vias
    
    • A point in this problem is expressed as a pair of non-negative integers.
    • Points have no area and lines have no width (more explanations later).
    • The routed net shapes $R$, obstacles $O$ and design boundary $B$ are always rectangles represented by their upper right (UR) and lower left (LL) corners.
    • The routed net vias $V$ and your output vias are always points.
    • Your output lines must be horizontal(y-equal) or vertical(x-equal) lines.
  • Format of Metal/Via Layers
    
    

    Figure2. Layer stack in a given problem

    • Layers are stacked like those shown in Figure 2.
    • All layers are aligned with the same coordinate system in the x and y axes.
    • All the routed net shapes $R$ and obstacles $O$ and lines exist only on metal layers.
    • A via on layer $V_{i-1}$ connects the same point of $M_{i-1}$ and $M_i$.
  • Definition of Connection
    

    Figure3a. Lines connecting net shapes	Figure3b. Lines not connecting net shapes

    • Any point touching between line/via/netShapes counts the connection.
    • For Figure 3b, these two lines do not connect the existing net shapes because the end points of the lines are not on the routed net shapes.
    • Stacked via is also considered as connected.
  • Steiner point identification
    

    Figure4a. Lines and vias not conntected	Figure4b. Lines and vias conntected

    • You should identify the location of Steiner point. For lines and vias, we only check if the end points are touched, as shown in Figure 4.
  • Spacing to Obstacles and Boundaries
    

    Figure5. valid path.

    • As mentioned, a line in this problem has no width. So the path in Figure 5 is valid.
    • You only need to consider the spacing to obstacles and boundaries because all routed net shapes and via are for the same net.
    • The given routed net shapes/via will always keep a minimum spacing S to these obstacles and boundaries.
  • Multi-threading Allowed and Encouraged.
    • The maximum number of cores that can be used is 4.

III. Evaluation Methodology

• Overall $Cost=\sum\limits_{q=1}^t=Cost(p_q)+Disjoint \ cost$
  
  • If $p_q$ is a H-line or V-line, Cost($p_q$) = length of this H-line or V-line.
  • If $p_q$ is a via, Cost($p_q$) = $C_v$.
• The goal is to minimize the overall cost for each case.
• There are several things to notice:
  1. If the components are not connected as a single net:
     $Disjoint\ cost = 2 \times (\#components - 1) \times (boundary\Delta X + boundary\Delta Y + \#ViaLayers \times C_v)$
     ($boundary\Delta X = UR_x-LL_x\ of\ B, boundary\Delta Y = UR_y-LL_y\ of\ B,\ and\ \#ViaLayers=\#MetalLayers-1$)
  2. Invalid paths would be discarded as shown Figure 6.
     

     Figure6. Invalid paths

     • E.g. $p$ fails to keep the minimum spacing with obstacles or boundaries.
     • The spacing violation of a via checks both upper and lower layer obstacles.
     • The non-horizontal H-line or non-vertical V-line will also be discarded.
     • Be aware that this removal may cause the net being disjoint!
     • If your path is overlapping with routed net shapes, we will not trim it for you.
     • If your path is overlapping with themselves, we will not trim it for you either.
       

       Figure7. Path overlapping net shapes

  3. Runtime bonus/penalty to overall cost
     

     Figure8. Runtime bonus calculation

     • We measure the runtime by the clock on the wall time.
     • If your runtime is within (or equal to) the first quartile of all the runtime of the teams. Then there will be a bonus 10% off to your overall cost, as shown in Figure 8.
     • If your runtime is within (or equal to) the second quartile of all the runtime of the teams. Then there will be a bonus 5% off to your overall cost.
     • If your runtime is over 4hrs, then the output of that case will be discarded. The cost would be treated as though the net is disjoint (huge disjoint cost).

IV. Example

• Remember that Line Cost = length
• Input format:
  
  ViaCost = Cv
  Spacing = S
  Boundary = (LLx,LLy) (URx,URy)
  #MetalLayers = W
  #RoutedShapes = X
  #RoutedVias = Y
  #Obstacles = Z
  RoutedShape Layer (LLx,LLy) (URx,URy)
  …
  RoutedVia Layer (x,y)
  …
  Obstacle Layer (LLx,LLy) (URx,URy)
  
  
• You can output H-line/V-line/via in any order. But be careful about IO handling in multi-thread environment.
• Output Format:
  H-line Layer (x1,y) (x2,y)
  …
  V-line Layer (x,y1) (x,y2)
  …
  Via Layer (x,y)
  
  
• Take Figure 1 for example, the input will be:
  
  ViaCost = 20
  Spacing = 5
  Boundary = (0,0) (1000,1000)
  #MetalLayers = 2
  #RoutedShapes = 7
  #RoutedVias = 1
  #Obstacles = 3
  RoutedShape M1 (50,100) (250,150)
  RoutedShape M1 (600,20) (750,140)
  RoutedShape M1 (50,850) (250,900)
  RoutedShape M1 (10,800) (500,995)
  RoutedShape M2 (75,20) (200,750)
  RoutedShape M2 (375,100) (575,600)
  RoutedShape M2 (475,20) (670,450)
  RoutedVia V1 (175,125)
  Obstacle M1 (350,300) (650,750)
  Obstacle M1 (50,350) (650,650)
  Obstacle M2 (350,700) (950,800)
  
  
• Example output:
  
  V-line M1 (700,140) (700,550)
  H-line M2 (575,550) (700,550)
  H-line M1 (500,850) (700,850)
  Via V1 (700,550)
  V-line M1 (700,550) (700,850)
  H-line M2 (200,150) (375,150)
  
  
• Your program should be named net_open_finder and we can execute as follows:
  ./net_open_finder <input.txt> <output.txt>

V. Test Cases and Evaluator