Ziele Untersuchung
mit Columbo Integrität von
Datenbanken Interaktion und
Portierbarkeit Ergonomie der
Schnittstellen

Angebot Produkte Projekt Beratung

Mittel Analytik Modellierung Sprachen Algebra Logik Hardware Denken Kreativität

Zusammenhänge Gesellschaft Wirtschaft Branche Firma


products/Sources/formale Sprachen/GAP/pkg/hap/tutorial/ (Algebra von RWTH Aachen Version 4.15.1^©) Datei vom 19.6.2025 mit Größe 11 kB

SSL chap15_mj.html Sprache: HTML

products/Sources/formale Sprachen/GAP/pkg/hap/tutorial/chap15_mj.html

<?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>
<script type="text/javascript"
 src="https://cdn.jsdelivr.net/npm/mathjax@2/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>
<title>GAP (HAP commands) - Chapter 15: Parallel computation</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="chap15" onload="jscontent()">

<div class="chlinktop">Goto Chapter: <a href="chap0_mj.html">Top</a> <a href="chap1_mj.html">1</a> <a href="chap2_mj.html">2</a> <a href="chap3_mj.html">3</a> <a href="chap4_mj.html">4</a> <a href="chap5_mj.html">5</a> <a href="chap6_mj.html">6</a> <a href="chap7_mj.html">7</a> <a href="chap8_mj.html">8</a> <a href="chap9_mj.html">9</a> <a href="chap10_mj.html">10</a> <a href="chap11_mj.html">11</a> <a href="chap12_mj.html">12</a> <a href="chap13_mj.html">13</a> <a href="chap14_mj.html">14</a> <a href="chap15_mj.html">15</a> <a href="chap16_mj.html">16</a> <a href="chapBib_mj.html">Bib</a> <a href="chapInd_mj.html">Ind</a> </div>

<div class="chlinkprevnexttop"> <a href="chap0_mj.html">[Top of Book]</a> <a href="chap0_mj.html#contents">[Contents]</a> <a href="chap14_mj.html">[Previous Chapter]</a> <a href="chap16_mj.html">[Next Chapter]</a> </div>

<a href="chap15.html">[MathJax off]</a>
<a id="X7F571E8F7BBC7514" name="X7F571E8F7BBC7514"></a>
<div class="ChapSects"><a href="chap15_mj.html#X7F571E8F7BBC7514">15 Parallel computation</a>
<div class="ContSect"> <a href="chap15_mj.html#X7EAE286B837D27BA">15.1 An embarassingly parallel computation</a>

</div>
<div class="ContSect"> <a href="chap15_mj.html#X80F359DD7C54D405">15.2 A non-embarassingly parallel computation</a>

</div>
<div class="ContSect"> <a href="chap15_mj.html#X8496786F7FCEC24A">15.3 Parallel persistent homology</a>

</div>
</div>

<h3>15 Parallel computation</h3>

<a id="X7EAE286B837D27BA" name="X7EAE286B837D27BA"></a>

<h4>15.1 An embarassingly parallel computation</h4>

The following example creates fifteen child processes and uses them simultaneously to compute the second integral homology of each of the \(2328\) groups of order \(128\). The final command shows that

\(H_2(G,\mathbb Z)=\mathbb Z_2^{21}\)

for the \(2328\)-th group \(G\) in GAP's library of small groups. The penulimate command shows that the parallel computation achieves a speedup of 10.4 .

<div class="example"><pre>
gap> Processes:=List([1..15],i->ChildProcess());;
gap> fn:=function(i);return GroupHomology(SmallGroup(128,i),2);end;;
gap> for p in Processes do
> ChildPut(fn,"fn",p);
> od;
gap> Exec("date +%s");L:=ParallelList([1..2328],"fn",Processes);;Exec("date +%s");
1716105545
1716105554
gap> Exec("date +%s");L1:=List([1..2328],fn);;Exec("date +%s");
1716105586
1716105680

gap> speedup:=1.0*(680-586)/(554-545);
10.4444

gap> L[2328];
[ 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2 ]

</pre></div>

The function <code class="code">ParallelList()</code> is built from HAP's six core functions for parallel computation.

<a id="X80F359DD7C54D405" name="X80F359DD7C54D405"></a>

<h4>15.2 A non-embarassingly parallel computation</h4>

The following commands use core functions to compute the product \(A=M\times N\) of two random matrices by distributing the work over two processors.

