Fast STA Graph Partitioning Framework for Multi-GPU Acceleration
Fast STA Graph Partitioning Framework for Multi-GPU Acceleration
复制标题
DOI：
10.23919/date56975.2023.10137050
复制
发表时间：
2023-04
期刊：
影响因子：
--
通讯作者：
Guannan Guo;Tsung-Wei Huang;Martin D. F. Wong
中科院分区：
文献类型：
--
作者：
Guannan Guo;Tsung-Wei Huang;Martin D. F. Wong
基于路径的分析（PBA）是静态时间分析（STA）的关键过程，以减少过度的松弛悲观主义。但是，由于执行时间长，PBA可以轻松成为主要的性能瓶颈。为了克服这一瓶颈，最近的STA研究提出了通过多核CPU和GPU并行性加速PBA算法。但是，当我们在具有数百万门的大型工业设计上计算PBA时，GPU的内存非常有限。在这项工作中，我们介绍了一个新的面向端点的分区框架，该框架可以将STA图分开并将PBA工作负载分开到多个GPU上。我们的框架可以根据共享逻辑的大小快速识别端点和组端点之间的逻辑重叠。然后，我们从分组的端点恢复图形分区，并将独立的PBA工作负载卸载到多个GPU。实验表明，我们的框架可以在很大程度上加速了超过1000万门的设计上的PBA过程。
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.