DREAMPlace-hvp — Exact Hessian-Vector Products for Second-Order Placement Optimization

This is a fork of DREAMPlace with exact Hessian-Vector Product (HVP) support for all DREAMPlace objective terms. The original DREAMPlace is developed by Yibo Lin's group at Peking University.

What this fork adds

Standard analytical placers (including DREAMPlace) rely on first-order optimizers (Nesterov's method) with a diagonal preconditioner $P$ that crudely approximates the inverse Hessian $H^{-1}$, or quasi-Newton methods (L-BFGS) that build low-rank approximations from gradient history — neither captures the true curvature of the objective. A diagonal preconditioner treats each cell independently, ignoring inter-cell correlations through shared nets, density coupling, and timing paths. When timing-driven objectives are introduced, the landscape becomes non-convex with saddle points where these methods stall.

This fork implements exact Hessian-Vector Products for all three DREAMPlace objective terms, enabling second-order optimization methods such as Saddle-Free Newton that can escape saddle points and produce coordinated updates across correlated cells.

Hessian analysis and second-order strategy

Term	Hessian structure	PSD?	Sparsity	Cost	Method
Electric density	$J_\rho^\top G J_\rho$	✓ PSD	Dense	$O(MN_b \log MN_b + N)$	HVP via Poisson pipeline + new CUDA kernels (detail below)
LogSumExp WL	Softmax Jacobian	✓ PSD	Sparse	$O(P)$	HVP, hand-derived closed-form, PyTorch
Weighted-Average WL	Symmetric rank-2 update	✗ Indefinite	Sparse	$O(P)$	HVP, hand-derived closed-form, PyTorch
Timing (planned)	Delay model $R \times C$ cross-terms over DAG	✗ Indefinite	Sparse	$O(P)$	Sparse Hessian assembly + Saddle-Free Newton

The WA WL Hessian is technically indefinite — negative eigenvalues can be constructed (e.g., $v^\top H v \approx -0.046$ for a 3-pin net) — but the negative curvature is extremely weak in practice and the objective behaves as effectively convex. The primary motivation for second-order methods remains timing-driven placement, where the Elmore delay model's $R \times C$ cross-terms introduce substantially stronger non-convexity.

The density Hessian $J_\rho^\top G J_\rho$ is not a Gauss-Newton approximation — it is exact almost everywhere, as the piecewise-linear basis functions have zero second derivatives.

The wirelength HVPs are hand-derived closed-form expressions implemented in PyTorch (no custom CUDA kernels). The density HVP requires the custom Poisson pipeline described below.

All HVPs are verified against finite differences (see Verification and docs/derivation.md for details).

Density HVP: the Poisson pipeline

The density gradient in DREAMPlace follows a three-stage pipeline:

$$\nabla E = J_\rho^\top G \rho$$

where $J_\rho$ is the density Jacobian (scatter), $G$ is the Poisson Green's function (DCT-based spectral solve), and $\rho$ is the density map. The HVP is its linearization:

$$H \cdot v = J_\rho^\top G J_\rho v$$

This decomposes into three steps with identical computational structure to the gradient:

Step	Gradient pipeline	HVP pipeline	Kernel
1 — Scatter	$\rho$ = scatter(pos) with $p_x \cdot p_y$	$\delta\rho = J_\rho \cdot v$ with $\frac{\partial p_x}{\partial x} \cdot p_y$	New: computeSignedDensityMapKernel
2 — Poisson	$G\rho$ via DCT	$G\delta\rho$ via DCT	Reused (unmodified)
3 — Gather	$J_\text{interp}^\top \cdot G\rho$ with $p_x \cdot p_y$	$J_\rho^\top \cdot G\delta\rho$ with $\frac{\partial p_x}{\partial x} \cdot p_y$	New: computeSignedElectricForceKernel

The Poisson solver (Step 2) is reused without modification because $G$ is a linear, self-adjoint operator under Neumann boundary conditions — the same DCT solve applies to both $\rho$ and $\delta\rho$.

Why signed kernels are needed. The original DREAMPlace computes the gather step (Step 3) using interpolation weights $p_x \cdot p_y$ rather than the exact density Jacobian transpose $J_\rho^\top$. These are related by summation-by-parts and produce equivalent gradients for first-order optimization. However, using $J_\text{interp}^\top$ in the HVP yields a non-symmetric product $J_\text{interp}^\top G J_\rho$, which is incorrect for Newton-type methods that require a symmetric Hessian. The new signed kernels implement the exact $J_\rho^\top$ to ensure full symmetry: $H = J_\rho^\top G J_\rho = H^\top$.

Computational cost. A single density HVP evaluation costs $O(MN_b \log MN_b + N)$ — the same as a single gradient evaluation — with $O(MN_b)$ additional memory for the $\delta\rho$ map.

Finite difference verification

All HVPs (density, LSE WL, WA WL) are verified against finite differences.

For the wirelength terms, standard pos-perturbation FD works directly, as the objective is smooth everywhere (rel. error: 1.5 × 10⁻³ for LSE, 2.3 × 10⁻⁵ for WA, both float32).

For the density term, direct FD is complicated by the piecewise-linear basis functions: when $\text{pos} + \varepsilon v$ crosses a bin boundary, $J_\rho^\top$ jumps discontinuously, producing an $O(1)$ residual unrelated to the HVP accuracy. We use field-only finite differences — fixing $J_\rho^\top$ at the original position and perturbing only the density field:

$$\text{FD}_\text{field} = J_\rho^\top(\text{pos}) \cdot \frac{G\rho(\text{pos}+\varepsilon v) - G\rho(\text{pos})}{\varepsilon} \approx J_\rho^\top G J_\rho v$$

Verification	Method	Relative error
Density Step 1 Jacobian	pos-perturbation FD	8.1 × 10⁻⁴
Density full HVP (field-only FD)	$J_\rho^\top$ fixed, field perturbed	3.6 × 10⁻⁴
Density full pipeline (pos FD, includes Term1')	pos and field both perturbed	10.8% (expected)
LSE WL HVP	pos-perturbation FD (float32)	1.5 × 10⁻³
WA WL HVP	pos-perturbation FD (float32)	2.3 × 10⁻⁵

Future direction

This HVP implementation is a building block toward Saddle-Free Newton optimization for timing-driven placement. Since the density and wirelength objectives are effectively convex, the dominant non-convexity originates from timing — specifically, from the delay model: the $R \times C$ cross-terms in multi-sink RC trees create bilinear coupling between cell positions, producing an indefinite Hessian. The timing Hessian is sparse — its non-zero pattern mirrors the netlist adjacency — which opens the door to scalable second-order methods that flip negative eigenvalues via $|\mathbf{H}|^{-1} \mathbf{g}$.

---

Below is the original DREAMPlace README.

---

DREAMPlace

Deep learning toolkit-enabled VLSI placement. With the analogy between nonlinear VLSI placement and deep learning training problem, this tool is developed with deep learning toolkit for flexibility and efficiency. The tool runs on both CPU and GPU. Over 30X speedup over the CPU implementation (RePlAce) is achieved in global placement and legalization on ISPD 2005 contest benchmarks with a Nvidia Tesla V100 GPU. DREAMPlace also integrates a GPU-accelerated detailed placer, ABCDPlace, which can achieve around 16X speedup on million-size benchmarks over the widely-adopted sequential placer NTUPlace3 on CPU.

• DREAMPlace
• Publications
• Dependency
• How to Install Python Dependency
• How to Build
  • Build with Docker
  • Build without Docker
• How to Get Benchmarks
• How to Run
• Configurations
• Authors
• Features

DREAMPlace runs on both CPU and GPU. If it is installed on a machine without GPU, only CPU support will be enabled with multi-threading.

• Animation

Bigblue4	Density Map	Electric Potential	Electric Field

• Reference Flow

Publications

• Yibo Lin, Shounak Dhar, Wuxi Li, Haoxing Ren, Brucek Khailany and David Z. Pan, "DREAMPlace: Deep Learning Toolkit-Enabled GPU Acceleration for Modern VLSI Placement", ACM/IEEE Design Automation Conference (DAC), Las Vegas, NV, Jun 2-6, 2019 (preprint) (slides)

• Yibo Lin, Zixuan Jiang, Jiaqi Gu, Wuxi Li, Shounak Dhar, Haoxing Ren, Brucek Khailany and David Z. Pan, "DREAMPlace: Deep Learning Toolkit-Enabled GPU Acceleration for Modern VLSI Placement", IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD), 2020

• Yibo Lin, Wuxi Li, Jiaqi Gu, Haoxing Ren, Brucek Khailany and David Z. Pan, "ABCDPlace: Accelerated Batch-based Concurrent Detailed Placement on Multi-threaded CPUs and GPUs", IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD), 2020 (preprint)

