# Autotuning PETSc em GPU

Um dos componentes básicos da computação numérica é a habilidade de resolver sistemas de equações no formato $Ax=b$. Sistemas como esse aparecem com frequência na computação científica, como no caso das aproximações de equações diferenciais parciais pelos métodos de diferenças finitas ou elementos finitos, ou nos passos intermediários das soluções de problemas não-lineares [1]. Esses métodos encontram aplicações práticas em diversas áreas da ciência e engenharia, sobretudo na simulação e análise de materiais.[^1]

Devido às suas especificidades e ao grande volume de operações envolvidas, é usual que tais problemas demandem o desenvolvimento de aplicações personalizadas em ambientes de alto desempenho. Por essa razão, existem bibliotecas de código que oferecem abstrações de alto nível para construir aplicações adaptadas à necessidade e que não estejam amarradas a uma arquitetura específica. Uma dessas bibliotecas é a *PETSc*, amplamente utilizada em *frameworks* voltados para computação científica de alto desempenho.

> Para encaixar melhor no contexto do projeto da HPE, fica legal falar um pouco sobre métodos de autotuning. A justificativa para o autotuning é justamente o aumento da complexidade dos modelos de programação, gerando a necessidade de se escrever código diferente para um mesmo programa, buscando atingir desempenho em diferentes arquiteturas. A existência de bibliotecas de alto nível que não dão acesso a oportunidades de otimização, ou fazem escolhas de otimização mais genéricas, também é uma motivação.
>
> [time=Mon, Apr 13, 2020 1:56 PM][name=Pedro]

A **PETSc** (*Portable, Extensible Toolkit for Scientific Computation*) é uma biblioteca de código aberto, desenvolvida pelo [Argonne National Laboratory (ANL)](https://www.mcs.anl.gov/petsc/index.html), que oferece soluções numéricas escaláveis para os sistemas de equações oriundos da discretização de equações diferenciais parciais. A PETSc é uma coleção de estruturas de dados e rotinas que compõem os ingredientes básicos para a implementação de *solvers* paralelos para problemas envolvendo EDPs em computadores de alta performance. O código pode ser incorporado em aplicações escritas em Fortran, C, C++ e Python [2].

## PETSc

A PETSc utiliza o padrão **MPI** (*Message Passing Interface*) para a cooperação entre os processos executados paralelamente. Embora originalmente desenvolvida para execução em máquinas multiprocessadas com memória compartilhada ou distribuída, a PETSc também oferece suporte para execução em GPU [5].

Um programa incorpora a PETSc ao utilizar as classes de vetores e matrizes oferecidas pela biblioteca. Existem diferentes estruturas de classes, apropriadas a cada tipo de problema e arquitetura. Uma matriz diagonal esparsa, por exemplo, deverá ter uma estrutura específica, diferente daquela utilizada por uma matriz densa. É na definição dessas classes onde são consideradas as características de cada arquitetura de processamento paralelo, de modo que um programa pode ser reimplementado para uma outra arquitetura sem que seja necessário reescrever as porções de código responsável por invocar as funções que geram as soluções.

## Análise de desempenho

As diferentes estruturas de dados e dos algoritmos podem apresentar variações no tempo de execução do programa. Além das variações inerentes à formulação do problema, é esperado que migrar o processamento paralelo em CPU para GPU também interfira no tempo de execução do programa.

## Espaço de otimização

> Normalmente, usamos o termo "espaço de busca"
>
> [time=Mon, Apr 13, 2020 1:09 PM][name=Pedro]

### Autotuning Workflow

#### Etapa Inicial

Qual é:

1. O problema alvo?
2. A métrica a minimizar?
3. O espaço de busca?

#### Statistical Learning

- Qual a variabilidade de uma amostra aleatória de configurações?
- Como minimizar a métrica alvo?
- Quanto tempo demora cada medição?

Para minimizar a métrica, podemos usar métodos:

1. Paramétricos
- Número relativamente baixo de parâmetros
- Screening
2. Não-paramétricos

No caso específico da obtenção de soluções de sistema lineares, cabe considerar os seguintes os seguintes aspectos:

- Magnitude do sistema de equações.
- Estruturas dos dados e algoritmos.
- Opções de compilação.

Mudanças em cada um desses aspectos podem provocar impactos significativos no tempo de execução do programa, que não são facilmente previsíveis. Logo, a elaboração de um problema modelo que aceite parâmetros modificando esses aspectos permitirá avaliar em quais condições a paralelização em GPU é preferível em relação à paralelização em CPU.

### Tamanho do sistema de equações

O tamanho da matriz do problema é o fator de maior impacto na quantidade de operações necessárias e consequentemente no tempo de execução do problema. CPU e GPU acessam a memória e executam os *threads* de modo bastante distinto, o primeiro podendo apresentar vantagem em relação ao segundo para problemas relativamente pequenos ou vice-versa. Para sistemas de equações gerados a partir da discretização de EDPs, modificações na resolução da malha permitem alterar o tamanho da matriz.

> Se entendi direito, a solução para um mesmo problema pode ser implementada
> usando matrizes de tamanhos diferentes. É isso?
> Um possível parâmetro nesse espaço de busca seria a resolução da malha?
> Acho que ficaria legal um exemplo.
>
> [time=Mon, Apr 13, 2020 1:07 PM][name=Pedro]

### Estruturas dos dados e algoritmos

A PETSc oferece opções distintas para o armazenamento dos dados na memória e variações na maneira como os algoritmos utilizam esses dados. Como os mecanismos de acesso a memória em cada modelo de paralelização é diferente, é esperado que variações na maneira como os dados são inicialmente dispostos também afete a velocidade dos programas.

> - "[...] também afete o [*desempenho*, ou *tempo de execução*] dos programas".
> - Aqui também vale a pena expandir a explicação com um exemplo concreto.
>
> [time=Mon, Apr 13, 2020 1:10 PM][name=Pedro]

### Opções de compilação

Além das operações de acesso a memória, parte significativa do processamento de soluções numéricas de EDPs envolve operações matemáticas. A linguagem CUDA oferece opções de compilação para otimizar tais operações, em particular:

- `-prec-div=false` (menor precisão na divisão).
- `-prec-sqrt=false` (menor precisão na raiz quadrada).
- `-use_fast_math` (operações aritméticas mais rápidas).

### Outras considerações

Além da implementação do paralelismo em GPU com CUDA, a PETSc também oferece paralelização em GPU com tecnologia OpenCL de modo transparente, por isso cabe ser considerada nos testes. Uma abordagem híbrida CPU/GPU também merece atenção, pois a PETSc permite essa flexibilidade e é uma configuração comum em ambientes HPC. Por último, uma aplicação independente da PETSc baseada puramente na biblioteca cuSolver da CUDA pode oferecer uma alternativa mais eficiente para em certos casos.

> - Um parâmetro do espaço de busca pode também ser o "fator de heterogeneidade" de um dado programa:
> - Quais porções de um programa serão executadas em cada dispositivo?
> - Como poderíamos controlar isso?
>
> [time=Mon, Apr 13, 2020 1:13 PM][name=Pedro]
>

> Está faltando falar um pouco dos métodos estatísticos que vamos usar para fazer o autotuning da PETSc. Acho que essa parte é minha :)
>
> [time=Mon, Apr 13, 2020 1:55 PM][name=Pedro]

