Galois Namespace Reference

Main Galois namespace. More...

Namespaces

namespace  AtomicImpl
namespace  Graph
 

Parallel graph data structures.


namespace  ParallelSTL
 

Parallel versions of STL library algorithms.


namespace  TwoLevelIteratorImpl

Classes

class  GReducible
 GReducible stores per thread values of a variable of type T. More...
struct  gmax
 Operator form of max. More...
struct  gmin
 Operator form of min. More...
struct  ReduceAssignWrap
 Turns binary functions over values into functions over references. More...
struct  ReduceVectorWrap
 Turns binary functions over item references into functions over vectors of items. More...
struct  ReduceMapWrap
 Turns binary functions over item (value) references into functions over maps of items. More...
struct  ReduceCollectionWrap
 Turns functions over elements of a range into functions over collections. More...
class  GSimpleReducible
 Simplification of GReducible where BinFunc calculates results by value, i.e., BinFunc conforms to:. More...
class  GAccumulator
 Accumulator for T where accumulation is sum. More...
class  GCollectionAccumulator
 General accumulator for collections following STL interface where accumulate means collection union. More...
class  GSetAccumulator
 Accumulator for set where accumulation is union. More...
class  GVectorAccumulator
 Accumulator for vector where accumulation is concatenation. More...
class  GVectorElementAccumulator
 Accumulator for vector where a vector is treated as a map and accumulate does element-wise addition among all entries. More...
class  GMapElementAccumulator
 Accumulator for map where accumulate does element-wise addition among all entries. More...
class  GReduceMax
 Accumulator for T where accumulation is max. More...
class  GReduceMin
 Accumulator for T where accumulation is min. More...
class  GAtomic
 An atomic wrapper that provides sensible atomic behavior for most primative data types. More...
class  GAtomicPadded
 Cache-line padded version of GAtomic. More...
struct  InsertBag
 Bag for only concurrent insertions. More...
class  Bag
 Bag for serial use. More...
class  SmallBag
 Bag that supports a small number of inline elements before defaulting to Bag<T> implementation. More...
class  MergeBag
 Like InsertBag but with random access iterators. More...
class  GChecked
 Conflict-checking wrapper for any type. More...
class  GChecked< void >
class  FixedSizeRing
 Ordered collection of bounded size. More...
class  gdeque
 Like std::deque but use Galois memory management functionality. More...
class  gslist
 Singly linked list. More...
class  LargeArray
 Large array of objects with proper specialization for void type. More...
class  LargeArray< void, isLazy >
 Void specialization. More...
class  LazyArray
 This is a container that encapsulates space for a constant size array. More...
class  StrictObject
 Single object with specialization for void type. More...
struct  StrictObject< void >
class  LazyObject
 Single (uninitialized) object with specialization for void type. More...
struct  LazyObject< void >
struct  GFixedAllocator
 Scalable fixed-sized allocator for T that conforms to STL allocator interface but does not support variable sized allocations. More...
class  ThreadSafeOrderedSet
 Thread-safe ordered set. More...
class  ThreadSafeMinHeap
 Thread-safe min heap. More...
struct  SparseBitVector
 Concurrent version of sparse bit vector. More...
class  Statistic
class  StatManager
 Controls lifetime of stats. Users usually instantiate an instance in main. More...
class  StatTimer
 Provides statistic interface around timer. More...
class  Timer
 A simple timer. More...
class  TimeAccumulator
 A multi-start time accumulator. More...
class  TwoLevelIterBase
 Common functionality of TwoLevelIterators. More...
class  TwoLevelFwdIter
 Two-Level forward iterator. More...
class  TwoLevelBiDirIter
 Two-Level bidirectional iterator. More...
class  TwoLevelRandIter
 Two-Level random access iterator. More...
struct  ChooseTwoLevelIterator
 Type function to select appropriate two-level iterator. More...
struct  ChooseStlTwoLevelIterator
 Type function to select appropriate two-level iterator. More...
struct  needs_parallel_break
 Indicates the operator may request the parallel loop to be suspended and a given function run in serial. More...
struct  does_not_need_push
 Indicates the operator does not generate new work and push it on the worklist. More...