• Yibo Lin, David Z. Pan, Haoxing Ren and Brucek Khailany, "DREAMPlace 2.0: Open-Source GPU-Accelerated Global and Detailed Placement for Large-Scale VLSI Designs", China Semiconductor Technology International Conference (CSTIC), Shanghai, China, Jun, 2020 (preprint)(Invited Paper)

• Jiaqi Gu, Zixuan Jiang, Yibo Lin and David Z. Pan, "DREAMPlace 3.0: Multi-Electrostatics Based Robust VLSI Placement with Region Constraints", IEEE/ACM International Conference on Computer-Aided Design (ICCAD), Nov 2-5, 2020 (preprint)

• Peiyu Liao, Siting Liu, Zhitang Chen, Wenlong Lv, Yibo Lin and Bei Yu, "DREAMPlace 4.0: Timing-driven Global Placement with Momentum-based Net Weighting", IEEE/ACM Proceedings Design, Automation and Test in Eurpoe (DATE), Antwerp, Belgium, Mar 14-23, 2022 (preprint)

• Peiyu Liao, Dawei Guo, Zizheng Guo, Siting Liu, Zhitang Chen, Wenlong Lv, Yibo Lin and Bei Yu, "DREAMPlace 4.0: Timing-driven Placement with Momentum-based Net Weighting and Lagrangian-based Refinement", IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD), Oct, 2023.

