/ / / [4][3][5] / FX10 TAHB RMATT / / C.D. Sudheer [12] T. Hoefler [11] T. Hatazaki[7] J. L. Traff[8] F. Ercal [6] T. Agarwal [9] G. Bh

Size: px

Start display at page:

Download "/ / / [4][3][5] / FX10 TAHB RMATT / / C.D. Sudheer [12] T. Hoefler [11] T. Hatazaki[7] J. L. Traff[8] F. Ercal [6] T. Agarwal [9] G. Bh"

たみえたかぎ
5 years ago
Views:

1 / 1,2,a) 1,2,b) / 6 / FX10 43%, 79% 35% sec / Task Allocation Technique for Avoiding Contentions on Multi-Dimensional Mesh/Torus Yoshiyuki Morie 1,2,a) Takeshi Nanri 1,2,b) Abstract: This paper proposed the task allocation technique for avoiding contentions on a multi-dimensional Mesh/Torus. This task allocation technique, unlike the existing technique, can predict contentions from the period of communication time and can search and output the task allocation that reduces contentions. This technique improves the better communication performance than the existing technique. In this paper, the performance evaluation experiment performs comparison with the technique using message size and the number of hops and the technique checking the bottleneck that are the existing technique in FX10 that is a Kei computer compatible machine that has a 6-dimensional Mesh/Torus network topology. In the experiment, the maximum performance gain about 43% over the technique using message and the number of hops and about 79% over technique checking the bottleneck. The effectiveness of the proposed technique was shown in this experiment. Moreover, Clarifying the set of the communications that execute to start transmission simultaneously by inserting synchronizations improved the maximum performance gain 35 %. Moreover, the execution time of searching the solution of the task allocation in the proposed technique was 272 sec at 96 nodes, this is a high speed comparatively for practical use even if compared with existing technique. Keywords: Task allocation technique, Contentions, Multi-dimenstional Mesh/Torus CREST a) morie.yoshiyuki.404@m.kyushu-u.ac.jp b) nanri@cc.kyushu-u.ac.jp 1. 95

2 / / / [4][3][5] / FX10 TAHB RMATT / / C.D. Sudheer [12] T. Hoefler [11] T. Hatazaki[7] J. L. Traff[8] F. Ercal [6] T. Agarwal [9] G. Bhanot [10] 3D 3D Task Allocation by using HopByte (TAHB) TAHB [15][16] Rank Map Automatic Tuning Tool (RMATT) 96

3 RMATT TAHB 3D [4][3] / task1 task2 task3 task4 task5 task6 1 step1 step2 step3 step4 task1 task3 task5 task2 task4 task6 step1 step2 step3 step A, B C A, B 3 AB C A 123 B C A 135 B C TAHB 4. / / 4.1 Task Allocation with Consideration Concurrent Communication (TAC3) 97

4 4.2 TAC3 4.3 Concurrent Communication Set Concurrent Communication Set(CCS) 2 CCS CCS CCS CCS 2 CCS CCS CCS CCS CCS CCS CCS 4.4 [1][2][9] G t = {V t, E t }, G n = {V n, E n } 2 P G t = {V t, E t } E t e ab = (v a, v b ) E t a loop iccs for iproc loop i iproc i i or break; i++; for iproc CCS[iCCS] break; iccs++; 2 CCS b ID cid CCS ID TAC3 CCS CCS CCS (1) f(v t, V n, P ) = N 1 max i=0 n 1 t=0 M(t, i, tork(t, i, cid)) (1) coll(t, π(i), π(tork(t, i, cid)))/b t CCS IDN CCS i ID n π(i) i ID tork(t, i, cid) t CCS i cid ID B M(t, i, j) t CCS i j coll(t, p, q) t CCS p q 98

