DotMP.Schedulers.WorkStealingScheduler Class Reference

Implementation of work-stealing scheduling. More...

Inheritance diagram for DotMP.Schedulers.WorkStealingScheduler:

Collaboration diagram for DotMP.Schedulers.WorkStealingScheduler:

Classes
struct	Queue
	Queue struct, ensuring that no two values share a cache line. This avoids false sharing issues. More...

Public Member Functions
override void	LoopInit (int start, int end, uint num_threads, uint chunk_size)
	Override method for LoopInit, is called when first starting a work-stealing loop. More...
override void	LoopNext (int thread_id, out int start, out int end)
	Override method for LoopNext, is called to get the bounds of the next chunk to execute. More...

Private Member Functions
void	StealHandler (int thread_id)
	Handles whether or not to steal and how to process the results from a steal. More...
bool	DoSteal (int thread_id)
	Perform a steal. More...

Private Attributes
Queue[]	queues
	Each thread's queue. More...
uint	chunk_size
	Chunk size to use. More...
uint	num_threads
	Number of threads. More...
volatile uint	threads_with_remaining_work
	Counts the remaining threads with work so threads know when to stop attempting to steal. More...
ThreadLocal< Random >	localRandom
	Random instance for compatibility with non-.NET 6 compiles. More...

Additional Inherited Members
Properties inherited from DotMP.Schedule
static Schedule	Static [get]
	The static scheduling strategy. Iterations are divided amongst threads in round-robin fashion. Each thread gets a 'chunk' of iterations, determined by the chunk size. If no chunk size is specified, it's computed as total iterations divided by number of threads. More...
static Schedule	Dynamic [get]
	The dynamic scheduling strategy. Iterations are managed in a central queue. Threads fetch chunks of iterations from this queue when they have no assigned work. If no chunk size is defined, a basic heuristic is used to determine a chunk size. More...
static Schedule	Guided [get]
	The guided scheduling strategy. Similar to dynamic, but the chunk size starts larger and shrinks as iterations are consumed. The shrinking formula is based on the remaining iterations divided by the number of threads. The chunk size parameter sets a minimum chunk size. More...
static Schedule	Runtime [get]
	Runtime-defined scheduling strategy. Schedule is determined by the 'OMP_SCHEDULE' environment variable. Expected format: "schedule[,chunk_size]", e.g., "static,128", "guided", or "dynamic,3". More...
static Schedule	WorkStealing [get]
	The work-stealing scheduling strategy. Each thread gets its own local queue of iterations to execute. If a thread's queue is empty, it randomly selects another thread's queue as its "victim" and steals half of its remaining iterations. The chunk size parameter specifies how many iterations a thread should execute from its local queue at a time. More...

Detailed Description

Implementation of work-stealing scheduling.

Member Function Documentation

DoSteal()

bool DotMP.Schedulers.WorkStealingScheduler.DoSteal ( int  thread_id )

inlineprivate

Perform a steal.

Parameters

thread_id

The thread ID.

Returns

Whether or not the steal was successful.

Exceptions

OverflowException

Thrown if there's an internal scheduler overflow.

LoopInit()

override void DotMP.Schedulers.WorkStealingScheduler.LoopInit ( int  start, int  end, uint  num_threads, uint  chunk_size  )

inlinevirtual

Override method for LoopInit, is called when first starting a work-stealing loop.

Parameters

start	The start of the loop, inclusive.
end	The end of the loop, exclusive.
num_threads	The number of threads.
chunk_size	The chunk size.

Exceptions

OverflowException

Thrown if there's an internal scheduler overflow.

Implements DotMP.Schedule.

LoopNext()

override void DotMP.Schedulers.WorkStealingScheduler.LoopNext ( int  thread_id, out int  start, out int  end  )

inlinevirtual

Override method for LoopNext, is called to get the bounds of the next chunk to execute.

Parameters

thread_id	The thread ID.
start	The start of the chunk, inclusive.
end	The end of the chunk, exclusive.

Exceptions

OverflowException

Thrown if there's an internal scheduler overflow.

Implements DotMP.Schedule.

StealHandler()

void DotMP.Schedulers.WorkStealingScheduler.StealHandler ( int  thread_id )

inlineprivate

Handles whether or not to steal and how to process the results from a steal.

Parameters

thread_id

The thread ID.

Member Data Documentation

chunk_size

uint DotMP.Schedulers.WorkStealingScheduler.chunk_size

private

Chunk size to use.

localRandom

ThreadLocal<Random> DotMP.Schedulers.WorkStealingScheduler.localRandom

private

Random instance for compatibility with non-.NET 6 compiles.

num_threads

uint DotMP.Schedulers.WorkStealingScheduler.num_threads

private

Number of threads.

queues

Queue [] DotMP.Schedulers.WorkStealingScheduler.queues

private

Each thread's queue.

threads_with_remaining_work

volatile uint DotMP.Schedulers.WorkStealingScheduler.threads_with_remaining_work

private

Counts the remaining threads with work so threads know when to stop attempting to steal.

---

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

• DotMP/Schedule.cs