est: Long runtime of `EstimateParasitics::estimateWireParasiticSteiner()` in `nangate45/bp_quad`

[jhkim-pii]

Describe the bug

Symptom

nangate45/bp_quad design suffers from the long runtime at the 3_3 global placement stage.
No more log printing more than 5 hours after this.

OR commit: 809a904
ORFS commit: 1face853132bd640ca2e8124ff6b94e51e0aa970

flow$ make DESIGN_CONFIG=./designs/nangate45/bp_quad/config.mk

13:48:38        280 |   0.7989 |  1.915588e+07 |   +5.99% |  1.99e-10 |      
13:48:56        290 |   0.7745 |  2.015698e+07 |   +5.23% |  2.54e-10 |      
13:49:18        300 |   0.7640 |  1.937550e+07 |   -3.88% |  4.11e-10 |      
13:49:36        310 |   0.7209 |  1.962389e+07 |   +1.28% |  6.11e-10 |      
13:49:58        320 |   0.6801 |  1.915879e+07 |   -2.37% |  9.14e-10 |      
13:50:16        330 |   0.6424 |  1.841629e+07 |   -3.88% |  1.47e-09 |      
13:50:18  [INFO GPL-0100] Timing-driven iteration 1/2, virtual: false.
13:50:18  [INFO GPL-0101]    Iter: 333, overflow: 0.631, keep resizer changes at: 1, HPWL: 37423852004
13:57:25  Iteration |   Area    | Resized | Buffers | Nets repaired | Remaining
13:57:25  ---------------------------------------------------------------------
13:57:25          0 |     +0.0% |       0 |       0 |             0 |    998005

GDB stacktrace

(gdb) bt
#0  0x000056388beb425e in pdr::get_nearest_neighbors(std::vector<odb::Point, std::allocator<odb::Point> > const&) ()
#1  0x000056388beb4bd1 in pdr::primDijkstra(std::vector<int, std::allocator<int> > const&, std::vector<int, std::allocator<int> > const&, int, float, utl::Logger*) ()
#2  0x000056388beb69ed in stt::SteinerTreeBuilder::makeSteinerTree(std::vector<int, std::allocator<int> > const&, std::vector<int, std::allocator<int> > const&, int, float) ()
#3  0x000056388beb6bd4 in stt::SteinerTreeBuilder::makeSteinerTree(odb::dbNet*, std::vector<int, std::allocator<int> > const&, std::vector<int, std::allocator<int> > const&, int) ()
#4  0x000056388bd83f19 in est::EstimateParasitics::makeSteinerTree(sta::Pin const*) ()
#5  0x000056388bd840da in est::EstimateParasitics::estimateWireParasiticSteiner(sta::Pin const*, sta::Net const*, sta::SpefWriter*) ()
#6  0x000056388bd86c0f in est::EstimateParasitics::updateParasitics(bool) ()
#7  0x000056388bcce565 in rsz::RepairDesign::repairNet(sta::Net*, sta::Pin const*, sta::Vertex*, bool, bool, bool, int, bool, sta::Scene*, int&, int&, int&, int&, int&) ()
#8  0x000056388bcd0290 in rsz::RepairDesign::repairDriver(sta::Vertex*, bool, bool, bool, int, bool, sta::Scene*, int&, int&, int&, int&, int&)
    ()
