Sincronização Orientada por Dependências para Stencils: Modelagem Causal e Avaliação de Barreiras, Semáforos e MPI

• Frederico L. Cabral LNCC / CEFET/RJ
• Carla Osthoff LNCC
• Diego Brandão CEFET/RJ
• Sanderson L. Gonzaga de Oliveira UNIFESP

DOI: https://doi.org/10.5753/sscad.2026.34909

Resumo

Barreiras de fase são simples e seguras, mas impõem uma ordem coletiva mais forte que a exigida pelo grafo de dependências de um stencil. Neste artigo, é formalizada a sincronização orientada por dependências para stencils de raio um, tendo como estudo de caso uma decomposição em faixas do Odd-Even Hopscotch para a equação do calor 2D. Um modelo causal distingue ordem de programa, sincronização entre vizinhos e ordenação causada por barreiras, mostrando que um stencil de raio um requer precedência apenas entre interfaces adjacentes. Com base nisso, propõe-se um protocolo OpenMP sem barreiras globais, usando semáforos POSIX direcionais, e compara-se sua localidade ao MPI ponto a ponto com troca de halos. Um modelo de primeira ordem do makespan, isto é, do tempo total necessário para concluir a execução, prevê vantagem dos semáforos quando o custo da espera coletiva imposto pela barreira supera o custo adicional do bloqueio local e do desequilíbrio entre vizinhos. A avaliação, com malha de tamanho equivalente a memória local de um ambiente computacional de última geração contendo 192 núcleos, mantém fixo o arranjo de memória das variantes OpenMP. Entre 32 e 192 threads, os semáforos superam as barreiras em todas as configurações; em 192 threads, reduzem o tempo mediano de forma significativa para TILE equivalente ao tamanho da memória cache, onde o MPI puro ainda é o mais rápido nos mesmos testes. Os resultados do estudo de caso sustentam o modelo causal e evidenciam que a sincronização local reduz a espera coletiva, aproximando-se do desempenho do MPI sem reproduzir seu modelo explícito de comunicação.

Referências

Cabral, F. L., Oliveira, S. L. G. d., Osthoff, C., Costa, G. P., Brandão, D. N., and Kischinhevsky, M. (2020). An evaluation of mpi and openmp paradigms in finite-difference explicit methods for pdes on shared-memory multi- and manycore systems. Concurrency and Computation: Practice and Experience, 32(20):e5642.

Datta, K., Murphy, M., Volkov, V., Williams, S., Carter, J., Oliker, L., Patterson, D. A., Shalf, J., and Yelick, K. A. (2008). Stencil computation optimization and auto-tuning on state-of-the-art multicore architectures. In Proceedings of the 2008 ACM/IEEE Conference on Supercomputing, pages 1–12.

Drepper, U. (2007). What every programmer should know about memory. Technical report, Red Hat.

Gourlay, A. R. (1970). Hopscotch: A fast second-order partial differential equation solver. IMA Journal of Applied Mathematics, 6(4):375–390.

Gropp, W., Lusk, E., and Skjellum, A. (2014). Using MPI: Portable Parallel Programming with the Message-Passing Interface. MIT Press, Cambridge, MA, 3 edition.

Hager, G. and Wellein, G. (2010). Introduction to High Performance Computing for Scientists and Engineers. CRC Press, Boca Raton, FL.

Hensgen, D., Finkel, R., and Manber, U. (1988). Two algorithms for barrier synchronization. International Journal of Parallel Programming, 17(1):1–17.

Hockney, R. W. (1994). The communication challenge for mpp: Intel paragon and meiko cs-2. Parallel Computing, 20(3):389–398.

IEEE and The Open Group (2018). IEEE Standard for Information Technology—Portable Operating System Interface (POSIX) Base Specifications, Issue 7. IEEE and The Open Group.

Lamport, L. (1978). Time, clocks, and the ordering of events in a distributed system. Communications of the ACM, 21(7):558–565.

Mellor-Crummey, J. M. and Scott, M. L. (1991). Algorithms for scalable synchronization on shared-memory multiprocessors. ACM Transactions on Computer Systems, 9(1):21–65.

MPI Forum (2023). MPI: A message-passing interface standard, version 4.1. Technical report, MPI Forum.

OpenMP Architecture Review Board (2021). OpenMP Application Programming Interface, Version 5.2. OpenMP Architecture Review Board.

Rabenseifner, R., Hager, G., and Jost, G. (2009). Hybrid mpi/openmp parallel programming on clusters of multi-core smp nodes. Proceedings of the 17th Euromicro International Conference on Parallel, Distributed and Network-based Processing, pages 427–436.

ten Thije Boonkkamp, J. H. M. and Verwer, J. G. (1987). On the odd-even hopscotch scheme for the numerical integration of time-dependent partial differential equations. Applied Numerical Mathematics, 3(1):183–193.