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

Arseniy Alekseyev arseniy.alekseyev at gmail.com
Sun Dec 25 04:31:48 CET 2011


Hi.

You may need to make sure that the CPU frequency scaling does not do
anything funny. (like only boosting the frequency to the maximum when
the parallel program is running)

Arseniy.

> 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
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>



More information about the Haskell-Cafe mailing list