[FEA] Speedup NN Descent Local Join
Nobody has claimed this yet.
- 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
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- 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