hama-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Apache Wiki <wikidi...@apache.org>
Subject [Hama Wiki] Update of "Architecture" by Edward J. Yoon
Date Sun, 27 Jun 2010 07:42:37 GMT
Dear Wiki user,

You have subscribed to a wiki page or wiki category on "Hama Wiki" for change notification.

The "Architecture" page has been changed by Edward J. Yoon.
The comment on this change is: Add BSP example .
http://wiki.apache.org/hama/Architecture?action=diff&rev1=128&rev2=129

--------------------------------------------------

  
  == Examples ==
  
+ === Pi Estimation ===
-  * Matrix Multiplication, Inversion [[https://issues.apache.org/jira/browse/HAMA-221|HAMA-221]]
-  * Pi Estimator [[https://issues.apache.org/jira/browse/HAMA-265|HAMA-265]]
-  * !PageRank
  
+ 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 Algorithm for Pi ====
+ 
+ Parallel strategy is break the loop into portions that can be executed by the tasks.
+ 
+  * For the task of estimating PI:
+    * Each task executes its portion of the loop a number of times.
+    * Each task can do its work without requiring any information from the other tasks (there
are no data dependencies).
+    * One task acts as master and collects the results.
+ 
+ {{{
+     public void bsp(BSPPeer 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(getName().toString());
+       byte[] myData = Bytes.toBytes(4.0 * (double) in / (double) iterations);
+       BSPMessage estimate = new BSPMessage(tagName, myData);
+ 
+       Log.info("Send a message (" + Bytes.toDouble(myData) + ") from "
+           + bspPeer.getServerName() + " to localhost:30000");
+       bspPeer.send(new InetSocketAddress("localhost", 30000), estimate);
+       bspPeer.sync();
+ 
+       double pi = 0.0;
+       BSPMessage received;
+       while ((received = bspPeer.getCurrentMessage()) != null) {
+         pi = (pi + Bytes.toDouble(received.getData())) / 2;
+       }
+ 
+       if (pi != 0.0)
+         System.out.println("Estimated value of PI is " + pi);
+ 
+     }
+ }}}
+ 

Mime
View raw message