5 coll t p q / / (DOR) DOR 4.5 NP [9] [17] 5. TAC3 TAHB RMATT 5.1 FX10 TAC3 TAHB RMATT CG TAC3 CCS TAHB RMATT RMATT e1 1.0 e8, RMATT TAC3 CCS CCS TAC3 CCS (TAC3 barrier) (TAC3 no-barrier) 2 CCS 5.2 FX10 CPU Fujitsu SPARC64TM IXfx 1.848GHz (16 ) 32GB 768 OS Linux OSMPI Fujitsu Technical Computing Suite v1.0 Tofu interconnect[14] 5GB/s Tofu interconnect XYZABC / 4x2x8x2x3x2 99

6 X Y Z A C B [19] FX10 3 2x3x2 ABC 3 / XYZ 3 / 12 3 FX10 FX x2x4x2x3x2 ( 1)2x2x2x2x3x2 ( 2)1x1x4x2x3x2( 3)1x2x2x2x3x2 ( 4) , 4 48 FX NAS Parallel Benchmarks[18] CG Conjugate Gradient method MB 5.4 no-ringtahb RMATT-O2FRMATTTAC3 no-ring FX10 6 / 3 no-ring 6 XYZABC 3 3 TAHBRMATT-O2F TAC3 TAHB (2) hop(π(i), π(j)) size(i, j) (2) n 1 n 1 i=0 j=0 i, j IDn π(i) i ID size(i, j) i j hop(p, q) p q RMATT-O2F (3) (hop(π(i), π(j)) size(i, j)) max link (3) n 1 n 1 i=0 j=0 i, j IDn π(i) i ID size(i, j) i j hop(p, q) p q link max link link RMATT FX10 RMATT TAHBRMATT-O2FRMATTTAC

7 5.5 CCS CG 2 Recursive doubling x4 Recursive doubling CCS CCS 1 CCS x8 48 CCS sec sec 4 1.4sec no-ring 1 2.4sec 2 1.9sec 3 1.7sec 4 1.5sec TAC sec TAC3 TAC3 14msec 17msec 1 TAC3 TAC3 81msec TAHBRMATT-O2F sec48 1.3sec RMATT TAHB RMATT-O2F sec sec TAC3 48% TAC3 TAHB RMATT 43%, 79% TAC3 CCS 1 1 TAC3 CCS Performance Ratio shape1 (96nodes:1x2x4x2x3x2) shape2 (96nodes:2x2x2x2x3x2) shape3 (48nodes:1x1x4x2x3x2) shape4 (48nodes:1x2x2x2x3x2) no-ring TAHB RMATT-O2F RMATT TAC3 nobarrier TAC3 barrier Task Allocation TAHBRMATT-O2F, RMATT noring 3 ID RMATT RMATT-O2F 2 RMATT 3 6 / FX RMATT-O2F RMATT FX10 6 / RMATT CCS TAC3 1 CG TAC3 CCS 101

8 1 default no-ring TAHB RMATT-O2F RMATT TAC3 TAC3 1(96 ) 1.671sec 2.398sec 1.501sec 1.585sec 1.762sec 1.207sec 1.126sec 2(96 ) 1.241sec 1.936sec 1.478sec 1.466sec 1.843sec 1.032sec 1.049sec 3(48 ) 1.236sec 1.667sec 1.255sec 1.316sec 1.419sec 1.025sec 1.039sec 4(48 ) 1.427sec 1.455sec 1.260sec 1.300sec 1.415sec 1.027sec 1.041sec 2 TAC3 CCS (sec) (sec) TAC3 10 CCS 2 1.0sec 1, 3, 4, 9 4 3, 4, % 1 CCS 1 CCS CG 3 TAC3 CCS CCS 256KB 512KB 3 TAC3 CCS (KB) (sec) (sec) CCS 6.2 RMATT TAC3RMATT-O2FTAHB 48, TAC3 128secTAHB 35secRMATT-O2F 122sec 96 TAC3 272secTAHB 72sec RMATT-O2F 257sec RMATT RMATT sec TAC3 7. / FX10 TAHB RMATT 43%, 79% CCS CCS TAHB RMATT TAC3 102

