par::step Namespace Reference

This contains everything grouping together bulk communication in one (or few) supersteps. More...


Classes

class  array
 This class represents a distributed array. More...
class  boolPredicate
class  bulk
 Bulk communication from a source array to a target array. More...
class  bulk_generic
 The shared code base of the par::step::bulk template classes. More...
class  compPredicate
class  Context
 Generate graphs via a generalized attachment model. More...
class  contract_pair_extr
 Extraction class to construct the predecessors of a list. More...
struct  copy_error
class  dlist
 A distributed list of items. More...
class  extract_commat
 Extraction class to identify the target process according to the position of the data. More...
class  extract_indjump
 extraction class needed in par::step::forest::findroot and defivatives. More...
class  extract_indjump_dist
 Internal class for par::step::vforest::indjump. More...
class  extract_over_parent
 An extraction classes to shortcut a list needed in par::step::list< val_t >::ranking and to send the successors to the predecessors. More...
class  extract_over_pred
 Extraction class for par::step::list< val_t >::ranking to send the predecessors to the successors. More...
class  extract_proc
 Extraction class to identify the target process according to the contents of the data. More...
class  extract_proc_generic
 The common implementation core for the template par::step::extract_proc. More...
class  forest
 A class that implements a distributed forest of items. More...
class  generic_extraction
 a generic type from which all extraction types for par::step::bulk should inherit. More...
class  index_range
 The necessary control structure for indices of distributed arrays. More...
class  index_set
 Represents a set of indices. More...
class  iterator
 This implements two classes of iterators over index ranges. More...
class  list
 A distributed list of items. More...
struct  over_mess_parent
struct  over_mess_pred
struct  over_message_parent
struct  over_message_pred
class  over_parent
 An extraction classes to shortcut a list needed in par::step::dlist::findroot and to send the successors to the predecessors. More...
class  over_pred
 Extraction class for par::step::dlist::findroot to send the predecessors to the successors. More...
class  pair_extr
 Specialized extraction class for the generation of random lists. More...
class  query_reply
 This implements an extension of bulk that allows to imediately send back as much information as one receives. More...
class  sorting
 Template wrapper for a parallel sort based on different sequential sort algorithms. More...
class  sorting_extraction
 The special extraction type for sorting. More...
class  subiterator
class  symmetric_extraction
class  vforest
 A class that implements a distributed valuated forest of items. More...
class  voidPredicate

Typedefs

typedef unsigned char indstate

Enumerations

enum  { indactive, indleaf, indfinished, indroot }

Functions

void BidirectEdges (array< cpp::edge< 2 > > &E)
 For each edge (a,b) in E add the opposite edge (b,a).
