AVALIAÇÃO DE DESEMPENHO DE ALGORITMOS UTILIZANDO SISTEMAS HÍBRIDOS

Prévia do material em texto

Rafael Manochio 
 
 
 
 
 
 
 
Avaliação de desempenho de algoritmos utilizando sistemas 
híbridos 
 
 
 
 
 
 
 
Trabalho de conclusão de curso apresentado ao 
Instituto Federal de São Paulo, como parte dos 
requisitos para a obtenção do grau de Tecnólogo 
em Sistemas para Internet. 
 
Área de Concentração: Sistemas Híbridos. 
 
 
Orientador: Prof. Me. Paulo Muniz de Ávila 
 
 
 
 
 
 
São João da Boa Vista 
2013
 
Autorizo a reprodução e divulgação total ou parcial deste trabalho, por qualquer 
meio convencional ou eletrônico, para fins de estudo e pesquisa, desde que 
citada a fonte. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 Ficha catalográfica preparada pela Seção de Tratamento 
 da Informação do Serviço de Biblioteca – IFSP 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 Manochio, Rafael. 
 Avaliação de desempenho de algoritmos utilizando 
sistemas híbridos. / Rafael Manochio; orientador Paulo Muniz de 
Ávila. São João da Boa Vista, 2013. 
 
 
 Trabalho de Conclusão de Curso, IFSP, 2013. 
 
 
1. Heterogêneo. 2. Paralelismo. 3. GPGPU. 4. 
Processador. 5. Java 6. Sistemas Híbridos 
 
I. Avaliação de desempenho de algoritmos 
utilizando sistemas híbridos. 
 
 
 
 
AGRADECIMENTOS 
 
Ao colegas e professores do Instituto Federal de São Paulo, campus São 
João da Boa Vista, que me ajudaram em todos os momentos de minha 
formação. 
 
RESUMO 
 
MANOCHIO, R. (2013). Avaliação de desempenho de algoritmos utilizando sistemas 
híbridos. Trabalho de Conclusão de Curso - Instituto Federal de São Paulo, São João da Boa 
Vista, 2013. 
 Sistemas Híbridos ou heterogêneos, são sistemas computacionais formados por CPUs 
(Central Processing Unit – Unidade de Processamento Central), GPUs (Graphics Processing 
Unit – Unidade de Processamento Gráfico) ou qualquer outro tipo de processador com 
finalidade específica. 
 Este trabalho tem por objetivo demonstrar os ganhos de desempenho no porte de 
código sequencial, utilizado em processadores comuns, para um código paralelizado de forma 
a utilizar os benefícios da execução de código em uma arquitetura Híbrida formada por CPUs 
e GPUs, de forma que o processador central e os inúmeros núcleos de processamento 
presentes nas aceleradoras gráficas atuais trabalhem em conjunto para acelerar o 
processamento de aplicações. 
 Será demostrado, através de experimentos de medição de desempenho, que 
nem todo tipo de código terá ganho de desempenho ao ser executado paralelamente, podendo 
até haver uma grande perda de desempenho, como no caso da utilização de certas 
implementações de algoritmos de ordenação; grandes ganhos, entretanto, podem ser obtidos 
utilizando algoritmos de Álgebra Linear Densa, o que ficará evidenciado nos resultados. 
 
Palavras-chave: 1. Heterogêneo. 2. Paralelismo. 3. GPGPU. 4. Processador. 5. Java 
 
ABSTRACT 
 
MANOCHIO, R. (2013). Performance evaluation of algorithms using hybrid systems. 
Course Conclusion Project – Instituto Federal de São Paulo, São João da Boa Vista, 2013. 
 
 Hybrid systems or heterogeneous computing systems are composed of CPUs (Central 
Processing Unit), GPU (Graphics Processing Unit) or any other type of special-purpose 
processor. 
 This paper aims to demonstrate the performance gains in the port of sequential code, 
used in common processors for a code parallelized in order to utilize the benefits of code 
execution on a hybrid architecture consisting of CPUs and GPUs, so the CPU and the 
numerous cores present in the current graphical accelerators work together to process of 
applications. 
 It will be demonstrated through performance measurement experiments, that not every 
kind of code has a performance gain to be executed in parallel, and may even be a large loss 
in performance, such as the use of certain implementations of sorting algorithms; large gains, 
however, can be obtained using Dense Linear Algebra algorithms, which will be shown in the 
results. 
Keywords: 1. Heterogeneous. 2. Parallelism. 3. GPGPU. 4. Processor. 5. Java 
LISTA DE FIGURAS 
 
Figura 1. Crescimento de Supercomputadores do ranking Top500 que utilizam o 
conceito de GPGPU entre 2010 e 2012. ...................................................... 3 
Figura 2. Os Sistemas Multiprocessados do tipo SMP e NUMA. .................................. 11 
Figura 3. Os Sistemas Multiprocessados mistos atuais. ................................................. 12 
Figura 4. Código de exemplo para processamento paralelo. .......................................... 14 
Figura 5. Código otimizado para processamento paralelo. ............................................. 15 
Figura 6. Incremento de desempenho de acordo com a lei de Amdahl. ......................... 17 
Figura 7. Paralelismo de Dados vs Paralelismo de Tarefas. ........................................... 18 
Figura 8. Paralelismo de Dados, soma de vetores. ......................................................... 19 
Figura 9. Balanceamento de Carga. ................................................................................ 20 
Figura 10. Pipelining. ...................................................................................................... 21 
Figura 11. SP da arquitetura VLIW4. ............................................................................. 22 
Figura 12. Processamento de instruções de um Wavefront na arquitetura VLIW4. ....... 23 
Figura 13. Comparativo entre paralelismo de dados (DLP - a), paralelismo a nível de 
instrução (ILP - b) e paralelismo de tarefas (TLP - c) ............................... 24 
Figura 14. SIMD da arquitetura GCN............................................................................. 24 
Figura 15. Unidade Computacional GCN – CU ............................................................. 25 
Figura 16. Comparativo entre a execução de wavefronts pela arquitetura GCN e a 
arquitetura VLIW4 (Radeon HD 6xxx – Cayman) .................................... 26 
Figura 17. A GPU GCN .................................................................................................. 27 
Figura 18 – Algumas empresas associadas ao Kfronos Group ....................................... 30 
Figura 19. Ciclo de execução da Aparapi ....................................................................... 31 
Figura 20: Código fonte BubbleSort ............................................................................... 40 
Figura 21: Código BubbleSort portado para execução paralela em OpenCL ................. 41 
Figura 22. Utilização de CPU antes do teste. .................................................................. 43 
Figura 23. Resultados do algoritmo de Multiplicação de Matriz 16 posições – 
Hardware 1 ................................................................................................. 44 
Figura 24. Resultados do algoritmo de Multiplicação de Matriz 1024 posições – 
Hardware 1 ................................................................................................. 45 
Figura 25. Resultados do algoritmo de Multiplicação de Matriz 2048 posições – 
Hardware 1 ................................................................................................. 46 
Figura 26 Carga de trabalho antes do início dos testes no Hardware 2 ........................... 47 
Figura 27 Resultados do algoritmo de Multiplicação de Matriz 16 posições – 
Hardware 2 .................................................................................................. 47 
Figura 28 Resultados do algoritmo de Multiplicação de Matriz 1024 posições – 
Hardware 2 .................................................................................................. 48 
Figura 29 Resultados do algoritmo de Multiplicação de Matriz 2048 posições – 
Hardware 2 .................................................................................................. 49 
Figura 30. Utilizaçãode CPU antes do teste – Hardware 1. ........................................... 50 
Figura 31. Teste dos Algoritmos de Ordenação em um vetor de 16 posições. ............... 51 
Figura 32. Execução do algoritmo QuickSort no modo GPU. ........................................ 52 
Figura 33. Teste dos Algoritmos de Ordenação em um vetor de 1024 posições. ........... 53 
Figura 34. Teste dos Algoritmos de Ordenação em um vetor de 2048 posições. ........... 54 
Figura 35 Utilização de CPU antes do teste – Hardware 2. ............................................ 55 
Figura 36 Teste dos Algoritmos de Ordenação em um vetor de 16 posições – 
Hardware 2. ................................................................................................. 55 
Figura 37 Teste dos Algoritmos de Ordenação em um vetor de 1024 posições – 
Hardware 2. ................................................................................................. 56 
Figura 38 Teste dos Algoritmos de Ordenação em um vetor de 2048 posições – 
Hardware 2. ................................................................................................. 57 
Figura 39 Teste dos Algoritmo de Ordenação BubbleSort em um vetor de 8192 
posições ....................................................................................................... 58 
 
LISTA DE TABELAS 
 
Tabela 1 Taxonomia de Flynn para computadores paralelos ....................................... 9 
Tabela 2 Configuração de Hardware 1 (Desktop) ................................................... 42 
Tabela 3 Configuração de Hardware 2 (Notebook) ................................................. 42 
 
 
LISTA DE SIGLAS 
 
ACE Asynchronous Compute Engines 
ALU Arithmetic Logic Unit 
cc-NUMA Cash Coherent NUMA 
CPU Central Processing Unit 
GCN Graphics Core Next 
GCP Graphics Command Processor 
GPGPU General-purpose graphics processing unit 
GPGPU General Purpose Graphics Processing Unit (Unidade de 
Processamento Gráfico de Propósito Geral) 
HPC High Performance Computing 
ILP Instruction Level Parallelism 
IPC Instructions per cycle 
ISC International Supercomputing Conference 
JTP Java Thread Pool 
MIMD Multiple Instruction, Multiple Data stream 
MISD Multiple Instruction, Single Data stream 
MPI Message Passing Interface 
MPP Massively Parallel Processor 
NUMA Non-Uniform Memory Access 
NUMA Non-Uniform Memory Access (Acesso não Uniforme à Memória) 
OpenCL Open Computing Language 
PCIe PCI Express 
PP Primitive Pipelines 
PPE Power Processor Element 
ROPs Raster Operations Pipelines 
SFU Special Function Unit 
SIMD Single Instruction, Multiple Data Stream 
SISD Single Instruction, Single Data Stream 
SMP Symmetric Multiprocessing 
SMP Symmetric Multiprocessing (Multiprocessamento Simétrico) 
SPE Synergistic Processor Elements 
TLP Thread Level Parallelism 
USM Unified shader model 
VLIW Very Long Instruction Word 
 
 
SUMÁRIO 
 