struct  needs_per_iter_alloc
 Indicates the operator may request the access to a per-iteration allocator. More...
struct  does_not_need_stats
 Indicates the operator doesn't need its execution stats recorded. More...
struct  does_not_need_aborts
 Indicates the operator doesn't need abort support. More...
struct  has_fixed_neighborhood
 Indicates that the neighborhood set does not change through out i.e. More...
struct  UnionFindNode
 Intrusive union-find implementation. More...
class  UserContext
 This is the object passed to the user's parallel loop. More...

Typedefs

typedef
GaloisRuntime::MM::SimpleBumpPtrWithMallocFallback
< GaloisRuntime::MM::FreeListHeap
< GaloisRuntime::MM::SystemBaseAlloc > > 
IterAllocBaseTy
 Base allocator for per-iteration allocator.
typedef
GaloisRuntime::MM::ExternRefGaloisAllocator
< char, IterAllocBaseTy
PerIterAllocTy
 Per-iteration allocator that conforms to STL allocator interface.

Enumerations

enum  MethodFlag {
  NONE = 0, CHECK_CONFLICT = 1, SAVE_UNDO = 2, ALL = 3,
  WRITE = 4
}
 

What should the runtime do when executing a method.

More...

Functions

template<typename T >
void swap (Galois::Bag< T > &a, Galois::Bag< T > &b)
template<typename T , unsigned N>
void swap (Galois::SmallBag< T, N > &a, Galois::SmallBag< T, N > &b)
template<typename T >
void swap (Galois::MergeBag< T > &a, Galois::MergeBag< T > &b)
template<typename WLTy , typename IterTy , typename FunctionTy >
void for_each (IterTy b, IterTy e, FunctionTy fn, const char *loopname=0)
 Galois unordered set iterator.
template<typename IterTy , typename FunctionTy >
void for_each (IterTy b, IterTy e, FunctionTy fn, const char *loopname=0)
 Galois unordered set iterator with default worklist policy.
template<typename WLTy , typename InitItemTy , typename FunctionTy >
void for_each (InitItemTy i, FunctionTy fn, const char *loopname=0)
 Galois unordered set iterator.
template<typename InitItemTy , typename FunctionTy >
void for_each (InitItemTy i, FunctionTy fn, const char *loopname=0)
 Galois unordered set iterator with default worklist policy.
template<typename WLTy , typename ConTy , typename FunctionTy >
void for_each_local (ConTy &c, FunctionTy fn, const char *loopname=0)
 Galois unordered set iterator with locality-aware container.
template<typename ConTy , typename FunctionTy >
void for_each_local (ConTy &c, FunctionTy fn, const char *loopname=0)
 Galois unordered set iterator with locality-aware container and default worklist policy.
template<typename IterTy , typename FunctionTy >
FunctionTy do_all (const IterTy &b, const IterTy &e, FunctionTy fn, const char *loopname=0)
 Standard do-all loop.
template<typename ConTy , typename FunctionTy >
FunctionTy do_all_local (ConTy &c, FunctionTy fn, const char *loopname=0)
 Standard do-all loop with locality-aware container.
template<typename FunctionTy >
static void on_each (FunctionTy fn, const char *loopname=0)
 Low-level parallel loop.
static void preAlloc (int num)
 Preallocate pages on each thread.
template<typename Iter , typename Cmp , typename NhFunc , typename OpFunc >
void for_each_ordered (Iter b, Iter e, Cmp cmp, NhFunc nhFunc, OpFunc fn, const char *loopname=0)
 Galois ordered set iterator for stable source algorithms.
template<typename Iter , typename Cmp , typename NhFunc , typename OpFunc , typename StableTest >
void for_each_ordered (Iter b, Iter e, Cmp cmp, NhFunc nhFunc, OpFunc fn, StableTest stabilityTest, const char *loopname=0)
 Galois ordered set iterator for unstable source algorithms.
template<typename IterTy , class Distance >
IterTy safe_advance_dispatch (IterTy b, IterTy e, Distance n, std::random_access_iterator_tag)
template<typename IterTy , class Distance >
IterTy safe_advance_dispatch (IterTy b, IterTy e, Distance n, std::input_iterator_tag)
template<typename IterTy , class Distance >
IterTy safe_advance (IterTy b, IterTy e, Distance n)
 Like std::advance but returns end if end is closer than the advance amount.
