先進的計算基盤システムシンポジウム Shuffle KVP KVP MapReduce KVP 7) Jimmy PageRank MapReduce.69 Jimmy KVP Jimmy key KVP value KVP MapReduce 3 PageRank 4 Jimmy M

Size: px

Start display at page:

Download "先進的計算基盤システムシンポジウム Shuffle KVP KVP MapReduce KVP 7) Jimmy PageRank MapReduce.69 Jimmy KVP Jimmy key KVP value KVP MapReduce 3 PageRank 4 Jimmy M"

れんかすみだ
6 years ago
Views:

1 先進的計算基盤システムシンポジウム MapReduce MapReduce MapReduce Map Reduce MapReduce MapReduce PageRank in-mapper combining.57 Acceleration for Graph Application in MapReduce with Eliminating Redundant Messages Nobuyuki Kuromatsu, Masao Okita and Kenichi Hagihara For MapReduce graph applications based on message passing, this papar proposes a new method to reduce communications between Map tasks and Reduce tasks, which are a bottleneck of a MapReduce job. The proposed method is a combination of the following two techniques. The first technique reduces the number of messages by removing redundant messages in a MapReduce job. The second technique reduces the size of a message by reusing message patterns of the first job in iterative jobs after the second. Experimental results show that the proposed method is up to.57 times faster than an existing in-mapper combining method for PageRank apllications with MapReduce.. ) 0 9 ) Google MapReduce 3) MapReduce key value key-value pair KVP MapReduce The Graduate School of Information Science and Technology of Osaka University MapReduce Jimmy Lin MapReduce 4) (i) iii (i) (ii) (i) (iii) Jimmy PageRank 5) Jimmy 6) Jimmy MapReduce Map Shuffle Reduce (i) (ii) (iii) c 03 Information Processing Society of Japan 88

2 先進的計算基盤システムシンポジウム Shuffle KVP KVP MapReduce KVP 7) Jimmy PageRank MapReduce.69 Jimmy KVP Jimmy key KVP value KVP MapReduce 3 PageRank 4 Jimmy MapReduce MapReduce MapReduce Map Reduce Map Reduce Map Shuffle Reduce 3 DFS Map 3) Reduce DFS Reduce MapReduce KVP key key Reduce KVP Reduce Map Map Map Map Shuffle Reduce Map Map Map Map Map Map () () () () Reduce (3) (3) Reduce Reduce MapReduce Fig. A flow of a MapReduce job KVP Map Map key () Shuffle Reduce Map Reduce KVP Map ()Reduce KVP key (3) Map Map Shuffle Reduce key KVP Reduce 3. PageRank PageRank G = (V, E) V E PageRank () (3) 5) () (3) () P R (v; ) = V ( d) P R (u; t ) P R (v; t) = + d V N out(u) u N in (v) () () c 03 Information Processing Society of Japan 89

