Comparando Paralelismo Entre Pthreads E CUDA

1. Introdução

As GPUs (unidades de processamento gráfico) segundo (Cook, 2012) estão presentes nos computadores atuais, provendo funcionalidades de renderização e exibição de imagens de alto desempenho. O surgimento dos shaders programáveis impulsionou a evolução das GPUs para GPGPUs (GPU de propósito geral) e consequentemente o surgimento da plataforma de programação paralela CUDA ( Nickolls, 2008).

Muitos trabalhos têm sido desenvolvidos sobre arquiteturas GPU com o objetivo de aumentar o desempenho na execução de aplicações científicas em diferentes áreas. Drozd (Drozd, 2012) implementou em CUDA o algoritmo de Burrow-Wheller, otimizado para o alinhamento de sequências de genes locais, atingindo um speedup de até 10x. A paralelização de um algoritmo que opera sobre matrizes de distâncias, de grande escala, de complexidade O (n2), proporcionou speedups de 20 a 30 vezes em relação ao método original (Arefin, 2012). Os resultados demonstraram uma redução surpreendente no número de iterações necessárias para a busca de resultado ideal. A natureza estocástica da aplicação favoreceu a obtenção de speedup na ordem de até 34x. O trabalho realizado por Myungho Lee (Lee, 2010) paralelizou e otimizou sobre GPU uma aplicação financeira baseada no algoritmo Monte Carlo, provendo speedups de até 190x sobre mono-processamento. O potencial das GPU aplicado a dinâmica dos fluidos de gases também foi explorado por Pei-Hung Lin(Lin, 2011). Outros trabalhos baseados em GPU foram aplicados ao enxame de partículas ( Farhadi, 2011) e propagação de ondas ( Zhou, 2012).

2. Plataforma GPU/CUDA

GPUs (Cook, 2012) são processadores de muitos núcleos, contendo dezenas, centenas ou milhares de núcleos de processamento, organizados fisicamente em grupos chamados de Streaming Multiprocessors (SM) ( Chatterjee,2011). Cada SM tem sua memória local e acesso a uma memória global. Uma GPU (Cook, 2012) consiste em um ou mais SMs, e quanto mais SMs uma GPU tenha, maior é o grau de paralelismo físico.

SMs ( Chatterjee,2011) são os responsáveis por escalonar e executar grupos de 32 threads, chamados de warps. O conhecimento da existência de warps por parte do programador pode auxiliar no desempenho da aplicação, pois o programador poderá organizar os dados da aplicação de forma a manter uma maior localidade para as warps. De uma forma geral, a otimização de dados na memória da GPU é fundamental para prover maior desempenho, uma vez que tal memória é bem limitada, quando comparada as memórias utilizadas nos computadores hospedeiros, e acessada exaustivamente.

CUDA (Whitepaper NVIDIA GF100, 2010) é uma arquitetura de software que oferece extensão para varias linguagens de programação convencionais. O programador escreve uma aplicação na linguagem convencional e faz chamadas a kernels CUDA, que podem codificar simples funções ou até programas inteiros. A aplicação executa no hospedeiro, mas os kernels executam na placa GPU por meio de um conjunto de threads paralelas.

3. Multiplicação matricial

Segundo (Boldrini, 1986) uma multiplicação matricial é definida da seguinte maneira: Sejam A uma matriz de dimensões MxN, onde cada elemento de a é representado por aij, e B uma matriz de dimensões NxP, onde cada elemento de B é representado por brs, o produto C de A e B, sendo C uma matriz de dimensões MxP onde cada elemento de C é representado por cuv , é dado pela equação (1).

Mais claramente falando, de acordo com (Boldrini, 1986) o elemento na posição cij é obtido pela soma dos produtos dos elementos da i-ésima linha da primeira matriz pelos elementos da j-ésima coluna da segunda matriz.

4. Implementação da multiplicação matricial

4.1. Em CUDA

A implementação da multiplicação matricial foi feita tratando a matriz como um vetor, sendo assim foi necessária uma abstração para o acesso de linhas e colunas das matrizes. Assim uma matriz de M linhas e N colunas era representada por um vetor onde as posições de 0 à M-1 representavam a primeira linha da matriz, M à 2M-1 a segunda linha e assim ate NM-1 a ultima linha.

Foi implementado um kernel para efetuar a multiplicação de uma linha por uma coluna, e então esse kernel é chamado para cada thread e ambas threads lêem e escrevem em um espaço de memória que é compartilhado.

4.2 Em Pthread

A implementação da multiplicação matricial em pthread foi feita de maneira diferente, foram criadas matrizes globais de mesmos tamanhos, e quadradas, um procedimento para efetuar a multiplicação de um numero de linhas da primeira matriz por todas colunas da segunda matriz, esse numero de linhas é calculado de acordo com a quantidade de threads que serão usadas para o calculo.

Houve também a necessidade da criação de uma estrutura de dados para “transportar” os parâmetros que seriam utilizados em cada thread, e também foi utilizado um array de semáforos para controlar quais threads já terminaram seu processamento.

5.Experimentos

Os experimentos foram executados em um computador com dois processadores Intel(R) Xeon(R) CPU E5-2630 com 32 GB de memória RAM, uma placa GPU GeForce GTX 680 e o sistema operacional Linux Ubuntu 11.10. A referida GPU possui 1536 núcleos de processamento, organizados em 4 GPCs (cluster de processamento gráfico), que por sua vez são constituídos de 2 SMXs (SMs de última geração) cada.

Os experimentos realizados foram feitos com matrizes quadradas com tamanho com tamanho variando de 1000x1000 à 10000x10000. Esse intervalo foi tanto em CUDA como em pthreads. Para a execução em pthreads foram criadas 24 threads, pois cada um dos processadores possui 6 núcleos com hyperthread. Já em CUDA foi utilizado o numero maximo de threads, que ultrapassa 67 milhões de threads(1024 threads por bloco com 65536 blocos), porem essas threads não são executadas todas em paralelo por falta de núcleos. Foram executados 5 repetições dos mesmos testes, e o resultado observado foi a media aritmética das 5 execuções.Os resultados são os apresenados na figura 1.

Foram também executados