template<typename IterTy >
IterTy split_range (IterTy b, IterTy e)
 Finds the midpoint of a range.
template<typename IterTy >
std::pair< IterTy, IterTy > block_range (IterTy b, IterTy e, unsigned id, unsigned num)
 Returns a continuous block from the range based on the number of divisions and the id of the block requested.
template<class InputIterator >
void uninitialized_destroy (InputIterator first, InputIterator last)
 Destroy a range.
template<typename IterTy , typename Function1Ty , typename Function2Ty >
static void for_each_det (IterTy b, IterTy e, Function1Ty prefix, Function2Ty fn, const char *loopname=0)
 Deterministic execution with prefix operator.
template<typename T , typename Function1Ty , typename Function2Ty >
static void for_each_det (T i, Function1Ty prefix, Function2Ty fn, const char *loopname=0)
 Deterministic execution with prefix operator.
template<typename IterTy , typename FunctionTy >
static void for_each_det (IterTy b, IterTy e, FunctionTy fn, const char *loopname=0)
 Deterministic execution with single operator.
template<typename T , typename FunctionTy >
static void for_each_det (T i, FunctionTy fn, const char *loopname=0)
 Deterministic execution with single operator.
unsigned int setActiveThreads (unsigned int num)
 Sets the number of threads to use when running any Galois iterator.
unsigned int getActiveThreads ()
 Returns the number of threads in use.
template<typename Outer , typename InnerBegFn , typename InnerEndFn >
ChooseTwoLevelIterator< Outer,
typename
InnerBegFn::result_type,
InnerBegFn, InnerEndFn >::type 
make_two_level_begin (Outer beg, Outer end, InnerBegFn innerBegFn, InnerEndFn innerEndFn)
 Creates two level iterator.
template<typename Outer , typename InnerBegFn , typename InnerEndFn >
ChooseTwoLevelIterator< Outer,
typename
InnerBegFn::result_type,
InnerBegFn, InnerEndFn >::type 
make_two_level_end (Outer beg, Outer end, InnerBegFn innerBegFn, InnerEndFn innerEndFn)
 Creates two level iterator.
template<typename Outer >
TwoLevelIteratorImpl::StlInnerIsIterator
< Outer >::type 
stl_two_level_begin (Outer beg, Outer end)
template<typename Outer >
TwoLevelIteratorImpl::StlInnerIsIterator
< Outer >::type 
stl_two_level_end (Outer beg, Outer end)
template<typename Outer >
TwoLevelIteratorImpl::StlInnerIsConstIterator
< Outer >::type 
stl_two_level_cbegin (Outer beg, Outer end)
template<typename Outer >
TwoLevelIteratorImpl::StlInnerIsConstIterator
< Outer >::type 
stl_two_level_cend (Outer beg, Outer end)
template<typename Outer >
TwoLevelIteratorImpl::StlInnerIsRvrsIterator
< Outer >::type 
stl_two_level_rbegin (Outer beg, Outer end)
template<typename Outer >
TwoLevelIteratorImpl::StlInnerIsRvrsIterator
< Outer >::type 
stl_two_level_rend (Outer beg, Outer end)
template<typename Outer >
TwoLevelIteratorImpl::StlInnerIsConstRvrsIterator
< Outer >::type 
stl_two_level_crbegin (Outer beg, Outer end)
template<typename Outer >
TwoLevelIteratorImpl::StlInnerIsConstRvrsIterator
< Outer >::type 
stl_two_level_crend (Outer beg, Outer end)

Variables

static const unsigned GALOIS_DEFAULT_CHUNK_SIZE = 32

Detailed Description

Main Galois namespace.

All the core Galois functionality will be found in here.


Typedef Documentation

Base allocator for per-iteration allocator.

Per-iteration allocator that conforms to STL allocator interface.


Enumeration Type Documentation

What should the runtime do when executing a method.

Various methods take an optional parameter indicating what actions the runtime should do on the user's behalf: (1) checking for conflicts, and/or (2) saving undo information. By default, both are performed (ALL).

