Bigger Buffer k-d Trees on Multi-Many-Core Systems
Institute for Computing and Information Sciences, Radboud University Nijmegen, Toernooiveld 212, 6525 EC Nijmegen, The Netherlands
arXiv:1512.02831 [cs.DC], (9 Dec 2015)
@article{gieseke2015bigger,
title={Bigger Buffer k-d Trees on Multi-Many-Core Systems},
author={Gieseke, Fabian and Oancea, Cosmin Eugen and Mahabal, Ashish and Igel, Christian and Heskes, Tom},
year={2015},
month={dec},
archivePrefix={"arXiv"},
primaryClass={cs.DC}
}
A buffer k-d tree is a k-d tree variant for massively-parallel nearest neighbor search. While providing valuable speed-ups on modern many-core devices in case both a large number of reference and query points are given, buffer k-d trees are limited by the amount of points that can fit on a single device. In this work, we show how to modify the original data structure and the associated workflow to make the overall approach capable of dealing with massive data sets. We further provide a simple yet efficient way of using multiple devices given in a single workstation. The applicability of the modified framework is demonstrated in the context of astronomy, a field that is faced with huge amounts of data.
December 15, 2015 by hgpu
