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

Tpetra: Graph / matrix insert doesn't merge, taking extra space & hindering thread parallelism #119

Closed
mhoemmen opened this issue Jan 30, 2016 · 10 comments
Closed

Tpetra: Graph / matrix insert doesn't merge, taking extra space & hindering thread parallelism #119

mhoemmen opened this issue Jan 30, 2016 · 10 comments
Labels
pkg: Tpetra story The issue corresponds to a Kanban Story (vs. Epic or Task) TpetraRF
Milestone
Tpetra-backlog

Comments

@mhoemmen
Copy link
Contributor

@trilinos/tpetra

CrsGraph::insert{Local,Global}Indices and CrsMatrix::insert{Local,Global}Values currently do something nonintuitive: multiple inserts to the same row and column index are stored separately and not merged until fillComplete. For example, inserting (1,1) into a CrsGraph 10 times would require storing 10 entries, until fillComplete, at which point the entries get merged together into a single entry. This is especially bad for StaticProfile, which currently would counterintuitively fail on 9 of those 10 inserts if the user reasonably gave CrsGraph an upper bound of 1 entry per row. We don't want users to have to rely on DynamicProfile, which is both slow and (especially due to this issue) memory-intensive.

Commit 68e77d5 begins the process of fixing this. It does not yet change the behavior of CrsGraph or CrsMatrix. For now, Tpetra has new internal utility functions for merging indices (for CrsGraph) or indices and values together (for CrsMatrix). I also added some unit tests for the new functions. However, they still need to be integrated into CrsGraph and CrsMatrix. My initial attempts broke a lot of invariants and made a lot of tests fail. I realize I'll have to do this VERY cautiously.
@mhoemmen mhoemmen mentioned this issue Feb 1, 2016
Closed
@mhoemmen
Copy link
Contributor Author