Enumerator:
NONE 
CHECK_CONFLICT 
SAVE_UNDO 
ALL 
WRITE 

Function Documentation

template<typename IterTy >
std::pair<IterTy, IterTy> Galois::block_range ( IterTy  b,
IterTy  e,
unsigned  id,
unsigned  num 
) [inline]

Returns a continuous block from the range based on the number of divisions and the id of the block requested.

template<typename IterTy , typename FunctionTy >
FunctionTy Galois::do_all ( const IterTy &  b,
const IterTy &  e,
FunctionTy  fn,
const char *  loopname = 0 
) [inline]

Standard do-all loop.

All iterations should be independent. Operator should conform to fn(item) where item is a value from the iteration range.

Parameters:
b beginning of range of items
e end of range of items
fn operator
loopname string to identify loop in statistics output
Returns:
fn
template<typename ConTy , typename FunctionTy >
FunctionTy Galois::do_all_local ( ConTy &  c,
FunctionTy  fn,
const char *  loopname = 0 
) [inline]

Standard do-all loop with locality-aware container.

All iterations should be independent. Operator should conform to fn(item) where item is an element of c.

Parameters:
c locality-aware container
fn operator
loopname string to identify loop in statistics output
Returns:
fn
template<typename InitItemTy , typename FunctionTy >
void Galois::for_each ( InitItemTy  i,
FunctionTy  fn,
const char *  loopname = 0 
) [inline]

Galois unordered set iterator with default worklist policy.

Operator should conform to fn(item, UserContext<T>&) where item is i and T is the type of item.

Parameters:
i initial item
fn operator
loopname string to identity loop in statistics output
template<typename WLTy , typename InitItemTy , typename FunctionTy >
void Galois::for_each ( InitItemTy  i,
FunctionTy  fn,
const char *  loopname = 0 
) [inline]

Galois unordered set iterator.

Operator should conform to fn(item, UserContext<T>&) where item is i and T is the type of item.

Template Parameters:
WLTy Worklist policy GaloisRuntime::WorkList
Parameters:
i initial item
fn operator
loopname string to identity loop in statistics output
template<typename IterTy , typename FunctionTy >
void Galois::for_each ( IterTy  b,
IterTy  e,
FunctionTy  fn,
const char *  loopname = 0 
) [inline]

Galois unordered set iterator with default worklist policy.

Operator should conform to fn(item, UserContext<T>&) where item is a value from the iteration range and T is the type of item.

Parameters:
b begining of range of initial items
e end of range of initial items
fn operator
loopname string to identity loop in statistics output
template<typename WLTy , typename IterTy , typename FunctionTy >
void Galois::for_each ( IterTy  b,
IterTy  e,
FunctionTy  fn,
const char *  loopname = 0 
) [inline]

Galois unordered set iterator.

Operator should conform to fn(item, UserContext<T>&) where item is a value from the iteration range and T is the type of item.

Template Parameters:
WLTy Worklist policy {
See also:
Galois::WorkList}
Parameters:
b begining of range of initial items
e end of range of initial items
fn operator
loopname string to identity loop in statistics output
template<typename T , typename FunctionTy >
static void Galois::for_each_det ( i,
FunctionTy  fn,
const char *  loopname = 0 
) [inline, static]

Deterministic execution with single operator.

The operator fn is used both for the prefix computation and for the continuation of computation, c.f., the prefix operator version which uses two different functions. The operator can distinguish between the two uses by querying UserContext.getLocalState().

Parameters:
i initial item
fn operator
loopname string to identity loop in statistics output
template<typename IterTy , typename FunctionTy >
static void Galois::for_each_det ( IterTy  b,
IterTy  e,
FunctionTy  fn,
const char *  loopname = 0 
) [inline, static]

Deterministic execution with single operator.

The operator fn is used both for the prefix computation and for the continuation of computation, c.f., the prefix operator version which uses two different functions. The operator can distinguish between the two uses by querying UserContext.getLocalState().

Parameters:
b begining of range of initial items
e end of range of initial items
fn operator
loopname string to identity loop in statistics output
template<typename T , typename Function1Ty , typename Function2Ty >
static void Galois::for_each_det ( i,
Function1Ty  prefix,
Function2Ty  fn,
const char *  loopname = 0 
) [inline, static]

