Explorando o Paralelismo com Matrizes

Prévia do material em texto

1 
 
Explorando o Paralelismo com Matrizes 
Organização de Computadores – CC53B 
 
Eduardo Carvalho Nunes RA: 1547542 
01 de dezembro de 2016 
 
1 Introdução 
A obtenção de alto desempenho não depende 
somente em utilizar dispositivos de hardware 
mais rápidos, mas também em melhorias de 
arquiteturas e técnicas de processamentos. 
Arquiteturas avançadas de computadores 
estão baseadas no conceito de processamento 
paralelo: pipeline, arranjo de processadores e 
multiprocessadores. Processadores paralelo é 
uma forma eficiente de processamento de 
informação que explora eventos no processo 
de computação. 
 Mecanismo de processamento paralelo 
foram desenvolvidas para computadores com 
um único processador: múltiplas unidades 
funcionais, paralelismo e pipeline dentro da 
CPU, superposição das operações da CPU e 
de entrada/saída, hierarquia de memória e 
multiprogramação e compartilhamento de 
tempo. Muitas das funções da ALU podem ser 
distribuídas em unidades funcionais 
especializadas que podem operar em paralelo. 
 Veja a figura abaixo e considere os 
processos P1, P2 e P3, realizando operações 
de entrada e saída e computação. 
 
 Multiprogramação e compartilhamento 
de tempo são soluções de software para obter 
concorrência num sistema com um 
processador. Dentro de um mesmo intervalo 
de tempo podem haver múltiplos processos 
ativos no computador, competindo por 
recursos de memória, entrada/saída e CPU. 
Multiprogramação consiste do intercalamento 
de programas, permitindo melhor utilização 
dos recursos através de superposição das 
operações de entrada/saída e da CPU. 
 Compartilhamento de tempo consiste 
em atribuir fatias iguais ou variáveis do tempo 
de CPU para vários programas, evitando que 
um determinado programa venha ocupar a 
CPU por um tempo muito longo. 
 
 
2 Desenvolvimento 
Foi desenvolvido dois (2) programas com a 
linguagem C para a resolução deste trabalho. 
Os programas foram compilados em um 
computador que possui quatro (4) núcleos, 
com processador Intel® Core™ i3-2365M e 
1.40GHz. O sistema operacional utilizado foi 
Linux/ubuntu 16.04 64bits. Os testes foram 
projetados no gcc 5.04, o comando time para 
exibir o tempo de execução. Para elaboração 
dos gráficos foi utilizado o Excel 2016 com 
base dos valores obtidos do comando time. 
 Em ambos programas elaboramos 
dezoito (18) testes com as seguintes matrizes 
quadradas: 10x10, 50x50, 100x100, 200x200, 
300x300, 400x400, 500x500, 600x600, 
700x700, 800x800, 900x900, 1000x1000, 
1100x1100, 1200x1200x, 1300x1300, 
1500x1500, 2000x2000 e 3000x3000. 
O primeiro programa cujo o nome do 
arquivo é matrizSequencial.c tem como 
objetivo multiplicar duas matrizes quadradas 
2 
 
de maneira sequencial. O segundo programa 
cujo o nome do arquivo é matrizThread.c 
também tem como objetivo multiplicar duas 
matrizes quadradas explorando o paralelismo 
usando thread. 
Ambos programas tem o procedimento 
que aloca memória para uma matriz. O 
procedimento recebe dois parâmetros inteiros 
e retorna um endereço da alocação, caso não 
conseguir alocar memória, retorna NULL. Veja 
a imagem abaixo o procedimento 
alocar_matriz.
 
 O programa matrizSequencial.c é bem 
simples, tem quatro (4) for. Os dois primeiros 
for preenche a matriz, o terceiro for multiplica a 
matriz 1 e 2 e guarda na matriz3, e por último 
um for para exibir a matriz resultante. 
 
Já o programa matrizThread.c não é tão 
simples como foi o matrizSequencial.c. O 
programa matrizThread.c tem quatro (4) 
procedimentos que são: multiplica, 
alocar_matriz, preenche e imprime. Foi 
utilizado a biblioteca pthread.h. 
O procedimento multiplica é a função 
que multiplica matriz A e B de modo paralelo 
usando thread. 
 
 O procedimento preenche tem como 
objetivo de preenche a matriz com números um 
(1).
 
 O procedimento imprime tem como 
objetivo imprimir uma matriz. 
 
