Detailed Description

This class represents a way to shard elements for multi-threading. The elements may be entries of a vector or the columns of a (column-major) matrix. The shards are selected to have roughly the same mass, where the mass of an entry depends on the constructor used. See the free functions below and in the .cc file for example usage.

Definition at line 34 of file sharder.h.

#include <sharder.h>

Classes
class	Shard

Public Types
using	ConstSparseColumnBlock
using	SparseColumnBlock

Public Member Functions
	Sharder (int64_t num_elements, int num_shards, Scheduler *scheduler, const std::function< int64_t(int64_t)> &element_mass)
	Sharder (int64_t num_elements, int num_shards, Scheduler *scheduler)
	Sharder (const Eigen::SparseMatrix< double, Eigen::ColMajor, int64_t > &matrix, int num_shards, Scheduler *scheduler)
	Sharder (const Sharder &other_sharder, int64_t num_elements)
	Sharder (const Sharder &other)=delete
Sharder &	operator= (const Sharder &other)=delete
	Sharder (Sharder &&other)=default
Sharder &	operator= (Sharder &&other)=default
int	NumShards () const
int64_t	NumElements () const
	The number of elements that are split into shards.
int64_t	ShardSize (int shard) const
int64_t	ShardStart (int shard) const
int64_t	ShardMass (int shard) const
void	ParallelForEachShard (const std::function< void(const Shard &)> &func) const
	Runs func on each of the shards.
double	ParallelSumOverShards (const std::function< double(const Shard &)> &func) const
	Runs func on each of the shards and sums the results.
bool	ParallelTrueForAllShards (const std::function< bool(const Shard &)> &func) const
const std::vector< int64_t > &	ShardStartsForTesting () const
	Public for testing only.

Member Typedef Documentation

◆ ConstSparseColumnBlock

using operations_research::pdlp::Sharder::ConstSparseColumnBlock

Initial value:

 ::Eigen::Block<
      const Eigen::SparseMatrix<double, Eigen::ColMajor, int64_t>,
      Eigen::Dynamic, Eigen::Dynamic,
      true>

These are public aliases for convenience. They will change only if there are breaking changes in Eigen.

Definition at line 38 of file sharder.h.

◆ SparseColumnBlock

using operations_research::pdlp::Sharder::SparseColumnBlock

Initial value:

 
      ::Eigen::Block<Eigen::SparseMatrix<double, Eigen::ColMajor, int64_t>,
                     Eigen::Dynamic, Eigen::Dynamic,
                     true>

Definition at line 42 of file sharder.h.

Constructor & Destructor Documentation

◆ Sharder() [1/6]

operations_research::pdlp::Sharder::Sharder	(	int64_t	num_elements,
		int	num_shards,
		Scheduler *	scheduler,
		const std::function< int64_t(int64_t)> &	element_mass )

Creates a Sharder for problems with num_elements elements and mass of each element given by element_mass. Each shard will have roughly the same mass. The number of shards in the resulting Sharder will be approximately num_shards but may differ. The scheduler will be used for parallel operations executed by e.g. ParallelForEachShard(). The scheduler may be nullptr, which means work will be executed in the same thread. If scheduler is not nullptr, the underlying object is not owned and must outlive the Sharder.

elem starts a new shard.

Definition at line 37 of file sharder.cc.

◆ Sharder() [2/6]

operations_research::pdlp::Sharder::Sharder	(	int64_t	num_elements,
		int	num_shards,
		Scheduler *	scheduler )

Creates a Sharder for problems with num_elements elements and unit mass. This constructor exploits having all element mass equal to 1 to take time proportional to num_shards instead of num_elements. Also see the comments above the first constructor.

Definition at line 73 of file sharder.cc.

◆ Sharder() [3/6]

operations_research::pdlp::Sharder::Sharder	(	const Eigen::SparseMatrix< double, Eigen::ColMajor, int64_t > &	matrix,
		int	num_shards,
		Scheduler *	scheduler )

inline