9 2 CCS, CCS [1] S. H. Bokhari, On the mapping problem, IEEE Trans. Computers, 30(3), pp , [2] S. Y. Lee and J. K. Aggarwal, A mapping strategy for parallel processing, IEEE Trans. Computers, 36(4), pp , [3] Y. Morie, T. Nanri, and M. Kurokawa, Task allocation method for avoiding contentions by the information of concurrent communication, in Proceedings of the Tenth IASTED International Conference on Parallel and Distributed Computing and Networks, pp , Feb [4],,,,,,, MPI,, Vol.48, No.13, pp , Aug [5] Y. Morie, T. Nanri, Task Allocation Optimization for Neighboring Communication on Fat-Tree, in Proceedings of The Fifth International Symposium on Advances of Computing and Networking (AHPCN-2012), Jun [6] F. Ercal, J. Ramanujan, and P. Sadayappan, Task allocation onto a hypercube by recursive Mincut Bipartitioning, Journal of Parallel and Distributed Computing, Vol. 10, N. 1, pp , [7] T. Hatazaki, Rank reordering strategy for MPI topology creation function, PVM/MPI98, LNCS 1497, pp , [8] J. L. Traff, Implementing the MPI process topology mechanism, Conference on Networking and Computing, in Proceedings of the 2002 ACM/IEEE Conference on Supercomputing, pp. 1-14, [9] T. Agarwal, A.Sharma, and L. V. Kale, Topology-aware task mapping for reducing communication contention on large parallel machines, in Proceedings of IEEE International Parallel and Distributed Processing Symposium 2006, pp. 1-10, [10] G. Bhanot, A. Gara, P. Heidelberger, E. Lawless, J. Sexton, and Robert Walkup, Optimizing task layout on the Blue Gene/L supercomputer, IBM J. Res. Dev. 49, No. 2/3, pp , [11] T. Hoefler, T. Schneider, and A. Lumsdaine, Multistage switches are not crossbars: Effects of static routing in high-performance networks, in Proceedings of the 2008 IEEE International Conference on Cluster Computing, CLUSTER08, IEEE Computer Society, Oct [12] C.D. Sudheer, T. Nagaraju, P.K. Baruah, and A. Srinivasan, Optimizing assignment of threads to SPEs of the cell BE processor, Tenth IEEE International Workshop on Parallel and Distributed Scientific and Engineering Computing (PDSEC), in Proceedings of the 23rd International Parallel and Distributed Processing Symposium, IEEE, [13] T. Hoefler and J. L. Traeff, Sparse collective operations for MPI, in Proceedings of the 23rd IEEE International Parallel & Distributed Processing Symposium (IPDPS), HIPS Workshop, May [14] Y. Ajima, Y. Takagi, T. Inoue, S. Hiramoto and T. Shimizu, The tofu interconnect, in Proceedings of the 19th IEEE Annual Symposium High Performanace Interconnects, pp.87 94, [15] RMATT, SACSIS2011, pp , Mar [16] RMATT, HPCS2012, pp , jan [17], [18] NAS Parallel Benchmarks, [19] Y. Ajima, T. Inoue, S. Hiramoto, T. Shimizu, Tofu: Interconnect for the K computer,, FUJITSU Sci. Tech. J., Vol. 48, No. 3, pp , July

1 2 4 5 9 10 12 3 6 11 13 14 0 8 7 15 Iteration 0 Iteration 1 1 Iteration 2 Iteration 3 N N N! N 1 MOPT(Merge Optimization) 3) MOPT 8192 2 16384 5 MOP

1 2 4 5 9 10 12 3 6 11 13 14 0 8 7 15 Iteration 0 Iteration 1 1 Iteration 2 Iteration 3 N N N! N 1 MOPT(Merge Optimization) 3) MOPT 8192 2 16384 5 MOP 10000 SFMOPT / / MOPT(Merge OPTimization) MOPT FMOPT(Fast MOPT) FMOPT SFMOPT(Subgrouping FMOPT) SFMOPT 2 8192 31 The Proposal and Evaluation of SFMOPT, a Task Mapping Method for 10000 Tasks Haruka Asano