21 julho, 2013 3 Comentários AUTOR: elemarjr CATEGORIAS: Sem categoria Tags:,

Introdução a Tiling com C++ AMP - Parte 1 - motivações

Tempo de leitura: 2 minutos

Olá. Tudo certo?

Estou iniciando essa série para apresentar um conceito fundamental para programação com C++ AMP: tiling.

Se você não conhece C++ AMP, recomendo a leitura da série introdutória que disponibilizei aqui no blog.

Por que usar tiling?

C++ AMP trata de processamento paralelo massivo, usando accelerators (leia-se GPU, no caso mais comum).

Consideremos a multiplicação de matrizes, proposta em um post do Daniel Moth - um dos integrantes do time que desenvolve a tecnologia.

void MatrixMultiplySimple(std::vector& vC,
const std::vector& vA,
const std::vector& vB, int M, int N, int W)
{
concurrency::array_view a(M, W, vA);
concurrency::array_view b(W, N, vB);
concurrency::array_view c(M, N, vC); c.discard_data();

concurrency::parallel_for_each(c.extent,
[=](concurrency::index<2> idx) restrict(amp) {
int row = idx[0]; int col = idx[1];
float sum = 0.0f;
for(int i = 0; i < W; i++) sum += a(row, i) * b(i, col); c[idx] = sum; }); } [/code] Neste exemplo,

  • os dados presentes na memória da CPU são copiados para a memória da GPU (e apenas a matriz resultante é copiada de volta no final) ;
  • parallel_for_each faz com que cada execução da função core ocorra em uma thread independente;
  • cada thread armazena o valor para a célula da matriz resultante em uma variável local que é, posteriormente, armazenada em definitivo na matriz resultante;
  • para computar o valor resultante, são feitas diversas consultas a memória global da GPU.

Pois bem, variáveis locais criadas em uma função core geralmente são armazenadas em um registrador da GPU. Logo, são acessadas em (geralmente) apenas 1 ciclo de processamento. Já valores em array/array_view, que ficam na memória global, tem custo de acesso bem mais alto .

GPUs oferecem um mecanismo de caching que pode diminuir consideravelmente o impacto do custo do acesso a memória global. Entretanto, diferente do que ocorre em mecanismos de caching de CPU, o controle fica totalmente a cargo do programador.

Em C++ AMP, o caching é utilizado quando há possibilidade de compartilhar dados entre diversas threads (execuções da função core). Essencialmente, os dados que podem ser compartilhados são armazenados no cache e ficam disponíveis enquanto houverem threads que podem consumir esses dados. O conjunto de threads que compartilha dados armazenado em cache é reconhecido como Tile.

O que é tiling?

De forma simplificada, consiste na ideia de agrupar dados (e consequentemente threads) em pequenos blocos (de até 1024 elementos), de forma a reduzir a quantidade de acessos a memória global através da utilização de um mecanismo de caching compartilhado entre essas threads.

Abaixo, o exemplo da multiplicação de matrizes, também do Daniel Moth, considerando tiling:

void MatrixMultiplyTiled(vector& vC,
const vector& vA,
const vector& vB, int M, int N, int W)
{
static const int TS = 16;

array_view a(M, W, vA);
array_view b(W, N, vB);
array_view c(M,N,vC); c.discard_data();

parallel_for_each(c.extent.tile< TS, TS >(),
[=] (tiled_index< TS, TS> t_idx) restrict(amp)
{
int row = t_idx.local[0]; int col = t_idx.local[1];
float sum = 0.0f;

for (int i = 0; i < W; i += TS) { tile_static float locA[TS][TS], locB[TS][TS]; locA[row][col] = a(t_idx.global[0], col + i); locB[row][col] = b(row + i, t_idx.global[1]); t_idx.barrier.wait(); for (int k = 0; k < TS; k++) sum += locA[row][k] * locB[k][col]; t_idx.barrier.wait(); } c[t_idx.global] = sum; }); } [/code] Por agora, esse código pode ter ficado um pouco obscuro - afinal, há uma modificação na lógica implementada. Mas, considerando os objetivos desse post, cabem as seguintes observações:

  • fragmentação da extent em pequenos blocos com 16x16. São os tiles!
  • utilização do modificador tile_staticé o nosso cache!
  • utilização do tile_index
  • utilização do barrier.wait() - é o nosso mecanismo de coordenação de execução entre as threads.

Nos próximos posts, explico cada um desses aspectos.

Concluindo...

Tiling é uma estratégia para utilização de caching disponível no C++ AMP. A adoção dessa estratégia pode proporcionar ganhos impressionantes de performance através da redução de acessos a memória global da GPU.

A forma como Tiling é adotada é extremamente dependente do algoritmo que estamos implementando.

Era isso.