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] Trivial Update of "Architecture" by udanax
Date Fri, 13 Mar 2009 00:49:26 GMT
Dear Wiki user,

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

The following page has been changed by udanax:
http://wiki.apache.org/hama/Architecture

------------------------------------------------------------------------------
  == Algorithms ==
  === Dense Matrix-Matrix multiplication ===
  
+ To mutliply two matrices A and B, We collect the blocks to 'collectionTable' firstly using
map/reduce.
+ Rows are named as c(i, j) with sequential number ((N^2 * i) + ((j * N) + k) to avoid duplicated
records. Each row has a two sub matrices of a(i, k) and b(k, j) so that 
+ minimized data movement and network cost. Finally, We multiply and sum sequentially.
+ 
+ {{{
  Blocking jobs:
  
-  * Collect the blocks to 'collectionTable' from A and B.
+ Collect the blocks to 'collectionTable' from A and B.
+ 
-   * A map task receives a row n as a key, and vector of each row as its value
+ - A map task receives a row n as a key, and vector of each row as its value
-    * emit (blockID, sub-vector)
+  - emit (blockID, sub-vector)
-   * Reduce task combines block
+ - Reduce task combines block
  
  Multiplication job:
  
-  * A map task receives a blockID n as a key, and two sub-matrices of A and B as its value
+ - A map task receives a blockID n as a key, and two sub-matrices of A and B as its value
-  * Reduce task computes sum of blocks
+ - Reduce task computes sum of blocks
- 
+ }}}
  === Find the maximum absolute row sum of matrix ===
  
-  * https://issues.apache.org/jira/browse/HAMA-171
+ Matrix.Norm.One is that find the maximum absolute row sum of matrix. Comparatively, it's
a good fit with MapReduce model because doesn't need iterative jobs or table/file JOIN operations.
+ 
+ {{{
+ 
+                                          j=n
+ The maximum absolute row sum =   max   ( sum | a_{i,j} | ) 
+                                1<=i<=n   j=1
+ 
+ 
-  * A map task receives a row n as a key, and vector of each row as its value
+ - A map task receives a row n as a key, and vector of each row as its value
-   * emit (row, the sum of the absolute value of each entries)
+  - emit (row, the sum of the absolute value of each entries)
-  * Reduce task select the maximum one
+ - Reduce task select the maximum one
+ }}}
  
  === Compute the determinant of matrix ===
  

Mime
View raw message