Scheduling Moldable BSP Tasks on Clouds
Resumo
O foco deste estudo é escalonamento de tarefas BSP moldáveis em ambientes de computação em nuvem. "Moldável" neste contexto está relacionado em possivelmente reduzir o número de processadores requisitados por uma tarefa BSP, recalculando seu custo de execução total a partir de um modelo de custo. A partir daí, analisamos como uma tarefa BSP moldável é influenciada pelo comportamento imprevisível das nuvens, simulando a execução de diversas tarefas BSP em nuvens computacionais públicas. O objetivo desse artigo é analisar a diferença entre o tempo de término daúltima tarefa (makespan), tanto em simulação quanto em nuvens reais, analisando os resultados e concluindo o quanto um modelo teórico é próximo a realidade.Referências
Armbrust, M., Fox, A., Grifth, R., Joseph, A. D., Katz, R., Konwinski, A., Lee, G., Patterson, D., Rabkin, A., Stoica, I., et al. (2010). A view of cloud computing. Communications of the ACM, 53(4):50–58.
Cáceres, E., Dehne, F., Ferreira, A., Flocchini, P., Rieping, I., Roncato, A., Santoro, N., and Song, S. W. (1997). Efcient parallel graph algorithms for coarse grained multicomputers and BSP. In Automata, Languages and Programming, pages 390–400. Springer.
Calinescu, R. (1997). A BSP approach to the scheduling of tightly-nested loops. In Proceedings of the 11th International Symposium on Parallel Processing, IPPS '97, pages 549–553, Washington, DC, USA. IEEE Computer Society.
Chandio, A., Bilal, K., Tziritas, N., Yu, Z., Jiang, Q., Khan, S., and Xu, C.-Z. (2014). A comparative study on resource allocation and energy efcient job scheduling strategies in large-scale parallel computing systems. Cluster Computing, 17(4):1349–1367.
Cordeiro, D., Goldman, A., Kraemer, A., and Junior, F. P. (2013). Using the BSP model on clouds. Cloud Computing and Big Data, 23:123.
Dehne, F., Fabri, A., and Rau-Chaplin, A. (1993). Scalable parallel geometric algorithms for coarse grained multicomputers. In Proceedings of the ninth annual symposium on Computational geometry, pages 298–307. ACM.
Dehne, F., Hutchinson, D., Maheshwari, A., and Dittrich, W. (1999). Reducing I/O complexity by simulating coarse grained parallel algorithms. In Parallel Processing, 1999. 13th International and 10th Symposium on Parallel and Distributed Processing, 1999. 1999 IPPS/SPDP. Proceedings, pages 14–20.
Dutot, P.-F., Netto, M. A. S., Goldman, A., and Kon, F. (2005). Scheduling moldable BSP tasks. In Job Scheduling Strategies for Parallel Processing, pages 157–172. Springer.
Feitelson, D. (2015). Parallel Workloads Archieve. http://www.cs.huji.ac.il/labs/parallel/workload/. Accessed: 2015-07-30.
Feitelson, D. G., Tsafrir, D., and Krakov, D. (2014). Experience with using the parallel workloads archive. Journal of Parallel and Distributed Computing, 74(10):2967–2982.
Gibbons, P., Matias, Y., and Ramachandran, V. (1998). The queue-read queue-write asyn-chronous PRAM model. Theoretical Computer Science, 196(1–2):3–29.
Gonçalves, M., Cunha, M., Sampaio, A., and Mendonça, N. C. (2015). Inferência de desempenho: Uma nova abordagem para o planejamento de capacidade de aplicações na nuvem. Anais do XXXIII Simpósio Brasileiro de Rede de Computadores e Sistemas Distribuídos.
Huang, K.-C., Huang, T.-C., Tsai, M.-J., and Chang, H.-Y. (2014). Moldable job scheduling for HPC as a service. In Park, J. J. J. H., Stojmenovic, I., Choi, M., and Xhafa, F., editors, Future Information Technology, volume 276 of Lecture Notes in Electrical Engineering, pages 43–48. Springer Berlin Heidelberg.
Huang, K.-C., Huanga, T.-C., Chang, M.-J. T. H.-Y., and Tung, Y.-H. (2013). Moldable job scheduling for HPC as a service with application speedup model and execution time information. Journal of Convergence, 4(4):14–22.
Hunold, S. (2015). One step toward bridging the gap between theory and practice in moldable task scheduling with precedence constraints. Concurrency and Computation: Practice and Experience, 27(4):1010–1026.
Juurlink, B. H. H. and Wijshoff, H. A. G. (1998). A quantitative comparison of parallel computation models. ACM Transactions on Computer Systems, 16(3):271–318.
Kirtzic, J. S. (2012). A Parallel Algorithm Design Model for the Gpu Architecture. PhD thesis, Richardson, TX, USA. AAI3547670.
Mell, P. and Grance, T. (2011). The nist denition of cloud computing.
Mu'alem, A. W. and Feitelson, D. G. (2001). Utilization, predictability, workloads, and user runtime estimates in scheduling the IBM SP2 with backlling. IEEE Transactions on Parallel and Distributed Systems, 12(6):529–543.
Nuaimi, K. A., Mohamed, N., Nuaimi, M. A., and Al-Jaroodi, J. (2012). A survey of load balancing in cloud computing: Challenges and algorithms. In Proceedings of the 2012 Second Symposium on Network Cloud Computing and Applications, NCCA '12, pages 137–142, Washington, DC, USA. IEEE Computer Society.
Skillicorn, D. B. and Talia, D. (1998). Models and languages for parallel computation. ACM Computing Surveys, 30(2):123–169.
Valiant, L. G. (1990). A bridging model for parallel computation. Commun. ACM, 33(8):103–111.
Wei, Y. and Blake, M. B. (2010). Service-oriented computing and cloud computing: Challenges and opportunities. IEEE Internet Computing, 14(6):72–75.
Yuvaraj, B. and Palanivel, K. A survey of virtual machine placement algorithms in cloud International Journal on Recent and Innovation Trends in computing environment. Computing and Communication, 3:121 – 126.
Cáceres, E., Dehne, F., Ferreira, A., Flocchini, P., Rieping, I., Roncato, A., Santoro, N., and Song, S. W. (1997). Efcient parallel graph algorithms for coarse grained multicomputers and BSP. In Automata, Languages and Programming, pages 390–400. Springer.
Calinescu, R. (1997). A BSP approach to the scheduling of tightly-nested loops. In Proceedings of the 11th International Symposium on Parallel Processing, IPPS '97, pages 549–553, Washington, DC, USA. IEEE Computer Society.
Chandio, A., Bilal, K., Tziritas, N., Yu, Z., Jiang, Q., Khan, S., and Xu, C.-Z. (2014). A comparative study on resource allocation and energy efcient job scheduling strategies in large-scale parallel computing systems. Cluster Computing, 17(4):1349–1367.
Cordeiro, D., Goldman, A., Kraemer, A., and Junior, F. P. (2013). Using the BSP model on clouds. Cloud Computing and Big Data, 23:123.
Dehne, F., Fabri, A., and Rau-Chaplin, A. (1993). Scalable parallel geometric algorithms for coarse grained multicomputers. In Proceedings of the ninth annual symposium on Computational geometry, pages 298–307. ACM.
Dehne, F., Hutchinson, D., Maheshwari, A., and Dittrich, W. (1999). Reducing I/O complexity by simulating coarse grained parallel algorithms. In Parallel Processing, 1999. 13th International and 10th Symposium on Parallel and Distributed Processing, 1999. 1999 IPPS/SPDP. Proceedings, pages 14–20.
Dutot, P.-F., Netto, M. A. S., Goldman, A., and Kon, F. (2005). Scheduling moldable BSP tasks. In Job Scheduling Strategies for Parallel Processing, pages 157–172. Springer.
Feitelson, D. (2015). Parallel Workloads Archieve. http://www.cs.huji.ac.il/labs/parallel/workload/. Accessed: 2015-07-30.
Feitelson, D. G., Tsafrir, D., and Krakov, D. (2014). Experience with using the parallel workloads archive. Journal of Parallel and Distributed Computing, 74(10):2967–2982.
Gibbons, P., Matias, Y., and Ramachandran, V. (1998). The queue-read queue-write asyn-chronous PRAM model. Theoretical Computer Science, 196(1–2):3–29.
Gonçalves, M., Cunha, M., Sampaio, A., and Mendonça, N. C. (2015). Inferência de desempenho: Uma nova abordagem para o planejamento de capacidade de aplicações na nuvem. Anais do XXXIII Simpósio Brasileiro de Rede de Computadores e Sistemas Distribuídos.
Huang, K.-C., Huang, T.-C., Tsai, M.-J., and Chang, H.-Y. (2014). Moldable job scheduling for HPC as a service. In Park, J. J. J. H., Stojmenovic, I., Choi, M., and Xhafa, F., editors, Future Information Technology, volume 276 of Lecture Notes in Electrical Engineering, pages 43–48. Springer Berlin Heidelberg.
Huang, K.-C., Huanga, T.-C., Chang, M.-J. T. H.-Y., and Tung, Y.-H. (2013). Moldable job scheduling for HPC as a service with application speedup model and execution time information. Journal of Convergence, 4(4):14–22.
Hunold, S. (2015). One step toward bridging the gap between theory and practice in moldable task scheduling with precedence constraints. Concurrency and Computation: Practice and Experience, 27(4):1010–1026.
Juurlink, B. H. H. and Wijshoff, H. A. G. (1998). A quantitative comparison of parallel computation models. ACM Transactions on Computer Systems, 16(3):271–318.
Kirtzic, J. S. (2012). A Parallel Algorithm Design Model for the Gpu Architecture. PhD thesis, Richardson, TX, USA. AAI3547670.
Mell, P. and Grance, T. (2011). The nist denition of cloud computing.
Mu'alem, A. W. and Feitelson, D. G. (2001). Utilization, predictability, workloads, and user runtime estimates in scheduling the IBM SP2 with backlling. IEEE Transactions on Parallel and Distributed Systems, 12(6):529–543.
Nuaimi, K. A., Mohamed, N., Nuaimi, M. A., and Al-Jaroodi, J. (2012). A survey of load balancing in cloud computing: Challenges and algorithms. In Proceedings of the 2012 Second Symposium on Network Cloud Computing and Applications, NCCA '12, pages 137–142, Washington, DC, USA. IEEE Computer Society.
Skillicorn, D. B. and Talia, D. (1998). Models and languages for parallel computation. ACM Computing Surveys, 30(2):123–169.
Valiant, L. G. (1990). A bridging model for parallel computation. Commun. ACM, 33(8):103–111.
Wei, Y. and Blake, M. B. (2010). Service-oriented computing and cloud computing: Challenges and opportunities. IEEE Internet Computing, 14(6):72–75.
Yuvaraj, B. and Palanivel, K. A survey of virtual machine placement algorithms in cloud International Journal on Recent and Innovation Trends in computing environment. Computing and Communication, 3:121 – 126.
Publicado
18/10/2015
Como Citar
OKADA, Thiago; GONZÁLES, Marcos; VEL LEJBMAN, Alfredo.
Scheduling Moldable BSP Tasks on Clouds. In: SIMPÓSIO EM SISTEMAS COMPUTACIONAIS DE ALTO DESEMPENHO (SSCAD), 16. , 2015, Florianópolis.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2015
.
p. 144-155.
DOI: https://doi.org/10.5753/wscad.2015.14279.
