A refined F-M partitioning algorithm for logic simulation

作者：Wang, Jiafang^*; Fu, Yuzhuo; Zhang, Jianpei

来源：International Journal of Simulation and Process Modelling, 2012, 7(1-2): 67-73.

DOI：10.1504/IJSPM.2012.047866

• Communication overheads
• F-M heuristic algorithms
• Graph partitioning problems
• Mixed-signal circuits
• Multi-level partitioning
• Network of workstations
• Parallel logic simulations
• Partitioning algorithms

Circuit partitioning is an efficient way to speed up the parallel simulation and reduce the communication overhead. How to exploit the parallelism inherent in complex and diverse systems is a research hotspot in simulation area. This paper aims to speed-up the simulation of digital and analogue mixed-signal circuits based on parallel and distributed event simulation (PDES) protocols, using the platforms of a network of workstations (NoWs). Most of partitioning algorithms are heuristic in nature because the graph partitioning problem is NP complete. Based on classical F-M heuristic algorithm, we proposed a multilevel partitioning approach TCFM, which can get fast convergence of F-M algorithm by refining the initial partitioning. The simulator was implemented on network of workstations, a performance matrix was proposed, and a benchmark of ISCAS85 was executed to show that it is feasible to obtain the speedup and lower communication overhead.

• 出版日期2012
• 单位上海交通大学; 哈尔滨工程大学