#include "mpi.h"
#include <iostream>
#include <cstdarg>
#include "SpParMat.h"
#include "SpParHelper.h"
#include "MPIType.h"
#include "Friends.h"
#include "OptBuf.h"

Functions
template<typename IT , typename NT >
FullyDistVec< IT, NT >	Concatenate (vector< FullyDistVec< IT, NT > > &vecs)
template<typename MATRIXA , typename MATRIXB >
bool	CheckSpGEMMCompliance (const MATRIXA &A, const MATRIXB &B)
template<typename SR , typename NUO , typename UDERO , typename IU , typename NU1 , typename NU2 , typename UDERA , typename UDERB >
SpParMat< IU, NUO, UDERO >	Mult_AnXBn_DoubleBuff (SpParMat< IU, NU1, UDERA > &A, SpParMat< IU, NU2, UDERB > &B, bool clearA=false, bool clearB=false)
template<typename SR , typename NUO , typename UDERO , typename IU , typename NU1 , typename NU2 , typename UDERA , typename UDERB >
SpParMat< IU, NUO, UDERO >	Mult_AnXBn_Synch (SpParMat< IU, NU1, UDERA > &A, SpParMat< IU, NU2, UDERB > &B, bool clearA=false, bool clearB=false)
template<typename MATRIX , typename VECTOR >
void	CheckSpMVCompliance (const MATRIX &A, const VECTOR &x)
template<typename SR , typename IU , typename NUM , typename UDER >
FullyDistSpVec< IU, typename promote_trait< NUM, IU > ::T_promote >	SpMV (const SpParMat< IU, NUM, UDER > &A, const FullyDistSpVec< IU, IU > &x, bool indexisvalue, OptBuf< int32_t, typename promote_trait< NUM, IU >::T_promote > &optbuf)
template<typename SR , typename IU , typename NUM , typename UDER >
FullyDistSpVec< IU, typename promote_trait< NUM, IU > ::T_promote >	SpMV (const SpParMat< IU, NUM, UDER > &A, const FullyDistSpVec< IU, IU > &x, bool indexisvalue)
template<typename IU , typename NV >
void	TransposeVector (MPI_Comm &World, const FullyDistSpVec< IU, NV > &x, int32_t &trxlocnz, IU &lenuntil, int32_t &trxinds, NV &trxnums, bool indexisvalue)
template<typename IU , typename NV >
void	AllGatherVector (MPI_Comm &ColWorld, int trxlocnz, IU lenuntil, int32_t &trxinds, NV &trxnums, int32_t &indacc, NV &numacc, int &accnz, bool indexisvalue)
template<typename SR , typename IVT , typename OVT , typename IU , typename NUM , typename UDER >
void	LocalSpMV (const SpParMat< IU, NUM, UDER > &A, int rowneighs, OptBuf< int32_t, OVT > &optbuf, int32_t &indacc, IVT &numacc, int32_t &sendindbuf, OVT &sendnumbuf, int &sdispls, int sendcnt, int accnz, bool indexisvalue)
template<typename SR , typename IU , typename OVT >
void	MergeContributions (FullyDistSpVec< IU, OVT > &y, int &recvcnt, int &rdispls, int32_t &recvindbuf, OVT &recvnumbuf, int rowneighs)
template<typename SR , typename IVT , typename OVT , typename IU , typename NUM , typename UDER >
void	SpMV (const SpParMat< IU, NUM, UDER > &A, const FullyDistSpVec< IU, IVT > &x, FullyDistSpVec< IU, OVT > &y, bool indexisvalue, OptBuf< int32_t, OVT > &optbuf)
template<typename SR , typename IVT , typename OVT , typename IU , typename NUM , typename UDER >
void	SpMV (const SpParMat< IU, NUM, UDER > &A, const FullyDistSpVec< IU, IVT > &x, FullyDistSpVec< IU, OVT > &y, bool indexisvalue)
template<typename SR , typename IU , typename NUM , typename NUV , typename UDER >
FullyDistVec< IU, typename promote_trait< NUM, NUV > ::T_promote >	SpMV (const SpParMat< IU, NUM, UDER > &A, const FullyDistVec< IU, NUV > &x)
template<typename SR , typename IU , typename NUM , typename NUV , typename UDER >
FullyDistSpVec< IU, typename promote_trait< NUM, NUV > ::T_promote >	SpMV (const SpParMat< IU, NUM, UDER > &A, const FullyDistSpVec< IU, NUV > &x)
template<typename IU , typename NU1 , typename NU2 , typename UDERA , typename UDERB >
SpParMat< IU, typename promote_trait< NU1, NU2 > ::T_promote, typename promote_trait< UDERA, UDERB > ::T_promote >	EWiseMult (const SpParMat< IU, NU1, UDERA > &A, const SpParMat< IU, NU2, UDERB > &B, bool exclude)
template<typename RETT , typename RETDER , typename IU , typename NU1 , typename NU2 , typename UDERA , typename UDERB , typename _BinaryOperation >
SpParMat< IU, RETT, RETDER >	EWiseApply (const SpParMat< IU, NU1, UDERA > &A, const SpParMat< IU, NU2, UDERB > &B, _BinaryOperation __binary_op, bool notB, const NU2 &defaultBVal)
template<typename RETT , typename RETDER , typename IU , typename NU1 , typename NU2 , typename UDERA , typename UDERB , typename _BinaryOperation , typename _BinaryPredicate >
SpParMat< IU, RETT, RETDER >	EWiseApply (const SpParMat< IU, NU1, UDERA > &A, const SpParMat< IU, NU2, UDERB > &B, _BinaryOperation __binary_op, _BinaryPredicate do_op, bool allowANulls, bool allowBNulls, const NU1 &ANullVal, const NU2 &BNullVal, const bool allowIntersect, const bool useExtendedBinOp)
template<typename RETT , typename RETDER , typename IU , typename NU1 , typename NU2 , typename UDERA , typename UDERB , typename _BinaryOperation , typename _BinaryPredicate >
SpParMat< IU, RETT, RETDER >	EWiseApply (const SpParMat< IU, NU1, UDERA > &A, const SpParMat< IU, NU2, UDERB > &B, _BinaryOperation __binary_op, _BinaryPredicate do_op, bool allowANulls, bool allowBNulls, const NU1 &ANullVal, const NU2 &BNullVal, const bool allowIntersect=true)
template<typename IU , typename NU1 , typename NU2 >
SpParVec< IU, typename promote_trait< NU1, NU2 > ::T_promote >	EWiseMult (const SpParVec< IU, NU1 > &V, const DenseParVec< IU, NU2 > &W, bool exclude, NU2 zero)
template<typename IU , typename NU1 , typename NU2 >
FullyDistSpVec< IU, typename promote_trait< NU1, NU2 > ::T_promote >	EWiseMult (const FullyDistSpVec< IU, NU1 > &V, const FullyDistVec< IU, NU2 > &W, bool exclude, NU2 zero)
template<typename RET , typename IU , typename NU1 , typename NU2 , typename _BinaryOperation , typename _BinaryPredicate >
FullyDistSpVec< IU, RET >	EWiseApply (const FullyDistSpVec< IU, NU1 > &V, const FullyDistVec< IU, NU2 > &W, _BinaryOperation _binary_op, _BinaryPredicate _doOp, bool allowVNulls, NU1 Vzero, const bool useExtendedBinOp)
template<typename RET , typename IU , typename NU1 , typename NU2 , typename _BinaryOperation , typename _BinaryPredicate >
FullyDistSpVec< IU, RET >	EWiseApply (const FullyDistSpVec< IU, NU1 > &V, const FullyDistSpVec< IU, NU2 > &W, _BinaryOperation _binary_op, _BinaryPredicate _doOp, bool allowVNulls, bool allowWNulls, NU1 Vzero, NU2 Wzero, const bool allowIntersect, const bool useExtendedBinOp)
template<typename RET , typename IU , typename NU1 , typename NU2 , typename _BinaryOperation , typename _BinaryPredicate >
FullyDistSpVec< IU, RET >	EWiseApply (const FullyDistSpVec< IU, NU1 > &V, const FullyDistVec< IU, NU2 > &W, _BinaryOperation _binary_op, _BinaryPredicate _doOp, bool allowVNulls, NU1 Vzero)
template<typename RET , typename IU , typename NU1 , typename NU2 , typename _BinaryOperation , typename _BinaryPredicate >
FullyDistSpVec< IU, RET >	EWiseApply (const FullyDistSpVec< IU, NU1 > &V, const FullyDistSpVec< IU, NU2 > &W, _BinaryOperation _binary_op, _BinaryPredicate _doOp, bool allowVNulls, bool allowWNulls, NU1 Vzero, NU2 Wzero, const bool allowIntersect=true)

