Today’s Integrated Circuit (IC) architects depend on Electronic Design Automation (EDA) software to conquer the overwhelming complexity of Very Large Scale Integrated (VLSI) designs. As the complexity of IC chips is still fast increasing, it is critical to maintain the momentum towards growing productivity of EDA tools. On the other hand, single-core Central Processing Unit (CPU) performance is unlikely to see significant improvement in the near future. It is thus essential to develop highly efficient parallel algorithms and implementations for EDA applications, so that their overall productivity can continue to increase in a scalable fashion. Among various emergent parallel platforms, Graphics Processing Units (GPUs) now offer the highest single-chip computing throughput. A large body of research, therefore, has been dedicated to accelerating EDA applications with GPUs. This monograph is aimed to develop a timely review of the existing literature on GPU-based EDA computing. Considering the substantial diversity of VLSI CAD algorithms, we extend a taxonomy of EDA computing patterns, which can be used as basic building blocks to construct complex EDA applications. GPU-based acceleration techniques for these patterns are then reviewed. On such a basis, we further survey recent works on building efficient data-parallel algorithms and implementations to unleash the power of GPUs for EDA applications.
Categories and Subject Descriptors: J.6 [Computer-Aided Engineering]— Computer-aided design (CAD).
General Terms: Algorithms, Design, Performance
Additional Keywords and Phrases: Electronic Design Automation(EDA), VLSI, GPU, Graphics Processor, GPGPU, logic simulation,circuit simulation, matrix, linear algebra, sparse matrix, graphtraversal, graph algorithm, dynamic programming, simulated annealing,structured grid
