Estudo e Avaliação do Problema de Otimização da Multiplicação de

Cadeias de Matrizes

Eduardo de Lucena Falcão, Alisson Vasconcelos Brito, Alexandre Nóbrega Duarte

Departamento de Informática – Universidade Federal da Paraíba (UFPB)

{eduardolfalcao, alisson.brito, alexandrend}@gmail.com

Abstract. Operations of matrix multiplications are widely used in scientific

applications, and commonly have huge dimensions. Another problem derived

of the first it’s the matrix-chain multiplications, which also has scientific

applicability. Thus, efficient algorithms for matrix multiplications (or matrix-

chains) are extremely useful, as also are new approaches or even distributed

versions of already known algorithms. The present work aims at analyzing

some approaches for the solution of the matrix-chain multiplications problem,

implement it and measure their runtime to analyse the efficacy of the same.

1. Introdução

Desde 1946, com a criação do primeiro computador eletrônico para fins genéricos (o

ENIAC), pode-se perceber a rápida evolução dos processadores ao longo de décadas

[Koomey et al 2009]. A principal razão para tal é a evolução tecnológica que permite

cada vez mais a construção de transistores sempre menores e mais baratos, de tal modo

que mais ou menos a cada dois anos seu número dobrasse nos processadores, seguindo

uma tendência conhecida como Lei de Moore [Schaller 1997].

A rápida evolução dos processadores já é um fator que constantemente tem

tornado a execução de programas mais eficiente. Contudo, o aumento da velocidade dos

processadores é apenas um dos fatores que podem elevar o desempenho de um

programa e, além disto, é limitado por outros fatores que têm influência direta nesta

melhoria, dentre eles, a memória [Alted 2010]. De nada adianta ter processadores super

velozes, se a memória não é rápida o suficiente para fornecê-los dados para

processamento sem que eles fiquem ociosos. Deste modo, foi preciso adotar uma nova

estratégia para diminuir o tempo de espera do processador: a memória cache.

A memória cache é um tipo bastante rápido de memória que serve para

armazenar os dados mais frequentemente usados pelo processador, evitando na maioria

das vezes que ele tenha que recorrer à “lenta” memória RAM (Random Access

Memory). É interessante perceber o funcionamento da memória cache com o objetivo

de usá-las da maneira mais eficiente possível, e.g. tentar minimizar o cache miss.

Além de aspectos de hardware como frequência do processador e tamanho da

memória, é importante utilizar as estruturas de dados e técnicas de algoritmos que mais

se adéquam ao estilo de problema a ser resolvido. Adicionalmente, podemos perceber

que as escolhas de ferramentas, Linguagens de Programação (LP), e APIs (Application

Programer Interface), também podem ter certo impacto no desempenho da solução.

O objetivo do presente trabalho é tornar evidentes os vários fatores que podem

influenciar no desempenho de um programa:

utilizar a memória cache de maneira inteligente;

estruturas de dados e técnicas de programação mais adequados ao problema;

ferramentas e LPs a serem utilizadas.

Para tal, será apresentado o problema da Multiplicação de Cadeias de Matrizes

explicado no tópico abaixo, avaliando seu tempo de execução quando projetado de

diferentes modos.

2. O Problema da Multiplicação de Cadeias de Matrizes

No problema da multiplicação de cadeias de matrizes, recebe-se como entrada uma

cadeia de n matrizes, e retorna-se o produto delas. É fácil perceber,

que por motivos da lógica da multiplicação de matrizes que a matriz deve ter número

de linhas igual ao número de colunas da matriz .

O problema em sua essência é trivial, pois se multiplicarmos sequencialmente as

n matrizes obteremos facilmente o resultado esperado. O maior desafio que reside neste

problema é otimizar o desempenho do programa que o resolve. Para tal, podemos

explorar técnicas de programação aplicadas ao problema específico, além de buscar

sempre explorar o processamento máximo do computador de maneira inteligente.

3. O Problema do Cache Miss

O cache miss acontece quando o processador necessita de um dado, e este não

está na memória cache. Tal fato obriga o processador a buscar um bloco de dados –

constituído por um número fixo de palavras - diretamente na memória RAM, trazendo-

os para a memória cache e em seguida fornecendo a palavra requerida ao processador.

Em razão do fenômeno da localidade espacial, quando um bloco de dados é

trazido para a memória cache para satisfazer uma dada referência à memória, é provável

que futuras referências sejam feitas para outras palavras desse bloco (Figura 1)

[Stallings 2010]. Sendo assim, é fácil perceber que quando acontece vários cache miss

