<html>
<head>
<style><!--
.hmmessage P
{
margin:0px;
padding:0px
}
body.hmmessage
{
font-size: 10pt;
font-family:Tahoma
}
--></style></head>
<body class='hmmessage'><div dir='ltr'>
<br>First of all, thanks a lot for your quick answer!<br>However, the question is what are the approximate limits <br>of this super-linear speedup? I mean, is it acceptable, if<br>parallelization happens even 100 time faster?<br><br>How can I calculate the limits of this speedup via the <br>cache size of my processor?<br><br>Cheers,<br>Burak.<br><br><div><div id="SkyDrivePlaceholder"></div><hr id="stopSpelling">CC: haskell-cafe@haskell.org<br>From: ekirpichov@gmail.com<br>Subject: Re: [Haskell-cafe] Parallel Karatsuba - A Weird speed up value greater than 4 on an Intel Quadcore CPU!<br>Date: Sat, 24 Dec 2011 19:53:26 +0400<br>To: ekcburak@hotmail.com<br><br>
<meta http-equiv="Content-Type" content="text/html; charset=unicode">
<meta name="Generator" content="Microsoft SafeHTML"><div>Superlinear speedup can occur due to the increased cache size.<br><br><div><br></div></div><div><br>24.12.2011, Χ 19:49, Burak Ekici &lt;<a href="mailto:ekcburak@hotmail.com">ekcburak@hotmail.com</a>&gt; ΞΑΠΙΣΑΜ(Α):<br><br></div><div></div><blockquote><div>

<style>
.ExternalClass .ecxhmmessage P
{padding:0px;}
.ExternalClass body.ecxhmmessage
{font-size:10pt;font-family:Tahoma;}

</style>
<div dir="ltr">
Dear List,<br><br>I am trying to parallelize Karatsuba multiplication with Haskell's<br>second generation strategies. Although, I am running the code on an<br>Intel quad-core&nbsp; CPU, I abnormally have a speedup much greater <br>than 4, around 10, which means a weird parallelization or something <br>occurs.<br><br>I would be appreciated, if anyone make some comments on the issue <br>
explaining the possible reasons why this weird incident occurs?<br><br>Here is the basic parallel portion of the code:<br><br><font style="" color="#FF0000">karatsuba :: Int -&gt; [Bool] -&gt; [Bool] -&gt; [Bool]</font><font style="" color="#FF0000"><br></font><font style="" color="#FF0000">karatsuba _ [] _ = []</font><font style="" color="#FF0000"><br></font><font style="" color="#FF0000">karatsuba _ _ [] = []</font><font style="" color="#FF0000"><br></font><font style="" color="#FF0000">karatsuba currentDepth xs ys </font><font style="" color="#FF0000"><br></font><font style="" color="#FF0000">&nbsp;| (l &lt; 32 || currentDepth &gt;= limit) = mul xs ys</font><font style="" color="#FF0000"><br></font><font style="" color="#FF0000">&nbsp;| otherwise = (x `add` (replicate l False ++ (z `add` (replicate l False ++ y)))) `Main.using` strategy&nbsp; </font><font style="" color="#FF0000"><br></font><font style="" color="#FF0000">&nbsp; where </font><font style="" color="#FF0000"><br></font><font style="" color="#FF0000">&nbsp;&nbsp; l = (min (length xs) (length ys)) `div` 2</font><font style="" color="#FF0000"><br></font><font style="" color="#FF0000">&nbsp;&nbsp; (xs0, xs1) = splitAt l xs</font><font style="" color="#FF0000"><br></font><font style="" color="#FF0000">&nbsp;&nbsp; (ys0, ys1) = splitAt l ys</font><font style="" color="#FF0000"><br></font><font style="" color="#FF0000">&nbsp;&nbsp; x&nbsp; = (normalize (karatsuba (currentDepth+1) xs0 ys0))</font><font style="" color="#FF0000"><br></font><font style="" color="#FF0000">&nbsp;&nbsp; y&nbsp; = (normalize (karatsuba (currentDepth+1) xs1 ys1)) </font><font style="" color="#FF0000"><br></font><font style="" color="#FF0000">&nbsp;&nbsp; z&nbsp; = ((karatsuba (currentDepth+1) (add xs0 xs1) (add ys0 ys1)) `sub` (normalize (karatsuba (currentDepth+1) xs0 ys0)) `sub` (normalize (karatsuba (currentDepth+1) xs1 ys1)))</font><font style="" color="#FF0000"><br></font><font style="" color="#FF0000">&nbsp;&nbsp; strategy res = do (Main.rpar) (x)</font><font style="" color="#FF0000"><br></font><font style="" color="#FF0000">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; (Main.rpar) (y)</font><font style="" color="#FF0000"><br></font><font style="" color="#FF0000">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; (Main.rpar) (z)</font><font style="" color="#FF0000"><br></font><font style="" color="#FF0000">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Main.rdeepseq res</font><br><br>Many thanks in advance and kind regards.<br><br>Saluti,<br>Burak.<br><br><br><br><br>                                               </div>
</div></blockquote><blockquote><div><span>_______________________________________________</span><br><span>Haskell-Cafe mailing list</span><br><span><a href="mailto:Haskell-Cafe@haskell.org">Haskell-Cafe@haskell.org</a></span><br><span><a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/mailman/listinfo/haskell-cafe</a></span><br></div></blockquote></div>                                               </div></body>
</html>