Pugs gains SMP parallelism support.
I hacked +RTS -N support into Pugs today; here's a short writeup: http://pugs.blogs.com/pugs/2006/10/smp_paralleliza.html Pugs's current implementation for concurrent operations on lists is very naive: chan <- newChan forM ([0..] `zip` xs) $ \(n, x) -> forkIO $ do rv <- runEvalIO env (reduce x) writeChan chan (n, rv) fmap (map snd . sort) (replicateM (length xs) (readChan chan)) While the initial result on Linux 2.6 is encouraging, on OSX/Intel with two CPUs it actually slightly slows down the program when running on -N2 or above. I wonder if there is a more efficient way doing this... Thanks, Audrey
On 10/21/06, Audrey Tang <autrijus@gmail.com> wrote:
I wonder if there is a more efficient way doing this...
I would use an IOArray: let l = length xs arr <- newArray_ (0, l) count <- newQSemN 0 let proc n x = do rv <- runEvalIO env (reduce x) writeArray arr n rv signalQSemN count 1 sequence_ $ zipWith proc [0..] xs waitQSemN count l elems $ unsafeFreeze arr STM might work better than a QSemN... -- Taral <taralx@gmail.com> "You can't prove anything." -- Gödel's Incompetence Theorem
在 Oct 21, 2006 9:58 AM 時，Taral 寫到：
On 10/21/06, Audrey Tang <autrijus@gmail.com> wrote:
I wonder if there is a more efficient way doing this...
I would use an IOArray:
let l = length xs arr <- newArray_ (0, l) count <- newQSemN 0 let proc n x = do rv <- runEvalIO env (reduce x) writeArray arr n rv signalQSemN count 1 sequence_ $ zipWith proc [0..] xs waitQSemN count l elems $ unsafeFreeze arr
Hmm, am I missing something here, but how does forkIO (and data parallelism) fit in into that scheme? Thanks, Audrey
On 10/21/06, Audrey Tang <autrijus@gmail.com> wrote:
let proc n x = do
Hmm, am I missing something here, but how does forkIO (and data parallelism) fit in into that scheme?
I R DUM. let proc n x = forkIO $ do -- Taral <taralx@gmail.com> "You can't prove anything." -- Gödel's Incompetence Theorem
在 Oct 21, 2006 5:14 PM 時，Taral 寫到：
On 10/21/06, Audrey Tang <autrijus@gmail.com> wrote:
let proc n x = do
Hmm, am I missing something here, but how does forkIO (and data parallelism) fit in into that scheme?
I R DUM.
let proc n x = forkIO $ do
I just implemented it that way, and benchmarking shows little or no parallelism gain is made by it, compared to the [MVar] approach suggested by Sebastian Sylvan ( http://pugs.blogs.com/pugs/2006/10/more_smp_parall.html )... But thanks a lot for the help. :-) Cheers, Audrey
On 10/22/06, Audrey Tang <autrijus@gmail.com> wrote:
I just implemented it that way, and benchmarking shows little or no parallelism gain is made by it, compared to the [MVar] approach suggested by Sebastian Sylvan ( http://pugs.blogs.com/pugs/2006/10/more_smp_parall.html )...
I wonder why? The IO monad is strict, so the computations should be done in parallel... -- Taral <taralx@gmail.com> "You can't prove anything." -- Gödel's Incompetence Theorem
On 10/22/06, Taral <taralx@gmail.com> wrote:
On 10/22/06, Audrey Tang <autrijus@gmail.com> wrote:
I just implemented it that way, and benchmarking shows little or no parallelism gain is made by it, compared to the [MVar] approach suggested by Sebastian Sylvan ( http://pugs.blogs.com/pugs/2006/10/more_smp_parall.html )...
I wonder why? The IO monad is strict, so the computations should be done in parallel...
They probably are. However you get the overhead of creating the array (when you don't really need O(1) random access) and every thread signals the same semaphore which may lead to some congestion which could slow things down. /S -- Sebastian Sylvan +46(0)736-818655 UIN: 44640862
On 10/23/06, Sebastian Sylvan <sylvan@student.chalmers.se> wrote:
They probably are. However you get the overhead of creating the array (when you don't really need O(1) random access) and every thread signals the same semaphore which may lead to some congestion which could slow things down.
You do need O(1) random access for the writers to put their results in efficiently. And newArray_ should be faster than N copies of newEmptyMVar. It is true that I have one congestion point (the semaphone) instead of N (the mvars). -- Taral <taralx@gmail.com> "You can't prove anything." -- Gödel's Incompetence Theorem
On 10/23/06, Taral <taralx@gmail.com> wrote:
On 10/23/06, Sebastian Sylvan <sylvan@student.chalmers.se> wrote:
They probably are. However you get the overhead of creating the array (when you don't really need O(1) random access) and every thread signals the same semaphore which may lead to some congestion which could slow things down.
You do need O(1) random access for the writers to put their results in efficiently. And newArray_ should be faster than N copies of newEmptyMVar. It is true that I have one congestion point (the semaphone) instead of N (the mvars).
I'm not so sure that a newArray is faster than N copies of newEmptyMVar, at any rate the [MVar] approach has *no* congestion points (each thread will have it's very own place to put the result without any blocking, there is no congestion) and there are no "index out of bounds" checks going on that you get with arrays (could be this that causes performance problems, and not congestion - though both could potentially be a problem for large number of threads). You could try having an array of MVars to get rid of the extra space that the list takes, and use unsafeWrite etc. to get faster writes back to the result array. Then do takeMVar on each item in the array to get "block for N resources" behaviour without having a single resource semaphore that could (profile!) suffer from congestion. /S -- Sebastian Sylvan +46(0)736-818655 UIN: 44640862
On 10/23/06, Sebastian Sylvan <sylvan@student.chalmers.se> wrote:
I'm not so sure that a newArray is faster than N copies of newEmptyMVar, at any rate the [MVar] approach has *no* congestion points
They are congestion points because each thread could conceivably attempt to putMVar at the same time as the main thread tries to takeMVar.
You could try having an array of MVars to get rid of the extra space that the list takes, and use unsafeWrite etc. to get faster writes back to the result array. Then do takeMVar on each item in the array to get "block for N resources" behaviour without having a single resource semaphore that could (profile!) suffer from congestion.
Meh, it seems like a lot of work for little. How many elements were in the benchmark list? I notice that the original benchmark ran for 5 seconds or so, what happens if the work per element is increased? If the length is increased? It's possible that the array approach wins when you try to process 100,000 elements. -- Taral <taralx@gmail.com> "You can't prove anything." -- Gödel's Incompetence Theorem
On 10/23/06, Taral <taralx@gmail.com> wrote:
On 10/23/06, Sebastian Sylvan <sylvan@student.chalmers.se> wrote:
I'm not so sure that a newArray is faster than N copies of newEmptyMVar, at any rate the [MVar] approach has *no* congestion points
They are congestion points because each thread could conceivably attempt to putMVar at the same time as the main thread tries to takeMVar.
That's not a congestion point at all! No more than I would call it congestion if one thread reads a channel and the other writes to it. It's just a straight consumer/producer relationship. The consumer blocks until the producer is done. With a congestion point (like a shared semaphore, depending on implementation of course) the independent producers interfere with each other because one thread can't signal the semaphore at the same time as another thread so they will have to wait until they can get access to the semaphore.
You could try having an array of MVars to get rid of the extra space that the list takes, and use unsafeWrite etc. to get faster writes back to the result array. Then do takeMVar on each item in the array to get "block for N resources" behaviour without having a single resource semaphore that could (profile!) suffer from congestion.
Meh, it seems like a lot of work for little.
How many elements were in the benchmark list? I notice that the original benchmark ran for 5 seconds or so, what happens if the work per element is increased? If the length is increased? It's possible that the array approach wins when you try to process 100,000 elements.
Perhaps. Depends on if congestion is indeed the bottle neck. If not, and if non-overlapping array access is indeed thread safe, then using unsafeRead etc. to use your original approach would surely be beneficial in this case. /S -- Sebastian Sylvan +46(0)736-818655 UIN: 44640862
Hello Audrey, Saturday, October 21, 2006, 12:14:49 PM, you wrote:
I hacked +RTS -N support into Pugs today; here's a short writeup: http://pugs.blogs.com/pugs/2006/10/smp_paralleliza.html
Pugs's current implementation for concurrent operations on lists is very naive:
yes, it's naive :) i think, you should use a larger blocks, otherwise expenses will eat all your profit -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com
Audrey Tang wrote:
I hacked +RTS -N support into Pugs today; here's a short writeup: http://pugs.blogs.com/pugs/2006/10/smp_paralleliza.html
Pugs's current implementation for concurrent operations on lists is very naive:
chan <- newChan forM ([0..] `zip` xs) $ \(n, x) -> forkIO $ do rv <- runEvalIO env (reduce x) writeChan chan (n, rv) fmap (map snd . sort) (replicateM (length xs) (readChan chan))
While the initial result on Linux 2.6 is encouraging, on OSX/Intel with two CPUs it actually slightly slows down the program when running on -N2 or above. I wonder if there is a more efficient way doing this...
Right, it all depends on how much you're doing in each thread. You might want to divide the work into larger chunks (several elements of the array) rather than creating a thread for every element. Cheers, Simon
participants (5)
-
Audrey Tang -
Bulat Ziganshin -
Sebastian Sylvan -
Simon Marlow -
Taral