File: chap15.txt

package info (click to toggle)
gap-hap 1.74%2Bds-1
  • links: PTS
  • area: main
  • in suites: forky, sid
  • size: 58,664 kB
  • sloc: xml: 16,678; sh: 197; javascript: 155; makefile: 121; ansic: 47; perl: 24
file content (137 lines) | stat: -rw-r--r-- 6,990 bytes parent folder | download | duplicates (2) 
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
 
  
  15 Parallel computation
  
  
  15.1 An embarassingly parallel computation
  
  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, Z)= 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 .
  
    Example  
    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 ]
    
  
  
  The  function  ParallelList()  is  built  from  HAP's six core functions for
  parallel computation.
  
  
  15.2 A non-embarassingly parallel computation
  
  The  following  commands use core functions to compute the product A=M× N of
  two random matrices by distributing the work over two processors.
  
    Example  
    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
    
  
  
  The  next  commands  compute  the  product  A=M× 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.
  
    Example  
    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
    
  
  
  
  15.3 Parallel persistent homology
  
  Section  5.8  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.
  
    Example  
    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