LUIZGUILHERMECASTILHOMARTINS - uel.br · 19 1 INTRODUÇÃO Diantedadificuldadedesemelhorarprocessadoressingle-coredevidoaoaltocon- sumodeenergiaeasaltastemperaturas

LUIZ GUILHERME CASTILHO MARTINS

OTIMIZAÇÃO DE CÓDIGO UTILIZANDOTÉCNICAS DE TRANSFORMAÇÃO DE LOOPS

LONDRINA–PR

2013

A todos aqueles queme apoiaram e contribuíram

para conclusão deste trabalho.

AGRADECIMENTOS

Agradeço primeiramente aos meus irmãos que estiveram por perto durante toda agraduação e meus pais que me apoiaram e incentivaram em tudo e sempre.

Professor Dr. Wesley Attrot, que propôs este tema desafiador e me motivou eincentivou durante a realização deste trabalho.

Aos amigos: Arthur Coutinho que me ajudou muito neste e em outros desafios.Beatriz que todos temem. Breno Kusunoki que sempre diz que horas são. Mateus Piveta.Clayton Kuwabara por ser mac fag. Hélio me ensiou que não está fácil nem para ela.Randal que me ajudou a corrigir este trabalho e é bobo. Ernesto que adora harumaki. Etodos os amigos que fiz durante a graduação, todas as horas de estudo e brincadeiras quetivemos juntos.

Agradeço a Bijuzinho, Gab, Morgana, Janja, Princesa Léia, e Maria, responsáveispor momentos de descontração durante a graduação.

Todos os professores que de uma forma ou outra, muito me ensinaram.

Agredeço também todos os funcionários da UEL, que no exercício de suas funções,ajudaram a tornar a graduação mais agradável.

“Say good-bye to the bad things.Say good-bye to all the times you felt lost.

To all the times it was a no instead of a yes.To all the scrapes and bruises, to all the heartache.

Say good-bye to everything you really want to do for the lasttime, because, the good things will always be there waiting for you.“

(Lily)

MARTINS, L. G. C.. Otimização de código utilizando técnicas de trans-formação de loops. 78 p. Trabalho de Conclusão de Curso (Graduação). Ba-charelado em Ciência da Computação – Universidade Estadual de Londrina,2013.

RESUMO

O objetivo deste trabalho é otimizar a computação de loops, os quais são co-nhecidos por serem responsáveis pelo maior gasto computacional de um programa.Loops com grande número de iterações sobre grandes vetores de dados, são os queapresentam grande gasto computacional e consequentemente maior chance de resul-tado na otimização. Técnicas de transformações de loops como, loop unswitching,loop fission, loop fusion, loop unrolling, entre outras, foram utilizadas para otimi-zação. A análise de dependência de dados foi utilizada para manter o significado doprograma depois das otimizações.

Palavras-chave: otimizição. tranformação de loops.

MARTINS, L. G. C.. Code otimization with loop transformations techi-niques. 78 p. Final Project (Undergraduation). Bachelor of Science in Com-puter Science – State University of Londrina, 2013.

ABSTRACT

The goal of this work is the optimization of computation of loops. Compu-tationally expensive programs in general spend most of their time in the executionof loops. Loops with a large number of iterations over a big data arrays, those arethe ones that spend of the process execution time. Thus, they are eligible to pro-duce better results after optimization. Tecniques of loop transformation such as,loop unswitching, loop fission, loop fusion, loop unrolling, among others, was usedin optimization. Analysis of data dependence was necessary to keep the meaning ofthe program after the optimizations.

Keywords: optmization. loops transformations.

LISTA DE ILUSTRAÇÕES

Figura 3.1 –Exemplo de DFG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30Figura 3.2 –Grafo de dependência do algoritmo 3.5 . . . . . . . . . . . . . . . . . . 36Figura 3.3 –Grafo de dependência do algoritmo 3.28 . . . . . . . . . . . . . . . . . 45Figura 3.4 –Grafo condensado acíclico do grafo de dependência . . . . . . . . . . . 45

—

LISTA DE TABELAS

Tabela 4.1 –Resultados das técnicas sobre o algoritmo 4.1. . . . . . . . . . . . . . . 51Tabela 4.2 –Resultados das técnicas sobre o algoritmo 4.6. . . . . . . . . . . . . . . 56Tabela 4.3 –Resultados das técnicas sobre o algoritmo 4.11. . . . . . . . . . . . . . 61Tabela 4.4 –Resultados das técnicas sobre o algoritmo 4.14. . . . . . . . . . . . . . 64Tabela 4.5 –Resultados das técnicas sobre o algoritmo 4.19. . . . . . . . . . . . . . 68Tabela 4.6 –Resultados das técnicas sobre o algoritmo 4.24. . . . . . . . . . . . . . 73Tabela 4.7 –Resultados experimentais. . . . . . . . . . . . . . . . . . . . . . . . . . 73

LISTA DE ABREVIATURAS E SIGLAS

CPU Central Processing Unit

DFG Data Flow Graph

IW Instruction Word

MISD Multiple Instruction Single Data

MIMD Multiple Instruction Multiple Data

NASA National Aeronautics and Space Administration

NOWs Network of Workstations

SISD Single Instruction Single Data

SIMD Single Instruction Multiple Data

VLIW Very Long Instruction Word

SUMÁRIO

1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2 Trabalhos Relacionados . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

3 Fundamentação Teórica . . . . . . . . . . . . . . . . . . . . . . . . . . . 233.1 Taxonomia de Flynn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

3.1.1 SISD: Single Instruction, Single Data . . . . . . . . . . . . . . . . 233.1.1.1 Processadores Escalares . . . . . . . . . . . . . . . . . . 243.1.1.2 Processadores Superescalares . . . . . . . . . . . . . . . 253.1.1.3 Processadores VLIW . . . . . . . . . . . . . . . . . . . . 25

3.1.2 SIMD: Single Instruction, Multiple Data . . . . . . . . . . . . . . 263.1.3 MISD: Multiple Instruction, Single Data . . . . . . . . . . . . . . 263.1.4 MIMD: Multiple Instruction, Multiple Data . . . . . . . . . . . . 26

3.1.4.1 Processadores Multi-Threaded . . . . . . . . . . . . . . . 273.1.4.2 Processadores Multi-Core . . . . . . . . . . . . . . . . . 27

3.2 Memória . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273.2.1 Memória Distribuída . . . . . . . . . . . . . . . . . . . . . . . . . 283.2.2 Memória Compartilhada . . . . . . . . . . . . . . . . . . . . . . . 28

3.3 Programação Paralela . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283.4 Data Flow Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293.5 Dependência . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

3.5.1 Dependência de Dados . . . . . . . . . . . . . . . . . . . . . . . . 313.5.1.1 Classificação de Load-Store . . . . . . . . . . . . . . . . 323.5.1.2 Dependência em Loops . . . . . . . . . . . . . . . . . . . 33

3.6 Reestruturação de Loops . . . . . . . . . . . . . . . . . . . . . . . . . . . 343.6.1 Transformações Simples . . . . . . . . . . . . . . . . . . . . . . . 34

3.6.1.1 Reordenação de Declarações . . . . . . . . . . . . . . . . 353.6.1.2 Unswitching . . . . . . . . . . . . . . . . . . . . . . . . . 353.6.1.3 Loop Peeling . . . . . . . . . . . . . . . . . . . . . . . . 363.6.1.4 Index Set Splitting . . . . . . . . . . . . . . . . . . . . . 383.6.1.5 Scalar Expansion . . . . . . . . . . . . . . . . . . . . . . 393.6.1.6 Loop Unrolling . . . . . . . . . . . . . . . . . . . . . . . 39

3.6.2 Loop Fusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 403.6.2.1 Complicações . . . . . . . . . . . . . . . . . . . . . . . . 42

3.6.3 Loop Fission . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 443.6.4 Loop Reversal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

3.6.5 Loop Interchanging . . . . . . . . . . . . . . . . . . . . . . . . . . 463.6.5.1 Loops Fortemente Aninhados . . . . . . . . . . . . . . . 463.6.5.2 Loops Não Fortemente Aninhados . . . . . . . . . . . . 47

4 Experimentos e Resultados . . . . . . . . . . . . . . . . . . . . . . . . . 494.1 Experimentos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

4.1.1 Experimento 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 494.1.2 Experimento 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 554.1.3 Experimento 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 604.1.4 Experimento 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 644.1.5 Experimento 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 674.1.6 Experimento 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

4.2 Resultados Experimentais . . . . . . . . . . . . . . . . . . . . . . . . . . 73

5 Conclusão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

19

1 INTRODUÇÃO

Diante da dificuldade de se melhorar processadores single-core devido ao alto con-sumo de energia e as altas temperaturas, a indústria de processadores adotou como soluçãoa esses problemas, o desenvolvimento de processadores multi-core, ou seja, processadorescom mais de um núcleo [1]. Além disso também considerou-se o poder de processamentoquando se utilizam vários processadores single-core trabalhando simultaneamente, os quaisoferecem grande desempenho, maior eficiência energética e menor custo. Porém, as aplica-ções desenvolvidas para a arquitetura single-core não se utilizam do poder computacionaldos processadores multi-core. Para que as aplicações possam usufruir do alto desempenhoque estes processadores oferecem, as aplicações devem ser divididas em múltiplas partespara que possam ser executadas em paralelo.

A paralelização de código permite ao programador resolver problemas com maioreficiência, porém projetar e codificar um programa paralelo continua sendo uma tarefadifícil, uma vez que além de dividi-lo em pequenas tarefas, deve-se considerar a concor-rência entre elas, as dependências de dados, entre outros fatores que dificultam o trabalhode paralelização [2].

Programas computacionalmente custosos, em geral gastam a maior parte do esforçona execução de ,loops, declarações de iteração que permitem que declarações sejam execu-tadas repetidamente, assim, a maior parte do ganho de eficiência será obtido otimizandoas partes do software onde há maior esforço computacional. As técnicas de reestruturaçãode loops como loop fusion, loop fission, loop peeling, entre outras, podem ser utilizadaspara otimizar loops e obter ganho de eficiência, melhorar o data locality1 e até o consumoenergético pode ser diminuído [3].

Neste contexto o objetivo deste trabalho será obter ganho de eficiência através dautilização de técnicas de reestruturação de loops e de dependências de dados aplicados aum software de equalização de áudio.

O restante deste trabalho está dividido da seguinte forma: O capítulo 2 apresentaos trabalhos relacionados; O capítulo 3 apresenta a fundamentação teória de arquiteturasparalelas, dependência de dados e das técnicas de transformações de loops; O capítulo 4é apresentado os resultados experimentais; O capítulo 5 é apresentada a conclusão sobreo trabalho.

1 A memória cache assume que se um dado é acessado uma vez este poderá ser acessado novamente embreve, esse comportamento é denominado data locality, podendo ser de dois tipos: temporal locality,se o dado é reusado e spatial locality, se o programa pode utilizar os dados próximos ao dado recémacessado, estes são também carregados na memória cache.

21

2 TRABALHOS RELACIONADOS

Nesta seção serão aprensentadas abordagens realizadas por outros autores quedesenvolveram estudo de técnicas relacionadas ao conteúdo deste trabalho.

Em "Patterns of optimized loops" [4] os autores investigam os conhecidos padrõesde paralelização de loops com características específicas. Assim como neste trabalho osautores procuram identificar em um loop determinadas características que os ajudem aidentificar quais técnicas são passíveis de serem aplicadas naquele loop.

Os autores abordam três padrões: partitioned loop pattern, tiled loop pattern ewavefront pattern. Todos estes padrões utilizam algumas das técnicas abordadas nestetrabalho. O padrão partitioned loop pattern utiliza como solução as técnicas loop indexset splitting, loop peeling. O padrão tiled loop pattern utiliza a técnica loop unrolling. Opadrão wavefront pattern utiliza a técnica loop interchange.

Não será utilizado nomenclaturas de padrões de loops paralelizáveis neste trabalho,embora, identificar características que ajudem a aplicar a melhor técnica de tranformaçãode loops será primordial para obter bons resultados.