3 先進的計算基盤システムシンポジウム struct Vertex{ double rank // P R (v; t) 3 int vertices // V 4 List<String> adjacency //N out (v) 5 } 6 struct Message{ 7 String from // 8 double message //M v 9 } 0 void map(string v, Vertex N){ // < v, N > Message M 3 M.from v 4 M.message N.rank / N.adjacency 5 //u N out (v) M v 6 foreach (String u :N.adjacency) 7 emit(u, M) // KVP< u, M > 8 //N out(v) 9 emit(v, N) 0 } void reduce(string v, List<Object> [X, X,...]){ 3 Vertex N 4 double s 0 5 foreach(object X :[X, X,...]) 6 if(isvertex(x)) // Vertex 7 N X 8 else 9 s s+x.message 30 N.rank ( d)/n.vertices+d s // 3 emit(v, N) // KVP< v, N > 3 // (3) 33 } MapReduce PageRank Fig. A naive implementation of PageRank v V P R (v; t ) P R (v; t) < ɛ (3) P R(v; t) t(t > 0) PageRank v V N out (v) = {u v u E} N in(v) = {u u v E} u v u v d 8) ɛ G 3. PageRank MapReduce PageRank Jimmy G v V P R(v; t) v P R (v; t) t > (i) M v = P R(v; t)/ N out(v) (ii) u N out (v) M v (iii) M w (w N in (v)) () (3) MapReduce key value KVP a b key value KVP < a, b > m V m Map p V (p) p v V (p) map map KVP < u, M v > < v, N > 7 9 v N Reduce KVP KVP Reduce KVP key r V Map r Reduce q V (q) q v V (q) reduce KVP 4. Jimmy 4) in-mapper combining IMC Schimmy IMC KVP Schimmy KVP Jimmy 4. In-Mapper Combining IMC Map KVP key KVP IMC KVP Reduce IMC Map (I) map KVP (II) KVP key key KVP KVP (III) KVP KVP 3. PageRank IMC c 03 Information Processing Society of Japan 90

4 先進的計算基盤システムシンポジウム Map p KVP v key KVP K(p v) value U(p v) Vertex value U(p v) u N in (v) V (p) v U(p v) v K(p v) < v, Σ M U(p v) M > IMC map IMC Map (III) Map 4. Schimmy Schimmy Shuffle Schimmy 3. PageRank Schimmy map Vertex G N out(v) N out(v) KVP N out (v) Map v V N out (v) 5. Jimmy KVP RRSP Removing Redundant messages to the Same Partition IRS In-Reducer Schimmy5. IRS PageRank MapReduce 3. KVP < u, M v > a h 3 f j b g i 3 k c d e 3 a a 3 PageRank Fig. 3 An example of graph in PagerRank < u, N > 5. RRSP RRSP Map p KVP value v u w M v KVP< u, M v > < w, M v > KVP M v p Reduce 3 PageRank b g Reduce < b, M a > < g, M a > b g M a RRSP Map KVP value value KVP KVP KVP key value KVP key KVP value PageRank RRSP v map KVP value M v Map p KVP K(p) K(p) = {< u, M v > v V (p), u N out (v)} r Reduce Q = {q, q,, q r} KVP K(p) K(p) = {< V (q) N out (v), M v > v V (p), q Q} key KVP Reduce KVP value int key c 03 Information Processing Society of Japan 9

5 先進的計算基盤システムシンポジウム 5.. IMC RRSP RageRank IMC RRSP KVP G e Map m Reduce r Map V /m e Map KVP e V /m IMC Map KVP key KVP KVP PageRank KVP key Map KVP V IMC D I (4) D I = V = m (4) e V e m RRSP Map KVP value KVP KVP PageRank v v KVP r RRSP D R (5) D R = r e (5) PageRank MapReduce r < m IMC RRSP KVP RRSP map MapReduce 5. IRS IRS RRSP Schimmy KVP Jimmy 4. Reduce Schimmy PageRank KVP f < V (q) N out (v), M v > q f Reduce G L(q v) = V (q) N out (v) q L(q v) L(q v) KVP q KVP <, M v > PageRank L(q v) CPU Table The experimenatal environment Intel Xeon 3.GHz 4 cores DDR3-SDRAM 333MHz ECC 8 GB SATA 6 Gb/s 700 rpm TB Gigabit Ethernet OS CentOS 5.6 Hadoop.0. HDFS Hadoop Reduce q KVP v L(q v) q <, M v > M v v L(q v) IRS q MapReduce q MapReduce Reduce 6. PageRank IMC MapReduce Hadoop 9) Map 64 MB Reduce PageRank ɛ = RRSP IRS 6. Wikipedia 0) Portals V = 999, 99 E = 46, 74, MB Map 5 5 PageRank c 03 Information Processing Society of Japan 9

6 先進的計算基盤システムシンポジウム IMC 4 Wikipedia PageRank 0 Fig. 4 Total execution time of 0 MapReduce jobs to calculate PageRank for a part of the Web 0 GB IMC GB KVP 5,000 4,500 4,000 3,500 3,000,500,000,500,000 6 KVP Fig. 6 Transfferd data size and the number of intermediate KVP in a job after the second iteration KVP Map Reduce IMC Fig. 5 5 Average execution time of a of job 0 IMC 0 IMC map reduce IMC PageRank IMC Shuffle KVP KVP 6 6 IMC KVP KVP IMC 6.8% 3.6% Map Reduce 7 Map Reduce Fig. 7 Average breakdowns of a Map task and a Reduce task in a job after the second iteration 7 4. (III) KVP map IMC 3.9 map Map KVP KVP.9 reduce IMC.4 IRS KVP reduce Reduce 6. PageRank c 03 Information Processing Society of Japan 93

