Page History

...

The value of PI can be calculated in a number of ways. Consider the following method of In this example, we are estimating PI

• Inscribe a circle in a square
• Randomly generate points in the square
• Determine the number of points in the square that are also in the circle
• Let r be the number of points in the circle divided by the number of points in the square
• PI ~ 4 r
  

Serial pseudo code for this procedure as below:

...

using following way:

• Each task executes locally its portion of the loop a number of times.
  {{{
  iterations = 10000
  circle_count = 0

do j = 1,iterations
generate 2 random numbers between 0 and 1
xcoordinate = random1
ycoordinate = random2
if (xcoordinate, ycoordinate) inside circle
then circle_count = circle_count + 1
end do

PI = 4.0*circle_count/iterations

...

}}}

The BSP implementation for Pi

A distributed strategy in HAMA with BSP programming model, is break the loop into portions that can be executed by the tasks.

• Each task executes locally its portion of the loop a number of times.
• One task acts as master and collects the results through the BSP communication interface.
  

  PI = pi_sum / n_processes

1) Each process computes the value of Pi locally, and 2) sends it to master task using send() function. Then, 3) the master task can recieve the messages using sync() function. Finally, we can calculate the average value of sum of PI values from each peers as below:

    public void bsp(BSPPeerProtocol bspPeer) throws IOException,
        KeeperException, InterruptedException {
      int in = 0, out = 0;
      for (int i = 0; i < iterations; i++) {
        double x = 2.0 * Math.random() - 1.0, y = 2.0 * Math.random() - 1.0;
        if ((Math.sqrt(x * x + y * y) < 1.0)) {
          in++;
        } else {
          out++;
        }
      }

      byte[] tagName = Bytes.toBytes(bspPeer.getPeerName());
      byte[] myData = Bytes.toBytes(4.0 * (double) in / (double) iterations);
      BSPMessage estimate = new BSPMessage(tagName, myData);

      bspPeer.send(masterTask, estimate);
      bspPeer.sync();

      double pi = 0.0;
      int numPeers = bspPeer.getNumCurrentMessages();
      BSPMessage received;
      while ((received = bspPeer.getCurrentMessage()) != null) {
        pi += Bytes.toDouble(received.getData());
      }

      if (bspPeer.getPeerName().equals(masterTask)) {
        pi = pi / numPeers;
        writeResult(pi);
      }
    }