Fast STA Graph Partitioning Framework for Multi-GPU Acceleration

Path-based Analysis (PBA) is a key process in Static Timing Analysis (STA) to reduce excessive slack pessimism. How-ever, PBA can easily become the major performance bottleneck due to its long execution time. To overcome this bottleneck, recent STA researches have proposed to accelerate PBA algorithms with manycore CPU and GPU parallelisms. However, GPU memory is rather limited when we compute PBA on large industrial designs with millions of gates. In this work, we introduce a new endpoint-oriented partitioning framework that can separate STA graphs and dispatch the PBA workload onto multiple GPUs. Our framework can quickly identify logic overlaps among endpoints and group endpoints based on the size of shared logic. We then recover graph partitions from the grouped endpoints and offload independent PBA workloads to multiple GPUs. Experiments show that our framework can largely accelerate the PBA process on designs with over 10M gates.