Title: A refined F-M partitioning algorithm for logic simulation

Authors: Jiafang Wang; Yuzhuo Fu; Jianpei Zhang

Addresses: School of Computer Science and Technology, Harbin Engineering University, Mailbox 231, No. 74 Xuefu Road, Nangang District, Harbin, Heilongjiang, China; School of Computer Science and Technology, Heilongjiang University, Mailbox 231, No. 74 Xuefu Road, Nangang District, Harbin, Heilongjiang, China. ' School of Microelectronics, Shanghai Jiaotong University, Wei Dian Zi Building 4F, No. 800, Dongchuan Road, Shanghai, China. ' School of Computer Science and Technology, Harbin Engineering University, Room 528, No. 21 Building, No. 145, Nantong Street, Harbin, China

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.

Keywords: F-M heuristic algorithm; parallel simulation; multilevel partitioning; circuit partitioning; logic simulation; mixed-signal circuits; distributed event simulation; workstation networks.

DOI: 10.1504/IJSPM.2012.047866

International Journal of Simulation and Process Modelling, 2012 Vol.7 No.1/2, pp.67 - 73

Published online: 15 Nov 2014 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article