一种用于并行电路仿真的电路划分算法

A circuit partitioning algorithm for parallel circuit simulation

结合递归的多级二路划分方法和迭代改进方法,提出一种用于并行电路仿真的电路划分算法.该算法第一阶段用递归的多级二路划分方法获取较好的初始解,第二阶段用迭代改进方法不断改进负载平衡和通信量目标.实验结果表明,相对于k路划分工具hMETIS-Kway,该算法可以获取更好的划分质量.

In this paper, we present a partitioning algorithm for parallel circuit simulation based on the recursive multilevel bipartitioning method and the iterative improvement method. In the first phase, a recursive multilevel bipartitioning method is designed to obtain an excellent initial solution. Then, in the second phase, an iterative improvement algorithm is proposed to further optimize the load balance and network communication. Experimental results show that the proposed algorithm can yields results better than those of the k way partitioning tool hMETIS - Kway.