Deterministic execution with prefix operator.

The prefix of the operator should be exactly the same as the operator but with execution returning at the failsafe point. The operator should conform to a standard Galois unordered set operator for_each().

Parameters:
i initial item
prefix prefix of operator
fn operator
loopname string to identity loop in statistics output
template<typename IterTy , typename Function1Ty , typename Function2Ty >
static void Galois::for_each_det ( IterTy  b,
IterTy  e,
Function1Ty  prefix,
Function2Ty  fn,
const char *  loopname = 0 
) [inline, static]

Deterministic execution with prefix operator.

The prefix of the operator should be exactly the same as the operator but with execution returning at the failsafe point. The operator should conform to a standard Galois unordered set operator for_each().

Parameters:
b begining of range of initial items
e end of range of initial items
prefix prefix of operator
fn operator
loopname string to identity loop in statistics output
template<typename ConTy , typename FunctionTy >
void Galois::for_each_local ( ConTy &  c,
FunctionTy  fn,
const char *  loopname = 0 
) [inline]

Galois unordered set iterator with locality-aware container and default worklist policy.

Operator should conform to fn(item, UserContext<T>&) where item is an element of c and T is the type of item.

Parameters:
c locality-aware container
fn operator
loopname string to identity loop in statistics output
template<typename WLTy , typename ConTy , typename FunctionTy >
void Galois::for_each_local ( ConTy &  c,
FunctionTy  fn,
const char *  loopname = 0 
) [inline]

Galois unordered set iterator with locality-aware container.

Operator should conform to fn(item, UserContext<T>&) where item is an element of c and T is the type of item.

Template Parameters:
WLTy Worklist policy GaloisRuntime::WorkList
Parameters:
c locality-aware container
fn operator
loopname string to identity loop in statistics output
template<typename Iter , typename Cmp , typename NhFunc , typename OpFunc , typename StableTest >
void Galois::for_each_ordered ( Iter  b,
Iter  e,
Cmp  cmp,
NhFunc  nhFunc,
OpFunc  fn,
StableTest  stabilityTest,
const char *  loopname = 0 
) [inline]

Galois ordered set iterator for unstable source algorithms.

Operator should conform to fn(item, UserContext<T>&) where item is a value from the iteration range and T is the type of item. Comparison function should conform to bool r = cmp(item1, item2) where r is true if item1 is less than or equal to item2. Neighborhood function should conform to nhFunc(item) and should visit every element in the neighborhood of active element item. The stability test should conform to bool r = stabilityTest(item) where r is true if item is a stable source.

Parameters:
b begining of range of initial items
e end of range of initial items
cmp comparison function
nhFunc neighborhood function
fn operator
stabilityTest stability test
loopname string to identity loop in statistics output
template<typename Iter , typename Cmp , typename NhFunc , typename OpFunc >
void Galois::for_each_ordered ( Iter  b,
Iter  e,
Cmp  cmp,
NhFunc  nhFunc,
OpFunc  fn,
const char *  loopname = 0 
) [inline]

Galois ordered set iterator for stable source algorithms.

Operator should conform to fn(item, UserContext<T>&) where item is a value from the iteration range and T is the type of item. Comparison function should conform to bool r = cmp(item1, item2) where r is true if item1 is less than or equal to item2. Neighborhood function should conform to nhFunc(item) and should visit every element in the neighborhood of active element item.

Parameters:
b begining of range of initial items
e end of range of initial items
cmp comparison function
nhFunc neighborhood function
fn operator
loopname string to identity loop in statistics output
unsigned int Galois::getActiveThreads (  ) 

Returns the number of threads in use.

template<typename Outer , typename InnerBegFn , typename InnerEndFn >
ChooseTwoLevelIterator<Outer, typename InnerBegFn::result_type, InnerBegFn, InnerEndFn>::type Galois::make_two_level_begin ( Outer  beg,
Outer  end,
InnerBegFn  innerBegFn,
InnerEndFn  innerEndFn 
) [inline]

Creates two level iterator.

