Mailing-List: contact hama-dev-help@incubator.apache.org; run by ezmlm
Precedence: bulk
Reply-To: hama-dev@incubator.apache.org
MIME-Version: 1.0
Date: Fri, 12 Feb 2010 11:41:44 +0900
Message-ID: <eb4706e1002111841x50303ba8r43c0397172437454@mail.gmail.com>
Subject: A BSP based matrix multiplication implementation.
From: "Edward J. Yoon" <edwardyoon@apache.org>
To: hama-dev@incubator.apache.org, hama-user@incubator.apache.org
Cc: common-user@hadoop.apache.org, mahout-user@lucene.apache.org
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

Hi,

I just made a pseudo code for this issue. I'm sure it will show better
performance than any M/R version of mat-mat mult on Hadoop.

Following is the sample code you could reference when porting to BSP versio=
n,
http://svn.apache.org/repos/asf/incubator/hama/trunk/src/test/org/apache/ha=
ma/bsp/BSPPeerTest.java

Does anyone have a interesting or want to implement this?

On Fri, Feb 12, 2010 at 11:20 AM, Edward J. Yoon (JIRA) <jira@apache.org> w=
rote:
>
> =C2=A0 =C2=A0[ https://issues.apache.org/jira/browse/HAMA-221?page=3Dcom.=
atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedComment=
Id=3D12832796#action_12832796 ]
>
> Edward J. Yoon commented on HAMA-221:
> -------------------------------------
>
> Here's my multi threaded version of mat-mat mult.
>
> In this example,
> =C2=A0- Thread.join() means a barrier.
> =C2=A0- The global storage (int[][] out) was used. =C2=A0(Of course, you =
can also split the summation into n-supersteps.)
>
> ----
> class MatMult extends Thread {
> =C2=A0static int m1[][];
> =C2=A0static int m2[][];
> =C2=A0static int out[][];
> =C2=A0static int n =3D 2;
> =C2=A0int row;
>
> =C2=A0MatMult(int i) {
> =C2=A0 =C2=A0row =3D i;
> =C2=A0 =C2=A0this.start();
> =C2=A0}
>
> =C2=A0public void run() {
> =C2=A0 =C2=A0int i, j;
> =C2=A0 =C2=A0for (i =3D 0; i < n; i++) {
> =C2=A0 =C2=A0 =C2=A0out[row][i] =3D 0;
>
> =C2=A0 =C2=A0 =C2=A0for (j =3D 0; j < n; j++) {
> =C2=A0 =C2=A0 =C2=A0 =C2=A0out[row][i] =3D out[row][i] + m1[row][j] * m2[=
j][i];
> =C2=A0 =C2=A0 =C2=A0}
> =C2=A0 =C2=A0}
> =C2=A0}
>
> =C2=A0public static void main(String args[]) throws Exception {
> =C2=A0 =C2=A0int i, j;
> =C2=A0 =C2=A0int n =3D 2;
> =C2=A0 =C2=A0m1 =3D new int[][] { { 1, 2 }, { 3, 4 } };
> =C2=A0 =C2=A0m2 =3D new int[][] { { 1, 2 }, { 3, 4 } };
> =C2=A0 =C2=A0out =3D new int[n][n];
>
> =C2=A0 =C2=A0MatMult mat[] =3D new MatMult[n];
> =C2=A0 =C2=A0for (i =3D 0; i < n; i++) {
> =C2=A0 =C2=A0 =C2=A0mat[i] =3D new MatMult(i);
> =C2=A0 =C2=A0}
>
> =C2=A0 =C2=A0for (i =3D 0; i < n; i++) {
> =C2=A0 =C2=A0 =C2=A0mat[i].join();
> =C2=A0 =C2=A0}
>
> =C2=A0 =C2=A0System.out.println("OUTPUT :");
> =C2=A0 =C2=A0for (i =3D 0; i < n; i++) {
> =C2=A0 =C2=A0 =C2=A0for (j =3D 0; j < n; j++) {
> =C2=A0 =C2=A0 =C2=A0 =C2=A0System.out.print(out[i][j] + "\t");
> =C2=A0 =C2=A0 =C2=A0}
> =C2=A0 =C2=A0 =C2=A0System.out.println();
> =C2=A0 =C2=A0}
> =C2=A0}
> }
>
>
>> A BSP matrix multiplication implementation.
>> -------------------------------------------
>>
>> =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 Key: HAMA-221
>> =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 URL: https://iss=
ues.apache.org/jira/browse/HAMA-221
>> =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 Project: Hama
>> =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0Issue Type: Improvement
>> =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0Components: bsp, matrix
>> =C2=A0 =C2=A0Affects Versions: 0.2.0
>> =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0Reporter: Edward J. Yoon
>> =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 Fix For: 0.2.0
>>
>>
>> Using the BSP model, we could improve the performance of mat-mat multipl=
ication. Let's evaluation it out on this issue.
>
> --
> This message is automatically generated by JIRA.
> -
> You can reply to this email to add a comment to the issue online.
>
>


--=20
Best Regards, Edward J. Yoon @ NHN, corp.
edwardyoon@apache.org
http://blog.udanax.org