Uso de Modelos Analíticos na Modelagem de Aplicações Paralelas Distribuídas
Resumo
Uma metodologia para desenvolvimento de programas paralelos deve especificar mecanismos capazes de caracterizar o comportamento das aplicações e permitir estudos sobre o desempenho de diferentes modelos de soluções. A metodologia PEMPIs-Het permite a modelagem, avaliação e predição de desempenho de programas paralelos em ambientes homogêneos e heterogêneos. Neste artigo, algumas aplicações são modeladas e a precisão das estimativas geradas para o tempo de execução das aplicações é verificada através de testes experimentais. Uma avaliação sobre diferentes modelos de soluções distribuídas é realizada e uma estimativa de desempenho é gerada para cada abordagem.Referências
Badia, R. M., Rodríguez, G., and Labarta, J. (2003). Deriving analytical models from a limited number of runs. In PARCO, pages 769–776.
Badia, R. M., Sirvent, R., Bubak, M., Funika, W., and Machner, P. (2007). Performance monitoring of grid superscalar with ocm-g/g-pm: Tuning and improvements. In CoreGRID Workshop on Grid Programming Model Grid and P2P Systems Architecture, Grid Systems, Tools and Environments, number TR-0080.
Burns, G., Daoud, R., and Vaigl, J. (1994). LAM: An Open Cluster Environment for MPI. In Proceedings of Supercomputing Symposium, pages 379–386.
Buyya, R. (1999). High Performance Cluster Computing: Programming and Applications. Prentice Hall PTR, Upper Saddle River, NJ, USA.
Cirne, W., Paranhos, D., Costa, L., Santos-Neto, E., Brasileiro, F., Sauve, J., Silva, F. A. B., Barros, C. O., and Silveira, C. (2003). Running bag-of-tasks applications on computational grids: The mygrid approach. icpp, 00:407.
Clark, D. (1995). Scheduling of parallel jobs on dynamic heterogenous networks.
Culler, D., Karp, R., Patterson, D., Sahay, A., Schauser, K. E., Santos, E., Subramonian, R., and von Eicken, T. (1993). Logp: towards a realistic model of parallel computation. In PPOPP ’93: Proceedings of the fourth ACM SIGPLAN symposium on Principles and practice of parallel programming, pages 1–12, New York, NY, USA. ACM Press.
de Oliveira Dias Júnior, E. A. (2006). Performance prediction and tuning in a multi-cluster environment. PhD thesis, Barcelona, Spain.
Foster, I. and Kesselman, C. (2003). The Grid 2: Blueprint for a New Computing Infrastructure. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA.
Foster, I., Kesselman, C., Nick, J. M., and Tuecke, S. (2002). The physiology of the grid: An open grid services architecture for distributed systems integration. Technical Report OGSI WG, Global Grid Forum.
Foster, I., Kesselman, C., and Tuecke, S. (2001). The anatomy of the grid: Enabling scalable virtual organizations. International Journal of High Performance Computing Applications, 15(3).
Franklin, M. and Govindan, V. (2003). The n-body problem: Distributed system load balancing and performance evaluation. Technical Report 93-16, Department of Computer Science and Engineering, Washington University, St. Louis.
Geist, A., Beguelin, A., Dongarra, J., Jiang, W., Manchek, R., and Sunderam, V. (1994). PVM: Parallel virtual machine: a users’ guide and tutorial for networked parallel computing. MIT Press, Cambridge, MA, USA.
Grove, D. A. (2003). A Performance Modeling System for Message-Passing Parallel Programs. PhD thesis, University of Adelaide, Department of Computer Science, Adelaide.
Grove, D. A. and Coddington, P. D. (2005a). Communication benchmarking and performance modelling of mpi programs on cluster computers. J. Supercomput., 34(2):201–217.
Grove, D. A. and Coddington, P. D. (2005b). Modeling message-passing programs with a performance evaluating virtual parallel machine. Perform. Eval., 60(1-4):165–187.
Laine, J. M. and Midorikawa, E. T. (2007a). Analisando a predição de desempenho com os modelos analíticos gerados pela metodologia pempis-het. WSCAD’07 - VIII Workshop em Sistemas Computacionais de Alto Desempenho.
Laine, J. M. and Midorikawa, E. T. (2007b). Using analytical models to load balancing in a heterogeneous network of computers. In Malyshkin, V. E., editor, PaCT, volume 4671 of Lecture Notes in Computer Science, pages 559–568. Springer.
Laine, J. M., Oliveira, H. M., and Midorikawa, E. T. (2003). Modeling repetition structures in mpi programs using a new graphical model. In International Conference on Parallel and Distributed Processing Techniques and Applications - PDPTA’03, pages 1696–1701, Las Vegas, Nevada.
Lastovetsky, A., Mkwawa, I.-H., and O’Flynn, M. (2006). An accurate communication model of a heterogeneous cluster based on a switch-enabled ethernet network. In ICPADS ’06: Proceedings of the 12th International Conference on Parallel and Distributed Systems, pages 15–20, Washington, DC, USA. IEEE Computer Society.
Lastovetsky, A. and Twamley, J. (2005). Towards a realistic performance model for networks of heterogeneous computers. pages 39–58. Springer.
Midorikawa, E. T., Oliveira, H., and Laine, J. M. (2005). Pempis: A new methodology for modeling and prediction of mpi programs performance. International Journal of Parallel Programming, 33(5):499–527.
Midorikawa, E. T., Oliveira, H. M., and Laine, J. M. (2004). Pempis: A new methodology for modeling and prediction of mpi programs performance. In 16th Symposium on Computer Architecture and High Performance Computing (SBAC-PAD 2004), pages 246–253, Foz do Iguaçu, Brazil. IEEE Computer Society.
Németh, Z. and Sunderam, V. (2002). A comparison of conventional distributed computing environments and computational grids. In Proceedings of the ICCS2002, volume II, pages 729–738, Amsterdam. Springer.
Nemeth, Z. and Sunderam, V. (2002). A formal framework for defining grid systems. In 2nd IEEE/ACM International Symposium on Cluster Computing and the Grid (CCGRID’2002), pages 202–211, Berlin. IEEE Computer Society Press.
Németh, Z. and Sunderam, V. (2003). Characterizing grids: Attributes, definitions, and formalisms. Journal of Grid Computing, 1(1):9–23.
Oliveira, H. M., Laine, J. M., and Midorikawa, E. T. (2002). Performance analysis and prediction of some mpi communication primitives. In International Conference on Parallel and Distributed Processing Techniques and Applications - PDPTA’02, Las Vegas, Nevada.
Oliveira, H. M., Laine, J. M., and Midorikawa, E. T. (2003). Algumas contribuições para modelagem de programas paralelos mpi. In WPERFORMANCE03 - II Workshop em Desempenho de Sistemas Computacionais e de Computação, Campinas, São Paulo, Brazil.
Polychronopoulos, C. D. and Kuck, D. J. (1987). Guided self-scheduling: a practical scheduling scheme for parallel supercomputers. IEEE Transactions on Computers, C-36(12):1425–1439.
Schopf, J. M. (1998). Performance prediction and scheduling for parallel applications on multi-user clusters. PhD thesis, La Jolla, CA, USA.
Shih, W.-C., Yang, C.-T., and Tseng, S.-S. (2006). A performance-based approach to dynamic workload distribution for master-slave applications on grid environments. In GPC, pages 73–82.
Shih, W.-C., Yang, C.-T., and Tseng, S.-S. (2007). A performance-based parallel loop scheduling on grid environments. J. Supercomput., 41(3):247–267.
Snir, M. and Otto, S. (1998). MPI — The Complete Reference: The MPI Core. MIT Press, Cambridge, MA, USA.
Squyres, J. M. and Lumsdaine, A. (2003). A Component Architecture for LAM/MPI. In Proceedings, 10th European PVM/MPI Users’ Group Meeting, number 2840 in Lecture Notes in Computer Science, pages 379–387, Venice, Italy. Springer-Verlag.
Tam, A. T. C. and Wang, C.-L. (1999). Realistic communication model for parallel computing on cluster. In IWCC ’99: Proceedings of the 1st IEEE Computer Society International Workshop on Cluster Computing, page 92, Washington, DC, USA. IEEE Computer Society.
Tzen, T. T. and Ni, L. M. (1993). Trapezoidal self-scheduling: A practical scheduling scheme for parallel compilers. IEEE Transactions on Parallel and Distributed Systems, 4(1):87–98.
Yang, C.-T. and Chang, S.-C. (2003). A parallel loop self-scheduling on extremely heterogeneous pc clusters. In International Conference on Computational Science, pages 1079–1088.
Yang, C.-T., Cheng, K.-W., and Shih, W.-C. (2007). On development of an efficient parallel loop self-scheduling for grid computing environments. Parallel Comput., 33(7-8):467–487.
Yang, C.-T., Shih, W.-C., and Tseng, S.-S. (2006). A dynamic partitioning self-scheduling scheme for parallel loops on heterogeneous clusters. In International Conference on Computational Science (1), pages 810–813.
Badia, R. M., Sirvent, R., Bubak, M., Funika, W., and Machner, P. (2007). Performance monitoring of grid superscalar with ocm-g/g-pm: Tuning and improvements. In CoreGRID Workshop on Grid Programming Model Grid and P2P Systems Architecture, Grid Systems, Tools and Environments, number TR-0080.
Burns, G., Daoud, R., and Vaigl, J. (1994). LAM: An Open Cluster Environment for MPI. In Proceedings of Supercomputing Symposium, pages 379–386.
Buyya, R. (1999). High Performance Cluster Computing: Programming and Applications. Prentice Hall PTR, Upper Saddle River, NJ, USA.
Cirne, W., Paranhos, D., Costa, L., Santos-Neto, E., Brasileiro, F., Sauve, J., Silva, F. A. B., Barros, C. O., and Silveira, C. (2003). Running bag-of-tasks applications on computational grids: The mygrid approach. icpp, 00:407.
Clark, D. (1995). Scheduling of parallel jobs on dynamic heterogenous networks.
Culler, D., Karp, R., Patterson, D., Sahay, A., Schauser, K. E., Santos, E., Subramonian, R., and von Eicken, T. (1993). Logp: towards a realistic model of parallel computation. In PPOPP ’93: Proceedings of the fourth ACM SIGPLAN symposium on Principles and practice of parallel programming, pages 1–12, New York, NY, USA. ACM Press.
de Oliveira Dias Júnior, E. A. (2006). Performance prediction and tuning in a multi-cluster environment. PhD thesis, Barcelona, Spain.
Foster, I. and Kesselman, C. (2003). The Grid 2: Blueprint for a New Computing Infrastructure. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA.
Foster, I., Kesselman, C., Nick, J. M., and Tuecke, S. (2002). The physiology of the grid: An open grid services architecture for distributed systems integration. Technical Report OGSI WG, Global Grid Forum.
Foster, I., Kesselman, C., and Tuecke, S. (2001). The anatomy of the grid: Enabling scalable virtual organizations. International Journal of High Performance Computing Applications, 15(3).
Franklin, M. and Govindan, V. (2003). The n-body problem: Distributed system load balancing and performance evaluation. Technical Report 93-16, Department of Computer Science and Engineering, Washington University, St. Louis.
Geist, A., Beguelin, A., Dongarra, J., Jiang, W., Manchek, R., and Sunderam, V. (1994). PVM: Parallel virtual machine: a users’ guide and tutorial for networked parallel computing. MIT Press, Cambridge, MA, USA.
Grove, D. A. (2003). A Performance Modeling System for Message-Passing Parallel Programs. PhD thesis, University of Adelaide, Department of Computer Science, Adelaide.
Grove, D. A. and Coddington, P. D. (2005a). Communication benchmarking and performance modelling of mpi programs on cluster computers. J. Supercomput., 34(2):201–217.
Grove, D. A. and Coddington, P. D. (2005b). Modeling message-passing programs with a performance evaluating virtual parallel machine. Perform. Eval., 60(1-4):165–187.
Laine, J. M. and Midorikawa, E. T. (2007a). Analisando a predição de desempenho com os modelos analíticos gerados pela metodologia pempis-het. WSCAD’07 - VIII Workshop em Sistemas Computacionais de Alto Desempenho.
Laine, J. M. and Midorikawa, E. T. (2007b). Using analytical models to load balancing in a heterogeneous network of computers. In Malyshkin, V. E., editor, PaCT, volume 4671 of Lecture Notes in Computer Science, pages 559–568. Springer.
Laine, J. M., Oliveira, H. M., and Midorikawa, E. T. (2003). Modeling repetition structures in mpi programs using a new graphical model. In International Conference on Parallel and Distributed Processing Techniques and Applications - PDPTA’03, pages 1696–1701, Las Vegas, Nevada.
Lastovetsky, A., Mkwawa, I.-H., and O’Flynn, M. (2006). An accurate communication model of a heterogeneous cluster based on a switch-enabled ethernet network. In ICPADS ’06: Proceedings of the 12th International Conference on Parallel and Distributed Systems, pages 15–20, Washington, DC, USA. IEEE Computer Society.
Lastovetsky, A. and Twamley, J. (2005). Towards a realistic performance model for networks of heterogeneous computers. pages 39–58. Springer.
Midorikawa, E. T., Oliveira, H., and Laine, J. M. (2005). Pempis: A new methodology for modeling and prediction of mpi programs performance. International Journal of Parallel Programming, 33(5):499–527.
Midorikawa, E. T., Oliveira, H. M., and Laine, J. M. (2004). Pempis: A new methodology for modeling and prediction of mpi programs performance. In 16th Symposium on Computer Architecture and High Performance Computing (SBAC-PAD 2004), pages 246–253, Foz do Iguaçu, Brazil. IEEE Computer Society.
Németh, Z. and Sunderam, V. (2002). A comparison of conventional distributed computing environments and computational grids. In Proceedings of the ICCS2002, volume II, pages 729–738, Amsterdam. Springer.
Nemeth, Z. and Sunderam, V. (2002). A formal framework for defining grid systems. In 2nd IEEE/ACM International Symposium on Cluster Computing and the Grid (CCGRID’2002), pages 202–211, Berlin. IEEE Computer Society Press.
Németh, Z. and Sunderam, V. (2003). Characterizing grids: Attributes, definitions, and formalisms. Journal of Grid Computing, 1(1):9–23.
Oliveira, H. M., Laine, J. M., and Midorikawa, E. T. (2002). Performance analysis and prediction of some mpi communication primitives. In International Conference on Parallel and Distributed Processing Techniques and Applications - PDPTA’02, Las Vegas, Nevada.
Oliveira, H. M., Laine, J. M., and Midorikawa, E. T. (2003). Algumas contribuições para modelagem de programas paralelos mpi. In WPERFORMANCE03 - II Workshop em Desempenho de Sistemas Computacionais e de Computação, Campinas, São Paulo, Brazil.
Polychronopoulos, C. D. and Kuck, D. J. (1987). Guided self-scheduling: a practical scheduling scheme for parallel supercomputers. IEEE Transactions on Computers, C-36(12):1425–1439.
Schopf, J. M. (1998). Performance prediction and scheduling for parallel applications on multi-user clusters. PhD thesis, La Jolla, CA, USA.
Shih, W.-C., Yang, C.-T., and Tseng, S.-S. (2006). A performance-based approach to dynamic workload distribution for master-slave applications on grid environments. In GPC, pages 73–82.
Shih, W.-C., Yang, C.-T., and Tseng, S.-S. (2007). A performance-based parallel loop scheduling on grid environments. J. Supercomput., 41(3):247–267.
Snir, M. and Otto, S. (1998). MPI — The Complete Reference: The MPI Core. MIT Press, Cambridge, MA, USA.
Squyres, J. M. and Lumsdaine, A. (2003). A Component Architecture for LAM/MPI. In Proceedings, 10th European PVM/MPI Users’ Group Meeting, number 2840 in Lecture Notes in Computer Science, pages 379–387, Venice, Italy. Springer-Verlag.
Tam, A. T. C. and Wang, C.-L. (1999). Realistic communication model for parallel computing on cluster. In IWCC ’99: Proceedings of the 1st IEEE Computer Society International Workshop on Cluster Computing, page 92, Washington, DC, USA. IEEE Computer Society.
Tzen, T. T. and Ni, L. M. (1993). Trapezoidal self-scheduling: A practical scheduling scheme for parallel compilers. IEEE Transactions on Parallel and Distributed Systems, 4(1):87–98.
Yang, C.-T. and Chang, S.-C. (2003). A parallel loop self-scheduling on extremely heterogeneous pc clusters. In International Conference on Computational Science, pages 1079–1088.
Yang, C.-T., Cheng, K.-W., and Shih, W.-C. (2007). On development of an efficient parallel loop self-scheduling for grid computing environments. Parallel Comput., 33(7-8):467–487.
Yang, C.-T., Shih, W.-C., and Tseng, S.-S. (2006). A dynamic partitioning self-scheduling scheme for parallel loops on heterogeneous clusters. In International Conference on Computational Science (1), pages 810–813.
Publicado
12/07/2008
Como Citar
LAINE, Jean M.; MIDORIKAWA, Edson T..
Uso de Modelos Analíticos na Modelagem de Aplicações Paralelas Distribuídas. In: WORKSHOP EM DESEMPENHO DE SISTEMAS COMPUTACIONAIS E DE COMUNICAÇÃO (WPERFORMANCE), 7. , 2008, Belém/PA.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2008
.
p. 200-219.
ISSN 2595-6167.