Em "Function inlining and loop unrolling for loop acceleration in reconfigurableprocessors" [5], os autores estudam os impactos do uso de funções inline e da técnica loopunrolling na melhora de desempenho de loops para uma arquitetura específica. Emboraa arquitetura alvo dos autores não se pareça com a utilizada neste trabalho os impactosde loop unrolling, tal qual a quantidade de vezes que poderá ser aplicado, serão um dospontos que mais exigirão testes e experimentos neste trabalho para a obtenção do melhorresultado.

Técnicas de tranformação de loops apresentam comportamentos diferentes paracada arquitetura. Por apresentarem este comportamento muitas vezes empirista, a expe-riência obtida pelos autores será de suma importância, para que no final deste trabalhotenha sido encontrada a melhor forma de utilizar esta técnica.

Embora o uso de funções inline apresentem bons resultados, estas não serão utili-zadas neste trabalho, uma vez que não são técnicas de transformação de loops.

Em "Exploitation of parallelism to nested loops with dependence cyles" [6], os au-tores estudam a exploração de paralelismo de loops contendo ciclos de dependências, comfoco na quebra das relações de dependências para então extrair paralelismo destes loopscom menos ou nenhuma relação de dependência.

Os autores começam realizando uma revisão teórica, apresentando os principaisconceitos de dependência, assim como as principais relações de dependências, true-dependence,

22 Capítulo 2. Trabalhos Relacionados

output-dependence e anti-dependence. São também apresentados alguns conceitos comoloop independent dependence, loop-carried dependence, dependence distance vector, depen-dence distance matrix, inter-statement ou intra-statement dependences e direction vectormatrix de loops aninhados.

De acordo com os autores os ciclos de relações anti-dependence e true-dependencepodem ser quebradas embora true-dependence é inquebrável.

A estratégia para quebrar a relação de dependência anti-dependence apresentadase baseia no uso de uma técnica de renomeação de variáveis chamada sink. A partir da qualé criada uma variável nova que será utilizada para manter os valores daquela envolvidana relação anti-dependence. Para output-dependence o mesmo algoritmo é apresentado.

Visto que os que os ciclos de relações de true-dependence não pode ser quebrados, osautores apresentam várias técnicas que permitem amenizar as relações de dependências, oresultado deste último algoritmo é especialmente voltado para a aplicação de vetorização.

Os autores mostram que a aplicabilidade de seus algoritmos satisfizeram e manti-veram todas as relações de dependências iniciais, assim não alterando o resultado final.

Os resultados obtidos utilizando vector loops mostraram que as técnicas propostassão muito significativa em termos de speed-up, a execução dos programas tranformadosforam de 41 a 69 vezes mais rápidos em comparação a execução dos programas originais.

23

3 FUNDAMENTAÇÃO TEÓRICA

3.1 Taxonomia de Flynn

Taxonomia de Flynn, proposta em 1966 [7] por Michael Flynn e expandida em1972 [8], é uma das formas de classificar o paralelismo disponível no processador.

Taxonomia de Flynn utiliza o conceito de sequência de objetos ou ações, que sãochamados de stream. Flynn introduziu dois tipos de stream: o stream de instrução etambém o stream de dados.

O stream de instrução consiste em uma sequência de instruções. Uma instrução ouinstruction word (IW) é uma cadeia de 0’s e 1’s que representa a menor operação visívelao programador e que será executada pelo processador. Uma instrução pode conter umaou mais operações, devido a esta peculiaridade, alguns autores utilizam instruction parainstruções que contenham apenas uma operação e instruction word para instruções quecontenham mais de uma operação.

Existem, no entanto, quatro combinações de streams que descrevem as arquiteturasde computadores mais comuns [9]:

1. SISD: Single Instruction, Single Data;

2. SIMD: Single Instruction, Multiple Data;

3. MISD: Multiple Instruction, Single Data;

4. MIMD: Multiple Instruction, Multiple Data.

Cada combinação de streams caracteriza uma classe de arquitetura e cada umadestas classes possui seus tipos de paralelismo específicos.

3.1.1 SISD: Single Instruction, Single Data

A classe de arquiteturas de processadores SISD inclui a maior parte dos proces-sadores ainda em uso na data da publicação deste trabalho, os processadores single-core,embora os programadores não percebam o paralelismo inerente destes, muita concorrênciapode estar presente.

Em 1966, Flynn cita em [9] o pipeline como uma forma de se obter concorrência nosprocessadores SISD, embora Flynn considere a decodificação das inúmeras instructionscomo sendo um bottleneck, devido à tecnologia da época. Na data de publicação deste

24 Capítulo 3. Fundamentação Teórica

trabalho, grande parte dos processadores utilizam-se de pipeline assim como também seaproveitam de alguma forma de múltiplas instructions.

A concorrência em processadores SISD é explorada em tempo de execução, reali-zando mais de uma operação por ciclo de clock da máquina.

A quantidade e o tipo de paralelismo possível em processadores SISD é determi-nada por quatro fatores principais:

1. O número de operações que podem ser executadas concorrentemente;

2. A forma como as operações serão arranjadas para execução, podendo ser estatica-mente, dinamicamente ou até mesmo utilizando ambas;

3. A ordem em que as operações são colocadas e retiradas em relação a ordem originaldo programa;

4. A maneira como o processador irá tratar cada exceção, podendo ser: preciso impre-ciso ou ambos.

3.1.1.1 Processadores Escalares

Processadores escalares são processadores simples, que executam no máximo umainstrução e no máximo uma operação por ciclo de clock de máquina [1, 3.5]. As instruçõesdo stream de instruções são executadas sequencialmente, assim uma nova instrução nãoserá executada até que a execução da instrução em execução seja finalizada e seu resul-tado devidamente armazenado. A semântica de instrução determina que uma sequência deações devem ocorrer para que se obtenha o resultado esperado, sendo: buscar a instrução,decodifica-la, acessar o dado ou registrador, execução da operação e armazenar o resul-tado. Podendo ocorrer overlap entre as ações, mas o resultado deve aparecer na ordemespecificada. Esse comportamento sequencial descreve o modelo de execução sequencial.No modelo de execução sequencial, a execução é dita instruction-precise se encontrar asseguintes condições [10]:

∙ Todas as instruções ou operações que precederam a instrução atual ou operaçãoatual já foram executadas e seus resultados armazenados.

∙ Todas as instruções ou operações na fila de execução não foram executadas ou seusresultados ainda não foram armazenados.

∙ A instrução ou operação em execução no momento está em um dos estados deexecução, tendo ou não seu resultado já armazenado.

A maioria dos processadores escalares implementam diretamente o modelo de exe-cução sequencial.

3.1. Taxonomia de Flynn 25

3.1.1.2 Processadores Superescalares

Enquanto processadores escalares estão limitados a executar uma única instruçãopor ciclo de clock de máquina, os processadores superescalares decoficam várias instruçõespor ciclo de clock de máquina, utilizando várias unidades funcionais e alocação dinâmicapara executar várias instruções por ciclo de clock de máquina. Processadores superesca-lares têm um comportamento similar ao pipeline [10].

A capacidade de executar múltiplas instruções implica em verificar se existe depen-dências entre as instruções, essa verificação tem que ser feita em nível de hardware. Pro-cessadores superescalares mais avançados geralmente incluem hardwares que preservam aordem e precisamente lida com as exceções, assim simplificando o modelo de programação.

Devido à complexidade da lógica para alocação dinâmica das instruções, proces-sadores superescalares de alto desempenho, em geral, estão limitados a executarem dequatro a oito instruções por ciclo de clock de máquina.

3.1.1.3 Processadores VLIW

Processadores VLIW (Very Long Instruction Word) assim como os processadoressuperescalares decodificam inúmeras instruções por ciclo de clock de máquina e utilizamvárias unidades funcionais.

Ao contrário dos processadores superescalares que utilizam hardware para realizaralocação dinâmica das instruções, os processadores VLIW executam as instruções atravésde alocação estática, esta alocação depende de uma análise do compilador. Assim, os pro-cessadores VLIW são menos complexos e apresentam desempenho potencialmente maior[10].

Processadores VLIW apresentam grande desempenho em aplicações que podemser efetivamente alocadas de forma estática, embora nem todas as aplicações tenhamesta característica, assim, a ordem de execução estática determinada pelo compilador nãoprocede. Duas classes de execução podem ocorrer e afetar o comportamento da execuçãoestática:

1. Atrasos de resultados das operações, devido à diferença da latência ocorrida com alatência considerada durante a alocação pelo compilador;

2. Exceções ou interrupções que colocam a ordem de execução em um estado nãoantecipado pelo compilador.

O processador consegue lidar com atrasos, embora isso tenha um impacto signifi-cante no desempenho. A causa mais comum de atrasos na execução se devem ao dado nãoestar mais na memória cache, esse fator é tratado considerando-se o pior caso de latência


possível e até evitando o uso da memória cache. Na falta de paralelismo para cobrir aslacunas da latênica, resulta na alocação de instruções com um número menor de operaçõesque o processador consegue executar, assim diminuindo o desempenho [11].

3.1.2 SIMD: Single Instruction, Multiple Data

A classe de processadores SIMD incluem dois tipos de processadores, vetoriais ematriciais. Processadores SIMD são projetados para utilizarem determinadas estruturasde dados, como vetores e matrizes. Em nível de código de máquina, programar para pro-cessadores SIMD é bastante similar a processadores SISD, a diferença é realizar operaçõesnas estruturas de dados agregadas. Como no processamento de algoritmos científicos háum grande uso de vetores e matrizes, processadores SIMD têm obtido grande desempenhona área [10].

Processadores vetoriais e matriciais apresentam diferenças tanto na implementaçãoquanto na organização dos dados.

Processadores matriciais consistem em elementos de processos interconectados,cada um tendo seu próprio espaço de memória. Processadores vetoriais consistem em umúnico processo que referencia a um espaço de memória global.

3.1.3 MISD: Multiple Instruction, Single Data

A classe de processadores MISD abstratamente é um pipeline de múltiplas unidadesfuncionais operando independentemente sob um único stream de dados. Em nível de micro-arquitetura é exatamente o que os processadores vetoriais fazem [2, 2.3].

Segundo [12] exceto no caso de um cientista da computação interessado em es-tranhas formas de computação a classe MISD é uma forma restritiva e impraticável deparalelismo.

3.1.4 MIMD: Multiple Instruction, Multiple Data

Na classe de processadores MIMD estão os multiprocessadores com alguma formade interconexão entre os processadores. Do ponto de vista do programador, cada processoé executado independentemente e de forma cooperativa para solucionar um mesmo pro-blema, embora alguma forma de sincronização entre os processos é necessária para que asinformações e dados sejam trocados entre os processadores [10].

Não existem limitações em que todos os processadores sejam idênticos, embora amaioria das configurações MIMD sejam homogêneas com processadores idênticos. Con-figurações heterogêneas de processadores são geralmente utilizados para aplicações compropósitos específicos.

3.2. Memória 27

Da perspectiva do hardware existem dois tipos de MIMD, sendo os processadoresmulti-cores e processadores multi-threaded.

3.1.4.1 Processadores Multi-Threaded

Em multi-threaded MIMD, um processador base é estendido para incluir múltiplosconjuntos de registradores para dados e para o programa. Com essa configuração, dife-rentes threads ou programas ocupam cada conjunto de registrador. Assim que recursos setornam disponíveis as threads continuam sua execução [9].

Uma vez que cada thread é independente, também o é no uso dos recursos disponí-veis, assim múltiplas threads, fazem melhor uso dos recursos e em consequência aumenta-seo número de instruções executadas por ciclo de clock de máquina.

Threads ditas críticas podem ter prioridade na execução para garantir que sejamexecutadas em menor tempo, enquanto threads não críticas se utilizam de recursos ociosos.

3.1.4.2 Processadores Multi-Core

Os processadores multi-core e também os múltiplos multi-core necessitam comuni-car os resultados de suas execuções através de uma rede de intercomunicação e de controlede tarefas. Assim sua implementação é significativamente mais complexa que processado-res multi-threaded.

A rede de intercomunicação de troca de dados entre os processadores realiza asincronização das execuções independentes.