1 INTRODUÇÃO .............................................................................................................. 1 
1.1 Motivação ............................................................................................................................... 4 
1.2 Objetivos ................................................................................................................................. 5 
1.3 Organização deste trabalho ..................................................................................................... 5 
2 PESQUISA BIBLIOGRÁFICA ......................................................................................... 7 
2.1 Paralelismo de Hardware ........................................................................................................ 7 
2.2 Taxonomia de Flynn ............................................................................................................... 7 
2.3 Sistemas de Memória distribuída e compartilhada ................................................................. 9 
2.3.1 Sistemas do tipo memória Distribuída ............................................................................... 10 
2.3.2 Sistemas do tipo memória Compartilhada.......................................................................... 10 
2.4 Aceleradores ......................................................................................................................... 12 
2.5 Paralelismo de Software ....................................................................................................... 13 
2.5.1 Processamento Paralelo e Sequencial................................................................................. 14 
2.5.2 Tipos de Paralelismo .......................................................................................................... 17 
2.6 Aceleradoras Gráficas e a arquitetura GCN .......................................................................... 21 
2.7 Frameworks .......................................................................................................................... 28 
2.7.1 OpenCl e Cuda ................................................................................................................... 29 
2.7.2 Aparapi ............................................................................................................................... 30 
2.8 Algoritmos de Ordenação ..................................................................................................... 31 
2.8.1 Métodos .............................................................................................................................. 31 
2.8.2 Análise Científica do Tempo de Execução de um Software .............................................. 32 
2.8.3 Classificação de Software .................................................................................................. 32 
2.8.4 A importância dos Algoritmos de Ordenação .................................................................... 33 
2.9 Descrição dos Algoritmos selecionados para teste ............................................................... 34 
2.9.1 SelectionSort: ..................................................................................................................... 34 
2.9.2 Quicksort ............................................................................................................................ 35 
2.9.3 Bubblesort .......................................................................................................................... 36 
2.10 Trabalhos relacionados ....................................................................................................... 36 
3 METODOLOGIA ......................................................................................................... 39 
3.1 Métricas ................................................................................................................................ 39 
3.2 Código ................................................................................................................................... 39 
4 RESULTADOS ............................................................................................................ 42 
4.1 Bateria de Testes ................................................................................................................... 43 
4.1.1 Álgebra Linear Densa: Multiplicação de Matrizes ............................................................. 43 
4.1.1.1 Configuração de Hardware 1 ........................................................................................ 43 
4.1.1.2 Configuração de Hardware 2 ........................................................................................ 46 
4.1.2 Grafos Transversais: Ordenação de Vetores ...................................................................... 49 
4.1.2.1 Configuração de Hardware 1 ........................................................................................50 
4.1.2.2 Configuração de Hardware 2 ........................................................................................ 54 
5 CONCLUSÕES ............................................................................................................ 59 
REFERÊNCIAS ................................................................................................................. 61 
 
 
 
 
 
1 
Capítulo 
 
1 Introdução 
 
 Diversos motivos levaram ao desenvolvimento das arquiteturas de processador com 
múltiplos núcleos que utilizamos em nossos computadores. 
Até meados de 2004, a forma mais simples de se obter mais desempenho de 
processamento consistia, basicamente, em substituir o processador central (CPU) por um com 
uma velocidade de clock maior (Sutter, 2005). 
 Diversos avanços na tecnologia de manufatura de processadores possibilitaram que 
clocks cada vez mais altos fossem alcançados a cada novo lançamento, como processos de 
litografia mais avançados com transistores cada vez menores ou processadores com um 
pipeline mais profundo; a Intel, por exemplo, tinha planos de lançar, nesta época, modelos do 
Pentium 4 de 5.2 GHz e até mesmo um modelo de 10 GHz era esperado para o ano seguinte 
(PC & Tech Autority. 2013). 
Apesar de toda tecnologia empregada, a indústria dos semicondutores percebeu que o 
limite físico da microeletrônica estava chegando, pois quanto mais rápido é o clock 
processador e quanto menores são os seus transístores mais energia é perdida em cada 
chaveamento em forma de calor (efeito conhecido como Gate Leakage) assim como 
sincronizar seus componentes internos se torna cada vez mais difícil (STOKES, 2013). 
Quando os processadores atingiram este limiar dos 4GHz, o consumo versus 
desempenho chegou a um limite conhecido como Power Wall, onde para se obter um pouco 
mais de desempenho era preciso gastar enormes e desproporcionais quantidades de energia, o 
que por sua vez aumentava, substancialmente, o Gate Leakage, gerando ainda mais 
calor.(STOKES, 2013). 
 A partir de então, as grandes empresas de semicondutores como Intel e AMD 
adotaram arquiteturas completamente diferentes para seus lançamentos subsequentes (Sutter, 
2005). 
 Os processadores mais modernos da época utilizavam exclusivamente arquiteturas do 
tipo Superscalar Pipelining que é uma técnica que permite paralelismo no nível de instrução 
(ILP) usando um único núcleo de processamento. Isto faz com que o processador consiga 
processar mais instruções por ciclo do que normalmente o faria (Sutter, 2005); 
2 
 
 A técnica consiste em despachar múltiplas instruções lidas da memória principal e 
selecionar as que podem ser executadas em paralelo, ou seja, instruções que não dependem 
uma da outra para serem executadas e enviá-las para unidades redundantes dentro do pipeline 
do processador. 
 Esta técnica não possui a mesma efetividade de um processador com mais núcleos, já 
que apenas algumas unidades são duplicadas (mesmo que seja todo o pipeline) e não o 
processador como um todo. A ênfase da técnica é, exatamente, manter o máximo de unidades 
de execução dentro de um processador em atividade pelo máximo de tempo disponível para a 
execução, isto permite que mais de uma instrução seja processada por ciclo de clock. 
 Esta arquitetura é muito eficiente para muitas aplicações, porém, não é muito eficiente 
quando se tenta executar um fluxo de instruções que possui um código com muitos desvios ou 
cuja execução seja difícil de prever (Sutter, 2005). 
O real paralelismo só ocorre quando possuímos unidades completas de processamento 
independentes, capazes de processar diferentes fluxos de instruções em paralelo, este método 
é conhecido como Thread Level Parallelism (TLP). Os processadores de múltiplos núcleos 
foram projetados exatamente para alcançar este objetivo. (Sutter, 2005). 
 Com mais unidades de execução disponíveis, os clocks podem se manter em um 
patamar mais baixo, gerando menos calor e consumindo menos energia e ao mesmo tempo, 
uma quantidade maior de instruções por ciclo (IPC) pode ser alcançada (Sutter, 2005). 
Atualmente, um novo ramo da computação paralela tem emergido: a computação acelerada 
ou sistemas híbridos. 
Existem muitos processadores que foram projetados e construídos para executar uma 
função específica com um desempenho muito superior ao que seria obtido por um 
processador de propósito geral como os que usamos como CPU de nossos computadores. 
Processadores gráficos, por exemplo, foram projetados para calcular enormes quantidades de 
dados em paralelo e exibir seus resultados (em forma de imagens) em nossos monitores. Uma 
CPU genérica jamais seria capaz de processar tamanha quantidade de dados e exibir os 
resultados em uma taxa satisfatória. Processadores gráficos como os contidos na placa gráfica 
AMD Radeon série 7800 podem conter mais de 1024 núcleos simples de processamento 
trabalhando em paralelo enquanto CPUs X86 com mais de oito núcleos são raras de se 
encontrar mesmo em servidores. 
 Seria excelente se fosse possível utilizar todo o poder de cálculo paralelo contido 
nestes processadores para executar não processamento de imagens, mas sim cálculos gerais, 
3 
 
os mesmos executados pelas CPUs tradicionais dos computadores. Este conceito existe e é 
chamado de GPGPU, unidade de processamento gráfico de propósito geral. 
Quando sistemas diferentes trabalham em conjunto para atingir um objetivo são conhecidos 
como Sistemas Híbridos (TSUCHIYAMA et al., 2013). 
De acordo com a Nvidia, uma das maiores fabricantes de processadores gráficos do 
mundo e grande incentivadora do conceito de GPGPU, durante a conferência internacional de 
supercomputação (International Supercomputing Conference (ISC)) de 2012 em Hamburgo 
na Alemanha, a quantidade de supercomputadores da Lista Top500, que enumera os 500 
maiores supercomputadores do mundo, que utilizam arquiteturas Hibridas com processadores 
gráficos como fonte de processamento aumentou 680% entre os anos de 2010 e 2012 nas 
posições entre 101 e 500 do ranking, 200% entre as posições de 51 e 100 e 40% entre as 50 
primeiras posições (Figura 1). (SUMIT GUPTA, 2013). 
 
 Estre grande avanço de processamento proporcionado por estas arquiteturas híbridas 
vem sendo utilizado, por exemplo, pela Universidade de Bristol para descobrir a cura para 
doenças como a gripe H1N1 que em 2009 matou mais 500,000 pessoas pelo mundo (SUMIT 
GUPTA, 2013). 
 Isto só é possível pelo fato de que estas arquiteturas tornam a obtenção de 
supercomputadores mais barata para qualquer instituição de ensino já que apenas um pequeno 
Figura 1. Crescimento de Supercomputadores do ranking Top500 que utilizam o 
conceito de GPGPU entre 2010 e 2012. 
Fonte: International Supercomputing Conference (ISC) - Nvidia 
4 
 
