0
$\begingroup$

Issue

Hello everyone, I have got a program (from the net) that I intend to speed up by converting it into its parallel version thru the use of pthreads surprisingly though, it runs slower than the serial version. Below is the program:

# include <stdio.h>

//fast square root algorithm
double asmSqrt(double x) 
{
  __asm__ ("fsqrt" : "+t" (x));
  return x;
}

//test if a number is prime
bool isPrime(int n)
{   
    if (n <= 1) return false;
    if (n == 2) return true;
    if (n%2 == 0) return false;

    int sqrtn,i;
    sqrtn = asmSqrt(n);

    for (i = 3; i <= sqrtn; i+=2) if (n%i == 0) return false;
    return true;
}

//number generator iterated from 0 to n
int main()
{
    n = 1000000; //maximum number
    int k,j;

    for (j = 0; j<= n; j++)
    {
        if(isPrime(j) == 1) k++;
        if(j == n) printf("Count: %d\n",k);
    }
    return 0;
}

First attempt for parallelization

I let the pthread manage the for loop

# include <stdio.h>
.
.

int main()
{
    .
    .
    //----->pthread code here<----
    for (j = 0; j<= n; j++)
    {
        if(isPrime(j) == 1) k++;
        if(j == n) printf("Count: %d\n",k);
    }
    return 0;
}

Well, it runs slower than the serial one

Second attempt

I divided the for loop into two threads and run them in parallel using pthreads

However, it still runs slower, I am intending that it may run about twice as fast or well faster. But its not!

Edit: These is my parallel code by the way:

# include <stdio.h>
# include <pthread.h>
# include <cmath>

# define NTHREADS 2

pthread_mutex_t mutex1 = PTHREAD_MUTEX_INITIALIZER;
int k = 0;

double asmSqrt(double x) 
{
  __asm__ ("fsqrt" : "+t" (x));
  return x;
}

struct arg_struct
{
    int initialPrime;
    int nextPrime;
};

bool isPrime(int n)
{   
    if (n <= 1) return false;

    if (n == 2) return true;

    if (n%2 == 0) return false;

    int sqrtn,i;
    sqrtn = asmSqrt(n);

    for (i = 3; i <= sqrtn; i+=2) if (n%i == 0) return false;

    return true;
}

void *parallel_launcher(void *arguments)
{
    struct arg_struct *args = (struct arg_struct *)arguments;

    int j = args -> initialPrime;
    int n = args -> nextPrime - 1;

    for (j = 0; j<= n; j++)
    {
        if(isPrime(j) == 1)
        {
            printf("This is prime: %d\n",j);
pthread_mutex_lock( &mutex1 );
            k++;
pthread_mutex_unlock( &mutex1 );
        }

        if(j == n) printf("Count: %d\n",k);
    }
pthread_exit(NULL);
}

int main()
{
    int f = 100000000;
    int m;

    pthread_t thread_id[NTHREADS];
    struct arg_struct args;

    int rem = (f+1)%NTHREADS;
    int n = floor((f+1)/NTHREADS);

    for(int h = 0; h < NTHREADS; h++)
    {
        if(rem > 0)
        {
            m = n + 1;
            rem-= 1;
        }
        else if(rem == 0)
        {
            m = n;
        }

        args.initialPrime = args.nextPrime;
        args.nextPrime = args.initialPrime + m;

        pthread_create(&thread_id[h], NULL, &parallel_launcher, (void *)&args);
        pthread_join(thread_id[h], NULL);
    }
   // printf("Count: %d\n",k);
    return 0;
}

Note: OS: Fedora 21 x86_64, Compiler: gcc-4.4, Processor: Intel Core i5 (2 physical core, 4 logical), Mem: 6 Gb, HDD: 340 Gb,

$\endgroup$
  • $\begingroup$ Welcome to SciComp! A couple comments: (1) I don't see any actual pthreads calls in your code. (2) A really naive attempt at parallelization would spawn threads that call isPrime on different values of j within the for loop. See the examples in computing.llnl.gov/tutorials/pthreads for details. $\endgroup$ – Geoff Oxberry Jun 15 '15 at 5:55
  • $\begingroup$ I made an edit and included the parallel version $\endgroup$ – James Guana Jun 15 '15 at 6:14
3
$\begingroup$

Part of the problem is that there is one thread that does all numbers:

void *parallel_launcher(void *arguments)
{
  struct arg_struct *args = (struct arg_struct *)arguments;

  int j = args -> initialPrime;
  int n = args -> nextPrime - 1;

  for (j = 0; j<= n; j++)
  {
...

Note how you initialize j correctly and then immediately set it to zero again. In other words, where every thread should do the interval [n,m), instead they do [0,m). The last one of your threads then does all primes and will of course not be faster than the sequential program. You should of course have seen this because the number of primes you print at the end is different for the sequential and the parallel version.

The other problem is that your code looks like this:

 for(int h = 0; h < NTHREADS; h++)
  {
    ...
    pthread_create(&thread_id[h], NULL, &parallel_launcher, (void *)&args);
    pthread_join(thread_id[h], NULL);

In other words, you create a thread and then immediately wait for it to finish before you start the next thread. That means that you never have two threads running in parallel -- no speedup can be expected from this.

$\endgroup$
  • $\begingroup$ Oh, good catch. I shouldn't debug before coffee! $\endgroup$ – Bill Barth Jun 15 '15 at 13:10
  • $\begingroup$ Yea, one of the cardinal sins ;-) $\endgroup$ – Wolfgang Bangerth Jun 15 '15 at 13:40
  • $\begingroup$ Based on my erroneous answer, I'd like to point out, that this could be done with ~3 lines of OpenMP (the pragma, a counter variable, and its incrementer). OpenMP will take care of the rest. $\endgroup$ – Bill Barth Jun 15 '15 at 14:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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