Quanto a comunicação realizada entre os processadores através de memória com-partilhada surgem dois principais problemas, manter a consistência da memória e tambéma coerência de cache. A solução para ambos os problemas se dão em técnicas de softwaree hardware [10].

3.2 Memória

A forma mais simples de se melhorar o desempenho de um sistema é replicaros computadores e criar uma forma destes trocarem dados. Dessa, forma consegue-seaumentar o desempenho sem que seja necessário alterar a CPU [13, 2.2].

Com o aumento contínuo da necessidade de desempenho em aplicações cada vezmais custosas, a maioria dos sistemas paralelos utilizam-se de uma entre duas tecnologias,memória distribuída ou memória compartilhada.


3.2.1 Memória Distribuída

Memória distribuída ou distributed memory ou shared-nothing é a mais simplesabordagem do ponto de vista de hardware. A premissa desta abordagem é utilizar várioscomputadores interligados através de uma rede.

O modelo padrão de programação consiste de processos separados para cada com-putador que se comunicam através da troca de mensagem ou message passing, o quenormalmente é feito através de bibliotecas desenvolvidas com esse propósito. Sendo este omodelo mais clássico de computação paralela. A forma moderna de sistemas com memóriadistribuída iniciou a partir do trabalho de Seitz em 1985 [14].

Devido ao baixo custo de processadores voltados ao mercado consumidor e dafácil montagem, alguns grupos exploraram tais fatores e começaram a construir clusterde computadores pessoais. Tais clusters já chamados de NOWs, Network of Workstations.Combinando todos estes fatores com o rápido avanço de desempenho de computadorespessoais e o avanço do open-source junto com versões de sistemas operacionais UNIX,ajudaram a difundir sistemas com tais caracteristicas. Hoje estes sistemas são comumenteconhecidos como Beowulfs ou Beowulf Cluster devido ao projeto de Thomas Sterling eDonald Becker realizado na NASA.

3.2.2 Memória Compartilhada

Memória compartilhada ou shared memory é uma abordagem mais complexa, tor-nando a memória visível a todos os processadores, permitindo que todos possam carregare gravar do mesmo endereço de memória [13, 2.2].

Entre as dificuldades desta abordagem, os dois que chamam mais atenção sãocoerência1 e consistência2 Sendo a consistência o mais problemático para o programador.

3.3 Programação Paralela

A programação paralela é uma camada abstrata sobre o hardware, e em geral osmodelos de programação paralela não são específicos para a arquitetura de hardware.

Existem vários modelos de programação paralela em uso na data de publicaçãodeste trabalho [1]:

a) Memória compartilhada ou shared memory (sem threads);1 Vários processadores acessando um mesmo dado compartilhado, deve-se garantir que se este for

atualizado todos os processadores passem a utilizar o dado atualizado em vez de utilizar um dadodepreciado.

2 Se um dado é manipulado por mais de um processador, a ordem de escrita e leitura deste dado entreos processadores deve ser respeitada.

3.4. Data Flow Graph 29

b) Threads;

c) Memória distribuída ou distributed memory (Troca de mensagens ou messagepassing);

d) Data parallel;

e) Híbrido;

f) SPMD (Single Program, Multiple Data);

g) MPMD (Multiple Program, Multiple Data).

3.4 Data Flow Graph

Data Flow Graph (DFG) ou grafo de fluxo de dados, é um modelo para programasque expressa a possibilidade de execução concorrente de partes do programa. Nos DFGs osnós representam operações (funções) e predicados a serem aplicados a objetos de dados e asarestas representam a ligação entre o nó que produz o dado e o nó que irá consumir aqueledado. Na literatura os nós também são chamados de atores. Assim, aspectos de controlee de dados de um programa podem ser representados em um único modelo integrado [10].

Embora muitas versões de DFGs tenham sido estudadas na literatura, elas possuemalgumas características em comum:

a) DFG é um grafo orientado em que uma aresta é um caminho que um dadopercorre do nó produtor para o nó consumidor;

b) Dinamicamente, o nó de um DFG aceita um ou mais dado como entrada,realizando computações e devolvendo os dados do retorno para suas saídas;

c) Uma ação de um nó é ativada com a presença dos dados de entrada.

Os estudos em DFGs tem sido focado principalmente em três modelos bem defi-nidos: DFGs estáticos, DFGs dinâmicos e DFGs síncronos.

Um exemplo de DFG pode ser visto na figura 3.4, onde o nó 1 é o produtor dedados para o nó 2 e 4, o nó 2 é produtor de dados para o nó 5, o nó 3 é produtor de dadospara os nós 4 e 5 e os nós 4 e 5 não são produtores, apenas consumidores. Entre as ordensde execuções que respeitem o DFG está 1, 2, 3, 4 e 5, outra execução possível é 3, 1, 4, 2e 5.

3.5 Dependência

Quando um programador escreve um programa em uma linguagem sequencial,o resultado esperado será obtido pela execução da primeira linha, depois a segunda eassim em diante, considerando exceções de controles de fluxos como loops e ramificações.


1

2

3

4

5

Figura 3.1 – Exemplo de DFG

Uma vez que o programador especificou a ordem que ele espera que as computaçõessejam realizadas. Obter paralelismo de um programa respeitando a estas especificaçõesnão é possível, uma vez que obter paralelismo implica em alterar a ordem das operaçõesrealizadas [11, 1.8].

Paralelizar um programa sequencial significa encontrar uma ordem de execuçãodiferente da especificada e que irá sempre computar o mesmo resultado. A programa-ção sequencial introduz restrições que podem ser críticas para o resultado esperado doprograma, assim como para transformar um programa em paralelo é importante encon-trar as restrições menos críticas e realizar transformações para que o programa continueretornando o resultado correto para qualquer entrada.

Uma dependência é uma relação entre duas declarações no programa. Um par dedeclarações < 1, 2 > está em uma relação se 2 é executada depois de 1 em um programasequencial, e deve ser executada após 1 em qualquer reordenação válida do programa sea ordem de acesso a memória será preservada.

1: PI = 3.141592: R = 53: AREA = PI * R * R

Os resultados obtidos por estas declarações são definidas por aqueles obtidosquando a ordem da execução realizada seja < 1, 2, 3 >. No entanto nada neste trechode código torna obrigatório a execução de 2 depois de 1, desta forma, os resultados obti-dos pela ordem de execução < 2, 1, 3 > serão os mesmos para a variável 𝐴𝑅𝐸𝐴, seja qualfor o valor da entrada. Por outro lado, o momento de execução de 3 é mais crítico, se 3for executada antes de 1 ou de 2, os resultados obtidos por esta execução diferenciariamdos resultados obtidos das computações realizadas na ordem original. Em termos de de-pendência pode-se observar que os pares < 1, 3 > e < 2, 3 > estão em uma relação de

3.5. Dependência 31

dependência, embora o par < 1, 2 > não. Dependências desse tipo são ditas dependênciade dados.

Dependência em linhas de código sequencial como visto anteriormente, é um con-ceito simples de entender. O problema é que examinar somente linhas de códigos sequên-ciais não garante eficiência em termos de paralelismo. Para se obter tal eficiência deve-seconsiderar os trechos de código que são mais executados, ou seja, devemos expandir oconceito de dependência para loops e vetores. O trecho de código a seguir ilustra a com-plexidade introduzida ao expandirmos o conceito de dependência.

1: for I = 1 to I < N do2: A(I) = B(I) + 13: B(I + 1) = A(I) - 54: end for

Este loop mostra a dependência entre < 2, 3 >, uma vez que o resultado computadode 𝐴 é imediatamente utilizando por 3 em todas as iterações, e também a dependêndiaentre < 3, 2 > exceto na primeira iteração, uma vez que o resultado obtido por 3 seráutilizado na iteração anterior. Detectar estas dependências é difícil, considerando que cadaiteração acessa diferentes elementos do vetor.

Loops e vetores são apenas parte do problema que envolve a análise de dependência,deve-se considerar também as estruturas condicionais, como as declarações 𝐼𝐹 .

Deve-se então entender um outro tipo de dependência, dado o trecho de código aseguir:

1: if D = 0 then2: A = A / D3: end if

A declaração 2 não pode ser executada antes de 1, uma vez que essa transformaçãopode ocasionar em uma divisão por zero, o que não ocorreria no programa original. Essadependência é chamada de dependência de controle.

3.5.1 Dependência de Dados

Em dependência de dados deve-se garantir que um dado seja produzido e consu-mido na ordem correta, assim, cuidando para que não se intercale o load e o store em ummesmo local da memória, desta forma, o próximo load pode obter um valor errado. Damesma forma, dois stores devem ocorrer na ordem correta para que no próximo load sejaobtido o valor correto. Assim, dependência de dados pode ser definida como [11, 2.2]:

Definição 1: Existe dependência de dados da declaração 1 para a declaração 2 (decla-ração 2 depende da declaração 1) se e somente se:


1. Ambas as declarações acessem o mesmo local de memória e ao menos umasdelas realizará store na memória, e

2. Existe um caminho de execução possível3 de 1 para 2.

Neste capítulo serão apresentadas várias propriedades onde as dependências podemser classificadas.

3.5.1.1 Classificação de Load-Store

Em termos da ordem de load-store, as dependências podem ocorrer de três formasem um programa [6]:

a) True dependence ou flow dependence. Uma declaração realiza store em umlocal da memória em que será realizado um load por uma segunda declara-ção.

1: foo = . . .2: . . . = foo

A dependência garante que 2 irá ler exatamente o que foi computado por 1.Esse tipo de dependência é também conhecida por dependência de fluxo e édenotada por 1 𝛿 2 ou 1 𝛿𝑓 2 (lê-se, 2 depende de 1).

b) Anti-dependence. Uma primeira declaração realiza load de um local onde umasegunda declaração irá escrever.

1: . . . = foo2: foo = . . .

Esta dependência previne a troca na ordem de execução entre 1 e 2, tal qualpoderia resultar em 1 utilizando-se do valor computado por 2. Em essênciaessa dependência existe para prevenir uma transformação que introduziria umanova dependência do tipo true dependence que de fato não existe no programaoriginal. Anti-dependence é denotado 1 𝛿− 2, 1 𝛿−1 2 ou 1 𝛿𝑎 2.

c) Output dependence. Ocorre quando duas declaração realizam store em ummesmo local.

1: foo = . . .2: foo = . . .

Essa dependência previne que ocorra uma troca entre as declarações e faça comque uma declaração que irá realizar load do valor computado não leia o valorerrado.

1: foo = 13 O caminho para a execução destas declações deve ser factível durante a execução.

3.5. Dependência 33

2: . . .3: foo = 24: bar = 2 * foo

Output dependence é denotado 1 𝛿0 2 ou 1 𝛿𝑜 2.

3.5.1.2 Dependência em Loops

Estendendo o conceito de dependência para loops requer alguma forma de para-metrizar as declarações pelas iterações do loop que são executadas. Para o loop simplesdo algoritmo 3.1:

1: for I = 1 to I < N do2: A(I + 1) = A(I) + B(I)3: end for

Algoritmo 3.1: Loop simples

A declaração 2 em qualquer iteração do loop depende dela mesmo da iteraçãoanterior. Embora uma simples alteração no index do vetor pode fazer com que a declaraçãotenha dependência de duas iterações anteriores. Ver algoritmo 3.2.

1: for I = 1 to I < N do2: A(I + 2) = A(I) + B(I)3: end for

Algoritmo 3.2: Loop simples com dependência de duas iterações

Para melhor definir dependências em loops, pode se fazer necessário o uso dealguma forma de parametrização das declarações, para que através desta representaçãoseja possível identificar em qual iteração as declarações ocorrem. Para isso faz-se necessárioo uso de números inteiros auxiliares (ou um vetor de números inteiros), os quais irãorepresentar o número da iteração de cada loop onde as declaração estão aninhadas [15].Para o loop simples do algoritmo 3.3

1: for I = 1 to I < N do2: . . .3: end for

Algoritmo 3.3: Loop simples

o número da iteração é igual ao número do loop index, neste caso o 𝐼. O indexinicia em 1 na primeira iteração, assumindo o valor 2 na segunda iteração e assim pordiante.

Considerando o loop parametrizado do algoritmo 3.4

