Pi Estimator
The value of PI can be calculated in a number of ways. Consider the following method of 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:
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.
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); } }