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);
}
}