NVIDIA / NVIDIA/cuvs

[FEA] Speedup NN Descent Local Join

Open
#842 0 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

feature request
Dominant language
Cuda
Stars
854
Forks
236
Avg merge
3d 3h
Merged PRs (30d)
62

Description

Upon doing some profiling on cagra, the nn descent local_join kernel + thread join seems to be a bottleneck while building a cagra graph with nn descent. This step takes about 30% of the total CAGRA build time.

I am working with a dataset that has 50M rows and 64 uint8 cols. The nn descent graph degree is 64 (and nn descent intermediate graph degree is 96). The following is an excerpt from the logs after syncing streams at each step and inserting print statements:

[3868420][16:29:44:032433][info ] inside cagra build_knn_graph
[3868420][16:29:44:032488][info ] inside nn_descent build
[3868420][16:30:20:520122][info ] inside GNND build
[3868420][16:30:24:172447][info ] copy 1: copying to d_list_sizes_new_, h_graph_old_ and d_list_sizes_old_
[3868420][16:30:24:861131][info ] finished copy 1
[3868420][16:30:24:861228][info ] # GNND iteraton: 1 / 20
[3868420][16:30:24:861233][info ] adding reverse edges
[3868420][16:30:25:737324][info ] finished adding reverse edges
[3868420][16:30:25:737362][info ] doing local join
[3868420][16:30:31:035741][info ] finished local join
[3868420][16:30:31:035764][info ] now copying graph
[3868420][16:30:31:197658][info ] done copying graph, now copying distance buffer
[3868420][16:30:31:197697][info ] done copying distance buffer
[3868420][16:30:31:870452][info ] copy 1: copying to d_list_sizes_new_, h_graph_old_ and d_list_sizes_old_
[3868420][16:30:32:574193][info ] finished copy 1
[3868420][16:30:32:574271][info ] # GNND iteraton: 2 / 20
[3868420][16:30:32:574273][info ] adding reverse edges
[3868420][16:30:33:782160][info ] finished adding reverse edges
[3868420][16:30:33:782189][info ] doing local join
[3868420][16:30:44:451316][info ] finished local join
[3868420][16:30:44:451342][info ] now copying graph
[3868420][16:30:44:567352][info ] done copying graph, now copying distance buffer
[3868420][16:30:44:567368][info ] done copying distance buffer
[3868420][16:30:45:268489][info ] copy 1: copying to d_list_sizes_new_, h_graph_old_ and d_list_sizes_old_
[3868420][16:30:45:961918][info ] finished copy 1
[3868420][16:30:45:961994][info ] # GNND iteraton: 3 / 20
[3868420][16:30:45:961997][info ] adding reverse edges
[3868420][16:30:47:158006][info ] finished adding reverse edges
[3868420][16:30:47:158075][info ] doing local join
[3868420][16:30:57:080683][info ] finished local join
[3868420][16:30:57:080737][info ] now copying graph
[3868420][16:30:57:197991][info ] done copying graph, now copying distance buffer
[3868420][16:30:57:198010][info ] done copying distance buffer
[3868420][16:30:57:982350][info ] copy 1: copying to d_list_sizes_new_, h_graph_old_ and d_list_sizes_old_
[3868420][16:30:58:681092][info ] finished copy 1
[3868420][16:30:58:681193][info ] # GNND iteraton: 4 / 20
[3868420][16:30:58:681196][info ] adding reverse edges
[3868420][16:30:59:755199][info ] finished adding reverse edges
[3868420][16:30:59:755230][info ] doing local join
[3868420][16:31:10:047609][info ] finished local join
[3868420][16:31:10:047635][info ] now copying graph
[3868420][16:31:10:164425][info ] done copying graph, now copying distance buffer
[3868420][16:31:10:164446][info ] done copying distance buffer
[3868420][16:31:10:909551][info ] copy 1: copying to d_list_sizes_new_, h_graph_old_ and d_list_sizes_old_
[3868420][16:31:11:597536][info ] finished copy 1
[3868420][16:31:11:597611][info ] # GNND iteraton: 5 / 20
[3868420][16:31:11:597615][info ] adding reverse edges
[3868420][16:31:12:570678][info ] finished adding reverse edges
[3868420][16:31:12:570712][info ] doing local join
[3868420][16:31:22:630021][info ] finished local join
[3868420][16:31:22:630063][info ] now copying graph
[3868420][16:31:22:746090][info ] done copying graph, now copying distance buffer
[3868420][16:31:22:746099][info ] done copying distance buffer
[3868420][16:31:23:831048][info ] copy 1: copying to d_list_sizes_new_, h_graph_old_ and d_list_sizes_old_
[3868420][16:31:24:523045][info ] finished copy 1
[3868420][16:31:24:523154][info ] # GNND iteraton: 6 / 20
[3868420][16:31:24:523158][info ] adding reverse edges
[3868420][16:31:25:485562][info ] finished adding reverse edges
[3868420][16:31:25:485602][info ] doing local join
[3868420][16:31:33:866669][info ] finished local join
[3868420][16:31:33:866692][info ] now copying graph
[3868420][16:31:33:984252][info ] done copying graph, now copying distance buffer
[3868420][16:31:33:985937][info ] done copying distance buffer
[3868420][16:31:35:159458][info ] copy 1: copying to d_list_sizes_new_, h_graph_old_ and d_list_sizes_old_

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start with the CAGRA build and NN-Descent/GNND profiling described in the logs, focusing on the local_join kernel and thread join. Compare per-iteration timings before and after an optimization; done requires a measured reduction in local_join and overall build time. The issue names no source files or tests, so locate the relevant entry points first.

Written by the indexing model from the issue text.

Assessment

Domain
performance, search
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.