Added basic push/pull optimization code to LAGraph_MaximalMatching - Githubissues

GraphBLAS / LAGraph

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

225 stars 59 forks source link

Added basic push/pull optimization code to LAGraph_MaximalMatching #226

Closed VidithM closed 1 year ago

VidithM commented 1 year ago

Changes to `LAGraph_MaximalMatching`:

Added basic push/pull optimization code that can be turned on and off with the OPTIMIZE_PUSH_PULL macro. The best sparsity threshold (the point at which the code switches from push to pull) was determined to be 0.06. Here are some new results:

Results for $N = 10^6$, $k = 10$, `sparsity_thresh` = 0.06	Threads	Speedup	Old Speedup (no push/pull)
8	15.6	10.38
12	20.29	13.85
24	28.67	15.54

The old results are from my undergrad thesis. All results were collected on backslash.

Changes to `test_CoarsenMatching`:

Deleted warning about LAGraph_Random since pre-built graphs are not being used in this test.
Other changes
Freed some objects earlier in the Parent_to_S function of LAGraph_CoarsenMatching
Put back code to make custom CPP matching tests use random seeds