search

The-OpenROAD-Project / OpenROAD

OpenROAD's unified application implementing an RTL-to-GDS Flow. Documentation at https://openroad.readthedocs.io/en/latest/
https://theopenroadproject.org/
BSD 3-Clause "New" or "Revised" License
1.59k stars 552 forks source link

DRT: long runtime due to unsolvable DRCs #5391

Open eder-matheus opened 3 months ago

eder-matheus commented 3 months ago

Describe the bug

From https://github.com/The-OpenROAD-Project/OpenROAD-flow-scripts/pull/2142, sky130hs/riscv32i has a huge runtime after the changes during synthesis. It happens due to a bad routing resources configuration, leading to many wires assigned to a congested region. DRT takes more than half of the iterations trying to solve 36 violations that look unsolvable.

Expected Behavior

DRT should give up on hopeless designs.

Environment

Git commit: 86e37aa483fe5409095cd4e68ff140f57a19998d
kernel: Linux 6.5.0-1023-gcp
os: Ubuntu 22.04.4 LTS (Jammy Jellyfish)
cmake version 3.24.2
-- The CXX compiler identification is GNU 11.4.0
-- Detecting CXX compiler ABI info
-- Detecting CXX compiler ABI info - done
-- Check for working CXX compiler: /usr/bin/c++ - skipped
-- Detecting CXX compile features
-- Detecting CXX compile features - done
-- OpenROAD version: v2.0-14595-g86e37aa48
-- System name: Linux
-- Compiler: GNU 11.4.0
-- Build type: RELEASE
-- Install prefix: /usr/local
-- C++ Standard: 17
-- C++ Standard Required: ON
-- C++ Extensions: OFF
-- The C compiler identification is GNU 11.4.0
-- Detecting C compiler ABI info
-- Detecting C compiler ABI info - done
-- Check for working C compiler: /usr/bin/cc - skipped
-- Detecting C compile features
-- Detecting C compile features - done
-- Found Python: /usr/bin/python3.10 (found version "3.10.12") found components: Interpreter
-- Performing Test CMAKE_HAVE_LIBC_PTHREAD
-- Performing Test CMAKE_HAVE_LIBC_PTHREAD - Success
-- Found Threads: TRUE
-- Performing Test C_COMPILER_SUPPORTS__-Wall
-- Performing Test C_COMPILER_SUPPORTS__-Wall - Success
-- Performing Test CXX_COMPILER_SUPPORTS__-Wall
-- Performing Test CXX_COMPILER_SUPPORTS__-Wall - Success
-- 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 -CMake Warning (dev) at src/sta/CMakeLists.txt:33 (option):
  Policy CMP0077 is not set: option() honors normal variables.  Run "cmake
  --help-policy CMP0077" for policy details.  Use the cmake_policy command to
  set the policy and suppress this warning.

  For compatibility with older versions of CMake, option is clearing the
  normal variable 'USE_TCL_READLINE'.
This warning is for project developers.  Use -Wno-dev to suppress it.

 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__-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__-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__-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
-- 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.1.0", minimum required is "4.0")
-- Using SWIG >= 4.1.0 -flatstaticmethod flag for python
-- Found Boost: /usr/local/lib/cmake/Boost-1.80.0/BoostConfig.cmake (found version "1.80.0")
-- boost: 1.80.0
-- Found Python3: /usr/include/python3.10 (found version "3.10.12") found components: Development Development.Module Development.Embed
-- Found ZLIB: /usr/lib/x86_64-linux-gnu/libz.so (found version "1.2.11")
-- spdlog: 1.8.1
-- Found BISON: /usr/bin/bison (found version "3.8.2")
-- Could NOT find Doxygen (missing: DOXYGEN_EXECUTABLE)
-- STA version: 2.5.0
-- STA git sha: 1c7f022cd0a02ce71d047aa3dbb64e924b6efbd5
-- System name: Linux
-- Compiler: GNU 11.4.0
-- Build type: RELEASE
-- Build CXX_FLAGS: -O3 -DNDEBUG
-- Install prefix: /usr/local
-- 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
-- SSTA: 0
-- Found SWIG: /usr/local/bin/swig (found suitable version "4.1.0", minimum required is "3.0")
-- STA executable: /home/emonteiro_openroad_tools/OpenROAD-flow-scripts/tools/OpenROAD/src/sta/app/sta
-- Found re2: /opt/or-tools/lib/cmake/re2/re2Config.cmake (found version "9.0.0")
-- Found Clp: /opt/or-tools/lib/cmake/Clp/ClpConfig.cmake (found version "1.17.7")
-- Found Cbc: /opt/or-tools/lib/cmake/Cbc/CbcConfig.cmake (found version "2.10.7")
-- Found SCIP: /opt/or-tools/lib/cmake/scip/scip-config.cmake (found version "8.0.1")
-- Found OpenMP_CXX: -fopenmp (found version "4.5")
-- Found OpenMP: TRUE (found version "4.5")
-- 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")
-- GUI is enabled
-- Charts widget is not enabled
-- Found Boost: /usr/local/lib/cmake/Boost-1.80.0/BoostConfig.cmake (found version "1.80.0") found components: serialization
-- Could NOT find VTune (missing: VTune_LIBRARIES VTune_INCLUDE_DIRS)
-- Found Boost: /usr/local/lib/cmake/Boost-1.80.0/BoostConfig.cmake (found suitable version "1.80.0", minimum required is "1.78")
-- TCL library: /usr/lib/x86_64-linux-gnu/libtcl.so
-- TCLNumber of processor cores: 32
 header: /usr/include/tcl/tcl.h