na execução de um programa, seu desempenho tenderá a cair. Os programadores podem

utilizar a propriedade da localidade espacial dentre outras relacionadas ao

funcionamento da memória cache no intuito de minimizar os cache miss e tornar a

execução dos programas mais rápidos.

Um exemplo simples que comprova tal fato é o problema da soma de todos os

elementos de uma matriz. Se para somar todos os elementos de uma matriz o algoritmo

percorrer as colunas ao invés das linhas, haverá maior probabilidade de ocorrer o cache

miss. Para comprovar este fato, foi implementado um programa simples na LP Java, que

mede o tempo de execução das duas formas de se percorrer uma matriz quadrada de

tamanho 10000. Ao percorrer as colunas o programa executou em 2886 milissegundos,

e ao percorrer as linhas o programa executou em 53 milissegundos. Podemos perceber

que quando minimizamos o cache miss tivemos um speedup superior a 50 vezes.

A Figura 1 ilustra o fenômeno da localidade espacial ocorrendo no problema da

soma dos elementos de uma matriz. Quando o primeiro elemento da matriz ( ) é

buscado para efetuar a soma, o processador buscará um bloco de dados sequencial (uma

linha do array, ou parte dela) para a memória cache. Se forem percorridas as linhas da

matriz, provavelmente os próximos elementos a serem somados (representados através

da cor verde e amarela na Figura 1) estarão na memória cache, o que ocasiona um cache

hit, tornando o acesso ao dado mais rápido. Se forem percorridas as colunas, há maior

probabilidade de que os próximos elementos a serem somados (vermelho) não estejam

na memória cache, ocorrendo um cache miss.

Figura 1 – Ilustração do fenômeno da localidade espacial.

4. Análise e Detalhamento de Possíveis Soluções para o Problema de

Multiplicação de Cadeias de Matrizes

Neste tópico serão descritas algumas abordagens possíveis para a solução deste

problema, que em alguns casos são complementares e em outros são antagônicas.

4.1. Abordagem Sequencial

Na abordagem sequencial multiplicam-se sequencialmente as n matrizes para obter seu

produto. Por exemplo, para uma cadeia com quatro matrizes a ordem de multiplicação

seria a seguinte: . O código da Tabela 1 recebe duas matrizes A e B

como entrada, e retorna a matriz C como resultado da multiplicação entre A e B. A

partir da Tabela 1 pode-se perceber que a complexidade para realizar a multiplicação

dessas duas matrizes é , sendo n relativo ao tamanho das matrizes (linhas e

colunas). Logo, para t matrizes tem-se que a complexidade é .

Tabela 1 – Código para multiplicação de duas matrizes. 1 for(int i=0; i<a.length ;i++){

for(int j=0; j<b[0].length ;j++){ c[i][j] = 0; for(int k=0; k<a[0].length ;k++) c[i][j] += a[i][k] * b[k][j]; } }

2

3

4

5

6

7

4.2. Abordagem com Programação Dinâmica

Analisando mais cuidadosamente o código da Tabela 1, pode-se perceber que o

número de multiplicações escalares relacionadas à multiplicação de duas matrizes

respeita o cálculo exibido na Figura 2. O referente à multiplicação pode ser

descrito de maneira mais detalhada por . Sendo assim, pode-se observar que a ordem com que as matrizes são

multiplicadas pode tornar o programa mais eficiente, ou seja, reduzir o número de

multiplicações.

Figura 2 – Quantidade de multiplicações escalares para a multiplicação de duas

matrizes. Adaptado de [Cormen et al 2002].

Por exemplo, para multiplicar uma cadeia de matrizes contendo três matrizes

existem duas parentizações possíveis. A Tabela 2 exibe as possíveis parentizações para

a seguinte cadeia com três matrizes: .

Tabela 2 – Possíveis ordens de multiplicação para uma cadeira com três matrizes.

1 2

A partir do cálculo fornecido pela Figura 2, é possível verificar que a ordem de

multiplicação das matrizes da linha 1 da Tabela 2 realiza 75000 multiplicações

escalares, ao passo que a ordem da linha 2 resulta em apenas 7500. Deste modo, Pode-

se perceber que para a multiplicação da cadeia já citada, apenas a ordem de

multiplicação das mesmas pode gerar um speedup de 10 vezes. É interessante perceber

que para o exemplo anterior a abordagem sequencial (4.1) é a mais rápida. Mas, deve

ser ressaltado que isso foi apenas uma coincidência, e que a probabilidade da

abordagem sequencial ser a mais rápida torna-se bastante remota quando o número de

