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
|
<?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 (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"><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="chap10.html">10</a> <a href="chap11.html">11</a> <a href="chap12.html">12</a> <a href="chap13.html">13</a> <a href="chap14.html">14</a> <a href="chap15.html">15</a> <a href="chap16.html">16</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="chap14.html">[Previous Chapter]</a> <a href="chap16.html">[Next Chapter]</a> </div>
<p id="mathjaxlink" class="pcenter"><a href="chap15_mj.html">[MathJax on]</a></p>
<p><a id="X7F571E8F7BBC7514" name="X7F571E8F7BBC7514"></a></p>
<div class="ChapSects"><a href="chap15.html#X7F571E8F7BBC7514">15 <span class="Heading">Parallel computation</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap15.html#X7EAE286B837D27BA">15.1 <span class="Heading">An embarassingly parallel computation</span></a>
</span>
</div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap15.html#X80F359DD7C54D405">15.2 <span class="Heading">A non-embarassingly parallel computation</span></a>
</span>
</div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap15.html#X8496786F7FCEC24A">15.3 <span class="Heading">Parallel persistent homology</span></a>
</span>
</div>
</div>
<h3>15 <span class="Heading">Parallel computation</span></h3>
<p><a id="X7EAE286B837D27BA" name="X7EAE286B837D27BA"></a></p>
<h4>15.1 <span class="Heading">An embarassingly parallel computation</span></h4>
<p>The following example creates fifteen child processes and uses them simultaneously to compute the second integral homology of each of the <span class="SimpleMath">2328</span> groups of order <span class="SimpleMath">128</span>. The final command shows that</p>
<p><span class="SimpleMath">H_2(G, Z)= Z_2^21</span></p>
<p>for the <span class="SimpleMath">2328</span>-th group <span class="SimpleMath">G</span> in <strong class="button">GAP</strong>'s library of small groups. The penulimate command shows that the parallel computation achieves a speedup of 10.4 .</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">Processes:=List([1..15],i->ChildProcess());;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">fn:=function(i);return GroupHomology(SmallGroup(128,i),2);end;;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">for p in Processes do</span>
<span class="GAPprompt">></span> <span class="GAPinput">ChildPut(fn,"fn",p);</span>
<span class="GAPprompt">></span> <span class="GAPinput">od;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Exec("date +%s");L:=ParallelList([1..2328],"fn",Processes);;Exec("date +%s");</span>
1716105545
1716105554
<span class="GAPprompt">gap></span> <span class="GAPinput">Exec("date +%s");L1:=List([1..2328],fn);;Exec("date +%s");</span>
1716105586
1716105680
<span class="GAPprompt">gap></span> <span class="GAPinput">speedup:=1.0*(680-586)/(554-545);</span>
10.4444
<span class="GAPprompt">gap></span> <span class="GAPinput">L[2328];</span>
[ 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2 ]
</pre></div>
<p>The function <code class="code">ParallelList()</code> is built from <strong class="button">HAP</strong>'s six core functions for parallel computation.</p>
<p><a id="X80F359DD7C54D405" name="X80F359DD7C54D405"></a></p>
<h4>15.2 <span class="Heading">A non-embarassingly parallel computation</span></h4>
<p>The following commands use core functions to compute the product <span class="SimpleMath">A=M× N</span> of two random matrices by distributing the work over two processors.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">M:=RandomMat(10000,10000);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">N:=RandomMat(10000,10000);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput"></span>
<span class="GAPprompt">gap></span> <span class="GAPinput">s:=ChildProcess();;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput"></span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Exec("date +%s");</span>
1716109418
<span class="GAPprompt">gap></span> <span class="GAPinput">Mtop:=M{[1..5000]};;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Mbottom:=M{[5001..10000]};;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">ChildPut(Mtop,"Mtop",s);</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">ChildPut(N,"N",s);</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">NextAvailableChild([s]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">ChildCommand("Atop:=Mtop*N;;",s);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Abottom:=Mbottom*N;;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">A:=ChildGet("Atop",s);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Append(A,Abottom);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Exec("date +%s");</span>
1716110143
<span class="GAPprompt">gap></span> <span class="GAPinput">AA:=M*N;;Exec("date +%s");</span>
1716111389
<span class="GAPprompt">gap></span> <span class="GAPinput">speedup:=1.0*(111389-110143)/(110143-109418);</span>
1.71862
</pre></div>
<p>The next commands compute the product <span class="SimpleMath">A=M× N</span> of two random matrices by distributing the work over fifteen processors. The parallelization is very naive (the entire matrices <span class="SimpleMath">M</span> and <span class="SimpleMath">N</span> are communicated to all processes) and the computation achieves a speedup of 7.6.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">M:=RandomMat(15000,15000);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">N:=RandomMat(15000,15000);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">S:=List([1..15],i->ChildCreate());;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Exec("date +%s");</span>
1716156583
<span class="GAPprompt">gap></span> <span class="GAPinput">ChildPutObj(M,"M",S);</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">ChildPutObj(N,"N",S);</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">for i in [1..15] do</span>
<span class="GAPprompt">></span> <span class="GAPinput">cmd:=Concatenation("A:=M{[1..1000]+(",String(i),"-1)*1000}*N;");</span>
<span class="GAPprompt">></span> <span class="GAPinput">ChildCommand(cmd,S[i]);</span>
<span class="GAPprompt">></span> <span class="GAPinput">od;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">A:=[];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">for i in [1..15] do</span>
<span class="GAPprompt">></span> <span class="GAPinput"> C:=ChildGet("A",S[i]);</span>
<span class="GAPprompt">></span> <span class="GAPinput"> Append(A,C);</span>
<span class="GAPprompt">></span> <span class="GAPinput">od;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Exec("date +%s");</span>
1716157489
<span class="GAPprompt">gap></span> <span class="GAPinput">AA:=M*N;;Exec("date +%s");</span>
1716164405
<span class="GAPprompt">gap></span> <span class="GAPinput">speedup:=1.0*(64405-57489)/(57489-56583);</span>
7.63355
</pre></div>
<p><a id="X8496786F7FCEC24A" name="X8496786F7FCEC24A"></a></p>
<h4>15.3 <span class="Heading">Parallel persistent homology</span></h4>
<p>Section <a href="chap5.html#X7D2CC9CB85DF1BAF"><span class="RefLink">5.8</span></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 <span class="SimpleMath">1.5</span> 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.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">file:=HapFile("data247.txt");;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Read(file);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">F:=ThickeningFiltration(T,25);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">S:=List([1..15],i->ChildCreate());;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">N:=[0,1,2];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Exec("date +%s");P:=ParallelPersistentBettiNumbers(F,N,S);;Exec("date +%s");</span>
1717160785
1717161285
<span class="GAPprompt">gap></span> <span class="GAPinput">Exec("date +%s");Q:=PersistentBettiNumbersAlt(F,N);;Exec("date +%s");</span>
1717161528
1717162276
<span class="GAPprompt">gap></span> <span class="GAPinput">speedup:=1.0*(1717162276-1717161528)/(1717161285-1717160785);</span>
1.496
</pre></div>
<div class="chlinkprevnextbot"> <a href="chap0.html">[Top of Book]</a> <a href="chap0.html#contents">[Contents]</a> <a href="chap14.html">[Previous Chapter]</a> <a href="chap16.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="chap10.html">10</a> <a href="chap11.html">11</a> <a href="chap12.html">12</a> <a href="chap13.html">13</a> <a href="chap14.html">14</a> <a href="chap15.html">15</a> <a href="chap16.html">16</a> <a href="chapBib.html">Bib</a> <a href="chapInd.html">Ind</a> </div>
<hr />
<p class="foot">generated by <a href="https://www.math.rwth-aachen.de/~Frank.Luebeck/GAPDoc">GAPDoc2HTML</a></p>
</body>
</html>
|