template<typename Outer , typename InnerBegFn , typename InnerEndFn >
ChooseTwoLevelIterator<Outer, typename InnerBegFn::result_type, InnerBegFn, InnerEndFn>::type Galois::make_two_level_end ( Outer  beg,
Outer  end,
InnerBegFn  innerBegFn,
InnerEndFn  innerEndFn 
) [inline]

Creates two level iterator.

template<typename FunctionTy >
static void Galois::on_each ( FunctionTy  fn,
const char *  loopname = 0 
) [inline, static]

Low-level parallel loop.

Operator is applied for each running thread. Operator should confirm to fn(tid, numThreads) where tid is the id of the current thread and numThreads is the total number of running threads.

Parameters:
fn operator
loopname string to identify loop in statistics output
static void Galois::preAlloc ( int  num  )  [inline, static]

Preallocate pages on each thread.

Parameters:
num number of pages to allocate of size Galois::Runtime::pageAllocInfo()
template<typename IterTy , class Distance >
IterTy Galois::safe_advance ( IterTy  b,
IterTy  e,
Distance  n 
) [inline]

Like std::advance but returns end if end is closer than the advance amount.

template<typename IterTy , class Distance >
IterTy Galois::safe_advance_dispatch ( IterTy  b,
IterTy  e,
Distance  n,
std::input_iterator_tag   
) [inline]
template<typename IterTy , class Distance >
IterTy Galois::safe_advance_dispatch ( IterTy  b,
IterTy  e,
Distance  n,
std::random_access_iterator_tag   
) [inline]
unsigned int Galois::setActiveThreads ( unsigned int  num  ) 

Sets the number of threads to use when running any Galois iterator.

Returns the actual value of threads used, which could be less than the requested value.

template<typename IterTy >
IterTy Galois::split_range ( IterTy  b,
IterTy  e 
) [inline]

Finds the midpoint of a range.

The first half is always be bigger than the second half if the range has an odd length.

template<typename Outer >
TwoLevelIteratorImpl::StlInnerIsIterator<Outer>::type Galois::stl_two_level_begin ( Outer  beg,
Outer  end 
) [inline]
template<typename Outer >
TwoLevelIteratorImpl::StlInnerIsConstIterator<Outer>::type Galois::stl_two_level_cbegin ( Outer  beg,
Outer  end 
) [inline]
template<typename Outer >
TwoLevelIteratorImpl::StlInnerIsConstIterator<Outer>::type Galois::stl_two_level_cend ( Outer  beg,
Outer  end 
) [inline]
template<typename Outer >
TwoLevelIteratorImpl::StlInnerIsConstRvrsIterator<Outer>::type Galois::stl_two_level_crbegin ( Outer  beg,
Outer  end 
) [inline]
template<typename Outer >
TwoLevelIteratorImpl::StlInnerIsConstRvrsIterator<Outer>::type Galois::stl_two_level_crend ( Outer  beg,
Outer  end 
) [inline]
template<typename Outer >
TwoLevelIteratorImpl::StlInnerIsIterator<Outer>::type Galois::stl_two_level_end ( Outer  beg,
Outer  end 
) [inline]
template<typename Outer >
TwoLevelIteratorImpl::StlInnerIsRvrsIterator<Outer>::type Galois::stl_two_level_rbegin ( Outer  beg,
Outer  end 
) [inline]
template<typename Outer >
TwoLevelIteratorImpl::StlInnerIsRvrsIterator<Outer>::type Galois::stl_two_level_rend ( Outer  beg,
Outer  end 
) [inline]
template<typename T >
void Galois::swap ( Galois::MergeBag< T > &  a,
Galois::MergeBag< T > &  b 
) [inline]
template<typename T , unsigned N>
void Galois::swap ( Galois::SmallBag< T, N > &  a,
Galois::SmallBag< T, N > &  b 
) [inline]
template<typename T >
void Galois::swap ( Galois::Bag< T > &  a,
Galois::Bag< T > &  b 
) [inline]
template<class InputIterator >
void Galois::uninitialized_destroy ( InputIterator  first,
InputIterator  last 
) [inline]

Destroy a range.


Variable Documentation

const unsigned Galois::GALOIS_DEFAULT_CHUNK_SIZE = 32 [static]

Generated on 12 Apr 2013 for Galois by  doxygen 1.6.1