/usr/share/gap/pkg/scscp/doc/chap8.html is in gap-scscp 2.1.4+ds-3.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 | <?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
<head>
<title>GAP (scscp) - Chapter 8: Parallel computing with SCSCP</title>
<meta http-equiv="content-type" content="text/html; charset=UTF-8" />
<meta name="generator" content="GAPDoc2HTML" />
<link rel="stylesheet" type="text/css" href="manual.css" />
<script src="manual.js" type="text/javascript"></script>
<script type="text/javascript">overwriteStyle();</script>
</head>
<body class="chap8" onload="jscontent()">
<div class="chlinktop"><span class="chlink1">Goto Chapter: </span><a href="chap0.html">Top</a> <a href="chap1.html">1</a> <a href="chap2.html">2</a> <a href="chap3.html">3</a> <a href="chap4.html">4</a> <a href="chap5.html">5</a> <a href="chap6.html">6</a> <a href="chap7.html">7</a> <a href="chap8.html">8</a> <a href="chap9.html">9</a> <a href="chapBib.html">Bib</a> <a href="chapInd.html">Ind</a> </div>
<div class="chlinkprevnexttop"> <a href="chap0.html">[Top of Book]</a> <a href="chap0.html#contents">[Contents]</a> <a href="chap7.html">[Previous Chapter]</a> <a href="chap9.html">[Next Chapter]</a> </div>
<p><a id="X859EF4678604393E" name="X859EF4678604393E"></a></p>
<div class="ChapSects"><a href="chap8.html#X859EF4678604393E">8 <span class="Heading">Parallel computing with <strong class="pkg">SCSCP</strong></span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap8.html#X7BB9C05286A1375B">8.1 <span class="Heading">Managing multiple requests</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap8.html#X8249D1A9804C6E08">8.1-1 SynchronizeProcesses</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap8.html#X7B56C3BB87C0A226">8.1-2 FirstProcess</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap8.html#X7CDA73307ABE9998">8.1-3 SCSCPservers</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap8.html#X8783850E81463D0F">8.1-4 ParQuickWithSCSCP</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap8.html#X796D134181D7D8D9">8.1-5 FirstTrueProcess</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap8.html#X7C1FD82A812DDBD0">8.2 <span class="Heading">MasterWorker skeleton</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap8.html#X788208B57D4C497F">8.2-1 ParListWithSCSCP</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap8.html#X8689C2B9840D7E3C">8.2-2 SCSCPreset</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap8.html#X84ACC8B4800D0E34">8.2-3 SCSCPLogTracesToGlobal</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap8.html#X78C5AEA07F961325">8.3 <span class="Heading">Example: parallelising Karatsuba multiplication for polynomials</span></a>
</span>
</div>
</div>
<h3>8 <span class="Heading">Parallel computing with <strong class="pkg">SCSCP</strong></span></h3>
<p><a id="X7BB9C05286A1375B" name="X7BB9C05286A1375B"></a></p>
<h4>8.1 <span class="Heading">Managing multiple requests</span></h4>
<p>Using procedure calls explained in the previous section, the user can create several requests to multiple services to execute them in parallel, or to wait until the fastest result will be available.</p>
<p><a id="X8249D1A9804C6E08" name="X8249D1A9804C6E08"></a></p>
<h5>8.1-1 SynchronizeProcesses</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SynchronizeProcesses</code>( <var class="Arg">process1</var>, <var class="Arg">process2</var>, <var class="Arg">...</var>, <var class="Arg">processN</var> )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SynchronizeProcesses</code>( <var class="Arg">proclist</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: list of records with components <code class="code">object</code> and <code class="code">attributes</code></p>
<p>The function collects results of from each process given in the argument, and returns the list, <span class="SimpleMath">i</span>-th entry of which is the result obtained from the <span class="SimpleMath">i</span>-th process. The function accepts both one argument that is a list of processes, and arbitrary number of arguments, each of them being a process.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">a:=NewProcess( "WS_Factorial", [10], "localhost", 26133 );</span>
< process at localhost:26133 pid=2064 >
<span class="GAPprompt">gap></span> <span class="GAPinput">b:=NewProcess( "WS_Factorial", [20], "localhost", 26134 );</span>
< process at localhost:26134 pid=1975 >
<span class="GAPprompt">gap></span> <span class="GAPinput">SynchronizeProcesses(a,b);</span>
[ rec( attributes := [ [ "call_id", "localhost:26133:2064:yCWBGYFO" ] ],
object := 3628800 ),
rec( attributes := [ [ "call_id", "localhost:26134:1975:yAAWvGTL" ] ],
object := 2432902008176640000 ) ]
</pre></div>
<p><a id="X7B56C3BB87C0A226" name="X7B56C3BB87C0A226"></a></p>
<h5>8.1-2 FirstProcess</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ FirstProcess</code>( <var class="Arg">process1</var>, <var class="Arg">process2</var>, <var class="Arg">...</var>, <var class="Arg">processN</var> )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ FirstProcess</code>( <var class="Arg">proclist</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: records with components <code class="code">object</code> and <code class="code">attributes</code></p>
<p>The function waits for the result from each process given in the argument, and returns the result coming first, terminating all remaining processes at the same time. The function accepts both one argument that is a list of processes, and arbitrary number of arguments, each of them being a process.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">a:=NewProcess( "WS_Factorial", [10], "localhost", 26133 );</span>
< process at localhost:26133 pid=2064 >
<span class="GAPprompt">gap></span> <span class="GAPinput">b:=NewProcess( "WS_Factorial", [20], "localhost", 26134 );</span>
< process at localhost:26134 pid=1975 >
<span class="GAPprompt">gap></span> <span class="GAPinput"> FirstProcess(a,b); </span>
rec( attributes := [ [ "call_id", "localhost:26133:2064:mdb8RaO2" ] ],
object := 3628800 )
</pre></div>
<p><a id="X7CDA73307ABE9998" name="X7CDA73307ABE9998"></a></p>
<h5>8.1-3 SCSCPservers</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SCSCPservers</code></td><td class="tdright">( global variable )</td></tr></table></div>
<p><code class="func">SCSCPservers</code> is a list of hosts and ports to search for <strong class="pkg">SCSCP</strong> services (which may be not only represented by <strong class="pkg">GAP</strong> services, but also by another <strong class="pkg">SCSCP</strong>-compliant systems).</p>
<p>It is used by parallel skeletons <code class="func">ParQuickWithSCSCP</code> (<a href="chap8.html#X8783850E81463D0F"><span class="RefLink">8.1-4</span></a>) and <code class="func">ParListWithSCSCP</code> (<a href="chap8.html#X788208B57D4C497F"><span class="RefLink">8.2-1</span></a>).</p>
<p>The initial value of this variable is specified in the file <code class="file">scscp/configpar.g</code> and may be reassigned later.</p>
<p><a id="X8783850E81463D0F" name="X8783850E81463D0F"></a></p>
<h5>8.1-4 ParQuickWithSCSCP</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ParQuickWithSCSCP</code>( <var class="Arg">commands</var>, <var class="Arg">listargs</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: record with components <code class="code">object</code> and <code class="code">attributes</code></p>
<p>This function is constructed using the <code class="func">FirstProcess</code> (<a href="chap8.html#X7B56C3BB87C0A226"><span class="RefLink">8.1-2</span></a>). It is useful when it is not known which partcular method is more efficient, because it allows to call in parallel several procedures (given by the list of their names <var class="Arg">commands</var>) with the same list of arguments <var class="Arg">listargs</var> (having the same meaning as in <code class="func">EvaluateBySCSCP</code> (<a href="chap6.html#X7C745B2878E0AC41"><span class="RefLink">6.3-1</span></a>)) and obtain the result of that procedure call which will be computed faster.</p>
<p>In the example below we call two factorisation methods from the <strong class="pkg">GAP</strong> package <strong class="pkg">FactInt</strong> to factorise <span class="SimpleMath">2^150+1</span>. The example is selected in such a way that the runtime of these two methods is approximately the same, so you should expect results from both methods in some random order from repeated calls.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">ParQuickWithSCSCP( [ "WS_FactorsECM", "WS_FactorsMPQS" ], [ 2^150+1 ] );</span>
rec( attributes := [ [ "call_id", "localhost:26133:53877:GQX8MhC8" ] ],
object := [ [ 5, 5, 5, 13, 41, 61, 101, 1201, 1321, 63901 ],
[ 2175126601, 15767865236223301 ] ] )
</pre></div>
<p><a id="X796D134181D7D8D9" name="X796D134181D7D8D9"></a></p>
<h5>8.1-5 FirstTrueProcess</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ FirstTrueProcess</code>( <var class="Arg">process1</var>, <var class="Arg">process2</var>, <var class="Arg">...</var>, <var class="Arg">processN</var> )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ FirstTrueProcess</code>( <var class="Arg">proclist</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: list of records</p>
<p>The function waits for the result from each process given in the argument, and stops waiting as soon as the first <code class="keyw">true</code> is returned, abandoning all remaining processes. It retuns a list containing a records with components <code class="code">object</code> and <code class="code">attributes</code> at the position corresponding to the process that returned <code class="keyw">true</code>. If none of the processes returned true, it will return a complete list of procedure call results.</p>
<p>The function accepts both one argument that is a list of processes, and arbitrary number of arguments, each of them being a process.</p>
<p>In the first example, the second call returns <code class="keyw">true</code>:</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">a:=NewProcess( "IsPrimeInt", [2^15013-1], "localhost", 26134 );</span>
< process at localhost:26134 pid=42554 >
<span class="GAPprompt">gap></span> <span class="GAPinput">b:=NewProcess( "IsPrimeInt", [2^521-1], "localhost", 26133 );</span>
< process at localhost:26133 pid=42448 >
<span class="GAPprompt">gap></span> <span class="GAPinput">FirstTrueProcess(a,b); </span>
[ , rec( attributes := [ [ "call_id", "localhost:26133:42448:Lz1DL0ON" ] ],
object := true ) ]
</pre></div>
<p>In the next example both calls return <code class="keyw">false</code>:</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">a:=NewProcess( "IsPrimeInt", [2^520-1], "localhost", 26133 );</span>
< process at localhost:26133 pid=42448 >
<span class="GAPprompt">gap></span> <span class="GAPinput">b:=NewProcess( "IsPrimeInt", [2^15013-1], "localhost", 26134 );</span>
< process at localhost:26134 pid=42554 >
<span class="GAPprompt">gap></span> <span class="GAPinput">FirstTrueProcess(a,b); </span>
[ rec( attributes := [ [ "call_id", "localhost:26133:42448:nvsk8PQp" ] ],
object := false ),
rec( attributes := [ [ "call_id", "localhost:26134:42554:JnEYuXL8" ] ],
object := false ) ]
</pre></div>
<p><a id="X7C1FD82A812DDBD0" name="X7C1FD82A812DDBD0"></a></p>
<h4>8.2 <span class="Heading">MasterWorker skeleton</span></h4>
<p>In this section we will present more general framework to run parallel computations, which has a number of useful features:</p>
<ul>
<li><p>it is implemented purely in <strong class="pkg">GAP</strong>;</p>
</li>
<li><p>the client (i.e. master, which orchestrates the computation) will work in UNIX/Linux, Mac OS X and MS Windows;</p>
</li>
<li><p>it may orchestrate both <strong class="pkg">GAP</strong> and non-<strong class="pkg">GAP</strong> <strong class="pkg">SCSCP</strong> servers;</p>
</li>
<li><p>if one of servers (i.e. workers) will be lost, it will retry the computation on another available server;</p>
</li>
<li><p>it allows to add dynamically new workers during the computation on hostnames and ports from a range perviously declared in <code class="func">SCSCPservers</code> (<a href="chap8.html#X7CDA73307ABE9998"><span class="RefLink">8.1-3</span></a>).</p>
</li>
</ul>
<p>To configure this functionality, the file <code class="file">scscp/configpar.g</code> assigns the global variable <code class="code">SCSCPservers</code> which specifies a list of hosts and ports to search for <strong class="pkg">SCSCP</strong> services (which may be not only represented by <strong class="pkg">GAP</strong> services, but also by another <strong class="pkg">SCSCP</strong>-compliant systems). See comments in this file for further instructions.</p>
<p><a id="X788208B57D4C497F" name="X788208B57D4C497F"></a></p>
<h5>8.2-1 ParListWithSCSCP</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ParListWithSCSCP</code>( <var class="Arg">listargs</var>, <var class="Arg">procname</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: list</p>
<p><code class="func">ParListWithSCSCP</code> implements the well-known master-worker skeleton: we have a master (<strong class="pkg">SCSCP</strong> client) and a number of workers (<strong class="pkg">SCSCP</strong> servers) which obtain pieces of work from the client, perform the required job and report back with the result, waiting for the next job.</p>
<p>It returns the list of the same length as <var class="Arg">listargs</var>, <span class="SimpleMath">i</span>-th element of which is the result of calling the procedure <var class="Arg">procname</var> with the argument <var class="Arg">listargs[i]</var>.</p>
<p>It accepts two options which should be given as non-negative integers: <code class="code">timeout</code> which specifies in minutes how long the client must wait for the result (if not given, the default value is one hour) and <code class="code">recallfrequency</code> which specifies the number of iterations after which the search for new services will be performed (if not given the default value is zero meaning no such search at all). There is also a boolean option <code class="code">noretry</code> which, if set to <code class="keyw">true</code>, means that no retrying calls will be performed if the timeout is exceeded and an incomplete resut may be returned.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">ParListWithSCSCP( List( [2..6], n -> SymmetricGroup(n)), "WS_IdGroup" );</span>
#I master -> [ "localhost", 26133 ] : SymmetricGroup( [ 1 .. 2 ] )
#I master -> [ "localhost", 26134 ] : SymmetricGroup( [ 1 .. 3 ] )
#I [ "localhost", 26133 ] --> master : [ 2, 1 ]
#I master -> [ "localhost", 26133 ] : SymmetricGroup( [ 1 .. 4 ] )
#I [ "localhost", 26134 ] --> master : [ 6, 1 ]
#I master -> [ "localhost", 26134 ] : SymmetricGroup( [ 1 .. 5 ] )
#I [ "localhost", 26133 ] --> master : [ 24, 12 ]
#I master -> [ "localhost", 26133 ] : SymmetricGroup( [ 1 .. 6 ] )
#I [ "localhost", 26133 ] --> master : [ 720, 763 ]
#I [ "localhost", 26134 ] --> master : [ 120, 34 ]
[ [ 2, 1 ], [ 6, 1 ], [ 24, 12 ], [ 120, 34 ], [ 720, 763 ] ]
</pre></div>
<p><a id="X8689C2B9840D7E3C" name="X8689C2B9840D7E3C"></a></p>
<h5>8.2-2 SCSCPreset</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SCSCPreset</code>( )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: nothing</p>
<p>If an error occurs during a call of <code class="func">ParQuickWithSCSCP</code> (<a href="chap8.html#X8783850E81463D0F"><span class="RefLink">8.1-4</span></a>) and <code class="func">ParListWithSCSCP</code> (<a href="chap8.html#X788208B57D4C497F"><span class="RefLink">8.2-1</span></a>), some of parallel requests may be still running at the remaining services, making them inaccessible for further procedure calls. <code class="func">SCSCPreset</code> resets them by closing all open streams to <strong class="pkg">SCSCP</strong> servers.</p>
<p><a id="X84ACC8B4800D0E34" name="X84ACC8B4800D0E34"></a></p>
<h5>8.2-3 SCSCPLogTracesToGlobal</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SCSCPLogTracesToGlobal</code>( <var class="Arg">testname</var> )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SCSCPLogTracesToGlobal</code>( )</td><td class="tdright">( function )</td></tr></table></div>
<p>To analyse the performance of parallel <strong class="pkg">SCSCP</strong> framework, we make use of the <strong class="pkg">EdenTV</strong> program <a href="chapBib.html#biBEdenTV">[BL07]</a> developed initially to visualize the performance of parallel programs written in functional programming language Eden, and now distributed under the GNU Public License and available from <span class="URL"><a href="http://www.mathematik.uni-marburg.de/~eden/?content=EdenTV">http://www.mathematik.uni-marburg.de/~eden/?content=EdenTV</a></span>.</p>
<p>Called with the string containing the name of the test, this functions turns on writing information about key activity events into trace files in current directories for the client and servers listed <code class="func">SCSCPservers</code> (<a href="chap8.html#X7CDA73307ABE9998"><span class="RefLink">8.1-3</span></a>). The trace file will have the name of the format <var class="Arg">testname</var><code class="code">.client.tr</code> for the client and <var class="Arg">testname</var><code class="code">.<hostname>.<port>.tr</code> for the server. After the test these files should be collected from remote servers and concatenated (e.g. using <code class="file">cat</code>) together with the standard preamble from the file <code class="file">scscp/tracing/stdhead.txt</code> (we recommend to put after the preamble first all traces from servers and then the client's traces to have nicer diagrams). The resulting file then may be opened with <strong class="pkg">EdenTV</strong>.</p>
<p>In the following example we use a dual core MacBook laptop to generate trace files for two tests and then show their corresponding trace diagrams:</p>
<div class="example"><pre>
SCSCPLogTracesToGlobal("quillen100");
ParListWithSCSCP( List( [1..100], i->[512,i]), "QuillenSeriesByIdGroup" );
SCSCPLogTracesToGlobal();
SCSCPLogTracesToGlobal( "euler" );
ParListWithSCSCP( [1..1000], "WS_Phi" );
SCSCPLogTracesToGlobal();
</pre></div>
<p><img src="img/quillen.jpg" align="left" /> <img src="img/euler.jpg" align="left" /> The diagrams (made on an dual core MacBook laptop), shows that in the first case parallelising is efficient and master successfully distributes load to workers, while in the second case a single computation is just too short, so most of the time is spent on communication. To parallelize the Euler's function example efficiently, tasks must rather be grouped in chunks, which should be enough large to reduce the communication overload, but enough small to ensure that tasks are evenly distributed.</p>
<p>Of course, tracing can be used to investigate communication between a client and a single server in a non-parallel context as well. For this purpose, <code class="func">SCSCPservers</code> (<a href="chap8.html#X7CDA73307ABE9998"><span class="RefLink">8.1-3</span></a>) must be modified to contain only one server.</p>
<p><code class="func">ParListWithSCSCP</code> (<a href="chap8.html#X788208B57D4C497F"><span class="RefLink">8.2-1</span></a>) can be easily modified to have parallel versions of other list operations like <code class="func">ForAll</code> (<span class="RefLink">Reference: ForAll</span>), <code class="func">ForAny</code> (<span class="RefLink">Reference: ForAny</span>), <code class="func">First</code> (<span class="RefLink">Reference: First</span>), <code class="func">Number</code> (<span class="RefLink">Reference: Number</span>), <code class="func">Filtered</code> (<span class="RefLink">Reference: Filtered</span>), and also to have the skeleton in which the queue may be modified during the computation (for example, to compute orbits). We plan to provide such tools in one of the next versions of the package.</p>
<p><a id="X78C5AEA07F961325" name="X78C5AEA07F961325"></a></p>
<h4>8.3 <span class="Heading">Example: parallelising Karatsuba multiplication for polynomials</span></h4>
<p>The file <code class="file">scscp/example/karatsuba.g</code> contains an implementation of the Karatsuba multiplication algorithm for polynomials. This algorithm can be easily parallelized since each recursive step creates three recursive calls of the same function for other polynomials. <em>We will not parallelize each</em> recursive call, since this will create enormous data flow. Instead of this we parallelize only the top-level function. For our experiments with parallelising Karatsuba multiplication for polynomials with integer coefficients we used the multi-core workstation, on which we started one <strong class="pkg">SCSCP</strong> client and two <strong class="pkg">SCSCP</strong> servers. To use it, modify the server configuration file adding to it the command to read the file <code class="file">scscp/example/karatsuba.g</code>, then define there the following function</p>
<div class="example"><pre>
KaratsubaPolynomialMultiplicationExtRepByString:=function(s1,s2)
return String( KaratsubaPolynomialMultiplicationExtRep(
EvalString(s1), EvalString(s2) ) );
end;;
</pre></div>
<p>and finally add the following lines to made it available as an <strong class="pkg">SCSCP</strong> procedure under the name <code class="code">WS_Karatsuba</code>:</p>
<div class="example"><pre>
InstallSCSCPprocedure( "WS_Karatsuba",
KaratsubaPolynomialMultiplicationExtRepByString);
</pre></div>
<p>(we do not include it into the default <code class="file">scscp/example/myserver.g</code> since the code contains a call to <code class="func">EvalString</code> (<span class="RefLink">Reference: EvalString</span>)).</p>
<p>This function provides a "bridge" between the client's function <code class="code">KaratsubaPolynomialMultiplicationWS</code> and the server's function <code class="code">KaratsubaPolynomialMultiplicationExtRep</code>, which performs the actual work on the server. <code class="code">WS_Karatsuba</code> converts its string arguments into internal representation of univariate polynomials (basically, lists of integers) and then converts the result back into string (since such data exchange format was chosen). We are going to parallelize the following part of the client's code:</p>
<div class="example"><pre>
...
u := KaratsubaPolynomialMultiplicationExtRep(f1,g1);
v := KaratsubaPolynomialMultiplicationExtRep(f0,g0);
w := KaratsubaPolynomialMultiplicationExtRep(
PlusLaurentPolynomialsExtRep(f1,f0),
PlusLaurentPolynomialsExtRep(g1,g0) );
...
</pre></div>
<p>and this can be done straightforwardly - we replace two first calls by calls of the appropriate <strong class="pkg">SCSCP</strong> services, then perform the 3rd call locally and then collect the results from the two remote calls:</p>
<div class="example"><pre>
...
u := NewProcess( "WS_Karatsuba",[ String(f1), String(g1) ],"localhost", 26133);
v := NewProcess( "WS_Karatsuba",[ String(f0), String(g0) ],"localhost", 26134);
w := KaratsubaPolynomialMultiplicationExtRep(
PlusLaurentPolynomialsExtRep(f1,f0),
PlusLaurentPolynomialsExtRep(g1,g0) );
wsresult:=SynchronizeProcesses2( u,v );
u := EvalString( wsresult[1].object );
v := EvalString( wsresult[2].object );
...
</pre></div>
<p>We obtain almost double speedup on three cores on randomly generated polynomials of degree 32000:</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">ReadPackage("scscp/example/karatsuba.g");</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">fam:=FamilyObj(1);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">f:=LaurentPolynomialByCoefficients( fam, </span>
<span class="GAPprompt">></span> <span class="GAPinput"> List([1..32000],i->Random(Integers)), 0, 1 );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">g:=LaurentPolynomialByCoefficients( fam, </span>
<span class="GAPprompt">></span> <span class="GAPinput"> List([1..32000],i->Random(Integers)), 0, 1 );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">t2:=KaratsubaPolynomialMultiplication(f,g);;time;</span>
5892
<span class="GAPprompt">gap></span> <span class="GAPinput">t3:=KaratsubaPolynomialMultiplicationWS(f,g);;time;</span>
2974
</pre></div>
<div class="chlinkprevnextbot"> <a href="chap0.html">[Top of Book]</a> <a href="chap0.html#contents">[Contents]</a> <a href="chap7.html">[Previous Chapter]</a> <a href="chap9.html">[Next Chapter]</a> </div>
<div class="chlinkbot"><span class="chlink1">Goto Chapter: </span><a href="chap0.html">Top</a> <a href="chap1.html">1</a> <a href="chap2.html">2</a> <a href="chap3.html">3</a> <a href="chap4.html">4</a> <a href="chap5.html">5</a> <a href="chap6.html">6</a> <a href="chap7.html">7</a> <a href="chap8.html">8</a> <a href="chap9.html">9</a> <a href="chapBib.html">Bib</a> <a href="chapInd.html">Ind</a> </div>
<hr />
<p class="foot">generated by <a href="http://www.math.rwth-aachen.de/~Frank.Luebeck/GAPDoc">GAPDoc2HTML</a></p>
</body>
</html>
|