Partitioning Strategies for Data Parallelism in PLINQ

Back to: LINQ Tutorial For Beginners and Professionals

Partitioning Strategies for Data Parallelism in PLINQ

In this article, I will discuss Partitioning Strategies for Data Parallelism in PLINQ with Examples. Please read our previous article discussing Deep Dive into PLINQ Operations with Examples. At the end of this article, you will understand the following pointers:

1. Partitioning Strategies for Data Parallelism in PLINQ
2. Automatic Partitioning in LINQ with Example
3. Range Partitioning in LINQ with Example
4. Chunk Partitioning in LINQ with Example
5. Hash Partitioning in LINQ with Example
6. Custom Partitioning in LINQ with Example
7. Differences Between Automatic, Range, Chunk, Hash, and Custom Partitioning in LINQ
8. Considerations for Choosing a Partitioning Strategy in LINQ

Partitioning Strategies for Data Parallelism in PLINQ

PLINQ, or Parallel LINQ, is a data parallelism component of the .NET framework that allows for the parallel execution of queries. Efficient data partitioning is crucial in PLINQ as it directly affects the performance and scalability of parallel operations. The following are the different partitioning strategies for data parallelism in PLINQ:

1. Automatic Partitioning in LINQ
2. Range Partitioning in LINQ
3. Chunk Partitioning in LINQ
4. Hash Partitioning in LINQ
5. Custom Partitioning in LINQ

Automatic Partitioning in LINQ with Example

PLINQ automatically partitions the data source into multiple partitions so that multiple threads can work on different data segments concurrently. The default partitioning strategy tries to balance the workload among available processors. However, the efficiency of automatic partitioning depends on the nature of the data and the operations being performed.

Here’s a basic example of how to use PLINQ in a .NET Console Application for parallel processing with automatic partitioning. This example demonstrates filtering a large collection of integers, selecting only prime numbers.

using System;
using System.Diagnostics;
using System.Linq;

namespace PLINQDemo
{
    class Program
    {
        static void Main(string[] args)
        {
            // Generate a list of numbers
            var numbers = Enumerable.Range(1, 1000000);

            // Start stopwatch for timing
            Stopwatch stopwatch = Stopwatch.StartNew();

            // Use PLINQ with AsParallel for automatic partitioning
            var primeNumbers = numbers.AsParallel()
                                      .Where(IsPrime)
                                      .ToList();

            stopwatch.Stop();
            Console.WriteLine($"Total prime numbers: {primeNumbers.Count}");
            Console.WriteLine($"Time taken: {stopwatch.ElapsedMilliseconds} ms");

            // Optional: print a few prime numbers
            primeNumbers.Take(10).ToList().ForEach(n => Console.WriteLine(n));

            Console.ReadKey();
        }

        // Method to check if a number is prime
        static bool IsPrime(int number)
        {
            if (number <= 1) return false;
            if (number == 2) return true;
            if (number % 2 == 0) return false;

            var boundary = (int)Math.Floor(Math.Sqrt(number));

            for (int i = 3; i <= boundary; i += 2)
            {
                if (number % i == 0) return false;
            }

            return true;
        }
    }
}

The above program generates a list of numbers from 1 to 1,000,000 and then uses PLINQ’s AsParallel() method to process them in parallel, automatically partitioning the data among available processors. It filters out the prime numbers from the list and measures the time taken for this operation, showcasing the performance benefits of parallel processing. When you run the above code, you will get the following output:

One of the key features of PLINQ is automatic partitioning, which splits the source collection into partitions and processes them in parallel without requiring explicit partitioning from the developer. Using PLINQ (Parallel LINQ) for automatic partitioning will distribute the processing of data collections across multiple threads, optimizing performance on multi-core or multi-processor systems.

Range Partitioning in LINQ with Example

This strategy involves dividing the data into ranges based on the index. Range partitioning is beneficial for ordered data sources like arrays or lists where each partition can process a contiguous range of elements. It works well when the processing time per element is uniform.

Here’s an example of how you might implement range partitioning using PLINQ in a .NET Console Application. The example will demonstrate parallel processing of a large range of numbers, where we will apply a simple operation to each number to illustrate how the work can be distributed across multiple threads.

using System;
using System.Diagnostics;
using System.Linq;

