Accelerating irregular algorithms on gpgpus using fine-grain hardware worklists

Abstract—Although GPGPUs are traditionally used to accel-erate workloads with regular control and memory-access struc-ture, recent work has shown that GPGPUs can also achieve sig-nificant speedups on more irregular algorithms. Data-driven implementations of irregular algorithms are algorithmically more efficient than topology-driven implementations, but issues with memory contention and memory-access irregularity can make the former perform worse in certain cases. In this paper, we propose a novel fine-grain hardware worklist for GPGPUs that addresses the weaknesses of data-driven implementations. We detail multiple work redistribution schemes of varying com-plexity that can be employed to improve load balancing. Fur-thermore, a virtualization mechanism supports seamless work spilling to memory. A convenient shared worklist software API is provided to simplify using our proposed mechanisms when implementing irregular algorithms. We evaluate challenging ir-regular algorithms from the LonestarGPU benchmark suite on a cycle-level simulator. Our findings show that data-driven im-plementations running on a GPGPU using the hardware work-list outperform highly optimized software-based implementa-tions of these benchmarks running on a baseline GPGPU with speedups ranging from 1.2–2.4 ⇥ and marginal area overhead. I