incubator-hama-commits mailing list archives

Site index · List index
Message view
Top
From Apache Wiki <wikidi...@apache.org>
Subject [Hama Wiki] Trivial Update of "MatMult" by Edward J. Yoon
Date Tue, 11 May 2010 02:41:12 GMT
```Dear Wiki user,

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

The "MatMult" page has been changed by Edward J. Yoon.
http://wiki.apache.org/hama/MatMult?action=diff&rev1=17&rev2=18

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

=== Block Approach ===

- To multiply two dense matrices A and B, we should build the "collectionTable" in the pre-processing
phase of !MapReduce. The collectionTable is an 1-D representation, transformed from the original
2-D representation of two matrices. Each row of the collectionTable has two submatrices of
A(i,k) and B(k,j) with the row index of (n2 ∗ i) + (n ∗ j) + k, where n denotes the row
size of matrix A and B. We call these submatrices a block. Each map task walks only on the
collectionTable instead of the original matrices, and thus it significantly reduces required
data movement over the network. The following code shows the block algorithm after pre-processing.
Each map task receives a blockID as a key, and two submatrices of A and B as its value, and
then multiplies two submatrices, A[i][j] ∗ B[j][k]. Afterward, a reduce task computes the
summation of blocks, s[i][k]+ = multipliedblocks. The pseudo-code of the block approach is
depicted in Algorithm 2.
+ To multiply two dense matrices A and B, we should build the "collectionTable" in the pre-processing
phase of !MapReduce. The collectionTable is an 1-D representation, transformed from the original
2-D representation of two matrices. Each row of the collectionTable has two submatrices of
A(i,k) and B(k,j) with the row index of (n2 ∗ i) + (n ∗ j) + k, where n denotes the row
size of matrix A and B. We call these submatrices a block. Each map task walks only on the
collectionTable instead of the original matrices, and thus it significantly reduces required
data movement over the network. The following code shows the block algorithm after pre-processing.
Each map task receives a blockID as a key, and two submatrices of A and B as its value, and
then multiplies two submatrices, A[i][j] ∗ B[j][k]. Afterward, a reduce task computes the
summation of blocks, s[i][k]+ = multipliedblocks.

{{{
Blocking jobs:

```
Mime
View raw message