namespace PLINQDemo
{
    class Program
    {
        static void Main(string[] args)
        {
            // Example data - a large range of integers
            var data = Enumerable.Range(1, 1000000);

            var stopwatch = Stopwatch.StartNew();

            // Parallel processing using PLINQ with range partitioning
            var processedData = data
                .AsParallel()
                .AsOrdered()
                .WithExecutionMode(ParallelExecutionMode.ForceParallelism)
                .WithDegreeOfParallelism(Environment.ProcessorCount) // Utilize all available processors
                .Select(number => {
                    // Simulate work
                    return number * 2;
                }).ToArray(); // ToArray to force parallel execution

            stopwatch.Stop();

            Console.WriteLine($"Processing completed in {stopwatch.ElapsedMilliseconds} milliseconds.");
            Console.WriteLine($"First 10 results: {string.Join(", ", processedData.Take(10))}");
            
            Console.ReadKey();
        }
    }
}

In the code above, we generate a large range of integers (1 to 1,000,000) to act as our dataset. We then use AsParallel() to enable parallel processing of this data using PLINQ. The AsOrdered() call is used to preserve the order of the original data, which might be important depending on the context. WithExecutionMode(ParallelExecutionMode.ForceParallelism) ensures that the operation is executed in parallel even if PLINQ thinks it would be faster to run sequentially (which might be the case for very small datasets or operations). We use WithDegreeOfParallelism(Environment.ProcessorCount) to utilize all available processors on the machine, effectively tailoring the degree of parallelism to the environment the application is running on.

The Select clause contains the operation to be applied to each element in the dataset. In this simple example, we’re doubling each number, but this could be replaced with any operation. The call to ToArray() at the end is used to force the execution of the query, as PLINQ queries are executed lazily. When you run the above code, you will get the following output:

Range partitioning in PLINQ (Parallel LINQ) is a technique that can be used to distribute a sequence of data across multiple partitions, such that each partition processes a contiguous range of elements. This can be particularly useful when working with large datasets that need to be processed in parallel, maximizing resource utilization and improving performance.

Chunk Partitioning in LINQ with Example

In chunk partitioning, data is dynamically partitioned into chunks of a certain size. Each thread fetches a chunk of data to process at a time. This approach can be more efficient than range partitioning when the processing time varies significantly across elements, as it allows for better load balancing among threads.

To demonstrate chunk partitioning using PLINQ (Parallel LINQ), we will create a simple example that processes a large collection of data in parallel, dividing it into chunks for efficiency. The AsParallel method enables parallel processing, and we can manage how the data is partitioned with WithExecutionMode and WithDegreeOfParallelism for custom partitioning strategies.

For this example, let’s create a program that processes a list of integers, performing a simple operation on each item. We’ll simulate chunk partitioning by explicitly defining the degree of parallelism, indirectly influencing how the data is chunked.

using System;
using System.Diagnostics;
using System.Linq;

namespace PLINQDemo
{
    class Program
    {
        static void Main(string[] args)
        {
            // Generate a large list of integers
            var largeListOfNumbers = Enumerable.Range(1, 1000000).ToList();

            // Stopwatch to measure execution time
            Stopwatch stopwatch = Stopwatch.StartNew();

            // Process the list in parallel with a custom degree of parallelism
            var processedList = largeListOfNumbers
                .AsParallel()
                .WithExecutionMode(ParallelExecutionMode.ForceParallelism)
                .WithDegreeOfParallelism(Environment.ProcessorCount) // Customize this based on your CPU
                .Select(number =>
                {
            // Simulate a workload
            return Math.Sqrt(number);
                })
                .ToList();

            stopwatch.Stop();

            Console.WriteLine($"Processing completed in {stopwatch.ElapsedMilliseconds} ms");
            Console.WriteLine($"First 5 results: {string.Join(", ", processedList.Take(5))}");
            
            Console.ReadKey();
        }
    }
}

Explanation:

