A refined F-M partitioning algorithm for logic simulation. (1st January 2012) - Wang, Jiafang; Fu, Yuzhuo; Zhang, Jianpei
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.