o número da iteração será 1 quando 𝑖 for igual a 𝐿, será 2 quando 𝐼 for igual a 𝐿 + 𝑆 eassim em diante. Formalizando-se o conceito de parametrização [11, 2.2];


1: for I = L to I < U with I = I + S do2: . . .3: end for

Algoritmo 3.4: Loop parametrizado

Definição 2: Para um loop arbitrário em que o index 𝐼 do loop é incrementado de 𝐿

até 𝑈 em incrementos de 𝑆, o número da iteração (normalizado) 𝑖 de uma iteraçãoqualquer terá o valor de (𝐼 − 𝐿 + 1)/𝑆, onde 𝐼 é o valor do index daquela iteração.

No caso de loops aninhados, o nível de aninhamento de um determinado loop seráigual ao número de loops que estão iterando sobre ele somado de um. Em aninhamentode loops os mesmo serão enumerados do mais externo para o mais interno, começando em1. Formalizando-se este conceito tem-se [11, 2.2];

Definição 3: Para um aninhamento de 𝑛 loops, o vetor de iteração 𝑖 de uma determinadaiteração no loop mais interno é um vetor de inteiros que contém o número da iteraçãode cada loop na ordem do aninhamento. O vetor de iterações é dado pela seguinteequação 𝑖 = 𝑖1, 𝑖2, . . . , 𝑖𝑛 onde 𝑖𝑘, 1 ≤ 𝑘 ≤ 𝑛, representa o número da iteração dok-ésimo loop aninhado.

Considerando-se um aninhamento de dois loops e o vetor de iteração 𝑖𝑡_𝑎𝑟𝑟𝑎𝑦[2],onde 𝑖𝑡_𝑎𝑟𝑟𝑎𝑦[0] contém o número da iteração do loop mais externo e 𝑖𝑡_𝑎𝑟𝑟𝑎𝑦[1] doloop mais interno. O conjunto de todas as possibilidades do vetor de iteração é chamadode espaço de iteração (iteration space). O espaço de iteração para este aninhamento seria{(1, 1), (1, 2), (2, 1), (2, 2)}.

Devido a importância da ordem de execução para tratamento de dependência,vetores de iteração precisam ser precisos quanto a ordem dos seus elementos internos emrelação a ordem de aninhamento dos loops.

3.6 Reestruturação de Loops

Na otimização do desempenho de um programa, os maiores ganhos serão obtidosdas regiões do programa onde gasta-se a mais tempo; as regiões repetitivas do programa[6] Essas correspondem por loops iterativos ou funções recursivas. O foco maior destetrabalho serão os loops contáveis, aqueles em que é possível determinar a quantidade deexecuções sem que seja necessário executa-los.

3.6.1 Transformações Simples

Serão apresentadas algumas transformações simples em loops que também serãoutilizadas em outras técnicas apresentadas nesta seção.

3.6. Reestruturação de Loops 35

3.6.1.1 Reordenação de Declarações

A reordenação pode ser realizada sobre qualquer granularidade, operação, decla-ração ou sequência de declarações. Será utilizado um grafo de controle aciclico (CFG)ou grafo de dependência. Um nó do grafo pode representar uma declaração ou um loopinteiro. A reordenação é considerada válida desde que respeite a dependência de dados,ou seja, não altere o significado do programa [15, 9.1].

Está técnica pode ser utilizada para vários propósitos, para amortizar a latência damemória, melhorar o data locality movendo declarações ou loops que utilizam as mesmasvariáveis próximas uma das outras [16].

A reordenação de declarações é útil, pois através dela é possível a aplicação deoutras técnicas.

Utilizando o algoritmo 3.5 para exemplificar a reordenação.

1: A(1) = 02: B(1) = 03: if C > 0 then4: A(2) = 15: B(2) = 96: end if7: for I = 3 to 9 do8: A(I) = A(I - 2) + A(I - 1) * 29: B(I) = B(I - 2) * 2 + B(I - 1)

10: end forAlgoritmo 3.5: Exemplo de algoritmo a ser reordenado

O grafo de dependência do algoritmo 3.5 pode ser visto na figura 3.6.1.1. Nesteexemplo deseja-se que as declarações 1 e 4 fiquem o mais próximo possível do loop. Umaforma de faze-lo é reordenando as declarações para a seguinte ordem 2, 3, 5, 1, 4 𝑒 7,como resultado tem-se o algoritmo 3.6.

3.6.1.2 Unswitching

Unswitching é uma transformação simples que retira do loop uma condição queindepende do loop. Unswitching trata um loop que tenha uma condição e faz com que acondição envolva um ou dois loops. A condição deve obrigatoriamente ser independentedo loop. A vantagem do uso do unswitching é a redução da frequência de execução dacondição, uma vez que fora retirada do loop. A desvantagem é o aumento da complexidadeda estrutura do loop, um loop contendo apenas um loop mais interno, poderá ter dois oumais loops internos. Essa desvantagem pode afetar a aplicabilidade de outras técnicas outransformações [17] [18].


1

2

3

4

5

7

Figura 3.2 – Grafo de dependência do algoritmo 3.5

1: B(1) = 02: Test = C > 03: if Test then4: B(2) = 95: end if6: A(1) = 07: if Test then8: A(2) = 19: end if

10: for I = 3 to 9 do11: A(I) = A(I - 2) + A(I - 1) * 212: B(I) = B(I - 2) * 2 + B(I - 1)13: end for

Algoritmo 3.6: Algoritmo 3.5 após a reordenação

Unswitching pode ser aplicado em um loop semelhante ao algoritmo 3.7, onde acondição é independente do loop.

O algoritmo 3.7 pode ser transformado no algoritmo 3.8.

Considerando o algoritmo 3.9 por apresentar um loop mais interno.

Aplicando-se unswitching no algoritmo 3.9 será removida a condição do loop maisinterno, ver algoritmo 3.10.

3.6.1.3 Loop Peeling

Loop peeling remove a primeira ou a ultima iteração do loop colocando-a em códigoseparado, podendo ser generalizado e realizado mais de uma vez se necessário. Essa técnica


1: loop2: declarações3: if teste then4: declarações de then5: else6: declarações de else7: end if8: mais declarações9: end loop

Algoritmo 3.7: Algoritmo onde a condição independe do loop

1: if teste then2: loop3: declarações4: declarações de then5: mais declarações6: end loop7: else8: loop9: declarações

10: declarações de else11: mais declarações12: end loop13: end if

Algoritmo 3.8: Algoritmo 3.7 depois de aplicar unswitching

1: for I = 1 to N do2: for J = 2 to N do3: if T(I) > 0 then4: A(I,J) = A(I, J - 1) * T(I) + B(J)5: else6: A(I,J) = 0 07: end if8: end for9: end for

Algoritmo 3.9: Algoritmo com loops aninhados

1: for I = 1 to N do2: if T(I) > 0 then3: for J = 2 to N do4: A(I,J) = A(I, J - 1) * T(I) + B(J)5: end for6: else7: for J = 2 to N do8: A(I,J) = 0 09: end for

10: end if11: end for

Algoritmo 3.10: Algoritmo 3.9 depois de unswitching


depente de saber se a variável de controle da iteração (index) é estritamente positiva,caso não o seja, deve-se proteger o código com uma condição maior que zero. Loop peelingtambém pode ser utilizado para retirar partes de código que não dependem do index doloop, assim, executando-os apenas uma vez [19].

Loop peeling também pode ser utilizado para ajustar a variação do index do loop,assim tornando possível a aplicação do loop fusion. Loop peeling não apresenta vantagenssignificativas no ganho de desempenho, sendo este ganho obtido pelas técnicas a seremaplicadas após o loop peeling.

Considerando o algoritmo 3.11 um loop contável e com index tendo como máximo𝑀𝐴𝑋.

1: calcula MAX2: for I = 0 to MAX - 1 do3: corpo do loop4: end for

Algoritmo 3.11: Algoritmo com loop contável

Aplicando loop peeling no algoritmo 3.11 um resultado possível seria o algoritmo 3.12.

1: calcula MAX2: if MAX > 0 then3: I = 04: corpo do loop5: for I = 1 to MAX - 1 do6: corpo do loop7: end for8: end if

Algoritmo 3.12: Algoritmo 3.11 depois de loop peeling

3.6.1.4 Index Set Splitting

Index set splitting ou loop splitting é uma generalização de loop peeling. Essa técnicadivide o index set de um loop em duas partes, replicando o corpo do loop apropriadamente.Assim como em loop peeling essa técnica é útil para ajustar o percurso do loop, ou pararemover condições que testam a variável que controla as iterações do loop [17] [4].

Considerando o algoritmo 3.13 com um loop com percurso indo até 𝑀𝐴𝑋.

1: calcula MAX2: for I = 0 to MAX - 1 do3: corpo do loop4: end for

Algoritmo 3.13: Algoritmo com um loop de percurso até 𝑀𝐴𝑋

Aplicando index set splitting em 3.13 na iteração 𝑊 resultaria no algoritmo 3.14.


1: calcula MAX2: for I = 0 to W - 1 do3: corpo do loop4: end for5: for I = S to MAX - 1 do6: corpo do loop7: end for

Algoritmo 3.14: Algoritmo 3.13 depois de index set splitting

3.6.1.5 Scalar Expansion

Uma vez que escalares são atribuídos e depois utilizados no loop, o grafo de de-pendência irá incluir relações de dependência de fluxo da atribuição para cada uso, oloop terá relações de anti-dependence. Esta dependência pode causar problemas ao tentaraplicar outras transformações. As relações de dependências podem ser quebradas atra-vés de expanding ou promoting, colocando o escalar em um vetor. Considerando apenasloops contáveis e com o escalar não tendo uso anterior ao loop. Neste caso alocando-seum vetor com o tamanho do percurso do loop e trocando a referência de cada iteraçãopara sua respectiva posição no vetor irá satisfazer as relações de dependências. Com cadaiteração do loop utilizando uma posição do vetor a anti-dependence e output dependencesão eliminadas [20].

O uso de scalar expansion em loops aninhados é possível, embora o tamanho dopercurso do loop possa ser proibitivo.

Após o final do loop deve ser atribuído ao escalar o seu valor correto, ou se consta-tado que o escalar não mais será utilizado após o loop, então basta desconsidera-lo. Casoo valor do escalar seja determinado condicionalmente dentro do loop invibializaria o usode scalar expansion exceto se o mesmo não será mais utilizado após o loop.

Tendo o algoritmo 3.15 com escalar 𝐸.

1: for I = 0 to N do2: E = A(I) + B(I)3: C(I) = E + 1/E4: end for

Algoritmo 3.15: Algoritmo contendo um escalar

Aplicando scalar expansion no algoritmo 3.15 e protegendo-o com uma condiçãomaior que zero, irá eliminar todas as relações de dependências, o resultado é o algo-ritmo 3.16

3.6.1.6 Loop Unrolling

A técnica loop unrolling baseia-se em duplicar o corpo do loop 𝑛 vezes, fazendocom que o número de iterações seja menor, no caso 𝑛 vezes menor. Com isso, aproveitando


1: if N >= 0 then2: alloc Ex(1:N)3: for I = 0 to N do4: Ex(I) = A(I) + B(I)5: C(I) = Ex(I) + 1/Ex(I)6: end for7: E = Ex(N)8: end if

Algoritmo 3.16: Algoritmo 3.15 após o scalar expansion

possíveis melhorias que possam existir durante as iterações, entre elas a diminuição donúmero de vezes em que será necessário realizar a comparação da condição de saída doloop. Com a duplicação do corpo do loop e com isso o incremento a cada iteração, se ovalor máximo de iteração não for par deverá então ser adicionando um tratamento paraevitar que a ultima iteração seja realizada [21].

Loop unrolling irá aumentar o número de linhas do código com isso dificultandoa leitura do mesmo. Considerando o algoritmo 3.17 e aplicando loop unrolling apenasduplicando uma vez, tem-se como resultado o algoritmo 3.18.

1: for I = 0 to N do2: A(I) = B(I)3: end for

Algoritmo 3.17: Loop simples com N par

1: for I = 0 to N by 2 do2: A(I) = B(I)3: A(I + 1) = B(I + 1)4: end for