• Yifan Chen, Zaiwen Wen, Yun Liang, Yibo Lin, "Stronger Mixed-Size Placement Backbone Considering Second-Order Information", IEEE/ACM International Conference on Computer-Aided Design (ICCAD), San Francisco, CA, Oct, 2023 (preprint)(Corresponding to DREAMPlace 4.1)

• Zizheng Guo, Haichuan Liu, Xizhe Shi, Shenglu Hua, Zuodong Zhang, Chunyuan Zhao, Runsheng Wang and Yibo Lin, "HeteroSTA: A CPU-GPU Heterogeneous Static Timing Analysis Engine with Holistic Industrial Design Support", IEEE/ACM Asia and South Pacific Design Automation Conference (ASPDAC), Hong Kong, Jan, 2026. (preprint)(Invited Paper)(Corresponding to DREAMPlace 4.3)

Dependency

• Python 3.5/3.6/3.7/3.8/3.9

• Pytorch 1.6/1.7/1.8/2.0

  • Other versions may also work, but not tested

• GCC

  • Recommend GCC 7.5 (with c++17 support).
  • Do not recommend GCC 9 or later due to backward compatibility issues.
  • Other compilers may also work, but not tested.

• Boost >= 1.55.0

  • Need to install and visible for linking

• Bison >= 3.3

  • Need to install

• Limbo

  • Integrated as a git submodule

• Flute

  • Integrated as a submodule

• OpenTimer

  • Modified version for timing optimization
  • Integrated as a submodule

• CUB

  • Integrated as a git submodule

