An Improved F-M Partitioning Algorithm in Parallel Logic Simulation

Author

Wang, Jiafang ; Fu, Yuzhuo

Author_Institution

Sch. of Comput. Sci. & Technol., Heilongjiang Univ., Harbin, China

fYear

2011

fDate

8-9 Oct. 2011

Firstpage

40

Lastpage

42

Abstract

The increasing complexity of digital VLSI designs is causing the simulation execution time to increase enormously. Circuit partitioning is an efficient way to speed up the parallel simulation and reduce the communication overhead. 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 and a benchmark of ISCAS85 was executed to show that it is feasible to obtain the speedup and lower communication overhead.

Keywords

VLSI; logic partitioning; logic simulation; parallel processing; F-M partitioning algorithm; ISCAS85 benchmark; TCFM; circuit partitioning; communication overhead reduction; digital VLSI designs; multilevel partitioning approach; parallel logic simulation; simulation execution time; workstation network; Algorithm design and analysis; Clustering algorithms; Computational modeling; Educational institutions; Heuristic algorithms; Integrated circuit modeling; Partitioning algorithms; Discovery; F-M heuristic algorithm; Multilevel Partitioning; Synchronization; parallel logic simulation;

fLanguage

English

Publisher

ieee

Conference_Titel

Knowledge Acquisition and Modeling (KAM), 2011 Fourth International Symposium on

Conference_Location

Sanya

Print_ISBN

978-1-4577-1788-8

Type

conf

DOI

10.1109/KAM.2011.18

Filename

6137572