Function Documentation

template<typename IU , typename NV >

void AllGatherVector	(	MPI_Comm &	ColWorld,
		int	trxlocnz,
		IU	lenuntil,
		int32_t *&	trxinds,
		NV *&	trxnums,
		int32_t *&	indacc,
		NV *&	numacc,
		int &	accnz,
		bool	indexisvalue
	)

Step 2 of the sparse SpMV algorithm

Parameters:

[in,out]	trxinds,trxnums	{ deallocated }
[in,out]	indacc,numacc	{ allocated }
[in,out]	accnz	{ set }
[in]	trxlocnz,lenuntil,indexisvalue

Definition at line 511 of file ParFriends.h.

template<typename MATRIXA , typename MATRIXB >

bool CheckSpGEMMCompliance	(	const MATRIXA &	A,
		const MATRIXB &	B
	)

Definition at line 128 of file ParFriends.h.

template<typename MATRIX , typename VECTOR >

void CheckSpMVCompliance	(	const MATRIX &	A,
		const VECTOR &	x
	)

Definition at line 438 of file ParFriends.h.

template<typename IT , typename NT >

FullyDistVec<IT,NT> Concatenate ( vector< FullyDistVec< IT, NT > > & vecs )

Concatenate all the FullyDistVec<IT,NT> objects into a single one

