Modelagem comonádica de stencils com execução paralela

• Lucas Ieks Minicz USP
• Daniel Cordeiro USP
• Emilio Francesquini UFABC

DOI: https://doi.org/10.5753/wscad_estendido.2021.18639

Resumo

Stencils resolvem um tipo de problema muito comum em computação paralela. Comônadas, por sua vez, são uma forma conveniente de escrever código paralelizável, mas implementações de stencils usando comônadas são incomuns fora de exemplos. Neste trabalho descrevemos um protótipo que implementa stencils usando comônadas para investigar os limites dessa estrutura quando se tenta usar bibliotecas existentes para paralelismo, e investigamos formas de solucioná-los. Também observamos que o compilador consegue otimizar nosso código bem, mas precisa de algumas anotações adicionais para isso. Concluímos que o uso de comônadas é muito apropriado para implementar stencils.

Referências

Chalmers, C. (2020). dense: Mutable and immutable dense multidimensional arrays. Disponível em: https://hackage.haskell.org/package/dense. Acesso em: 06 de ago. de 2021.

Jones, S. P. (2003). Haskell 98 Language and Libraries: The Revised Report. Cambridge University Press, 2003 edition.

Kmett, E. A. (2021). comonad: Comonads. Disponível em: https://hackage.haskell.org/package/comonad. Acesso em: 06 de ago. de 2021.

Kuleshevich, A. (2021). massiv: Massiv is an Array Library. Disponível em: https://hackage.haskell.org/package/massiv. Acesso em: 06 de ago. de 2021.

Lesniak, M. (2010). Pastha: Parallelizing stencil calculations in haskell. In Proceedings of the 5th ACM SIGPLAN Workshop on Declarative Aspects of Multicore Programming, DAMP ’10, page 5–14, New York, NY, USA. ACM.

Lippmeier, B., Chakravarty, M., Keller, G., and Peyton Jones, S. (2012). Guiding parallel array fusion with index types. In Haskell Symposium, Copenhagen. ACM.

Lippmeier, B. and Keller, G. (2011). Efficient parallel stencil convolution in haskell. In Sigplan Notices SIGPLAN, volume 46, pages 59–70.

Orchard, D. and Mycroft, A. (2011). Efficient and correct stencil computation via pattern matching and static typing. Electronic Proceedings in Theoretical Computer Science, 66:25.

O’Sullivan, B. (2014). criterion: a Haskell microbenchmarking library. Disponível em: http://www.serpentine.com/criterion/. Acesso em: 06 de ago. de 2021.

Roth, G., Mellor-crummey, J., Kennedy, K., and Brickner, R. G. (1997). Compiling stencils in high performance fortran. In Supercomputing ’97: Proceedings of the 1997 ACM/IEEE conference on Supercomputing, pages 1–20. ACM Press.

Schaefer, A. and Fey, D. (2011). High performance stencil code algorithms for GPGPUs. Procedia Computer Science, 4:2027–2036.

Uustalu, T. and Vene, V. (2008). Comonadic notions of computation. Electronic Notes in Theoretical Computer Science, 203(5):263–284.