Introdução a Sistemas Distribuídos

Estudando o Problema a ser Resolvido

Eduardo de Lucena Falcão

Introdução

● Na maioria das vezes, qual a nossa atitude quando nos deparamos com um problema de programação?

Otimização do Programa

Em ordem de importância:

1. O algoritmo: estruturas de dados e técnicas de algoritmos mais adequadas ao problema;

2. Software: Linguagens de Programação e APIs;

3. Hardware: frequência do processador, e capacidade de memória.

*1 única instância de processamento

Otimização do Programa

● Preciso melhorar ainda mais meu tempo de execução!

● Tornar distribuído o algoritmo que já era paralelo.

– Ex.: Map-Reduce

Objetivo da Aula

● Exemplo Prático de um problema simples

– Multiplicação de Cadeias de Matrizes● Multiplicação de Matrizes

● Tornar evidente em números, o que a análise e estudo do problema pode nos proporcionar (tempo de execução).

● Efeito bola de neve! (quando não tiramos maior proveito de nosso algoritmo)

O Problema da Multiplicação de Cadeias de Matrizes

● Entrada: cadeia com n matrizes

● Saída: matriz resultante do produto das n matrizes

● 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.

Lembrando...

● Multiplicação de matrizes:

– A[m,n] X B[n,o] = C[m,o]

A[3,2]

1 4

2 5

3 6

B[2,4]7 9 11 13

8 10 12 14

C[3,4]

Lembrando...

A[3,2]

1 4

2 5

3 6

B[2,4]7 9 11 13

8 10 12 14

C[3,4]

1*7 + 4*8

2*7 + 5*8

3*7 + 6*8

● Multiplicação de matrizes:

– A[m,n] X B[n,o] = C[m,o]

Lembrando...

● Multiplicação de matrizes:

– A[m,n] X B[n,o] = C[m,o]

A[3,2]

1 4

2 5

3 6

B[2,4]7 9 11 13

8 10 12 14

C[3,4]

39 49 59 69

54 68 82 96

69 87 105 123

Abordagem Sequencial

● Multiplicam-se sequencialmente as n matrizes para obter seu produto.

● Ex.: para uma cadeia com quatro matrizes a ordem de multiplicação seria: .

● Complexidade:

– , sendo n o tamanho (linha de A, coluna de A, coluna de B)das matrizes.

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];

}

}

E o problema do 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 –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. [Stallings 2010]

E o problema do Cache Miss?

● Soma de todos os elementos de uma matriz quadrada de tamanho 10000 (Java):– Percorrendo as linhas: 53 ms;

– Percorrendo as colunas: 2886 ms.

● Speedup superior a 50 vezes.

E o que o Cache Miss interfere em nosso problema?

● Onde há matrizes *pode* haver cache miss;

● Sempre devemos ficar atentos quando estivermos trabalhando com matrizes, objetivando o cache hit;

● É natural que ocorra o cache miss para o problema de multiplicação de matrizes, pois é inerente a seu algoritmo;

● Mas é possível *tentar* burlar o cache miss para este problema de algumas maneiras.

Abordagem com Minimização de Cache Miss

● Que tal 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, 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.

Quanto às *Cadeias* de Matrizes?

● Quanto às cadeias: o que podemos fazer para otimizar nosso programa?

– Resp.: utilizar a Programação Dinâmica

● Analisando mais cuidadosamente o código da multiplicação de matrizes, pode-se perceber que o número de multiplicações escalares relacionadas à multiplicação de duas matrizes respeita o seguinte cálculo:

Abordagem com Programação Dinâmica

● 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.

● Por ex., para multiplicar uma cadeia de matrizes contendo três matrizes existem duas parentizações possíveis.

– Ex.: Ordem de mult. Nº de mult. escalares

1 75000

2 7500

Abordagem com Programação Dinâmica

● Speedup de 10x. É interessante perceber que para o exemplo anterior a abordagem sequencial é 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.

Ordem de mult. Nº de mult. escalares

1 75000

2 7500

Abordagem com Programação Dinâmica

● Mas como proceder para encontrar a parentização otimizada?

● Através da força bruta, o nº 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].

Abordagem Paralela com Threads

● A abordagem paralela 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, a abordagem paralela com threads apresentada aqui não caracteriza 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.

Abordagem Paralela com Threads

● 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 paralela utilizando a biblioteca OpenMP.

Abordagem Paralela com OpenMP

● A abordagem paralela 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.

Abordagem Paralela com OpenMP

● 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.

# pragm a om p parallel for

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];

}

}

Abordagem Paralela com OpenMP

● 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 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.

Resultados

● 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

Resultados

● Linguagem de Programação Java:

a) Abordagem sequencial;

b) Utilizando técnicas de PD;

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 paralela em 2 Threads;

e) Utilizando técnicas de PD, minimizando o cache miss, além de tornar a lógica do algoritmo paralela em 4 Threads.

0

5

10

15

20

25

30

35

40 36,7

10,9

6,2 6,6 6,4

Qual o Aprendizado?

● O objetivo dessa aula 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.

Qual a aplicação disso em nosso curso?

● Devemos sempre tentar fazer o mesmo antes de partir para a estratégia Distribuída!

● Caso contrário, todos esses segundos ou milissegundos que se acumularam, se tornarão uma bola de neve quando milhares de requisições forem feitas a seu sistemas.

● E isso lhe custará dinheiro, muito dinheiro!!

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.

Dúvidas