SFP is a Rectilinear Steiner Minimum Tree (RSMT) heuristic. The CUDA implementation thereof is fast and produces relatively good solutions. It accepts inputs in the ISPD'08 format.
Click on SFP_10.cu to download the CUDA code, on SFP_10.cpp to download the OpenMP code, or on SFP_10large.cpp to download the serial code that only processes one large net. Note that SFP is protected by the license included in the beginning of the code.
The CUDA code can be compiled as follows:
nvcc -O3 -arch=sm_52 SFP_10.cu -o sfp
The OpenMP code can be compiled as follows:
g++ -O3 -fopenmp SFP_10.cpp -o sfp
To compute the RSMTs of the nets in the file
./sfp input.gr 0
The serial code can be compiled as follows:
g++ -O3 SFP_10large.cpp -o sfp
To compute the RSMT of a random 10000-pin net, enter:
A. Fallin, A. Kothari, J. He, C. Yanez, K. Pingali, R. Manohar, and M. Burtscher. "A Simple, Fast, and GPU-friendly Steiner-Tree Heuristic." Proceedings of the 23rd IEEE International Workshop on Parallel and Distributed Scientific and Engineering Computing. May 2022.
[pdf] [pptx] [video]
This work has been supported in part by the Defense Advanced Research Projects Agency under award number DARPA HR001117S0054 as well as by equipment donations from NVIDIA Corporation.