# Parallel slower than serial

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()
{
.
.
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 <cmath>

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);
k++;
}

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

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

struct arg_struct args;

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;

}
// 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,

• 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. – Geoff Oxberry Jun 15 '15 at 5:55
• I made an edit and included the parallel version – Jones G Jun 15 '15 at 6:14

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++)
{
...