Evaluating Parallelism Strategies and Scheduling for Irregular Problems: A Case Study with OpenMP

• Paulo Zimpel UFMS
• Vinicius Dias UFLA
• Samuel Ferraz UFMS

Resumo

As multi-core architectures have become widespread, various techniques have been developed to better exploit the performance of modern computer systems. While the generation of parallel strategies has been extensively explored, proportionally small effort has been made to really understand the internal structure of executions. In this context, this paper presents an evaluation of execution and memory demands of irregular problems, using the subgraph enumeration algorithm and the OpenMP programming model. The goal is to offer conceptual guidelines for those aiming to develop parallel algorithms on parallel architectures. We implement and evaluate different parallelization and scheduling strategies on an irregular, computationally intensive problem, using synthetically generated graphs to test performance under varying structural characteristics. The results provide practical insights into selecting appropriate parallelization and scheduling strategies for irregular problems, demonstrating how architectural features and workload characteristics must be carefully considered for optimal performance.

Palavras-chave: Processor scheduling, High performance computing, Conferences, Computational modeling, Programming, Computer performance, Parallel architectures, Parallel algorithms, Guidelines, Context modeling, multi-core, irregularity, parallelization, scheduling, OpenMP