Dot product of two large vectors

General OpenMP discussion

Dot product of two large vectors

Postby B4nnar » Tue Oct 22, 2013 2:19 am

Hello again,
Before I start once again to anyone who spent his time on my previous problem, especially to ftinetti for his replies.

My next program is about dot product, one of the common tasks for beginners.
Write a sequential C main program to compute a dot product of two large vectors
a and b. Assume that the size of a and b are divisible by the number of threads.
Write n OpenMP code to calculate the dot product and use clause reduce to calculate the final result.

After studing informations from openMp exercises and multiple presentations like this one I've created some code piece. Yet, the info from second link surprised me a bit. Here is the code:
Code: Select all
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <omp.h>

#define VECTOR_LENGHT 1000

double dot_product (int N, double* A, double* B)
{
    double dot=0.0, *a,*b;
    int n,i, nthreads, tid;

    #pragma omp parallel default (none) reduction (+: dot) \
      shared (N,A,B) private (n,i, nthreads, tid, a,b)
    {
        nthreads = omp_get_num_threads();
        tid = omp_get_thread_num();

        n = N/nthreads; // Min iter for all threads
        a = A + n*tid; // Ptrs to this threads
        b = B + n*tid; // chunks of X & Y

        if ( tid == nthreads-1 )
            n += N-n*nthreads;

        dot = a[0]*b[0];
        for (i=1; i<n; i++)
            dot += a[i]*b[i];
    }
    return dot;
}

int main (int argc, char *argv[])
{
    int i;
    double vec_A[VECTOR_LENGHT], vec_B[VECTOR_LENGHT], sum;

    for (i=0; i<VECTOR_LENGHT; i++)
        vec_A[i] = vec_B[i] = 1.0*i;

    sum = dot_product(VECTOR_LENGHT, vec_A, vec_B);
    printf("Sum value: %.8f.\n", sum);

    system("PAUSE");
    return 0;
}

The part which surprised me is:
Code: Select all
        n = N/nthreads; // Min iter for all threads
        a = A + n*tid; // Ptrs to this threads
        b = B + n*tid; // chunks of X & Y

        if ( tid == nthreads-1 )
            n += N-n*nthreads;

The comments are taken from the link. From what I understood:
"n = Vector_size / number_of_threads" -> divides the work to be done between threads; The rest is kinda mistery to me. Would be glad if someone could give me some insight on this method.
Thanks in advance.
B4nnar
 
Posts: 4
Joined: Mon Oct 21, 2013 9:09 am

Re: Dot product of two large vectors

Postby MarkB » Mon Oct 28, 2013 8:02 am

Using pointer arithmetic is a little obfuscated, and the example code is dealing with the case where the number of threads does not divide N exactly. A simpler solution would be:

Code: Select all
        #pragma omp parallel default (none) reduction (+: dot) \
          shared (N,A,B) private (n,i, nthreads, tid, lo, hi)
        {
            nthreads = omp_get_num_threads();
            tid = omp_get_thread_num();

            n = N/nthreads; // no of. iters for each thread
            lo = n*tid; // This thread start here
            hi =  n*(tid+1); // ...and finishes here
           
            for (i=lo; i<hi; i++)
                dot += a[i]*b[i];
        }
MarkB
 
Posts: 434
Joined: Thu Jan 08, 2009 10:12 am


Return to Using OpenMP

Who is online

Users browsing this forum: Google [Bot], Yahoo [Bot] and 10 guests