April 7, 2010

A Multi-Threaded Pi Estimator

Hadoop 의 Map/Reduce 로 Pi estimator가 구현되어있는데,
이를 Hama, BSP로 처리하면 M/R과 어떠한 성능/코드복잡도 차이를 보여줄까?
물론 안봐도 비디오로 예측되는 바, 이 예제로는 딱히 큰 매리트가 없을것도 같으나..

어쨌건 연습삼아 아래와 같은 Pi 계산 알고리즘을 multi-threaded 프로그래밍을써서 간단하게 만들어 봤다.

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

이를 자바로 구현해보면 아래와 같다.

public class PiEstimator {
  private double pi = 0.0;
  private final int numTasks = 10;
  private int allFinished = 0;
  private long starttime = 0;

  class PiEstimatorTask extends Thread {
    private PiEstimator Parent = null;
    private static final int iterations = 100000;

    public PiEstimatorTask(PiEstimator Parent) {
      this.Parent = Parent;
    }

    public void run() {
      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++;
        }
      }
      double estimate = 4.0 * (double) in / (double) iterations;
      ((PiEstimator) Parent).sync(estimate);
    }
  }
  
  public synchronized void sync(double est) {
    long rt = System.currentTimeMillis() - starttime;
    System.out.println("Terminated at " + rt + " ms, est " + est);
    pi = (allFinished == 0) ? est : (pi + est) / 2;
    allFinished++;
  }

  public double getPi() {
    return pi;
  }

  public void run() throws Exception {
    PiEstimatorTask[] PiTask = new PiEstimatorTask[numTasks];
    System.out.println("Instantiating " + numTasks + " threads");
    for (int i = 0; i < numTasks; i++) {
      PiTask[i] = new PiEstimatorTask(this);
    }
    starttime = System.currentTimeMillis();
    System.out.println("Starting threads, time = 0 ms");
    for (int i = 0; i < numTasks; i++) {
      (PiTask[i]).start();
    }
    
    for (int i = 0; i < numTasks; i++) {
      (PiTask[i]).join();
    }
  }

  public static void main(String[] args) throws Exception {
    PiEstimator pi = new PiEstimator();
    pi.run();
    System.out.println("Final estimate is: " + pi.getPi());
  }
}

No comments:

Post a Comment