void BidirectEdges (mem::chunk< cpp::edge< 2 > > &E)
void BidirectEdges (chunk< edge< 2 > > &E)
template<unsigned dim, unsigned where>
void degree (array< size_t > &deg, array< cpp::edge< dim > >const &arr)
 Compute the `where' degree for each vertex.
template void degree< 2, 0 > (array< size_t > &deg, array< cpp::edge< 2 > >const &arr)
template void degree< 2, 2-1 > (array< size_t > &deg, array< cpp::edge< 2 > >const &arr)
template void degree< 3, 0 > (array< size_t > &deg, array< cpp::edge< 3 > >const &arr)
template void degree< 3, 3-1 > (array< size_t > &deg, array< cpp::edge< 3 > >const &arr)
template void degree< 4, 0 > (array< size_t > &deg, array< cpp::edge< 4 > >const &arr)
template void degree< 4, 4-1 > (array< size_t > &deg, array< cpp::edge< 4 > >const &arr)
template void degree< 5, 0 > (array< size_t > &deg, array< cpp::edge< 5 > >const &arr)
template void degree< 5, 5-1 > (array< size_t > &deg, array< cpp::edge< 5 > >const &arr)
template void degree< 6, 0 > (array< size_t > &deg, array< cpp::edge< 6 > >const &arr)
template void degree< 6, 6-1 > (array< size_t > &deg, array< cpp::edge< 6 > >const &arr)
template void degree< 7, 0 > (array< size_t > &deg, array< cpp::edge< 7 > >const &arr)
template void degree< 7, 7-1 > (array< size_t > &deg, array< cpp::edge< 7 > >const &arr)
template void degree< 8, 0 > (array< size_t > &deg, array< cpp::edge< 8 > >const &arr)
template void degree< 8, 8-1 > (array< size_t > &deg, array< cpp::edge< 8 > >const &arr)
size_t eContract (mem::chunk< cpp::edge< 2 > > &EdgesC, mem::chunk< off_t > &namesC)
 Contract a series of edges (one per vertex) in Edges and return the mapping in names.
int fclose (FILE *os)
 Close a set of streams as obtained by par::step::fopen or par::step::fdopen.
FILE * fdopen (int fd, char const *mode)
 Open a set of streams, one for each parXXL process.
int fflush (FILE *os)
 Flush a set of streams as obtained from par::step::fopen or par::step::fdopen.
FILE * fopen (char const *name, char const *mode)
 Open a set of files, one for each parXXL process.
FILE * freopen (char const *name, char const *mode, FILE *stream)
template<>
void generate (array< ulong > &C, par::sys::seed_t &seed, unsigned twist)
template<>
void generate (array< long > &C, par::sys::seed_t &seed, unsigned twist)
template<>
void generate (array< unsigned > &C, par::sys::seed_t &seed, unsigned twist)
template<>
void generate (array< signed > &C, par::sys::seed_t &seed, unsigned twist)
template<>
void generate (array< ushort > &C, par::sys::seed_t &seed, unsigned twist)
template<>
void generate (array< short > &C, par::sys::seed_t &seed, unsigned twist)
template<>
void generate (array< uchar > &C, par::sys::seed_t &seed, unsigned twist)
template<>
void generate (array< schar > &C, par::sys::seed_t &seed, unsigned twist)
template<class T >
void generate (array< T > &C, par::sys::seed_t &seed, unsigned twist)
template<class T >
void generate (array< T > &C, unsigned twist)
template<class T >
void generate (array< T > &C, par::sys::seed_t &seed)
template<class T >
void generate (array< T > &C)
 Generate an integer random permutation in place.
template<class S , class E >
par::cntrl::proc_t identification (E *restrict tthis, off_t const i, S const &d, off_t const nb, par::cntrl::proc_t *restrict ids)
 For par::step::bulk communcations where one item in the source par::step::array could go to several other parXXL processes and not only a single one.
template<>
par::cntrl::proc_t identification< off_t, over_parent > (over_parent *tthis, off_t const i, off_t const &d, off_t const nb, par::cntrl::proc_t *ids)
template<>
par::cntrl::proc_t identification< off_t, over_pred > (over_pred *tthis, off_t const i, off_t const &d, off_t const nb, par::cntrl::proc_t *ids)
template<unsigned dim>
void indegree (array< size_t > &deg, array< cpp::edge< dim > >const &arr)
template void indegree< 2 > (array< size_t > &deg, array< edge< 2 > >const &arr)
template void indegree< 3 > (array< size_t > &deg, array< edge< 3 > >const &arr)
template void indegree< 4 > (array< size_t > &deg, array< edge< 4 > >const &arr)
template void indegree< 5 > (array< size_t > &deg, array< edge< 5 > >const &arr)
template void indegree< 6 > (array< size_t > &deg, array< edge< 6 > >const &arr)
template void indegree< 7 > (array< size_t > &deg, array< edge< 7 > >const &arr)
template void indegree< 8 > (array< size_t > &deg, array< edge< 8 > >const &arr)
FILE * operator<< (FILE *os, subiterator &i)
template<unsigned dim>
void outdegree (array< size_t > &deg, array< cpp::edge< dim > >const &arr)
template void outdegree< 2 > (array< size_t > &deg, array< edge< 2 > >const &arr)
template void outdegree< 3 > (array< size_t > &deg, array< edge< 3 > >const &arr)
template void outdegree< 4 > (array< size_t > &deg, array< edge< 4 > >const &arr)
template void outdegree< 5 > (array< size_t > &deg, array< edge< 5 > >const &arr)
template void outdegree< 6 > (array< size_t > &deg, array< edge< 6 > >const &arr)
template void outdegree< 7 > (array< size_t > &deg, array< edge< 7 > >const &arr)
template void outdegree< 8 > (array< size_t > &deg, array< edge< 8 > >const &arr)
off_t page_floor (off_t size, off_t mn)
template<class T >
void permute (array< T > &A, par::sys::seed_t &seed)
template<class T >
void permute (array< T > &A)
 Randomly permute a par::step::array.
template<class T , class assignOp >
void prefixOp (par::step::array< T > &ar)
template<class T >
void qsort (array< T > &Tp, array< T const > &Tl, sys::str targetURL)
 Template wrapper for a parallel sort based on qsort.
template<class T >
void qsort (array< T > *&Tp, sys::str targetURL, bool destroy=false)
template<class T >
void qsort (array< T > &Tp, sys::str targetURL, bool destroy=false)
 Template wrapper for a parallel sort based on qsort.
template<class T >
void quicksort (array< T > &Tp, array< T const > &Tl)
template<class T >
void quicksort (array< T > &Tp, array< T const > &Tl, sys::str targetURL)
template<class T >
void quicksort (array< T > *&Tp, bool destroy=false)
template<class T >
void quicksort (array< T > *&Tp, sys::str targetURL, bool destroy=false)
template<class T >
void quicksort (array< T > &Tp, bool destroy=false)
template<class T >
void quicksort (array< T > &Tp, sys::str targetURL, bool destroy=false)
 Template wrapper for a parallel sort based on par::sys::quicksort.
void read_dot (array< cpp::edge< 2 > > &E, char const *name)
 Read an edge array in parallel.
template<class T , class assignOp >
void scalarOp (T &restrict a, array< T const > &chu)
 Apply assignOp to a whole par::step::array.
template<class T , PAR_SYS_SORT_F(T) const seqsort>
void sort (array< T > *&Tp, bool destroy=false)
template<class T , PAR_SYS_SORT_F(T) const seqsort>
void sort (array< T > *&Tp, sys::str targetURL, bool destroy=false)
template<class T , PAR_SYS_SORT_F(T) const seqsort>
void sort (array< T > &Tt, array< T const > &Ts)
template<class T , PAR_SYS_SORT_F(T) const seqsort>
void sort (array< T > &Tt, array< T const > &Ts, sys::str targetURL)
template<class T , PAR_SYS_SORT_F(T) const seqsort>
void sort (array< T > &Tp, bool destroy=false)
template<class T , PAR_SYS_SORT_F(T) const seqsort>
void sort (array< T > &Tp, sys::str targetURL, bool destroy=false)
template<unsigned d>
size_t SortEdges (array< cpp::edge< d > > &E, bool unify)
 Sort an array of edges lexicographically.
template<unsigned d>
size_t SortEdges (mem::chunk< cpp::edge< d > > &E, bool unify)
template<typename T >
mem::chunk< T[2] > valueDistr (array< T const >const &values)
 Compute the distribution of the occurring values in values.
template<typename T >
mem::chunk< T[2] > valueDistr (mem::chunk< T const >const &deg)
double vClustering (sys::seed_t &seed, array< cpp::edge< 2 >const > const &E, size_t &iter)
 Estimate the clustering coefficient of graph E.
double vClustering (sys::seed_t &seed, mem::chunk< cpp::edge< 2 >const > const &E, size_t &iter)
double vClustering (seed_t &seed, array< edge< 2 >const > const &Ereal, size_t &tried)
mem::chunk< off_tvComponents (mem::chunk< cpp::edge< 2 >const > &EdgesC)
 Contract all Edges and return the obtained vertex.
template<unsigned d>
size_t vContract (mem::chunk< cpp::edge< d > > &Edges, array< off_t const > const &names)
 Identify all vertices in graph Edges as indicated by names.
template<unsigned d>
size_t vContract (mem::chunk< cpp::edge< d > > &Edges, mem::chunk< off_t const > const &names)
mem::chunk< size_tvDegree (array< size_t const > const &offs, size_t global)
 Obtain the degree for all items from an offset array offs.
template<unsigned d>
mem::chunk< size_tvDegree (array< cpp::edge< d > const > const &Edges)
 Obtain the outdegree (degree in position 0) for all vertices.
mem::chunk< size_tvDegree (mem::chunk< size_t const > const &offs, size_t global)
template<unsigned d>
mem::chunk< size_tvDegree (mem::chunk< cpp::edge< d > const > const &Edges)
mem::chunk< size_t[2] > vDegreeDistr (mem::chunk< cpp::edge< 2 > > &E)
mem::chunk< size_t[2] > vDegreeDistr (array< cpp::edge< 2 > const > const &Edges)
 Compute the degree distribution of graph Edges.
mem::chunk< size_t[2] > vDegreeDistr (mem::chunk< cpp::edge< 2 > const > const &Edges)
template<class T , class assignOp >
void vectorOp (array< T > &chu, array< T const > &cho)
template<unsigned d, unsigned twist, typename T >
void vMix (sys::seed_t &seed, cpp::edge< d > *Ep, size_t len, T numvert)
template<unsigned d>
void vMix (sys::seed_t &seed, mem::chunk< cpp::edge< d > > &Edges)
template<unsigned d>
mem::chunk< size_tvOffset (array< cpp::edge< d > const > const &Edges)
 Obtain the global offset of the edge list for all vertices.
template<unsigned d>
mem::chunk< size_tvOffset (mem::chunk< cpp::edge< d > const > const &Edges)
template<unsigned d>
void vRename (mem::chunk< cpp::edge< d > > &Edges, array< off_t const > const &names)
 Rename the vertices of graph Edges according to names.
template<unsigned d>
void vRename (mem::chunk< cpp::edge< d > > &Edges, mem::chunk< off_t const > const &names)
void write_dot (char const *name, array< par::cpp::edge< 2 > > const &E, bool directed=true, char const *spec=NULL)


Detailed Description

This contains everything grouping together bulk communication in one (or few) supersteps.


Typedef Documentation

typedef unsigned char par::step::indstate

Definition at line 33 of file par_step_forest_extract_indjump.h.


Enumeration Type Documentation

anonymous enum

Enumerator:
indactive 
indleaf 
indfinished 
indroot 

Definition at line 35 of file par_step_forest_extract_indjump.h.


Function Documentation

void par::step::BidirectEdges ( chunk< edge< 2 > > &  E  ) 

Definition at line 103 of file par_step_graph.cc.

template<unsigned dim, unsigned where>
void par::step::degree ( array< size_t > &  deg,
array< cpp::edge< dim > >const &  arr 
) [inline]

Compute the `where' degree for each vertex.

