DIY 3.0 data-parallel out-of-core C++ library

- Main Page
- Modules
- Namespaces
- Classes
- Files
- Examples

All Classes Namespaces Functions Typedefs Groups Pages
Functions
Algorithms

## Detailed Description

The following algorithms are included in DIY:

## Sort

A parallel sample sort that sorts values of each block and computes the boundaries in `samples`. Optionally, the results can be all_to_all distributed to everyone. A shorter version of the API with a default comparison function and the all_to_all exchange mandatory is also included. The sort uses the same k-ary global reduction as in the communication module.

See the example here.

## Kd-tree

A set of points initially distributed in a set of blocks can be redistributed in a kd-tree containing the same number of blocks. The number of blocks must be a power of 2, and the depth of the kd-tree will be log_2(num_blocks). The block boundaries are computed using a histogram; hence they are approximate to the bin width of the histogram. The number of histogram bins is user-supplied.

See the example here.

## Functions
template<class Block , class T , class Cmp >
void | diy::sort (Master &master, const Assigner &assigner, std::vector< T > Block::*values, std::vector< T > Block::*samples, size_t num_samples, const Cmp &cmp, int k=2, bool samples_only=false)
| sample sort `values` of each block, store the boundaries between blocks in `samples` More...
template<class Block , class T >
void | diy::sort (Master &master, const Assigner &assigner, std::vector< T > Block::*values, std::vector< T > Block::*samples, size_t num_samples, int k=2)
| sample sort `values` of each block, store the boundaries between blocks in `samples` shorter version of above sort algorithm with the default less-than comparator used for T and all_to_all exchange included More...
template<class Block , class Point >
void | diy::kdtree (Master &master, const Assigner &assigner, int dim, const ContinuousBounds &domain, std::vector< Point > Block::*points, size_t bins, bool wrap=false)
| build a kd-tree and sort a set of points into it (use histograms to determine split values) More...
template<class Block , class Point >
void | diy::kdtree_sampling (Master &master, const Assigner &assigner, int dim, const ContinuousBounds &domain, std::vector< Point > Block::*points, size_t samples, bool wrap=false)
| build a kd-tree and sort a set of points into it (use sampling to determine split values) More...

## Function Documentation

template<class Block , class Point >

void diy::kdtree | ( | Master & | master,
|  | const Assigner & | assigner,
|  | int | dim,
|  | const ContinuousBounds & | domain,
|  | std::vector< Point > Block::* | points,
|  | size_t | bins,
|  | bool | wrap = `false`
| ) |  |

build a kd-tree and sort a set of points into it (use histograms to determine split values)

Parameters

  master | master object
  assigner | assigner object
  dim | dimensionality
  domain | global data extents
  points | input points to sort into kd-tree
  bins | number of histogram bins for splitting a dimension
  wrap | periodic boundaries in all dimensions

Examples:
  reduce/kd-tree.cpp.

template<class Block , class Point >

void diy::kdtree_sampling | ( | Master & | master,
|  | const Assigner & | assigner,
|  | int | dim,
|  | const ContinuousBounds & | domain,
|  | std::vector< Point > Block::* | points,
|  | size_t | samples,
|  | bool | wrap = `false`
| ) |  |

build a kd-tree and sort a set of points into it (use sampling to determine split values)

Parameters

  master | master object
  assigner | assigner object
  dim | dimensionality
  domain | global data extents
  points | input points to sort into kd-tree
  samples | number of samples to take in each block
  wrap | periodic boundaries in all dimensions

Examples:
  reduce/kd-tree.cpp.

template<class Block , class T , class Cmp >

void diy::sort | ( | Master & | master,
|  | const Assigner & | assigner,
|  | std::vector< T > Block::* | values,
|  | std::vector< T > Block::* | samples,
|  | size_t | num_samples,
|  | const Cmp & | cmp,
|  | int | k = `2`,
|  | bool | samples_only = `false`
| ) |  |

sample sort `values` of each block, store the boundaries between blocks in `samples`

Parameters

  master | master object
  assigner | assigner object
  values | all values to sort
  samples | (output) boundaries of blocks
  num_samples | desired number of samples
  cmp | comparison function
  k | k-ary reduction will be used
  samples_only | false: results will be all_to_all exchanged; true: only sort but don't exchange results

Examples:
  reduce/sample-sort.cpp, and reduce/sort.cpp.

template<class Block , class T >

void diy::sort | ( | Master & | master,
|  | const Assigner & | assigner,
|  | std::vector< T > Block::* | values,
|  | std::vector< T > Block::* | samples,
|  | size_t | num_samples,
|  | int | k = `2`
| ) |  |

sample sort `values` of each block, store the boundaries between blocks in `samples` shorter version of above sort algorithm with the default less-than comparator used for T and all_to_all exchange included

Parameters

  master | master object
  assigner | assigner object
  values | all values to sort
  samples | (output) boundaries of blocks
  num_samples | desired number of samples
  k | k-ary reduction will be used