last day (14 days later) » 

4:00 AM
0
Q: How to improve forking/joining of multithreading program?

iKishoreI have coded a prime number program (sieve of eratosthenes) that executes using pthreads. This is my first multithreading program and I don't know why my program takes roughly 3 mins. time to execute. Thats too much time! Can someone tell me where exactly am I wrong: #include<iostream> #include<

 
jxh
Instead of forking thread after thread, where you have to join before forking again when you are at the limit, why not redesign your solution so that you just fork the right number of threads, and let each do 1/8th of the total task?
 
Wug
@jxh: it's hard to divide this task up without starting it, in particular, it starts each pass of the algorithm at the next available prime, and the value of that prime is only evident once all previous primes have finished being processed. Not that it isn't possible, but it's certainly not trivial.
 
jxh
@Wug: Pipeline processing. Assume 8 threads, T[i]. Each thread is given 1/8th part of the sieve to work. T[0] starts on 2 until it reaches its end, then hands off to T[1], and then T[0] starts on 3. Thus T[0] is sieving 3 while T[1] is sieving 2. Eventually, when T[0] is sieving 19, all the threads will be busy sieving. That's just off the top of my head.
 
Wug
Here's a mathematical optimization that will probably help you more than anything else: You only have to sieve up to sqrt(LIMIT), not all the way up to LIMIT.
 
jxh
@Wug: That optimization only applies if you are trying to determine if LIMIT itself is a prime.
 
Wug
4:00 AM
No, it's true in general. No number in your sieve of size LIMIT will have a factor greater than sqrt(LIMIT) unless it also has a factor less than SQRT(limit). If a and b are your factors, and a and b are both > sqrt(LIMIT), than ab > LIMIT. notice now this optimization is already employed in the search function, wherein marking composite numbers starts at jump*jump (which will be outside of LIMIT for any jump > sqrt(LIMIT)
To be honest, I don't know why you're using threads for this. Unless it's an assignment. Here's an ideone I threw together that sieves the first hundred million primes in less than ideone's 5 second time limit (wolfram alpha verifies that the quantity is correct, but I didn't print them all) ideone.com/mEHr2p
 
jxh
@Wug: What I mean is, if you don't sieve up all the way, you won't know if, say, LIMIT-1 is a prime or not.
 
Wug
@jxh: If LIMIT-1 is not a prime, it will have a factor less than or equal to sqrt(LIMIT - 1), which is strictly less than sqrt(LIMIT).
 
jxh
@Wug: But then you have to test for primality for all numbers greater than sqrt(LIMIT) rather than just iterate through the result of the sieve when printing out which numbers are prime.
 
Wug
OK so
 
jxh
I have to go in a few minutes, will this be quick? I can pick up the chat later if you need some more time.
 
Wug
4:02 AM
I'm trying to think of a succinct way to explain it
When you do a pass through the sieve, you eliminate all multiples of that number as prime candidates
 
jxh
Yes
 
Wug
since you do passes in numerical order, lowest to highest, you're guaranteed that no candidate that is left has any factors smaller than the number you just tested
 
jxh
yes
 
Wug
if it has no factors smaller than that number, than any number up to that number squared which has not been sieved yet is guaranteed to be prime
pretend the question is about N=100
2 eliminates all even numbers
etc etc
 
jxh
okay, I understand what you mean now
 
Wug
4:05 AM
you get to 7
7 is the last number that will eliminate anything under 100
 
jxh
I thought you meant you can stop sieving when you reach sqrt(LIMIT)
 
Wug
the next prime is 11
you can, 10 is sqrt(100) so you don't have to sieve further
if there were some composite number X with a factor p such that p > 10, it MUST have another integer factor q < 10
 
jxh
but you really mean you do sieve all the way up to LIMIT, but you stop running the sieve once you have determined a prime greater than or equal to SQRT(LIMIT)
 
Wug
and you would have hit it already
 
jxh
no I get it.
I misunderstood you
 
Wug
4:07 AM
I don't get what you don't get
:P
anyway I have an answer to his question, but I'm not going to share it with him because I'm pretty sure I'd be doing his homework
 
jxh
I thought you meant you only had to sieve up to SQRT(LIMIT) itself, and then test for all the numbers greater than that for primality. But, you really are saying to sieve all the way to LIMIT, but you can stop once you find a prime greater than or equal to SQRT(LIMIT)
 