• Enumerable.Range(1, 1000000).ToList(): Generates a list of integers from 1 to 1,000,000.
• AsParallel(): Converts the LINQ query into a parallel query.
• WithExecutionMode(ParallelExecutionMode.ForceParallelism): Forces the query to be processed in parallel.
• WithDegreeOfParallelism(Environment.ProcessorCount): Specifies the number of processors to use for parallel tasks. You can adjust this value based on your system’s capabilities or specific requirements.
• Select(number => Math.Sqrt(number)): A simple operation (calculating the square root) performed on each number in the list.
• Stopwatch: Measures the execution time of the parallel processing for performance comparison.

When you run the above code, you will get the following output:

Hash Partitioning in LINQ with Example

Hash partitioning distributes elements based on a hash function applied to the keys of the elements. This strategy ensures that the same thread processes all elements with the same key. Hash partitioning is particularly useful for operations like grouping and joining, where elements must be grouped based on certain attributes.

Hash partitioning is a technique used to distribute a collection of data across multiple partitions based on a hash value computed from each element. This can significantly improve performance in parallel processing scenarios by ensuring a more even distribution of work. Here’s an example of using PLINQ for hash partitioning in a .NET Console Application.

using System;
using System.Linq;

namespace PLINQDemo
{
    class Program
    {
        static void Main(string[] args)
        {
            // Example collection
            var numbers = Enumerable.Range(1, 50).ToList();

            // Using PLINQ with AsParallel and WithExecutionMode for parallel execution
            var partitioned = numbers
                                .AsParallel()
                                .WithExecutionMode(ParallelExecutionMode.ForceParallelism)
                                .WithDegreeOfParallelism(2) // Adjust based on your environment
                                .GroupBy(number => number % 2) // Simple hash function: even or odd
                                .Select(group => new { Key = group.Key == 0 ? "Even" : "Odd", Numbers = group.ToList() })
                                .ToList();

            // Outputting the results
            foreach (var partition in partitioned)
            {
                Console.WriteLine($"{partition.Key}: {string.Join(", ", partition.Numbers)}");
            }

            Console.ReadKey();
        }
    }
}

Explanation:

• AsParallel(): Converts the LINQ to Parallel LINQ, enabling parallel execution.
• WithExecutionMode(ParallelExecutionMode.ForceParallelism): Forces the query to be executed in parallel, which can be helpful for demonstration purposes.
• WithDegreeOfParallelism(2): Specifies the number of concurrent tasks. Adjust this based on the number of cores you wish to utilize.
• GroupBy(number => number % 2): This acts as a simple hash function, grouping numbers into even and odd.
• Select(group => …): Transforms each group into a new object containing the group key (“Even” or “Odd”) and the list of numbers in that group.

When you run this application, it will print out the even and odd numbers from 1 to 100, demonstrating a basic form of hash partitioning using PLINQ, as shown in the image below.

Custom Partitioning in LINQ with Example

For scenarios where the built-in partitioners do not provide optimal performance, PLINQ allows custom partitioners to be created. Custom partitioning gives complete control over how the data is divided and processed in parallel, allowing for optimizations based on the specific characteristics of the data and operations.

To demonstrate custom partitioning using PLINQ (Parallel LINQ), we’ll create a simple example of partitioning a large collection of numbers and performing a parallel operation on each partition. Custom partitioning can be beneficial when you have knowledge about the data that allows you to partition it more efficiently than the default partitioner.

In this example, let’s say we have an array of integers, and we want to find the squares of these integers in parallel, using custom partitioning to distribute the work among multiple threads.

using System;
using System.Collections.Concurrent;
using System.Linq;
using System.Threading.Tasks;

namespace PLINQDemo
{
    class Program
    {
        static void Main(string[] args)
        {
            // Example data
            var numbers = Enumerable.Range(1, 1000000).ToArray();

            // Custom partitioner - simple range partitioning
            var rangePartitioner = Partitioner.Create(0, numbers.Length, 10000); // Partition size of 10,000

            // Parallel query with custom partitioning
            var squares = rangePartitioner.AsParallel().SelectMany(range =>
            {
                Console.WriteLine($"Computing range {range.Item1} to {range.Item2} on thread {Task.CurrentId}");
                return Enumerable.Range(range.Item1, range.Item2 - range.Item1).Select(i => numbers[i] * numbers[i]);
            }).ToArray();

            // Output some results
            Console.WriteLine($"Computed {squares.Length} squares.");
            Console.WriteLine($"First 10 squares: {string.Join(", ", squares.Take(10))}");

            Console.ReadKey();
        }
    }
}

