1

I am comparing the run time of a sequential c program that computes the norm of a matrix to that of one using multithreading with openMp. I have produced the following graph from my result, which are generally as you would expect,but I am unsure what has produced the spikes in the program, with some of the programs taking 20 times as long as expected to complete. Is this purely down to the overhead of producing the multiple threads? If so why is the overhead sometimes so much more than other times? Revised Graph of time to compute norm of a matrix

void matrix_norm(int n, double *z, double *norm){
    struct timeval tv1, tv2;
    struct timezone tz;
    int i, j;
    *norm = DBL_MAX*(-1.); 

    gettimeofday(&tv1, &tz);

    #pragma omp parallel for
    for(i=0; i<n; i++){
        double row_sum = 0.;
        #pragma omp parallel 
        for(j=0;j<n;j++)
            row_sum += z[i*n+j];
        #pragma omp critical
        {
            if(row_sum>*norm){
                *norm = row_sum;
            }
        }
    }
    gettimeofday(&tv2, &tz);
    double elapsed = (double) (tv2.tv_sec-tv1.tv_sec) + (double) (tv2.tv_usec-tv1.tv_usec) * 1.e-6;
    printf("%d %f\n",n, elapsed);
}

Here is the result using Z boson's solution

Revised Graph of time to compute norm of a matrix

7
  • 1
    I don't really know what you're doing here, e.g. temp doesn't even seem to be defined. Anyway, you might start looking first at the critical section you placed inside the outer loop, why? Keep everything private as long as possible, put the critical section outside the loop. Typically this kind of thing can be done with a reduction clause.
    – steabert
    Nov 10, 2014 at 18:56
  • Your code was a bit ambiguous. Does my solution do what your want? Did my solution fix your spikes? If so, can you update your plot (I like plots).
    – Z boson
    Nov 11, 2014 at 10:56
  • @Zboson It did for the most part, thanks. Definitely improved the performance and reduced the amount and size of spikes in run time. Nov 11, 2014 at 11:35
  • 1
    @user2644013, I did not mean to replace the plot. You should include the before and after plots.
    – Z boson
    Nov 11, 2014 at 11:53
  • I'm a little surprised you see so much of an improvement. This operations should be memory bandwidth bound so the most I would expect is about a factor of two using multiple threads.
    – Z boson
    Nov 11, 2014 at 11:56

1 Answer 1

0

Try the following function

void matrix_norm(int n, double *z, double *norm){
    int i, j;
    double dtime, temp;
    temp = DBL_MIN;
    dtime = -omp_get_wtime();
    #pragma omp parallel for private(j) reduction(max:temp)
    for(i=0; i<n; i++) {
        double row_sum = 0.;
        for(j=0; j<n; j++)
            row_sum += z[i*n+j];
        if(row_sum>temp) {
            temp = row_sum;
        }
    }
    *norm = temp;
    dtime += omp_get_wtime();
    printf("%d %f\n",n, dtime);
}

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.