Current status:

  • I need to add patches here (as .txt files, since GitHub doesn't take .patch files). Patches fail tests but are still worth having as a reference for doing work.
  • For second attempt at fixing this, be more cautious. In particular, don't try to get rid of lazy allocation.

@mhoemmen mhoemmen added the stage: in progress Work on the issue has started label Feb 15, 2016
@mhoemmen mhoemmen removed the stage: in progress Work on the issue has started label Mar 6, 2016
@mhoemmen mhoemmen mentioned this issue Mar 12, 2016
Closed
@jgfouca jgfouca mentioned this issue Jul 6, 2016
Merged
bartlettroscoe added a commit that referenced this issue Aug 2, 2016
@bartlettroscoe
Automatic snapshot commit from tribits at c7658ab
d34df61 
Origin repo remote tracking branch: 'github/master'
Origin repo remote repo URL: 'github = git@github.com:tribitspub/TriBITS.git'

At commit:

commit 514ea61cde407bb713d837b3d3a92f641c2c7dd8
Author:  Roscoe A. Bartlett <rabartl@sandia.gov>
Date:    Mon Aug 1 17:31:16 2016 -0400
Summary: Move and rename sorted_str() to sorted_dict_str() (TriBITS #119)
bartlettroscoe added a commit that referenced this issue Aug 8, 2016
@bartlettroscoe
Automatic snapshot commit from tribits at 1205b3f
841e66d 
Origin repo remote tracking branch: 'github/master'
Origin repo remote repo URL: 'github = git@github.com:tribitspub/TriBITS.git'

At commit:

commit 1205b3f13656316d9e88c03e62b4739f68e49c9d
Author:  Roscoe A. Bartlett <rabartl@sandia.gov>
Date:    Mon Aug 8 17:36:52 2016 -0400
Summary: Fix echoRunSysCmnd() with extraEnv (#119)
mhoemmen pushed a commit that referenced this issue Sep 9, 2016
Tpetra::CrsGraph: Address #601 (globalAssemble bug)
3d70d02 
@trilinos/tpetra Address #601 (globalAssemble highly broken) for
CrsGraph.  This fixes the known performance and correctness issues
with CrsGraph::globalAssemble.

This commit has the side effect of starting to address #119 for
CrsGraph::insertGlobalIndices.  When the graph is StaticProfile and
the graph doesn't have enough space for us just to write the values
into the extra space, insertGlobalIndicesImpl now checks whether the
input indices have some entries in common ("duplicates") with the
row's current column indices.  If so (if there are duplicates), and if
that means the row actually _does_ have enough space, it then merges
in the new entries (without sorting).

In order to make tests pass, I had to fix CrsGraph unit tests as well.
I wrote "fix" because the tests were being _too_ strict.  That is,
they were expecting StaticProfile inserts always to fail if the row is
out of room, regardless of whether there _would_ be enough space if
the input were merged in instead of just being appended without a
merge.  This commit fixes that.  Now, the CrsGraph tets only expect
StaticProfile inserts to fail if the result of merging the input
column indices with the current column indices in that row does not
exceed the static allocation.

Build/Test Cases Summary
Enabled Packages: Ifpack2, TpetraCore
Disabled Packages: FEI,PyTrilinos,Moertel,STK,SEACAS,ThreadPool,OptiPack,Rythmos,Intrepid,ROL
0) MPI_DEBUG => passed: passed=130,notpassed=0 (3.67 min)
1) SERIAL_RELEASE => passed: passed=100,notpassed=0 (1.36 min)
Other local commits for this build/test group: 081712c, 7be0c06
@mhoemmen mhoemmen added the story The issue corresponds to a Kanban Story (vs. Epic or Task) label Sep 16, 2016
@mhoemmen
Copy link
Contributor Author

This is story-level, because it needs to be broken up into smaller tasks in order to succeed.
The solution for #601 actually addressed a small part of this for CrsGraph.

@mhoemmen mhoemmen mentioned this issue Sep 27, 2016
Closed
@mhoemmen mhoemmen added this to the Tpetra-backlog milestone Nov 2, 2016
@mhoemmen
Copy link
Contributor Author

I've been looking at this. It turns out that it's not enough to check whether input indices have matching entries currently in the row. One must also check whether the input itself has duplicates. Otherwise, if the input is (for example) [1, 1, 1, 1], insertion into an empty row [] would result in [1, 1, 1, 1], but insertion into a row [1] would result in [1].

@mhoemmen mhoemmen mentioned this issue Feb 21, 2017
Closed
@mhoemmen
Copy link
Contributor Author

BUMP: This hinders (not actually blocks) #2267 .

  1. It makes the "local assembly into owned graph" part of that use pattern more difficult.
  2. It inflates the amount of memory that a fix for Tpetra: create CrsGraph transferAndFillComplete #2267 might need.

@william76 @tjfulle

@mhoemmen mhoemmen mentioned this issue Feb 28, 2018
Closed
@mhoemmen
Copy link
Contributor Author

@trilinos/tpetra BUMP per @csiefer2 request

@github-actions
Copy link

This issue has had no activity for 365 days and is marked for closure. It will be closed after an additional 30 days of inactivity.
If you would like to keep this issue open please add a comment and remove the MARKED_FOR_CLOSURE label.
If this issue should be kept open even with no activity beyond the time limits you can add the label DO_NOT_AUTOCLOSE.

@github-actions github-actions bot added the MARKED_FOR_CLOSURE Issue or PR is marked for auto-closure by the GitHub Actions bot. label Dec 15, 2020
@mhoemmen
Copy link
Contributor Author

I have a vague memory that this got fixed early this year, but I might be remembering a different bug.

@github-actions github-actions bot removed the MARKED_FOR_CLOSURE Issue or PR is marked for auto-closure by the GitHub Actions bot. label Dec 18, 2020
@trilinos-autotester trilinos-autotester mentioned this issue Nov 11, 2021
Closed
@github-actions
Copy link

This issue has had no activity for 365 days and is marked for closure. It will be closed after an additional 30 days of inactivity.
If you would like to keep this issue open please add a comment and/or remove the MARKED_FOR_CLOSURE label.
If this issue should be kept open even with no activity beyond the time limits you can add the label DO_NOT_AUTOCLOSE.
If it is ok for this issue to be closed, feel free to go ahead and close it. Please do not add any comments or change any labels or otherwise touch this issue unless your intention is to reset the inactivity counter for an additional year.

@github-actions github-actions bot added the MARKED_FOR_CLOSURE Issue or PR is marked for auto-closure by the GitHub Actions bot. label Dec 18, 2021
@mhoemmen
Copy link
Contributor Author

@csiefer2 Did y'all actually fix this?

@github-actions github-actions bot removed the MARKED_FOR_CLOSURE Issue or PR is marked for auto-closure by the GitHub Actions bot. label Dec 22, 2021
@csiefer2
Copy link
Member

Kokkos-level graph assembly (in progress) should render this moot, at least if you're using it.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
pkg: Tpetra story The issue corresponds to a Kanban Story (vs. Epic or Task) TpetraRF
Projects
Tpetra
Status: Done
Milestone
Tpetra-backlog
Development

No branches or pull requests
4 participants
@mhoemmen @jwillenbring @csiefer2 @kddevin