Definition at line 28 of file ParFriends.h.

template<typename RETT , typename RETDER , typename IU , typename NU1 , typename NU2 , typename UDERA , typename UDERB , typename _BinaryOperation >

SpParMat<IU,RETT,RETDER> EWiseApply	(	const SpParMat< IU, NU1, UDERA > &	A,
		const SpParMat< IU, NU2, UDERB > &	B,
		_BinaryOperation	__binary_op,
		bool	notB,
		const NU2 &	defaultBVal
	)

Definition at line 1080 of file ParFriends.h.

template<typename RETT , typename RETDER , typename IU , typename NU1 , typename NU2 , typename UDERA , typename UDERB , typename _BinaryOperation , typename _BinaryPredicate >

SpParMat<IU,RETT,RETDER> EWiseApply	(	const SpParMat< IU, NU1, UDERA > &	A,
		const SpParMat< IU, NU2, UDERB > &	B,
		_BinaryOperation	__binary_op,
		_BinaryPredicate	do_op,
		bool	allowANulls,
		bool	allowBNulls,
		const NU1 &	ANullVal,
		const NU2 &	BNullVal,
		const bool	allowIntersect,
		const bool	useExtendedBinOp
	)

Definition at line 1097 of file ParFriends.h.

template<typename RETT , typename RETDER , typename IU , typename NU1 , typename NU2 , typename UDERA , typename UDERB , typename _BinaryOperation , typename _BinaryPredicate >

SpParMat<IU,RETT,RETDER> EWiseApply	(	const SpParMat< IU, NU1, UDERA > &	A,
		const SpParMat< IU, NU2, UDERB > &	B,
		_BinaryOperation	__binary_op,
		_BinaryPredicate	do_op,
		bool	allowANulls,
		bool	allowBNulls,
		const NU1 &	ANullVal,
		const NU2 &	BNullVal,
		const bool	allowIntersect = `true`
	)

Definition at line 1115 of file ParFriends.h.

