  In this paper, we study the parallelization of the dedispersion algorithm on
many-core accelerators, including GPUs from AMD and NVIDIA, and the Intel Xeon
Phi. An important contribution is the computational analysis of the algorithm,
from which we conclude that dedispersion is inherently memory-bound in any
realistic scenario, in contrast to earlier reports. We also provide empirical
proof that, even in unrealistic scenarios, hardware limitations keep the
arithmetic intensity low, thus limiting performance. We exploit auto-tuning to
adapt the algorithm, not only to different accelerators, but also to different
observations, and even telescopes. Our experiments show how the algorithm is
tuned automatically for different scenarios and how it exploits and highlights
the underlying specificities of the hardware: in some observations, the tuner
automatically optimizes device occupancy, while in others it optimizes memory
bandwidth. We quantitatively analyze the problem space, and by comparing the
results of optimal auto-tuned versions against the best performing fixed codes,
we show the impact that auto-tuning has on performance, and conclude that it is
statistically relevant.
