Solução eficiente de modelos estruturados a partir de descritores tensoriais combinados a estruturas arborescentes
Resumo
Formalismos Markovianos estruturados surgiram para facilitar a representação de modelos com inúmeros estados e transições. Entretanto, esta estruturação introduz desafios algorítmicos, tais como detecção de estados válidos, bem como soluções numéricas especializadas. Pesquisas recentes propõem utilizar Diagramas de Decisão Multi-valorados (MDD) para armazenamento compacto deste estados. Neste artigo apresenta-se uma técnica eficiente de mapeamento das transições entre estados, permitindo adequar a solução via métodos iterativos, ou mesmo diretos. Resultados preliminares mostram ganhos significativos em tempo de processamento e memória em função da relação entre o conjunto de estados total e válidos do modelo.
Referências
Baldo, L., Brenner, L., Fernandes, L. G., Fernandes, P., and Sales, A. (2005). Performance Models for Master/Slave Parallel Programs. Electronic Notes In Theoretical Computer Science (ENTCS), 128(4):101–121.
Benoit, A., Fernandes, P., Plateau, B., and Stewart, W. J. (2004). On the benefits of using functional transitions and Kronecker algebra. Performance Evaluation, 58(4):367–390.
Bertolini, C., Brenner, L., Fernandes, P., Sales, A., and Zorzo, A. F. (2004a). Structured Stochastic Modeling of Fault-Tolerant Systems. In Proceedings of the 12th IEEE/ACM Int. Symposium on Modelling, Analysis and Simulation on Computer and Telecommunication Systems (MASCOTS’04), pages 139–146. IEEE Computer Society.
Bertolini, C., Farina, A. G., Fernandes, P., and Oliveira, F. M. (2004b). Test Case Generation using Stochastic Automata Networks: Quantitative Analysis. In Proc. of the 2nd IEEE Int. Conf. on Software Engineering and Formal Methods, pages 251–260.
Brenner, L., Fernandes, P., Plateau, B., and Sbeity, I. (2007). PEPS2007 - Stochastic Automata Networks Software Tool. In Proceedings of the 4th IEEE International Conference on the Quantitative Evaluation of Systems (QEST 2007), pages 163–164.
Brenner, L., Fernandes, P., and Sales, A. (2005). The Need for and the Advantages of Generalized Tensor Algebra for Kronecker Structured Representations. International Journal of Simulation: Systems, Science & Technology (IJSIM), 6(3-4):52–60.
Buchholz, P., Ciardo, G., Donatelli, S., and Kemper, P. (2000). Complexity of memoryefficient Kronecker operations with applications to the solution of Markov models. INFORMS Journal on Computing, 12(3):203–222.
Buchholz, P. and Dayar, T. (2004). Block SOR for Kronecker structured representations. Linear Algebra and its Applications, 386:83–109.
Chanin, R., Corrêa, M., Fernandes, P., Sales, A., Scheer, R., and Zorzo, A. F. (2006). Analytical Modeling for Operating System Schedulers on NUMA Systems. Electronic Notes in Theoretical Computer Science (ENTCS), 151(3):131–149.
Czekster, R. M. (2010). Solução numérica de descritores Markovianos a partir de reestruturações de termos tensoriais. PhD thesis, Pontifícia Universidade Católica do Rio Grande do Sul (PUCRS), Brasil.
Czekster, R. M., Fernandes, P., Sales, A., and Webber, T. (2010a). Analytical Modeling of Software Development Teams in Globally Distributed Projects. In Proc. of the 5th IEEE Int. Conference on Global Software Engineering (ICGSE’10), pages 287–296.
Czekster, R. M., Fernandes, P., Sales, A., and Webber, T. (2010b). Restructuring tensor products to enhance the numerical solution of structured Markov chains. In Proceedings of the 6th International Conference on the Numerical Solution of Markov Chains (NSMC ’10), pages 36–39, Williamsburg, VA, USA.
Czekster, R. M., Fernandes, P., Sales, A., Webber, T., and Zorzo, A. (2011). Stochastic model for QoS assessment in multi-tier web services. In International Workshop on Practical Applications of Stochastic Modelling (PASM ’11), pages 93–109.
Czekster, R. M., Fernandes, P., Vincent, J. M., and Webber, T. (2007). Split: a flexible and efficient algorithm to vector-descriptor product. In Proc. of the 2nd Int. Conf. on Performance Evaluation, Methodologies and Tools (ValueTools ’07), Nantes, France.
Czekster, R. M., Fernandes, P., and Webber, T. (2009). GTAexpress: a Software Package to Handle Kronecker Descriptors. In Proc. of the 6th IEEE Int. Conference on Quantitative Evaluation of Systems (QEST 2009), pages 281–282, Budapest, Hungary.
Dotti, F. L., Fernandes, P., and Nunes, C. M. (2011). Structured Markovian Models for Discrete Spatial Mobile Node Distribution. Journal of the Brazilian Computer Society (JBCS), 17(1):31–52.
Dotti, F. L., Fernandes, P., Sales, A., and Santos, O. M. (2005). Modular Analytical Performance Models for Ad Hoc Wireless Networks. In Proc. of the 3rd IEEE Int. Symp. on Modeling and Optim. in Mobile, Ad Hoc, and Wireless Nets, pages 164–173.
Fernandes, P., Plateau, B., and Stewart, W. J. (1998). Efficient descriptor-vector multiplication in Stochastic Automata Networks. Journal of the ACM, 45(3):381–414.
Fernandes, P., Sales, A., Santos, A. R., and Webber, T. (2011). Performance Evaluation of Software Development Teams: A Practical Case Study. In International Workshop on Practical Applications of Stochastic Modelling (PASM ’11), pages 5–21.
Fernandes, P., Vincent, J. M., and Webber, T. (2008). Perfect Simulation of Stochastic Automata Networks, volume 5055 of LNCS, pages 249–263. Springer-Verlag.
Miner, A. S. (2002). Efficient state space generation of GSPNs using decision diagrams. In International Conference on Dependable Systems and Networks (DSN 2002), pages 637–646, Washington, DC, USA.
Miner, A. S. and Ciardo, G. (1999a). A data structure for the efficient Kronecker solution of GSPNs. In Proceedings of the 8th International Workshop on Petri Nets and Performance Models, pages 22–31, Zaragoza, Spain.
Miner, A. S. and Ciardo, G. (1999b). Efficient Reachability Set Generation and Storage Using Decision Diagrams. In Proc. of the 20th International Conference on Applications and Theory of Petri Nets, volume 1639 of LNCS, pages 6–25. Springer-Verlag.
Mokdad, L., Ben-Othman, J., and Gueroui, A. (2001). Quality of Service of a Rerouting Algorithm Using Stochastic Automata Networks. In Proceedings of the 6th IEEE Symposium on Computers and Communications, pages 338–343, Hammamet, Tunisia.
Plateau, B. (1985). On the stochastic structure of parallelism and synchronization models for distributed algorithms. In Proc. of the 1985 ACM SIGMETRICS Conf. on Measurements and Modeling of Computer Systems, pages 147–154, Austin, Texas, USA.
Saad, Y. (1995). Iterative Methods for Sparse Linear Systems. Boston: PWS Publishing Company.
Sales, A. (2009). Réseaux d’Automates Stochastiques: Génération de l’espace d’états atteignables et Multiplication vecteur-descripteur pour une sémantique en temps discret. PhD thesis, Institut National Polytechnique de Grenoble, France. [link].
Sales, A. and Plateau, B. (2009). Reachable State Space Generation for Structured Models which use Functional Transitions. In Proc. of the 6th IEEE Int. Conference on the Quantitative Evaluation of Systems (QEST 2009), pages 269–278, Budapest, Hungary.
Stewart, W. J. (1994). Introduction to the numerical solution of Markov chains. Princeton University Press.
Webber, T. (2009). Reducing the Impact of State Space Explosion in Stochastic Automata Networks. PhD thesis, Pontifícia Universidade Católica do Rio Grande do Sul (PUCRS), Brasil.
Benoit, A., Fernandes, P., Plateau, B., and Stewart, W. J. (2004). On the benefits of using functional transitions and Kronecker algebra. Performance Evaluation, 58(4):367–390.
Bertolini, C., Brenner, L., Fernandes, P., Sales, A., and Zorzo, A. F. (2004a). Structured Stochastic Modeling of Fault-Tolerant Systems. In Proceedings of the 12th IEEE/ACM Int. Symposium on Modelling, Analysis and Simulation on Computer and Telecommunication Systems (MASCOTS’04), pages 139–146. IEEE Computer Society.
Bertolini, C., Farina, A. G., Fernandes, P., and Oliveira, F. M. (2004b). Test Case Generation using Stochastic Automata Networks: Quantitative Analysis. In Proc. of the 2nd IEEE Int. Conf. on Software Engineering and Formal Methods, pages 251–260.
Brenner, L., Fernandes, P., Plateau, B., and Sbeity, I. (2007). PEPS2007 - Stochastic Automata Networks Software Tool. In Proceedings of the 4th IEEE International Conference on the Quantitative Evaluation of Systems (QEST 2007), pages 163–164.
Brenner, L., Fernandes, P., and Sales, A. (2005). The Need for and the Advantages of Generalized Tensor Algebra for Kronecker Structured Representations. International Journal of Simulation: Systems, Science & Technology (IJSIM), 6(3-4):52–60.
Buchholz, P., Ciardo, G., Donatelli, S., and Kemper, P. (2000). Complexity of memoryefficient Kronecker operations with applications to the solution of Markov models. INFORMS Journal on Computing, 12(3):203–222.
Buchholz, P. and Dayar, T. (2004). Block SOR for Kronecker structured representations. Linear Algebra and its Applications, 386:83–109.
Chanin, R., Corrêa, M., Fernandes, P., Sales, A., Scheer, R., and Zorzo, A. F. (2006). Analytical Modeling for Operating System Schedulers on NUMA Systems. Electronic Notes in Theoretical Computer Science (ENTCS), 151(3):131–149.
Czekster, R. M. (2010). Solução numérica de descritores Markovianos a partir de reestruturações de termos tensoriais. PhD thesis, Pontifícia Universidade Católica do Rio Grande do Sul (PUCRS), Brasil.
Czekster, R. M., Fernandes, P., Sales, A., and Webber, T. (2010a). Analytical Modeling of Software Development Teams in Globally Distributed Projects. In Proc. of the 5th IEEE Int. Conference on Global Software Engineering (ICGSE’10), pages 287–296.
Czekster, R. M., Fernandes, P., Sales, A., and Webber, T. (2010b). Restructuring tensor products to enhance the numerical solution of structured Markov chains. In Proceedings of the 6th International Conference on the Numerical Solution of Markov Chains (NSMC ’10), pages 36–39, Williamsburg, VA, USA.
Czekster, R. M., Fernandes, P., Sales, A., Webber, T., and Zorzo, A. (2011). Stochastic model for QoS assessment in multi-tier web services. In International Workshop on Practical Applications of Stochastic Modelling (PASM ’11), pages 93–109.
Czekster, R. M., Fernandes, P., Vincent, J. M., and Webber, T. (2007). Split: a flexible and efficient algorithm to vector-descriptor product. In Proc. of the 2nd Int. Conf. on Performance Evaluation, Methodologies and Tools (ValueTools ’07), Nantes, France.
Czekster, R. M., Fernandes, P., and Webber, T. (2009). GTAexpress: a Software Package to Handle Kronecker Descriptors. In Proc. of the 6th IEEE Int. Conference on Quantitative Evaluation of Systems (QEST 2009), pages 281–282, Budapest, Hungary.
Dotti, F. L., Fernandes, P., and Nunes, C. M. (2011). Structured Markovian Models for Discrete Spatial Mobile Node Distribution. Journal of the Brazilian Computer Society (JBCS), 17(1):31–52.
Dotti, F. L., Fernandes, P., Sales, A., and Santos, O. M. (2005). Modular Analytical Performance Models for Ad Hoc Wireless Networks. In Proc. of the 3rd IEEE Int. Symp. on Modeling and Optim. in Mobile, Ad Hoc, and Wireless Nets, pages 164–173.
Fernandes, P., Plateau, B., and Stewart, W. J. (1998). Efficient descriptor-vector multiplication in Stochastic Automata Networks. Journal of the ACM, 45(3):381–414.
Fernandes, P., Sales, A., Santos, A. R., and Webber, T. (2011). Performance Evaluation of Software Development Teams: A Practical Case Study. In International Workshop on Practical Applications of Stochastic Modelling (PASM ’11), pages 5–21.
Fernandes, P., Vincent, J. M., and Webber, T. (2008). Perfect Simulation of Stochastic Automata Networks, volume 5055 of LNCS, pages 249–263. Springer-Verlag.
Miner, A. S. (2002). Efficient state space generation of GSPNs using decision diagrams. In International Conference on Dependable Systems and Networks (DSN 2002), pages 637–646, Washington, DC, USA.
Miner, A. S. and Ciardo, G. (1999a). A data structure for the efficient Kronecker solution of GSPNs. In Proceedings of the 8th International Workshop on Petri Nets and Performance Models, pages 22–31, Zaragoza, Spain.
Miner, A. S. and Ciardo, G. (1999b). Efficient Reachability Set Generation and Storage Using Decision Diagrams. In Proc. of the 20th International Conference on Applications and Theory of Petri Nets, volume 1639 of LNCS, pages 6–25. Springer-Verlag.
Mokdad, L., Ben-Othman, J., and Gueroui, A. (2001). Quality of Service of a Rerouting Algorithm Using Stochastic Automata Networks. In Proceedings of the 6th IEEE Symposium on Computers and Communications, pages 338–343, Hammamet, Tunisia.
Plateau, B. (1985). On the stochastic structure of parallelism and synchronization models for distributed algorithms. In Proc. of the 1985 ACM SIGMETRICS Conf. on Measurements and Modeling of Computer Systems, pages 147–154, Austin, Texas, USA.
Saad, Y. (1995). Iterative Methods for Sparse Linear Systems. Boston: PWS Publishing Company.
Sales, A. (2009). Réseaux d’Automates Stochastiques: Génération de l’espace d’états atteignables et Multiplication vecteur-descripteur pour une sémantique en temps discret. PhD thesis, Institut National Polytechnique de Grenoble, France. [link].
Sales, A. and Plateau, B. (2009). Reachable State Space Generation for Structured Models which use Functional Transitions. In Proc. of the 6th IEEE Int. Conference on the Quantitative Evaluation of Systems (QEST 2009), pages 269–278, Budapest, Hungary.
Stewart, W. J. (1994). Introduction to the numerical solution of Markov chains. Princeton University Press.
Webber, T. (2009). Reducing the Impact of State Space Explosion in Stochastic Automata Networks. PhD thesis, Pontifícia Universidade Católica do Rio Grande do Sul (PUCRS), Brasil.
Publicado
19/07/2011
Como Citar
CZEKSTER, Ricardo M.; FERNANDES, Paulo; SALES, Afonso; WEBBER, Thais.
Solução eficiente de modelos estruturados a partir de descritores tensoriais combinados a estruturas arborescentes. In: WORKSHOP EM DESEMPENHO DE SISTEMAS COMPUTACIONAIS E DE COMUNICAÇÃO (WPERFORMANCE), 10. , 2011, Natal/RN.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2011
.
p. 2100-2113.
ISSN 2595-6167.
