This effort is still a "work in progress". Please feel free to add comments. BRBut please make the content less visible by using smaller fonts. – Edward J. Yoon
Overview
Hama is a parallel matrix computational package.
Matrices are basically tables. They are ways of storing numbers and other things. Typical matrix has rows and columns. Actually called a 2-way matrix because it has two dimensions. For example, you might have respondents-by-attitudes. Of course, you might collect the same data on the same people at 5 points in time. In that case, you either have 5 different 2-way matrices, or you could think of it as a 3-way matrix, that is respondent-by-attitude-by-time.
We choosed Hbase which <row, column, timestamp> column-oriented sparse table storage to store the matrices.
- Hama use column-oriented storage of matrices (HBase) , and so compressed column format is a natural choice of sparse storage
- Hama forces the elements of each column to be stored in increasing order of their row index
See also: [http://labs.google.com/papers/bigtable-osdi06.pdf Bigtable], A Distributed Storage System for Structured Data
Parallel Strategies for Dense Matrix
In Map/Reduce programming, user can easily take advantage of the below parallel data layouts, communication paradigms.
- 1D Column Blocked Layout
- 1D Column Block Cyclic Layout
- 2D Row and Column Blocked Layout
- 2D Row and Column Block Cyclic Layout
Square blocking
The matrix multiplication of the original arrays can be transformed into matrix multiplication of blocks. For example,
C_block(1,1)=A_block(1,1)*B_block(1,1) + A_block(1,2)*B_block(2,1)
+-----+-----+ +-----+-----+ +-----+-----+ | x x | | | --> | --> | | | | | | | x x | | | --> | --> | | ↓ ↓ | | +-----+-----+ = +-----+-----+ * +-----+-----+ | | | | | | | | | | | | | | | | | | ↓ ↓ | | +-----+-----+ +-----+-----+ +-----+-----+