In particulare if dim is 2, where=0 corresponds to the outdegree and 1 to the indgree of a vertex.

template void par::step::degree< 2, 0 > ( array< size_t > &  deg,
array< cpp::edge< 2 > >const &  arr 
)

template void par::step::degree< 2, 2-1 > ( array< size_t > &  deg,
array< cpp::edge< 2 > >const &  arr 
)

template void par::step::degree< 3, 0 > ( array< size_t > &  deg,
array< cpp::edge< 3 > >const &  arr 
)

template void par::step::degree< 3, 3-1 > ( array< size_t > &  deg,
array< cpp::edge< 3 > >const &  arr 
)

template void par::step::degree< 4, 0 > ( array< size_t > &  deg,
array< cpp::edge< 4 > >const &  arr 
)

template void par::step::degree< 4, 4-1 > ( array< size_t > &  deg,
array< cpp::edge< 4 > >const &  arr 
)

template void par::step::degree< 5, 0 > ( array< size_t > &  deg,
array< cpp::edge< 5 > >const &  arr 
)

template void par::step::degree< 5, 5-1 > ( array< size_t > &  deg,
array< cpp::edge< 5 > >const &  arr 
)

template void par::step::degree< 6, 0 > ( array< size_t > &  deg,
array< cpp::edge< 6 > >const &  arr 
)

