Array sum using OpenMP in logn time

We know that the sum of the array can be calculated in O(n) run time. But can you compute the sum of the array in log n time? The answer would be yes. You can find the sum of an array in log n time. I will explain how you can write the parallel code to find the array sum using OpenMP in O(log n) run time.

Array sum using OpenMP Programming

The OpenMP is a library that implements parallelism within a process. You just have to follow the syntax provided by the library. The internal implementation of parallelism is handled by it.

Pseudocode for array sum using OpenMP

The input to the program will be the queue Q which holds array value and its size ‘n’. The output will be the sum of the elements inside it. Since the addition and deletion of elements in the queue can be done at a constant time we will use the queue to implement it.

Algorithm ompArraySum(Q, n){
    // Make sure the number of threads will be n/2
    for i=1 to logn do in parallel {
        Q = q.front()
        Q.pop()
        Q = q.front()
        Q.pop()
        Q.push(x+y)
    }
    return Q.front()
}

Source code for array sum

The source code for the array sum using the OpenMP library is given below. I have used the “accumulate()” function to cross-check the result. The accumulate function will take O(n) run time. Remember to store the array value in the queue data structure. Then only it will take O(log n) to compute the array sum in the given source code below.

#include<omp.h> 
#include <bits/stdc++.h> 
using namespace std; 

int main(){
	vector<int> arr{3, 1, 2, 5, 4, 0}; 
	queue<int> data; 
	int arr_sum = accumulate(arr.begin(), arr.end(), 0); 
	int arr_size = arr.size(); 
	int new_data_size, x, y;

	for(int i=0; i<arr_size; i++){ 
		data.push(arr[i]); 
	}
	omp_set_num_threads(ceil(arr_size/2));
	
	#pragma omp parallel 
		{ 
			#pragma omp critical 
			{ 
				new_data_size = data.size(); 
				for(int j=1; j<new_data_size; j=j*2){ 
					x = data.front(); 
					data.pop(); 
					y = data.front(); 
					data.pop(); 
					data.push(x+y); 
				} 
			} 

		} 


	cout << "Array prefix sum:" << data.front() << endl; 
	if(arr_sum == data.front())
		{ cout << "Correct sum" << endl; 
	}else{ 
		cout << "Incorrect Answer" << endl; 
	} 
	return 0;
}

Conclusion

You have learned how to compute the sum of the array element in O(log n) run time. The idea was to parallelize the code and compute it. The library used to implement the parallelism in C++ code is OpenMP. You can implement it in the C programming language as well.

You maybe be interested to learn about the following topics. Check them out.