Explanation

• The Partitioner.Create method creates a simple range partitioner. This partitioner divides the input range into chunks, with each chunk containing a subrange of the total range. The third argument to Partitioner.Create specifies the approximate size of each subrange.
• The AsParallel() method enables parallel processing, and SelectMany is used to process each subrange in parallel. Inside SelectMany, we compute the squares of the numbers in each subrange.
• We use Console.WriteLine will print information about the ranges being processed and the thread processing, demonstrating the parallel execution.

Now, run your application, and you should see an output indicating that different ranges of numbers are being processed in parallel, along with the first 10 squares computed by your application.

Differences Between Automatic, Range, Chunk, Hash, and Custom Partitioning in LINQ

The differences between automatic, range, chunk, hash, and custom partitioning strategies in LINQ, specifically within the context of Parallel LINQ (PLINQ), revolve around how data is divided and processed across multiple threads or tasks. Understanding these differences is key to optimizing parallel query performance in .NET applications. Here’s a breakdown:

Automatic Partitioning

• Nature: PLINQ uses the default strategy when no specific partitioning is defined.
• Behavior: The system decides how to partition the data source across tasks, typically aiming for a balance that maximizes performance based on the workload and available resources.
• Use Cases: Suitable for many general cases where specific data distribution strategies are not required for performance optimization.

Range Partitioning

• Nature: Divides data into contiguous ranges based on their indices, allocating each range to a different task.
• Behavior: Works well with ordered collections (e.g., arrays, lists) where each task processes a sequential subset of the data.
• Use Cases: It is effective for operations where processing is uniform and predictable across elements or when working with data structures that support fast random access.

Chunk Partitioning

• Nature: Dynamically allocates chunks of data to tasks as they become available to work on the next chunk.
• Behavior: Each task processes a chunk of data before requesting more, which can lead to better load balancing, especially when the processing time per element varies.
• Use Cases: This is ideal for scenarios with uneven workloads per data element or when the total workload is not known in advance.

Hash Partitioning

• Nature: Distributes elements based on the hash value of a key associated with each element, ensuring that all elements with the same key are processed together.
• Behavior: This can lead to efficient grouping and joining operations by consolidating relevant data elements under the same task.
• Use Cases: Useful for operations that group or join data based on specific attributes or keys.

Custom Partitioning

• Nature: Allows developers to define their own strategy for partitioning data and assigning tasks.
• Behavior: Provides the highest level of control, enabling optimizations specific to the data characteristics or the nature of the processing required.
• Use Cases: This is best suited for specialized scenarios where the built-in partitioning strategies do not offer optimal performance, and the developer deeply understands the data and workload.

Key Differences Between Automatic, Range, Chunk, Hash, and Custom Partitioning in LINQ

• Control vs. Convenience: Automatic partitioning offers convenience and general efficiency without developer intervention. In contrast, custom partitioning offers maximum control at the cost of increased complexity.
• Performance Optimization: Range and chunk partitioning are optimized for different types of workloads (uniform vs. variable workloads, respectively). Hash partitioning focuses on data grouping efficiency.
• Flexibility: Custom partitioning allows for bespoke solutions tailored to specific performance characteristics or data structures, potentially outperforming built-in strategies in certain contexts.

Considerations for Choosing a Partitioning Strategy in LINQ

Choosing the right partitioning strategy is crucial for achieving optimal performance in PLINQ. It often requires understanding the data and the operations being performed, and it may involve experimenting with different strategies to find the most effective one for a given scenario.

• Nature of the Data: Ordered versus unordered, uniform size versus variable size, etc.
• Operation Characteristics: Operations that benefit from data locality may favor range partitioning, while operations with variable processing times per element may benefit more from chunk partitioning.
• Scalability and Performance Requirements: The goal is to minimize overhead while maximizing the utilization of available computational resources.
• Complexity and Maintenance: While custom partitioning can offer the best performance, it adds complexity to the codebase.

In the next article, I will discuss Advanced PLINQ Features with Examples. In this article, I explain Partitioning Strategies for Data Parallelism in PLINQ with Examples. I hope you enjoy this Partitioning Strategies for Data Parallelism in PLINQ with Examples article.