<div class="example"><pre>
gap> M:=RandomMat(10000,10000);;
gap> N:=RandomMat(10000,10000);;
gap> 
gap> s:=ChildProcess();;
gap> 
gap> Exec("date +%s");
1716109418
gap> Mtop:=M{[1..5000]};;
gap> Mbottom:=M{[5001..10000]};;
gap> ChildPut(Mtop,"Mtop",s);
gap> ChildPut(N,"N",s);
gap> NextAvailableChild([s]);;
gap> ChildCommand("Atop:=Mtop*N;;",s);;
gap> Abottom:=Mbottom*N;;
gap> A:=ChildGet("Atop",s);;
gap> Append(A,Abottom);;
gap> Exec("date +%s");
1716110143

gap> AA:=M*N;;Exec("date +%s");
1716111389

gap> speedup:=1.0*(111389-110143)/(110143-109418);
1.71862

</pre></div>

The next commands compute the product \(A=M\times N\) of two random matrices by distributing the work over fifteen processors. The parallelization is very naive (the entire matrices \(M\) and \(N\) are communicated to all processes) and the computation achieves a speedup of 7.6.

<div class="example"><pre>
gap> M:=RandomMat(15000,15000);;
gap> N:=RandomMat(15000,15000);;
gap> S:=List([1..15],i->ChildCreate());;

gap> Exec("date +%s");
1716156583
gap> ChildPutObj(M,"M",S);
gap> ChildPutObj(N,"N",S);
gap> for i in [1..15] do
> cmd:=Concatenation("A:=M{[1..1000]+(",String(i),"-1)*1000}*N;");
> ChildCommand(cmd,S[i]);
> od;
gap> A:=[];;
gap> for i in [1..15] do
> C:=ChildGet("A",S[i]);
> Append(A,C);
> od;
gap> Exec("date +%s");
1716157489

gap> AA:=M*N;;Exec("date +%s");
1716164405

gap> speedup:=1.0*(64405-57489)/(57489-56583);
7.63355

</pre></div>

<a id="X8496786F7FCEC24A" name="X8496786F7FCEC24A"></a>

<h4>15.3 Parallel persistent homology</h4>

Section <a href="chap5_mj.html#X7D2CC9CB85DF1BAF">5.8</a> illustrates an alternative method of computing the persitent Betti numbers of a filtered pure cubical complex. The method lends itself to parallelisation. However, the following parallel computation of persistent Betti numbers achieves only a speedup of \(1.5\) due to a significant time spent transferring data structures between processes. On the other hand, the persistent Betti function could be used to distribute computations over several computers. This might be useful for larger computations that require significant memory resources.

<div class="example"><pre>
gap> file:=HapFile("data247.txt");;
gap> Read(file);;
gap> F:=ThickeningFiltration(T,25);;
gap> S:=List([1..15],i->ChildCreate());;
gap> N:=[0,1,2];;
gap> Exec("date +%s");P:=ParallelPersistentBettiNumbers(F,N,S);;Exec("date +%s");
1717160785
1717161285

gap> Exec("date +%s");Q:=PersistentBettiNumbersAlt(F,N);;Exec("date +%s");
1717161528
1717162276
gap> speedup:=1.0*(1717162276-1717161528)/(1717161285-1717160785);
1.496

</pre></div>

<div class="chlinkprevnextbot"> <a href="chap0_mj.html">[Top of Book]</a> <a href="chap0_mj.html#contents">[Contents]</a> <a href="chap14_mj.html">[Previous Chapter]</a> <a href="chap16_mj.html">[Next Chapter]</a> </div>

<div class="chlinkbot">Goto Chapter: <a href="chap0_mj.html">Top</a> <a href="chap1_mj.html">1</a> <a href="chap2_mj.html">2</a> <a href="chap3_mj.html">3</a> <a href="chap4_mj.html">4</a> <a href="chap5_mj.html">5</a> <a href="chap6_mj.html">6</a> <a href="chap7_mj.html">7</a> <a href="chap8_mj.html">8</a> <a href="chap9_mj.html">9</a> <a href="chap10_mj.html">10</a> <a href="chap11_mj.html">11</a> <a href="chap12_mj.html">12</a> <a href="chap13_mj.html">13</a> <a href="chap14_mj.html">14</a> <a href="chap15_mj.html">15</a> <a href="chap16_mj.html">16</a> <a href="chapBib_mj.html">Bib</a> <a href="chapInd_mj.html">Ind</a> </div>

<hr />
generated by <a href="https://www.math.rwth-aachen.de/~Frank.Luebeck/GAPDoc">GAPDoc2HTML</a>
</body>
</html>

quality100%

¤ Dauer der Verarbeitung: 0.19 Sekunden (vorverarbeitet) ¤

Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.