template void par::step::degree< 6, 6-1 > ( array< size_t > &  deg,
array< cpp::edge< 6 > >const &  arr 
)

template void par::step::degree< 7, 0 > ( array< size_t > &  deg,
array< cpp::edge< 7 > >const &  arr 
)

template void par::step::degree< 7, 7-1 > ( array< size_t > &  deg,
array< cpp::edge< 7 > >const &  arr 
)

template void par::step::degree< 8, 0 > ( array< size_t > &  deg,
array< cpp::edge< 8 > >const &  arr 
)

template void par::step::degree< 8, 8-1 > ( array< size_t > &  deg,
array< cpp::edge< 8 > >const &  arr 
)

int par::step::fclose ( FILE *  os  ) 

Close a set of streams as obtained by par::step::fopen or par::step::fdopen.

Beware that par::step::fclose is not called automatically at the end of a process. You have to do that by yourself, otherwise the data on processes different than 0 is lost.

As a special case, if os corresponds to one of the streams stdin and stderr are never effectively closed, but only par::step::fflush is called to ensure synchronization.

This function defines a strong synchronization point.

Definition at line 156 of file par_step_file.cc.

FILE * par::step::fdopen ( int  fd,
char const *  mode 
)

Open a set of streams, one for each parXXL process.

This behaves similar to par::step::fopen but for the extra care that has to be taken when interpreting fd as the number of an open file descriptor.

