Performance Characterization of Parallel Combination Generators on CPU and GPU Systems

Combinatorics is a fundamental aspect of computer science and encompasses many aspects from graph theory to automata. One often overlooked aspect of combinatorics is combination generation which is key to several applications, and critically key to several security protocols. Despite this, there has been an insignificant research dedicated to improving combination generating algorithms since their original introduction roughly 50 years ago. Since their introduction, a number of aspects of computing have changed including the introduction of multi-core CPUs and GPUs. This work examines combination generating algorithms which create combinations for all possible values of n objects taken k at a time. In this paper, we parallelize seven existing combination generation algorithms and optimize one for improved performance on modern parallel architectures. We perform a thorough evaluation of all eight algorithms on a wide range of parameter spaces to gauge their scalability. Combination generators are typically used as a subroutine in a larger application, and so we also examine the performance when combinations are used as input into another routine. We show that the architectural differences between the CPU and GPU influence the performance of the algorithms and include analyses to explain these differences. From our evaluation, we recommend specific combination generators that have the best performance based on architecture and application scenario.