Performance Prediction of Parallel Applications with Parallel Patterns using Stochastic Methods
Resumo
One of the main problems in the high performance computing area is to find the best strategy to parallelize an application. In this context, the use of analytical methods to evaluate the performance behavior before the real implementation of such applications seems to be an interesting alternative and can help to identify better directions for the implementation strategies. In this work, the Stochastic Automata Network (SAN) formalism is adopted to model and evaluate the performance of parallel applications. The methodology used is based on the construction of generic SAN models to describe classical parallel programming patterns, like Master/Slave, Pipeline and Divide and Conquer. Those models are adapted to represent cases of a real application through the definition of input parameters values. Finally, we present a comparison between the results of the SAN models and a real application, aiming at verifying the accuracy of the adopted technique.
Referências
B. Plateau and K. Atif. Stochastic Automata Network of Modeling Parallel Systems. Software Engineering, IEEE Transactions on, 17(10):1093 –1108, October, 1991.
C. Bertolini, L. Brenner, P. Fernandes, A. Sales, and A. F. Zorzo. Structured Stochastic Modeling of Fault- Tolerant Systems. In 12th IEEE/ACM Internacional Symposium on Modelling, Analysis and Simulation on Computer and Telecommunication Systems (MASCOTS’ 04), pages 139–146, Volendam, The Netherlands, October, 2004. IEEE Press.
O. Gusak, T. Dayar, and J.-M. Fourneau. Iterative disaggregation for a class of lumpable discrete-time stochastic automata networks. Perform. Eval., 53:43–69, June, 2003.
R. Marculescu and A. Nandi. Probabilistic Application Modeling for System-Level Performance Analysis. In Design Automation & Test in Europe (DATE), pages 572–579, Munich, Germany, March, 2001.
L. Mokdad, J. Ben-Othman, and A. Gueroui. Quality of Service of a Rerouting Algorithm Using Stochastic Automata Networks. In 6th IEEE Symposium on Computers and Communications, pages 338–343, Hammamet, Tunisia, July, 2001. IEEE Computer Society.
G. Bolch, S. Greiner, H. Meer, and K. S. Trivedi. Queueing Networks and Markov Chains: Modeling and Performance Evaluation with Computer Science Applications. Wiley-Interscience, New York, NY, USA, 1998.
L. Brenner, L. G. Fernandes, P. Fernandes, and A. Sales. Performance Analysis Issues for Parallel Implementations of Propagation Algorithm. In Proceedings of the 15th Symposium on Computer Architecture and High Performance Computing, SBAC-PAD ’03, pages 183–190,Washington, DC, USA, 2003. IEEE Computer Society.
L. Baldo, L. G. Fernandes, P. Roisenberg, P. Velho, and T. Webber. Parallel PEPS Tool Performance Analysis Using Stochastic Automata Networks. In Euro-Par ’04, pages 214–219, Pisa, Italy, 2004. Springer.
T. G. Mattson, B. A. Sanders, and B. L. Massingill. Patterns for Parallel Programming. Addison-Wesley, Boston, MA, 2005.
A. Grama, A. Gupta, G. Karypis, and V. Kumar. Introduction to Parallel Computing. Pearson (Addison- Wesley), Boston, MA, 2003.
M. J. Quinn. Parallel Programming in C with MPI and OpenMP. McGraw-Hill, New York, 2004.
A. Benoit, L. Brenner, P. Fernandes, B. Plateau, and W. J. Stewart. The peps software tool. In P. Kemper and W.H. Sanders, editors, 13th International Conference on Modelling Techniques and Tools for Computer Performance Evaluation TOOLS 2003, pages 98– 115, Urbana, Illinois, USA, 2003.
L. F. M. de Moraes and D.L.F.G. Vieira. Analytical Modelling and Message Delay Performance Evaluation of the IEEE 802.16 MAC Protocol. In Proceedings of the 2010 IEEE International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems, MASCOTS ’10, pages 182–190, Washington, DC, USA, 2010. IEEE Computer Society.
A. Navarro, R. Asenjo, S. Tabik, and C. Cascaval. Analytical Modeling of Pipeline Parallelism. In Proceedings of the 2009 18th International Conference on Parallel Architectures and Compilation Techniques, pages 281–290, Washington, DC, USA, 2009. IEEE Computer Society.
F. Delamare, F. L. Dotti, P. Fernandes, C. M. Nunes, and L. C. Ost. Analytical Modeling of Random WayPoint Mobility Patterns. In Proceedings of the 3rd ACM international workshop on Performance evaluation of wireless ad hoc, sensor and ubiquitous networks, PE-WASUN ’06, pages 106–113, New York, NY, USA, 2006. ACM.
R. Chanin, M. Corrêa, P. Fernandes, A. Sales, R. Scheer, and A. F. Zorzo. Analytical Modeling for Operating System Schedulers on NUMA Systems. Electron. Notes Theor. Comput. Sci., 151:131–149, June, 2006.
L. Baldo, L. Brenner, L. G. Fernandes, P. Fernandes, and A. Sales. Performance Models For Master/Slave Parallel Programs. Electron. Notes Theor. Comput. Sci., 128:101–121, April, 2005.
C. Bertolini, L. Brenner, P. Fernandes, A. Sales, and A. F. Zorzo. Structured Stochastic Modeling of Fault- Tolerant Systems. In 12th IEEE/ACM Internacional Symposium on Modelling, Analysis and Simulation on Computer and Telecommunication Systems (MASCOTS’ 04), pages 139–146, Volendam, The Netherlands, October, 2004. IEEE Press.
O. Gusak, T. Dayar, and J.-M. Fourneau. Iterative disaggregation for a class of lumpable discrete-time stochastic automata networks. Perform. Eval., 53:43–69, June, 2003.
R. Marculescu and A. Nandi. Probabilistic Application Modeling for System-Level Performance Analysis. In Design Automation & Test in Europe (DATE), pages 572–579, Munich, Germany, March, 2001.
L. Mokdad, J. Ben-Othman, and A. Gueroui. Quality of Service of a Rerouting Algorithm Using Stochastic Automata Networks. In 6th IEEE Symposium on Computers and Communications, pages 338–343, Hammamet, Tunisia, July, 2001. IEEE Computer Society.
G. Bolch, S. Greiner, H. Meer, and K. S. Trivedi. Queueing Networks and Markov Chains: Modeling and Performance Evaluation with Computer Science Applications. Wiley-Interscience, New York, NY, USA, 1998.
L. Brenner, L. G. Fernandes, P. Fernandes, and A. Sales. Performance Analysis Issues for Parallel Implementations of Propagation Algorithm. In Proceedings of the 15th Symposium on Computer Architecture and High Performance Computing, SBAC-PAD ’03, pages 183–190,Washington, DC, USA, 2003. IEEE Computer Society.
L. Baldo, L. G. Fernandes, P. Roisenberg, P. Velho, and T. Webber. Parallel PEPS Tool Performance Analysis Using Stochastic Automata Networks. In Euro-Par ’04, pages 214–219, Pisa, Italy, 2004. Springer.
T. G. Mattson, B. A. Sanders, and B. L. Massingill. Patterns for Parallel Programming. Addison-Wesley, Boston, MA, 2005.
A. Grama, A. Gupta, G. Karypis, and V. Kumar. Introduction to Parallel Computing. Pearson (Addison- Wesley), Boston, MA, 2003.
M. J. Quinn. Parallel Programming in C with MPI and OpenMP. McGraw-Hill, New York, 2004.
A. Benoit, L. Brenner, P. Fernandes, B. Plateau, and W. J. Stewart. The peps software tool. In P. Kemper and W.H. Sanders, editors, 13th International Conference on Modelling Techniques and Tools for Computer Performance Evaluation TOOLS 2003, pages 98– 115, Urbana, Illinois, USA, 2003.
L. F. M. de Moraes and D.L.F.G. Vieira. Analytical Modelling and Message Delay Performance Evaluation of the IEEE 802.16 MAC Protocol. In Proceedings of the 2010 IEEE International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems, MASCOTS ’10, pages 182–190, Washington, DC, USA, 2010. IEEE Computer Society.
A. Navarro, R. Asenjo, S. Tabik, and C. Cascaval. Analytical Modeling of Pipeline Parallelism. In Proceedings of the 2009 18th International Conference on Parallel Architectures and Compilation Techniques, pages 281–290, Washington, DC, USA, 2009. IEEE Computer Society.
F. Delamare, F. L. Dotti, P. Fernandes, C. M. Nunes, and L. C. Ost. Analytical Modeling of Random WayPoint Mobility Patterns. In Proceedings of the 3rd ACM international workshop on Performance evaluation of wireless ad hoc, sensor and ubiquitous networks, PE-WASUN ’06, pages 106–113, New York, NY, USA, 2006. ACM.
R. Chanin, M. Corrêa, P. Fernandes, A. Sales, R. Scheer, and A. F. Zorzo. Analytical Modeling for Operating System Schedulers on NUMA Systems. Electron. Notes Theor. Comput. Sci., 151:131–149, June, 2006.
L. Baldo, L. Brenner, L. G. Fernandes, P. Fernandes, and A. Sales. Performance Models For Master/Slave Parallel Programs. Electron. Notes Theor. Comput. Sci., 128:101–121, April, 2005.
Publicado
26/10/2011
Como Citar
RAEDER, Mateus; GRIEBLER, Dalvan; BALDO, Lucas; FERNANDES, Luiz Gustavo.
Performance Prediction of Parallel Applications with Parallel Patterns using Stochastic Methods. In: SIMPÓSIO EM SISTEMAS COMPUTACIONAIS DE ALTO DESEMPENHO (SSCAD), 12. , 2011, Vitória.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2011
.
p. 97-104.
DOI: https://doi.org/10.5753/wscad.2011.17273.
