Split: a flexible and efficient algorithm to vector-descriptor product

ABSTRACT

Many Markovian stochastic structured modeling formalisms like Petri nets, automata networks and process algebra represent the infinitesimal generator of the underlying Markov chain as a descriptor instead of a traditional sparse matrix. A descriptor is a compact and structured storage based on a sum of tensor (Kronecker) products of small matrices that can be handled by many algorithms allowing affordable stationary and transient solutions even for very large Markovian models. One of the most efficient algorithms used to compute iterative solutions of descriptors is the Shuffle algorithm which is used to perform the multiplication by a probability vector. In this paper we propose an alternative algorithm called Split, since it offers a flexible solution between the pure sparse matrix approach and the Shuffle algorithm using a hybrid solution. The Split algorithm puts the Shuffle approach in perspective by presenting a faster execution time for many cases and at least the same efficiency for the worst cases. The Split algorithm is applied to solve two SAN models based on real problems showing the practical contribution of this paper.

REFERENCES

• 1: Marco Ajmone Marsan , Gianni Conte , Gianfranco Balbo, A class of generalized stochastic Petri nets for the performance evaluation of multiprocessor systems, ACM Transactions on Computer Systems (TOCS), v.2 n.2, p.93-122, May 1984 [doi>10.1145/190.191]
• 2: V. Amoia, G. D. Micheli, and M. Santomauro. Computer-Oriented Formulation of Transition-Rate Matrices via Kronecker Algebra. IEEE Transactions on Reliability, R-30(2):123--132, 1981.
• 3: L. Baldo, L. Brenner, L. G. Fernandes, P. Fernandes, and A. Sales. Performance Models for Master/Slave Parallel Programs. Electronic Notes In Theoretical Computer Science, 128(4):101--121, April 2005.
• 4: L. Baldo, L. G. Fernandes, P. Roisenberg, P. Velho, and T. Webber. Parallel PEPS Tool Performance Analysis using Stochastic Automata Networks. In Euro-Par 2004 International Conference on Parallel Processing, volume 3149 of LNCS, pages 214--219, Pisa, Italy, 2004.
• 5: L. Brenner, P. Fernandes, and A. Sales. The Need for and the Advantages of Generalized Tensor Algebra for Kronecker Structured Representations. International Journal of Simulation: Systems, Science & Technology, 6(3-4):52--60, February 2005.
• 6: Peter Buchholz, A distributed numerical/simulative algorithm for the analysis of large continuous time Markov chains, Proceedings of the eleventh workshop on Parallel and distributed simulation, p.4-11, June 10-13, 1997, Lockenhaus, Austria
• 7: Peter Buchholz, A new approach combining simulation and randomization for the analysis of large continuous time Markov chains, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.8 n.2, p.194-222, April 1998 [doi>10.1145/280265.280274]
• 8: Peter Buchholz , Gianfranco Ciardo , Susanna Donatelli , Peter Kemper, Complexity of Memory-Efficient Kronecker Operations with Applications to the Solution of Markov Models, INFORMS Journal on Computing, v.12 n.3, p.203-222, July 2000 [doi>10.1287/ijoc.12.3.203.12634]
• 9: Peter Buchholz , Gianfranco Ciardo , Susanna Donatelli , Peter Kemper, Complexity of Memory-Efficient Kronecker Operations with Applications to the Solution of Markov Models, INFORMS Journal on Computing, v.12 n.3, p.203-222, July 2000 [doi>10.1287/ijoc.12.3.203.12634]
• 10: Peter Buchholz , Peter Kemper, Hierarchical Reachability Graph Generation for Petri Nets, Formal Methods in System Design, v.21 n.3, p.281-315, November 2002 [doi>10.1023/A:1020321222420]
• 11: M. Davio. Kronecker Products and Shuffle Algebra. IEEE Transactions on Computers, C-30(2):116--125, 1981.
• 12: Susanna Donatelli, Superposed Generalized Stochastic Petri Nets: Definition and Efficient Solution, Proceedings of the 15th International Conference on Application and Theory of Petri Nets, p.258-277, June 20-24, 1994
• 13: Fernando L. Dotti , Paulo Fernandes , Afonso Sales , Osmar M. dos Santos, Modular Analytical Performance Models for Ad Hoc Wireless Networks, Proceedings of the Third International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks, p.164-173, April 04-06, 2005 [doi>10.1109/WIOPT.2005.31]
• 14: Fernando Luís Dotti , Leila Ribeiro, Specification of mobile code system using graph grammars, Fourth International Conference on Formal methods for open object-based distributed systems IV, p.45-64, September 2000, Stanford, California, United States
• 15: P. Fernandes. Methodes numeriques pour la solution de systhemes Markoviens a grand espace d'etats. PhD thesis, Institut National Polytechnique de Grenoble, France, 1998.
• 16: Paulo Fernandes , Brigitte Plateau , William J. Stewart, Efficient descriptor-vector multiplications in stochastic automata networks, Journal of the ACM (JACM), v.45 n.3, p.381-414, May 1998 [doi>10.1145/278298.278303]
• 17: P. Fernandes, R. Presotto, A. Sales, and T. Webber. An Alternative Algorithm to Multiply a Vector by a Kronecker Represented Descriptor. In 21^st UK Performance Engineering Workshop, pages 57--67, Newcastle, UK, June 2005.
• 18: P. Fernandes, R. Presotto, A. Sales, and T. Webber. An Alternative Algorithm to Multiply a Vector by a Kronecker Represented Descriptor. Technical Report TR 047, PUCRS, Porto Alegre, 2005. http://www.inf.pucrs.br/tr/tr047.pdf.
• 19: Jane Hillston , Leïla Kloul, An Efficient Kronecker Representation for PEPA Models, Proceedings of the Joint International Workshop on Process Algebra and Probabilistic Methods, Performance Modeling and Verification, p.120-135, September 12-14, 2001
• 20: Jinyang Li , Charles Blake , Douglas S.J. De Couto , Hu Imm Lee , Robert Morris, Capacity of Ad Hoc wireless networks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.61-69, July 2001, Rome, Italy [doi>10.1145/381677.381684]
• 21: Andrew S. Miner, Efficient Solution of GSPNs Using Canonical Matrix Diagrams, Proceedings of the 9th international Workshop on Petri Nets and Performance Models (PNPM'01), p.101, September 11-14, 2001
• 22: Gianfranco Ciardo , Andrew S. Miner, A Data Structure for the Efficient Kronecker Solution of GSPNs, Proceedings of the The 8th International Workshop on Petri Nets and Performance Models, p.22, September 08-10, 1999
• 23: Andrew S. Miner , Gianfranco Ciardo, Efficient Reachability Set Generation and Storage Using Decision Diagrams, Proceedings of the 20th International Conference on Application and Theory of Petri Nets, p.6-25, June 21-25, 1999
• 24: Brigitte Plateau , Karim Atif, Stochastic Automata Network of Modeling Parallel Systems, IEEE Transactions on Software Engineering, v.17 n.10, p.1093-1108, October 1991 [doi>10.1109/32.99196]
• 25: W. J. Stewart. MARCA: Markov chain analyzer. A software package for Markov modeling, pages 37--62. Numerical Solution of Markov Chains. New York, 1991.
• 26: W. J. Stewart. Introduction to the numerical solution of Markov chains. Princeton University Press, 1994.

INDEX TERMS

Keywords:
Kronecker products, numerical methods, performance evaluation, tensor algebra