Algoritmo 3.18: Algoritmo 3.17 após loop unrolling

3.6.2 Loop Fusion

Se dois loops são adjacentes e possuem o mesmo limite, algumas vezes podem seragrupados em um loop simples. Originalmente, esta técnica fora desenvolvida como umaforma de reduzir os custos de testes e ramificações no código [20].

Sem os conceitos de dependências de dados, as descrições anteriores de loop fusioneram restritas a loops livres de dependências de dados.

O desenvolvimento de deep memory hierarchies fez com que esta técnica fosseimportante para aproveitar o memory locality. Utilizando loop fusion em loops que refe-renciam os mesmos dados melhoram o temporal locality, podendo assim impactar signifi-cativamente o desempenho da memória cache e da memória virtual. Outra vantagem do


uso de loop fusion é tirar vantagem de otimizações escalares mais eficiêntes no corpo doloop, uma vez que o mesmo ficou maior após o seu uso [16] [22].

No algoritmo 3.19 tem-se dois loops adjacentes com limites compatíveis. O algo-ritmo 3.20 mostra o resultado da aplicação do loop fusion.

1: for I = 0 to N do2: corpo do loop 13: end for4: for I = 0 to N do5: corpo do loop 26: end for

Algoritmo 3.19: Algoritmo com dois loops adjacentes

1: for I = 0 to N do2: corpo do loop 13: corpo do loop 24: end for

Algoritmo 3.20: Algoritmo 3.19 após loop fusion

O uso de loop fusion será considerada válida se toda dependência de dados forpreservada. Após a aplicação do loop fusion todas as relações de dependências devemseguir o fluxo original do "corpo do loop 1"para o "corpo do loop 2".

Em alguns casos unir loops adjacentes podem ocasionar em violação na dependên-cia de dados, se um loop tem dependência sobre os dados do outro. Considere os loops doalgoritmo 3.21.

1: for I = 0 to N do2: A(I) = B(I) + 13: end for4: for I = 0 to N do5: C(I) = A(I) / 26: end for7: for I = 0 to N do8: D(I) = 1 / C(I + 1)9: end for

Algoritmo 3.21: Algoritmo com três loops adjacentes

Uma aplicação ingênua do loop fusion no algoritmo 3.21 resultaria no algoritmo 3.22que viola as regras básicas de dependência. Considerando o algoritmo 3.21 existem doistipos dependência de dados, sendo uma depêndencia do tipo true dependence ou flow de-pendence na relação 2 𝛿𝑓 5 e outra entre 5 𝛿𝑓 8, o segundo tipo de dependência é do tipoanti-dependence na relação 8 𝛿𝑎 5, essa dependência fica mais evidente quando observadoo algoritmo 3.22, uma vez que a união dos loops causa a violação desta dependência.


Pode-se então observar que o uso não adequado do loop fusion violaria as regras dedependências e assim alterando o sentido do programa. Uma aplicação correta da técnicano algoritmo 3.21 e seu resultado pode ser observado no algoritmo 3.23.

1: for I = 0 to N do2: A(I) = B(I) + 13: C(I) = A(I) / 24: D(I) = 1 / C(I + 1)5: end forAlgoritmo 3.22: Violação da dependência de dados do algoritmo 3.21 após loop fusion

1: for I = 0 to N do2: A(I) = B(I) + 13: C(I) = A(I) / 24: end for5: for I = 0 to N do6: D(I) = 1 / C(I + 1)7: end forAlgoritmo 3.23: Resultado de uma correta aplicação de loop fusion no algoritmo 3.21

3.6.2.1 Complicações

Uma vez que loop fusion requer que dois loops sejam compatíveis um com o ou-tro para, ou seja, tenham o mesmo número de iterações, sejam adjacentes e tenham amesma varíavel de iteração. Todas estas condições devem ser satisfeitas para que possaser aplicado o loop fusion [20].

No caso de algumas das condições ou todas não estejam satisfeitas mas ainda assimdeseja-se aplicar o loop fusion, então será necessária a utilização de transformações nosloops para que fiquem compatíveis.

Para loops com diferentes limites de percurso, deve-se considerar a aplicação de looppeeling ou index set splitting para arrajar os limites entre eles ou mesmo incluir declaraçõescondicionais para protejer o código em algumas iterações. Ambas as alternativas possuemdesvantagens, se utilizado loop peeling ou index set splitting irá adicionar mais código comum loop extra, mesmo que pequeno. Se adicionar uma declaração condicional dentro doloop deve-se considerar o overhead sobre o teste condicional [15].

Se os loops não forem adjacentes, será então necessário reordenar as delcaraçõespara que se tornem adjacentes.

Uma complicação extra pode ocorrer caso existam escalares atribuídos em algumdos loops, assim será necessário garantir que após o loop possuam o valor correto.

Considerando o algoritmo 3.24, nota-se que os loops já são adjacentes e também sãocontáveis, mas o primeiro loop possui uma iteração a mais que o segundo. Para corrigir


essa iteração a mais pode ser retirado uma das iterações do primeiro loop utilizandoloop peeling, assim teríamos como resultado o algoritmo 3.25. Para aplicar loop fusion noalgoritmo 3.25 deverá ser criada uma variável 𝑋 que controle devidamente o valor de 𝐼, queserá utilizada como variável de controle do loop. Como resultado tem-se o algoritmo 3.26.

1: for I = 1 to 99 do2: A(I) = B(I) + 13: end for4: for I = 1 to 98 do5: C(I) = A[I + 1] * 26: end for

Algoritmo 3.24: Algoritmo com dois loops adjacentes e contáveis

1: I = 12: A(I) = B(I) + 13: for I = 2 to 98 do4: A(I) = B(I) + 15: end for6: for I = 1 to 98 do7: C(I) = A[I + 1] * 28: end for

Algoritmo 3.25: Resultado de loop peeling no algoritmo 3.24

1: I = 12: A(I) = B(I) + 13: for X = 0 to 97 do4: I = X + 25: A(I) = B(I) + 16: I = X + 17: C(I) = A[I + 1] * 28: end for

Algoritmo 3.26: Resultado de loop fusion no algoritmo 3.24

Um exemplo de loops que não se pode aplicar loop fusion pode ser visto no algo-ritmo 3.27, uma vez que o escalar 𝐷 é atribuído no primeiro loop e utilizado no segundo.

1: for I = 0 to 100 do2: D = A(I)3: B(I) = D4: end for5: for J = 0 to 100 do6: C(J) = C(J) + D7: end for

Algoritmo 3.27: Exemplo de loops que não podem ser unidos


3.6.3 Loop Fission

Um loop simples pode ser quebrado em dois ou mais loops menores, isso é o inversode loop fusion, essa técnica é chamada de loop fission ou loop distribution. Loop fissioné muito utilizada em máquinas com instruction cache menores, esta técnica pode serutilizada para quebrar grandes loops que não seriam suportados pela cache em loopsmenores que caibam na cache. Podendo também melhorar a memory locality em casosonde um único loop utiliza vários vetores, assim dividindo estes vetores entre mais de umloop [15].

Quando um loop é dividido, o index ou induction variable será utilizado em cadaparte do loop. Para evitar problemas em saber quando a induction variable será atualizada,pode ser criada uma nova variável que a substitua, assim trocando todas as referênciaspor esta nova variável.

Antes de aplicar esta técnica, primeiro será construído um grafo de dependênciaem nível das declarações do loop. Caso não haja ciclos no grafo de dependência, então oloop poderá ser divido em cada nó do grafo. Em caso de ciclos no grafo, então a abordagemnão poderá ser a mesma, pois violaria a dependência de dados, logo, se dois nós formamum ciclo no grafo, eles podem ser unidos em um único nó, pois não será possível separa-los.Se o grafo de dependência for fortemente conectado, então a não será possível a aplicaçãode loop fission.

A ordem correta dos loops após o loop fission pode ser encontrada através de umgrafo acíclico condensado do grafo de dependência. Sendo cada nó no grafo condensadoum loop.

Considerando o algoritmo 3.28 com quatro declarações em seu corpo e quatrovetores, o grafo de dependência pode ser visto na figura 3.6.3. Como pode-se observar nografo de dependência, existe um ciclo entre as linhas 3 e 4, sendo assim, não será possívelsepará-las em diferentes loops, também existe uma dependência entre a linha 2 com alinha 3 e da linha 5 com a 4. O grafo condensado na figura 3.6.3 mostra a ordem emque os loops devem estar. O algoritmo 3.29 mostra o resultado de loop fission sobre oalgoritmo 3.28.

1: for I = 1 to N do2: A(I) = A(I) + B(I - 1)3: B(I) = C(I - 1) * X + C4: C(I) = 1 / B(I)5: D(I) = sqrt(C(I))6: end for

Algoritmo 3.28: Algoritmo em que ser quer aplicar loop fission


2

3

4

5

Figura 3.3 – Grafo de dependência do algoritmo 3.28

3-4

2 5

Figura 3.4 – Grafo condensado acíclico do grafo de dependência

1: for I = 0 to N - 1 do2: B(I + 1) = C(I) * X + C3: C(I + 1) = 1 / B(I + 1)4: end for5: for I = 0 to N - 1 do6: A(I + 1) = A(I + 1) + B(I)7: end for8: for I = 0 to N - 1 do9: D(I + 1) = sqrt(C(I + 1))

10: end for11: I = I + 1

Algoritmo 3.29: Resultado de loop fission sobre o algoritmo 3.28

3.6.4 Loop Reversal

Algumas vezes pode-se desejar que um loop intere de trás para frente, ou seja, dofinal do percurso do loop para o início, e isso é chamado de loop reversal. Caso existe umarelação de dependência, essa relação muda de sentido devido ao decrescimento do índicedo loop, com isso violando a relação de dependência [15].

Um uso para esta técnica é permitir o uso de loop fusion onde antes não erapermitido. Considere o algoritmo 3.21, onde a fusão de três loops resultou em dois loops,ver algoritmo 3.23. Aplicando loop reversal pode-se obter apenas um loop como resultado,algoritmo 3.30.


1: for I = N downto 0 do2: A(I) = B(I) + 13: C(I) = A(I) / 24: D(I) = 1 / C(I + 1)5: end for

Algoritmo 3.30: Resultado da aplicação de loop reversal e loop fusion no algoritmo 3.23

3.6.5 Loop Interchanging

Loop interchanging talvez seja a mais importante técnica de reestruturação deloops. Esta técnica resume-se em loops que estejam fortemente aninhados serem trocadosde posição, o loop mais externo é trocado pelo mais interno. No caso de apenas um loopcarregar todas as dependências, este pode ser trocado de posição e se tornar o loop maisexterno, assim, os outros loops podem ser executados em paralelo [17].

Loop interchanging tem sido utilizado para melhorar o desempenho de um pro-grama. Um loop mais externo com um número maior de iterações e o loop mais internocom apenas algumas iterações, em um cenário como este haverá loop startup overheadsobre o loop mais interno, trocando-os de posição, a ocorrência de loop startup overheadserá de apenas algumas vezes [23].

3.6.5.1 Loops Fortemente Aninhados

Dois loops estão fortemente aninhados quando o único código no corpo do loopmais externo for o loop mais interno. Para loops contáveis, com percurso do loop maisinterno não dependendo da iteração do loop mais externo, aplicar loop interchanging seráapenas troca-los de posição. Ao aplicar loop interchanging no algoritmo 3.31 seria obtidoo algoritmo 3.32 como resultado [15].

1: for I = do2: for J = do3: corpo do loop4: end for5: end for

Algoritmo 3.31: Dois loops fortemente aninhados

1: for J = do2: for I = do3: corpo do loop4: end for5: end for

Algoritmo 3.32: Resultado de loop interchanging no algoritmo 3.31

Assim como em todas as técnicas de reestruturação de loops, deve-se atentar empreservar as relações de dependência entre os loops. Se toda dependência for preservada e


o sentido do programa se mantiver, então, o resultado do loop interchanging será sempreválido.

3.6.5.2 Loops Não Fortemente Aninhados

