Performance evaluation of OpenMP-based algorithms for handling Kronecker descriptors

详细信息    查看全文

• 作者：Antonio M. Lima <sup>antonio.lima@acad.pucrs.brsup>  ; [Author Vitae] ; Marco A.S. Netto<sup> ; sup><sup>marco.netto@gmail.comsup>  ; [Author Vitae] ; Thais Webber <sup>thais.webber@pucrs.brsup>  ; [Author Vitae] ; Ricardo M. Czekster <sup>ricardo.czekster@pucrs.brsup>  ; [Author Vitae] ; Cesar A.F. De Rose <sup>cesar.derose@pucrs.brsup>  ; [Author Vitae] ; Paulo Fernandes <sup>paulo.fernandes@pucrs.brsup>  ; [Author Vitae]
• 关键词：Parallel algorithms ; OpenMP ; NUMA machines ; Markovian models ; Kronecker descriptors ; Performance evaluation ; Scientific computing
• 刊名：Journal of Parallel and Distributed Computing
• 出版年：2012
• 出版时间：May, 2012
• 年：2012
• 卷：72
• 期：5
• 页码：678-692
• 全文大小：1148 K

文摘

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.