C# Can Barrier or something similar be used to synchonise tasks multiple times?

Question

I understand a Barrier can be used to have several tasks synchronise their completion before a second phase runs.

I would like to have several tasks synchronise multiple steps like so:

state is 1;
Task1 runs and pauses waiting for state to become 2;
Task2 runs and pauses waiting for state to become 2;
Task2 is final Task and causes the state to progress to state 2;
Task1 runs and pauses waiting for state to become 3;
Task2 runs and pauses waiting for state to become 3;
Task2 is final Task and causes the state to progress to state 3;
state 3 is final state and so all tasks exit.

I know I can spin up new tasks at the end of each state, but since each task does not take too long, I want to avoid creating new tasks for each step.

I can run the above synchronously using for loops, but final state can be 100,000, and so I would like to make use of more than one thread to run the process faster as the process is CPU bound.

I have tried using a counter to keep track of the number of completed Tasks that is incremented by each Task on completion. If the Task is the final Task to complete then it will change the state to the next state. All completed Tasks then wait using while (iterationState == state) await Task.Yield but the performance is terrible and it seems to me a very crude way of doing it.

What is the most efficient way to get the above done? There must be an optimised tool to get this done?

I'm using Parallel.For, creating 300 tasks, and each task needs to run through up to 100,000 states. Each task running through one state completes in less than a second, and creating 300 * 100,000 tasks is a huge overhead that makes running the whole thing synchronously much faster, even if using a single thread.

So I'd like to create 300 Tasks and have these Tasks synchronise moving through the 100,000 states. Hopefully the overhead of creating only 300 tasks instead of 300 * 100,000 tasks, with the overhead of optimised synchronisation between the tasks, will run faster than when doing it synchronously on a single thread.

Each state must complete fully before the next state can be run.

So - what's the optimal synchronisation technique for this scenario? Thanks!

Answer 1

while (iterationState == state) await Task.Yield is indeed a terrible solution to synchronize across your 300 tasks (and no, 300 isn't necessarily super-expensive: you'll only get a reasonable number of threads allocated).

The key problem here isn't the Parallel.For, it's synchronizing across 300 tasks to wait efficiently until each of them have completed a given phase.

The simplest and cleanest solution here would probably be to have a for loop over the stages and a parallel.for over the bit you want parallelized:

for (int stage = 0; stage < 10000; stage++)
{
   // the next line blocks until all 300 have completed
   // will use thread pool threads as necessary
   Parallel.For( ... 300 items to process this stage ... );
}

No extra synchronization primitives needed, no spin-waiting consuming CPU, no needless thrashing between threads trying to see if they are ready to progress.

Answer 2

I think I am understanding what you are trying to do, so here is a suggested way to handle it. Note - I am using Action as the type for the blocking collection, but you can change it to whatever would work best in your scenario.

// Shared variables
CountdownEvent workItemsCompleted = new CountdownEvent(300);
BlockingCollection<Action> workItems = new BlockingCollection<Action>();
CancellationTokenSource cancelSource = new CancellationTokenSource();

// Work Item Queue Thread
for(int i=1; i < stages; ++i)
{
    workItemsCompleted.Reset(300);
    for(int j=0; j < workItemsForStage[i].Count; ++j)
    {
         workItems.Add(() => {}) // Add your work item here
    }
    workItemsCompleted.Wait(token) // token should be passed in from cancelSource.Token
}

// Worker threads that are making use of the queue
// token should be passed to the threads from cancelSource.Token
while(!token.IsCancelled)
{
    var item = workItems.Take(token); // Blocks until available item or token is cancelled
    item();
    workItemsCompleted.Signal();
}

You can use cancelSource from your main thread to cancel the running operations if you need to. In your worker threads you would then need to handle the OperationCancelledException. With this setup you can launch as many worker threads as you need and easily benchmark where you are getting your optimal performance (maybe it is with only using 10 worker threads, etc). Just launch as many workers as you want and then queue up the work items in the Work item queue thread. It's basically a producer-consumer type model except that the producer queues up one phase of the work, then blocks until that phase is done and then queues up the next round of work.