This is a library plus a test harness for collecting algorithms that use the GraphBLAS. For test coverage reports, see https://graphblas.org/LAGraph/ . Documentation: https://lagraph.readthedocs.org
Other
229
stars
61
forks
source link
Optimize minimum mode selection in the CDLP algorithm #32
The 'minimum mode selection' algorithm in my previous CDLP implementation was very inefficient as it traversed the array of elements in the direction of 0 -> N-1, identified the start and end position of each row, i.e. row_start_i -> row_end_i, then traversed those in the opposite direction row_end_i -> row_start_i. This probably resulted in failed branch prediction and cache misses, causing a performance hit which was evident at larger sizes such as the Twitter data set with 2B edges.
This uses a single pass on arrays I and X and is significantly faster (on the Twitter data set, the previous runtime was 10h+, now it's less than 1h) but there are still performance gains to be made.
The 'minimum mode selection' algorithm in my previous CDLP implementation was very inefficient as it traversed the array of elements in the direction of
0 -> N-1, identified the start and end position of each row, i.e.row_start_i -> row_end_i, then traversed those in the opposite directionrow_end_i -> row_start_i. This probably resulted in failed branch prediction and cache misses, causing a performance hit which was evident at larger sizes such as the Twitter data set with 2B edges.This uses a single pass on arrays
IandXand is significantly faster (on the Twitter data set, the previous runtime was 10h+, now it's less than 1h) but there are still performance gains to be made.