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

MST Preprocessing for symbolic Cholesky #1765

Merged
merged 26 commits into from
Jan 16, 2025
Merged

MST Preprocessing for symbolic Cholesky #1765

merged 26 commits into from
Jan 16, 2025

Conversation

upsj
Copy link
Member

@upsj upsj commented Jan 11, 2025 •
edited
Loading

Extracted from #1758, this only contains the MST preprocessing step.

Related literature: A. Fallin, A. Gonzalez, J. Seo, and M. Burtscher, “A High-Performance MST Implementation for GPUs,” in Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, in SC ’23. New York, NY, USA: Association for Computing Machinery, Nov. 2023, pp. 1–13. doi: 10.1145/3581784.3607093.

@upsj upsj added the 1:ST:ready-for-review This PR is ready for review label Jan 11, 2025
@upsj upsj requested a review from a team January 11, 2025 13:41
@upsj upsj self-assigned this Jan 11, 2025
@ginkgo-bot ginkgo-bot added reg:build This is related to the build system. reg:testing This is related to testing. reg:benchmarking This is related to benchmarking. type:factorization This is related to the Factorizations reg:helper-scripts This issue/PR is related to the helper scripts mainly concerned with development of Ginkgo. mod:all This touches all Ginkgo modules. labels Jan 11, 2025
@MarcelKoch MarcelKoch self-requested a review January 13, 2025 13:18
MarcelKoch
MarcelKoch requested changes Jan 14, 2025
View reviewed changes
Copy link
Member

@MarcelKoch MarcelKoch left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Mostly LGTM. I have some questions about the distinction between the device and non-device code paths.
Also I think it would be helpful if you add the literature reference to the code.

test/factorization/cholesky_kernels.cpp Outdated Show resolved Hide resolved
reference/test/factorization/cholesky_kernels.cpp Outdated Show resolved Hide resolved
reference/test/factorization/cholesky_kernels.cpp Outdated Show resolved Hide resolved
core/factorization/symbolic.cpp Show resolved Hide resolved
reference/factorization/cholesky_kernels.cpp Show resolved Hide resolved
reference/factorization/elimination_forest_kernels.cpp Outdated Show resolved Hide resolved
reference/factorization/elimination_forest_kernels.cpp Outdated Show resolved Hide resolved
omp/factorization/elimination_forest_kernels.cpp Outdated Show resolved Hide resolved
common/cuda_hip/factorization/elimination_forest_kernels.cpp Outdated Show resolved Hide resolved
dev_tools/scripts/generate_cuda_memory_ptx.py Outdated Show resolved Hide resolved
yhmtsai
yhmtsai reviewed Jan 14, 2025
View reviewed changes
Copy link
Member

@yhmtsai yhmtsai left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

first part of my review

benchmark/sparse_blas/operations.cpp Outdated Show resolved Hide resolved
benchmark/sparse_blas/operations.cpp Outdated Show resolved Hide resolved
core/factorization/elimination_forest.cpp Outdated Show resolved Hide resolved
reference/factorization/cholesky_kernels.cpp Outdated Show resolved Hide resolved
reference/test/factorization/cholesky_kernels.cpp Outdated Show resolved Hide resolved
test/factorization/cholesky_kernels.cpp Show resolved Hide resolved
upsj and others added 18 commits January 15, 2025 09:57
@upsj
add ani4 to symbolic cholesky test set
e62b52f
@upsj
fix sparsity pattern output
016d0ea
@upsj
fix incorrect include
91f5b97
@upsj
add Cholesky skeleton tree computation kernel
50924ca
@upsj
add more precise atomic operations
0bf134d
@upsj
fix matrix symmetry
9caaa2d
@upsj
fix reference MST algorithm
f2d970c
@upsj
add GPU MST algorithm for Cholesky preprocessing
0af05e2
@upsj
add AMD support
7158492
@upsj
add benchmark for MST-enhanced symbolic Cholesky
7d96d1d
@upsj
extract elimination forest kernels into separate file
ef4b6f1
@upsj
update copyright years
213ced6
@upsj
rename compute_elim_forest to compute_elimination_forest
7bb00ab
@upsj @MarcelKoch
consider only lower triangular entries for skeleton tree input
6bff427 
Co-authored-by: Marcel Koch <[email protected]>
@upsj
fix memory script
5aa16c8
@upsj
remove unnecessary tabs/newlines from generation script
941ceb7
@upsj
rebuild memory.nvidia.hpp.inc
418714b
@upsj @MarcelKoch @yhmtsai
review updates
bfd2598 
Co-authored-by: Marcel Koch <[email protected]>
Co-authored-by: Yu-Hsiang M. Tsai <[email protected]>
@upsj upsj force-pushed the cholesky-mst-extracted branch from fce1842 to 8656cdf Compare January 15, 2025 09:57
@upsj upsj requested review from MarcelKoch and yhmtsai January 15, 2025 09:58
MarcelKoch
MarcelKoch approved these changes Jan 15, 2025
View reviewed changes
Copy link
Member