cluster de processadores gráficos pode proporcionar entre 5 e 10 vezes mais desempenho que 
uma solução similar e mais cara que utiliza somente processadores comuns. (SUMIT 
GUPTA, 2013). 
 A Virtualização é dos temas mais abordados e discutidos no universo da computação 
nos últimos anos, questões como consolidação e otimização de recursos e o “Green TI”, ou 
computação verde que visa controlar os gastos energéticos e emissões atmosféricas 
resultantes do uso dos computadores fazem com que o tema de virtualização seja o baluarte 
da tecnologia da informação atual (NVIDIA, 2013) 
 Pensando neste mercado emergente, a Nvidia lançou uma tecnologia Chamada de 
Nvidia GRID VGX, segundo a Nvidia (2013): 
 
“A biblioteca de software GRID é uma suíte de tecnologias que permite soluções 
virtualizadas baseadas em GPU - incluindo capacitação de gráficos em hipervisores - 
e fluxos remotos acelerados para os usuários finais. Essas tecnologias melhoram a 
performance de aplicativos e desktops virtualizados de forma eficaz e econômica.” 
(NVIDIA. 2013) 
 
 Os sistemas GRID da Nvidia utilizam processadores gráficos projetados 
especificamentepara serem utilizados em Datacenters e são conhecidos como Tesla, uma 
versão desta aceleradora, a K20x está presente no cluster do Oak Ridge National Laboratory's 
Titan, o número 1 (2012) do Top 500. A AMD também criou, tardiamente, seu produto 
concorrente chamado FirePro que já possui alguns adeptos entre os grandes Datacenters do 
Mundo (LATIF. 2012). 
 
Sistemas Híbridos, principalmente os que utilizam GPUs e CPUs são uma tecnologia 
em franca expansão no mundo dos supercomputadores e utilizados por cada vez mais 
instituições e empresas, devido a isto, sistemas Híbridos compostos por CPUs e GPGPUs são 
o tema central deste trabalho. 
 
1.1 Motivação 
 
Apesar da utilização crescente em grandes datacenters e de ser tema principal de 
convenções de supercomputação no mundo todo, os benefícios da utilização de Sistemas 
Híbridos em computação de baixa escala, como em computadores pessoais, ainda é pouco 
divulgada e apenas uma pequena fração dos softwares comerciais atuais exploram 
5 
 
verdadeiramente o poder de computação que utilização de processadores mistos como CPU + 
GPGPU podem proporcionar. 
 
1.2 Objetivos 
 
O objetivo deste trabalho é demonstrar os ganhos de desempenho no porte de código 
sequencial, utilizado em processadores comuns, para um código paralelizado capaz de fazer 
uso de todos os núcleos presentes nas CPUs atuais e também o ganho de desempenho 
adquirido em executar este código paralelizado em uma arquitetura Híbrida, de modo que o 
processador central e os inúmeros núcleos de processamento presentes nas aceleradoras 
gráficas atuais, trabalhem em conjunto para acelerar o processamento de aplicações. 
 
1.3 Organização deste trabalho 
 
No capítulo um, é realizada uma introdução ao tema de GPGPU, abordando a 
evolução do multiprocessamento com o passar dos anos focando nas abordagens de empresas 
como Intel, AMD e Nvidia assim como exibir em panorama da adoção do conceito de 
GPGPU nos tempos atuais. 
 No capítulo dois, são abordadas todos os conceitos avançados por traz da tecnologia 
de GPGPU necessários para o compreensão deste trabalho, como o paralelismo de Hardware, 
software, multiprocessamento, aceleradoras e linguagens de programação utilizadas em 
sistemas Híbridos. 
 O capítulo três aborda os métodos, métricas e tecnologias utilizados para alcançar os 
objetivos deste trabalho. 
 O capítulo quatro exibe os resultados preliminares dos experimentos detalhados no 
capítulo três. 
 O capítulo cinco exibe as conclusões resultantes dos experimentos realizados no 
capítulo quatro. 
 
 
 
7 
Capítulo 
 
2 Pesquisa Bibliográfica 
 
Cada arquitetura de hardware tem seus pontos fortes e fracos, assim como recursos e 
limitações que podem auxiliar os programadores a escreverem seus softwares para esta 
arquitetura ou impedi-los de fazê-lo. Antes de escrever um software que utilize todo o poder 
de computação oferecido pelo hardware alvo, o programador deve estudar como este 
funciona para que possa explorar seus pontos fortes corretamente. 
 Para este trabalho, o Hardware alvo será as placas gráficas da série 7800 da AMD. O 
motivo para escolha deste Hardware é o fato de que sua arquitetura, chamada de GCN – 
Graphics Core Next, foi projetada especificamente para promover alto desempenho em 
aplicações GPGPU (ADVANCED MICRO DEVICES, 2013). 
 Outros Hardwares, de fabricantes diferentes, como GPUs e processadores Intel, 
também serão testados a fim de fornecer um estrutura mais sólida de comparação para os 
resultados. 
 Nos próximos tópicos, serão explorados, especificamente, a arquitetura GCN das 
AMD série 7800, assim como as arquiteturas gráficas de modo geral e sua classificação 
taxonômica, conhecimento necessário para entender os motivos pelos quais uma arquitetura 
Híbrida pode fornecer ganhos de desempenho na execução de aplicações. 
 
2.1 Paralelismo de Hardware 
 
 No universo da computação, o paralelismo é implementado de diversas formas, em 
Hardware, Software, Instruções, Dados, etc. 
 Neste capítulo, serão abordados os temas relativos ao paralelismo de Hardware, de 
forma que este conceito, essencial para o entendimento dos resultados obtidos, sejam 
compreendidos. 
 
2.2 Taxonomia de Flynn 
 
De acordo com Ryoji Tsuchiyama: 
 
8 
 
A Taxonomia de Flynn é uma classificação de arquiteturas de computador proposta 
por Michael J. Flynn; ela se baseia na concorrência de fluxos de instruções e de 
dados disponíveis na arquitetura. Um fluxo de instruções é o conjunto de instruções 
que formam um processo, e um fluxo de dados é o conjunto de dados que serão 
processados (TSUCHIYAMA et al., 2013). 
 
A classificação proposta por Michael J. Flynn divide as arquiteturas de computador em 
quatro categorias distintas. Ainda de acordo com Ryoji Tsuchiyama estas categorias são: 
 
1. Single Instruction, Single Data Stream (SISD) – Única instrução, Único fluxo de dados: 
O sistema SISD é um sistema sequencial onde um único fluxo de instruções processa 
um único fluxo de dados. Os processadores pré-2004 são deste tipo; 
 
2. Single Instruction, Multiple Data Stream (SIMD) – Única instrução, Múltiplos fluxos de 
Dados: 
Uma instrução é distribuída entre várias unidades computacionais, onde cada unidade 
processa a mesma instrução em dados diferentes. O processador vetorial, um exemplo 
de supercomputador, é deste tipo de arquitetura. Recentemente, vários 
microprocessadores incluem processadores do tipo SIMD. Por exemplo, as instruções 
SSE dos processadores INTEL e a instrução SPE no Cell Broadband Engine que 
processam instruções do tipo SIMD; 
 
3. Multiple Instruction, Single Data stream (MISD) – Multiplas instruções, Único fluxo de 
Dados: 
Múltiplos fluxos de processos em um único fluxo de dados. Muito poucos sistemas se 
encaixam nesta categoria com exceção dos sistemas tolerantes a falhas; e 
 
4. Multiple Instruction, Multiple Data stream (MIMD) - Múltiplas instruções, Múltiplos 
fluxos de Dados: 
Múltiplas unidades de processamento que processam múltiplos fluxos de dados 
utilizando múltiplos fluxos de instruções. 
 
 Utilizando este esquema de classificação, muitas arquiteturas de hardware paralelas, 
como o SMP e sistemas do tipo Cluster, são da categoria MIMD, que por sua vez é 
categorizada pelo tipo de memória utilizada (TSUCHIYAMA et al., 2013). 
9 
 
Os dois principais tipos de memória utilizados por sistemas de computadores são a 
memória compartilhada e memória distribuída. Em sistemas com memória compartilhada, 
cada CPU disponível no sistema tem permissão para acessar o mesmo espaço de memória, em 
sistemas de memória distribuída, cada CPU disponível no sistema tem um espaço de memória 
exclusivo. 
Diferentes tipos de memória resultam em diferentes tipos de acesso a dados, se cada 
CPU estiver executando um processo, um sistema com memória compartilhada 
possibilita que dois processos se comuniquem através de leitura/escrita ao espaço de 
memória compartilhada. Por outro lado, o sistema com memória distribuída requer 
que as transferências de dados sejam executadas explicitamente pelo usuário, já que 
os dois espaços de memória são gerenciados por dois sistemas operacionais 
(TSUCHIYAMA et al., 2013). 
 
A tabela abaixo (Tabela 1) sintetiza as arquiteturas descritas acima e as relaciona com alguns 
exemplos de arquiteturas que a utilizam: 
 
Tabela 1 Taxonomia de Flynn para computadores paralelos 
Fluxo de Instruções Fluxo de Dados Nome Exemplos 
1 1 SISD 
Máquina Clássica 
de Von Newman 
1 Múltiplas SIMD 
Supercomputador 
Vetorial, 
Processador 
Vetorial. 
Múltiplas 1 MISD 
Sistemas de alta 
confiabilidade. 
Múltiplas Múltiplas MIMD 
Multiprocessador, 
Multicomputador. 
Fonte: (TANENBAUM, 2007) 
 
2.3 Sistemas de Memória distribuída e compartilhada 
Existem diversos tipos de sistemas computacionais que utilizam um ou outro sistema 
de memória, variando de acordo com o propósito da arquitetura.Um profundo conhecimento 
destes sistemas não é necessário para a compreensão deste trabalho, porém um pequeno 
estudo do tema será útil para se entender a arquitetura utilizada pelas placas gráficas. 
10 
 
