Performance evaluation of OpenMP-based algorithms for handling Kronecker descriptors

Antonio M. Lima, Marco A.S. Netto*, Thais Webber, Ricardo M. Czekster, Cesar A.F. De Rose, Paulo Fernandes

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review


Numerical analysis of Markovian models is relevant for performance evaluation and probabilistic analysis of systems’ behavior from several fields in science and engineering. These models can be represented in a compact fashion using Kronecker algebra. The Vector-Descriptor Product (VDP) is the key operation to obtain stationary and transient solutions of models represented by Kronecker-based descriptors. VDP algorithms are usually CPU intensive, requiring alternatives such as data partitioning to produce results in less time. This paper introduces a set of parallel implementations of a hybrid algorithm for handling descriptors and a detailed performance analysis on four real Markovian models. The implementations are based on different scheduling strategies using OpenMP and existing techniques of static and dynamic load balancing, along with data partitioning presented in the literature. The performance evaluation study contains analysis of speed-up, synchronization and scheduling overheads, task mapping policies, and memory affinity. The results presented here provide insights into different implementation choices for an application on shared-memory systems and how this application benefited from this architecture.
Original languageEnglish
Pages (from-to)678-692
Number of pages15
JournalJournal of Parallel and Distributed Computing
Issue number5
Publication statusPublished - 1 May 2012


  • Kronecker descriptors
  • Markovian models
  • NUMA machines
  • OpenMP
  • Parallel algorithms
  • Performance evaluation
  • Scientific computing


Dive into the research topics of 'Performance evaluation of OpenMP-based algorithms for handling Kronecker descriptors'. Together they form a unique fingerprint.

Cite this