SA-PCB: Simulated Annealing-based Placement For PCB Layout

• See https://github.com/The-OpenROAD-Project/PCB-PR-App

• GCC compiler >= 4.8.5
• boost library >= 1.62
• cpp-taskflow >= 2.0
• Python >= 3.6
• shapely >= 1.6.4
• matplotlib >= 3.0.2
• docopt >= 0.6.2
• numpy >= 1.15.4
• argparse >= 1.1
• tqdm >= 4.30.0 [python-multistart]
• numba >= 0.42.1 [python-multistart]
• multiprocessing [python-multistart]
• yaml
• json
• Recommended OS: Centos6, Centos7 or Ubuntu 16.04

$ git clone --recursive https://github.com/choltz95/c-pcb-annealer
$ cd ~/c-pcbannealer
$ pip install -r requirements.txt
$ make install
$ make

You may have to fix some Swoop errors. Download DRU.py and place into the eagle2bookshelf
directory.

 $ wget https://raw.githubusercontent.com/NVSL/Swoop/master/Swoop/DRU.py
 $ mv DRU.py eagle2bookshelf

To make sure your installation is correct and the current tool version is stable enough,
run a Hello World application:

$ make test
$ open test.png

./sa parameters
   -i <optional, value> : for denoting # outer iterations PER SA INSTANCE
   -j <optional, value> : for denoting 'j'*#nodes inner iterations
   -t <optional, value> : for denoting initial temperature
   -f <optional, str>   : for output filename
   -e <optional, float> : convergence epsilon
   -v <optional>        : Ben-amur flag
   -x <optional, int>   : simulated annealing instance index
   -p <required, string>: input placement board
   -d <optional, {0-3}> : debug verbosity
   -r <optional, {0-3}> : rotation
   EXAMPLE: ./sa -i 20000 -j 20 -t 1 -p input -f output

• BSD-3-clause License [Link]

C++ annealer for simple PCB placement of polygonal components. Supports the following:

• Analytical overlap for arbitrary polygons using boost geometries
• Support 90 deg., 45 deg., free rotation [free rotation in progress]
• HPWL cost term for wirelength
• BEN-AMEUR et al. cost-normalization & automatic initial temperature
• Variable placement shift window, smaller displacement with temperature
• Geometric temperature updates (cooling schedule) based on Timberwolf schedule
• Bookshelf parser
• Bookshelf version translator
• Plotting & animations

• Parallel multistart [Issues with cpp-taskflow. Still support for multi-start via python script.]
• R-Tree spatial indexing for fast overlap computation
• Free rotation
• Algorithm very sensitive to parameters
• Broken support for weighted modules/nets
• Set up Dockerfile
• Support json configuration files for algorithm parameters

• Chester Holtz, Devon Merrill, James (Ting-Chou) Lin, Connie (Yen-Yi) Wu (Ph.D. advisor: Chung-Kuan Cheng, Steven Swanson).
• Pull requests to improve the tool are very appreciated.

• Sechen, C. and Sangiovanni-Vincentelli, A. L., "The Timber-Wolf placement and routing package", IEEE J. Solid-State Circuits 30:510–522 1985.
• Spindler, P. and Johannes, F., "Fast and Accurate Routing Demand Estimation for Efficient Routability-driven Placement ", IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2007.
• C.-K. Cheng, A. B. Kahng, I. Kang and L. Wang, "RePlAce: Advancing Solution Quality and Routability Validation in Global Placement", to appear in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2018. (Digital Object Identifier: 10.1109/TCAD.2018.2859220)
• Ben-Ameur, Walid. "Computing the initial temperature of simulated annealing." Computational Optimization and Applications 29, no. 3 (2004): 369-385.
• James M. Varanelli and James P. Cohoon. Two-stage simulated annealing methodology. In Proceedings of the 5th Great Lakes Symposium on VLSI, pages 50–53, Buffalo, NY, 16.-18. March 1995. IEEE, Los Alamitos, CA. †EI M153001/95
• K. D. Boese A. B. Kahng and S. Muddu A new adaptive multistart technique for combinatorial global optimizations, Operations Research Letters, 16(2): 101-113, September, 1993.