2.3.1 Sistemas do tipo memória Distribuída 
Existem dois tipos principais de sistemas de computador de alta performance, HPC 
(High Performance Computing), que utilizam memória distribuída, estes são os Clusters e os 
Processadores massivamente paralelos ou MPP (Massively Parallel Processor). 
 Os sistemas do tipo Cluster são sistemas de computadores interligados em rede 
capazes de trabalhar em conjunto realizando tarefas que levariam muito tempo para serem 
processadas em computadores comuns, mas que quando quebradas em pequenas partes e 
enviadas para cada um dos nós da rede, faz com que o objetivo seja alcançado em uma fração 
do tempo. Este é o tipo mais comum de HPC (TSUCHIYAMA et al., 2013). 
 Os sistemas do tipo MPP, assim como os Cluster, são sistemas de computadores 
interligados em rede capazes de trabalhar em conjunto, porém, ao contrário dos Clusters, os 
sistemas do tipo MPP utilizam hardware dedicado e específico para a tal, o que os torna 
extremamente caros e raros. O NEC Earth Simulator e o IBM blue Gene são exemplos deste 
tipo de sistema (TSUCHIYAMA et al., 2010). 
 O grande problema com estas arquiteturas reside na lentidão do meio utilizado para 
transferir dados entre os processadores, mesmo com o avanço das tecnologias de rede como 
as redes do tipo 10Gbit Ethernet, estes meios de comunicação ainda são muito inferiores aos 
meios utilizados pelos processadores para acessar sua memória local 
(TSUCHIYAMA et al., 2010). 
 
Concluindo: 
Pelas razões citadas acima, os sistemas do tipo Cluster são projetados para 
algoritmos paralelos conde as CPUs não tem de se comunicar com frequência. Estes 
tipos de algoritmos são chamados de Paralelos de Granularidade Alta. Este 
algoritmos são frequentemente utilizados em simulações onde muitas tentativas são 
necessárias, mas estas não possuem dependência 
(Tsuchiyama et all - 2010). 
 
2.3.2 Sistemas do tipo memória Compartilhada 
Assim como nos Sistemas de Memória Distribuída, existem dois tipos principais de 
sistemas de computador de alta performance que utilizam memória compartilhada, estes são 
os sistemas SMP (Symmetric Multiprocessing – Multiprocessamento Simétrico) e os sistemas 
NUMA (Non-Uniform Memory Access – Acesso não Uniforme à Memória). 
 
11 
 
Nos Sistemas do tipo memória Compartilhada, todos os processadores compartilham 
o mesmo espaço de endereçamento, permitindo que estes processadores se 
comuniquem entre si através de leituras/escritas na memória compartilhada. Como 
transferências de dados entre nós é desnecessária, isto resulta em um sistema muito 
mais simples do ponto de vista do software (Tsuchiyama et all - 2010). 
 
 
A Figura 2 ilustra as diferenças fundamentais entre um sistema NUMA e um sistema SMP. 
 
 
 Ambos são métodos válidos e muito utilizados para se implementar sistemas 
multiprocessados, a principal diferença entre eles está na forma de acesso a memória; 
sistemas do tipo NUMA priorizam o acesso a uma memória local mais próxima, mais ágil e 
com um custo de acesso menor; sistemas do tipo SMP possuem canais de acesso 
compartilhados a uma memória principal mais distante (TSUCHIYAMA et al., 2010). 
 O acesso compartilhado a memória dos sistemas SMP tornam este sistema não 
escalável, já que ao se adicionar mais processadores ao conjunto, o gargalo no acesso a 
memória se torna evidente, porém, este método torna o sistema barato de se produzir e por 
este motivo os sistemas do tipo SMP são muito utilizados em estações de Trabalho com até 2 
Processadores, onde o gargalo não se torna um agravante considerável ao desempenho geral. 
Em contrapartida, sistemas do tipo NUMA tem maior dificuldade em manter o conteúdo de 
seus caches de baixo nível sincronizados e coerentes entre os processadores do conjunto, por 
este motivo, um hardware especializado e um cache de acesso global geralmente são 
adicionados formando um sistema conhecido como NUMA de Cache Coerente ou Cash 
Coherent NUMA (cc-NUMA) (TSUCHIYAMA et al., 2010). 
 A Figura 2 deixa claro as semelhanças entre os sistemas do tipo SMP e os atuais 
processadores de múltiplos núcleos. 
 Processadores de múltiplos núcleos possuem dois ou mais processadores completos 
em seu interior, com seu próprio cache de baixo nível e unidades de processamento, mas 
Figura 2. Os Sistemas Multiprocessados do tipo SMP e NUMA. 
Fonte: (The OpenCL Programming Book, 2010) 
 
12 
 
todos estes núcleos compartilham o mesmo espaço de memória e a acessam através de uma 
única controladora compartilhada (TSUCHIYAMA et al., 2010). 
 Se interligarmos estes processadores de múltiplos núcleos acabamos por formar um 
sistema do tipo NUMA, em outras palavras, os servidores atuais que utilizam o sistema 
NUMA são na verdades sistemas NUMA formados por conjuntos de processadores que por 
sua vez utilizam internamente uma arquitetura do tipo SMP como mostrado na Figura 3 
(TSUCHIYAMA et al., 2010). 
 
 
Figura 3. Os Sistemas Multiprocessados mistos atuais. 
Fonte: (The OpenCL Programming Book, 2010) 
 
2.4 Aceleradores 
Aceleradores são coprocessadores projetados especificamente para auxiliar um ou 
mais processadores genéricos a desempenhar determinadas tarefas com o máximo 
desempenho possível ao invés de utilizar vários processadores genéricos para cumprir a 
mesma tarefa (TSUCHIYAMA et al., 2010). 
Um exemplo deste tipo de sistema é o supracitado Cell Broadband Engine que é composto 
por um processador IBM PowerPC chamado de Power Processor Element (PPE) e 8 
Synergistic Processor Elements (SPE) que são núcleos especializados em cálculos 
matemáticos de ponto flutuante (TSUCHIYAMA et al., 2010). 
 Este acelerador é o mesmo utilizado no console de videogame Playstation 3 da Sony 
que ficou muito conhecido pelo seu alto poder de processamento e por sido adaptado em sua 
primeira versão para trabalhar em um cluster com 12 consoles onde através de sistema 
operacional, de código aberto Linux adaptado, é atualmente utilizado para realizar simulações 
de interações de determinadas drogas com as membranas celulares pelo departamento de 
Biologia da Universidade Estadual de Campinas. Este tipo de simulação requer grande poder 
de processamento, o que comprova o enorme poder de processamento, proporcionado pelos 
aceleradores e o seu potencial para criar sistemas de processamento massivamente paralelo a 
13 
 
custo infinitamente menor ao de um datacenter que utiliza processadores comuns (Sato, et all, 
2007). 
Um outro exemplo de acelerador, e um dos focos deste trabalho é a Aceleradora 
Gráfica AMD Radeon HD 7850, que possui um processador com 1024 unidades de cálculo 
distribuídas em 16 unidades computacionais formando um conjunto capaz de produzir uma 
potência de cálculo de até 160 GFlops em cálculos de ponto flutuante de precisão dupla em 
um chip que possui 2,8 Bilhões de Transistores. 
Aceleradores Combinados com CPUs genéricas formam um sistema Híbrido. 
 
Um acelerador proporciona por um baixo custo e baixo gasto energético um sistema 
de alto desempenho. Entretanto a velocidade de transferência entre um processador 
central e um acelerador pode se tornar um gargalo fazendo com que os aceleradores 
sejam inadequados para aplicações que requeiram uma alta taxa de operações de 
entrada e saída, portanto, a decisão de se utilizar um sistema hibrido e qual sistema 
hibrido utilizar deve ser sabiamente planejada (Tsuchiyama et all. 2010). 
 
2.5 Paralelismo de Software 
 
Em 1965, o então presidente da Intel Gordon E. Moore fez uma observação que acabou 
se transformando em uma Lei conhecida como Lei de Moore; esta Lei diz que o número de 
transistores dos chips teria um aumento de 60%, pelo mesmo custo, a cada período de 18 
meses; Moore revisou sua Lei em1975 dizendo que o número de transistores dobraria a cada 
dois anos, mantendo seu custo (Moore, 1965). 
 A grande questão atual é como otimizar o software para aproveitar todo estes recursos, 
já que o avanço das tecnologias e linguagens de programação não acompanham a velocidade 
de evolução do Hardware. 
A maioria dos desenvolvedores não se preocupam em otimizar seus códigos para o 
hardware em que serão executados se conformando em relegar todo o trabalho aos 
compiladores que por mais avançados que sejam ainda não são capazes de tornar softwares 
não otimizados em softwares eficazes em termos de aproveitamento de hardware. 
 O problema se agrava quando precisamos produzir um código capaz de ser executado 
em um acelerador como o supracitado AMD Radeon 7850, e suas 1024 unidades 
computacionais. Este tipo de software exige não só um código altamente otimizado, mas 
também um software capaz de utilizar o processamento de diferentes processadores em um 
sistema híbrido paralelamente e lidar com todas as peculiaridades que um ambiente como este 
traz. 
14 
 
2.5.1 Processamento Paralelo e Sequencial 
 Para exemplificar as diferenças entre o processamento paralelo e sequencial, 
assumiremos o código exibido na Figura 4: 
 
001 
002 
003 
004 
005 
006 
007 
for(i=0;i<N;i++){ 
 resultA = task_a(i); 
 resultB = task_b(i); 
 resultC = task_c(i); 
 resultD = task_d(i); 
 resultAll += resultA + resultB + resultC + resultD; 
} 
Figura 4. Código de exemplo para processamento paralelo. 
Fonte: (The OpenCL Programming Book, 2010) 
 
