Quelle aboutParallel.html Sprache: HTML

products/sources/formale Sprachen/GAP/pkg/hap/www/SideLinks/About/aboutParallel.html

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
 <meta http-equiv="content-type"
content="text/html; charset=ISO-8859-1">
 <title>AboutHap</title>
</head>
<body
style="color: rgb(0, 0, 153); background-color: rgb(204, 255, 255);"
link="#000066" vlink="#000066" alink="#000066">
 
<table
style="text-align: left; margin-left: auto; margin-right: auto; color: rgb(0, 0, 102);"
border="0" cellpadding="20" cellspacing="10">
 <tbody>
 <tr align="center">
 <th style="vertical-align: top;">
 <table style="width: 100%; text-align: left;" cellpadding="2"
cellspacing="2">
 <tbody>
 <tr>
 <td style="vertical-align: top;"><a href="aboutTDA.html">Previous</a> 
 </td>
 <td
style="text-align: center; vertical-align: top; color: rgb(0, 0, 102);"><big>About HAP: Parallel Computation 
 </big></td>
 <td style="text-align: right; vertical-align: top;"><a
href="aboutAbelianCategories.html">next</a> 
 </td>
 </tr>
 </tbody>
 </table>
 <big></big> 
 </th>
 </tr>
 <tr>
 <td
style="vertical-align: top; background-color: rgb(255, 255, 255); text-align: left;">Homological
computations
can require much time and memory. In principle,
many of the computations can be distributed in fairly obvious ways over
several processors on one or more PCs.
HAP contains a few basic functions for achieving this. 
 </td>
 </tr>
 <tr>
 <td
style="vertical-align: top; background-color: rgb(255, 255, 255);">The
following commands compute the third integral homology groups of the
fourteen groups of order 16 using two child processes. The first child
is on the
local machine and the second child is on a remote machine for which ssh
has been configured to require no password. This is an example of
"trivial parallelism". On a multiprocessor
machine distinct child processes would normally automatically
be assigned to different processors. 
 </td>
 </tr>
 <tr>
 <td
style="background-color: rgb(255, 255, 204); vertical-align: top;">gap>
s:=ChildProcess();; 
gap> t:=ChildProcess("alberti.vlan.nuigalway.ie");; 
 
gap>
ChildCommand("Odd:=List([1,3,5,7,9,11,13],i->GroupHomology(SmallGroup(16,i),3));",s); 
gap>
ChildCommand("Even:=List([2,4,6,8,10,12,14],i->GroupHomology(SmallGroup(16,i),3));",t); 
gap> ODD:=ChildGet("Odd",s);; 
gap> EVEN:=ChildGet("Even",t);; 
 
gap> for i in [1..7] do 
gap> Print("Group ",2*i-1," has third homology ",ODD[i],"\n"); 
gap> Print("Group ",2*i," has third homology ",EVEN[i],"\n"); 
gap> od; 
 
Group 1 has third homology [ 16 ] 
Group 2 has third homology [ 4, 4, 4 ] 
Group 3 has third homology [ 2, 2, 4, 4 ] 
Group 4 has third homology [ 2, 4, 4 ] 
Group 5 has third homology [ 2, 2, 8 ] 
Group 6 has third homology [ 2, 8 ] 
Group 7 has third homology [ 2, 2, 8 ] 
Group 8 has third homology [ 2, 8 ] 
Group 9 has third homology [ 16 ] 
Group 10 has third homology [ 2, 2, 2, 2, 2, 2, 4 ] 
Group 11 has third homology [ 2, 2, 2, 2, 2, 2, 4 ] 
Group 12 has third homology [ 2, 2, 2, 8 ] 
Group 13 has third homology [ 2, 2, 2, 8 ] 
Group 14 has third homology [ 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2 ] 
 </td>
 </tr>
 <tr>
 <td
style="vertical-align: top; background-color: rgb(255, 255, 255);">A
weakness with the above parallel computation is that the naive
distribution of tasks over the two child processes might result in one
process being finished long before the other. The command
NextAvailableChild() can be used to overcome this problem.
Alternatively, the function ParallelList() can be used. 
 
The following commands, on a two-processor IBM laptop, show that
parallel computation can halve the time to compute the second homology
of the groups of order 128. 
 </td>
 </tr>
 <tr>
 <td
style="vertical-align: top; background-color: rgb(255, 255, 204);">gap>
s:=ChildProcess();; 
gap> t:=ChildProcess();; 
gap> fn:=function(i);return
GroupHomology(SmallGroup(128,i),2);end; 
gap> ChildPut( fn, "fn", s); 
gap> ChildPut( fn, "fn", t); 
 
gap> Exec("date"); 
Sat Oct 6 23:52:55 IST 2007 
gap> Lparallel:=ParallelList([1..2328],"fn",[s,t]);; 
gap> Exec("date"); 
Sun Oct 7 00:00:37 IST 2007 
gap> L:=List([1..2328], fn);; 
gap> Exec("date"); 
Sun Oct 7 00:14:07 IST 2007 
 </td>
 </tr>
 <tr>
 <td
