[Haskell-cafe] Parallel Karatsuba - A Weird speed up value greater than 4 on an Intel Quadcore CPU!

[Burak Ekici]

Dear List,

I am trying to parallelize Karatsuba multiplication with Haskell's
second generation strategies. Although, I am running the code on an
Intel quad-core  CPU, I abnormally have a speedup much greater 
than 4, around 10, which means a weird parallelization or something 
occurs.

I would be appreciated, if anyone make some comments on the issue 

explaining the possible reasons why this weird incident occurs?

Here is the basic parallel portion of the code:

karatsuba :: Int -> [Bool] -> [Bool] -> [Bool]
karatsuba _ [] _ = []
karatsuba _ _ [] = []
karatsuba currentDepth xs ys 
 | (l < 32 || currentDepth >= limit) = mul xs ys
 | otherwise = (x `add` (replicate l False ++ (z `add` (replicate l False ++ y)))) `Main.using` strategy  
  where 
   l = (min (length xs) (length ys)) `div` 2
   (xs0, xs1) = splitAt l xs
   (ys0, ys1) = splitAt l ys
   x  = (normalize (karatsuba (currentDepth+1) xs0 ys0))
   y  = (normalize (karatsuba (currentDepth+1) xs1 ys1)) 
   z  = ((karatsuba (currentDepth+1) (add xs0 xs1) (add ys0 ys1)) `sub` (normalize (karatsuba (currentDepth+1) xs0 ys0)) `sub` (normalize (karatsuba (currentDepth+1) xs1 ys1)))
   strategy res = do (Main.rpar) (x)
                     (Main.rpar) (y)
                     (Main.rpar) (z)
                     Main.rdeepseq res

Many thanks in advance and kind regards.

Saluti,
Burak.




 		 	   		  
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20111224/d4173349/attachment.htm>