### Trabalhos relacionados

Os trabalhos [3] e [4] apresentaram análises semelhantes, mas não contemplam as inovações recentes em GPUs NVIDIA e nas bibliotecas numéricas relacionadas.

> Esse trabalho da Boyana [4] usa o Orio, uma bibilioteca de transformação fonte-fonte com a qual já trabalhei. Com ela é possível parametrizar um algoritmo existente e gerar novas versões do código em C. A PETSc faz algo assim? Pergunto por que tenho experiência com source-to-source transformation, mas acho que usar o Orio pode não ser uma boa, o código é meio velho e sem manutenção. Vou procurar algo mais recente nesse sentido, e assim podemos ter uma boa chance de parametrizar os algoritmos.
>
> [time=Mon, Apr 13, 2020 1:52 PM][name=Pedro]

[^1]: Para sistemas lineares extensos e esparsos, comuns na discretização de EDPs, os métodos computacionais mais eficientes envolvem algoritmos paralelos de gradiente conjugado e o subespaço de Krylov. Essa é a abordagem escolhida por diferentes softwares voltados para esse tipo de problema em HPC.

## Bibliografia preliminar

[1] Balay, Satish, Shrirang Abhyankar, Mark F. Adams, Jed Brown, Peter Brune, Kris Buschelman, Lisandro Dalcin, et al. 2020. “PETSc Users Manual.” ANL-95/11 - Revision 3.13. Argonne National Laboratory. https://www.mcs.anl.gov/petsc.

[2] Freund, Roland W, Gene H Golub, and Noël M Nachtigal. 1992. “Iterative Solution of Linear Systems.” Acta Numerica 1. Cambridge University Press: 57–100.

[3] Kumbhar, Pramod. 2011. “Performance of Petsc Gpu Implementation with Sparse Matrix Storage Schemes.” PhD thesis, Master’s thesis, The University of Edinburgh (Aug 2011).

[4] Mametjanov, Azamat, Daniel Lowell, Ching-Chen Ma, and Boyana Norris. 2012. “Autotuning Stencil-Based Computations on Gpus.” In 2012 Ieee International Conference on Cluster Computing, 266–74. IEEE.

[5] Minden, Victor, Barry Smith, and Matthew G Knepley. 2013. “Preliminary Implementation of Petsc Using Gpus.” In GPU Solutions to Multi-Scale Problems in Science and Engineering, 131–40. Springer.