Abstract
Graphics Processing Units (GPUs) have been widely used for computational intensive applications owing to its massive number of computing cores. However, only few algorithms can fully utilize the computational power of GPUs, because it requires not only enough degree of parallelism, but also the synergetic control between computation and data access in the finest granularity. In this thesis, we proposed the Multi-Sweep-Line (MSL) algorithm on GPU for the VLSI layout density calculation, which computes the union area of components in a layout. The shapes of most components are rectilinear rectangles. The MSL algorithm divides the input layout hierarchically into windows, slabs, and sweep line regions to explore the large degree of parallelism. In addition, to overcome the memory limitation of GPU, tasks are partitioned into batches based on memory usage, estimated by sampling algorithms. Optimization techniques, fast segmented sort, reducing atomic instruction, load balance, are also applied to further improve the performance. The experimental results show that our MLS implementation can achieve 75 to nearly 160 times speedup over the CPU version on GTX 1080 ti.