Click here to Skip to main content
15,907,395 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
See more:
I have to problems that I need help solving. 1st problem is to have multiple consumer threads working together to find all the prime numbers in a given range and measure how long the program will take to find all prime numbers using 2, 3, & 4 consumer threads. 2nd problem is to have a 2-item buffer instead of a 1-item buff and measure how long the program will take to find and print all prime numbers using 2, 3, and 4 consumer threads. Here is my code. I have tried searching the web and got nothing. Can you please help. My code is below.

What I have tried:

C++
#include <stdio.h>
#include <pthread.h>
#define MAX 1234568500

pthread_mutex_t the_mutex;
pthread_cond_t condc, condp;
int buffer = 0;

unsigned long long int isPrime(unsigned long long int x)
{
	int i;
	
	for(i=2;i<=x/2;++i)
	{
		if(x % i == 0)
		{
			return -1;
		}
	}
	
	return x;
}

void *producer(void *ptr)
{
	unsigned long long int i;
	for(i=1234567800;i<=MAX;i++)
	{
		pthread_mutex_lock(&the_mutex);
		
		while(buffer!=0)
			pthread_cond_wait(&condp,&the_mutex);
		
		buffer = i;
		pthread_cond_signal(&condc);
		pthread_mutex_unlock(&the_mutex);
	}
	
	pthread_exit(0);
}

void *consumer(void *ptr)
{
	unsigned long long int i;
	for(i=1234567800;i<=MAX;i++)
	{
		pthread_mutex_lock(&the_mutex);
		
		while(buffer==0)
			pthread_cond_wait(&condc,&the_mutex);
		
		if(isPrime(buffer)!=-1)
			printf("%d\n",isPrime(buffer));
			
		buffer = 0;
		pthread_cond_signal(&condp);
		pthread_mutex_unlock(&the_mutex);
	}
	pthread_exit(0);
}

int main(int argc, char **argv)
{
	int num_args = argc - 1
	pthread_t pro,con;
	
	pthread_mutex_init(&the_mutex,0);
	
	pthread_cond_init(&condc,0);
	pthread_cond_init(&condp,0);
	
	pthread_create(&con,0,consumer,0);
	pthread_create(&pro,0,producer,0);
	
	pthread_join(pro,0);
	pthread_join(con,0);
	
	pthread_cond_destroy(&condc);
	pthread_cond_destroy(&condp);
	
	pthread_mutex_destroy(&the_mutex);
	
	return 0;
}
Posted
Updated 6-Mar-20 14:14pm
v2

I have been thinking about your first problem for a while and I think I have an algorithm in mind. It has to do with dividing the work between the threads. The thing is, you probably won't see much improvement over a single-threaded version until you get to really big numbers. What ever. You wanted a multi-threaded version so here is one possibility. The first thing to do is what most prime finders do : test the value for divisibility by 2. If it is then it's not a prime number so get that out of the way first because then you eliminate half of the possibilities. Then you always start at 3 and check every odd number after it since the even ones are already ruled out.

Here's where the dividing the work part comes in. Each thread is given a stride value. With one thread the stride is 2. With two threads the stride is 4. This works out to the stride value being twice the number of threads. Correspondingly, the starting point will be :
C
startingPoint = 3 + ( ( threadIndex - 1 ) * 2 );
This translates to the starting points with four threads will be 3 for thread 1, 5 for thread 2, 7 for thread 3, and 9 for thread 4.

With these values, you could write your test function as :
C
typedef unsigned long long  ULL;

int IsPrime( ULL value, int threadIndex, int threadCount )
{
    ULL strideValue = 2 * (ULL) threadCount;
    ULL lastValue = value / 2;                              // stop testing here
    ULL testValue = 3 + ( ( (ULL) threadIndex - 1 ) * 2 );  // start testing here
    while( testValue <= lastValue )
    {
        if( ( value % testValue ) == 0 )
            return 0;                       // nope, we found a factor
        testValue += strideValue;
    }
    return 1;   // yes, it is a prime
}
The next thing to do is figure out how the threads will report their results. There are a wide variety of ways to do this. One would be to have a single result value and a counter that tells you how many threads have reported. The variables would have their access controlled by a mutex. When a thread finishes it acquires the mutex, sets the result value to true only if its result is true (if false then leave it alone) and then increments the counter. If the thread finds it was the last one (counter == number of threads) it sets a signal indicating the test is done. After all this it releases the mutex.

The next step is to start and signal the threads. This part I will leave to you since it appears that you are using the pthread library and I can't help you with that. I know how threads and signals work in general, but not that library.

There are different ways this algorithm can be used, depending on how you want to test. The IsPrime algorithm was written assuming the threads are testing one value. Another way you can do testing like this is to build a list of prime numbers. For this, you would use a generic IsPrime function written for one thread but you would distribute the values to test as is done in this IsPrime function with different start and stride values, depending on the thread count and index. Then you would need an array of results with a counter controlled by a mutex.
 
Share this answer
 
Comments
Rick York 6-Mar-20 11:02am    
Incidentally, I have been working with CUDA lately and this is how code is parallelized in it. I can imagine this program parallelized to work with GPUs and it would be really fast on large numbers.
Quote:
How to change the program to use multiple consumer level threads

Before resorting to multi-threads, the first thing to do is to make sure that the tested algorithm is optimized.
Your code is a very inefficient 'Trial Division' variant, it happen that just optimizing the code will outperform by far any multi-threaded variation of your code.
See my article to get ideas of how to optimize a Trial Division algorithm: Integer Factorization: Trial Division Algorithm[^]

Your algorithm tells if a number is a prime by finding a factor, returning the factor instead of -1 have much more usages than just telling if prime or not.
 
Share this answer
 
Comments
Member 14764665 6-Mar-20 20:18pm    
Thank you I greatly appreciate this answer. We were given this code in class and just change the code to add these features

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900