Este pseudocódigo é um bom exemplo sobre o quão importante é a otimização de 
código para o processamento paralelo. Se este código for executado em um processador de 
único núcleo sequencial, cada uma das tarefas (task_a, Task_b, etc.) seriam executadaa 
sequencialmente N vezes incrementando o valor de I em cada iteração, somando seus 
resultados e gravando-os em uma variável nomeada resultAll (TSUCHIYAMA et al., 2010). 
 Sem otimização, mesmo em um processador de múltiplos núcleos, este código seria 
executado em apenas um dos núcleos disponíveis. No caso de um processador de Dois 
Núcleos, um deles ficariam ocioso durante todo o processo, o que é claramente um enorme 
desperdício de energia e processamento, principalmente em sistemas móveis onde a economia 
de energia é vital. (TSUCHIYAMA et al., 2010). 
 Com um pouco de otimização de código, é possível fazer um que cada um dos laços 
fossem executados em um dos dois núcleos do processador simultaneamente, finalizando 
assim a execução de todo o processo em quase metade do tempo de execução do método 
sequencial, como mostrado na Figura 5. 
 
15 
 
 
Figura 5. Código otimizado para processamento paralelo. 
Fonte: (The OpenCL Programming Book, 2010) 
 
 Processar código de maneira paralela mostra-se então claramente vantajoso, mas será 
que esta afirmação é verdadeira para todos os cenários? 
 De acordo com Tsuchiyama (2010), existem 3 passos que devem ser seguidos ao 
portar código para execução paralela: 
 
1. Analisar as dependências entre as estruturas de dados e entre os processos, etc, para 
se decidir quais seções podem ser executadas em paralelo; 
2. Decidir qual é o melhor algoritmo para executar o código em múltiplos 
processadores; e 
3. Reescrever o código usando frameworks como o Message Passing Interface (MPI), 
OpenMP ou OpenCL. 
 
16 
 
 Portanto, antes de converter um código para processamento paralelo, deve-se 
inicialmente, analisa-lo e decidir as seções que podem ser executadas em paralelo. 
 Em 1967 na AFIPS Spring Joint Computer Conference, o engenheiro da computação Gene 
Myron Amdahl, apresentou aos presentes o que ficaria conhecida como a Lei de Amdahl. 
A Lei de Amdahl, é utilizada para encontrar o aprimoramento máximo esperado de um 
sistema quando apenas parte deste sistema é aprimorado. Esta Lei é comumente utilizada em 
computação paralela para prever a aceleração de processamento máxima quando utilizados 
múltiplos processadores (Stijn Eyerman, et all, 2010). 
 A Lei afirma que um software gasta y% do seu tempo de execução do código que não 
pode ser executado em paralelo e que o aprimoramento de velocidade máximo obtido por 
paralelizar o código é no máximo 1/y, assim a Lei é expressa pela formula: 
 
S = N/(Y*N)+(1-Y) 
 
 Sendo N o número de processadores ou núcleos do conjunto e Y a porcentagem de 
código que não poder ser processada em paralelo. (Michalove, apud Lewis et all, 1992) 
 Por exemplo, dois softwares reescritos para serem executados em paralelo em um 
processador com quatro núcleos, as porcentagens de código que não pode ser executada em 
paralelo (Y) são de respectivamente de 10 e 50%; de acordo com a Lei de Amdahl o 
incremento de desempenho máximo para este cenário é de aproximadamente 3 e 1,3 vezes o 
desempenho do processamento inteiramente serial conforme exibido na Figura 6 
(TSUCHIYAMA et al., 2010). 
17 
 
 
Figura 6. Incremento de desempenho de acordo com a lei de Amdahl. 
Fonte: (The OpenCL Programming Book, 2010) 
 
 A Lei de Amdahl é bastante pessimista em termos de incremento de desempenho, 
levando-se em consideração sistemas com grandes quantidades de núcleos de processamento 
torna-se visível que mais importante do que paralelizar o código é reduzir a quantidade de 
código que só pode ser processada serialmente (TSUCHIYAMA et al., 2010). 
Existe outra Lei, bem menos pessimista no que diz respeito aos ganhos da execução paralela 
chamada de Lei de Gustafson (TSUCHIYAMA et al., 2010). 
A Lei de Gustafson diz que a fração de um software capaz de ser executada em 
paralelo aumenta conforme o tamanho do software também aumenta, reduzindo a proporção 
do software que só pode ser executada sequencialmente (TSUCHIYAMA et al., 2010). 
 Se tomarmos como exemplo um software onde apenas as operações de carga, 
inicialização e fechamento devem ser executadas sequencialmente e todo o restante pode ser 
executado em paralelo, a Lei de Gustafson é bem lógica. 
 Estas duas leis são a base da programação paralela (TSUCHIYAMA et al., 2010). 
2.5.2 Tipos de Paralelismo 
Após selecionar quais áreas do código podem ser executadas em paralelo, podemos 
decidir qual é o melhor algoritmo para executar o código em múltiplos processadores 
 Existem dois tipos de paralelismo de software: O paralelismo de Dados (Data 
Parallel) e o paralelismo de Tarefas (Task Parallel). 
18 
 
Para se executar alguma tarefa (task) em paralelo é necessário separar dos dados dos 
processos. 
 Retomando o código da Figura 4 mas desta vez executado em com Processador de 
quatro núcleos, se utilizado o paralelismo de dados, cada processador poderia executar N/4 
iterações do loop, já se utilizado o paralelismo de tarefas, cada processador poderia executar 
uma das quatro tarefas presentes em cada iteração do loop como mostrado na Figura 7 
(TSUCHIYAMA et al., 2010). 
 
 
Figura 7. Paralelismo de Dados vs Paralelismo de Tarefas. 
Fonte: (The OpenCL Programming Book, 2010) 
 
O Paralelismo de Dados é o mais indicado para quando as dependências entre os 
dados executados por cada um dos processadores é mínima, o que o torna muito eficiente em 
operações como soma de vetores, onde a escala de desempenho é diretamente proporcional ao 
número de processadores, ou no processamento de pixels onde cada bloco de pixels pode ser 
tratado por um processador de forma independente tornando o desempenho também 
facilmente escalável. 
O paralelismo de dados é o de mais simples implementação entre os algoritmos 
paralelos, já que não é necessário se preocupar com dependências durante a implementação 
do código como exibido na Figura 8 (TSUCHIYAMA et al., 2010). 
 
19 
 
 
Figura 8. Paralelismo de Dados, soma de vetores. 
Fonte: (The OpenCL Programming Book, 2010) 
 
 Já o Paralelismo de tarefas é o mais complexo dos métodos de paralelismo e pode ser 
encontradonas arquiteturas da maioria dos processadores atuais e consiste, basicamente, na 
capacidade de se executar tarefas diferentes em unidades de processamento diferentes. 
 Controlar o fluxo de tarefas entre os processadores não é uma tarefa fácil, já que ao 
contrário do paralelismo de dados, cada tarefa pode terminar sua execução em tempos 
diferentes. Existem dois métodos muito utilizados de controle de paralelismo de tarefas, 
focados em aproveitar ao máximo os recursos das unidades de execução. Este são o 
balanceamento de carga e o pipelining. 
O balanceamento de carga ou Load balancing faz com que uma das unidades de 
processamento fique encarregada de despachar tarefas para as outras fazendo com que o 
tempo ocioso de cada uma das unidades seja reduzido ao mínimo possível como mostrado na 
Figura 9 (TSUCHIYAMA et al., 2010). 
 
 
20 
 
 
Figura 9. Balanceamento de Carga. 
Fonte: (The OpenCL Programming Book, 2010) 
 
O pipelining é o mais comum de ser encontrado e é explorado com sucesso nos computadores 
pessoais. A técnica de pipelining, também conhecida como instruction pipelinine, ou pipeline 
de instruções consiste em desacoplar os diferentes estágios de execução dentro do 
processador, como a busca, decodificação e execução e fazer com que cada uma delas seja 
executada de forma sobreposta (TSUCHIYAMA et al., 2010). 
 Este método é muito eficiente quando muitas tarefas diferentes devem ser executadas, 
porém, este método aumenta significativamente a complexidade do código (TSUCHIYAMA 
et al., 2010). 
 A Figura 10 mostra em detalhes uma implementação deste sistema. 
A escolha entre um ou outro algoritmo não pode ser feita somente por decisão do 
programador, as funções disponíveis no hardware alvo são determinantes para a escolha do 
algoritmo a ser utilizado. 
 Como informado, as aceleradoras gráficas com arquiteturas capazes de executar 
operações de propósito geral e não somente operações gráficas, são nosso hardware alvo, e 
por isto devem ser estudadas para que seus recursos possam ser utilizados corretamente. 
 
21 
 
 
Figura 10. Pipelining. 
Fonte: (The OpenCL Programming Book, 2010) 
 
 
2.6 Aceleradoras Gráficas e a arquitetura GCN 
 
Antes da entrada no mercado do Unified Shader Model, ou modelo de shaders unificado 
(USM) em 2002, as GPUs eras especializadas somente para processamento de imagem e 
possuíam unidades especializadas para cada uma das operações gráficas padrão, pixels, 
geometria e vórtices (STOKES, 2007). 
 Com o advento das aceleradoras gráficas com suporte ao USM, as unidades 
especializadas foram substituídas por unidades “genéricas” capazes de executar qualquer uma 
destas três operações básicas (STOKES, 2007). 
Esta mudança abriu caminho para o uso de computação genérica em aceleradoras gráficas 
(STOKES, 2007). 
22 
 
