Accelerating Support Count for Association Rule Mining on GPUs

In this work, we present a highly parallel work-efficientalgorithm for performing support count on a GPU. Wedevelop a compressed data layout scheme that enables high off-chipmemory bandwidth utilization. Our data layout results inlow overhead parallel coordination while reducing the memoryrequirements of support count. We evaluate our algorithm through extensive experimentationboth on synthetically generated and real data. We achievemaximum throughput of 50 billion evaluations per secondfor our parallel two phase algorithm, while outperformingthat of non work-efficient implementations on a multi-coreCPU and a GPU by almost 40×. Resolving bank conflictsresults in reduction of the execution time per iteration of ouralgorithm up to 6%. Employing additional optimizations such asloop unrolling leads to improvement in execution time up to 18%.