#9  0x000056388bcd34ac in rsz::RepairDesign::repairDesign(double, double, double, bool, bool, int&, int&, int&, int&, int&) ()
#10 0x000056388bc82d3c in rsz::Resizer::findResizeSlacks(bool) ()
#11 0x000056388b8305ed in gpl::TimingBase::executeTimingDriven(bool) ()
#12 0x000056388b7dae04 in gpl::NesterovPlace::runTimingDriven(int, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&, int, int&, long&, bool) ()
#13 0x000056388b830099 in gpl::NesterovPlace::doNesterovPlace(int) ()
#14 0x000056388b7eb623 in gpl::Replace::doNesterovPlace(int, gpl::PlaceOptions const&, int) ()
#15 0x000056388a06d23f in replace_nesterov_place_cmd(std::map<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, std::less<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > >, std::allocator<std::pair<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > > > > const&, std::map<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, std::less<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > >, std::allocator<std::pair<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > > > > const&) ()
#16 0x000056388a0717c4 in _wrap_replace_nesterov_place_cmd ()
#17 0x000078b7d8adc2f9 in TclNRRunCallbacks () from /lib/x86_64-linux-gnu/libtcl8.6.so
#18 0x000078b7d8add6bc in ?? () from /lib/x86_64-linux-gnu/libtcl8.6.so
#19 0x000078b7d8add10b in Tcl_EvalEx () from /lib/x86_64-linux-gnu/libtcl8.6.so
#20 0x000078b7d8ade42a in Tcl_Eval () from /lib/x86_64-linux-gnu/libtcl8.6.so
#21 0x000056388a123f8d in sta::sourceTclFile(char const*, bool, bool, Tcl_Interp*) ()
#22 0x000056388c4d5efe in tclAppInit(int&, char**, char const*, Tcl_Interp*) [clone .constprop.0] ()
#23 0x000078b7d8b93eea in Tcl_MainEx () from /lib/x86_64-linux-gnu/libtcl8.6.so
#24 0x0000563889f73c9a in main ()

Expected Behavior

No hang. Reasonable runtime.

Environment