A arquitetura GCN é a base das atuais e futuras implementações das aceleradoras da 
AMD que podem ser eficientes tanto em processamento gráfico quanto em computação de 
propósito geral. 
 A arquitetura GCN sucede a até então altamente eficiente arquitetura VLIW (Very 
Long Instruction Word) (SMITH, 2011). 
Segundo a Philips Semiconductors (1999): 
As arquiteturas VLIW se distinguem das tradicionais arquiteturas RISC e CISC 
implementadas nos processadores de massa disponíveis no mercado. É importante 
disquinguir a arquitetura de instruções – o modelo de programação – da 
implementação – o chip em si e suas características. 
Microprocessadores VLIW e implementações superescalares de conjuntos de 
instruções tradicionais compartilham algumas características – múltiplas unidades de 
execução e a habilidade de executar múltiplas operações simultaneamente. As 
técnicas para alcançar alto desempenho entretanto são bem diferentes pois nas 
instruções VLIW o paralelismo está implícito mas precisa ser descoberto pelo 
hardware em tempo de execução pelos processadores superescalares. 
Implementações da arquitetura VLIW são mais simples para o alto desempenho. 
Assim como as arquiteturas RISC permitem implementações mais baratas e simples 
de alto desempenho do que as implementações CISCs, as arquiteturas VLIW são 
mais simples e baratas do que as RISCs devido a simplificações no hardware. 
Arquiteturas VLIW entretanto requerem mais suporte por parte dos compiladores. 
(very-long, 1999) 
 
A arquitetura VLIW da AMD, que em sua série HD 6XXX (codinome Cayman) é 
chamada de VLIW4, possui este nome devido a sua implementação em hardware dos 
chamados SPs, ou Stream Processors. Cada SP é composto por 5 unidades fundamentais de 
cálculo (ALU) junto com registradores, unidade de desvio e uma unidade de função especial 
(SFU) exibidos na Figura 11 (SMITH, 2011). 
 
 
Figura 11. SP da arquitetura VLIW4. 
Fonte: Anandtech, (2012) 
 
A arquitetura VLIW foi projetada para executar muitas operações de uma mesma 
tarefa em paralelo ao quebrá-la em grupos menores chamados de wavefronts. No caso da 
implementação VLIW4 da AMD, cada wavefront é composto por 64 valores (pixels, etc.) e 
uma lista de instruções para serem executadas nestes dados (Figura 12) (SMITH, 2011). 
http://www.anandtech.com/show/4455/amds-graphics-core-next-preview-amd-architects-for-compute/2
23 
 
 Em uma situação ideal quando uma wavefront chega ao SP para ser executada, 4 ou 5 
instruções descem pelo pipeline e são executadas em paralelo; no pior dos casos, quando uma 
instrução possui uma dependência de outra, menos instruções podem descer pelo pipeline e 
serem executadas (SMITH, 2011). 
 
Figura 12. Processamento de instruções de um Wavefront na arquitetura VLIW4. 
Fonte: Anandtech, (2012) 
 
Ao contrário das CPUs genéricas dos computadores atuais com suas arquiteturas RISC 
e CISC que podem reorganizar a execução das instruções e até mesmo executá-las fora de 
ordem, a arquitetura VLIW é extremamente dependente do compilador e não pode ter sua 
execução alterada em tempo de execução o que a torna ineficiente para execução de propósito 
geral. Esta ineficiência fez com que a AMD migrasse para a arquitetura nomeada Graphics 
Core Next (SMITH, 2011). 
A arquitetura GCN abandona o VLIW em favor de uma arquitetura SIMD. Apesar de 
a arquitetura do tipo SIMD possa parecer com a arquitetura VLIW, elas são muito diferentes 
no processo de execução. A arquitetura VLIW é focada no paralelismo a nível de instrução 
(ILP – ver Figura 13) e a implementação da arquitetura SIMD feita pela AMD, apesar do 
nome, é mais focada em paralelismo a nível de tarefa (Smith, 2011). A Figura 13 mostra um 
comparativo entre os tipos de paralelismo de dados. 
http://www.anandtech.com/show/4455/amds-graphics-core-next-preview-amd-architects-for-compute/2
24 
 
 
Figura 13. Comparativo entre paralelismo de dados (DLP - a), paralelismo a nível de 
instrução (ILP - b) e paralelismo de tarefas (TLP - c) 
Fonte: (Ahn, et all, 2007) 
 Diferentemente dos SPs da arquitetura VLIW4, os SIMDs da arquitetura GCN são 
compostos por 16 unidades ALU (Arithmetic logic unit – Unidade Lógica Aritimética) e um 
registrador de 64KB (Figura 14). A arquitetura GCN continua a trabalhar com os wavefronts 
de 64 instruções do VLIW4, porém estes agora levam somente 4 ciclos para serem 
processados por um único SIMD da arquitetura GCN, exibido na Figura 14 (SMITH, 2011). 
 
 
Figura 14. SIMD da arquitetura GCN 
Fonte: Anandtech, (2012) 
 
Cada SIMD é apenas parte de um grande conjunto que compõem os processadores das 
aceleradoras AMD com arquitetura GCN. 
25 
 
 Um SIMD sozinho é capaz de executar uma série de operações vetoriais e somente 
isto, mas, quando combinados os SIMDs formam o que a AMD chama de Unidade 
Computacional ou CU - Computational Unit - que é capaz de muito mais (Figura 15) 
(SMITH, 2011). 
 
Figura 15. Unidade Computacional GCN – CU 
Fonte: Anandtech, (2012) 
 
 Uma unidade computacional é formada, por quatro blocos SIMD, o que significa que 
cada CU pode trabalhar em quatro instruções paralelamente.Cada CU também contém uma 
peça de hardware chamada de Control Hardware & Branch Unit, responsável pela busca, 
http://images.anandtech.com/doci/4455/GCN-CU.png
http://www.anandtech.com/show/4455/amds-graphics-core-next-preview-amd-architects-for-compute/2
26 
 
decodificação e agendamento das Wavefronts e suas instruções, um cache de 16KB para 
dados e texturas e uma unidade escalar (SMITH, 2011). 
A unidade escalar foi projetada para manter quaisquer operações matemáticas 
consideradas ineficientes, como operações com inteiros simples, desvios (ifs e elses), saltos e 
acessos ao cache L1 dedicado, longe dos SIMDs (SMITH, 2011). 
 A unidade escalar pode processar uma instrução por ciclo, ou seja, é capaz de 
processar quatro instruções simples no mesmo período de tempo em que um único SIMD 
pode processar uma wavefront completa (SMITH, 2011). 
 Portanto, cada CU possui uma GPU escalar e uma GPU vetorial onde cada tarefa é 
enviada para a unidade que se adapta melhor a ela, melhorando a latência de processamento 
em geral. 
 Com estes componentes combinados, a AMD eliminou a principal fraqueza da 
arquitetura VLIW que é sua incapacidade de agendar instruções em tempo de execução graças 
a sua enorme dependência do compilador. Cada CU da arquitetura GCN é capaz de agendar a 
execução das suas wavefronts e, apesar de não possuir a capacidade de processamento fora de 
ordem, as CUs podem selecionar diferentes wavefronts de uma mesma tarefa ou de uma tarefa 
diferente e executa-las tornando a arquitetura GCN uma arquitetura do tipo MIMD (Figura 
16) (SMITH, 2011). 
 
Figura 16. Comparativo entre a execução de wavefronts pela arquitetura GCN e a arquitetura 
VLIW4 (Radeon HD 6xxx – Cayman) 
Fonte: Anandtech, (2012) 
http://images.anandtech.com/doci/4455/Wavefront.png
27 
 
 
Assim como uma combinação de SIMDs com outros componentes especializados 
formam uma CU, um agrupamento de CU com outros componentes especializados formam a 
GPU em si. 
Quando agrupadas e conectadas ao cache L1, somente leitura global, quatro CUs formam um 
vetor de CU e vetores de CU quando conectados a um cache L2 global formam uma GPU 
GCN (Figura 17) (SMITH, 2011). 
 
Figura 17. A GPU GCN 
Fonte: Anandtech, (2012) 
http://images.anandtech.com/doci/4455/AMD-GCN-3.png
28 
 
 
Explicando os componentes especializados da Figura 17, a AMD introduziu na 
arquitetura GCN um cache L2 acoplado as controladoras de memória da aceleradora. Cada 
controladora de memória possui uma palavra de 64 bits e está conectada a uma porção do 
cache L2 de 64 ou 128KB dependendo do modelo. Todas as CUs tem acesso ao cache L2 e 
podem enxergar os mesmos dados, isto evita acessos desnecessários a VRAM (Vídeo RAM, 
que é a memória RAM dedicada, especialmente ao hardware gráfico) para sincronização. A 
sincronização entre a CPU genérica e a GPU fica a cargo de protocolos específicos para tal 
presentes na tecnologia de PCIe (PCI Express – atual padrão para interconexão de periféricos 
em computadores) (SMITH, 2011). 
Os componentes nomeados como Asynchronous Compute Engines (ACE) são 
responsáveis por receber as tarefas do processador central e as distribuir pelas CU para 
processamento. 
Como informado previamente, as GPUs GCN são processadores que não possuem a 
capacidade de processar as informações fora de ordem, mas através das ACEs a GPU pode 
priorizar tarefas, impedindo que estas consumam muitos recursos da aceleradora por 
demasiado tempo, assim como evitar loops infinitos, possibilitando assim que a arquitetura 
GCN possua uma limitada capacidade de execução fora de ordem, assim como as atuais 
CPUs de execução em ordem como os Atom e os ARM V8 (SMITH, 2011). 
Muita capacidade de processamento genérico foi adicionada a arquitetura GCN, 
porém esta continua sendo uma arquitetura focada em processamento gráfico, por isto alguns 
componentes foram adicionados a GPU para o processamento de imagens. Os Primitive 
Pipelines (PP) são interligados ao Graphics Command Processor (GCP) que é responsável 
por escalonar trabalhos relacionados ao processamento gráfico e distribui-los pelos 
componentes responsáveis na GPU. As PP são responsáveis pelas tarefas de processamento 
de Tessellation, geometria, processamento de superfície entre outros. 
Depois de passar pelas CUs os dados são entregues as ROPs ou Raster Operations Pipelines 
que são responsáveis pela finalização da imagem e por grava-la novamente na memória para 
que seja então finalmente exibida (SMITH, 2011). 
 
2.7 Frameworks 
 
