Ejemplo de Uso: Cálculo de $\pi$

El área bajo la curva $y = \frac{1}{1+x^2}$ entre 0 y $1$ nos proporciona un método para calcular $\pi$ :

$$\int_{0}^{1} \frac{4}{(1+x^2)} dx = 4 \arctan(x) \vert _{0}^{1} = 4 ( \frac{\pi}{4} - 0) = \pi$$

Esta integral puede aproximarse por la suma:

$$\pi \simeq \sum_{i=0}^{N-1} \frac{4}{N \times \left (1+ (\frac{i+0.5}{N})^2 \right)}$$ (5.1)

El siguiente programa C calcula una parte de la suma:

~/src/perl/grid-machine/examples$ cat -n pi.c
 1  #include <stdio.h>
 2  #include <stdlib.h>
 3  
 4  main(int argc, char **argv) {
 5    int id, N, np, i;
 6    double sum, left;
 7  
 8    if (argc != 4) { 
 9      printf("Usage:\n%s id N np\n",argv[0]);
10      exit(1); 
11    }
12    id = atoi(argv[1]);
13    N = atoi(argv[2]);
14    np = atoi(argv[3]);
15    for(i=id, sum = 0; i<N; i+=np) {
16      double x = (i + 0.5)/N;
17      sum += 4 / (1 + x*x);
18    }
19    sum /= N;
20    printf("%lf\n", sum);
21    exit(0);
22  }

El siguiente ejemplo calcula el número $\pi$ en paralelo lanzando diversos procesos que realizan una suma parcial. El proceso padre recolecta los resultados tan pronto como terminan haciendo uso de IO::Select:

~/src/perl/grid-machine/examples$ cat -n gridpipes.pl 
 1  #!/usr/bin/perl
 2  use warnings;
 3  use strict;
 4  use IO::Select;
 5  use GRID::Machine;
 6  use Time::HiRes qw(time gettimeofday tv_interval);
 7  
 8  #my @machine = qw{europa};
 9  #my @machine = qw{europa beowulf orion};
10  my @machine = qw{nereida europa};
11  #my @machine = qw{127.0.0.1 127.0.0.2 127.0.0.3 127.0.0.4};
12  #my @machine = qw{beo chum};
13  my $nummachines = @machine;
14  my %machine; # Hash of GRID::Machine objects
15  #my %debug = (beowulf => 12345, orion => 0, nereida => 0);
16  #my %debug = (europa => 12344, beowulf => 0, orion => 0, nereida => 0);
17  my %debug = (europa => 0, beowulf => 0, orion => 0, nereida => 0);
18  
19  my $np = shift || $nummachines; # number of processes
20  my $lp = $np-1;
21  
22  my $N = shift || 100;
23  
24  my @pid;  # List of process pids
25  my @proc; # List of handles
26  my %id;   # Gives the ID for a given handle
27  
28  my $cleanup = 0;
29  
30  my $pi = 0;
31  
32  my $readset = IO::Select->new(); 
33  
34  my $i = 0;
35  for (@machine){
36    my $m = GRID::Machine->new(host => $_, debug => $debug{$_}, );
37  
38    $m->copyandmake(
39      dir => 'pi', 
40      makeargs => 'pi', 
41      files => [ qw{pi.c Makefile} ], 
42      cleanfiles => $cleanup,
43      cleandirs => $cleanup, # remove the whole directory at the end
44      keepdir => 1,
45    );
46  
47    $m->chdir("pi/");
48  
49    die "Can't execute 'pi'\n" unless $m->_x("pi")->result;
50  
51    $machine{$_} = $m;
52    last unless ++$i < $np;
53  }
54  
55  my $t0 = [gettimeofday];
56  for (0..$lp) {
57    my $hn = $machine[$_ % $nummachines];
58    my $m = $machine{$hn};
59    ($proc[$_], $pid[$_]) = $m->open("./pi $_ $N $np |");
60    $readset->add($proc[$_]); 
61    my $address = 0+$proc[$_];
62    $id{$address} = $_;
63  }
64  
65  my @ready;
66  my $count = 0;
67  do {
68    push @ready, $readset->can_read unless @ready;
69    my $handle = shift @ready;
70  
71    my $me = $id{0+$handle};
72  
73    my ($partial);
74    my $numBytesRead = sysread($handle,  $partial, 1024);
75    chomp($partial);
76  
77    $pi += $partial;
78    print "Process $me: machine = $machine[$me % $nummachines] partial = $partial pi = $pi\n";
79  
80    $readset->remove($handle) if eof($handle); 
81  } until (++$count == $np);
82  
83  my $elapsed = tv_interval ($t0);
84  print "Pi = $pi. N = $N Time = $elapsed\n";

