Análise de Desempenho de Multiplicações de Matrizes Utilizando Diferentes Métodos de Otimização Sherlon Almeida da Silva1, Claudio Schepke1 1
Curso de Ciência da Computação Universidade Federal do Pampa – Campus Alegrete Av. Tiarajú, 810 – Bairro: Ibirapuitã – Alegrete – RS – CEP: 97546-550
[email protected],
[email protected]
Resumo. Sistemas computacionais são utilizados em diversas áreas do conhecimento e seu desempenho é fundamental para maior precisão nos resultados. Para problemas complexos a aplicação de otimizações tornam-se necessárias. O objetivo deste trabalho é analisar o desempenho de algoritmos de Multiplicação de Matrizes e agilizar este processo através de diferentes métodos. O ganho computacional foi 60 vezes maior após estas otimizações.
1. Introdução Matrizes são operações fundamentais de Álgebra Linear que são aplicadas em diversos campos do conhecimento, um algoritmo eficiente para tal operação é importante pois conforme a complexidade da ordem aumenta a operação exige maior capacidade de performance [Marquezan et al. 2002]. Através do avanço tecnológico das últimas décadas os algoritmos de sistemas necessitam ser modificados para melhor aproveitar o poder computacional atual. Algoritmos de soluções complexas exigem mais eficiência do computador, muitas vezes sobrecarregando o processador e a memória, o que gera perda de velocidade. A otimização desses algoritmos traz vantagens de ganho de desempenho e maior eficiência. Desta forma os resultados obtidos através do algoritmo otimizado tornam-se mais precisos e satisfatórios. Profissionais de diversas áreas deparam-se com problemas ao buscarem soluções computacionais pois a precisão de seus resultados sofre limitações relacionadas aos recursos tecnológicos disponíveis. Portanto será analisado o desempenho de algoritmos de Multiplicação de Matrizes buscando possíveis melhoras de desempenho através de otimizações no código fonte na linguagem C e também através de diretivas de otimização oferecidas pelo compilador gcc, visando proporcionar melhores resultados nestas áreas que envolvem tais problemas fundamentais de Álgebra linear.
2. Ambiente de Programação e Execução A análise de desempenho e os dados coletados foram gerados a partir do sistema Linux e para a implementação dos algoritmos foi utilizado o compilador gcc versão 4.9.2 na linguagem C. O computador utilizado para os testes possui um processador Intel(R) Core(TM) i3 CPU M 380 @ 2.53GHz, memória RAM de 2GB e um sistema de arquitetura 32 bits.
3. Produto Matricial e Algoritmos Utilizados A implementação eficiente do produto matricial é fundamental pois aparece em muitos outros algoritmos matriciais, uma vez que ele é a modelagem matemática da
aplicação de uma função linear, sua implementação eficiente permite a obtenção de ótimo desempenho em um processador [Maillard 2005]. A multiplicação de matrizes Amxn x Bmxn é dada a partir do produto escalar entre os elementos da linha da matriz A e os elementos da coluna da matriz B, gerando a correspondente matriz Cmxn. Toda matriz possui uma ordem mxn para representar o tamanho das linhas e colunas, respectivamente, e seus elementos são representados pelas letras i (linhas) e j (colunas). A multiplicação segue a fórmula: Cij = ∑𝒏𝒌=𝟏 𝑨𝒊𝒌 𝒙 𝑩𝒌𝒋, para i, j = 1...n, onde n é a ordem das matrizes A e B [Santos 2000]. Para os seguintes testes foram utilizadas apenas matrizes quadradas (m e n possuem o mesmo valor), onde m e n são o resultado de potências de base 2. Foram implementados quatro algoritmos de multiplicação de matrizes, sendo eles o algoritmo Convencional, um algoritmo baseado em Loop Unrolling de duas somas, um baseado em Loop Unrolling de quatro somas e outro baseado em Multiplicação de Matrizes por Blocos. Cada um dos quatro algoritmos foi implementado em Matriz de Vetor Simples e Matriz de Vetor de Ponteiros, totalizando oito códigos. 3.1. Algoritmo Convencional Este algoritmo utiliza três laços de repetição for aninhados visando percorrer todos elementos da matriz. Cada laço possui uma variável de incremento, sendo elas respectivamente i, j e k. A variável i é responsável pelo deslocamento dos elementos nas linhas, a variável j é responsável pelo deslocamento destes elementos nas colunas, e a variável k é utilizada para os incrementos para as multiplicações [Celes et al. 2004]. 3.2. Algoritmo Loop Unrolling 2 e 4 Somas Sucessivas Este algoritmo baseado em Loop Unrolling trabalha da mesma forma que o algoritmo Convencional. Porém a cada incremento da variável k há duas somas no primeiro código, e quatro somas no segundo código, as quais serão armazenadas na posição de memória da matriz resposta Cij. 3.3. Algoritmo por Blocos Este algoritmo baseado em Multiplicação por Blocos possui seis laços de repetição for aninhados e suas variáveis de incremento são i, j, k, x, y, z. Este método divide a matriz desejada em blocos, onde cada bloco é uma matriz diferente. Sua operação de multiplicação funciona de forma semelhante à convencional. Pode-se interpretar esta multiplicação como “matriz de matrizes”. As variáveis i e j percorrem os blocos linhas e colunas, dentro desses blocos as variáveis k e x percorrem as linhas e colunas do bloco, e as variáveis y e z são responsáveis pelos incrementos para as multiplicações.
4. Técnicas de Otimização e Análise de Desempenho O compilador gcc possibilita técnicas próprias para otimizar os códigos em tempo de execução, os níveis de otimização são -O0 no qual não há otimização, -O1 o gcc tenta reduzir o tempo de compilação e o tamanho do executável, -O2 melhora o desempenho, é o mais seguro e utilizado, -O3 proporciona maior otimização, porém como é um nível muito alto de otimização pode gerar efeitos colaterais [Borges 2010].
Para cada código foram realizadas vinte e cinco execuções para se obter o tempo decorrido em segundos. Através desses resultados foi feita a média e organizada a seguir na tabela 1, a primeira coluna mostra as ordens executadas e a primeira linha mostra os algoritmos utilizados. O M1 e M2 são os códigos Convencionais, o M3 e M4 são baseados em Loop Unrolling de duas somas, o M5 e M6 são baseados em Loop Unrolling de quatro somas, e o M7 e M8 são baseados em Multiplicação por Blocos. O M1, M3, M5 e M7 são matrizes de Vetor Simples e M2, M4, M6 e M8 de Vetor de Ponteiros. Como se pode observar, as matrizes implementadas em Vetor de Ponteiros cuja ordem ultrapassa 210 obtiveram melhores resultados sobre aquelas implementadas por Vetor Simples, visto que estas apontam diretamente para a região de cada linha, facilitando o acesso à memória. Enquanto na de vetor simples os dados são armazenados de forma contígua e é necessário um breve cálculo para identificar a posição do elemento. Tabela 1. Dados coletados na execução (Otimização Código Fonte) ORDEM – MATRIZ 64x64 128x128 256x256 512x512 1024x1024 2048x2048
M1
M2
M3
M4
M5
M6
M7
M8
0.00 0.02 0.18 1,70 45,86 439,08
0.00 0.02 0.17 1,70 20,49 176,98
0.00 0.02 0.18 1,69 48,99 400,64
0.00 0.02 0.16 2,02 20,79 176,63
0.00 0.02 0.17 1,55 45,67 398,92
0.00 0.01 0.15 1,45 17,60 161,31
0.00 0.02 0.14 1,35 10,84 87,80
0.00 0.02 0.16 1,30 10,41 83,67
A tabela 2 mostra os resultados das diretivas de otimização feitas sobre os oito códigos, neste caso foi testado apenas para matrizes de ordem 2048x2048 pois, como foi observado na tabela 1, quanto maior é o porte do sistema computacional otimizado mais facilmente é visto este ganho de desempenho. A matriz convencional ao ser otimizada e reformulada através da implementação em forma de Multiplicações por Blocos teve ganho computacional de aproximadamente 5 vezes. Após a otimização na implementação do código foi utilizada a diretiva -O3 sobre este resultado, o que proporcionou um desempenho de aproximadamente 11 vezes mais rápido. Ao comparar o resultado inicial que foi aproximadamente 439 segundos do algoritmo da Matriz Convencional, com aproximadamente 7 segundos do algoritmo de Multiplicação por Blocos que foi otimizado na implementação e com as diretivas do gcc, obteve-se um ganho computacional de aproximadamente 60 vezes mais rápido. Tabela 2. Dados coletados na execução (Diretivas de Otimização gcc) MATRIZ M1 M2 M3 M4 M5 M6 M7 M8
DIRETIVAS DE OTIMIZAÇÃO GCC -O0 -O1
412.91 177.92 394.89 174.32 406.64 168.67 86.96 83.21
128.02 101.72 129.03 99.42 131.05 99.18 8.80 10.63
-O2
-O3
128.01 100.65 127.90 103.23 134.55 81.53 10.35 10.40
127.67 100.72 128.01 98.74 130.11 115.25 10.34 7.28
A figura 1 apresenta os resultados gerais obtidos durante as execuções através das diretivas de otimização do gcc aplicado aos códigos de multiplicação de matrizes de
ordem 2048x2048. Nota-se claramente o ganho em desempenho a partir de diferentes técnicas e níveis de otimização.
Figura 1. Desempenho Geral das Multiplicações de Matrizes – Tempo (s).
5. Conclusão A elaboração de programas visando desempenho computacional cresceu nas últimas décadas. O alto desempenho é fundamental para resultados consistentes em problemas gerais. A otimização do código fonte gera um resultado satisfatório, e sobre este código as diretivas de otimização do gcc possibilitam um desempenho ainda maior. Métodos de otimização para melhoria de performance de sistemas computacionais são importantes e necessários principalmente para problemas de grande complexidade, para obter resultados mais precisos, rápidos e com menor custo computacional para o processador e memória, uma vez que a velocidade e precisão destes resultados estão diretamente relacionados aos recursos computacionais atuais. O próximo passo é testar o processamento paralelo destes algoritmos com a interface de programação OpenMP.
Referências Borges A.; Opções Básicas do gcc. Linux Magazine Online, 2010, p.20. Disponível em: . Celes, W.; Cerqueira, R.; Rangel, J. L. Introdução a Estruturas de Dados: com Técnicas de Programação em C. Campus, 2004, p.71. Maillard N.; Algoritmos Matriciais em Processamento de Alto Desempenho. Instituto de Informática da Universidade Federal do Rio Grande do Sul. Escola Regional de Alto Desempenho, 2005. Marquezan C.; Contessa D.; Alves R.; Diverio T.; Análise de Complexidade e Desempenho de Algoritmos para Multiplicação de Matrizes. Escola Regional de Alto Desempenho, 2002. Santos R. J.; Álgebra Linear Matricial. Belo Horizonte: Imprensa Universitária da UFMG, 2000, p.5.
