CODEWITHSUNDEEP
multithreadingalgorithmparallel-processing
Jason
Jason

Reputation: 851

Most parallel algorithm for calculating sum of squares?

Say I need to calculate the sum of squares for a big array A[n] where n could be millions and I have N threads to use. Can anyone point me to a good parallel algorithm for doing this? thanks!

Upvotes: 1

Views: 856

Answers (1)

Vikram Bhat
Vikram Bhat

Reputation: 6246

Here is an algorithm :- 

1. divide numbers in n/N blocks 
2. Compute for one block squares in parallel in O(1)
3. addition can be done in O(log(N)) for 1 block using adding pair at time

Time complexity :- O(log(N)*(n/N))

Note: This time complexity is completely theorical practically you need to wait for threads to sync after end of parallel operation which increases delay.

Edit:-

Following pseudo code might explain O(logN) parallel algorithm for a thread :-

void add(i,N) {

  int k = 1;

  while(i+k<N && i%k==0 && (i/k)%2==0) {

      arr[i] = arr[i]+arr[i+k];
      synchronize();
      k = 2*k;
   }


}

Note :- This is code for thread number i working on ith index of N sized block , note that the loop is O(logN) as k increases by 2 times every iteration , synchronize() function is used to wait for other threads to finish their iteration if they are not in sync. Try to solve this for an example you will get the idea , the final answer of addition will be in arr[0]

Upvotes: 1

Related Questions