• munkres-cpp

  • Integrated as a git submodule

• HeteroSTA

  • Used as a GPU-accelerated timing analysis engine

• CUDA 9.1 or later (Optional)

  • If installed and found, GPU acceleration will be enabled.
  • Otherwise, only CPU implementation is enabled.

• GPU architecture compatibility 6.0 or later (Optional)

  • Code has been tested on GPUs with compute compatibility 6.0, 7.0, and 7.5.
  • Please check the compatibility of the GPU devices.
  • The default compilation target is compatibility 6.0. This is the minimum requirement and lower compatibility is not supported for the GPU feature.
  • For compatibility 7.0, it is necessary to set the CMAKE_CUDA_FLAGS to -gencode=arch=compute_70,code=sm_70.

• Cairo (Optional)

  • If installed and found, the plotting functions will be faster by using C/C++ implementation.
  • Otherwise, python implementation is used.

• NTUPlace3 (Optional)

  • If the binary is provided, it can be used to perform detailed placement.

To pull git submodules in the root directory

git submodule init
git submodule update

Or alternatively, pull all the submodules when cloning the repository.

git clone --recursive https://github.com/limbo018/DREAMPlace.git

How to Install Python Dependency

Go to the root directory.

pip install -r requirements.txt

How to Build

Two options are provided for building: with and without Docker.

Build with Docker

You can use the Docker container to avoid building all the dependencies yourself.

1. Install Docker on Windows, Mac or Linux.
2. To enable the GPU features, install NVIDIA-docker; otherwise, skip this step.
3. Navigate to the repository.
4. Get the docker container with either of the following options.
   • Option 1: pull from the cloud limbo018/dreamplace.

   docker pull limbo018/dreamplace:cuda
   

   • Option 2: build the container.

   docker build . --file Dockerfile --tag your_name/dreamplace:cuda
   

5. Enter bash environment of the container. Replace limbo018 with your name if option 2 is chosen in the previous step.

Run with GPU on Linux.

docker run --gpus 1 -it -v $(pwd):/DREAMPlace limbo018/dreamplace:cuda bash

Run with GPU on Windows.

docker run --gpus 1 -it -v /dreamplace limbo018/dreamplace:cuda bash

Run without GPU on Linux.

docker run -it -v $(pwd):/DREAMPlace limbo018/dreamplace:cuda bash

Run without GPU on Windows.

docker run -it -v /dreamplace limbo018/dreamplace:cuda bash

6. cd /DREAMPlace.
7. Go to next section to complete building within the container.

Build without Docker

CMake is adopted as the makefile system. To build, go to the root directory.

mkdir build
cd build # we call this <build directory>
cmake .. -DCMAKE_INSTALL_PREFIX=<installation directory> -DPython_EXECUTABLE=$(which python)
make
make install

Where <build directory> is the directory where you compile the code, and <installation directory> is the directory where you want to install DREAMPlace (e.g., ../install). Third party submodules are automatically built except for Boost.

To clean, go to the root directory.

rm -r build

<build directory> can be removed after installation if you do not need incremental compilation later.

Here are the available options for CMake.

• CMAKE_INSTALL_PREFIX: installation directory
  • Example cmake -DCMAKE_INSTALL_PREFIX=path/to/your/directory
• CMAKE_CUDA_FLAGS: custom string for NVCC (default -gencode=arch=compute_60,code=sm_60)
  • Example cmake -DCMAKE_CUDA_FLAGS=-gencode=arch=compute_60,code=sm_60
• CMAKE_CXX_ABI: 0|1 for the value of _GLIBCXX_USE_CXX11_ABI for C++ compiler, default is 0.
  • Example cmake -DCMAKE_CXX_ABI=0
  • It must be consistent with the _GLIBCXX_USE_CXX11_ABI for compling all the C++ dependencies, such as Boost and PyTorch.
  • PyTorch in default is compiled with _GLIBCXX_USE_CXX11_ABI=0, but in a customized PyTorch environment, it might be compiled with _GLIBCXX_USE_CXX11_ABI=1.