-- The CXX compiler identification is GNU 13.3.0
-- Detecting CXX compiler ABI info
-- Detecting CXX compiler ABI info - done
-- Check for working CXX compiler: /usr/bin/g++ - skipped
-- Detecting CXX compile features
-- Detecting CXX compile features - done
-- OpenROAD version: 26Q1-1144-g809a904c3f
-- System name: Linux
-- Compiler: GNU 13.3.0
-- Build type: DEBUG
-- Install prefix: /usr/local
-- C++ Standard: 20
-- C++ Standard Required: ON
-- C++ Extensions: OFF
-- LTO/IPO is disabled
-- The C compiler identification is GNU 13.3.0
-- Detecting C compiler ABI info
-- Detecting C compiler ABI info - done
-- Check for working C compiler: /usr/bin/gcc - skipped
-- Detecting C compile features
-- Detecting C compile features - done
-- Performing Test C_COMPILER_SUPPORTS__-Wno-array-bounds
-- Performing Test C_COMPILER_SUPPORTS__-Wno-array-bounds - Success
-- Performing Test CXX_COMPILER_SUPPORTS__-Wno-array-bounds
-- Performing Test CXX_COMPILER_SUPPORTS__-Wno-array-bounds - Success
-- Performing Test C_COMPILER_SUPPORTS__-Wno-nonnull
-- Performing Test C_COMPILER_SUPPORTS__-Wno-nonnull - Success
-- Performing Test CXX_COMPILER_SUPPORTS__-Wno-nonnull
-- Performing Test CXX_COMPILER_SUPPORTS__-Wno-nonnull - Success
-- Performing Test C_COMPILER_SUPPORTS__-Wno-maybe-uninitialized
-- Performing Test C_COMPILER_SUPPORTS__-Wno-maybe-uninitialized - Success
-- Performing Test CXX_COMPILER_SUPPORTS__-Wno-maybe-uninitialized
-- Performing Test CXX_COMPILER_SUPPORTS__-Wno-maybe-uninitialized - Success
-- Performing Test C_COMPILER_SUPPORTS__-Wno-format-overflow
-- Performing Test C_COMPILER_SUPPORTS__-Wno-format-overflow - Success
-- Performing Test CXX_COMPILER_SUPPORTS__-Wno-format-overflow
-- Performing Test CXX_COMPILER_SUPPORTS__-Wno-format-overflow - Success
-- Performing Test C_COMPILER_SUPPORTS__-Wno-unused-variable
-- Performing Test C_COMPILER_SUPPORTS__-Wno-unused-variable - Success
-- Performing Test CXX_COMPILER_SUPPORTS__-Wno-unused-variable
-- Performing Test CXX_COMPILER_SUPPORTS__-Wno-unused-variable - Success
-- Performing Test C_COMPILER_SUPPORTS__-Wno-unused-function
-- Performing Test C_COMPILER_SUPPORTS__-Wno-unused-function - Success
-- Performing Test CXX_COMPILER_SUPPORTS__-Wno-unused-function
-- Performing Test CXX_COMPILER_SUPPORTS__-Wno-unused-function - Success
-- Performing Test C_COMPILER_SUPPORTS__-Wno-write-strings
-- Performing Test C_COMPILER_SUPPORTS__-Wno-write-strings - Success
-- Performing Test CXX_COMPILER_SUPPORTS__-Wno-write-strings
-- Performing Test CXX_COMPILER_SUPPORTS__-Wno-write-strings - Success
-- Performing Test C_COMPILER_SUPPORTS__-Wno-sign-compare
-- Performing Test C_COMPILER_SUPPORTS__-Wno-sign-compare - Success
-- Performing Test CXX_COMPILER_SUPPORTS__-Wno-sign-compare
-- Performing Test CXX_COMPILER_SUPPORTS__-Wno-sign-compare - Success
-- Performing Test C_COMPILER_SUPPORTS__-Wno-deprecated
-- Performing Test C_COMPILER_SUPPORTS__-Wno-deprecated - Success
-- Performing Test CXX_COMPILER_SUPPORTS__-Wno-deprecated
-- Performing Test CXX_COMPILER_SUPPORTS__-Wno-deprecated - Success
-- Performing Test C_COMPILER_SUPPORTS__-Wno-c++11-narrowing
-- Performing Test C_COMPILER_SUPPORTS__-Wno-c++11-narrowing - Failed
-- Performing Test CXX_COMPILER_SUPPORTS__-Wno-c++11-narrowing
-- Performing Test CXX_COMPILER_SUPPORTS__-Wno-c++11-narrowing - Failed
-- Performing Test C_COMPILER_SUPPORTS__-Wno-register
-- Performing Test C_COMPILER_SUPPORTS__-Wno-register - Failed
-- Performing Test CXX_COMPILER_SUPPORTS__-Wno-register
-- Performing Test CXX_COMPILER_SUPPORTS__-Wno-register - Success
-- Performing Test C_COMPILER_SUPPORTS__-Wno-format
-- Performing Test C_COMPILER_SUPPORTS__-Wno-format - Success
-- Performing Test CXX_COMPILER_SUPPORTS__-Wno-format
-- Performing Test CXX_COMPILER_SUPPORTS__-Wno-format - Success
-- Performing Test C_COMPILER_SUPPORTS__-Wno-reserved-user-defined-literal
-- Performing Test C_COMPILER_SUPPORTS__-Wno-reserved-user-defined-literal - Failed
-- Performing Test CXX_COMPILER_SUPPORTS__-Wno-reserved-user-defined-literal
-- Performing Test CXX_COMPILER_SUPPORTS__-Wno-reserved-user-defined-literal - Failed
-- Performing Test C_COMPILER_SUPPORTS__-Wno-alloc-size-larger-than
-- Performing Test C_COMPILER_SUPPORTS__-Wno-alloc-size-larger-than - Success
-- Performing Test CXX_COMPILER_SUPPORTS__-Wno-alloc-size-larger-than
-- Performing Test CXX_COMPILER_SUPPORTS__-Wno-alloc-size-larger-than - Success
-- Performing Test C_COMPILER_SUPPORTS__-Wno-attributes
-- Performing Test C_COMPILER_SUPPORTS__-Wno-attributes - Success
-- Performing Test CXX_COMPILER_SUPPORTS__-Wno-attributes
-- Performing Test CXX_COMPILER_SUPPORTS__-Wno-attributes - Success
-- Performing Test C_COMPILER_SUPPORTS__-Wno-aggressive-loop-optimizations
-- Performing Test C_COMPILER_SUPPORTS__-Wno-aggressive-loop-optimizations - Success
-- Performing Test CXX_COMPILER_SUPPORTS__-Wno-aggressive-loop-optimizations
-- Performing Test CXX_COMPILER_SUPPORTS__-Wno-aggressive-loop-optimizations - Success
-- Performing Test C_COMPILER_SUPPORTS__-Wno-stringop-overflow
-- Performing Test C_COMPILER_SUPPORTS__-Wno-stringop-overflow - Success
-- Performing Test CXX_COMPILER_SUPPORTS__-Wno-stringop-overflow
-- Performing Test CXX_COMPILER_SUPPORTS__-Wno-stringop-overflow - Success
-- Performing Test C_COMPILER_SUPPORTS__-Wno-changes-meaning
-- Performing Test C_COMPILER_SUPPORTS__-Wno-changes-meaning - Failed
-- Performing Test CXX_COMPILER_SUPPORTS__-Wno-changes-meaning
-- Performing Test CXX_COMPILER_SUPPORTS__-Wno-changes-meaning - Success
-- Performing Test C_COMPILER_SUPPORTS__-fpermissive
-- Performing Test C_COMPILER_SUPPORTS__-fpermissive - Failed
-- Performing Test CXX_COMPILER_SUPPORTS__-fpermissive
-- Performing Test CXX_COMPILER_SUPPORTS__-fpermissive - Success
-- Performing Test C_COMPILER_SUPPORTS__-x
-- Performing Test C_COMPILER_SUPPORTS__-x - Failed
-- Performing Test CXX_COMPILER_SUPPORTS__-x
-- Performing Test CXX_COMPILER_SUPPORTS__-x - Failed
-- Performing Test C_COMPILER_SUPPORTS__c++
-- Performing Test C_COMPILER_SUPPORTS__c++ - Failed
-- Performing Test CXX_COMPILER_SUPPORTS__c++
-- Performing Test CXX_COMPILER_SUPPORTS__c++ - Failed
-- Performing Test C_COMPILER_SUPPORTS__-Wno-unused-but-set-variable
-- Performing Test C_COMPILER_SUPPORTS__-Wno-unused-but-set-variable - Success
-- Performing Test CXX_COMPILER_SUPPORTS__-Wno-unused-but-set-variable
-- Performing Test CXX_COMPILER_SUPPORTS__-Wno-unused-but-set-variable - Success
-- Performing Test C_COMPILER_SUPPORTS__-std=c++17
-- Performing Test C_COMPILER_SUPPORTS__-std=c++17 - Failed
-- Performing Test CXX_COMPILER_SUPPORTS__-std=c++17
-- Performing Test CXX_COMPILER_SUPPORTS__-std=c++17 - Success
-- Performing Test C_COMPILER_SUPPORTS__-fno-exceptions
-- Performing Test C_COMPILER_SUPPORTS__-fno-exceptions - Success
-- Performing Test CXX_COMPILER_SUPPORTS__-fno-exceptions
-- Performing Test CXX_COMPILER_SUPPORTS__-fno-exceptions - Success
-- TCL library: /usr/lib/x86_64-linux-gnu/libtcl.so
-- TCL header: /usr/include/tcl/tcl.h
-- TCL readline library: /usr/lib/x86_64-linux-gnu/libtclreadline.so
-- TCL readline header: /usr/include/x86_64-linux-gnu
-- Found SWIG: /usr/local/bin/swig (found suitable version "4.3.0", minimum required is "4.0")
-- Using SWIG >= 4.3.0 -flatstaticmethod flag for python
-- boost: 1.89.0
-- Performing Test CMAKE_HAVE_LIBC_PTHREAD
-- Performing Test CMAKE_HAVE_LIBC_PTHREAD - Success
-- Found Threads: TRUE
-- Found GTest: /usr/local/lib/cmake/GTest/GTestConfig.cmake (found version "1.13.0")
-- GTest: 1.13.0
-- Found Python3: /usr/include/python3.12 (found version "3.12.3") found components: Development Development.Module Development.Embed
-- Found ZLIB: /usr/lib/x86_64-linux-gnu/libz.so (found version "1.3")
-- spdlog: 1.15.0
-- Found BISON: /usr/bin/bison (found version "3.8.2")
-- Found Doxygen: /usr/bin/doxygen (found version "1.9.8") found components: doxygen dot
-- STA version: 3.0.0
-- STA git sha: 7937b647b608b7d04ffc21ca9ed74c42c818f330
-- System name: Linux
-- Compiler: GNU 13.3.0
-- Build type: DEBUG
-- Build CXX_FLAGS: -g
-- Install prefix: /usr/local
-- IPO/LTO: not supported - CMake doesn't support IPO for current C compiler
-- Found FLEX: /usr/bin/flex (found version "2.6.4")
-- TCL library: /usr/lib/x86_64-linux-gnu/libtcl.so
-- TCL header: /usr/include/tcl/tcl.h
-- TCL readline library: /usr/lib/x86_64-linux-gnu/libtclreadline.so
-- TCL readline header: /usr/include/x86_64-linux-gnu/tclreadline.h
-- CUDD library: /usr/local/lib/libcudd.a
-- CUDD header: /usr/local/include/cudd.h
-- SSTA: 0
-- Found SWIG: /usr/local/bin/swig (found suitable version "4.3.0", minimum required is "3.0")
-- STA library: /workspace/ws7/OpenROAD-flow-scripts/tools/OpenROAD/build/libOpenSTA.a
-- STA executable: /workspace/ws7/OpenROAD-flow-scripts/tools/OpenROAD/build/sta
-- Found BZip2: /opt/or-tools/lib/libbz2.so (found version "1.1.0")
-- Looking for BZ2_bzCompressInit
-- Looking for BZ2_bzCompressInit - found
-- Found re2: /opt/or-tools/lib/cmake/re2/re2Config.cmake (found version "11.0.0")
-- Found Clp: /opt/or-tools/lib/cmake/Clp/ClpConfig.cmake (found version "1.17.10")
-- Found Cbc: /opt/or-tools/lib/cmake/Cbc/CbcConfig.cmake (found version "2.10.12")
-- Found SCIP: /opt/or-tools/lib/cmake/scip/scip-config.cmake (found version "9.2.2")
-- Found OpenMP_CXX: -fopenmp (found version "4.5")
-- Found OpenMP: TRUE (found version "4.5")
-- Found OR-Tools: /opt/or-tools/lib/cmake/ortools (version: 9.14.6206)
-- TCL library: /usr/lib/x86_64-linux-gnu/libtcl.so
-- TCL header: /usr/include/tcl/tcl.h
-- Found OpenMP_C: -fopenmp (found version "4.5")
-- Found OpenMP: TRUE (found version "4.5")
-- Found OpenMP: TRUE (found version "4.5")
-- Found OpenGL: /usr/lib/x86_64-linux-gnu/libOpenGL.so
-- GUI is enabled
-- Could NOT find VTune (missing: VTune_LIBRARIES VTune_INCLUDE_DIRS) 
-- TCL library: /usr/lib/x86_64-linux-gnu/libtcl.so
-- TCL header: /usr/include/tcl/tcl.h
-- Found Eigen3: /usr/local/share/eigen3/cmake/Eigen3Config.cmake (found version "3.4.1")
-- TCL readline enabled
-- Tcl Extended disabled
-- Python3 enabled