Já na main foi declarado no início os 
parâmetros do pthtead e em seguida a 
chamada para preencher a matriz A e B. 
 
Depois das matrizes preenchidas, 
criamos as threads. Se houver erro na criação 
da thread o programa para de executar. Cada 
multiplicação, cria-se uma thread. 
 
Por fim imprime a matriz resultante e 
executa o exit do pthread. 
 
 
3 
 
3. Resultados 
Como foi citado na secção anterior, foi feito 
dezoito (18) testes com matrizes quadradas. 
Nesta secção vamos mostrar uma tabela com 
tempo real do programa sequencial e paralelo, 
também alguns gráficos e uso dos núcleos pelo 
software htop. 
 Veja a tabela abaixo em tempo real de 
execução de cada multiplicação de matriz 
quadrada nxm. 
 Sequencial Thread 
Matriz 10x10 0m0.002s 0m0.005s 
Matriz 50x50 0m0.005s 0m0.008s 
Matriz 100x100 0m0.022s 0m0.017s 
Matriz 200x200 0m0.111s 0m0.066s 
Matriz 300x300 0m0.332s 0m0.192s 
Matriz 400x400 0m0.844s 0m0.451s 
Matriz 500x500 0m1.691s 0m0.881s 
Matriz 600x600 0m2.953s 0m1.720s 
Matriz 700x700 0m4.876s 0m2.912s 
Matriz 800x800 0m9.056s 0m4.207s 
Matriz 900x900 0m13.289s 0m6.136s 
Matriz 1000x1000 0m20.550s 0m8.848s 
Matriz 1100x1100 0m24.542s 0m11.741s 
Matriz 1200x1200 0m24.730s 0m11.958s 
Matriz 1300x1300 1m6.067s 0m29.546s 
Matriz 1500x1500 1m7.945s 0m31.588s 
Matriz 2000x2000 3m2.986s 1m19.482s 
Matriz 3000x3000 10m53.395s 5m26.309s 
 Veja em seguida as comparações em 
milésimos de segundo através de gráficos a 
seguir. 
 
 
 Os gráficos de colunas foi divido em 
duas partes e até matriz 1500x1500 para que 
seja mais fácil a visualização dos resultados. 
Agora vejamos o próximo gráfico modelo de 
linha a seguir. 
 
 Observando os resultados através da 
tabela e gráficos concluí se que o programa 
sequencial é mais lento que o thread. Na 
próxima imagem veremos através do htop o 
programa sequencial sendo executado, pode 
se observar que o programa sequencial 
somente está usando um (1) núcleo. 
 
 
 
 Lembrando que o computador utilizado 
para realizar este trabalho, contém quatro (4) 
núcleos, na imagem acima o programa 
sequencial utiliza o segundo núcleo com 100%. 
Agora vendo a imagem abaixo o programa 
paralelo com thread utiliza os quatro (4) 
núcleos com 100%. 
 
4 
 
4. Referência 
1. Paralelismo. Disponível em:< 
http://www.eng.uerj.br/~ldmm/Arquitetur
as_de_Alto_Desempenho/Paralelismo.
pdf>. Acesso em 30/11/2016. 
 
2. Paralelismo Computadores de alto-
desempenho são utilizados em diversas 
áreas. Disponível em: 
<http://docplayer.com.br/2093230-
Paralelismo-computadores-de-alto-
desempenho-sao-utilizados-em-
diversas-areas.html>. Acesso em: 
30/11/2016. 
 
3. Monitorando processos no Linux com o 
Htop. Disponível em:< 
https://www.vivaolinux.com.br/artigo/Mo
nitorando-processos-no-Linux-com-o-
Htop>. Acesso em 01/12/2016. 
 
4. POSIX Threads. Disponível em:< 
https://pt.wikipedia.org/wiki/POSIX_Thr
eads>. Acesso em 29/11/2016. 
 
5. Pthread. Disponível em:< 
http://pubs.opengroup.org/onlinepubs/7
908799/xsh/pthread.h.html>. Acesso 
em 29/11/2016. 
 
6. Programação Paralela em Arquiteturas 
Multi-Core/ Programação em Pthreads. 
Disponível em:< 
https://pt.wikibooks.org/wiki/Programa%
C3%A7%C3%A3o_Paralela_em_Arquit
eturas_Multi-
Core/Programa%C3%A7%C3%A3o_e
m_Pthreads>. Acesso em: 29/11/2016.