Question

Write a CREW PRAM algorithm for adding all \(n\) numbers of a list in \(\Theta(\lg n)\) time.

Short answer

The CREW PRAM algorithm processes a parallel binary tree reduction. The sum of all elements in the list is stored in the last element of the list after \( \lceil \log_2{n} \rceil \) computational steps, that are executed in parallel. The time complexity of the algorithm is therefore \(\Theta(\lg n)\).

Step-by-step solution

Initialize the Problem

Given a list of \(n\) numbers. The task is to write a CREW PRAM algorithm to add all the \(n\) numbers in \(\Theta(\lg n)\) time.

Process Parallel Binary Tree Reduction

The algorithm will add all the numbers together in a binary tree format. In step \(i\) (where \(i\) starts from 0), each processor \(P_j\) (for every \(j\) such that \(2^i \leq j < n\)) adds element \(X[j-2^i]\) of the number list to \(X[j]\), where \(X\) is the array that represents the list of \(n\) numbers. Specifically, processor \(P_j\) computes \(X[j] = X[j] + X[j - 2^i]\). It's important to notice the number of steps \(i\) will be \(\lceil \log_2{n} \rceil\), since in every step, the distance to the element to be added doubles.

Finalize the Algorithm

After \(\lceil \log_2{n} \rceil\) steps, the sum of all elements in the original list of numbers is stored in the last element. The algorithm performs \(n\) additions in parallel at each step, with a total of \(\lceil \log_2{n} \rceil\) steps, thereby achieving the time complexity of \(\Theta(\lg n)\).

Key concepts

Parallel Computing

Parallel computing is a computational paradigm that divides a complex problem into smaller segments, which are then solved concurrently by multiple processors. This approach leverages the power of several computing resources, enabling faster processing and more efficient use of computational power.

In the context of our CREW PRAM algorithm for adding numbers, parallel computing allows us to perform multiple additions simultaneously. PRAM, which stands for Parallel Random-Access Machine, is a shared-memory abstract machine used for modeling parallel algorithms. The 'CREW' in CREW PRAM stands for Concurrent Read, Exclusive Write, meaning that any number of processors can read a memory location simultaneously, but only one processor can write to any memory location at a time.

By spreading the workload across multiple processors, we can greatly reduce the time it takes to sum a large list of numbers, which is essential for applications requiring quick computations of large datasets, such as in scientific simulations or data mining tasks.

Binary Tree Reduction

Binary tree reduction is a technique in parallel algorithms where the computation structure resembles that of a binary tree. At each level of this conceptual tree, we combine the results from the previous level until we reach a single output value at the root of the tree.

In our adding algorithm, the use of binary tree reduction simplifies the problem of adding all numbers by structuring it as a balanced binary tree. Each leaf at the bottom represents a number from the list, and each internal node represents the sum of its two children. Here's how it works: during each step, pairs of numbers are summed up, and this operation is recursively applied to the sums themselves until we reach the final total at the root.

This method is well-suited for the CREW PRAM model because it ensures that no two processors try to write to the same location at the same time—thanks to its Exclusive Write property—while allowing concurrent reads necessary for the addition of pairs of numbers.

Time Complexity

Time complexity is a fundamental concept in computer science that describes the amount of time an algorithm takes to run as a function of the length of the input. It provides a framework for estimating how the execution time of an algorithm increases with the size of the input.

In the CREW PRAM algorithm for summing a list of numbers, the time complexity is \(\Theta(\lg n)\). This notation means that the running time grows logarithmically with the size of the input list \(n\). This logarithmic time complexity is achieved due to the nature of binary tree reduction, wherein each level of the tree reduces the problem size by half, leading to a total of about \(\lceil \log_2{n} \rceil\) levels or steps. This indicates an algorithm that is highly efficient for parallel processing, as it scales well with the addition of more processors, making it ideal for operations on large datasets where speed is of the essence.