To Reproduce

OR commit: 809a904
ORFS commit: 1face853132bd640ca2e8124ff6b94e51e0aa970

flow$ make DESIGN_CONFIG=./designs/nangate45/bp_quad/config.mk

Relevant log output

Screenshots

No response

Additional Context

No response

[jhkim-pii]

  pdr::get_nearest_neighbors() at pd.cpp:82                                                 
    └─ pdr::primDijkstra()     at pd.cpp:458    ← pts vector has 189,648 points !!! --> Long runtime
      └─ stt::SteinerTreeBuilder::makeSteinerTree()               
        └─ est::EstimateParasitics::estimateWireParasiticSteiner()
          └─ rsz::RepairDesign::repairNet()
            └─ rsz::RepairDesign::repairDesign()
              └─ rsz::Resizer::findResizeSlacks()
                └─ gpl::TimingBase::executeTimingDriven()
                  └─ gpl::NesterovPlace::runTimingDriven()  ← iter=352
                    └─ gpl::NesterovPlace::doNesterovPlace()

Target pin: p_clk_A_i (SigType=SIGNAL, 189K load pins)
It looks like estimateWireParasiticsSteiner() tries to estimate RC for the high fanout clock pin.
It is the GPL stage, and the clock network is ideal. So the RC estimation trial looks weird.

[maliberty]

Why is RepairDesign::repairNet even looking at such a net?

[povik]

Related to #9502 from last week

[eder-matheus]

I believe this issue was fixed in #9547