galois::worklists Namespace Reference

Scheduling policies for Galois. More...

Classes
struct	Deterministic
	Deterministic execution. More...
class	BulkSynchronous
	Bulk-synchronous scheduling. More...
class	ExternalReference
struct	NoGlobalQueue
struct	LocalQueue
struct	OrderedByIntegerMetric
	Approximate priority scheduling. More...
class	OrderedList
struct	OwnerComputes
struct	ChunkHeader
class	PerThreadChunkQueue
class	PerThreadChunkStack
class	StealingQueue
struct	PerThreadChunkMaster
class	Wrapper
	Simple Container Wrapper worklist (not scalable). More...
struct	StableIterator
	Low-overhead worklist when initial range is not invalidated by the operator. More...
class	ConExtListNode
class	ConExtIterator
class	ConExtLinkedStack
class	ConExtLinkedQueue
struct	DummyIndexer

Typedefs
template<int ChunkSize = 64, typename T = int, bool Concurrent = true>
using	ChunkFIFO = internal::ChunkMaster< T, ConExtLinkedQueue, false, false, ChunkSize, Concurrent >
	Chunk FIFO. More...
template<int ChunkSize = 64, typename T = int, bool Concurrent = true>
using	ChunkLIFO = internal::ChunkMaster< T, ConExtLinkedStack, false, true, ChunkSize, Concurrent >
	Chunk LIFO. More...
template<int ChunkSize = 64, typename T = int, bool Concurrent = true>
using	PerSocketChunkFIFO = internal::ChunkMaster< T, ConExtLinkedQueue, true, false, ChunkSize, Concurrent >
	Distributed chunked FIFO. More...
template<int ChunkSize = 64, typename T = int, bool Concurrent = true>
using	PerSocketChunkLIFO = internal::ChunkMaster< T, ConExtLinkedStack, true, true, ChunkSize, Concurrent >
	Distributed chunked LIFO. More...
template<int ChunkSize = 64, typename T = int, bool Concurrent = true>
using	PerSocketChunkBag = internal::ChunkMaster< T, ConExtLinkedQueue, true, true, ChunkSize, Concurrent >
	Distributed chunked bag. More...
template<int ChunkSize = 64, typename T = int>
using	PerThreadChunkLIFO = PerThreadChunkMaster< true, ChunkSize, StealingQueue< PerThreadChunkStack >, T >
template<int ChunkSize = 64, typename T = int>
using	PerThreadChunkFIFO = PerThreadChunkMaster< false, ChunkSize, StealingQueue< PerThreadChunkQueue >, T >
template<typename T = int>
using	FIFO = Wrapper< T, std::deque< T >, false >
template<typename T = int>
using	GFIFO = Wrapper< T, galois::gdeque< T >, false >
template<typename T = int>
using	LIFO = Wrapper< T, std::deque< T >, true >
template<typename T = int>
using	GLIFO = Wrapper< T, galois::gdeque< T >, true >

Detailed Description

Scheduling policies for Galois.

Scheduling policies for Galois iterators.

Unless you have very specific scheduling requirement, PerSocketChunkLIFO or PerSocketChunkFIFO is a reasonable scheduling policy. If you need approximate priority scheduling, use OrderedByIntegerMetric. For debugging, you may be interested in FIFO or LIFO, which try to follow serial order exactly.

The way to use a worklist is to pass it as a template parameter to for_each(). For example,

galois::for_each(galois::iterate(beg,end), fn,
galois::wl<galois::worklists::PerSocketChunkFIFO<32>>()); 

Typedef Documentation

template<int ChunkSize = 64, typename T = int, bool Concurrent = true>

using galois::worklists::ChunkFIFO = typedef internal::ChunkMaster<T, ConExtLinkedQueue, false, false, ChunkSize, Concurrent>

Chunk FIFO.

A global FIFO of chunks of some fixed size.

Template Parameters

ChunkSize

chunk size

template<int ChunkSize = 64, typename T = int, bool Concurrent = true>

using galois::worklists::ChunkLIFO = typedef internal::ChunkMaster<T, ConExtLinkedStack, false, true, ChunkSize, Concurrent>

Chunk LIFO.

A global LIFO of chunks of some fixed size.

Template Parameters

ChunkSize

chunk size

template<typename T = int>

using galois::worklists::FIFO = typedef Wrapper<T, std::deque<T>, false>

template<typename T = int>

using galois::worklists::GFIFO = typedef Wrapper<T, galois::gdeque<T>, false>

template<typename T = int>

using galois::worklists::GLIFO = typedef Wrapper<T, galois::gdeque<T>, true>

template<typename T = int>

using galois::worklists::LIFO = typedef Wrapper<T, std::deque<T>, true>

template<int ChunkSize = 64, typename T = int, bool Concurrent = true>

using galois::worklists::PerSocketChunkBag = typedef internal::ChunkMaster<T, ConExtLinkedQueue, true, true, ChunkSize, Concurrent>

Distributed chunked bag.

A scalable and resource-efficient policy when you are agnostic to the particular scheduling order.

Template Parameters

chunksize

chunk size

template<int ChunkSize = 64, typename T = int, bool Concurrent = true>

using galois::worklists::PerSocketChunkFIFO = typedef internal::ChunkMaster<T, ConExtLinkedQueue, true, false, ChunkSize, Concurrent>

Distributed chunked FIFO.

A more scalable version of ChunkFIFO.

Template Parameters

ChunkSize

chunk size

template<int ChunkSize = 64, typename T = int, bool Concurrent = true>

using galois::worklists::PerSocketChunkLIFO = typedef internal::ChunkMaster<T, ConExtLinkedStack, true, true, ChunkSize, Concurrent>

Distributed chunked LIFO.

A more scalable version of ChunkLIFO.

Template Parameters

chunksize

chunk size

template<int ChunkSize = 64, typename T = int>

using galois::worklists::PerThreadChunkFIFO = typedef PerThreadChunkMaster<false, ChunkSize, StealingQueue<PerThreadChunkQueue>, T>

template<int ChunkSize = 64, typename T = int>

using galois::worklists::PerThreadChunkLIFO = typedef PerThreadChunkMaster<true, ChunkSize, StealingQueue<PerThreadChunkStack>, T>