ICCAD 2017 Contest

Net Open Location Finder with Obstacles

Cindy Shen and Kai-Shun Hu
Synopsys Taiwan Co., Ltd.,
29F, No. 333, Section 1, Keelung Road, Taipei, Taiwan


0. Announcements


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


III. Evaluation Methodology


IV. Example


V. Test Cases and Evaluator

  1. TestCase
        - 3 cases are in the tgz file.
  2. Evaluator
        - Contestants can use this evaluator to validate their output answer.
        md5sum:
        2db6d3247e209580803e4bc90ced5860 eval_3

        Usage of evaluator:
        " ./eval <case> <ans> " to evaluate and draw SVG.
        or
        " ./eval <case> " to draw SVG only.

        It will generate per metal layer SVG files (named Mx.svg) in the executing path to help you visualize the problem.
        You can open it by web browser like Chrome and FireFox.

        For zoom-in zoom-out support, please install chrome extension
        https://chrome.google.com/webstore/detail/svg-navigator/pefngfjmidahdaahgehodmfodhhhofkl
        And check 'Allow access to file URLs' in the chrome://extensions/
  3. TestCaseA

VI. Alpha Test


VII. Beta Test


VIII. Reference


IX. FAQ

  1. What's the problem that I cannot execute the binary file in problem B when I use eval at my terminal?

    The evaluator binary is a Linux binary. Please run it on Linux OS. Linux distribution tested are RHEL 6.6 and Ubuntu 14.04 LTS.
  2. In the given example, there are two routed shapes(on M2) overlapping. Should we consider they are both connected to the net if either of the shapes is connected to it?
    Yes, because if two routed shape are overlapping, these two shapes form a connected component.
  3. Is it possible in this problem that a routed shape overlap an obstacle or a via point is on an obstacle?
    No. We guaranteed “The given routed net shapes/via will always keep a minimum spacing S to obstacles and boundaries.” In the problem description. Thus the overlapping of routed shape/ via to obstacle would never exist in the testcase.
  4. Is there always one or more vias in any Via Layer?
    I think you mean routed via. No, not guaranteed. But the via layer is always available for your (answer)via.
  5. In public testcases, there are many overlapping Net shapes, and so are Obstacles. Is it general and legal?

    Yes, It is general and legal (as long as there is no overlapping between net shapes and obstacles).
  6. Is the coordinate of all given shape, obstacle, via, generated line and via integer?
    Yes, as described in the detailed rule: “A point in this problem is expressed as a pair of non-negative integers.”
  7. As a contestant, I am so glad to write to you for few questions about the problem we chose, Net Open Location Finder with Obstacles. I wonder if we are allowed to directly import some open source package (or head file) that are published online as a reference or we have to write the algorithm all by ourselves?
    Yes, you can use any open source package as long as being careful about any copylefts that package claims.
  8. 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)
    What's the range(maximum and minimum value) of Cv, S, W, X, Y,Z and Boundary in the Input format?
    For your question about Cv, S, W, X, Y, Z and Boundary in the Input format:
    All their minimum value are clearly 0.
    For the maximum value:
    We guarantee #MetalLayer W to be less than or equal to 10.
    ViaCost Cv, Spacing S, #RoutedVias Y to be less than or equal to 100.
    #RoutedShapes X, #Obstacles Z to be less than 1 million (10^6).
    And we guarantee that maximum value of Boundaries < UINT32_MAX.
  9. In problem B, we used the evaluator to check our result, but we found that if we insert via at the position (x between obstacle's x1 and obstacle's x2 , obstacle's y2 + Spacing), for example, in case2, we insert Via V1 (10149,10083), evaluator will show that we insert invalid via. We think the lines have no width in this problem, via aligns the obstacle's boundary + Spacing should be valid.
    You are right! This via is valid. This is a minor defect in our evaluator code. We have updated the Evaluator on our website.
  10. How many cores can we use for multi-threading in the problem? Are the maximum number of cores equal to the number of cores in CIC machine?
    The maximum number of cores that you can use is 4. It is equal to the number of cores in CIC machine.
  11. Is it possible that the distance between Routed shape and Obstacles equals to Spacing S? or it must be longer than Spacing S?
    It is possible that the distance between Routed shape and Obstacles equals to Spacing S. Equal to Spacing S is good enough.
  12. I do not know #Comps,what is that?
    It’s “Number of components after inserting answer paths”. If #Comps=1, it means your answer paths connect this net completely.
  13. Are these six cases the final one or not?
    No. Plan to add additional 2 large scale cases in beta test. One is public, one is hidden.
  14. We found that the evaluation metric of problem B in alpha test is the sum of the cost of each case, which means the results of large-scaled cases would dominate the final score. Is this the original intention of the evaluation metric? If not, we wonder if it is possible to change the evaluation metric (for example, normalize the cost of each case, etc.) in beta and final test or not.
    Yes it is our intention to have this kind of metric. In the real world EDA problems, almost all the cases are very large-scaled. So we don’t consider the small-scaled cases would be as important as the large-scaled one. And the different normalize method may partialize some cases or some team. Thus we add another two new large-scaled cases, caseA (public) and caseB (hidden). And hope you can focus on large-scaled cases.
  15. Is TeseCase1/2/3 the testcase of AlphaTest case1/2/3? Is TaseCaseA the public case mentioned in answer to Q13?
    1) Yes. 2) Yes.
  16. We find some RoutedShapes have zero area in case1. Like this: RoutedShape M3 (4380,243) (4543,243) Is it legal? Another question: Is a Obstacle has zero area legal? If it is legal and Spacing = 0, can a line cross the Obstacle?

    Zero area obstacle is legal. A line should still keep min spacing to obstacle. A line cross obstacle is invalid.
  17. (1)Are there any via given in case connecting no RoutedShape? (2)If answer is yes, should we need to connect these vias to other RoutedShape?
    (1)Yes. (2)Yes.