Loops não fortemente aninhados, ao contrário do fortemente aninhado, o loop maisexterno tem mais declaração em seu corpo do que apenas o loop interno. As vezes é possíveltransformar loops não fortemente aninhados em fortemente aninhados utilizando-se loopfission. Algumas vezes isto pode não ser possível, então outra forma de faze-lo seria colocarestas declarações do loop mais externo dentro do corpo do loop mais interno, utilizando-se de declarações condicionais para ajustar em qual iteração devem ser executadas. Umajuste possível seria executa-las quando o index dos loops forem iguais, outro ajuste seriaa criação de uma nova iteração no início ou fim para executa-las [15].

Utilizando o ajuste condicional de igualdade do index com mesmo limite de per-curso aplicada ao algoritmo 3.33, resultaria no algoritmo 3.34.

1: for I = 1 to N do2: corpo do loop externo3: for J = 1 to N do4: corpo do loop interno5: end for6: end for

Algoritmo 3.33: Dois loops não fortemente aninhados

1: for J = 1 to N do2: for I = 1 to N do3: if I == J then4: corpo do loop externo5: else6: corpo do loop interno7: end if8: end for9: end for

Algoritmo 3.34: Resultado de loop interchanging no algoritmo 3.33

49

4 EXPERIMENTOS E RESULTADOS

Este capítulo apresenta os resultado obtidos na aplicação das técnicas de transfor-mação de loops e também os experimentos realizados.

Para a realização dos experimentos foi escolhido o programa wat1, que é um equa-lizador de áudio de 1 e 2 canais.

Á escolha do wat foi motivada pelo fato de ser compatível com arquivos compostosde grandes vetores de dados. Arquivos de áudio apresentam essa composição. Sobre essesvetores são iterados loops uma grande quantidade de vezes. Isso permite que se ganhedesempenho aplicando modificações sobre os loops do wat. Tal ganho de desempenhoresulta em uma equalização mais rápida.

Os experimentos realizados foram executados em uma máquina com as seguintesconfiguração: processador, Intel Core 2 Duo, 2.4 GHz, memória 4 GB 1064 MHz DD3 eHD 256 GB Solid State SATA Drive.

Para compilação dos resultados, foram realizados dez medições de tempo e entãofeita a média geométrica destes tempos.

4.1 Experimentos

Nesta seção serão apresentados os testes e experimentos realizados sobre os loopsextraídos de wat, assim como seus resultados individuais.

4.1.1 Experimento 1

Analisando o loop do algoritmo 4.1 o qual transforma dois bytes em um double.

1 https://github.com/luizguilhermecm/wat

50 Capítulo 4. Experimentos e Resultados

1 int it = i = 0;

2 while (it < wi ->wav_header -> subchunk2_size ){

3 wi -> left_side [i] = bytes_to_double ( buffer [it],

4 buffer [it + 1]);

5 wi -> zero_data [i] = 0;

6 it += 2;

7 if(wi ->wav_header -> num_channels == 2){

8 wi -> right_side [i] = bytes_to_double ( buffer [it],

9 buffer [it + 1]);

10 it +=2;

11 }

12 i++;

13 }

Algoritmo 4.1: Loop extraído do wat.

Devido a existência de uma declaração if no corpo do loop e sendo este if inde-pendente do loop, foi aplicado a técnica loop unswitching, que retira a comparação if docorpo do loop envolvendo um novo loop para cada caso da comparação, assim nenhum dosloops terão declações de comparação em seu corpo. O algoritmo 4.2 mostra o resultadodo algoritmo 4.1 após a alteração com o uso de loop unswitching.

Considerando o algoritmo 4.2 será aplicado a técnica loop unroll com o intuitode diminuir o número de iterações e consequentemente a quantidade de comparaçõesrealizadas no loop em duas vezes. O algoritmo 4.3 mostra o resultado do loop unrollduplicando o corpo do loop.

Considerando o algoritmo 4.2 onde o primeiro loop itera sobre dois vetores e osegundo loop itera sobre três vetores, será aplicado loop fission dividindo-os de forma quecada loop itere somente sobre um vetor. O algoritmo 4.4 mostra o resultado de loop fissionno algoritmo 4.2.

O algoritmo 4.4 apresenta cinco loops, cada um iterando sobre um vetor. Seráaplicado loop unrolling dobrando o corpo de cada um dos loops para que o número deiterações seja dividido por dois. O algoritmo 4.5 mostra o resultado de loop unrolling noalgoritmo 4.4.

A tabela 4.1.1 apresenta os resultados obtidos sobre o algoritmo 4.1. O algo-ritmo 4.3 obteve o melhor desempenho, embora a melhora do algoritmo 4.2 seja seme-lhante. Logo, o custo de computação da função bytes_to_double é o mais significativodeste loop, fazendo com que a diminuição das comparações não obtivesse resultado signi-ficativo, apenas aumentando a quantidade de dados a ser acessada a cada iteração. Umasolução é apresentada em [5], onde o autor propõe utilizar funções inline com o intuito

4.1. Experimentos 51

de diminuir o custo de acesso à função.

O algoritmo 4.4 obteve resultado negativo em seu desempenho, aumentando em 31ms no tempo da computação. Este é um indício de que a quantidade de dados acessados acada iteração não é o suficiente para suprir a quantidade de dados suportada pela memoriacache e instruction cache. O uso de loop unrolling no algoritmo 4.4 fez com que aumentassea quantidade de dados acessados por iteração, assim, melhorando seu desempenho, masainda sendo maior que o algoritmo retirado de wat.

Algoritmo Técnicas aplicadas Tempo de execuçãoAlgoritmo 4.1 nenhuma 470 msAlgoritmo 4.2 loop unswitching 448 msAlgoritmo 4.3 loop unswitching, loop unroll 444 msAlgoritmo 4.4 loop unswitching, loop fission 501 msAlgoritmo 4.5 loop unswitching, loop fisson, loop unroll 480 ms

Tabela 4.1 – Resultados das técnicas sobre o algoritmo 4.1.

1 i = it = 0;




5 buffer [it + 1]);


7 it += 2;

8 i++;

9 }

10 }

11 else if(wi ->wav_header -> num_channels == 2){



14 buffer [it + 1]);


16 it += 2;



19 it +=2;

20 i++;

21 }

22 }

Algoritmo 4.2: Loop unswitching no algoritmo 4.1.


1 int it = i = 0;




5 buffer [it + 1]);


7 it += 2;

8 i++;




12 it += 2;

13 i++;

14 }

15 }






21 it += 2;



24 it +=2;

25 i++;




29 it += 2;



32 it +=2;

33 i++;

34 }

35 }

Algoritmo 4.3: Loop unroll no algoritmo 4.2.


1 i = it = 0;




5 buffer [it + 1]);

6 it += 2;

7 i++;

8 }



11 it += 2;

12 i++;

13 }

14 }




18 it += 4;

19 i++;

20 }




24 it += 4;

25 }

26 i = 0; it = 2;




30 it += 4;

31 i++;

32 }

33 }

Algoritmo 4.4: Loop fission no algoritmo 4.2.


1 i = i t = 0 ;2 i f ( wi−>wav_header−>num_channels == 1){3 while ( i t < wi−>wav_header−>subchunk2_size ){4 wi−>l e f t _ s i d e [ i ] = bytes_to_double ( b u f f e r [ i t ] ,5 b u f f e r [ i t + 1 ] ) ;6 wi−>zero_data [ i ] = 0 ;7 i t += 2 ;8 i ++;9 wi−>l e f t _ s i d e [ i ] = bytes_to_double ( b u f f e r [ i t ] ,

10 b u f f e r [ i t + 1 ] ) ;11 wi−>zero_data [ i ] = 0 ;12 i t += 2 ;13 i ++;14 }15 }16 else i f ( wi−>wav_header−>num_channels == 2){17 while ( i t < wi−>wav_header−>subchunk2_size ){18 wi−>zero_data [ i ] = 0 ;19 i t +=4;20 i ++;21 wi−>zero_data [ i ] = 0 ;22 i t +=4;23 i ++;24 }25 i = i t = 0 ;26 while ( i t < wi−>wav_header−>subchunk2_size ){27 wi−>l e f t _ s i d e [ i ] = bytes_to_double ( b u f f e r [ i t ] ,28 b u f f e r [ i t + 1 ] ) ;29 i t += 4 ;30 i ++;31 wi−>l e f t _ s i d e [ i ] = bytes_to_double ( b u f f e r [ i t ] ,32 b u f f e r [ i t + 1 ] ) ;33 i t += 4 ;34 i ++;35 }36 i = 0 ;37 i t = 2 ;38 while ( i t < wi−>wav_header−>subchunk2_size ){39 wi−>r i g h t _ s i d e [ i ] = bytes_to_double ( b u f f e r [ i t ] ,40 b u f f e r [ i t + 1 ] ) ;41 i t +=4;42 i ++;43 wi−>r i g h t _ s i d e [ i ] = bytes_to_double ( b u f f e r [ i t ] ,44 b u f f e r [ i t + 1 ] ) ;45 i t +=4;46 i ++;47 }48 }

Algoritmo 4.5: Loop unrolling no algoritmo 4.4.


4.1.2 Experimento 2

Analisando o loop do algoritmo 4.6 que rearranja os dados para o calculo da FFT.

1 for(i = 0; i < wi -> nb_samples ; i++){

2 wi -> left_fixed [2*i+1] = wi -> left_side [i];

3 wi -> left_fixed [2*i+2] = 0;


5 wi -> right_fixed [2*i+1] = wi -> right_side [i];

6 wi -> right_fixed [2*i+2] = 0;

7 }

8 }


O algoritmo 4.6 é parecido com o algoritmo 4.1, uma vez que ambos contêm umadeclaração if independente do loop em seu corpo. Assim, também foi aplicada a técnicaloop unswitching no algoritmo 4.6. O algoritmo 4.7 mostra o resultado da aplicação deloop unswitching no algoritmo 4.6.

Com o intuito de diminuir o número de iterações será aplicado loop unroll noalgoritmo 4.7. O algoritmo 4.8 mostra o resultado de loop unroll no algoritmo 4.7.

Considerando o algoritmo 4.7 onde o segundo loop itera sobre dois vetores. Seráaplicado loop fission, dividindo-o em dois loops onde cada um itere em um vetor. Oalgoritmo 4.9 mostra o resultado de loop fission no algoritmo 4.7.

Com algoritmo 4.9 agora com três loops. Será aplicado loop unrolling neste paraque o número de iterações em cada loop seja dividido por quatro. O algoritmo 4.10 mostrao resultado de loop unrolling no algoritmo 4.9.

A tabela 4.1.2 apresenta os resultados obtidos sobre o algoritmo 4.6. O algo-ritmo 4.10 obteve o melhor desempenho, utilizando as técnicas loop unswitching, loopfission e loop unrolling. O algoritmo 4.9 obteve o pior desempenho devido a iteração so-bre uma quantidade pequena de dados, assim não utilizando os benefícios da memóriacache e memory locality. A melhora do algoritmo 4.10 sobre o algoritmo 4.8 deve-se aofato do algoritmo 4.10 iterar sobre um mesmo conjunto de vetores, assim, desfrutandodos benefícios de memory locality.







4 wi -> left_fixed [2*i+2] = 0;

5 }

6 }




10 wi -> left_fixed [2*i+2] = 0;


12 wi -> right_fixed [2*i+2] = 0;

13 }

14 }




2 for(i = 0; i < wi -> nb_samples ; i += 2){


4 wi -> left_fixed [2*i+2] = 0;

5 wi -> left_fixed [2*(i +1)+1] = wi -> left_side [i + 1];

6 wi -> left_fixed [2*(i +1)+2] = 0;

7 }

8 }




12 wi -> left_fixed [2*i+2] = 0;


14 wi -> right_fixed [2*i+2] = 0;

15

16 wi -> left_fixed [2*(i +1)+1] = wi -> left_side [i+1];

17 wi -> left_fixed [2*(i +1)+2] = 0;

18 wi -> right_fixed [2*(i +1)+1] = wi -> right_side [i+1];

19 wi -> right_fixed [2*(i +1)+2] = 0;

20

21 }

22 }

Algoritmo 4.8: Loop unroll no algoritmo 4.7.





4 wi -> left_fixed [2*i+2] = 0;

