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

Eugene Kirpichov ekirpichov at gmail.com
Sat Dec 24 17:06:21 CET 2011

```If the cache was infinitely faster, then doubling it would give an infinite speedup for an algorithm whose working set was exactly one core's cache size.

24.12.2011, в 19:58, Burak Ekici <ekcburak at hotmail.com> написал(а):

>
> First of all, thanks a lot for your quick answer!
> However, the question is what are the approximate limits
> of this super-linear speedup? I mean, is it acceptable, if
> parallelization happens even 100 time faster?
>
> How can I calculate the limits of this speedup via the
> cache size of my processor?
>
> Cheers,
> Burak.
>
> From: ekirpichov at gmail.com
> Subject: Re: [Haskell-cafe] Parallel Karatsuba - A Weird speed up value greater than 4 on an Intel Quadcore CPU!
> Date: Sat, 24 Dec 2011 19:53:26 +0400
> To: ekcburak at hotmail.com
>
> Superlinear speedup can occur due to the increased cache size.
>
>
>
> 24.12.2011, в 19:49, Burak Ekici <ekcburak at hotmail.com> написал(а):
>
> 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.
>
>
>
>
> _______________________________________________
> Haskell-Cafe mailing list