Siguen algunos ejemplos de ejecución que demuestran que la técnica acelera. Comparaciones con Globus demuestran que el rendimiento en este ejemplo es superior a Globus.

pp2@nereida:~/LGRID_Machine/examples$ time ssh beowulf 'pi/pi 0 1000000000 1'
3.141593

real    0m27.020s
user    0m0.036s
sys     0m0.008s

casiano@beowulf:~$ time ssh orion 'pi/pi 0 1000000000 1'
3.141593

real    0m29.120s
user    0m0.028s
sys     0m0.003s

pp2@nereida:~/LGRID_Machine/examples$ time ssh nereida 'pi/pi 0 1000000000 1'
3.141593

real    0m32.534s
user    0m0.036s
sys     0m0.008s

pp2@nereida:~/LGRID_Machine/examples$ time gridpipes.pl 1 1000000000
Process 0: machine = beowulf partial = 3.141593 pi = 3.141593
Pi = 3.141593. N = 1000000000 Time = 27.058693

real    0m28.917s
user    0m0.584s
sys     0m0.192s

pp2@nereida:~/LGRID_Machine/examples$ time gridpipes.pl 2 1000000000
Process 0: machine = beowulf partial = 1.570796 pi = 1.570796
Process 1: machine = orion partial = 1.570796 pi = 3.141592
Pi = 3.141592. N = 1000000000 Time = 15.094719

real    0m17.684s
user    0m0.904s
sys     0m0.260s


pp2@nereida:~/LGRID_Machine/examples$ time gridpipes.pl 3 1000000000
Process 0: machine = beowulf partial = 1.047198 pi = 1.047198
Process 1: machine = orion partial = 1.047198 pi = 2.094396
Process 2: machine = nereida partial = 1.047198 pi = 3.141594
Pi = 3.141594. N = 1000000000 Time = 10.971036

real    0m13.700s
user    0m0.952s
sys     0m0.240s

# 2 veces nereida
pp2@nereida:~/LGRID_Machine/examples$ time gridpipes.pl 2 1000000000
Process 0: machine = 127.0.0.1 partial = 1.570796 pi = 1.570796
Process 1: machine = 127.0.0.2 partial = 1.570796 pi = 3.141592
Pi = 3.141592. N = 1000000000 Time = 16.38121

real    0m17.849s
user    0m0.504s
sys     0m0.212s

******************************************
con -O 3 en gcc
pp2@nereida:~/LGRID_Machine/examples$ time gridpipes.pl 4 1000000000
Process 3: machine = 127.0.0.4 partial = 0.785398 pi = 0.785398
Process 0: machine = 127.0.0.1 partial = 0.785398 pi = 1.570796
Process 1: machine = 127.0.0.2 partial = 0.785398 pi = 2.356194
Process 2: machine = 127.0.0.3 partial = 0.785398 pi = 3.141592
Pi = 3.141592. N = 1000000000 Time = 18.508143

real    0m21.299s
user    0m0.840s
sys     0m0.360s
pp2@nereida:~/LGRID_Machine/examples$ time gridpipes.pl 2 1000000000
Process 1: machine = 127.0.0.2 partial = 1.570796 pi = 1.570796
Process 0: machine = 127.0.0.1 partial = 1.570796 pi = 3.141592
Pi = 3.141592. N = 1000000000 Time = 16.552487

real    0m18.076s
user    0m0.504s
sys     0m0.188s
pp2@nereida:~/LGRID_Machine/examples$ time gridpipes.pl 3 1000000000
Process 1: machine = 127.0.0.2 partial = 1.047198 pi = 1.047198
Process 0: machine = 127.0.0.1 partial = 1.047198 pi = 2.094396
Process 2: machine = 127.0.0.3 partial = 1.047198 pi = 3.141594
Pi = 3.141594. N = 1000000000 Time = 17.372372

real    0m19.461s
user    0m0.696s
sys     0m0.240s
pp2@nereida:~/LGRID_Machine/examples$ time gridpipes.pl 1 1000000000
Process 0: machine = 127.0.0.1 partial = 3.141593 pi = 3.141593
Pi = 3.141593. N = 1000000000 Time = 32.968117

real    0m33.858s
user    0m0.336s
sys     0m0.128s

Estos son los contenidos del Makefile:

pp2@nereida:~/src/perl/Event/select$ cat -T Makefile
pi:
^Icc pi.c -o pi