style="vertical-align: top; background-color: rgb(255, 255, 255);">The
following commands illustrate a naive parallel computation of the
product A=M*N of two random matrices M and N. The computation involves
just one child and takes 64% of the time needed for the standard
sequential
calculation of M*N. 
 </td>
 </tr>
 <tr>
 <td
style="vertical-align: top; background-color: rgb(255, 255, 204);">gap>
M:=RandomMat(2000,2000);;
#Two
random matrices. 
gap> N:=RandomMat(2000,2000);; 
 
gap> s:=ChildProcess();; 
 
gap> Exec("date"); 
Tue Nov 27 05:17:55 GMT 2007 
gap>
Mtop:=M{[1..1000]};;
#Splitting
the first matrix in two 
gap> Mbottom:=M{[1001..2000]};; 
 
gap>
ChildPut(Mtop,"Mtop",s);
#Transferring
data to the child. 
gap> ChildPut(N,"N",s); 
gap> NextAvailableChild([s]);; 
 
gap>
ChildCommand("Atop:=Mtop*N;;",s);;
#Matrix multiplication on child. 
gap>
Abottom:=Mbottom*N;;
#Matrix
multiplication on parent. 
gap> A:=ChildGet("Atop",s);; 
gap>
Append(A,Abottom);;
#A
is the product M*N. 
gap> Exec("date"); 
Tue Nov 27 05:18:47 GMT 2007 
 </td>
 </tr>
 <tr>
 <td
style="vertical-align: top; background-color: rgb(255, 255, 255);">The
parallel multiplication took 52 seconds on a two-processor IBM laptop,
compared to 81 seconds below for multiplication on a single processor.
This is a speedup factor of 0.64 . 
 </td>
 </tr>
 <tr>
 <td
style="vertical-align: top; background-color: rgb(255, 255, 204);">gap>
Exec("date");M*N;;Exec("date"); 
Tue Nov 27 05:13:56 GMT 2007 
Tue Nov 27 05:15:17 GMT 2007 
 </td>
 </tr>
 <tr>
 <td
style="vertical-align: top; background-color: rgb(255, 255, 255);">The
following commands show how two processors could be used to compute H8(G,Z)
for
the group G=SmallGroup(512,1201). The commands begin with the
definition of the function 
 
 <div style="text-align: center;">ParallelResolution(G,N,n,t). 
 </div>
 
Unfortunately, this example is too naive: the loads on the two
processors is extremely unbalanced. 
 </td>
 </tr>
 <tr>
 <td
style="vertical-align: top; background-color: rgb(255, 255, 204);">################################################# 
ParallelResolution:=function(G,N,n,t) 
local 
 R,S,T,nat,iso; 
 

nat:=NaturalHomomorphismByNormalSubgroup(G,N); 

iso:=IsomorphismPermGroup(N);
#HAPPrintTo()
and HAPRead() will only work with 

ChildPut(n,"n",t);
#permutation
or matrix groups. 
 ChildPut(Image(iso),"N",t); 

ChildCommand("R:=ResolutionFiniteGroup(N,n);",t); 

ChildCommand("HAPPrintTo(\"/tmp/test\",R);",t); 
 

S:=ResolutionFiniteGroup(Image(nat),n); 
 
 while not
IsAvailableChild(t)
do
#This
should ensure that the next command is 

od;
#not
processed too soon! 
 
 R:=HAPRead("/tmp/test"); 
 R!.group:=N; 

R!.elts:=List(R!.elts,x->PreImagesRepresentative(iso,x)); 
 
 T:=ResolutionFiniteExtension( 

GeneratorsOfGroup(G), 

List(GeneratorsOfGroup(G),x->Image(nat,x)), 

S,n,false,R); 
 return T; 
end; 
################################################# 
 
 
G:=SmallGroup(512,1201);; 
phi:=NaturalHomomorphismByNormalSubgroup(G,Centre(G));; 
t:=ChildProcess();; 
T:=ParallelResolution(G,Centre(G),9,t);; 
C:=TensorWithIntegers(T);; 
 
Homology(C,8); 
[ 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 4, 4, 4, 8 ] 
 </td>
 </tr>
 <tr>
 <td style="vertical-align: top;">
 <table
style="margin-left: auto; margin-right: auto; width: 100%; text-align: left;"
border="0" cellpadding="2" cellspacing="2">
 <tbody>
 <tr>
 <td style="vertical-align: top;"><a
style="color: rgb(0, 0, 102);" href="aboutTDA.html">Previous
Page</a> 
 </td>
 <td style="text-align: center; vertical-align: top;"><a
href="aboutContents.html">Contents</a> 
 </td>
 <td style="text-align: right; vertical-align: top;"><a
href="aboutAbelianCategories.html">Next
page 
 </a> </td>
 </tr>
 </tbody>
 </table>
 <a href="aboutTopology.html"> 
 </a> </td>
 </tr>
 </tbody>
</table>
 
 
</body>
</html>

Messung V0.5

¤ Dauer der Verarbeitung: 0.11 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.

Bemerkung:

Die farbliche Syntaxdarstellung und die Messung sind noch experimentell.