Highly Parallel Sorting Network Verification Using FPGAs

Sorting networks are of prime importance as circuits, with applications in sorting small data chunks, big data analytics, permuting packets, and system interconnects. Finding optimal sorting networks is a highly complex problem, and knowledge on optimal sorting networks is limited. When optimising the network depth or the number of comparators, one of the most expensive tasks is considered to be verification, that is, to verify that the candidate compare-and-swap network actually sorts the data. This grows exponentially with the size of the sorting network. However, FPGAs allow vast amounts of internal parallelism, and our presented work exploits this flexibility using dataflow techniques to achieve unparalleled amounts of speedup for sorting network verification. This work can be used in a modular way to accelerate the search for optimal sorting networks with a high number of inputs, as well for similar verification problems.