How to Get Benchmarks

To get ISPD 2005 and 2015 benchmarks, run the following script from the directory.

python benchmarks/ispd2005_2015.py

How to Run

Before running, make sure the benchmarks have been downloaded and the python dependency packages have been installed. Go to the install directory and run with JSON configuration file for full placement.

cd <installation directory>
python dreamplace/Placer.py test/ispd2005/adaptec1.json

Test individual pytorch op with the unit tests in the root directory.

cd <installation directory>
python unittest/ops/hpwl_unittest.py

Configurations

Descriptions of options in JSON configuration file can be found by running the following command.

cd <installation directory>
python dreamplace/Placer.py --help

The list of options as follows will be shown.

JSON Parameter	Default	Description
aux_input	required for Bookshelf	input .aux file
lef_input	required for LEF/DEF	input LEF file
def_input	required for LEF/DEF	input DEF file
verilog_input	optional for LEF/DEF	input VERILOG file, provide circuit netlist information if it is not included in DEF file
lib_input	optional for HeteroSTA	Liberty input for both corners; supports "path.lib" or ["a.lib", "b.lib"]
early_lib_input	optional for HeteroSTA	Early-corner Liberty input; supports string or string list
late_lib_input	optional for HeteroSTA	Late-corner Liberty input; supports string or string list
sdc_input	optional for timing	input SDC file
gpu	1	enable gpu or not

...

Authors

• Yibo Lin, supervised by David Z. Pan, composed the initial release.
• Zixuan Jiang and Jiaqi Gu improved the efficiency of the wirelength and density operators on GPU.
• Yibo Lin and Jiaqi Gu developed and integrated ABCDPlace for detailed placement.
• Peiyu Liao and Siting Liu developed and integrated timing optimization in global placement for DREAMPlace 4.0.
• Yifan Chen developed the 2-stage flow and improved the optimizer for macro placement in DREAMPlace 4.1. Set use_bb to 1 to turn on BB-step and macro_place_flag to 1 to enable 2-stage flow for macro placement.
• Yiting Liu contributed the GiFt operator for placement initialization, published at ICCAD 2024. Set gift_init_flag to 1 to turn on this feature, and use gift_init_scale to control the scale parameter of this operator.

Yiting Liu, Hai Zhou, Jia Wang, Fan Yang, Xuan Zeng, Li Shang, 
"The Power of Graph Signal Processing for Chip Placement Acceleration", 
  IEEE/ACM International Conference on Computer-Aided Design (ICCAD), New Jersey, USA, Oct, 2024
(Thanks for contributing the source code!)

• Shenglu Hua integated HeteroSTA into DREAMPlace 4.3. Set timer_engine to "heterosta" to turn on this feature.

• Pull requests to improve the tool are more than welcome. We appreciate all kinds of contributions from the community.

Features

• 0.0.2

  • Multi-threaded CPU and optional GPU acceleration support

• 0.0.5

  • Net weighting support through .wts files in Bookshelf format
  • Incremental placement support

• 0.0.6

  • LEF/DEF support as input/output
  • Python binding and access to C++ placement database

• 1.0.0

  • Improved efficiency for wirelength and density operators from TCAD extension

• 1.1.0

  • Docker container for building environment

• 2.0.0

  • Integrate ABCDPlace: multi-threaded CPU and GPU acceleration for detailed placement
  • Support independent set matching, local reordering, and global swap with run-to-run determinism on one machine
  • Support movable macros with Tetris-like macro legalization and min-cost flow refinement

• 2.1.0

  • Support deterministic mode to ensure run-to-run determinism with minor runtime overhead

• 2.2.0

  • Integrate routability optimization relying on NCTUgr from TCAD extension
  • Improved robustness on parallel CPU version

• 3.0.0

  • Support fence regions as published at ICCAD 2020
  • Add quadratic penalty to accelerate gradient descent at plateau during global placement
  • Inject noise to escape from saddle points during global placement