-- Found Boost: /usr/local/lib/cmake/Boost-1.80.0/BoostConfig.cmake (found version "1.80.0") found components: serialization system thread
-- Found Boost: /usr/local/lib/cmake/Boost-1.80.0/BoostConfig.cmake (found version "1.80.0")
-- Found Eigen3: /usr/local/share/eigen3/cmake/Eigen3Config.cmake (found version "3.4.1")
-- TCL readline enabled
-- Tcl Extended disabled
-- Python3 enabled
-- Configuring done
-- Generating done
-- Build files have been written to: /tmp/tmp.7iB4sPiEuj

To Reproduce

Test case available here: https://drive.google.com/file/d/1c7lxyFGMgj7dW62qUXk2nnEbXUs1-IAF/view?usp=sharing Another case where DRT struggles with lots of DRCs (specifically shorts): https://drive.google.com/file/d/1DdmM-jvEBQU2zW74LxlAi9veSflmJj12/view?usp=sharing

Relevant log output

No response

Screenshots

No response

Additional Context

No response

gadfort commented 3 months ago

This is similar to: https://github.com/The-OpenROAD-Project/OpenROAD/issues/5305

gadfort commented 3 months ago

I think the better solution would be to figure out why DRT is generating so many shorts as the starting point.

eder-matheus commented 3 months ago

@gadfort For both designs, the problem seems to be the route guides generated by GRT. We were using very low resource adjustments (20%) for these designs, and when I increased it to 40%, both sky130hd/aes and sky130hs/riscv32i finished in less than 20 iterations.

What happens is that when using very low reduction values, GRT assigns too many nets to the same region, which can make DRT struggle to find a clean solution. I'm investigating how to turn GRT smarter about the resources available, in parallel to understanding if it's possible to detect if a design can't be routed without DRCs.

gadfort commented 3 months ago

@eder-matheus is it possible the original resources are not getting computed correctly? If I don't apply any reductions, I would assume the capacities reported should reflect the number of tracks available.

In the image below, you can see the capacity (20) is reported for the GCell (it's hard to see the outline), but if I count the number of resources it's 16 if I exclude the tracks that are inside the power rails, in this cell, global routing is using 17 resources which might be contributing to the issue. image

It looks like GRT should be derating the power, but this appears to not be the case here.

eder-matheus commented 3 months ago

@gadfort If I remember correctly, the Capacity shown in the GUI is the first computed (i.e., it considers all the resources calculated before any reduction). The usage would include the reductions from blockages and user-defined adjustments and the routing. I'll double-check if that is the case.

eder-matheus commented 3 months ago

@gadfort If I remember correctly, the Capacity shown in the GUI is the first computed (i.e., it considers all the resources calculated before any reduction). The usage would include the reductions from blockages and user-defined adjustments and the routing. I'll double-check if that is the case.

That's how it works. I load the design without running the routing, and it shows what I described: the capacity is the full resources calculated at first, and the reductions from blockages are shown in the usage.

gadfort commented 3 months ago

@eder-matheus ahh, okay. thanks for checking on that

stefanottili commented 3 months ago

grt needs to be a lot less optimistic about routing resources … see https://github.com/The-OpenROAD-Project/OpenROAD/issues/5061

gadfort commented 3 months ago

@eder-matheus just updating the routing resources per design doesn't seem that viable and overall is a sub-par solution. Now that your CI is down to 9 minutes, how are you going to track the improvements made here?

eder-matheus commented 3 months ago

@eder-matheus just updating the routing resources per design doesn't seem that viable and overall is a sub-par solution. Now that your CI is down to 9 minutes, how are you going to track the improvements made here?

In this issue, we have a test case where the vast number of shorts still happens. I also found the files for an old run (before my update in the routing resources) for sky130hd/aes, which takes almost two hours only in DRT. It's available here: https://drive.google.com/file/d/1DdmM-jvEBQU2zW74LxlAi9veSflmJj12/view?usp=sharing.

And I agree there are better solutions than updating the config files per design. I had to make this change for sky130hd/aes to have an important PR merged, but GRT should be more intelligent in how it handles congestion without user input.

eder-matheus commented 3 months ago

@gadfort FYI, I created this issue to track the necessary GRT enhancement regarding routing resource adjustments: https://github.com/The-OpenROAD-Project/OpenROAD/issues/5423.