Wug
Fun fact: there are 234954223 prime numbers that are less than 5 billion
 
jxh
So, you are right, I misunderstood you.
 
hey @Wug I am also printing the top 10 primes, now the highest prime up to N = 10^8 is 99999989. So up to SQRT(LIMIT) is not what we are doing here
 
jxh
okay, I got to sign out now. later guys.
 
Wug
4:10 AM
@iKishore are you the askwe
asker*
I don't remember.
Is this a homework problem
 
yes.
nope. just trying to understand how threading works
 
Wug
OK
 
I have a project coming up.
 
Wug
your solution is slow because you're creating so many threads, which is not a cheap operation
as someone (@jxh maybe?) pointed out, you'd be better off to try to reuse threads somehow
I have something ugly and inelegant that parallelizes the inner loop instead of the outer one
 
the point is am I making any thing wrong. because if everything is perfect then I will smile and go with the same notion. The thing the question came up because I expected threads will work better.
 
Wug
4:12 AM
well, TBH, your implementation is a lot slower than a single threaded approach
so you've failed in creating a useful multithreaded program
 
are you saying this is not a typical multithreading problem?
 
Wug
Well, threads are difficult to get right. Generally, when people bother to use them, there is a provably significant advantage
otherwise it's not worth the trouble
in the real world, you probably wouldn't thread this if you were only going up to 32 bit integers
Gimme a sec to benchmark my single threaded one locally to see if the MT one is really an improvement
Looks like it's about twice as fast, on an 8 core machine
The speedup is not, in a practical sense, worth it here
 
I have a serialised implementation of the same. the performance was good. Since I am new to threading, my notion is that dividing the work equally to cores will improve the performance. but now I am seeing something different. may be If I ask this way, if any thread expert has to implement the same, using multithreading, then how he would have done it?
 
Wug
its a difference of a few seconds
I'll show you the one I have
I'm not an expert, and there are probably better ways to do it
 
okay.
 
Wug
4:21 AM
The single threaded one does worse in comparison to the multithreaded one as the numbers increase in size. For N=100M, the ST one takes about 2 seconds whereas the MT one takes about 1 (on my machine), but for N=1B, the ST one takes about 50 seconds to the MT one's 11 seconds
Here is the single threaded one ideone.com/mEHr2p
and the multithreaded one ideone.com/2XlFWL
 
One min. I guess you are using Macbook pro?
 
Wug
linux
(the MT one won't run on ideone because it needs to be compiled with -pthread)
 
compiler?
 
Wug
gcc
(g++)
 
got it
11 sec is far better than my 200 sec. any day.
 
Wug
4:25 AM
Your long runtime was because of the thousands of threads you were making and destroying
Mine makes 8 threads, and they stick around until they're done
Each thread is responsible for doing one chunk of the sieve filtering for each pass, all 8 threads work on the pass until it's done, at which point the main thread moves onto the next pass and sets the threads working again
 
Oh! I think I am getting it now. you make thread, reuse them to do things and then kill it all at the end. right?
 
Wug
yep
I spent some time trying to think of ways to run the outer loop in parallel, but that's significantly more complicated
 
Got it buddy. thats where I am doing it wrong.
 
Wug
In particular, it's hard to know whether or not you
you're ready to start the next loop, because all of the previous loops need to have finished the beginning of their runs to know what the next prime i
is
and, with threads, it's hard to guarantee that sort of thing without doing a lot of explicit work
 
okay
 
Wug
4:28 AM
so I gave up on it and did it this way instead
I need to head home, it's late.
 
but thank you so much. may the sole of Ritchie bless you. its his birth day
:)
*soul
 
Wug
uhh
hold on
are you an RIT student
 
nope.
 
Wug
wow im a nerd
never mind I get it
Ritchie was the name of RIT's mascot
 
haha... i meant Dennis McAlstair Ritchie
:)
 
Wug
4:31 AM
yeah I figured that out after thinking what other ritchies you could possibly mean
 
haha..
 
Wug
and I totally know some professors at RIT (which just started classes) that would assign projects like this
 
nope. i am from UCF
FL
u student/prof.?
 

last day (14 days later) »