A data structure for geographical partitioning
called multi-dimensional data-indexing enables effective
CPU-based nearest-neighbor searches. Despite not being a
natural match for Many-Integrated Core Architecture
(MIC) implementation, depth-first search MultiDimensional Data-Indexing can nevertheless be successful
with the right engineering choices.
We suggested a technique that minimizes data
structure memory trace by limiting the maximum height of
the DFS Multi-Dimensional Data-Indexing.
With tens of thousands to tens of millions of points in
the MIC kernel code, we optimize the multi-core MIC NN
search. In comparison to a single-core CPU of equivalent
power, it is 20–40 times quicker. NN uses the knowledge
obtained from improving MIC code to find ways to rewrite
As a consequence, the initial level of CTA and
engineering choices to make the Multi-Dimensional DataIndexing search algorithm on CPU and MIC simpler
account for the bulk of the parallel performance in this
study. Threads inside each thread warp split onto several
search pathways for the second level of CTA using MultiDimensional Data-Indexing.
Multi-Dimensional Data-Indexing, MIC, depth-first search, Thread-block size.