For process 0, the call does the same as fdopen, i.e opens a stream on file descriptor fd. This is in particular useful to write to stdout (fd == 1) or stderr (fd == 2). If fd is 0 or less the result is anologous to par::step::fopen with a filename of NULL.

For the other processes, if fd corresponds to a number > 0, an anonymous file is opened with fd as file descriptor. If previously fd was corresponding to an open file description this file descripion is closed as described for the second argument of dup2. If fd is 0 or less, a stream on an anonymous file is opened and the result is returned.

Definition at line 73 of file par_step_file.cc.

int par::step::fflush ( FILE *  os  ) 

Flush a set of streams as obtained from par::step::fopen or par::step::fdopen.

This functions collects all data that is written so far by the individual processes and appends it to the stream on process 0. The data is appended in the order of the process numbers.

If on process 0 the stream corresponds to a file, the file pointer is then set to the end of the enlarged file such that all subsequent data is written after the collected data. On processes different from 0 the file is then truncated to length 0.

This function defines a strong synchronization point.

Definition at line 84 of file par_step_file.cc.

FILE* par::step::fopen ( char const *  name,
char const *  mode 
) [inline]

Open a set of files, one for each parXXL process.

The rationale of this function is to collectively create and maintain a file amoung all parXXL processes. Every process writes into its own file and then all the data is collected together (in the order of process numbers) at each call to par::step::fflush or finally at par::step::fclose. So each individual write operation should be fast, since it is on an unshared file descriptor -- each flush or close operation should also be fast in the sense that it should mostly be constraint by bandwidth requirements if the programmer doesn't abuse it.

For process 0 this behaves as the system call fopen.

For all other processes name is replaced by some unique and non-existing filename, the corresponding file is opened as for fopen and then this file is immediately unlinked.

Arguments name and mode as well as error indications are the same as for fopen.

If name is NULL, the call does nothing for the caller (but the parXXL synchronization) and returns NULL. This means in particular that if name is NULL for process 0, all data will be lost after each call to par::step::fflush or par::step::fclose. All parXXL functions that work on FILE* should tollerate arguments that are NULL and do the best for it. If you use other functions such as fprintf you should always check the file pointer first.

Beware that par::step::fclose is not called automatically at the end of a process. You have to do that by yourself, otherwise the data on processes different than 0 is lost.

This function defines a strong synchronization point.

Definition at line 72 of file par_step_file.h.

FILE * par::step::freopen ( char const *  name,
char const *  mode,
FILE *  stream 
)

Definition at line 30 of file par_step_file.cc.

template<class S , class E >
par::cntrl::proc_t par::step::identification ( E *restrict  tthis,
off_t const   i,
S const &  d,
off_t const   nb,
par::cntrl::proc_t *restrict  ids 
) [inline]

For par::step::bulk communcations where one item in the source par::step::array could go to several other parXXL processes and not only a single one.

This here is in fact a template that will be used by parXXL if there is only an identify method for E,

