Analyzing Parallel Algorithms with the PRAM Model

1. The PRAM (Parallel Random-Access Machine) Model

The PRAM model consists of a collection of processors that all connect to a single, shared memory space.

The model operates on a few key assumptions:

• There are multiple processors, each with its own local memory (registers).
• All processors can access any location in the shared memory in unit time. This is a powerful and important idealization.
• The processors operate in lock-step, meaning they execute instructions synchronously. In each step, every processor executes its instruction for that step.

This model is useful because it simplifies the world. By assuming uniform memory access time and perfect synchronization, it lets us focus purely on the structure of the computation and identify the maximum possible parallelism, without getting bogged down by the details of a specific machine's architecture.

To get a more formal definition of the PRAM model, please review the following slides.

2. Memory Access Conflicts and PRAM Sub-models

The assumption that any processor can access any memory cell in unit time raises a crucial question: what happens if multiple processors try to access the same memory cell in the same synchronous step?

The rules for handling these read and write conflicts define different sub-models of the PRAM. These models form a hierarchy based on how restrictive they are.

• EREW (Exclusive Read, Exclusive Write): The most restrictive model. In any given step, each memory location can be read by at most one processor and written to by at most one processor.
• CREW (Concurrent Read, Exclusive Write): This model relaxes the reading constraint. Multiple processors can read from the same memory location simultaneously, but writes must still be exclusive. This is a very common and practical model.
• CRCW (Concurrent Read, Concurrent Write): The most powerful and least restrictive model. It allows simultaneous reads and writes to the same memory location. Since a concurrent write is ambiguous, several variants exist to define the outcome:
  • COMMON: The write succeeds only if all processors are trying to write the exact same value.
  • ARBITRARY: An arbitrary processor among those attempting to write succeeds. The algorithm must work correctly no matter which one is chosen.
  • PRIORITY: The processor with the highest priority (e.g., the lowest index) succeeds.

The following video and text provide a clear overview of these distinctions.

For a textual reference, the document we looked at earlier also defines these sub-models precisely.

An algorithm designed for EREW will run on a CREW machine, and a CREW algorithm will run on a CRCW machine. The reverse is not always true. Therefore, the hierarchy of computational power is: CRCW ≥ CREW ≥ EREW.

3. Analyzing a PRAM Algorithm: Parallel Reduction

Now let's use the PRAM model to analyze a simple but fundamental parallel algorithm: reduction. A reduction operation takes a collection of values and "reduces" them to a single value using an associative operator like sum, product, max, or min.

Problem: Given an array of n numbers, find their sum.

• Sequential Algorithm: A simple loop that iterates through the array. Time complexity: O(n).

• Parallel Algorithm: We can perform the additions in parallel using a tree-like structure. Let's assume we have n numbers and n/2 processors.

Let's trace the steps for n=8 numbers in an array A:

1. Step 1: Use 4 processors.
   • P0 computes A[0] = A[0] + A[1]
   • P1 computes A[2] = A[2] + A[3]
   • P2 computes A[4] = A[4] + A[5]
   • P3 computes A[6] = A[6] + A[7]
2. Step 2: Use 2 processors.
   • P0 computes A[0] = A[0] + A[2]
   • P1 computes A[4] = A[4] + A[6]
3. Step 3: Use 1 processor.
   • P0 computes A[0] = A[0] + A[4]

The final sum is in A[0].

Performance Analysis

• Parallel Time (T_p): The algorithm takes 3 steps for n=8. In general, it takes log₂(n) steps. So, the parallel time complexity is O(log n). This is a significant improvement over the sequential O(n).
• Total Work (W): This is the total number of operations performed by all processors.
  • Step 1: 4 additions
  • Step 2: 2 additions
  • Step 3: 1 addition
  • Total work = 4 + 2 + 1 = 7, which is n-1. The work complexity is O(n).
• Work-Efficiency: A parallel algorithm is called "work-efficient" if its work complexity is asymptotically the same as the time complexity of the best known sequential algorithm. In this case, our parallel algorithm does O(n) work, and the sequential algorithm takes O(n) time. So, this algorithm is work-efficient.

PRAM Model Suitability

Which PRAM model does this algorithm require? In our description, Processor 0 reads A[0] and A[2] in Step 2. These values were written by Processor 0 and Processor 1 in Step 1. No two processors read or write the same location in the same step. This algorithm can be implemented on an EREW PRAM with careful indexing.

Let's analyze a slightly more formal algorithm for finding the maximum value, designed specifically for the EREW model.

In this example, at each step k, the jump distance is 2^k. A processor id (where id is a multiple of jump) reads its own value M[2*id] and a value from a neighbor M[2*id - jump]. Because of how id and jump are structured, no two processors will read or write to the same memory location simultaneously. This demonstrates the constraints of designing for the EREW model. The time complexity is again O(log n) because the loop runs log n times.

4. The Work-Depth Model

A more general and powerful way to analyze PRAM algorithms is the Work-Depth model (also called the Work-Time or Work-Span model).

• Work (W or T₁): The total number of operations, as we just calculated. It's equivalent to the time it would take to run on a single processor.
• Depth (D or T∞): The length of the longest chain of dependent operations (the "critical path"). This is equivalent to the time it would take to run on an infinite number of processors. For our reduction example, the depth is O(log n).

These two parameters are often all you need to characterize a parallel algorithm's performance. The time T_p on p processors can be estimated by the simple and powerful relationship:
$T_p=O\left(\frac{W}{p}+D\right)$

This formula captures two fundamental bounds:

1. The W/p term represents the "parallelism bound": you have W total work to do, and p processors can at best do it in W/p time.
2. The D term represents the "dependency bound": no matter how many processors you have, you can't go faster than the longest dependency chain.

For our reduction algorithm, W = O(n) and D = O(log n). Therefore, the time on p processors is T_p = O(n/p + log n). This single formula tells us how the algorithm scales with both problem size n and processor count p. This framework is very useful for your background in algorithms and mathematics.

Conclusion

In this lesson, we introduced the PRAM, a theoretical model for parallel computation that allows us to analyze algorithms by abstracting away hardware specifics.

Key Takeaways:

• The PRAM model consists of multiple synchronous processors connected to a single shared memory with uniform access time.
• PRAM sub-models—EREW, CREW, and CRCW—are defined by their rules for handling concurrent memory access, forming a hierarchy of computational power.
• We can analyze parallel algorithms using two key metrics:
  • Parallel Time (T_p): The number of steps on p processors.
  • Work (W): The total number of operations performed.
• A work-efficient algorithm has a work complexity asymptotically equal to the time of the best sequential algorithm.
• The Work-Depth model (W and D) provides a powerful formula, T_p = O(W/p + D), to estimate an algorithm's runtime on any number of processors.

Preview of the Next Lesson

We've now seen how to analyze a simple reduction algorithm. In the next lesson, we will build on this foundation to tackle a more complex and widely used parallel primitive: the prefix sum, also known as scan. We will use the PRAM model to design and analyze a parallel prefix sum algorithm. This will challenge us to think more deeply about data movement and dependencies in parallel execution.