@MarcelKoch MarcelKoch left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I would still prefer changing the comment about the edge weights, but it's not a blocker.

reference/test/factorization/cholesky_kernels.cpp Outdated Show resolved Hide resolved
reference/factorization/elimination_forest_kernels.cpp Outdated Show resolved Hide resolved
reference/factorization/elimination_forest_kernels.cpp Outdated Show resolved Hide resolved
core/factorization/symbolic.cpp Show resolved Hide resolved
@upsj upsj added the 1:ST:no-changelog-entry Skip the wiki check for changelog update label Jan 15, 2025
@codecov Codecov
Copy link

codecov bot commented Jan 16, 2025

Codecov Report

Attention: Patch coverage is 52.23214% with 107 lines in your changes missing coverage. Please review.

Project coverage is 89.35%. Comparing base (75b134a) to head (706d584).

Files with missing lines Patch % Lines
test/factorization/cholesky_kernels.cpp 0.00% 55 Missing ⚠️
core/factorization/symbolic.cpp 7.14% 26 Missing ⚠️
omp/factorization/elimination_forest_kernels.cpp 40.00% 24 Missing ⚠️
core/device_hooks/common_kernels.inc.cpp 0.00% 2 Missing ⚠️
Additional details and impacted files 
@@             Coverage Diff             @@
##           develop    #1765      +/-   ##
===========================================
- Coverage    89.73%   89.35%   -0.38%     
===========================================
  Files          795      797       +2     
  Lines        65800    65965     +165     
===========================================
- Hits         59045    58946      -99     
- Misses        6755     7019     +264

☔ View full report in Codecov by Sentry.
📢 Have feedback on the report? Share it here.

yhmtsai
yhmtsai reviewed Jan 16, 2025
View reviewed changes
Copy link
Member

@yhmtsai yhmtsai left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

second part of my review. some question might be dumb after I go through the algorithm.
Will do the algorithm part later

common/cuda_hip/factorization/elimination_forest_kernels.cpp Outdated Show resolved Hide resolved
common/cuda_hip/factorization/elimination_forest_kernels.cpp Outdated Show resolved Hide resolved
common/cuda_hip/factorization/elimination_forest_kernels.cpp Show resolved Hide resolved
core/factorization/symbolic.cpp Show resolved Hide resolved
test/factorization/cholesky_kernels.cpp Show resolved Hide resolved
test/factorization/cholesky_kernels.cpp Show resolved Hide resolved
common/cuda_hip/components/memory.nvidia.hpp.inc Show resolved Hide resolved
common/cuda_hip/factorization/elimination_forest_kernels.cpp Show resolved Hide resolved
@upsj upsj requested a review from yhmtsai January 16, 2025 10:31
@upsj upsj added 1:ST:ready-to-merge This PR is ready to merge. and removed 1:ST:ready-for-review This PR is ready for review labels Jan 16, 2025
@upsj upsj merged commit 0b3436e into develop Jan 16, 2025
10 of 11 checks passed
@upsj upsj deleted the cholesky-mst-extracted branch January 16, 2025 13:53
@sonarqubecloud SonarQubeCloud
Copy link

Quality Gate Passed Quality Gate passed

Issues
0 New issues
0 Accepted issues

Measures
0 Security Hotspots
0.0% Coverage on New Code
0.0% Duplication on New Code

See analysis details on SonarQube Cloud

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers

@yhmtsai yhmtsai yhmtsai approved these changes

@MarcelKoch MarcelKoch MarcelKoch approved these changes

Assignees

@upsj upsj

Labels
1:ST:no-changelog-entry Skip the wiki check for changelog update 1:ST:ready-to-merge This PR is ready to merge. 1:ST:run-full-test mod:all This touches all Ginkgo modules. reg:benchmarking This is related to benchmarking. reg:build This is related to the build system. reg:helper-scripts This issue/PR is related to the helper scripts mainly concerned with development of Ginkgo. reg:testing This is related to testing. type:factorization This is related to the Factorizations
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.
4 participants
@upsj @MarcelKoch @yhmtsai @ginkgo-bot