Neste momento, já foram abordados os itens principais a serem analisados para se 
portar código, para execução paralela. Foi abordado no texto como analisar as estruturas do 
29 
 
código e decidir quais seções podem ser processadas em paralelo e sobre como é importante 
se reduzir acima de tudo, as porções do código que só podem ser processadas 
sequencialmente. Foi informado também que o nosso Hardware alvo, as aceleradoras gráficas 
com arquitetura GCN são, de acordo com a Taxonomia de Flynn uma arquitetura do tipo 
MIMD que pode, diferentemente da geração anterior VLIW, escalonar tarefas em tempo de 
execução e processar wavefronts até mesmo de tarefas diferentes, concorrentemente, o que as 
tornam excelentes em paralelismo de tarefas. 
 O próximo passo para alcançar o objetivo deste trabalho é avaliar os possíveis ganhos 
de desempenho quando o código de um software é portado para execução paralela em um 
sistema Híbrido, a partir de comparações de desempenho de processamento entre código 
portado e não portado para paralelismo em sistemas híbridos. 
A escolha de um framework adequado é essencial para atingir este objetivo. 
 Os frameworks existem para auxiliar a paralelização do código, o programador deve 
especificar as áreas do código que devem ser executadas em paralelo e o framework se 
encarrega de transferir os dados e as tarefas para as unidades de execução corretas, permitindo 
que o programador se concentre apenas no código. 
2.7.1 OpenCl e Cuda 
 
 Uma tecnologia que tem chamado a atenção da indústria e vem sendo suportado por 
cada vez mais fabricantes (AMD, NVIDIA e Intel entre eles) é o OpenCL. 
Segundo Tsuchiyama (2010): 
O OpenCL (Open Computing Language) é um “Framework para programação 
paralela em sistemas heterogêneos”. Este framework inclui a linguagem C OpenCL 
assim como o compilador e o ambiente de desenvolvimento necessário para se 
executar código escrito em C OpenCL (TSUCHIYAMA et al., 2010). 
 
O OpenCL é uma tecnologia padronizada e livre mantida pelo Khronos Group, o 
mesmo responsável pela especificação OpenGL, com membros como AMD, Apple, IBM, 
Intel, NVIDIA, Texas Instruments, Sony e Toshiba. 
 
A escolha do OpenCL como framework padrão para a utilização neste trabalho não foi 
por mero acaso, existem outras tecnologias similares com menor atualização em hardware 
comum como a Message Passing Interface (MPI) muito utilizada em cluster ou a OpenMP 
utilizada por sistemas com memória compartilhada (SMP, NUMA) e outras com grande 
aceitação como a linguagem CUDA da NVIDIA. A linguagem CUDA permite uma 
30 
 
programação simples assim como permite que a CPU execute tarefas genéricas enquanto a 
GPU executa as tarefas de paralelismo de dados. As GPUs NVIDIA são fabricadas tanto em 
suas versões para computadores pessoais como versões especializadas para GPGPU como as 
aceleradoras Tesla. 
 Infelizmente a linguagem CUDA, assim como seus compiladores, são proprietários e 
somente podem ser executados em soluções vendidas pela própria NVIDIA o que tornaria o 
escopo deste projeto bastante limitado. 
 As aceleradoras mais atuais fabricadas pela NVIDIA, já oferecem suporte ao 
framework OpenCL. 
 A Figura 18 mostra algumas das empresas associadas ao Khronos Group, mantenedor 
do OpenCL; o forte apoio da indústria foi determinante para a escolha do OpenCL como 
framework padrão utilizado neste trabalho. 
 
 
Figura 18– Algumas empresas associadas ao Kfronos Group 
Fonte: (KFRONOS GROUP, 2013) 
 
2.7.2 Aparapi 
 
 Apesar de todos os benefícios, programar e otimizar código em OpenCL é 
extremamente trabalhoso, devido ao uso de linguagens que estão longe de ser de alto nível 
(C/C++) e o fato de que o programador deve tratar no próprio código as transferências de 
dados ente a memória do Host e a do Dispositivo (CPU para GPU) (Frost, 2011). 
Pensando nisto, a AMD, em 14 de Setembro de 2011, lançou como OpenSource a API 
Aparapi, para programação paralela utilizando a linguagem JAVA. 
 A Aparapi consegue, em tempo de execução, identificar se um sistema suporta a 
execução de código em OpenCL e converte o bytecode do método run() do JAVA para 
OpenCL. Se o código, por algum motivo não pode ser convertido, a API executa o código 
usando JTP (Java Thread Pool – permite a execução de múltiplas threads em Java 
concorrentemente) (Frost, 2011), a Figura 19 mostra em detalhes o que ocorre ao início da 
execução de um Kernel OpenCL na API Aparapi: 
31 
 
 
Figura 19. Ciclo de execução da Aparapi 
Fonte: Frost, (2012). 
 
 O Framework Aparapi será utilizado extensivamente em todos os testes realizados 
neste trabalho e os resultados colhidos fornecerão uma visão mais detalhada sobre os ganhos 
de desempenho obtidos por um software Java ao portar parte de seu código para OpenCl. 
 
2.8 Algoritmos de Ordenação 
 
 Neste segmento, são detalhados os métodos e algoritmos de ordenação que serão 
utilizados nos testes de desempenho GPGPU, assim como as teorias utilizadas na medição de 
desempenho de software. 
2.8.1 Métodos 
 A principal motivação para o surgimento do computador foi resolver problemas, nesse 
contexto, o que importava era a resolução do problema, não importando muito o método de 
resolução e o tempo gasto para isso. Porém, para aplicações de grande porte, onde são 
necessários milhões de cálculos, ou cálculos sobre números extremamente grandes, surge a 
motivação para o estudo de métodos capazes de realizar a tarefa, da forma mais eficiente 
possível, onde enormes economias de memória e processamento podem ser obtidas pela 
simples otimização de código. (SEDGEWICK; WAYNE, 2011) 
32 
 
 Um design cuidadoso de um algoritmo é uma parte extremamente efetiva de se 
resolver um grande problema não importando a área de aplicação. 
 A escolha de um algoritmo para resolver um problema particular é uma tarefa árdua e 
complexa que envolve uma análise matemática sofisticada, onde é necessária muita atenção 
aos métodos de comparação de desempenho. Não se deve utilizar algoritmo algum, sem antes 
ter uma boa ideia sobre quantos recursos ele consumirá ou como deverá ser seu desempenho 
esperado. (SEDGEWICK; WAYNE, 2011) 
2.8.2 Análise Científica do Tempo de Execução de um Software 
 O mesmo método utilizado pelos cientistas de diversas áreas é também empregado 
para estudar o tempo de execução de um software. 
O tempo de execução de um software pode ser medido da seguinte forma, de acordo com o 
método cientifico: 
1. Observar o desenrolar da execução de um software e tomar medidas precisas dos 
dados; 
2. Criar uma Hipótese modelo consistente com os dados observados; 
3. Fazer predições utilizando a hipótese criada; 
4. Verificar as predições realizando novas observações; e 
5. Validar a hipótese através da repetição dos testes e comparando observações. 
 
 Um dos pilares do método científico é o de que experimentos devem ser reproduzíveis 
de forma que outros pesquisadores possam testar a hipótese criada. 
Não é possível saber com toda a certeza que uma hipótese está 100% correta, porém podemos 
validar que a hipótese esteja consistente com o que foi observado (SEDGEWICK; WAYNE, 
2011). 
2.8.3 Classificação de Software 
 No que diz respeito aos software, é conhecido que o tempo de execução destes é 
extremamente ligado à entrada de dados, ou seja, o tamanho da variável de entrada é 
determinante para se calcular o tempo de execução esperado de um software. 
 Uma das classificações de algoritmos mais utilizadas é a de ordem de crescimento; um 
programa cuja ordem de crescimento é constante executa um número fixo de operações para 
terminar sua tarefa, consequentemente, é independente do tamanho da entrada. 
33 
 
As classificações por ordem de crescimento são divididas entre (SEDGEWICK; WAYNE, 
2011): 
 Lineares: Programas que gastam uma quantidade de tempo constante processando 
cada pedaço dos dados de entrada, ou que são baseados em um único loop de 
execução são considerados lineares e são representados pela expressão N; 
 Logarítmicos: Um software cuja classificação de ordem de crescimento seja 
logarítmica é geralmente mais lento que um software de tempo constante. Geralmente 
são reconhecidos pela expressão matemática log N; 
 Linearitmicos: Este termo é utilizado para descrever algoritmos cujo tempo de 
execução para um problema de tamanho N possui uma ordem de crescimento de N log 
N; 
 Quadrático: Um programa cujo tempo de execução seja da ordem de crescimento 
N^2, possui dois loops de execução aninhados e é usado para cálculos envolvendo 
todos os pares de N elementos; 
 Cúbico: Um programa cujo tempo de execução seja da ordem de crescimento N^3, 
possui três loops de execução aninhados e é usado para cálculos envolvendo todos as 
triplas de N elementos; e 
 Exponencial: São programas cujo tempo de execução pode ser expressado por 2N ou 
maior. Estes algoritmos são extremamente lentos. 
2.8.4 A importância dos Algoritmos de Ordenação 
 Ordenação é o processo de rearranjar um sequência de objetos e colocá-los em alguma 
forma lógica. 
De acordo com Sedgewick e Wayne (2011): 
 
“No início da informática, acreditava-se que 30 por cento de todos os 
ciclos de processamento de um computador eram gastos realizando 
algum tipo de algoritmo de ordenação. Se esta fração é menor hoje em 
dia, uma das razões é que os algoritmos de ordenação são relativamente 
mais eficientes, não que a necessidade ou a importância de se realizar a 
ordenação tenha diminuído, na verdade, a ubiquidade da computação 
nos colocou em um mar de informações cujo primeiro passo para ser 
organizada é geralmente a ordenação. Todos os sistemas de 
computadores possuem implementações de algoritmos de ordenação 
para uso de sistemas e seus usuários” ( SEDGEWICK, 2011). 
 