See also:
par::step::generic_extraction::identify.
To implement your own method you should specialize this template, so put something like
 template<>
       inline
       par::cntrl::proc_t identification < S, E >
                  (E* tthis,
     off_t const i,
     S const& d,
     off_t const nb,
     par::cntrl::proc_t * ids){
 do_something_clever_here
 }
immediatly after the declaration of your class. As an example have a look at identification<list_type,extract_over_succ>().

Parameters:
tthis is a pointer to an instance of an extraction type
i same as for par::step::generic_extraction::identify.
d dito.
nb dito.
ids a table of target parXXL processes where this item goes. identification will be called with a length of ids that is at least the number of parXXL processes.
Returns:
This function must return the number of parXXL processes where this data item d has to be send to.

Definition at line 190 of file par_step_extraction.h.

template<>
par::cntrl::proc_t par::step::identification< off_t, over_parent > ( over_parent *  tthis,
off_t const   i,
off_t const &  d,
off_t const   nb,
par::cntrl::proc_t ids 
) [inline]

template<>
par::cntrl::proc_t par::step::identification< off_t, over_pred > ( over_pred *  tthis,
off_t const   i,
off_t const &  d,
off_t const   nb,
par::cntrl::proc_t ids 
) [inline]

template<unsigned dim>
void par::step::indegree ( array< size_t > &  deg,
array< cpp::edge< dim > >const &  arr 
) [inline]

template void par::step::indegree< 2 > ( array< size_t > &  deg,
array< edge< 2 > >const &  arr 
)

template void par::step::indegree< 3 > ( array< size_t > &  deg,
array< edge< 3 > >const &  arr 
)

template void par::step::indegree< 4 > ( array< size_t > &  deg,
array< edge< 4 > >const &  arr 
)

template void par::step::indegree< 5 > ( array< size_t > &  deg,
array< edge< 5 > >const &  arr 
)

template void par::step::indegree< 6 > ( array< size_t > &  deg,
array< edge< 6 > >const &  arr 
)

template void par::step::indegree< 7 > ( array< size_t > &  deg,
array< edge< 7 > >const &  arr 
)

template void par::step::indegree< 8 > ( array< size_t > &  deg,
array< edge< 8 > >const &  arr 
)

FILE * par::step::operator<< ( FILE *  os,
subiterator &  i 
)

Definition at line 92 of file par_step_iterator.cc.

template<unsigned dim>
void par::step::outdegree ( array< size_t > &  deg,
array< cpp::edge< dim > >const &  arr 
) [inline]

template void par::step::outdegree< 2 > ( array< size_t > &  deg,
array< edge< 2 > >const &  arr 
)

template void par::step::outdegree< 3 > ( array< size_t > &  deg,
array< edge< 3 > >const &  arr 
)

template void par::step::outdegree< 4 > ( array< size_t > &  deg,
array< edge< 4 > >const &  arr 
)

template void par::step::outdegree< 5 > ( array< size_t > &  deg,
array< edge< 5 > >const &  arr 
)

template void par::step::outdegree< 6 > ( array< size_t > &  deg,
array< edge< 6 > >const &  arr 
)

template void par::step::outdegree< 7 > ( array< size_t > &  deg,
array< edge< 7 > >const &  arr 
)

template void par::step::outdegree< 8 > ( array< size_t > &  deg,
array< edge< 8 > >const &  arr 
)

off_t par::step::page_floor ( off_t  size,
off_t  mn 
) [inline]

Definition at line 36 of file par_step_array.h.

void par::step::read_dot ( array< cpp::edge< 2 > > &  E,
char const *  name 
)

Read an edge array in parallel.

name should be an uri that points to the data. See par::mem::url_t for the possibilities.

Definition at line 24 of file par_step_edge.cc.

double par::step::vClustering ( seed_t &  seed,
array< edge< 2 >const > const &  Ereal,
size_t tried 
)

Definition at line 124 of file par_step_graph.cc.

void par::step::write_dot ( char const *  name,
array< par::cpp::edge< 2 > > const &  E,
bool  directed = true,
char const *  spec = NULL 
)

Definition at line 47 of file par_step_edge.cc.


Generated on Tue Oct 13 22:04:21 2009 for parXXL by  doxygen 1.5.8