I am trying to implement a parallel quick sort algorithm but i am not so sure how to make use of pthreads inside the quick sort function. This is a link to my code on paste bin http://pastebin.com/tG0h6cMU
3
-
There is no correlation: you can run hundreds of threads on a single-core CPU. If some of the threads are blocked some of the time (perhaps waiting for I/O) it might be a speed improvement.unwind– unwind2013-02-21 10:46:30 +00:00Commented Feb 21, 2013 at 10:46
-
You haven't actually asked about how to multithread your quick-sort, and it would probably be best if you actually tried implementing that first.Mats Petersson– Mats Petersson2013-02-21 10:58:30 +00:00Commented Feb 21, 2013 at 10:58
-
@ Mats petersson i have implemented it.Its in the paste bin folder.It Just does not work .user1850254– user18502542013-02-21 11:02:39 +00:00Commented Feb 21, 2013 at 11:02
Add a comment
|
2 Answers
Number of threads per process should be near 1.0 if they are CPU bound. If there is I/O of some sort involved, then you can have more threads - for example, compiling the Linux kernel tends to run fastest if you run about 1.5 "jobs" (make -j N where N = cores * 1.5) per core. Note however that this is very dependant on the actual behaviour of the threads/processes, and it's almost certainly necessary to measure the ideal performance for YOUR particular scenario.
Certainly, if the number of thread exceed the number of cores by too much, you get "thread thrashing". If there aren't enough threads, the cores aren't kept busy, so that's not great either.
Comments
In general you could do without pthread_mutex_lock, a parallel quicksort without thread-synchronization. According to WP: https://en.wikipedia.org/wiki/Quicksort#Parallelization
Now specifically to your implementation:
I cannot compile the code because i am missing read_in and gen_random but i can tell you these:
There are a few problems with your code:
Line 45: You are assigning an int r to int* r !!!
Line 133: if(a,...).
Also there are a few unused variables (237: unsorted, 236: sorted, 218: i). Maybe you forgot something
1 Comment
user1850254
Sorry ,The unsorted ,sorted variables are unused because i passed it in as function parameters.The if ( a,) is a typo.I wanted to use the mutex locks to ensure that each thread had access to a critical section without overiding values.