Accelerating datapath merging by task parallelisation on multicore systems

ABSTRACT

Datapath merging is an efficient approach to reduce hardware resources and configuration time in the synthesis of digital systems. In order to solve datapath merging, we have to find the maximum weighted clique, which is an NP-hard problem. So, datapath merging is a time-consuming process. In this article, we use OpenMP library to perform divide and conquer task parallelism to find the maximum weighted clique. Therefore, considerable reduction in the synthesis time and almost linear speedup has been achieved. The experimental results obtained from running this algorithm on different benchmarks represent speedup ranging from 1.2 times to 6.5 times for an 8-core system.

KEYWORDS:

• Datapath merging
• Branch and Bound algorithm
• task parallelisation
• shared memory paradigm

Acknowledgments

The authors would like to thank Institute for Research in Fundamental Sciences (IPM) which supported this research at the context of research project number CS1395-4-670.

Disclosure statement

No potential conflict of interest was reported by the authors.

ORCID

Mahmood Fazlali http://orcid.org/0000-0002-1701-5562

Additional information

Funding

This work was supported by School of Computer Science, Institute for Research in Fundamental Sciences (IPM) [ CS1395-4-670].