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 .
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.
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.
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\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.
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
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.
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
Here is a story of naive implementation design causing a serial algorithm to run at least 170 times slower than it should!
The following snippet begins with the construction of a regular CW-complex \(Y\) with 157539 cells. It then constructs the cellular chain complex \(C_\ast=C_\ast(Y)\). Computing the homology of \(Y\) directly from \(C_\ast\) would be time consuming due to the large number of cells in \(Y\). So, an elementary procedure is used to eliminate redundant generators from \(Y\) in order to obtain a smaller quasi-isomorphic chain complex \(D_\ast\) and this smaller complex is used to quickly obtain the homology. However, the construction of \(D_\ast\) takes over 170 seconds.
gap> K:=ContractibleGcomplex("SL(3,Z)s");; gap> G:=HAPCongruenceSubgroupGamma0(3,101);; gap> Y:=GComplexToRegularCWComplex(K,G);; gap> C:=ChainComplexOfRegularCWComplex(Y); Chain complex of length 3 in characteristic 0 . gap> List([0..3],C!.dimension); [ 3679, 37565, 75083, 41212 ] gap> D:=ContractedComplex(C);time; Chain complex of length 3 in characteristic 0 . 170547 gap> List([0..3],D!.dimension); [ 1, 27, 78, 67 ] gap> List([0..3],n->Homology(D,n));time; [ [ 0 ], [ 25 ], [ 2, 2, 2, 2, 2 ], [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ] ] 26
The above procedure for reducing the number of generators in a chain complex of free abelian groups uses the same elementary technique for "generator removal" as a slightly more elaborate implementation programmed some years earlier. The earlier implementation is (unnecessarily) restricted to chain complexes arising as cellular chain complexes of regular CW-complexes while the later implemetation is aimed at arbitrary chain complexes of free abelian groups. The earlier implementation returns chain homotopy equivalences between the original and the simplified complexes. To ease the the coding of the later implementation it was decided to output just the simplified chain complex and forget about the chain maps yielding the chain equivalence.
The following snippet illustrates the earlier implementation. It again begins with the construction of the regular CW-complex \(Y\) with 157539 cells. It then takes just over a second to construct a pair of chain equivalences \(f_1\colon C_\ast(Y) \rightarrow C_\ast(Y')\) and \(f_2\colon C_\ast(Y') \rightarrow C_\ast(Y)\) with \(Y'\) a homotopy equivalent non-regular CW-complex with fewer cells. It uses \(D_\ast=C_\ast(Y')\) to quickly compute the homology of \(Y\).
gap> K:=ContractibleGcomplex("SL(3,Z)s");; gap> G:=HAPCongruenceSubgroupGamma0(3,101);; gap> Y:=GComplexToRegularCWComplex(K,G);; gap> f:=ChainComplexEquivalenceOfRegularCWComplex(Y);time; [ Chain Map between complexes of length 3 . , Chain Map between complexes of length 3 . ] 1192 gap> C:=Source(f[1]); Chain complex of length 3 in characteristic 0 . gap> List([0..3],C!.dimension); [ 3679, 37565, 75083, 41212 ] gap> D:=Target(f[1]); Chain complex of length 3 in characteristic 0 . gap> List([0..3],D!.dimension); [ 4, 15, 29, 33 ] gap> List([0..3],n->Homology(D,n));time; [ [ 0 ], [ 25 ], [ 2, 2, 2, 2, 2 ], [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ] ] 211
The takeaway from this story is that careful design of the datatypes to be used in the implementation of an algorithm can significantly impact the speed of the implementation! This is a well established principle, illustrated forcefully by the story. The decision to output chain maps \(C_\ast \leftrightarrow D_\ast\) leads to an implementation where all redundant generators in \(C_\ast\) first have to be identified, and enough information has to be retained to produce the chain maps. The later decision to output just the complex \(D_\ast\) leads to an easier to implement process of eliminating each redundant generator in a boundary matrix as soon at it is found. This is analogous to a gaussian elimination procedure for producing echelon form that updates a boundary matrix each time a suitable pivot is found; it is easy to code but less efficient than the earlier implementation.
A new implementation of ContractedComplex(C) is on the HAP to-do list.
generated by GAPDoc2HTML