BEGIN:VCALENDAR
VERSION:2.0
PRODID:Linklings LLC
BEGIN:VTIMEZONE
TZID:America/Chicago
X-LIC-LOCATION:America/Chicago
BEGIN:DAYLIGHT
TZOFFSETFROM:-0600
TZOFFSETTO:-0500
TZNAME:CDT
DTSTART:19700308T020000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=2SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0500
TZOFFSETTO:-0600
TZNAME:CST
DTSTART:19701101T020000
RRULE:FREQ=YEARLY;BYMONTH=11;BYDAY=1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTAMP:20210808T235336Z
LOCATION:Room A
DTSTART;TZID=America/Chicago:20210809T081500
DTEND;TZID=America/Chicago:20210809T083000
UID:icpp_ICPP 2021_sess134_duac_pap103@linklings.com
SUMMARY:Warp-centric K-Nearest Neighbor Graphs construction on GPU
DESCRIPTION:DUAC Workshop\n\nWarp-centric K-Nearest Neighbor Graphs constr
uction on GPU\n\nMeyer, Pozo, Nunan Zola\n\nRecent advances and applicatio
ns of machine learning algorithms are becoming more common in different fi
elds. It is expected that some applications require the processing of larg
e datasets with those algorithms, which leads to high computational costs.
Massively parallel GPU methods can be applied to surpass this limitation
and reduce the execution time of these algorithms. The construction of app
roximate K-Nearest Neighbor Graphs (K-NNG) is frequently required for simi
larity search or other applications such as the t-SNE dimensionality reduc
tion technique. The K-NNG represents the K closest points (neighbors) for
each point in a set. In this paper, we propose and analyze an all-points K
-Nearest Neighbor Graph construction algorithm on GPU called Warp-centric
K-NNG (w-KNNG), which is based on the Random Projection Forest method. Usu
ally, the construction or search for k-NN sets for high dimensional points
presents challenges for its implementation on many-core processing units,
due to the space limitation in maintaining these sets in high speed share
d memory. We present three warp-centric approaches for our algorithm that
efficiently search and maintain the k-NN high dimensional point sets in gl
obal memory. In our experiments, the new methods allows the algorithm to a
chieve up to 639% faster execution when compared to the state-of-the-art F
AISS library, considering an equivalent accuracy of approximate K-NNG. One
of the new strategies (w-KNNG atomic) is more successful when applied to
a smaller number of dimensions, while the tiled w-KNNG approach was succes
sful in general scenarios for higher dimensional points.
END:VEVENT
END:VCALENDAR