TY - JOUR
T1 - Accelerating datapath merging by task parallelisation on multicore systems
AU - Fazlali, Mahmood
AU - Fallah, Mohammad K.
AU - Hosseinpour, Naemeh
AU - Katanforoush, Ali
N1 - Funding Information:
This work was supported by School of Computer Science, Institute for Research in Fundamental Sciences (IPM) [ CS1395-4-670].
Funding Information:
This work was supported by School of Computer Science, Institute for Research in Fundamental Sciences (IPM) [CS1395-4-670]. 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.
Funding Information:
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.
Publisher Copyright:
© 2019, © 2019 Informa UK Limited, trading as Taylor & Francis Group.
PY - 2019/1/3
Y1 - 2019/1/3
N2 - 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.
AB - 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.
KW - Branch and Bound algorithm
KW - Datapath merging
KW - shared memory paradigm
KW - task parallelisation
UR - http://www.scopus.com/inward/record.url?scp=85059591461&partnerID=8YFLogxK
U2 - 10.1080/17445760.2018.1552957
DO - 10.1080/17445760.2018.1552957
M3 - Article
AN - SCOPUS:85059591461
SN - 1744-5760
VL - 34
SP - 615
EP - 628
JO - International Journal of Parallel, Emergent and Distributed Systems
JF - International Journal of Parallel, Emergent and Distributed Systems
IS - 5
ER -