A hardware accelerator for k-th nearest neighbor thinning

Abstract—This paper presents an accelerator for k-th nearest neighbor thinning, a run time intensive algorithmic kernel used in recent multi-objective optimizers. We discuss the thinning algorithm and the accelerator architecture with its modules and operation, and evaluate the accelerator with respect to two different application scenarios. The first is an embedded computing scenario where the accelerator core is part of a configurable system-on-chip implemented on a modern platform FPGA. We show the resource requirements for different instances of the accelerator and report on the raw speedups achieved, which are up to 358x. The second scenario is in high performance computing where we map the accelerator core to a cutting-edge reconfigurable computer, the XD1000 system, and achieve overall speedups of up to 6.6x compared to a software reference. Index Terms—k-th nearest neighbor thinning, reconfigurable accelerator, FPGA, SPEA2