Parallel Data Distribution Strategies

1. The Principle of Data Decomposition

Before diving into specific strategies, let's establish the underlying principle. In many parallel applications, especially in scientific and engineering domains, the computations are tightly bound to the data they operate on. For instance, updating a cell in a fluid dynamics simulation depends on its neighboring cells.

This leads to a powerful design paradigm: to parallelize the computation, we first partition the data. Once the data is distributed among the processors, we can apply the "owner-computes" rule, where each processor is responsible for performing the computations on the data it "owns".

To begin, let's briefly review this concept of partitioning a problem by decomposing its data.

The key idea is that by splitting the data (e.g., a large matrix or a list of transactions) across processors, we implicitly create parallel tasks. The challenge now becomes how to perform this split effectively.

2. Strategy 1: Block Distribution

The most straightforward way to distribute data is block distribution. Imagine you have a large array of data and P processors. In a block distribution, you divide the array into P contiguous, equal-sized chunks, and assign one chunk to each processor.

This strategy can be applied to arrays (1D), matrices (2D), or higher-dimensional data structures. For a 2D matrix, we can apply a block distribution along the rows or along the columns.

The following reading illustrates this simple but powerful scheme.

Properties of Block Distribution:

• Pros:

  • Simplicity: It's easy to calculate which processor owns which data element.
  • Good Data Locality: Each processor works on a contiguous block of memory. This is highly beneficial for CPU caches (a topic we covered in Module 2), as accessing one element makes it likely that nearby elements, which will be needed soon, are also loaded into the cache.

• Cons:

  • Potential for Load Imbalance: This is the major drawback. Block distribution assumes that the amount of computational work is uniform across all data. If some parts of the data require more computation than others, some processors will be heavily loaded while others finish early and sit idle.

Let's see a classic example where this becomes a problem.

3. Motivating the Need for Better Strategies: Load Imbalance

Consider an algorithm like Gaussian elimination or LU decomposition on a matrix. The computation is not uniform. In the beginning, all rows and columns are involved. As the algorithm progresses, rows and columns are eliminated, and the "active" part of the matrix shrinks.

If we use a simple block distribution, the processors assigned the first few rows/columns will do a lot of work throughout the entire algorithm. Processors assigned the last few rows/columns will finish their work very quickly and then have nothing to do. This creates a severe load imbalance, hurting parallel efficiency.

This problem forces us to find distribution schemes that can average out such non-uniform workloads.

4. Strategy 2: Cyclic Distribution

To combat load imbalance, we can use cyclic distribution. Instead of giving each processor a large contiguous chunk, we distribute the data elements in a round-robin fashion.

For a 1D array and P processors:

• Processor 0 gets elements 0, P, 2P, 3P, ...
• Processor 1 gets elements 1, P+1, 2P+1, 3P+1, ...
• ...
• Processor k gets elements k, P+k, 2P+k, ...

This ensures that each processor gets a fine-grained, interleaved sampling of data from all across the array, which is very effective at balancing the load even when the work is non-uniform.

Properties of Cyclic Distribution:

• Pros:

  • Excellent Load Balancing: By giving each processor a little bit of every part of the dataset, it naturally averages out hotspots and regions of heavy computation.

• Cons:

  • Poor Data Locality: A processor's data is now spread across memory. Accessing element i and then element i+P involves jumping a large distance in memory, which is inefficient for CPU caches.

We have a clear trade-off: block distribution has good locality but can have bad load balance, while cyclic distribution has good load balance but bad locality. Is there a way to get the best of both worlds?

5. Strategy 3: Block-Cyclic Distribution

The block-cyclic distribution is a hybrid strategy that combines the advantages of the block and cyclic schemes. The idea is to:

1. Partition the data into small, contiguous blocks (with a fixed block_size).
2. Distribute these blocks among the processors in a cyclic, round-robin manner.

Block-cyclic distribution introduces a tunable parameter: the block size. By adjusting this parameter, we can navigate the trade-off between load balance and locality.

• A small block size (e.g., 1) makes the distribution behave like cyclic, prioritizing load balance.
• A large block size (e.g., N/P, where N is the total data size) makes it behave like block, prioritizing locality.

In fact, both block and cyclic distributions are just special cases of the block-cyclic distribution.

Properties of Block-Cyclic Distribution:

• Pros:

  • Tunable Performance: It provides a knob (the block size) to balance the trade-off between load balance and data locality.
  • General-Purpose: It is a robust and widely used strategy in high-performance numerical libraries (like ScaLAPACK) because of its flexibility.

• Cons:

  • More Complex: The mapping from a global data index to a specific processor and local index is more complicated to compute than in the simple block or cyclic schemes.

The image "Data distribution strategies" we saw earlier also provides an excellent visualization of how these strategies apply to 2D data, creating combinations like (BLOCK, BLOCK), (CYCLIC, CYCLIC), and (BLOCK, CYCLIC). The choice depends heavily on the algorithm's data access and communication patterns.

Conclusion

In this lesson, we explored three fundamental strategies for distributing data across parallel processors. The choice of strategy is critical and involves managing a core trade-off in parallel computing.

Key Takeaways:

• Block Distribution: Assigns large, contiguous chunks of data to processors. It offers excellent data locality but can suffer from poor load balance if the workload is non-uniform.
• Cyclic Distribution: Assigns data elements in a round-robin fashion. It provides excellent load balancing but at the cost of poor data locality.
• Block-Cyclic Distribution: A hybrid strategy that assigns small blocks of data cyclically. It offers a tunable balance between load locality and load balance, making it a powerful and flexible choice for many applications.
• The core trade-off is Load Balance vs. Data Locality. Optimizing a parallel algorithm often involves finding the sweet spot between these two competing goals.

Preview of the Next Lesson

Now that we understand how data can be laid out across processors, we need a way to reason about how those processors can access the data and interact with each other. In the next lesson, we will be introduced to an abstract model of a parallel computer known as the PRAM (Parallel Random-Access Machine). We will learn how to analyze a simple parallel algorithm using the PRAM model, which will provide a formal framework for thinking about parallel execution, memory access, and complexity.