タスクネットワークの解析情報を用いたスケジューリング手法

全文

(1)2006−HPC−107（11） 2006／7／31. 社団法人情報処理学会研究報告 IPSJ SIG Technical Report. †. †. †. †. †. ††,. MegaScript MegaScript. A Task Scheduling Scheme Using Analytical Information on Task Network Satoshi Katano,† Eiichirou Mori,† Kazuhiko Ohno,† Takahiro Sasaki,† Toshio Kondo† and Hiroshi Nakashima††, We are developing a task-parallel script language named MegaScript. To obtain high performance in mega-scale environment, scheduling scheme considering load-balancing and communication cost is required. However, optimal scheduling is difficult because number of scheduled tasks is extremely large. In our scheduling scheme, a task network model is represented as composition of basic structures. Based on this model, we extract pipeline parallelism and dependency costs. Using the result, efficient scheduling is possible.. 1.. MegaScript 1)∼3). Pflops 100. MegaScript. Tflops. MegaScript. † Mie University †† Toyohashi University of Technology. 4). Presently with Kyoto University. −61− 1.

(2) t1 = T1.new() t2 = T2.new_array(M) t3 = T3.new_array(M*N) s1 = Stream.new() s2 = Stream.new_array(M) s1.connect(t1, IN) s1.connect(t2, OUT) for i in 0..M s2.connect(t2[i], IN) s2.connect(t3[i*N..(i+1)*N], OUT) end. 2. MegaScript MegaScript. 1. T1 S1 Ruby5). T2. 2.1. T2 M. S2. S2. MegaScript. T3. MegaScript. T3. T3. T3 N. N 2. input(1) FOR @arg[0] compute(100) END output(10) 3. Task. Stream. MegaScript 3 MegaScript ). ( 1. 2. 2.2 Cc. Ci. MegaScript MegaScript Cc Co 2). 3. −62− 2. Cc. 100 Co. arg[0] 10. Co.

(3) • Sequence. Branch. Indep. Dep. 4. 3.2. T1. T2. T1. Sequence. (1). .... Tn. T1. Indep. T2 Dep. (2). Branch. T1. (3) T2. (. ). (4). Sequence+loop. 4. 5. 4.1. 2.3 MegaScript create schedule. MegaScript. MegaScript. 3.. 4. Sequence. 3.1 Branch (1) (2). Indep Dep. Sequence+loop Sequence+loop • 4.1.1 •. −63− 3. ( 5 Sequence. (. ).. 5. ).

(4) Sequence T1. T1. T2. Sequence+loop T2. Indep. (1). (2). 7. input(1) 6. For @arg[0] conpute(50) output(1) END. MegaScript. 8. A. B. C. D. 9. T1 T1 7. 6. T2 T2 T1 T2. (2). • Sequence 4.2.1 Sequence • Indep. MegaScript Indep 8. • Dep Input Dep. 4. Indep • Sequence+loop. Dep. Output (. • • •. A: B: C:. •. D:. 9). Sequence+loop 4.2 B D. 7. (1). C 4 −64−.

(5) Cdi Cci. Ti. Cdi + Cci. Tj. Cdi. Ti. Cdi. Tj. Sequence. 4.3.1. Cci. Sequence. 10 Sequence. Ti. T j1. Cdi Cci. Cci +C di. Cdi Cci. Ti T jn. Cci +C di T j1. Cdi. 4.3.2 Cc T jn. Cd. Cdi. • Sequence 10 Sequence. 11. Ti Cdi1. T i1 C ci1. Tj. T in. Cdin Ccin. T i1. MAX(Cdi1+Cci1, .. , C din +C cin ). Cdi1 Cci1 Tj. T in. Tj Ti Cdi + Cci. Cdin Ccin. Ti Tj Ti. MIN(C di1, .. ,C din ). Tj. Ti Tj • 11. 12. Sequence Ti Ti. Cdi Cci. Ti. Cdi Cci. Tj1 . . . Tjn Ti. Ti Tj1 . . . Tjn. Tj. Cdi + Cci. Tj. Cdi. Ti. Tj1 . . . Tjn Ti. Tj1 . . . Tjn •. 13. 12 8. C 4.3. Ti1 . . . Tin Ti1 . . . Tin Cdi1 +. Tj Cci1 ,. . . ,Cdin + Ccin Tj Ti1 . . . Tin Ti1 . . . Tin Tj 5 −65−. Tj.

(6) T1. T2. 0 50. 50 50. T3. host1. host2. host1. host2. 0. 0. 50 100. T1. T3. 50. T5. 100 125. T2. 100 100 T4 25 T5 25. T4. T1. 50. T2. T3. T4 T5. 100 150. (1). (2). (3). 14. • 13 Sequence 4.4. 1). 14(1). 14(2) T1. T1 host2. 14(3). T1. T3 host1 100 150 T4 (1). ,. , , : MegaScript , SACSIS2003,. pp. 73–76 (2003). , , : MegaScript , 2003-HPC-95, pp. 113–118 (2003). 3) , , : MegaScript , 2003-HPC-95, pp. 119–124 (2003). 4) , , , , : , 2004HPC-100, pp. 19–24 (2004). 5) , : Ruby, ASCII (1999).. 2). T3. ,. host2 T5 175. host1 (2). 150. (2). 5. MegaScript. 6E −66−.

(7)