5 }

6 }




10 wi -> left_fixed [2*i+2] = 0;

11 }



14 wi -> right_fixed [2*i+2] = 0;

15 }

16 }






4 wi -> left_fixed [2*i+2] = 0;


6 wi -> left_fixed [2*(i +1)+2] = 0;


8 wi -> left_fixed [2*(i +2)+2] = 0;


10 wi -> left_fixed [2*(i +3)+2] = 0;

11 }

12 }




16 wi -> left_fixed [2*i+2] = 0;


18 wi -> left_fixed [2*(i +1)+2] = 0;


20 wi -> left_fixed [2*(i +2)+2] = 0;


22 wi -> left_fixed [2*(i +3)+2] = 0;

23 }



26 wi -> right_fixed [2*i+2] = 0;


28 wi -> right_fixed [2*(i +1)+2] = 0;


30 wi -> right_fixed [2*(i +2)+2] = 0;


32 wi -> right_fixed [2*(i +3)+2] = 0;

33 }

34 }



4.1.3 Experimento 3

Analisando o loop do algoritmo 4.11 o qual multiplica um dado vetor por onzefatores de equalização.

1 for(i = BAND_MIN ; i < BAND_MAX ; i++){

2 if(i < BAND_0 )

3 temp[i] *= wi ->factors ->fac_0;

4 else if(i < BAND_1 )


















22 else

23 temp[i] *= wi ->factors -> fac_10 ;

24 }


O algoritmo 4.11 também possui declaração de comparação no corpo do loop,porém as comparações do algoritmo 4.11 dependem da iteração do loop, sendo assim nãoé permitido a aplicação de loop unswitching.

Para este loop foi aplicado a técnica index set splitting, uma vez que os limitesdo loop e também o valor de cada comparação realizada ser fixo no programa, o in-dex set splitting irá dividir o loop em onze loops com o espaço de iteração variando deBAND_MIN até BAND_0, BAND_0 até BAND_1 e assim até o ultimo loop que iráiterar de BAND_9 até BAND_MAX. Com isso será eliminadas todas as declarações decomparação e continuará iterando o mesmo número de vezes.


O algoritmo 4.12 mostra o resultado da aplicação de index set splitting no algo-ritmo 4.11.

Com o intuito de diminuir o número de iterações no algoritmo 4.12 foi aplicadoloop unrolling em cada um dos onze loops. O algoritmo 4.13 mostra o resultado de loopunrolling no algoritmo 4.12.

A tabela 4.1.3 apresenta os resultados obtidos sobre o algoritmo 4.11. O algo-ritmo 4.13 obteve o melhor desempenho, onde fora aplicado index set splitting dividindoo loop em onze novos loops sem declarações de comparações aninhadas. A técnica loopunrolling dividiu por dois a quantidade de iterações dos onze loops.

Algoritmo Técnicas aplicadas Tempo de execuçãoAlgoritmo 4.11 nenhuma 240 msAlgoritmo 4.12 index set splitting 145 msAlgoritmo 4.13 index set splitting, loop unroll 75 ms



1 for(i = BAND_MIN ; i < BAND_0 ; i++)


3

4 for(i = BAND_0 ; i < BAND_1 ; i++)


6

7 for(i = BAND_1 ; i < BAND_2 ; i++)


9

10 for(i = BAND_2 ; i < BAND_3 ; i++)


12

13 for(i = BAND_3 ; i < BAND_4 ; i++)


15

16 for(i = BAND_4 ; i < BAND_5 ; i++)


18

19 for(i = BAND_5 ; i < BAND_6 ; i++)


21

22 for(i = BAND_6 ; i < BAND_7 ; i++)


24

25 for(i = BAND_7 ; i < BAND_8 ; i++)


27

28 for(i = BAND_8 ; i < BAND_9 ; i++)


30

31 for(i = BAND_9 ; i < BAND_MAX ; i++)

32 temp[i] *= wi ->factors -> fac_10 ;

Algoritmo 4.12: Index set splitting no algoritmo 4.11.


1 for ( i = BAND_MIN; i < BAND_0; i += 2){2 temp [ i ] *= wi−>f a c t o r s −>fac_0 ;3 temp [ i + 1 ] *= wi−>f a c t o r s −>fac_0 ;4 }5 for ( i = BAND_0; i < BAND_1; i += 2){6 temp [ i ] *= wi−>f a c t o r s −>fac_1 ;7 temp [ i + 1 ] *= wi−>f a c t o r s −>fac_1 ;8 }9 for ( i = BAND_1; i < BAND_2; i += 2){

10 temp [ i ] *= wi−>f a c t o r s −>fac_2 ;11 temp [ i + 1 ] *= wi−>f a c t o r s −>fac_2 ;12 }13 for ( i = BAND_2; i < BAND_3; i += 2){14 temp [ i ] *= wi−>f a c t o r s −>fac_3 ;15 temp [ i + 1 ] *= wi−>f a c t o r s −>fac_3 ;16 }17 for ( i = BAND_3; i < BAND_4; i += 2){18 temp [ i ] *= wi−>f a c t o r s −>fac_4 ;19 temp [ i + 1 ] *= wi−>f a c t o r s −>fac_4 ;20 }21 for ( i = BAND_4; i < BAND_5; i += 2){22 temp [ i ] *= wi−>f a c t o r s −>fac_5 ;23 temp [ i + 1 ] *= wi−>f a c t o r s −>fac_5 ;24 }25 for ( i = BAND_5; i < BAND_6; i += 2){26 temp [ i ] *= wi−>f a c t o r s −>fac_6 ;27 temp [ i + 1 ] *= wi−>f a c t o r s −>fac_6 ;28 }29 for ( i = BAND_6; i < BAND_7; i += 2){30 temp [ i ] *= wi−>f a c t o r s −>fac_7 ;31 temp [ i + 1 ] *= wi−>f a c t o r s −>fac_7 ;32 }33 for ( i = BAND_7; i < BAND_8; i += 2){34 temp [ i ] *= wi−>f a c t o r s −>fac_8 ;35 temp [ i + 1 ] *= wi−>f a c t o r s −>fac_8 ;36 }37 for ( i = BAND_8; i < BAND_9; i += 2){38 temp [ i ] *= wi−>f a c t o r s −>fac_9 ;39 temp [ i + 1 ] *= wi−>f a c t o r s −>fac_9 ;40 }41 for ( i = BAND_9; i < BAND_MAX; i += 2){42 temp [ i ] *= wi−>f a c t o r s −>fac_10 ;43 temp [ i + 1 ] *= wi−>f a c t o r s −>fac_10 ;44 }



4.1.4 Experimento 4

Analisando o loop do algoritmo 4.14 que transforma os dados após a aplicação daFFT.


2 wi -> left_side [i] = wi -> left_fixed [2*i+1];


4 wi -> right_side [i] = wi -> right_fixed [2*i+1];

5 }

6 }


O algoritmo 4.14 também contém uma declaração if no corpo do loop que é inde-pendente do loop. Assim, foi também aplicada neste loop a técnica loop unswitching. Oalgoritmo 4.15 mostra o resultado de loop unswitching no algoritmo 4.14.

Para que o número de iteração no algoritmo 4.15 foi aplicado loop unrolling. Oalgoritmo 4.16 mostra o resultado de loop unrolling no algoritmo 4.14.

O segundo loop do algoritmo 4.15 está iterando sobre dois vetores do lado direitodas declarações de atribuição, sendo assim, foi aplicado loop fission, dividindo-os em doisloops. O algoritmo 4.17 mostra o resultado de loop fission no algoritmo 4.15.

Para diminuir o número de iterações dos loops do algoritmo 4.17 foi aplicado loopunrolling em cada um dos loops. O algoritmo 4.18 mostra o resultado de loop unrollingno algoritmo 4.17.

A tabela 4.1.4 apresenta os resultados obtidos sobre o algoritmo 4.14. O algo-ritmo 4.18 apresentou o melhor desempenho A melhora no desempenho seguiu de acordocom a ordem em que as técnicas foram sendo aplicadas, removendo-se declarações decomparação do corpo do loop com loop unswitching e então dividindo em dois loops comloop fission, iterando sobre um conjunto de dados único e então multiplicando o corpo doloop com loop unrolling diminuindo o número de iterações, desta forma, aproveitando osbenefícios de memory locality.







4 }

5 }





10 }

11 }



2 for(i = 0; i < wi -> nb_samples ; i+=2){


4 wi -> left_side [i + 1] = wi -> left_fixed [2*(i +1)+1];

5 }

6 }






12 wi -> right_side [i + 1] = wi -> right_fixed [2*(i +1)+1];

13 }

14 }






4 }

5 }




9 }



12 }

13 }






5 }

6 }





11 }



14 wi -> right_side [i + 1] = wi -> right_fixed [2*(i +1)+1];

15 }

16 }



4.1.5 Experimento 5

Analisando o algoritmo 4.19 que apresenta dois loops, sendo que o primeiro con-verte um vetor double em um vetor short int e o segundo loop combina os bytes do vetorshort int em um vetor unsigned char.


2 wi -> short_left [i] = ( short int)wi -> left_side [i];


4 wi -> short_right [i] = ( short int)wi -> right_side [i];

5 }

6 }

7 int it = wi ->wav_header -> num_channels * 2;

8 int count = 0;

9 for(i = 0; i < wi -> nb_samples * it; i += it){

10 memcpy (&wi -> buffer [i], &wi -> short_left [count], 2);


12 memcpy (&wi -> buffer [i + 2], &wi -> short_right [count], 2);

13 }

14 count ++;

15 }


O algoritmo 4.19 contém uma declaração if no corpo de cada um dos loops, ondeambos são independentes de seu respectivo loop. Sendo assim, foi aplicada a técnica loopunswitching em cada um dos loops do algoritmo 4.19 e resultando no algoritmo 4.20.

Para diminuir o número de iterações do algoritmo 4.20 será aplicado loop unrolling.O algoritmo 4.21 mostra o resultado de loop unrolling nos loops do algoritmo 4.20.

O algoritmo 4.20 agora sem declaração if no corpo do loops apresenta dois loopspara cada resultado de if ou else if, sendo assim, foi feito uma reordenação das declaraçõescom o intuito de melhorar a legibilidade do código para aplicação de outras técnicas. Oalgoritmo 4.22 mostra o resultado da reordenação das declarações do algoritmo 4.20, ondecada resultado das comparações possuem dois loops, a ordem de computação dos loopsfoi mantida para que o significado do programa não se altere.

Analisando o algoritmo 4.22, nota-se que os loops tem como espaço de iteraçãoo valor de wi->nb_samples, embora o segundo loop itere sobre wi->nb_samples * ite-rator, é possível aplicar a técnica loop fusion nos loops, assim unindo-os em um únicoloop, sendo necessário ajustar o espaço de iteração. Devido ao segundo loop utilizar osdados computados pelo primeiro loop, será necessário garantir que essa dependência seja


mantida.

A aplicação do loop fusion sobre o algoritmo 4.20 pode se tornar confusa devido àaplicação do loop unswitching, que torna mais complexa a leitura do código. A reordenaçãode declarações fez com que o algoritmo 4.20 ficasse mais legível, o algoritmo 4.23 mostrao resultado de loop fusion no algoritmo 4.22.

A tabela 4.1.5 apresenta os resultados obtidos sobre o algoritmo 4.19. O algo-ritmo 4.21 apresentou o melhor desempenho, uma vez que, a técnica loop unswitchingfez com que fosse realizada as comparações de if, else if uma única vez e não em cadaiteração. O uso de loop unrolling fez com que o número de iteração fosse dividido pordois, assim diminuindo o número de comparações realizadas na condição do loop.

O algoritmo 4.23 onde fora aplicado loop fusion e loop unswitching, mesmo apre-sentando melhora no desempenho não superou o uso de loop unrolling no algoritmo 4.20.Essa melhora menos significativa deve-se a desvantagem de loop fusion, onde o aumentode dados acessados em cada iteração pode prejudicar o reuso da memória cache [22].