Creates a Sharder for processing matrix. The elements correspond to columns of matrix and have mass linear in the number of non-zeros. Also see the comments above the first constructor.

Definition at line 161 of file sharder.h.

◆ Sharder() [4/6]

operations_research::pdlp::Sharder::Sharder	(	const Sharder &	other_sharder,
		int64_t	num_elements )

Constructs a Sharder with the same scheduler as other_sharder, for problems with num_elements elements and unit mass. The number of shards will be approximately the same as that of other_sharder. Also see the comments on the first constructor.

The std::max() protects against other_sharder.NumShards() == 0, which will happen if other_sharder had num_elements == 0.

Definition at line 104 of file sharder.cc.

◆ Sharder() [5/6]

operations_research::pdlp::Sharder::Sharder ( const Sharder & other )

delete

Sharder may be moved, but not copied. Moved-from objects may be in an invalid state. The only methods that may be called on a moved-from object are the destructor or operator=.

◆ Sharder() [6/6]

operations_research::pdlp::Sharder::Sharder ( Sharder && other )

default

Member Function Documentation

◆ NumElements()

int64_t operations_research::pdlp::Sharder::NumElements ( ) const

inline

The number of elements that are split into shards.

Definition at line 184 of file sharder.h.

◆ NumShards()

int operations_research::pdlp::Sharder::NumShards ( ) const

inline

Definition at line 181 of file sharder.h.

◆ operator=() [1/2]

Sharder & operations_research::pdlp::Sharder::operator= ( const Sharder & other )

delete

◆ operator=() [2/2]

Sharder & operations_research::pdlp::Sharder::operator= ( Sharder && other )

default

◆ ParallelForEachShard()

void operations_research::pdlp::Sharder::ParallelForEachShard ( const std::function< void(const Shard &)> & func ) const

Runs func on each of the shards.

Definition at line 110 of file sharder.cc.

◆ ParallelSumOverShards()

double operations_research::pdlp::Sharder::ParallelSumOverShards ( const std::function< double(const Shard &)> & func ) const

Runs func on each of the shards and sums the results.

Definition at line 140 of file sharder.cc.

◆ ParallelTrueForAllShards()

bool operations_research::pdlp::Sharder::ParallelTrueForAllShards ( const std::function< bool(const Shard &)> & func ) const

Runs func on each of the shards. Returns true iff all shards returned true.

Recall std::vector<bool> is not thread-safe.

Definition at line 149 of file sharder.cc.

◆ ShardMass()

int64_t operations_research::pdlp::Sharder::ShardMass ( int shard ) const

inline

Definition at line 198 of file sharder.h.

◆ ShardSize()

int64_t operations_research::pdlp::Sharder::ShardSize ( int shard ) const

inline

Definition at line 186 of file sharder.h.

◆ ShardStart()

int64_t operations_research::pdlp::Sharder::ShardStart ( int shard ) const

inline

Definition at line 192 of file sharder.h.

◆ ShardStartsForTesting()

const std::vector< int64_t > & operations_research::pdlp::Sharder::ShardStartsForTesting ( ) const

inline

Public for testing only.

Definition at line 218 of file sharder.h.

The documentation for this class was generated from the following files:

ortools/pdlp/sharder.h
ortools/pdlp/sharder.cc

Detailed Description

Classes

Public Types

Public Member Functions

Member Typedef Documentation

◆ ConstSparseColumnBlock

◆ SparseColumnBlock

Constructor & Destructor Documentation

◆ Sharder() [1/6]

◆ Sharder() [2/6]

◆ Sharder() [3/6]

◆ Sharder() [4/6]

◆ Sharder() [5/6]

◆ Sharder() [6/6]

Member Function Documentation

◆ NumElements()

◆ NumShards()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ ParallelForEachShard()

◆ ParallelSumOverShards()

◆ ParallelTrueForAllShards()

◆ ShardMass()

◆ ShardSize()

◆ ShardStart()

◆ ShardStartsForTesting()