Add Parallel Prefix Sum Algorithm in C,C++,Java and Python

[Ikshvaku24]

The Parallel Prefix Sum algorithm, also known as Parallel Scan or Parallel Reduction, is a parallel algorithm that efficiently computes the prefix sum of a sequence of numbers in parallel. The prefix sum of a sequence is a new sequence where each element represents the sum of all the preceding elements, including itself. The algorithm works by dividing the input sequence into smaller chunks and assigning each chunk to a separate processor or thread. Each processor then computes the partial sum of its assigned chunk. Afterwards, a binary tree reduction is performed to combine the partial sums obtained by each processor, resulting in the final prefix sum.

The key steps of the algorithm are as follows:

1. Divide the input sequence equally among the available processors.

2. Each processor computes the partial sum of its assigned chunk.

3. Use a binary tree reduction technique to combine the partial sums.

   • Processors are arranged in a binary tree structure, where each leaf node corresponds to a processor and each internal node represents the sum of its two child nodes.
   • Partial sums are communicated between processors and added to the corresponding parent node in the binary tree.
   • This process continues until the root node is reached, which holds the final prefix sum.

4. Retrieve the final prefix sum as the output.

Time Complexity: O(n/p + log n)

[firoz3130]

Is this issue available?If so can i get it assigned?

[github-actions[bot]]

Stale issue message