7 先進的計算基盤システムシンポジウム DS-L IMC IMC Fig. 8 Speedup with proposed method and IMC for DS-L PageRank ne Table Total execution time of PageRank for random generated graphs n e IMC 5,376,34, ,543,39, ,865 3,47,807 5,06,903,67 DS-L ,966 3,509, ,99 5,354 4, ,076 3,80 3, ,696 7,563 5,3 75,4684,3 7, ,67,96,07 75,03,894,59 5,5,5 987 DS-S 40 50,94,786, ,06,773,06 5,63,08, ,880 3,4, ,450 5,48 3,94 V = DS-L V =5 DS-S Java Random DS-L DS-S e DS-L e = 5, 50, 75 4 GB 44 GB 66 GB DS-S GB GB 33 GB n PageRank 5 IMC 9 DS-S IMC IMC Fig. 9 Speedup with proposed method and IMC for DS-S 3 Table 3 IMC KVP Reduction rate of the number of intermediate KVP with proposed method and IMC D I D R DS-L 40 D I D R D I D R D I D R DS-S 40 D I D R D I D R IMC 8 9 IMC.57 DS-L e = 75 n = n 40 e V 3 D R D R V (5) n = 0 e 50 V Shuffle DS-L IMC Map reduce DS-L KVP c 03 Information Processing Society of Japan 94

8 先進的計算基盤システムシンポジウム V IMC D I m V e (4) D I (6) V k D I = k V (6) DS-S D I DS-L D I e IMC 9 e D R 3 (5) e e value KVP D I e (6) n IMC 9 n D R 3 r = n (5) n n D I n (5) n r D R Reduce r n r n r n r 7. Jimmy MapReduce KVP value value KVP KVP MapReduce KVP PageRank MapReduce IMC.57 PageRank IMC Reduce Jimmy (B) (B) ) Lumsdaine, A., Gregor, D., Hendrickson, B. and Berry, J. W.: Challenges in Parallel Graph Processing, Parallel Processing Letters, Vol. 7, No., pp. 5 0 (007). ) The ISC Domain Survey (0). 3) Dean, J. and Ghemawat, S.: MapReduce: simplified data processing on large clusters, CACM, Vol. 5, No., pp (008). 4) Lin, J. and Schatz, M.: Design patterns for efficient graph algorithms in MapReduce, 8th Workshop on Mining and Learning with Graphs, MLG 0, ACM, pp (00). 5) Page, L., Brin, S., Motwani, R. and Winograd, T.: The PageRank Citation Ranking: Bringing Order to the Web., Technical Report , Stanford InfoLab (999). 6) Cudre-Mauroux, P., Aberer, K. and Feher, A.: Probabilistic Message Passing in Peer Data Management Systems, nd Int l Conf. Data Engineering, ICDE 06, IEEE, p. 4 (006). 7) Wang, G., Butt, A., Pandey, P. and Gupta, K.: A simulation approach to evaluating design decisions in MapReduce setups, Int l Sympo. Modeling, Analysis Simulation of Computer and Telecommunication Systems, MASCOTS 09, IEEE, pp. (009). 8) Boldi, P., Santini, M. and Vigna, S.: PageRank as a function of the damping factor, 4th Int l Conf. World Wide Web, WWW 05, ACM, pp (005). 9) White, T.: Hadoop: The Definitive Guide, Yahoo! Press, USA (00). 0) Wikipedia. the free encyclopedia (0). c 03 Information Processing Society of Japan 95

,4) 1 P% P%P=2.5 5%!%! (1) = (2) l l Figure 1 A compilation flow of the proposing sampling based architecture simulation

,4) 1 P% P%P=2.5 5%!%! (1) = (2) l l Figure 1 A compilation flow of the proposing sampling based architecture simulation 1 1 1 1 SPEC CPU 2000 EQUAKE 1.6 50 500 A Parallelizing Compiler Cooperative Multicore Architecture Simulator with Changeover Mechanism of Simulation Modes GAKUHO TAGUCHI 1 YOUICHI ABE 1 KEIJI KIMURA 1