Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Make ST_distance core kernels (point-point, point-linestring, linestring-linestring) perfectly load balanced. #1061

Open
isVoid opened this issue Apr 7, 2023 · 1 comment · May be fixed by #1144
Open

Make ST_distance core kernels (point-point, point-linestring, linestring-linestring) perfectly load balanced. #1061

isVoid opened this issue Apr 7, 2023 · 1 comment · May be fixed by #1144
Assignees
@isVoid
Labels
performance

Comments

@isVoid
Copy link
Contributor

isVoid commented Apr 7, 2023 •
edited
Loading

Currently, distance computation kernels are not perfectly load balanced. Most kernels follow this pattern: launch the number of threads on one operand and for each thread loop over points/segments of the correponding pair in the other. This can slow down the operation if the data are unbalanced/skewed.

Instead, the kernels should launch the number of thread that's makes one thread computes one pair of point-point/point-segment/segment-segment, then uses atomic operation to aggregate the result. This avoids slow down if the data is skewed.
@isVoid isVoid mentioned this issue Apr 7, 2023
Closed
@github-project-automation github-project-automation bot moved this to Todo in cuSpatial Apr 7, 2023
@isVoid isVoid self-assigned this Apr 7, 2023
@isVoid isVoid changed the title Make core kernels (point-point, point-linestring, linestring-linestring) perfectly load balanced. Make ST_distance core kernels (point-point, point-linestring, linestring-linestring) perfectly load balanced. Apr 8, 2023
@isVoid isVoid linked a pull request May 19, 2023 that will close this issue
Draft
3 tasks
@isVoid isVoid moved this from Todo to In Progress in cuSpatial May 22, 2023
@isVoid
Copy link
Contributor Author

isVoid commented May 30, 2023

This work require further investigation on the performance for load-balanced kernel. According to a recent benchmark , the "loop-segment" kernels performs better than load-balanced kernel if the dataset is not skewed. However, there exists some ground for optimization for load balanced kernel.

Benchmark:
https://gist.github.com/isVoid/99ce3f6425528217da78118ab2653959

@isVoid isVoid moved this from In Progress to Blocked in cuSpatial May 30, 2023
@isVoid isVoid mentioned this issue Jun 5, 2023
Closed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@isVoid isVoid

Labels
performance
Projects
cuSpatial
Status: Blocked
Milestone
No milestone
1 participant
@isVoid