Parallel slower than serial

Question

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,

Answer 1

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.