Ultrafast CPU/GPU Kernels for Density Accumulation in Placement

Abstract

Density accumulation is a widely-used primitive operation in physical design, especially for placement. Iterative invocation in the optimization flow makes it one of the runtime bottlenecks. Accelerating density accumulation is challenging due to data dependency and workload imbalance. In this paper, we propose efficient CPU/GPU kernels for density accumulation by decomposing the problem into two phases: constant-time density collection for each instance and a linear-time prefix sum. We develop CPU and GPU dedicated implementations, and demonstrate promising efficiency benefits on tasks from large-scale placement problems.

Publication
58th ACM/IEEE Design Automation Conference (DAC) 2021
Jing Mai
Jing Mai
Third-year CS Ph.D. Student

PKU CS Ph.D. student 2021 🎩🎩🎩 Peking University BS. Computer Science and Technology. Try to do something fun. Focus on machine learning applications, MLsys, and emerging technology in VLSI CAD.