34 
 
 Além dos motivos citados acima, existem outros que incentivaram a escolha dos 
algoritmos de ordenação para inclusão neste trabalho como forma de teste de desempenho de 
processamento (SEDGEWICK; WAYNE, 2011): 
 
 Técnicas similares aos algoritmos de ordenação podem ser utilizadas para resolver 
outros problemas. 
 Algoritmos de ordenação são geralmente um ponto de partida para resolver outros 
problemas; 
 Algoritmos de ordenação possuem uma enorme importância para o processamento de 
dados comerciais e científicos na moderna computação. Aplicações relacionadas a 
processamento transacional, análise combinatória, astrofísica, dinâmica molecular, 
linguística, genômicas, previsão do tempo e em muitos outros campos. 
 Um dos algoritmos de ordenação incluídos neste trabalho, o QuickSort é considerado 
hoje um dos dez algoritmos mais usados pela ciência e engenharia no século 20. 
 
2.9 Descrição dos Algoritmos selecionados para teste 
 
 Foram selecionados, pelos motivos supracitados, três algoritmos de ordenação para 
uso nos testes de desempenho de processamento paralelo: 
2.9.1 SelectionSort: 
 Um dos algoritmos mais simples de ordenação conhecidos. Primeiramente, o 
algoritmo encontra o menor item em um vetor e o substitui pelo item que está na primeira 
posição do vetor, ou por ele mesmo caso este já seja o menor item do vetor, então prossegue 
encontrando o menor item do vetor e trocando-o pelo que está armazenado na segunda 
posição e assim sucessivamente até que todo o vetor esteja ordenado. Este método é chamado 
de ordenaçãopor seleção já que funciona de forma a continuamente selecionar o menor item 
restante em um vetor (SEDGEWICK; WAYNE, 2011).. 
 O algoritmo SelectionSort é um método simples de se implementar e entender e é 
caracterizado por duas propriedades: 
 
O tempo necessário para a execução é insensitivo a entrada, ou seja, uma varredura de 
vetor pelo algoritmo não fornece muitas pistas sobre onde estará o menor item na 
35 
 
próxima varredura. Este comportamento pode ser desvantajoso em situações onde o 
vetor está totalmente ordenado já que, neste caso, o tempo de execução será 
praticamente o mesmo de que se o vetor estivesse totalmente desordenado. 
 A movimentação de dados é mínima; o número de acessos ao vetor é uma 
função linear do tamanho do vetor (SEDGEWICK; WAYNE, 2011). 
2.9.2 Quicksort 
 O algoritmo Quicksort é do tipo dividir-para-conquistar. Seu funcionamento, assim 
como no algoritmo de Mergesort consiste em dividir um vetor em duas partes e ordena-las 
separadamente, logo após, é realizada uma fusão dos vetores para só então haver uma 
ordenação do vetor completo. A diferença entre o Mergesort e o Quicksort consiste no fato de 
que no Mergesort o vetor é dividido ao meio, já no Quicksort o vetor é dividido de acordo 
com o conteúdo do vetor (SEDGEWICK; WAYNE, 2011). 
 As características de desempenho do Quicksort exigem uma análise matemática para 
se fazer um posicionamento preciso sobre seu desempenho 
 O loop central do algoritmo, realiza um incremento de um índice e compara uma 
entrada do vetor com um valor fixo, este é um dos fatores que tornam o Quicksort tão rápido; 
algoritmos como o Mergesort e o Shellsort são geralmente mais lentos que o Quicksort pois 
também realizam movimentação de dados em seus loops principais. 
Como citado anteriormente, uma das grandes vantagem do Quicksort é a forma com que este 
divide seu vetor em duas partes a escolha depende do valor da chave de particionamento 
(SEDGEWICK; WAYNE, 2011). 
 A chave decide onde um vetor será divido em dois vetores distintos ordenados 
aleatoriamente. No melhor dos casos, o vetor será dividido em duas partes iguais, desta forma 
o número de comparações para ordenação seriam iguais em ambos os su-vetores satisfazendo 
assim a premissa do dividir para conquistar: CN = 2CN/2 + N; o termo 2CN/2 refere-se ao 
custo de se ordenar dois subsetores, o N refere-se ao custo de se examinar cada entrada do 
vetor. O fato de fazer poucas comparações tornam o Quicksort ainda mais rápido. 
 Entretanto, o Quicksort pode ser extremamente ineficiente se as partições forem 
desbalanceadas, onde o menor valor está no primeiro subvetor e o segundo menor número 
está no segundo subvetor, assim a reordenação do vetor unificado será bem mais dispendiosa. 
 Evitar uma situação como está é o que leva os programadores a realizar um sorteio 
randômico dos valores do vetor antes de ordená-lo, isto faz com que o caso acima seja tão 
36 
 
improvável que não há um motivo para se preocupar com a possibilidade (SEDGEWICK; 
WAYNE, 2011). 
2.9.3 Bubblesort 
 Como o nome sugere, este algoritmo trabalha de forma a “flutuar” pequenas chaves do 
lado direito do vetor para o lado esquerdo. O algoritmo se inicia movendo uma chave do final 
do vetor para a esquerda enquanto a chave for menor que as chaves pela qual ela passa. 
Quando uma chave menor é encontrada esta troca de lugar com a chave em movimento e todo 
o vetor é movido para direita e todo processo é repetido. Desta forma, em cada iteração o 
vetor torna-se mais ordenado até que ao final de várias iterações esteja totalmente ordenado 
(TYLMAD, 2013). 
 No melhor cenário, onde a lista está totalmente ordenada, nada é alterado e o tempo de 
execução é linear. No pior cenário, entretanto a lista pode estar ordenada ao contrário (do 
menor para o maior) onde para um vetor de N posições teriam de ser realizadas N trocas, ou 
seja, o desempenho do algoritmo decai para uma complexidade de n2 (TYLMAD, 2013). 
 Os três algoritmos de ordenação demonstrados neste segmento assim como os 
conceitos de análise cientifica de desempenho serão utilizados nos testes realizados neste 
trabalho. 
 
2.10 Trabalhos relacionados 
 
 Trabalhos anteriores relacionados ao teste de desempenho de GPUs são 
estritamente focados em analisar o desempenho destas aceleradoras para os aficionados por 
vídeo games, através de medições de dados como FPS (Frames per second, ou quadros por 
segundo – A quantidade de quadros por segundo que a GPU é capaz de renderizar de um 
determinado jogo), sendo esta a metodologia de medição de desempenho mais comum e 
eficaz para este tipo de trabalho (DANALIS et al., 2010). 
 Estas medições, geralmente, são realizadas com software específico e proprietário 
como o RightMark e o 3DMark, que são especificamente projetados para fornecer a medição 
de desempenho das GPUs ao executar código em DirectX. (DANALIS et al., 2010) 
 Além disto, a maioria dos trabalhos relacionados voltados para a medição de 
desempenho das GPUs na execução de código de paralelo em GPUs de propósito geral em 
sistemas Híbridos são voltados para a arquitetura Nvidia e sua linguagem proprietária CUDA. 
37 
 
 Outro sistema chamado Gbench, que é voltado para a comparação de desempenho de 
CPU e GPU em operações comuns do conhecido software de engenharia MatLab. 
 Volkov e Demmel também mediram o desempenho de processamento das GPUs no 
cálculo de Álgebra Linear com extensa descrição do sistema de memória das GPUs. 
 Parboil e Rodinia são sistemas de benchmark focados na análise do comportamento na 
execução de aplicações cientificas e Kernels em GPUs, porém, também foram escritos usando 
a linguagem CUDA da Nvidia (DANALIS et al., 2010). 
 Outro sistema chamado SHOC (Scalable HeterOgeneous Computing Benchmark 
Suite, ou Sistema de medição de desempenho de computação Heterogênea), trabalha de uma 
forma um pouco diferente dos demais, segundo Danalis: 
 
“O SHOC é distinto de outros sistemas pois foi projetado para ser 
verdadeiramente um conjunto escalável de testes de desempenho, capaz de 
testar grandes clusters e um enorme número de dispositivos diferentes.” 
(DANALIS et al., 2010) 
 
 O SHOC inclui suporte para a linguagem OpenCl, porém também se distingue deste 
trabalho pois não opera especificamente com o Framework Aparapi. 
 Tratando especificamente de código utilizando a Aparapi, existem muitos trabalhos 
não especializados disponíveis na grande rede, o que é surpreendente em se tratando de um 
Framework tão específico e recente, o que mostra a força que a nova proposta de computação 
como a computação Híbrida possui. 
 Existem trabalhos como o de Mahadevan, que atualmente trabalha com a integração 
de frameworks como o Aparapi em dispositivos móveis que utilizam o sistema operacional 
Android, desta forma, levando os benefícios da computação heterogênea para estes 
dispositivos que tem como linguagem de programação principal o Java. (MAHADEVAN, 
2013) 
 Outros trabalhos, no entanto, são voltados para a análise de desempenho da Aparapi 
em aplicações bastante específicas como o trabalho de Krishan Gopal Gupta (Gupta, 2013) 
onde este realiza testes de desempenho do framework Aparapi, através da execução de um 
algoritmo chamado Sobel Edge Detection ou Detecção de Sobel Edge, que é um algoritmo de 
processamento de imagens voltado para a detecção de contornos das formas obtidas de uma 
imagem qualquer. Os resultados obtidos por Kristian foram elucidativos, segundo os 
resultados, somente em grandes cargas de trabalho é que a Aparapi se mostra compensatória, 
38 
 
já que seus tempos de execução necessários para criar as treads e kernels do OpenCl podem 
não compensar em pequenas cargas de trabalho quando confrontados com o desempenho de 
uma CPU multicore atual. 
 Por fim, um outro trabalho relacionado a Aparapi utilizado como referência inclusive 
por Kristian Gupta (Gupta, 2013) em seu trabalho,