uw-ipd / tmol

TMol
Apache License 2.0
31 stars 3 forks source link

Aleaverfay/fast cpu apsp #274

Closed aleaverfay closed 1 year ago

aleaverfay commented 1 year ago

This PR speeds up the Floyd Warshall O(N^3) all-pairs-shortest-path algorithm In PoseStack construction with Dijkstra's single-source shortest-path-to-all-other-vertices O(N^2 + NKlnK) algorithm when a threshold/cutoff weight/distance is given where K is the expected number of nodes that will be traversed from each starting node before the threshold is reached. For an average sized antibody sequence (e.g. Pertuzumab) this is a roughly 100x speedup. The N^2 component is to simply initialize the output weight tensor / examine all input edge weights.

codecov[bot] commented 1 year ago

Codecov Report

Attention: 1 lines in your changes are missing coverage. Please review.

Comparison is base (ace29a8) 94.93% compared to head (d2be565) 94.95%. Report is 2 commits behind head on master.

Additional details and impacted files ```diff @@ Coverage Diff @@ ## master #274 +/- ## ========================================== + Coverage 94.93% 94.95% +0.02% ========================================== Files 374 375 +1 Lines 23883 23997 +114 ========================================== + Hits 22673 22787 +114 Misses 1210 1210 ``` | [Flag](https://app.codecov.io/gh/uw-ipd/tmol/pull/274/flags?src=pr&el=flags&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=uw-ipd) | Coverage Δ | | |---|---|---| | [_shrug_Testing_CPU](https://app.codecov.io/gh/uw-ipd/tmol/pull/274/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=uw-ipd) | `90.16% <83.20%> (+0.13%)` | :arrow_up: | | [_shrug_Testing_CPU_debug_w_o_jit](https://app.codecov.io/gh/uw-ipd/tmol/pull/274/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=uw-ipd) | `91.96% <83.20%> (?)` | | | [_shrug_Testing_CPU_w_o_jit](https://app.codecov.io/gh/uw-ipd/tmol/pull/274/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=uw-ipd) | `?` | | | [_shrug_Testing_CUDA](https://app.codecov.io/gh/uw-ipd/tmol/pull/274/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=uw-ipd) | `92.40% <98.47%> (+0.02%)` | :arrow_up: | Flags with carried forward coverage won't be shown. [Click here](https://docs.codecov.io/docs/carryforward-flags?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=uw-ipd#carryforward-flags-in-the-pull-request-comment) to find out more. | [Files](https://app.codecov.io/gh/uw-ipd/tmol/pull/274?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=uw-ipd) | Coverage Δ | | |---|---|---| | [tmol/pose/compiled/apsp\_ops.py](https://app.codecov.io/gh/uw-ipd/tmol/pull/274?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=uw-ipd#diff-dG1vbC9wb3NlL2NvbXBpbGVkL2Fwc3Bfb3BzLnB5) | `100.00% <100.00%> (ø)` | | | [tmol/pose/pose\_stack\_builder.py](https://app.codecov.io/gh/uw-ipd/tmol/pull/274?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=uw-ipd#diff-dG1vbC9wb3NlL3Bvc2Vfc3RhY2tfYnVpbGRlci5weQ==) | `97.61% <100.00%> (ø)` | | | [...tests/io/test\_pose\_stack\_construction\_benchmark.py](https://app.codecov.io/gh/uw-ipd/tmol/pull/274?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=uw-ipd#diff-dG1vbC90ZXN0cy9pby90ZXN0X3Bvc2Vfc3RhY2tfY29uc3RydWN0aW9uX2JlbmNobWFyay5weQ==) | `100.00% <100.00%> (ø)` | | | [...sts/pose/compiled/test\_all\_pairs\_shortest\_paths.py](https://app.codecov.io/gh/uw-ipd/tmol/pull/274?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=uw-ipd#diff-dG1vbC90ZXN0cy9wb3NlL2NvbXBpbGVkL3Rlc3RfYWxsX3BhaXJzX3Nob3J0ZXN0X3BhdGhzLnB5) | `100.00% <100.00%> (ø)` | | | [tmol/tests/pose/test\_pose\_stack\_construction.py](https://app.codecov.io/gh/uw-ipd/tmol/pull/274?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=uw-ipd#diff-dG1vbC90ZXN0cy9wb3NlL3Rlc3RfcG9zZV9zdGFja19jb25zdHJ1Y3Rpb24ucHk=) | `98.93% <ø> (ø)` | | | [tmol/tests/score/ref/test\_ref\_energy\_term.py](https://app.codecov.io/gh/uw-ipd/tmol/pull/274?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=uw-ipd#diff-dG1vbC90ZXN0cy9zY29yZS9yZWYvdGVzdF9yZWZfZW5lcmd5X3Rlcm0ucHk=) | `100.00% <100.00%> (ø)` | | | [...tests/utility/datastructures/test\_in\_place\_heap.py](https://app.codecov.io/gh/uw-ipd/tmol/pull/274?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=uw-ipd#diff-dG1vbC90ZXN0cy91dGlsaXR5L2RhdGFzdHJ1Y3R1cmVzL3Rlc3RfaW5fcGxhY2VfaGVhcC5weQ==) | `100.00% <100.00%> (ø)` | | | [tmol/utility/cpp\_extension.py](https://app.codecov.io/gh/uw-ipd/tmol/pull/274?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=uw-ipd#diff-dG1vbC91dGlsaXR5L2NwcF9leHRlbnNpb24ucHk=) | `98.18% <100.00%> (+0.10%)` | :arrow_up: | | [tmol/tests/pack/sim\_anneal/test\_sim\_anneal.py](https://app.codecov.io/gh/uw-ipd/tmol/pull/274?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=uw-ipd#diff-dG1vbC90ZXN0cy9wYWNrL3NpbV9hbm5lYWwvdGVzdF9zaW1fYW5uZWFsLnB5) | `12.38% <0.00%> (-0.12%)` | :arrow_down: | ... and [1 file with indirect coverage changes](https://app.codecov.io/gh/uw-ipd/tmol/pull/274/indirect-changes?src=pr&el=tree-more&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=uw-ipd)

:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.