Jaeseok Myung

Intelligent Data Systems Lab School of Computer Science & Engineering Seoul National University, Seoul, Korea Page 1

Introduction β’ Matrix multiplication is an important operation for many applications β Scientific Computing, Social Network Analysis, β¦ β Finding π-hop neighbors from a social network

a b

c

(π1 )2

β¨

π1 a

b

c

a

0

1

1

b

1

0

0

c

0

1

0

β¨

a

b

c

a

1

1

0

b

0

1

c

1

0

π1 β¨ (π1 )2 a

b

c

a

1

1

1

1

b

1

1

1

0

c

1

1

0

β’ MapReduce has emerged as a scalable data processing framework β The size of data is rapidly increasing β MapReduce is a new programming model so it requires new algorithms

β’ In this paper, we focus on MR algorithms for the matrix multiplication Page 2

Matrix Multiplication using Join Operation β’ Matrix multiplication is often translated into a join operation between two relations

SELECT M1.row, M2.col, sum(M1.val*M2.val) FROM M1, M2 WHERE M1.col=M2.row GROUP BY M1.row, M2.col

β’ Especially, join operation is useful for sparse matrices β There are a number of sparse matrices in real-world

β’ In this paper, we deal with the matrix multiplication via join algorithms in MapReduce Page 3

Our Approach: Inter-Operation Parallelism β’ Several studies have been published to improve performance of

multiplication between two matrices

β’ However, we focus on multiplication of several matrices β Thus, we focus on the entire equation rather than an operation β’ The notion of inter-operation parallelism

β Fortunately, matrix multiplication is associative π΄π΅πΆπ· =

π΄π΅ πΆ π· =

π΄π΅ πΆπ·

=

π΄π΅πΆ π· = β― = (π΄π΅πΆπ·)

β’ We believe that the notion of inter-operation parallelism is helpful for MapReduce and matrix chain multiplication

A

B

3rd

ββ

ββ C

2nd

ββ

D

A

ββ

B

C

D

1st Page 4

Iterative MapReduce β’ Multiplication of several matrices requires MapReduce iteration β It is important to reduce the number of MapReduce jobs because MR iteration is usually inefficient

Page 5

Implementation β’ Three different methods for matrix chain multiplication

3rd

ββ ββ A

ββ

B

C

D

1st

(1) Serial 2-way (S2) (n-1) iterations

2nd

ββ

2nd A

ββ

B

C

ββ

D

1st

(2) Parallel 2-way (P2) log2 π iterations

ββ A

B

C

D

(3) Parallel M-way (PM) logπ π iterations

Page 6

Experiments β 1 β’ Amazon EC2 (4 units) β M (10,000 X 10,000)

Time (sec.)

400

300 200 100 0

M^3

M^4

M^5

M^6

S2

91

137

205

295

P2

90

89

134

136

PM

44

54

56

87

β The result shows the importance of the inter-operation parallelism Page 7

Experiments β 2 β’ Amazon EC2 β M (1,000,000 X 1,000,000)

Time (sec.)

1500 1000 500 0

4 units

8 units

S2

710

373

P2

310

304

PM

788

1030

β’ PM shows the worst performance β’ S2 has iteration overhead, but it can take advantage of multiple machines β’ P2 shows the best performance Page 8

Discussion β’ Different MR implementations for 2-way and m-way join β MR programming model is based on the key-value model β’ Join operation should be implemented like a hash join algorithm β Mapper make a partition of records that shares the same join key β Reducer actually make a join result for the partition

Page 9

Overhead in Hadoopβs MR Implementation - Sorting β’ Mappers always do sorting for every partition even if records in the partition will be discarded β Only thing we expect to the mapper is just transfer a record to the right reducer

Page 10

Discussion β’ Serial 2-way Join β Several iterations β No duplication

β’ Parallel 2-way Join β No duplication β Reduced iterations

β’ Parallel m-way join β No iterations β Duplication

β’ Parallel 2-way join balances the intra-operation parallelism and the inter-operation parallelism, so it shows the best performance

Page 11

Conclusion β’ Contribution β The first MR approach to the matrix chain multiplication β Applying the MR multi-way join algorithm to the matrix chain multiplication β’ Implementation of S2 / P2 / PM

β Experiments β’ Analysis of limitations

β’ Two Types of Overhead for Matrix Chain Multiplication with MR β Overhead between MR jobs -> this paper β’ Experimental results shows that P2 shows the best performance

β Overhead within a MR job (Sorting) -> Future work β’ There have been several studies for efficient MR job execution β HaLoop, HOP, β¦

Page 12

Appendix

Jaeseok Myung

Intelligent Data Systems Lab School of Computer Science & Engineering Seoul National University, Seoul, Korea Page 13

What is MapReduce? β’ MapReduce a parallel programming model based on the notion of functional programming β Map (k1, v1) -> list(k2, v2) β Reduce (k2, list(v2)) -> list (k3, v3)

Introduction to Hadoop, Jteam

Page 14

Related Work β’ Several studies exist to optimize multiplication of two matrices β A MapReduce Algorithm for Matrix Multiplication, 2009 β’ http://homepage.mac.com/j.norstad/matrix-multiply/index.html

β PEGASUS: A Peta-Scale Graph Mining System - Implementation and Observations, ICDM 2009 β SystemML: Declarative Machine Learning on MapReduce, ICDE 2011

β’ Multiplication of several matrices requires MapReduce iteration β It is important to reduce the number of MapReduce jobs because MR iteration is inefficient Page 15

A Multi-way Join Algorithm in MapReduce

R(A,B)

S(B,C)

T(C,D)

β’ Let h be a hash function with range 1, 2, β¦, m β S(b, c) -> (h(b), h(c)) β R(a, b) -> (h(b), all) β T(c, d) -> (all, h(c))

β’ [EDBT 10] minimize the expression β r|h(c)|+s+t|h(b)| β where |h(c)|*|h(b)| = k

h(c) = 0

h(T.c) = 1 1 2

h(S.b) = 2 h(S.c) = 1 3

h(b) = 0 1 2

3 h(R.b) = 2

Reduce processes

(# of Reduce processes: 42 = 16) m=4, k=16

Page 16