matrizes da cadeia aumenta, o que proporciona um ganho expressivo quando se utiliza a

abordagem com a parentização otimizada.

Mas como proceder para encontrar a parentização otimizada? Através da força

bruta, o número de soluções seria exponencial em n ( ), sendo n o número de

multiplicações, tornando essa verificação inviável [Cormen et al 2002]. Uma alternativa

viável para este problema é a utilização da estratégia de Programação Dinâmica.

A Programação Dinâmica (PD) geralmente é aplicada a problemas de

otimização, ou seja, problemas que possuem várias soluções, mas deseja-se encontrar

uma solução ótima, como é o caso do corrente problema. Para aplicar a PD ao problema

da multiplicação de cadeias de matrizes são necessárias quatro etapas: caracterizar a

estrutura de uma solução ótima, que nesse caso é a estrutura de uma colocação ótima

dos parênteses; definir recursivamente o valor de uma solução ótima para o problema;

calcular o valor de uma parentização ótima; construir a solução ótima a partir das

informações coletadas. Mais detalhes sobre descrição e implementação desse problema

através da PD são fornecidos em [Cormen et al 2002].

4.3. Abordagem com Minimização de Cache Miss

O tópico 3 explicou alguns detalhes quanto a ocorrência de cache miss. Com relação ao

problema de multiplicação de matrizes, deve-se primeiramente ressaltar que a própria

natureza de seu algoritmo o faz mais suscetível à ocorrência de cache miss. Pois é

sabido que para multiplicar duas matrizes, deve-se percorrer a linha da primeira e a

coluna da segunda, e quando se percorre a coluna de uma matriz a probabilidade de

ocorrência do cache miss aumenta (vide Tópico 3).

A Tabela 1 exibe o código referente a um algoritmo tradicional para

multiplicação de matrizes. Nesse código o algoritmo sempre preencherá linha por linha

da matriz resultante. Este comportamento do algoritmo requer que o processador faça a

multiplicação de uma linha da primeira matriz com todas as colunas da segunda matriz.

Baseado no funcionamento do algoritmo, observou-se que é possível minimizar

a ocorrência do cache miss invertendo as linhas 1 e 2 da Tabela 1 (quando pertinentes),

com o objetivo de que o programa reutilize dados previamente armazenados na

memória cache. Pensou-se o seguinte (Tabela 3): se a quantidade de linhas da primeira

matriz é maior que a quantidade de linhas da segunda matriz, deve-se manter o código

da Tabela 1, caso contrário, devem ser invertidas as linhas 1 e 2 da Tabela 1. Com essa

verificação, o algoritmo sempre percorrerá a “maior linha possível”, o que minimiza o

cache miss.

Tabela 3 – Código proposto para minimização do cache miss. if(a.length > b.length) <Código da Tabela 1> else <Código da Tabela 1 com linhas 1 e 2 invertidas>

Outra maneira de se reduzir o cache miss para o problema da multiplicação de

matrizes seria multiplicar a primeira matriz pela matriz transposta da segunda. Pode-se

perceber que para isto seria necessário mudar o código relativo à multiplicação das

matrizes: ao invés de multiplicar linhas da primeira matriz por colunas da segunda,

multiplicar-se-iam linhas da primeira matriz por linhas da segunda (Figura 3), o que

implicaria numa redução significativa do cache miss. Para evitar um custo adicional

para o cálculo da transposta da segunda matriz, poderia apenas ser alterado o método de

criação das mesmas para já criá-las como sendo suas próprias transpostas.

A Figura 3 exemplifica a multiplicação tradicional com uma matriz

convencional, e a multiplicação proposta com a matriz transposta. As linhas coloridas

representam os cálculos relativos à primeira linha da matriz resultante:

Linhas vermelhas: multiplicar linha 1 da primeira matriz com colunas 1, 2, ..., n

da segunda matriz;

Linhas azuis: multiplicar linha 1 da primeira matriz com linhas 1, 2, ..., n da

segunda matriz.

Figura 3 – Multiplicação convencional, e multiplicação com matrizes transpostas.

4.4. Abordagem Distribuída com Threads

A abordagem distribuída utilizando threads visa explorar a potencialidade máxima dos

processadores atuais, que geralmente possuem mais de um núcleo físico e/ou lógico.

Contudo, será explicado adiante o porquê da abordagem distribuída com threads

utilizada no presente trabalho não caracterizar uma solução ótima, apesar de explorar a

capacidade máxima do hardware.

A estratégia utilizada para esta abordagem divide a cadeia