• 4.0.0

  • Support timing optimization in global placement as published at DATE 2022
  • Add momentum-based net weighting strategy
  • Integrate OpenTimer for static timing analysis
  • Tested under ICCAD 2015 contest benchmarks (see test/iccad2015.ot)

• 4.1.0

  • Support BB step and 2-stage macro placement flow as published at ICCAD 2023 (Need to set use_bb to 1 to turn on BB-step and macro_place_flag to 1 to enable 2-stage flow for macro placement)
  • Tested under ISPD 2005 with all fixed macros and IO pads regarded as movable macros (see test/ispd2005free) and MMS benchmarks (see test/mms)

• 4.2.0

  • Support GiFt initialization as published at ICCAD 2024

• 4.3.0

  • Support GPU-accelerated timing analysis using HeteroSTA.

Reference Results for Macro Placement

Recently, many studies chose DREAMPLace for macro placement, e.g., [Cheng+, NeurIPS2021], [Lai+, NeurIPS2023], etc. However, the results reported on the same benchmarks vary significantly from one work to another. For better comparison, we provide the results collected from our GPU machine for reference. If your results deviate significantly (i.e., >5% longer HPWL) from the following numbers, something may be wrong. We recommend you to contact us with logs for validation.

Note that DREAMPlace 4.1.0 only implements the BB step and 2-stage flow proposed in [Chen+, ICCAD2023].

ISPD2005 benchmark with all fixed macros and IO pads regarded as movable macros. It can be downloaded from here.

	DREAMPlace 4.0			DREAMPlace 4.1.0
	Iterations	HPWL(x10^6)	Time(s)	Iterations	HPWL(x10^6)	Time(s)
adaptec1	600	101.3	26.3	748	68.2	27.6
adaptec2	588*	137.5*	40.6*	784	86.3	40.1
adaptec3	765	179.5	54.1	894	144.0	56.1
adaptec4	876	153.3	48.9	872	140.8	57.3
bigblue1	699	86.2	23.5	813	82.0	25.5
bigblue2	1267*	2426.7*	679.4*	869	98.1	193.4
bigblue3	1207	330.2	115.4	1307	288.8	140.1
bigblue4	1581	820.1	239.6	1875	610.0	234.5
average ratio	0.937	4.211	1.258	1.000	1.000	1.000

MMS benchmark (modified from ISPD2005 benchmarks with movable macros and fixed IO pads)

Our modified version can be downloaded from here.

	DREAMPlace 4.0			DREAMPlace 4.1.0
	Iterations	HPWL(x10^6)	Time(s)	Iterations	HPWL(x10^6)	Time(s)
adaptec1	607	65.3	17.8	746	64.7	25.8
adaptec2	569	79.3	28.5	734	75.8	35.8
adaptec3	659	158.1	44.6	755	153.3	38.9
adaptec4	735	141.7	46.8	782	142.4	47.5
adaptec5	1053	326.3	63.8	1405	337.6	78.4
bigblue1	646	85.4	21.3	809	85.3	28.9
bigblue2	638	125.3	42.0	773	125.4	48.4
bigblue3	911	279.3	112.5	1097	273.8	136.1
bigblue4	1189	648.8	172.4	1515	643.2	215.4
newblue1	574	62.8	22.5	749	62.0	30.4
newblue2	730	155.5	34.8	861	156.1	43.9
newblue3	1318*	597.3*	55.71*	830	270.6	72.8
newblue4	1009	246.2	52.6	1274	245.8	53.9
newblue5	1254	444.2	99.4	1537	446.4	134.9
newblue6	929	410.6	96.1	1157	409.3	115.1
newblue7	1077	903.6	184.1	1578	903.2	235.1
average ratio	0.855	1.081	0.830	1.000	1.000	1.000

`*` denotes divergence or legalization failure. Note that if you observe divergence or legalization errors in the log, then the results may not be representative.