Accelerate Analytical Placement with GPU: A Generic Approach

Chun‐Xun Lina and Martin D. F. Wongb
University of Illinois at Urbana‐Champaign, IL, USA
aclin99@illinois.edu
bmdfwong@illinois.edu

ABSTRACT


This paper presents a generic approach of exploiting GPU parallelism to speed up the essential computations in VLSI nonlinear analytical placement. We consider the computation of wire length and density which are widely used as cost and constraint in nonlinear analytical placement. For wire length gradient computing, we utilize the sparse characteristic of circuit graph to transform the compute‐intensive portions into sparse matrix multiplications, which effectively optimizes the memory access pattern and mitigates the imbalance workload. For density, we introduce a computation flattening technique to achieve load balancing among threads and a High‐Precision representation is integrated into our approach to guarantee the reproducibility. We have evaluated our method on a set of contest benchmarks from industry. The experimental results demonstrate our GPU method achieves a better performance over both the CPU methods and the straight forward GPU implementation.



Full Text (PDF)