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

[Eugene Kirpichov]

I mean exactly 2x one cores cache size of course.



24.12.2011, в 20:06, Eugene Kirpichov <ekirpichov at gmail.com> написал(а):

> 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.
>> 
>> CC: haskell-cafe at haskell.org
>> 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
>> Haskell-Cafe at haskell.org
>> http://www.haskell.org/mailman/listinfo/haskell-cafe
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20111224/9bc7b07d/attachment.htm>