The FindPrimeGroupsInParallel method is the heart of the ParallelPrimesTuple example solution. Like the preceding solution, this solution uses form-level variables to allow different instances of the parallel method to share the same values. The following code shows this example's variable declarations:

// Parameters used by parallel method CheckForGroupsInParallel.
private const int NumValuesPerBatch = 10000;
private object ParallelMaxLockObject = new object();
private List<List<int>> ParallelGroups = null;
private int ParallelMax = -1;
private int ParallelSpacing = -1;
private int ParallelNumPerGroup = -1;
private bool[] ParallelIsPrime = null;

Most of these values are used by the CheckForGroupsInParallel method to look for prime tuples. You’ll see how they are used shortly when you read about that method.

The first two variables, NumValuesPerBatch and ParallelMaxLockObject, are more interesting. To understand how they work, you need to know a bit about coordination between parallel method instances.

In the preceding solution, parallel instances of the methods always wrote false into the primes table, so it didn't matter which process wrote first, and there were no race conditions.

This example needs to build a single list containing different tuples of primes, so all of the parallel instances of its methods must write different values into that same list. It would be bad if one instance were in the middle of writing to that list when another instance interrupted and wrote to the same list. Depending on the timing, it's not clear what would happen to the list. It might contain the first method's changes, the second method's changes, both sets of changes, or it might be completely corrupted and unusable.

One way to coordinate between parallel method instances is to use a lock object. A lock object is any object that can be seen by all instances of the method. This example simply uses a new generic object.

When a method needs to write to the shared list, it uses the lock keyword to lock that object. No other instance of the method is allowed to lock the same object until this instance unlocks it. Because only one instance of the method can lock the object at a time, only one instance can access the shared list at a time.

Unfortunately, this creates another problem—locking an object is relatively slow. For a fast search, such as the one used by this program, locking and unlocking that object many times can slow performance significantly.

One solution to this problem is to perform the work in batches. Instead of examining a single value to see if it begins a tuple of primes, each instance of the method searches a whole batch of values and builds its own list of prime tuples. After it has finished searching its batch of values, the method locks the lock object, merges its list with the program's master list, and then unlocks the lock object.

The NumValuesPerBatch constant gives the number of values that each instance of the method should search.

The following FindPrimeGroupsInParallel method starts the process of searching for prime tuples:

// Find groups of primes in parallel.
private List<List<int>> FindPrimeGroupsInParallel(int max, int spacing,
    int numPerGroup, bool[] isPrime)
{
    // Initialize the parallel parameters.
    ParallelGroups = new List<List<int>>();
    ParallelMax = max;
    ParallelSpacing = spacing;
    ParallelNumPerGroup = numPerGroup;
    ParallelIsPrime = isPrime;

    // Treat 2 specially.
    List<int> group = GroupAt(2, max, spacing, numPerGroup, isPrime);
    if (group != null) ParallelGroups.Add(group);

    // Look for other groups in parallel batches.
    Parallel.For(0, max / NumValuesPerBatch, CheckForGroupsInParallel);

    return ParallelGroups;
}

This method starts by initializing the form-level variables. For example, ParallelGroups is the list that will eventually hold all of the prime tuples.

Next, the method uses the GroupAt method to see if there is a group of primes starting at the value 2. Handling that value separately allows the rest of the code to consider only odd starting values for groups.

The code then uses Parallel.For to launch several instances of the CheckForGroupsInParallel method in parallel. The number of groups is the maximum value, max, that the method should check, divided into batches of NumValuesPerBatch values.

After the parallel methods finish, the FindPrimeGroupsInParallel method returns the ParallelGroups list.

The following code shows the CheckForGroupsInParallel method, which does the real work of looking for prime tuples:

// Check values i * ValuesPerCall through (i + 1) * ValuesPerCall.
private void CheckForGroupsInParallel(int i)
{
    // Make a list of groups found in this batch.
    List<List<int>> results = new List<List<int>>();

    // Look for prime groups.
    int start = i * NumValuesPerBatch;
    int stop = start + NumValuesPerBatch;
    if (start % 2 == 0) start++;        // Check odd values.
    if (stop == ParallelMax) stop++;    // Include the original max 
    //value.
    for (int j = start; j < stop; j += 2)
    {
        List<int> group = GroupAt(j, ParallelMax, ParallelSpacing,
            ParallelNumPerGroup, ParallelIsPrime);
        if (group != null) results.Add(group);
    }

    // If we found any groups, add them to the global list.
    if (results.Count > 0)
    {
        lock (ParallelMaxLockObject)
        {
            ParallelGroups.AddRange(results);
        }
    }
}

The method first creates a list named results to hold any prime tuples that it finds. This list is not shared by other instances of the method, so it is safe for this instance to read and write into this list without risk of interference.

This method looks for prime tuples, in the i^th batch of NumValuesPerBatch values. For example, if i is 14 and NumValuesPerBatch is 1,000, then the method considers numbers between 14,000 and 14,999 as potential starting points for prime tuples with the desired spacing and length.

The method calculates the appropriate start and stop values that it can use to cover that range, considering only odd starting numbers. (That's why we handled the special case of groups starting at 2 separately.)

The method loops through the potential starting values, calling the GroupAt method to see if any of the values starts a prime tuple. If GroupAt finds an appropriate tuple, the method adds it to its results list.

After it has examined all of the potential starting values, the method needs to copy its results into the master list, ParallelGroups. Because this might interfere with other parallel instances of the method, the code locks the ParallelMaxLockObject. It uses the ParallelGroups list's AddRange method to copy the newly found tuples into the master list. When the lock block ends, the lock on the ParallelMaxLockObject is automatically released, so other instances of the method can use the master list when they need to do so.

The following screenshot shows the ParallelPrimeTuples example program after it found sexy prime pairs (pairs of primes separated by 6) between 1 and 100 million. You can see that the parallel search was significantly faster than the single iterative search:

You can experiment with the NumValuesPerBatch constant to see how it affects performance. If you set it to 10, the program spends a lot of time coordinating many parallel method instances and locking and unlocking objects, so it is slower than the iterative search. When NumValuesPerBatch is large, say 10,000, the parallel search takes about half as long on my computer. My computer is a quad-core laptop, so it has four CPUs and can therefore run four method instances simultaneously. Ideally, the parallel search would take about a quarter of the time the iterative search takes, but overhead prevents you from ever actually achieving that large an improvement.

Download the ParallelPrimeTuples example solution to see additional details.