template<typename RET , typename IU , typename NU1 , typename NU2 , typename _BinaryOperation , typename _BinaryPredicate >

FullyDistSpVec<IU,RET> EWiseApply	(	const FullyDistSpVec< IU, NU1 > &	V,
		const FullyDistVec< IU, NU2 > &	W,
		_BinaryOperation	_binary_op,
		_BinaryPredicate	_doOp,
		bool	allowVNulls,
		NU1	Vzero,
		const bool	useExtendedBinOp
	)

Performs an arbitrary binary operation _binary_op on the corresponding elements of two vectors with the result stored in a return vector ret. The binary operatiation is only performed if the binary predicate _doOp returns true for those elements. Otherwise the binary operation is not performed and ret does not contain an element at that position. More formally the operation is defined as: if (_doOp(V[i], W[i])) ret[i] = _binary_op(V[i], W[i]) else // ret[i] is not set Hence _doOp can be used to implement a filter on either of the vectors.

The above is only defined if both V[i] and W[i] exist (i.e. an intersection). To allow a union operation (ex. when V[i] doesn't exist but W[i] does) the allowVNulls flag is set to true and the Vzero argument is used as the missing V[i] value.

The type of each element of ret must not necessarily be related to the types of V or W, so the return type must be explicitly specified as a template parameter: FullyDistSpVec<int, double> r = EWiseApply<double>(V, W, plus, retTrue, false, 0)

Definition at line 1285 of file ParFriends.h.

template<typename RET , typename IU , typename NU1 , typename NU2 , typename _BinaryOperation , typename _BinaryPredicate >

FullyDistSpVec<IU,RET> EWiseApply	(	const FullyDistSpVec< IU, NU1 > &	V,
		const FullyDistSpVec< IU, NU2 > &	W,
		_BinaryOperation	_binary_op,
		_BinaryPredicate	_doOp,
		bool	allowVNulls,
		bool	allowWNulls,
		NU1	Vzero,
		NU2	Wzero,
		const bool	allowIntersect,
		const bool	useExtendedBinOp
	)

Performs an arbitrary binary operation _binary_op on the corresponding elements of two vectors with the result stored in a return vector ret. The binary operatiation is only performed if the binary predicate _doOp returns true for those elements. Otherwise the binary operation is not performed and ret does not contain an element at that position. More formally the operation is defined as: if (_doOp(V[i], W[i])) ret[i] = _binary_op(V[i], W[i]) else // ret[i] is not set Hence _doOp can be used to implement a filter on either of the vectors.

The above is only defined if both V[i] and W[i] exist (i.e. an intersection). To allow a union operation (ex. when V[i] doesn't exist but W[i] does) the allowVNulls flag is set to true and the Vzero argument is used as the missing V[i] value. !allowVNulls && !allowWNulls => intersection !allowVNulls && allowWNulls => operate on all elements of V allowVNulls && !allowWNulls => operate on all elements of W allowVNulls && allowWNulls => union

The type of each element of ret must not necessarily be related to the types of V or W, so the return type must be explicitly specified as a template parameter: FullyDistSpVec<int, double> r = EWiseApply<double>(V, W, plus, retTrue, false, 0, false, 0)

Definition at line 1375 of file ParFriends.h.

template<typename RET , typename IU , typename NU1 , typename NU2 , typename _BinaryOperation , typename _BinaryPredicate >

FullyDistSpVec<IU,RET> EWiseApply	(	const FullyDistSpVec< IU, NU1 > &	V,
		const FullyDistVec< IU, NU2 > &	W,
		_BinaryOperation	_binary_op,
		_BinaryPredicate	_doOp,
		bool	allowVNulls,
		NU1	Vzero
	)

Definition at line 1472 of file ParFriends.h.

template<typename RET , typename IU , typename NU1 , typename NU2 , typename _BinaryOperation , typename _BinaryPredicate >

FullyDistSpVec<IU,RET> EWiseApply	(	const FullyDistSpVec< IU, NU1 > &	V,
		const FullyDistSpVec< IU, NU2 > &	W,
		_BinaryOperation	_binary_op,
		_BinaryPredicate	_doOp,
		bool	allowVNulls,
		bool	allowWNulls,
		NU1	Vzero,
		NU2	Wzero,
		const bool	allowIntersect = `true`
	)

Definition at line 1482 of file ParFriends.h.

template<typename IU , typename NU1 , typename NU2 , typename UDERA , typename UDERB >

SpParMat<IU,typename promote_trait<NU1,NU2>::T_promote,typename promote_trait<UDERA,UDERB>::T_promote> EWiseMult	(	const SpParMat< IU, NU1, UDERA > &	A,
		const SpParMat< IU, NU2, UDERB > &	B,
		bool	exclude
	)

Definition at line 1060 of file ParFriends.h.

template<typename IU , typename NU1 , typename NU2 >

SpParVec<IU,typename promote_trait<NU1,NU2>::T_promote> EWiseMult	(	const SpParVec< IU, NU1 > &	V,
		const DenseParVec< IU, NU2 > &	W,
		bool	exclude,
		NU2	zero
	)

if exclude is true, then we prune all entries W[i] != zero from V if exclude is false, then we perform a proper elementwise multiplication

Definition at line 1131 of file ParFriends.h.

template<typename IU , typename NU1 , typename NU2 >

FullyDistSpVec<IU,typename promote_trait<NU1,NU2>::T_promote> EWiseMult	(	const FullyDistSpVec< IU, NU1 > &	V,
		const FullyDistVec< IU, NU2 > &	W,
		bool	exclude,
		NU2	zero
	)

if exclude is true, then we prune all entries W[i] != zero from V if exclude is false, then we perform a proper elementwise multiplication

Definition at line 1182 of file ParFriends.h.

template<typename SR , typename IVT , typename OVT , typename IU , typename NUM , typename UDER >

void LocalSpMV	(	const SpParMat< IU, NUM, UDER > &	A,
		int	rowneighs,
		OptBuf< int32_t, OVT > &	optbuf,
		int32_t *&	indacc,
		IVT *&	numacc,
		int32_t *&	sendindbuf,
		OVT *&	sendnumbuf,
		int *&	sdispls,
		int *	sendcnt,
		int	accnz,
		bool	indexisvalue
	)

Step 3 of the sparse SpMV algorithm, with the semiring

Parameters:

[in,out]	optbuf	{scratch space for all-to-all (fold) communication}
[in,out]	indacc,numacc	{index and values of the input vector, deleted upon exit}
[in,out]	sendindbuf,sendnumbuf	{index and values of the output vector, created}

Definition at line 570 of file ParFriends.h.

template<typename SR , typename IU , typename OVT >

void MergeContributions	(	FullyDistSpVec< IU, OVT > &	y,
		int *&	recvcnt,
		int *&	rdispls,
		int32_t *&	recvindbuf,
		OVT *&	recvnumbuf,
		int	rowneighs
	)

Definition at line 631 of file ParFriends.h.

template<typename SR , typename NUO , typename UDERO , typename IU , typename NU1 , typename NU2 , typename UDERA , typename UDERB >

SpParMat<IU,NUO,UDERO> Mult_AnXBn_DoubleBuff	(	SpParMat< IU, NU1, UDERA > &	A,
		SpParMat< IU, NU2, UDERB > &	B,
		bool	clearA = `false`,
		bool	clearB = `false`
	)

Parallel C = A*B routine that uses a double buffered broadcasting scheme

Precondition:: { Input matrices, A and B, should not alias } Most memory efficient version available. Total stages: 2*sqrt(p) Memory requirement during first sqrt(p) stages: <= (3/2)*(nnz(A)+nnz(B))+(1/2)*nnz(C) Memory requirement during second sqrt(p) stages: <= nnz(A)+nnz(B)+nnz(C) Final memory requirement: nnz(C) if clearA and clearB are true

Definition at line 161 of file ParFriends.h.

template<typename SR , typename NUO , typename UDERO , typename IU , typename NU1 , typename NU2 , typename UDERA , typename UDERB >

SpParMat<IU, NUO, UDERO> Mult_AnXBn_Synch	(	SpParMat< IU, NU1, UDERA > &	A,
		SpParMat< IU, NU2, UDERB > &	B,
		bool	clearA = `false`,
		bool	clearB = `false`
	)

Parallel A = B*C routine that uses only MPI-1 features Relies on simple blocking broadcast

Precondition:: { Input matrices, A and B, should not alias }

Definition at line 333 of file ParFriends.h.

template<typename SR , typename IU , typename NUM , typename UDER >

FullyDistSpVec< IU, typename promote_trait< NUM, IU >::T_promote > SpMV	(	const SpParMat< IU, NUM, UDER > &	A,
		const FullyDistSpVec< IU, IU > &	x,
		bool	indexisvalue,
		OptBuf< int32_t, typename promote_trait< NUM, IU >::T_promote > &	optbuf
	)

Automatic type promotion is ONLY done here, all the callee functions (in Friends.h and below) are initialized with the promoted type If indexisvalues = true, then we do not need to transfer values for x (happens for BFS iterations with boolean matrices and integer rhs vectors)

Definition at line 826 of file ParFriends.h.

template<typename SR , typename IU , typename NUM , typename UDER >

FullyDistSpVec<IU,typename promote_trait<NUM,IU>::T_promote> SpMV	(	const SpParMat< IU, NUM, UDER > &	A,
		const FullyDistSpVec< IU, IU > &	x,
		bool	indexisvalue
	)

Definition at line 462 of file ParFriends.h.

template<typename SR , typename IVT , typename OVT , typename IU , typename NUM , typename UDER >

void SpMV	(	const SpParMat< IU, NUM, UDER > &	A,
		const FullyDistSpVec< IU, IVT > &	x,
		FullyDistSpVec< IU, OVT > &	y,
		bool	indexisvalue,
		OptBuf< int32_t, OVT > &	optbuf
	)

This version is the most flexible sparse matrix X sparse vector [Used in KDT] It accepts different types for the matrix (NUM), the input vector (IVT) and the output vector (OVT) without relying on automatic type promotion Input (x) and output (y) vectors can be ALIASED because y is not written until the algorithm is done with x.

Definition at line 728 of file ParFriends.h.

template<typename SR , typename IVT , typename OVT , typename IU , typename NUM , typename UDER >

void SpMV	(	const SpParMat< IU, NUM, UDER > &	A,
		const FullyDistSpVec< IU, IVT > &	x,
		FullyDistSpVec< IU, OVT > &	y,
		bool	indexisvalue
	)

Definition at line 813 of file ParFriends.h.

template<typename SR , typename IU , typename NUM , typename NUV , typename UDER >

FullyDistVec<IU,typename promote_trait<NUM,NUV>::T_promote> SpMV	(	const SpParMat< IU, NUM, UDER > &	A,
		const FullyDistVec< IU, NUV > &	x
	)

Parallel dense SpMV

Definition at line 839 of file ParFriends.h.

template<typename SR , typename IU , typename NUM , typename NUV , typename UDER >

FullyDistSpVec<IU,typename promote_trait<NUM,NUV>::T_promote> SpMV	(	const SpParMat< IU, NUM, UDER > &	A,
		const FullyDistSpVec< IU, NUV > &	x
	)

Old version that is no longer considered optimal Kept for legacy purposes To be removed when other functionals are fully tested.

Definition at line 913 of file ParFriends.h.

template<typename IU , typename NV >

void TransposeVector	(	MPI_Comm &	World,
		const FullyDistSpVec< IU, NV > &	x,
		int32_t &	trxlocnz,
		IU &	lenuntil,
		int32_t *&	trxinds,
		NV *&	trxnums,
		bool	indexisvalue
	)

Step 1 of the sparse SpMV algorithm

Parameters:

[in,out]	trxlocnz,lenuntil,trxinds,trxnums	{ set or allocated }
[in]	indexisvalue

Definition at line 475 of file ParFriends.h.

Functions

Function Documentation