A refined F-M partitioning algorithm for logic simulation. (1st January 2012)

• Record Type: Journal Article
• Authors: Wang, Jiafang; Fu, Yuzhuo; Zhang, Jianpei
• Is Part Of: International journal of simulation and process modelling. Volume 7:Number 1/2(2012)
• Page Start: 67
• Page End: 73
• Publication Date: 2012-01-01
• Subjects: F-M heuristic algorithm -- parallel logic simulation -- multilevel partitioning; Management -- Computer simulation -- Periodicals; Mathematical models -- Periodicals; Operations research -- Periodicals; Simulation methods -- Periodicals; 003.05
• Languages: English
• ISSNs: 1740-2123

Abstract

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.