Running times in detailed routing as a function of design parameters #3298

oharboe · 2023-05-07T18:41:42Z

oharboe
May 7, 2023
Collaborator

mock-array-big has 3 essential parameters that can be adjusted: array area(number of elements), element size (area) and data width (bits).

I thought it would be interesting to see how detailed routing (TritonRoute) varies across these parameters, so I made a python snippet(https://github.com/Pinata-Consulting/OpenROAD-flow-scripts/commits/plot-running-times) to gather some data and plot them

The graph below is interactive(measured on a machine with 16 threads and 64gByte of RAM, where memory consumption appears to peak at 20gByte), which helps in terms of understanding the 4 dimensions being represented:

Video: https://drive.google.com/file/d/1pmkIZh6tUOrWhAkVRgm0fxCD7yaf766Q/view

Snapshot:

8 x 8 64 bit array detailed route times plotted against threads

Conclusion so far

Detailed routing is surprisingly slow when the area is large, but everything else is the same.

This run takes 40 minutes or so, APTOS_MOCK_PITCH_SCALE=20 make FLOW_VARIANT=scale-20 route DESIGN_CONFIG=designs/asap7/mock-array-big/config.mk whereas APTOS_MOCK_PITCH_SCALE=2 make FLOW_VARIANT=scale-2 DESIGN_CONFIG=designs/asap7/mock-array-big/config.mk completes in a few minutes

Detailed of testing...

It looks like the performance of detailed routing is sensitive to area:

MOCK_ARRAY_PITCH_SCALE=2 make OPENROAD_EXE="perf record -o perf.data ~/OpenROAD-flow-scripts/tools/install/OpenROAD/bin/openroad" DESIGN_CONFIG=designs/asap7/mock-array-big/config.mk FLOW_VARIANT=scale-2 route

Samples: 15M of event 'cycles', Event count (approx.): 14285585618565
Overhead  Command   Shared Object           Symbol
  16,94%  openroad  openroad                [.] fr::FlexGridGraph::initEdges
   8,38%  openroad  openroad                [.] fr::FlexGridGraph::outOfDieVia
   7,46%  openroad  openroad                [.] fr::FlexDRWorker::modMinSpacingCostVia
   5,92%  openroad  openroad                [.] fr::FlexGCWorker::Impl::isCornerOverlap
   4,62%  openroad  libstdc++.so.6.0.30     [.] std::_Rb_tree_increment
   4,23%  openroad  [unknown]               [k] 0xffffffffa7b87f27
   4,20%  openroad  openroad                [.] fr::FlexDRWorker::modMinSpacingCostPlanar
   3,31%  openroad  openroad                [.] fr::frLayer::getMinSpacingValue
   3,22%  openroad  openroad                [.] fr::FlexGridGraph::getIdx
   2,93%  openroad  openroad                [.] fr::FlexGCWorker::Impl::initNet_pins_polygonCorners_helper
   2,48%  openroad  openroad                [.] fr::FlexDRWorker::modMinSpacingCostVia_eol
   2,46%  openroad  openroad                [.] box2boxDistSquareNew
   2,37%  openroad  openroad                [.] fr::FlexDRWorker::modBlockedPlanar
   2,17%  openroad  openroad                [.] fr::FlexGridGraph::addFixedShapeCostVia
   1,71%  openroad  openroad                [.] odb::dbTransform::apply
   1,45%  openroad  openroad                [.] fr::FlexGridGraph::isEdgeInBox
   1,43%  openroad  openroad                [.] odb::dbTransform::apply
   1,28%  openroad  openroad                [.] fr::FlexDRWorker::modBlockedVia
   1,25%  openroad  openroad                [.] std::vector<fr::FlexGridGraph::Node, std::allocator<fr::Fle

Same run, but bigger area

MOCK_ARRAY_PITCH_SCALE=20 make OPENROAD_EXE="perf record -o perf.data ~/OpenROAD-flow-scripts/tools/install/OpenROAD/bin/openroad" DESIGN_CONFIG=designs/asap7/mock-array-big/config.mk FLOW_VARIANT=scale-20 route

2_4_floorplan_macro.odb:

Overhead  Command   Shared Object           Symbol
  15,25%  openroad  openroad                [.] fr::FlexGridGraph::initEdges
  14,39%  openroad  openroad                [.] fr::FlexGCWorker::Impl::isCornerOverlap
   7,94%  openroad  openroad                [.] fr::FlexGCWorker::Impl::initNet_pins_polygonCorners_helper
   7,67%  openroad  openroad                [.] fr::FlexGridGraph::outOfDieVia
   6,08%  openroad  openroad                [.] fr::FlexDRWorker::modMinSpacingCostVia
   3,98%  openroad  libstdc++.so.6.0.30     [.] std::_Rb_tree_increment
   3,80%  openroad  openroad                [.] fr::FlexDRWorker::modMinSpacingCostPlanar
   2,84%  openroad  [unknown]               [k] 0xffffffffa7b87f27
   2,64%  openroad  openroad                [.] fr::FlexGridGraph::getIdx
   2,62%  openroad  openroad                [.] fr::frLayer::getMinSpacingValue
   2,11%  openroad  openroad                [.] box2boxDistSquareNew
   1,66%  openroad  openroad                [.] fr::FlexDRWorker::modMinSpacingCostVia_eol
   1,45%  openroad  openroad                [.] odb::dbTransform::apply
   1,40%  openroad  openroad                [.] fr::FlexGridGraph::isEdgeInBox
   1,36%  openroad  openroad                [.] std::vector<fr::FlexGridGraph::Node, std::allocator<fr::Fle
   1,31%  openroad  openroad                [.] fr::FlexGridGraph::addFixedShapeCostVia
   1,25%  openroad  openroad                [.] boost::geometry::index::detail::rtree::visitors::spatial_qu
   1,20%  openroad  openroad                [.] odb::dbTransform::apply
   1,15%  openroad  openroad                [.] fr::FlexDRWorker::modBlockedPlanar
   0,88%  openroad  openroad                [.] fr::frSpacingTablePrlConstraint::typeId
   0,86%  openroad  libc.so.6               [.] malloc

It's interesting thing that the 1st run with 1200 violations takes 20 minutes, the 2nd run with 700 violations takes 12 seconds:

[INFO DRT-0195] Start 1st optimization iteration.
    Completing 10% with 5729 violations.
    elapsed time = 00:02:00, memory = 29854.12 (MB).
    Completing 20% with 4647 violations.
    elapsed time = 00:04:04, memory = 30005.05 (MB).
    Completing 30% with 3871 violations.
    elapsed time = 00:06:04, memory = 30034.33 (MB).
    Completing 40% with 3694 violations.
    elapsed time = 00:08:04, memory = 30100.05 (MB).
    Completing 50% with 1899 violations.
    elapsed time = 00:10:00, memory = 28813.91 (MB).
    Completing 60% with 1471 violations.
    elapsed time = 00:11:58, memory = 29945.56 (MB).
    Completing 70% with 1042 violations.
    elapsed time = 00:13:55, memory = 29941.39 (MB).
    Completing 80% with 908 violations.
    elapsed time = 00:15:49, memory = 29953.07 (MB).
    Completing 90% with 805 violations.
    elapsed time = 00:17:44, memory = 30011.33 (MB).
    Completing 100% with 738 violations.
    elapsed time = 00:19:38, memory = 28749.75 (MB).
[INFO DRT-0199]   Number of violations = 1176.
Viol/Layer          M2     M3     V3     M4     V4     M5     M6     M7
Corner Spacing       0      0      0      2      0      0      0      0
CutSpcTbl            0      0      5      0      2      0      0      0
EOL                  0      0      0      4      0      1      0      0
Metal Spacing      209    105      0     92      0      2      0      0
Recheck             12      0      0     91      0    247      2     86
Short              157    153      0      0      0      0      0      0
eolKeepOut           0      0      0      3      0      3      0      0
[INFO DRT-0267] cpu time = 11:11:56, elapsed time = 00:19:39, memory = 28720.20 (MB), peak = 30179.07 (MB)
Total wire length = 330230 um.
Total wire length on LAYER M1 = 0 um.
Total wire length on LAYER M2 = 32835 um.
Total wire length on LAYER M3 = 28341 um.
Total wire length on LAYER M4 = 130089 um.
Total wire length on LAYER M5 = 91062 um.
Total wire length on LAYER M6 = 30826 um.
Total wire length on LAYER M7 = 17074 um.
Total wire length on LAYER M8 = 0 um.
Total wire length on LAYER M9 = 0 um.
Total wire length on LAYER Pad = 0 um.
Total number of vias = 41385.
Up-via summary (total 41385):.

----------------
 Active        0
     M1     1424
     M2     5855
     M3    20852
     M4    11321
     M5     1354
     M6      579
     M7        0
     M8        0
     M9        0
----------------
           41385


[INFO DRT-0195] Start 2nd optimization iteration.
    Completing 10% with 1154 violations.
    elapsed time = 00:00:02, memory = 28720.20 (MB).
    Completing 20% with 1135 violations.
    elapsed time = 00:00:03, memory = 28720.20 (MB).
    Completing 30% with 1116 violations.
    elapsed time = 00:00:06, memory = 28720.20 (MB).
    Completing 40% with 1078 violations.
    elapsed time = 00:00:10, memory = 28716.63 (MB).
    Completing 50% with 1059 violations.
    elapsed time = 00:00:13, memory = 28716.63 (MB).
    Completing 60% with 978 violations.
    elapsed time = 00:00:16, memory = 28716.63 (MB).
    Completing 70% with 945 violations.
    elapsed time = 00:00:17, memory = 28716.63 (MB).
    Completing 80% with 920 violations.
    elapsed time = 00:00:20, memory = 28716.63 (MB).
    Completing 90% with 755 violations.
    elapsed time = 00:00:24, memory = 28716.63 (MB).
    Completing 100% with 717 violations.
    elapsed time = 00:00:27, memory = 28716.63 (MB).
[INFO DRT-0199]   Number of violations = 755.

maliberty · 2023-05-07T21:24:56Z

maliberty
May 7, 2023
Maintainer

How many threads in your experiment?

2 replies

oharboe May 8, 2023
Collaborator Author

[INFO ORD-0030] Using 16 thread(s).

oharboe May 8, 2023
Collaborator Author

How many threads in your experiment?

See plot I added to the top description, I've plotted 8, 16, 32 and 48 threads and wall clock running time.

oharboe · 2023-05-08T04:50:15Z

oharboe
May 8, 2023
Collaborator Author

@rovinski I would not have guessed that the area of the design is what really drives up the time of detailed routing.

9 replies

rovinski May 8, 2023
Collaborator

From the profile you posted most of it makes sense - anything with init in it involves a lot of memory allocation. But this one:

   8,38%  openroad  openroad                [.] fr::FlexGridGraph::outOfDieVia

is a little suspicious in how much it consumes. There might be an opportunity for optimization there.

OpenROAD/src/drt/src/dr/FlexGridGraph.cpp

Lines 92 to 105 in ca91275

    
           bool FlexGridGraph::outOfDieVia(frMIdx x, 
        
                                           frMIdx y, 
        
                                           frMIdx z, 
        
                                           const Rect& dieBox) 
        
           { 
        
             frLayerNum lNum = getLayerNum(z) + 1; 
        
             if (lNum > getTech()->getTopLayerNum()) 
        
               return false; 
        
             frViaDef* via = getTech()->getLayer(lNum)->getDefaultViaDef(); 
        
             Rect viaBox(via->getLayer1ShapeBox()); 
        
             viaBox.merge(via->getLayer2ShapeBox()); 
        
             viaBox.moveDelta(xCoords_[x], yCoords_[y]); 
        
             return !dieBox.contains(viaBox); 
        
           }

rovinski May 8, 2023
Collaborator

I don't think there's a silver bullet here, mostly just some small optimizations which can chip away at the runtime.

oharboe May 9, 2023
Collaborator Author

The slowdown I'm seeing seem to be time taken for the detailed router to traverse the "empty" space between the elements.

Empty space can be common in a top down approach where an overgenerous floorplan has been provided at first to be tightened later.

The speed of the detailed router in architectural exploration is important, because the developer is running experiments and waiting for some sort of feedback.

oharboe May 9, 2023
Collaborator Author

Fleeting vain attempt: #3306

Post change profile

Overhead  Command   Shared Object           Symbol
  12,96%  openroad  openroad                [.] fr::FlexDRWorker::modMinSpacingCostVia                                ◆
  11,84%  openroad  openroad                [.] fr::FlexGridGraph::initEdges                                          ▒
   6,94%  openroad  openroad                [.] fr::FlexGridGraph::getIdx                                             ▒
   6,62%  openroad  openroad                [.] fr::frLayer::getMinSpacingValue                                       ▒
   6,04%  openroad  openroad                [.] fr::FlexDRWorker::modMinSpacingCostPlanar                             ▒
   5,67%  openroad  openroad                [.] fr::FlexDRWorker::modBlockedPlanar                                    ▒
   5,65%  openroad  openroad                [.] fr::FlexDRWorker::modMinSpacingCostVia_eol                            ▒
   5,59%  openroad  openroad                [.] fr::FlexGridGraph::outOfDieVia                                        ▒
   5,50%  openroad  openroad                [.] fr::FlexGridGraph::addFixedShapeCostVia                               ▒
   4,35%  openroad  openroad                [.] box2boxDistSquareNew                                                  ▒
   3,45%  openroad  openroad                [.] odb::dbTransform::apply                                               ▒
   3,17%  openroad  openroad                [.] fr::FlexDRWorker::modBlockedVia                                       ▒
   3,10%  openroad  libstdc++.so.6.0.30     [.] std::_Rb_tree_increment                                               ▒
   2,79%  openroad  openroad                [.] odb::dbTransform::apply                                               ▒
   2,67%  openroad  openroad                [.] fr::FlexDRWorker::modMinSpacingCostVia_eol_helper                     ▒
   2,34%  openroad  openroad                [.] fr::frSpacingTablePrlConstraint::typeId                               ▒
   1,17%  openroad  openroad                [.] fr::FlexGridGraph::isEdgeInBox                                        ▒
   1,10%  openroad  openroad                [.] fr::FlexGCWorker::Impl::isCornerOverlap                               ▒
   0,96%  openroad  [unknown]               [k] 0xffffffff9b587f27                                                    ▒
   0,75%  openroad  openroad                [.] fr::FlexGridGraph::getIdxBox                                          ▒
   0,63%  openroad  openroad                [.] std::vector<fr::FlexGridGraph::Node, std::allocator<fr::FlexGridGraph:▒
   0,58%  openroad  openroad                [.] fr::FlexGCWorker::Impl::initNet_pins_polygonCorners_helper            ▒
   0,53%  openroad  openroad                [.] odb::dbTechLayer::getNumMasks                                         ▒
   0,12%  openroad  libc.so.6               [.] __memset_avx2_unaligned_erms                                          ▒
   0,12%  openroad  [unknown]               [k] 0xffffffff9af4e19d                                                    ▒

oharboe May 9, 2023
Collaborator Author

I wonder if the "final" keyword will have any effect with -O3...

#3308

Doesn't appear to do much.

Overhead  Command   Shared Object            Symbol
  13,07%  openroad  openroad                 [.] fr::FlexDRWorker::modMinSpacingCostVia
  11,88%  openroad  openroad                 [.] fr::FlexGridGraph::initEdges
   6,88%  openroad  openroad                 [.] fr::FlexGridGraph::getIdx
   6,61%  openroad  openroad                 [.] fr::frLayer::getMinSpacingValue
   6,23%  openroad  openroad                 [.] fr::FlexGridGraph::outOfDieVia
   5,93%  openroad  openroad                 [.] fr::FlexDRWorker::modMinSpacingCostPlanar
   5,65%  openroad  openroad                 [.] fr::FlexDRWorker::modMinSpacingCostVia_eol
   5,55%  openroad  openroad                 [.] fr::FlexDRWorker::modBlockedPlanar
   5,52%  openroad  openroad                 [.] fr::FlexGridGraph::addFixedShapeCostVia
   4,40%  openroad  openroad                 [.] box2boxDistSquareNew
   3,40%  openroad  openroad                 [.] odb::dbTransform::apply
   3,04%  openroad  libstdc++.so.6.0.30      [.] std::_Rb_tree_increment
   3,04%  openroad  openroad                 [.] fr::FlexDRWorker::modBlockedVia
   2,78%  openroad  openroad                 [.] odb::dbTransform::apply
   2,66%  openroad  openroad                 [.] fr::FlexDRWorker::modMinSpacingCostVia_eol_helper
   2,30%  openroad  openroad                 [.] fr::frSpacingTablePrlConstraint::typeId
   1,15%  openroad  openroad                 [.] fr::FlexGridGraph::isEdgeInBox
   1,13%  openroad  openroad                 [.] fr::FlexGCWorker::Impl::isCornerOverlap
   0,97%  openroad  [unknown]                [k] 0xffffffff9b587f27
   0,69%  openroad  openroad                 [.] fr::FlexGridGraph::getIdxBox

maliberty · 2023-05-08T18:37:25Z

maliberty
May 8, 2023
Maintainer

The area of the design will definitely matter. You will have tracks at the same pitch and have to traverse more of them during routing a larger area.

0 replies

maliberty · 2023-05-08T19:57:45Z

maliberty
May 8, 2023
Maintainer

Rather than plot "detailed route times plotted against threads" it is usually easier to look at speedup (t(1)/t(N)) vs threads. It makes it clearer how close to ideal scaling you are getting (the 45 degree line is perfect).

1 reply

oharboe May 8, 2023
Collaborator Author

I didn't measure t(1), smallest I did was 8 threads. It takes forever to measure t(1)...

I messed around a bit. It won't be a 45 degree as that would require tinkering with the axis...

So here 6 on the x axis is 6 * 8 = 48 threads.

oharboe · 2023-05-09T18:33:44Z

oharboe
May 9, 2023
Collaborator Author

@maliberty @rovinski I fixed the image for the 1000x1000um when I took a snapshot. I accidentally used the small macro, the spacing between the macros should be very short, nearly abutment.

0 replies

oharboe · 2023-05-18T06:52:10Z

oharboe
May 18, 2023
Collaborator Author

It looks like the expected behavior is that the 0th and the 1st iteration will take a long time for top level designs with lots of wires and little contention, even if these routes are horizontal and vertical and that the low hanging fruit has already been picked.

1 reply

Kivamar Jun 20, 2023

very interesting, thank you

binsa7261 · 2023-06-30T18:04:20Z

binsa7261
Jun 30, 2023

wow this looks very impressive, bravo!

0 replies

v11sman · 2023-07-17T17:16:59Z

v11sman
Jul 17, 2023

I learned a lot of interesting things

0 replies

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Running times in detailed routing as a function of design parameters #3298

{{title}}

{{editor}}'s edit

{{editor}}'s edit

Replies: 8 comments 13 replies

{{title}}

{{title}}

{{title}}

{{title}}

{{editor}}'s edit

{{editor}}'s edit

{{title}}

{{title}}

{{title}}

{{title}}

{{editor}}'s edit

{{editor}}'s edit

{{title}}

{{editor}}'s edit

{{editor}}'s edit

{{title}}

{{title}}

{{title}}

{{editor}}'s edit

{{editor}}'s edit

{{title}}

{{editor}}'s edit

{{editor}}'s edit

{{title}}

{{title}}

{{title}}

{{title}}

Select a reply

Running times in detailed routing as a function of design parameters #3298

oharboe May 7, 2023 Collaborator

Replies: 8 comments · 13 replies

maliberty May 7, 2023 Maintainer

oharboe May 8, 2023 Collaborator Author

oharboe May 8, 2023 Collaborator Author

oharboe May 8, 2023 Collaborator Author

rovinski May 8, 2023 Collaborator

rovinski May 8, 2023 Collaborator

oharboe May 9, 2023 Collaborator Author

oharboe May 9, 2023 Collaborator Author

oharboe May 9, 2023 Collaborator Author

maliberty May 8, 2023 Maintainer

maliberty May 8, 2023 Maintainer

oharboe May 8, 2023 Collaborator Author

oharboe May 9, 2023 Collaborator Author

oharboe May 18, 2023 Collaborator Author

Kivamar Jun 20, 2023

binsa7261 Jun 30, 2023

v11sman Jul 17, 2023

oharboe
May 7, 2023
Collaborator

Replies: 8 comments 13 replies

maliberty
May 7, 2023
Maintainer

oharboe May 8, 2023
Collaborator Author

oharboe May 8, 2023
Collaborator Author

oharboe
May 8, 2023
Collaborator Author

rovinski May 8, 2023
Collaborator

rovinski May 8, 2023
Collaborator

oharboe May 9, 2023
Collaborator Author

oharboe May 9, 2023
Collaborator Author

oharboe May 9, 2023
Collaborator Author

maliberty
May 8, 2023
Maintainer

maliberty
May 8, 2023
Maintainer

oharboe May 8, 2023
Collaborator Author

oharboe
May 9, 2023
Collaborator Author

oharboe
May 18, 2023
Collaborator Author

binsa7261
Jun 30, 2023

v11sman
Jul 17, 2023