pelo número de threads a serem criadas. Desse modo, cada thread fica encarregada de

realizar a multiplicação de uma sub-cadeia, e ao final, quando todas terminarem sua

execução, a thread principal realizará a multiplicação das matrizes resultantes. Como

exemplo, considere uma cadeia com doze matrizes ( ) utilizando a

abordagem distribuída com duas threads. Esta cadeia seria quebrada ao meio em duas

sub-cadeias e , e depois passaria pelo processo de

se encontrar a parentização ótima através da estratégia de PD. Porém, é fácil perceber

que a parentização ótima para a cadeia muito dificilmente será

alcançada com a divisão da cadeia. Para alcançarmos tanto a parentização ótima e ainda

explorar a capacidade máxima do processador outra estratégia deve ser utilizada, como

por exemplo, a abordagem distribuída utilizando a biblioteca OpenMP.

4.5. Abordagem Distribuída com OpenMP

A abordagem distribuída utilizando a biblioteca OpenMP (Open Multi-Processing) não

divide a cadeia de matrizes em sub-cadeias, e portanto, mantém a parentização

otimizada encontrada através da abordagem por PD. Ao invés disso, utilizam-se

diretivas em trechos de código que são interpretadas pelo compilador, e que ao executar

o programa, ativam as threads dos processadores de acordo com as mesmas. Portanto, o

trecho de código que se pretende distribuir deve ser minuciosamente estudado para que

nenhuma violação lógica ou física seja cometida.

Para o problema da multiplicação de matrizes, foi percebido que os elementos da

matriz resultante não possuem interdependências, o que possibilita a paralelização desse

trecho de código, mais especificamente do loop for da linha 1 na Tabela 1. Deste modo,

o código ficaria como apresentado abaixo na Tabela 4.

Tabela 4 – Paralelizando com a biblioteca OpenMP. #pragma omp parallel for <Código da Tabela 1>

A biblioteca OpenMP usa o modelo de paralelismo fork-and-join, que ramifica a

thread principal em threads paralelas, e quando estas terminam de executar, a thread

principal reassume o controle do programa [Chandra et al 2001]. Existem diversas

diretivas da biblioteca OpenMP que permitem os programadores tornarem seus

programas distribuídos. A diretiva que foi utilizada na Tabela 4 atua de forma simples,

ela subdivide a quantidade total de iterações no loop for pelo número de threads a serem

utilizadas, e cada thread executará uma parte das iterações que antes eram executadas

por apenas uma thread. No problema da multiplicação de matrizes, se a matriz

resultante tiver 10 linhas, e for especificado que o processador deve trabalhar com duas

threads, a primeira computará o produto das 5 primeiras linhas da matriz resultante, e a

segunda computará as linhas restantes (Figura 4).

Figura 4 – Multiplicação com abordagem não-distribuída e distribuída.

5. Resultados

Para avaliar algumas das abordagens supracitadas pensou-se em realizar cinco

experimentos, aliando diferentes algoritmos e técnicas de programação. As cinco

estratégias são citadas abaixo, visando a cada novo experimento implementado

melhorar o desempenho do programa.

1. Linguagem de Programação Java:

a) Abordagem sequencial, maximizando o cache miss;

b) Utilizando técnicas de PD, maximizando o cache miss;

c) Utilizando técnicas de PD, minimizando o cache miss;

d) Utilizando técnicas de PD, minimizando o cache miss, além de tornar a lógica do

algoritmo distribuída:

i. Em 2 Threads;

ii. Em 4 Threads;

“Maximizar o cache miss” tem o objetivo de tornar mais evidente a ocorrência

do mesmo, e prover uma noção de tempo desperdiçado quando o mesmo ocorre. Para

tal, as linhas 1 e 2 da Tabela 1 devem ser invertidas com a lógica inversa da Tabela 3.

Para minimizar o cache miss foi utilizada o código presente na Tabela 3. E para tornar a

lógica do algoritmo distribuído foi utilizada a abordagem explanada no tópico 4.4. Para

fins de padronização as matrizes foram preenchidas com 1’s.

Para tais experimentos, foi utilizado um notebook Dell Vostro 3450, Sistema

Operacional Windows 7 Professional Service Pack 1 de 64 Bits, 4 GB de memória

RAM, processador Intel® Core™ i5-250M de 2.5 GHz.

A cadeia de matrizes escolhida para os experimentos foi a seguinte:

<7000,50,30,5000,32,40,5000,80,20,4000,20,10,1000,50>, o que equivale às matrizes

. Pode-se perceber que todas as matrizes da

