Galoised BfsIterator

[yishanlu]

Improved BfsIterator using the Galois framework.

~2X speedup compared to original BfIterator when using Galoised BfsIterator for full timing update on large circuits in TAU 2019 benchmark suites.

Steps to compile this version

• Install Galois as a library as indicated here. You need at least cmake and boost library. The compiler should support c++14 syntax.
• Run export GALOIS_PREFIX_PATH=<prefix_path_where_you_install_galois>.
• Replace $GALOIS_PREFIX_PATH/lib/CMake/Galois/GaloisConfig.cmake: 20 as follows: set(Galois_CXX_FLAGS "-D__STDC_CONSTANT_MACROS -D__STDC_LIMIT_MACROS -DBOOST_NO_AUTO_PTR -DGALOIS_USE_LONGJMP_ABORT -DGALOIS_COPYRIGHT_YEAR=2018 -DGALOIS_VERSION=5.0.0 -DGALOIS_VERSION_PATCH=0 -DGALOIS_VERSION_MINOR=0 -DGALOIS_VERSION_MAJOR=5 -g -Wall -march=\"native\" -O3 -DNDEBUG")
• Build OpenSTA as usual. Now you have the Galoised BfsIterator.

Choosing Galoised/original BfsIterator

• The flag use_galoised_bfs_iterator in /search/Bfs.cc: 35 controls which BfsIterator is used.
• Set the flag to true and then recompile OpenSTA to use the Galoised BfsIterator.
• Set the flag to false and then recompile OpenSTA to use the original BfsIterator.

Testcases

• Circuits from TAU2019 benchmark suites are added at /examples/tau2019
• Untar all the tarballs in /examples/tau2019
• Run <path_to_sta_executable> <design>.tcl -threads <n> to time <design>.

[yishanlu]

TODO: After the release of Galois 6.0,

1. File a pull request to add Galois as a git submodule to OpenROAD;
2. Change Galoised parts in this pull request if necessary;
3. Change CMakeLists.txt to conform with OpenROAD conventions;
4. Merge with OpenSTA master.

[maliberty]

Issues or PRs should be filed with https://github.com/parallaxsw/OpenSTA if still relevant. This is effectively a fork (though not strictly for historical reasons).