Replication-aided partitioning (RAP) has recently been introduced to facilitate the design of parallel logic simulation algorithms. By replicating overlapped work, RAP can significantly reduce the cost of inter-thread synchronization. However, the state-of-the-art RAP algorithm, RepCut, relies on time-consuming hypergraph construction and partitioning, where minimizing cut size corresponds to reducing replication. To overcome this runtime challenge, we introduce SimPart, a simple yet highly effective and efficient GPU-parallel replication-aided partitioner. SimPart tackles the partitioning problem directly without solving another proxy problem and proposes a hybrid strategy that can maximally utilize GPU threads for simulation atop our partitions. Compared to RepCut, SimPart achieves an average speedup of 23 \(\times \) in partitioning and 1.58 \(\times \) in GPU-parallel simulation, while increasing the original graph size by only 0.3%.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

SimPart: A Simple Yet Effective Replication-Aided Partitioning Algorithm for Logic Simulation on GPU

  • Yi-Hua Chung,
  • Shui Jiang,
  • Wan-Luan Lee,
  • Yanqing Zhang,
  • Haoxing Ren,
  • Tsung-Yi Ho,
  • Tsung-Wei Huang

摘要

Replication-aided partitioning (RAP) has recently been introduced to facilitate the design of parallel logic simulation algorithms. By replicating overlapped work, RAP can significantly reduce the cost of inter-thread synchronization. However, the state-of-the-art RAP algorithm, RepCut, relies on time-consuming hypergraph construction and partitioning, where minimizing cut size corresponds to reducing replication. To overcome this runtime challenge, we introduce SimPart, a simple yet highly effective and efficient GPU-parallel replication-aided partitioner. SimPart tackles the partitioning problem directly without solving another proxy problem and proposes a hybrid strategy that can maximally utilize GPU threads for simulation atop our partitions. Compared to RepCut, SimPart achieves an average speedup of 23 \(\times \) in partitioning and 1.58 \(\times \) in GPU-parallel simulation, while increasing the original graph size by only 0.3%.