cadeia possuem o número de linhas muito superior ao número de colunas, ou justamente

o inverso, pois a ocorrência de cache miss torna-se mais acentuada nesses casos.

A Figura 5 exibe o gráfico com o resultado dos experimentos propostos. A

legenda na direita corresponde aos experimentos descritos anteriormente.

Figura 5 – Resultados do experimento na LP Java.

Pode-se observar que a diferença de desempenho da abordagem que usa PD para

a sequencial é deveras significante (25.8 segundos), um fato esperado e descrito nos

tópicos 4.1 e 4.2 do tópico. Analisando o resultado dos experimentos 1.b e 1.c, pode-se

notar que quando é utilizada uma estratégia de minimização de cache miss (descrita no

tópico 4.3) para o problema, obteve-se 4.7 segundos de speedup, que representa uma

evolução de quase 50%. É importante ressaltar que quando o tamanho da cadeia

aumenta, essa disparidade também tende a aumentar. Por último, ao analisar a estratégia

distribuída (descrita no tópico 4.4), pode-se perceber que tanto a 1.d quanto 1.e,

utilizando 2 e 4 threads respectivamente, apresentaram perda de desempenho. No tópico

4.4, já se havia cogitado a possibilidade dessa ocorrência devido à perda de parentização

ótima. Porém, é de se esperar que esta abordagem apresente ganho de desempenho para

determinadas cadeias de matrizes, principalmente quando o número de matrizes cresce.

0

20

40 36,7

10,9 6,2 6,6 6,4

1.a

1.b

1.c

1.d

5. Conclusão

O objetivo do presente trabalho foi mostrar a importância de dominar técnicas

relacionadas a projeto de algoritmos, e também conceitos de arquitetura de

computadores para obter melhor desempenho do software e hardware. Ao utilizar a

técnica de PD aliada à minimização de cache miss, obteve-se um speedup de 6x em

relação ao desempenho da solução mais simples (sequencial). É interessante perceber

que todos os algoritmos estão na mesma ordem de complexidade de tempo ( ), e

mesmo assim foram obtidos ganhos de desempenho.

Destes resultados, pode-se colher como aprendizado, que ao receber um

problema é necessário estudá-lo, visualizá-lo de diferentes perspectivas para adotar a

estratégia de solução mais eficiente. Para tal, devem ser analisados os algoritmos

pertinentes, ferramentas (APIs, bibliotecas, etc.) e LPs a serem utilizadas, além de

conceitos sobre funcionamento de software/hardware, de sistemas operacionais e da

arquitetura do computador de uma forma generalizada.

7. Trabalhos Futuros

Como possibilidades para trabalhos futuros, pode ser considerada a implementação das

abordagens já citadas na LP C++, uma vez que geralmente os programas escritos nessa

LP tendem a ter melhor desempenho que em Java. Além disso, a abordagem descrita no

tópico 4.5 parece ser a mais eficiente. O fato de aproveitar o desempenho da LP C++,

realizando a distribuição do algoritmo em quantas threads desejar, mantendo a

parentização ótima alcançada pela PD, e minimizar a ocorrência de cache miss com a

abordagem da matriz transposta, aparenta ser a melhor solução analisada no presente

trabalho. Outra tarefa interessante seria implementar os algoritmos para multiplicação

de matrizes desenvolvidos por Strassen , que possui complexidade de , ou o

desenvolvido por Coppersmith e Winograd com ordem de complexidade , aliando à alguma abordagem de minimização de cache miss para comparação dos

resultados [Robinson 2005].

Referências

Koomey, J. G., Berard, S., Sanchez, M., Wong, H. (2009) “Assessing Trends in the

Electrical Efficiency”. Final report to Microsoft Corporation and Intel Corporation.

Schaller, R. R. “Moore's law: past, present and future”. (1997) IEEE Spectrum, Vol 34,

pp. 52-59.

Alted, F. “Why Modern CPUs are Starving and what can be done about it”. (2010)

Computing in Science & Engineering, pp. 68–71.

Stallings, W. “Arquitetura e Organização de Computadores”. (2010) Editora Prentice

Hall, pp. 122-144.

Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C. “Algoritmos: Teoria e Prática”.

(2002) Editora Campus, pp. 259-295.

Chandra, R., Dagum, L., Kohr, D., Maydan, D., McDonald, J., Menon, R. “Parallel

Programming in OpenMP”. (2001) Editora Morgan Kaufmann.

Robinson, S. “Toward an Optimal Algorithm for Matrix Multiplication”. (2005) Society

for Industrial and Applied Mathematics. Vol. 38, Nº 9.