Reducing thread divergence in GPU-based bees swarmrnoptimization applied to association rule mining

摘要

The association rules mining (ARM) problem is one of the most important problems in the area of data mining.rnIt aims at finding all relevant association rules from transactional databases. It is CPU time intensivernand requires a huge computing power when dealing with large transactional databases. To deal with thisrnissue, Graphics Processing Units (GPUs) are a powerful tool to speed up the search process. However, theirrnperformance is closely subject to thread/branch divergence resulting from the single instruction multiplerndata parallel model of GPUs. In this paper, we propose three approaches based on database reorganization,rnaiming to reduce thread divergence in GPU-based bees swarm optimization metaheuristic for ARM, respectively,rnnamed block-based reordering, transactions-based reordering, and transactions-based reordering withrnmedian value. Theoretical and experimental studies have been carried out using well-known large ARMrninstances. The experiments have been performed on an Intel Xeon 64 bit quad-core processor E5520 coupledrnto Nvidia Tesla C2075 448 cores. The results show that the proposed approaches minimize considerably thernnumber of thread divergence and improve the overall execution time. Indeed, the number of thread divergencernoccurrences has been reduced by up to eight times making the execution much faster. Copyright ©rn2016 John Wiley & Sons, Ltd.