Algoritmo Técnicas aplicadas Tempo de execuçãoAlgoritmo 4.19 nenhuma 494 msAlgoritmo 4.20 loop unswitching 450 msAlgoritmo 4.21 loop unswitching, loop unrolling 422 msAlgoritmo 4.23 loop unswitching, loop fusion 477 ms






4 }

5 }





10 }

11 }

12 int count = 0;


14 int it = 2;



17 count ++;

18 }

19 }


21 int it = 4;




25 count ++;

26 }

27 }






4 wi -> short_left [i + 1] = ( short int)wi -> left_side [i + 1];

5 }

6 }





11 wi -> short_left [i+1] = ( short int)wi -> left_side [i+1];

12 wi -> short_right [i+1] = ( short int)wi -> right_side [i+1];

13 }

14 }

15 int count = 0;


17 int it = 4;



20 count ++;

21 memcpy (&wi -> buffer [i + 2], &wi -> short_left [count], 2);

22 count ++;

23 }

24 }


26 int it = 8;




30 count ++;

31 memcpy (&wi -> buffer [i + 4], &wi -> short_left [count], 2);


33 count ++;

34 }

35 }



1 int count = 0;




5 }

6 int it = 2;



9 count ++;

10 }

11 }





16 }

17 int it = 4;




21 count ++;

22 }

23 }

Algoritmo 4.22: Reordenação das declarações do algoritmo 4.20.


1 int count = 0;


3 int it = 2;


5 wi -> short_left [i/it] = ( short int)wi -> left_side [i/it];


7 count ++;

8 }


10 int it = 4;


12 wi -> short_left [i/it] = ( short int)wi -> left_side [i/it];

13 wi -> short_right [i/it] = ( short int)wi -> right_side [i/it];



16 count ++;

17 }

18 }

Algoritmo 4.23: Loop fusion no algoritmo 4.22.

4.1.6 Experimento 6

Analisando o loop do algoritmo 4.24 que escreve em arquivo o vetor buffer.

1 for(i = 0; i < wi ->wav_header -> subchunk2_size ; i++){

2 fwrite (&wi -> buffer [i], sizeof ( unsigned char), 1, f);

3 }


Para diminuir o número de iterações no algoritmo 4.24 foi aplicado loop unrolling.O algoritmo 4.25 mostra o resultado de loop unrolling no algoritmo 4.24.

1 for(i = 0; i < wi ->wav_header -> subchunk2_size ; i += 4){

2 fwrite (&wi -> buffer [i], sizeof ( unsigned char), 1, f);

3 fwrite (&wi -> buffer [i + 1], sizeof ( unsigned char), 1, f);



6 }

7 }


4.2. Resultados Experimentais 73

A tabela 4.1.6 apresenta os resultados obtidos sobre o algoritmo 4.24. A técnicaloop unrolling aplicada melhorou o tempo em 514 ms, sendo que a leitura e escrita emdisco é um dos gargalos de wat.

Algoritmo Técnicas aplicadas Tempo de execuçãoAlgoritmo 4.24 nenhuma 6910 msAlgoritmo 4.25 loop unrolling 6296 ms


4.2 Resultados Experimentais

Os experimentos foram compilados utilizando o compilador GCC sem utilizar ne-nhuma forma de otimização por parte do compilador. Os códigos foram escritos e reescritosmanualmente a cada experimento.

Considerando os resultados experimentais da tabela 4.2, o tempo total de execuçãodos loops analisados foi de 8750 ms, após a aplicação das técnicas de tranformação deloops o tempo total foi de 7816 ms, ou seja, houve uma melhora de 11.94% no tempo decomputação destes loops.

Experimento Tempo sem otimização Tempo com otimização Ganho %1 470 ms 444 ms 5.85%2 485 ms 435 ms 11.26%3 240 ms 75 ms 320%4 150 ms 144 ms 4.16%5 494 ms 422 ms 17.06%6 6910 ms 6296 ms 9.75%

Tabela 4.7 – Resultados experimentais.

Considerando o tempo de execução de wat na equalização de um arquivo de áudiosterio (2 canais de áudio) de 40 MB e com 4 minutos e 15 segundos de duração, o tempototal de execução de wat sem otimização é de 19396 ms e o tempos de execução otimizadoé de 18062 ms, ou seja, uma melhora de 7.5%. O percentual de desempenho é menordevido ao fato de que o cálculo da transformada de Fourier [24] utilizado em wat nãopode ser otimizado, uma vez que, foi utilizado um código já otimizado para este cálculo.

Durante os experimentos foi observado que a utilização de mais de uma técnicapode não só obter o ganho individual de cada uma das técnicas, como também potencia-lizar os resultados uma das outras.

75

5 CONCLUSÃO

Neste trabalho foi discutido um procedimento de paralelização de tarefas sobreum algoritmo pré-existente. Inicialmente foi apresentada uma fundamentação teórica comtécnicas clássicas de paralelização, tanto em hardware como em software. Em seguida, foidescrita com maior profundidade a programação envolvendo paralelismo, destacando-seas técnicas de transformação de loops.

O objetivo desse trabalho foi aplicar técnicas de transformação de loops em umaaplicação para melhora de seu desempenho. A aplicação utilizada foi o programa de equa-lização de áudio wat. Embora existam muitas técnicas, a obtenção de benefícios em usá-lasé uma característica empírica. Os resultados obtidos com as otimizações mostraram queo uso de técnicas de transformação de loops podem significar um grande impacto no de-sempenho do programa. Casos onde as técnicas não obtiveram resultados significativos,acabou por ficar evidente que o custo computacional estava em chamadas de função quenão podem ser melhoradas com transformação de loop.

Dessa forma, pode-se elencar alguns trabalhos futuros a fim de se chegar em re-sultados ainda mais expressivos do que os aqui obtidos.

Entre os trabalhos futuros é desejável que se aborde toda a questão de transfor-mação de loops voltados a uma arquitetura específica. Esse tipo de investigação pode sermotivada por possíveis comportamentos diferenciados de um mesmo algoritmo conformea plataforma de hardware tal como memória cache e intruction cache.

Técnicas de otimização de código a serem aplicadas naqueles que estão no corpodo loop pode ser primordial para que o custo compucional do loop seja reduzido, tal comoutilizar funções inline e substituição de variáveis, evitando gasto com acesso a memóriaatravés de ponteiros.

77

REFERÊNCIAS

1 GEBALI, F. Algorithms and Parallel Computing. [S.l.]: Wiley, 2011. (Wiley Series onParallel and Distributed Computing). ISBN 9780470934630.

2 PACHECO, P. An Introduction to Parallel Programming. [S.l.]: Elsevier Science, 2011.(An Introduction to Parallel Programming). ISBN 9780080921440.

3 LIU, M. et al. General loop fusion technique for nested loops considering timing andcode size. In: Proceedings of the 2004 international conference on Compilers, architecture,and synthesis for embedded systems. New York, NY, USA: ACM, 2004. (CASES ’04), p.190–201. ISBN 1-58113-890-3.

4 TASHAROFI, S.; JOHNSON, R. Patterns of optimized loops. In: Proceedings of the2010 Workshop on Parallel Programming Patterns. New York, NY, USA: ACM, 2010.(ParaPLoP ’10), p. 6:1–6:8. ISBN 978-1-4503-0127-5.

5 MINISKAR, N. R. et al. Function inlining and loop unrolling for loop accelerationin reconfigurable processors. In: Proceedings of the 2012 international conference onCompilers, architectures and synthesis for embedded systems. New York, NY, USA:ACM, 2012. (CASES ’12), p. 101–110. ISBN 978-1-4503-1424-4.

6 CHANG, W.-L.; CHU, C.-P.; HO, M. S.-H. Exploitation of parallelism to nestedloops with dependence cycles. Journal of Systems Architecture, v. 50, n. 12, p. 729 – 742,2004. ISSN 1383-7621.

7 FLYNN, M. Very high-speed computing systems. Proceedings of the IEEE, v. 54,n. 12, p. 1901–1909, 1966. ISSN 0018-9219.

8 FLYNN, M. Some computer organizations and their effectiveness. Computers, IEEETransactions on, C-21, n. 9, p. 948–960, 1972. ISSN 0018-9340.

9 FLYNN, M. J.; RUDD, K. W. Parallel architectures. ACM Comput. Surv., ACM,New York, NY, USA, v. 28, n. 1, p. 67–70, mar. 1996. ISSN 0360-0300.

10 PADUA, D. Encyclopedia of Parallel Computing. [S.l.]: Springer, 2011. (Springerreference, v. 4). ISBN 9780387097657.

11 KENNEDY, K.; ALLEN, J. R. Optimizing compilers for modern architectures: adependence-based approach. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc.,2002. ISBN 1-55860-286-0.

12 OPENSHAW, S.; TURTON, I. High Performance Computing and the Art of ParallelProgramming: An Introduction for Geographers, Social Scientists and Engineers. [S.l.]:Taylor & Francis, 1999. ISBN 9780415156929.

13 DONGARRA, J. et al. Source Book of Parallel Computing. [S.l.]: Morgan Kaufmann,2003. (The Morgan Kaufmann Series in Computer Architecture and Design Series).ISBN 9781558608719.

78 Referências

14 SEITZ, C. L. The cosmic cube. Commun. ACM, ACM, New York, NY, USA, v. 28,n. 1, p. 22–33, jan. 1985. ISSN 0001-0782.

15 WOLFE, M. High Performance Compilers for Parallel Computing. [S.l.]: ADDISONWESLEY Publishing Company Incorporated, 1996. ISBN 9780805327304.

16 MCKINLEY, K. S.; CARR, S.; TSENG, C.-W. Improving data locality with looptransformations. ACM Trans. Program. Lang. Syst., ACM, New York, NY, USA, v. 18,n. 4, p. 424–453, jul. 1996. ISSN 0164-0925.

17 GHODRAT, M. A.; GIVARGIS, T.; NICOLAU, A. Control flow optimization inloops using interval analysis. In: Proceedings of the 2008 international conference onCompilers, architectures and synthesis for embedded systems. New York, NY, USA:ACM, 2008. (CASES ’08), p. 157–166. ISBN 978-1-60558-469-0.

18 YANG, M.; UH, G.-R.; WHALLEY, D. B. Efficient and effective branch reorderingusing profile data. ACM Trans. Program. Lang. Syst., ACM, New York, NY, USA, v. 24,n. 6, p. 667–697, nov. 2002. ISSN 0164-0925.

19 SONG, L.; KAVI, K. What can we gain by unfolding loops? SIGPLAN Not., ACM,New York, NY, USA, v. 39, n. 2, p. 26–33, fev. 2004. ISSN 0362-1340.

20 WOLF, M. E.; MAYDAN, D. E.; CHEN, D.-K. Combining loop transformationsconsidering caches and scheduling. In: Proceedings of the 29th annual ACM/IEEEinternational symposium on Microarchitecture. Washington, DC, USA: IEEE ComputerSociety, 1996. (MICRO 29), p. 274–286. ISBN 0-8186-7641-8.

21 DRAGOMIR, O. S.; STEFANOV, T.; BERTELS, K. Optimal loop unrolling andshifting for reconfigurable architectures. ACM Trans. Reconfigurable Technol. Syst.,ACM, New York, NY, USA, v. 2, n. 4, p. 25:1–25:24, set. 2009. ISSN 1936-7406.

22 RIVERA, G.; TSENG, C.-W. Locality optimizations for multi-level caches. In:Proceedings of the 1999 ACM/IEEE conference on Supercomputing. New York, NY,USA: ACM, 1999. (Supercomputing ’99). ISBN 1-58113-091-0.

23 ALLEN, R.; KENNEDY, K. Automatic loop interchange. SIGPLAN Not., ACM,New York, NY, USA, v. 39, n. 4, p. 75–90, abr. 2004. ISSN 0362-1340.

24 RAO, K.; KIM, D.; HWANG, J. Fast Fourier Transform - Algorithms andApplications: Algorithms and Applications. [S.l.]: Springer, 2011. (Signals andcommunication technology). ISBN 9781402066290.

Documents

LUIZGUILHERMECASTILHOMARTINS - uel.br · 19 1 INTRODUÇÃO Diantedadificuldadedesemelhorarprocessadoressingle-coredevidoaoaltocon- sumodeenergiaeasaltastemperaturas