submatrix_dissection Module Reference

Data Types
type	submatrix_dissection_type

Functions/Subroutines
subroutine	submatrix_get_relevant_sm_columns (this, sm_id, first, last)
	determine which columns of the submatrix are relevant for the result matrix

Detailed Description

Note

This module implements a modified version of the submatrix method, proposed in M. Lass, S. Mohr, H. Wiebeler, T. Kuehne, C. Plessl A Massively Parallel Algorithm for the Approximate Calculation of Inverse p-th Roots of Large Sparse Matrices Proc. Platform for Advanced Scientific Computing (PASC) Conference, ACM, 2018

The method is extended to minimize the required data transfers and floating-point operations under the assumption that non-zero blocks of the matrix are close to its diagonal.

Submatrices can be constructed not for single columns of the matrix but for a set of w consecutive submatrices. The underlying assumption is that columns next to each other have relatively similar occupation patterns, i.e., constructing a submatrix from columns x and x+1 should not lead to a much bigger submatrix than contructing it only from column x.

The construction of the submatrices requires communication between all ranks. It is crucial to implement this communication as efficient as possible, i.e., data should only ever be transferred once between two ranks and message sizes need to be sufficiently large to utilize the communication bandwidth. To achieve this, we communicate the required blocks for all submatrices at once and copy them to large buffers before transmitting them via MPI.

Note on multi-threading: Submatrices can be constructed and processed in parallel by multiple threads. However, generate_submatrix, get_sm_ids_for_rank and copy_resultcol are the only thread-safe routines in this module. All other routines involve MPI communication or operate on common, non-protected data and are hence not thread-safe.

TODO:

• generic types (for now only dp supported)
• optimization of threaded initialization
• sanity checks at the beginning of all methods

Author

Michael Lass

Function/Subroutine Documentation

submatrix_get_relevant_sm_columns()

subroutine submatrix_dissection::submatrix_get_relevant_sm_columns	(	class(submatrix_dissection_type), intent(in)	this,
		integer, intent(in)	sm_id,
		integer, intent(out)	first,
		integer, intent(out)	last
	)

determine which columns of the submatrix are relevant for the result matrix

Parameters

this	- object of class submatrix_dissection_type
sm_id	- id of the submatrix
first	- first column of submatrix that is relevant
last	- last column of submatrix that is relevant

Definition at line 100 of file submatrix_dissection.F.

Here is the call graph for this function: