1ª Questão - Avaliar a soma:

Universidade Federal de Minas Gerais

Departamento de Ciência da Computação

Pós-Graduação em Ciência da Computação

PROJETO E ANÁLISE DE ALGORÍTMOS

Profº Nívio Ziviani

4º Trabalho

José Pinheiro de Queiroz Neto

Belo Horizonte - MG

2002

Computação Paralela

1. Introdução

A Computação Paralela é uma das áreas de pesquisa em Ciência da Computação que visa aperfeiçoar e desenvolver algoritmos que possam utilizar de forma eficiente os recursos de uma máquina paralela. Os resultados destas pesquisas tem-se mostrado de extrema importância para execução de tarefas com grande massa de dados e alto custo computacional, como no caso de simulações de experimentos científicos de diversas áreas de pesquisa. Este trabalho consiste em apresentar um projeto e implementação consistentes de um algoritmo paralelo para o cálculo da multiplicação de duas matrizes, a ser executado em uma máquina paralela do tipo multicomputador, utilizando sockets para a comunicação entre os processos. Além de uma análise dos algoritmos, são apresentados estudos comparativos de ganho de speedup para 2, 4 e 8 processadores, gerando resultados consistentes que comprovam a eficácia do algoritmo paralelo implementado.

2. Aplicações e Motivação

Existem diversos campos de aplicação da computação paralela, e sua grande maioria se encontra em simulações e cálculos de experimentos científicos voltados à ciência, isto porque muitos dos problemas científicos são tão complexos que resolvê-los através de simulação numérica requer um extraordinário poder computacional, somente obtido em máquinas paralelas, e se encontram em diversas áreas, tais como [Quinn 94]:

Química Quântica, Estatísticas da Mecânica, e Física Relativista;
Cosmologia e Astrofísica;
Dinâmica dos Fluídos e Turbulência;
Projeto de Materiais e Supercondutividade;
Biologia, Farmacologia, Sequência do Genoma, Engenharia Genética, Cadeias de Proteínas, Atividade Enzimática, e Modelagem de Células;
Medicina, Modelagem de órgãos e ossos humanos;
Clima Global e Modelagem de Meio Ambiente.

Além de toda esta gama de aplicações, outro forte motivo para o uso da computação paralela encontra-se na própria Ciência da Computação, pois esta ferramenta é de fundamental importância para a solução em tempo hábil de problemas de otimização, processamento de imagens de grande porte, processamento de grandes massas de dados, entre outros. Neste trabalhos trataremos de um problema específico, como forma de demonstrar os principais pontos que envolvem a computação paralela.

3. Especificação do Problema

Dadas uma matriz A[m₁][n₁] , uma matriz B[m₂][n₂] e um conjunto de p processadores contidos em máquinas interligadas em rede, tais que n₁=m₂ , para m₁,n₁,m₂,n₂ 0. O problema consiste em encontrar a matriz C[m₁][n₂] = A[m₁][n₁] x B[m₂][n₂], através do projeto e implementação de um algoritmo paralelo utilizando os p processadores, visando reduzir o tempo de execução do processo de forma a obter um ganho de speedup.

4. Algoritmo Paralelo

4.1 Arquitetura

O algoritmo Paralelo, desenvolvido a partir de [Quinn 94], possui arquitetura do tipo MIMD (Multiplie Instruction Multiple Data), utilizando memória distribuída, onde cada processador possui sua própria memória e utiliza a rede para se comunicar com outros processadores via troca de mensagens, configurando uma máquina paralela do tipo multicomputadores utilizando uma NOW (Network Of Computers).

As trocas de mensagens ocorrem entre o módulo que distribui as tarefas e recolhe os resultados, denominado cliente, e os módulos que recebem os dados e efetuam o processamento, denominados escravos. Este é um tipo de arquitetura onde vários processadores trabalham em sincronismo com uma massa de dados distribuída, aplicando nesta o mesmo processamento e retornando o resultado parcial de cada um para a composição do resultado final. A figura 1 ilustra a arquitetura utilizada.

Figura 1

4.2 Os Módulos Cliente e Escravo

O algoritmo paralelo possui dois módulos distintos, o cliente e o escravo. O algoritmo do módulo cliente pode ser pode ser resumido nos seguintes passos:

Gerar as matrizes A e B para a realização dos testes, conforme número de linhas e colunas especificadas, desde que obedecendo ao critério dado na Seção 3;
Estabelecer as conexões com os p módulos escravo;
Distribuir a massa de dados para os p módulos escravo;
Enviar um sinal de sincronismo e receber os resultados de cada escravo para compor o resultado final.

A massa de dados é enviada da seguinte forma: divide-se a quantidade m₁ de linhas da matriz A pelo número p de processadores desejados, e em seguida é enviado m₁/p linhas da matriz A e toda a matriz B para cada módulo escravo.

O módulo escravo, por sua vez, irá receber estes dados enviados pelo cliente e proceder à multiplicação da submatriz de A pela matriz de B, gerando uma submatriz resultado de C, que após um sinal de sincronismo é enviada ao cliente para composição do resultado final.

O algoritmo do módulo cliente pode ser pode ser resumido nos seguintes passos:

Ficar em estado espera para a conexão do módulo cliente;
Estabelecer a conexão com o módulo cliente quando solicitado;
Receber os dados enviados pelo cliente e efetuar o processamento;
Receber sinal de sincronismo e enviar a submatriz resultado para o módulo cliente.

Em seguida são apresentados os algoritmos como uma função em linguagem estruturada.

- Módulo Mestre:

int main (int argc, char *argv[]) {

/* Declara as variáveis (vide Anexo I) */

/* Verifica e recebe argumentos da linha de comando (vide Anexo I)*/

/* Verifica condição de multiplicação das matrizes */

if (ACol!=BLin){

printf("Números de Colunas de A diferente de Linhas de B\n");

exit(0);

}

/* CAMADA DE TRANSPORTE E DE REDE (TCP/IP) */

/* Define as máquinas e estabelece conexão */

nome_host(nomeproc);

for(i=0;i<numproc;i++)

sd[i] = cria_socket_cli(i,nomeproc);

printf("Conexao estabelecida!\n");

/* CAMADA DE APLICACÃO */

/* Gera Matrizes A e B */

GeraMatriz(ALin,ACol,A);

GeraMatriz(BLin,BCol,B);

/* Define o tamanho dos blocos para envio */

NLin = ALin/numproc; IniLin = 0; FimLin = NLin;

/* Envia um bloco da matriz A e toda a matriz B para cada processador */

for(j=0;j<numproc;j++){

envia_matriz(sd[j],IniLin,FimLin,ACol,A);

envia_matriz(sd[j],0,BLin,BCol,B);

IniLin = FimLin;

FimLin += NLin;

}

/* Recebe Matriz a matriz resultante C de forma sincronizada com envio */

IniLin = 0;

FimLin = NLin;

for(j=0;j<numproc;j++){

send(sd[j], (void *)&sinc, sizeof(int),0);

recebe_matriz_result(sd[j],IniLin,FimLin,BCol,C);

IniLin = FimLin;

FimLin += NLin;

}

/* Imprime a matriz resultante C = A x B */

imprime_matriz(ALin,BCol,C);

}

- Módulo Escravo

int main (int argc, char *argv[]) {

/* Declara as variáveis (vide Anexo I) */

/* Verifica e recebe argumentos da linha de comando (vide Anexo I)*/

/* CAMADA DE TRANSPORTE E DE REDE (TCP/IP) */

/* Cria o Socket para o processador escravo*/

proc = atoi(argv[1]);

sd = cria_socket_serv(proc);

/* Servidor Cria novo socket para cada conexão */

while(1) {

printf ("\nServidor em estado de espera...\n");

cliLen = sizeof(cliAddr);

newSd = accept(sd, (struct sockaddr *) &cliAddr, &cliLen);

if(newSd<0) {

perror("conexão não foi aceita ");

return ERROR;

}

/* CAMADA DE APLICACÃO */

/* Recebe o bloco de dados das matrizes A e B */

recebe_matriz(newSd,&ALin,&ACol,A);

recebe_matriz(newSd,&BLin,&BCol,B);

/* Executa a multiplicação C = A x B */

multiplica_matrizes(ALin,BCol,A,B,C);

/* Envia matriz C após sinal de sincronismo */

recv(newSd,(void *)&sinc,sizeof(int),0);

envia_matriz_result(newSd,ALin,BCol,C);

}/* fim do while(1) */

close(newSd);

}

4.3 Exemplo de Execução do Algoritmo Paralelo

De forma a tornar mais claro o funcionamento do algoritmo paralelo proposto, é apresentada uma execução passo a passo da massa de dados obtida da Figura 7.2 de [Quinn 94], a partir de uma seqüência de passos principais que explicam o funcionamento básico do algoritmo proposto, e sendo apresentado em seguida os formatos das submatrizes e matrizes enviadas para os escravos pelo cliente, as submatrizes resultantes da execução da multiplicação por cada escravo, e a matriz resultante formada pelas submatrizes retornadas dos escravos para o cliente.

Matrizes de Entrada:

A = B =

- Utilizando 2 processadores

Cliente estabelece conexão com os 2 escravos;
Cliente divide e envia a submatriz A , com n/2 linhas, e a matriz B para cada escravo;
Escravo recebe submatriz A e a matriz B e efetua a multiplicação;
Cliente envia sinal de sincronismo para escravo;
Escravo recebe sinal de sincronismo e envia submatriz resultante;
Cliente recebe e concatena as submatrizes para a matriz resultante.

Escravo 1:

Escravo 2:

Cliente: Recebe as submatrizes resultantes em C =

- Utilizando 4 processadores

Cliente estabelece conexão com os 4 escravos;
Cliente divide e envia a submatriz A , com n/4 linhas, e a matriz B para cada escravo;
Escravo recebe a submatriz A e a matriz B e efetua a multiplicação;
Cliente envia sinal de sincronismo para escravo;
Escravo recebe sinal de sincronismo e envia submatriz resultante;
Cliente recebe e concatena as submatrizes para a matriz resultante.

Escravo 1:

Escravo 2:

Escravo 3:

Escravo 4:

Cliente: Recebe as submatrizes resultantes em C :

5. Análise de Complexidade

Para a análise de complexidade de custo desenvolvida nesta seção, são consideradas como matrizes de entrada de dados as matrizes A e B quadradas de ordem n. Esta simplificação visa tão somente facilitar o entendimento das análises desenvolvidas, e pode ser estendida para o caso mais geral sem maiores dificuldades. O custo de complexidade de tempo do algoritmo paralelo proposto pode ser dividido em custo do processamento e custo da comunicação:

- Custo do Processamento:

Custo de atribuição das matrizes de entrada à variável buffer para envio aos escravos:

Custo da submatriz A = p. = n² (1)

Custo da matriz B = p.n² (2)

Custo do cálculo da submatriz resultado = (3)
Custo de atribuição das submatrizes resultantes à matriz resultante final = n² (4)

Portanto, o custo total do processamento é dado por:

C_p = (5)

C_p = (6)

- Custo da Comunicação:

Seja: - Tempo de latência.

- Tempo de envio de um elemento.

Custo de envio da matriz A = = (7)
Custo de envio da matriz B = = (8)
Custo de recebimento da matriz C = =

(9)

Portanto, o custo total da comunicação é dado por:

Cc = ++

Cc = (10)

6. Comparação com Outras Alternativas de Implementação

Outras alternativas para implementação do algoritmo paralelo de multiplicação de matrizes podem ser encontradas em [Quinn 94], e nesta seção é feita uma comparação, adaptando a estratégia proposta para uma NOW, conforme utilizado para o algoritmo proposto neste trabalho, e cuja estratégia será denominada SM (Submatriz/Matriz). Novamente, para facilitar o entendimento, são consideradas como matrizes de entrada de dados as matrizes A e B quadradas de ordem n.

6.1 Estratégia Row-Colum-Oriented-Algorithm (RCO)

Nesta estratégia, as linhas da matriz A e as colunas da matriz B são dividas pelos p processadores e enviadas a cada escravo, que receberão as duas submatrizes e executarão a multiplicação gerando uma submatriz resultado de tamanho n²/p², perfazendo um total de p submatrizes B para uma mesma submatriz A em um único processador.

- Custo do Processamento:

O Custo do processamento não vai mudar com a forma de divisão e transmissão dos dados, e continua sendo dado por (5), portanto:

C_p =

- Custo da Comunicação:

Seja: - Tempo de latência.

- Tempo de envio de um elemento.

1. Custo de envio da matriz A = = (11)

Custo de envio da matriz B = = (12)
Custo de recebimento da matriz C = = (13)

Portanto, o custo total da comunicação é dado por:

Cc = ++

Cc = (14)

Considerando que o custo de processamento é o mesmo, e analisando o custo de comunicação, através de (10) e (14), temos que:

Cc SM < Cc RCO

Analisando a estratégia SM em relação à RCO, temos que:

O custo do processamento é o mesmo;
O custo da comunicação é inferior;
O processo de controle de recebimento dos resultados é mais simples;

6.2 Estratégia Block-Oriented-Algorithm (BO)

Nesta estratégia, as matrizes A e B são dividas em p submatrizes de ordem n/Öp, sendo p o número de processadores tal que Öp seja inteiro, e enviadas a cada escravo, que receberão as duas submatrizes e executarão a multiplicação gerando uma submatriz resultado de tamanho n²/p² cumulativamente em Ö p iterações, perfazendo um total de p submatrizes resultantes.

- Custo do Processamento:

A complexidade de custo do processamento não vai mudar com a forma de divisão e transmissão dos dados, e continua sendo dado por (5), portanto:

C_p =

- Custo da Comunicação:

Seja: - Tempo de latência.

- Tempo de envio de um elemento.

Custo de envio da matriz A = = (15)
Custo de envio da matriz B = = (16)
Custo de recebimento da matriz C = = (17)

Portanto, o custo total da comunicação é dado por:

Cc = ++

Cc = (18)

Considerando que o custo de processamento é o mesmo, e analisando o custo de comunicação, através de (10) e (18), temos que:

Cc SM Cc BO

Analisando a estratégia SM em relação à BO, temos que:

O custo do processamento é o mesmo;
O custo da comunicação é superior ao da estratégia BO;
O processo de controle de envio dos dados e recebimento dos resultados é mais simples, o que reduz a possibilidade de erro na implementação;
A limitação da estratégia BO quanto ao número de processadores (Ö p inteiro) limita de maneira considerável o número de processadores a serem utilizados, o que vem a ser uma grande desvantagem em relação à SM.

7. Limite Inferior Utilizando O Modelo PRAM e SIMD

7.1 Modelo PRAM

O limite inferior para multiplicação de duas matrizes pode ser dado a partir das seguintes afirmativas:

O custo de uma computação PRAM é dado pela complexidade paralela vezes o número de processadores utilizados.
Um algoritmo paralelo no Modelo PRAM é ótimo se seu custo estiver na mesma classe de complexidade do algoritmo sequencial ótimo.
O limite inferior para multiplicação de matrizes para um algoritmo sequencial pode ser obtida a partir de [Luchesi et al 79] em seu Corolário 1, e cuja prova matemática encontra-se disponível no mesmo, que afirma:

Pelo menos n² multiplicações são necessárias para calcular o produto de duas matrizes n x n .

Considerando o exposto acima, uma vez que o ótimo PRAM encontra-se na mesma classe de complexidade do algoritmo seqüencial ótimo, e este possui limite inferior dado por W (n²), podemos afirmar que:

Limite Inferior do Modelo PRAM para multiplicação de matrizes = W (n²)

7.2 Modelo SIMD

Algumas abordagens podem ser encontradas para a implementação de multiplicações de matrizes utilizando o modelo SIMD. Em [Quinn 94] temos duas abordagens:

2-D Mesh: Neste modelo, o limite inferior, dado pelo Teorema 7.1, é W (n) passos para transmissão de dados, utilizando n² processadores.

Hypercube: Neste modelo, o limite inferior, dado pelo Teorema 7.2, é W (log n) passos para transmissão de dados, utilizando n³ processadores.

Se considerarmos somente a complexidade , o limite inferior é dado pelo modelo hypercube: W (log n). Entretanto é importante observar que o custo no modelo 2-D Mesh é menor, pois utiliza apenas n² processadores.

8. Implementação do Algoritmo

O algoritmo foi implementado em linguagem C, no compilador gcc (gcc -lnsl -lsocket arquivo.c -o executavel), utilizando uma plataforma Sun Ultra 5 em ambiente Solaris 5.7. A estratégia utilizada no algoritmo foi obtida em [Quinn 94] e possui os seguintes arquivos: o mestre, o escravo, um módulo contendo as funções e um arquivo de cabeçalho.

Algumas decisões de implementação foram tomadas, visando reduzir os efeitos da NOW no processamento, permitindo obter-se resultados mais consistentes, que são:

A variável de transferência de dados (buffer) é limitada a 1024 bytes. Isto visa evitar que mensagens maiores sofram interferência do time out de concorrência da rede.
O número de linhas da matriz A deve ser múltiplo do número de processadores. Isto simplifica e torna o processo de divisão dos dados mais eficiente.
As matrizes de dados possuem elementos de 1 byte. Isto permite que matrizes com linhas de até 1024 elementos possam ser utilizadas, em conformidade com o limite máximo do buffer.
Utilização de mensagens de sincronismo para recebimento de dados. Visa somente simplificar a implementação, evitando a necessidade do uso de threads.

Para utilizar o programa, primeiro ative os p processadores escravos, bastando digitar em cada máquina a ser utilizada o seguinte comando:

<escravo <numprocessador

Onde numprocessador é o número com o qual aquele processador será identificado.

Em seguida, inicie o processo pelo cliente, bastando digitar o seguinte comando:

<cliente <numprocessadores ALinhas AColunas BLinhas BColunas

Onde:

numprocessadores é a quantidade de processadores desejada (max 8)

Alinhas é o número de linhas da matriz A

AColunas é o número de colunas da matriz A

Blinhas é o número de linhas da matriz B

BColunas é o número de colunas da matriz B

O comando irá fazer a conexão do cliente com cada escravo, e executar o algoritmo conforme Seção 4.2. Um exemplo de saída do programa pode ser visto no Anexo I. As principais funções do programa são:

Função cria_socket_serv: Recebe como entrada o numero do processador, cria o socket, mapeia o endereço do servidor para a porta utilizada, cria um buffer para a fila de processos e retornar o número do identificador do socket criado.

Função cria_socket_cli: Recebe como entrada o numero do processador e o vetor de strings contendo os nomes das máquinas. Identifica o host pelo nome da máquina, define o endereço do cliente, cria o socket, mapeia o endereço do cliente para a porta utilizada, faz a conexão ao servidor indicado pelo número do processador e retornar o número do identificador do socket criado.

Função envia_matriz: Recebe como entrada o número do identificador do socket, o número de linhas inicial e final, o número de colunas e a matriz de dados. Envia uma mensagem para escravo contendo a ordem (linhas/colunas) da matriz e em seguida envia um bloco de linhas da matriz, sendo enviado linha a linha.

Função recebe_matriz: Recebe como entrada o número do identificador do socket, variáveis para receber o número de linhas e colunas e a matriz de dados. Recebe uma mensagem contendo a ordem (linhas e colunas) da matriz e em seguida recebe um bloco de linhas da matriz, sendo recebido linha a linha.

Função multiplica_matrizes: Recebe como entrada o número de linhas e colunas, a matriz de dados A e matriz de dados B. Calcula e fornece a matriz resultado C = A x B.

Função envia_matriz_result: Recebe como entrada o número do identificador do socket, o número de linhas e colunas e a matriz de dados. Envia um bloco de linhas da matriz, sendo enviado linha a linha.

Função recebe_matriz_result: Recebe como entrada o número do identificador do socket, variáveis para receber o número de linhas e colunas e a matriz de dados. Recebe um bloco de linhas da matriz resultado, sendo recebido linha a linha.

As demais funções podem ser encontradas no código fonte do programa, conforme Anexo II.

O código fonte do algoritmo seqüencial, utilizado para estudos comparativos, pode ser encontrado no Anexo III

9. Resultados Obtidos

Para a realização dos testes e obtenção dos resultados, foram utilizadas matrizes quadradas de ordem n, utilizando 2, 4 e 8 processadores, nas seguintes máquinas da rede do DCC/UFMG:

ciclope.dcc.ufmg.br – Sun Ultra Sparc 5, com Solaris 5.7

vampira.dcc.ufmg.br – Sun Ultra Sparc 5, com Solaris 5.7

gambit.dcc.ufmg.br – Sun Ultra Sparc 5, com Solaris 5.7

tempestade.dcc.ufmg.br – Sun Ultra Sparc 5, com Solaris 5.7

wolverine.dcc.ufmg.br – Sun Ultra Sparc 5, com Solaris 5.7

magneto.dcc.ufmg.br – Sun Ultra Sparc 5, com Solaris 5.7

jubileu.dcc.ufmg.br – Sun Ultra Sparc 5, com Solaris 5.7

jean.dcc.ufmg.br – Sun Ultra Sparc 5, com Solaris 5.7

Os teste foram realizados no dia 07 de setembro entre 06:00h e 07:00h, situação em que a rede se encontrava com o tráfego mínimo, permitindo menos influência de concorrência para a transmissão / recepção das mensagens.

Os tempos foram obtidos utilizando o comando time , obtendo o tempo real total de execução do cliente, sem impressão em tela dos resultados, visando obter somente o tempo do processo paralelizado considerando o custo de comunicação da rede. O algoritmo seqüencial foi executado no mesmo tipo de máquina, nas mesmas condições.

As Tabelas 1 e 2 apresentam os resultados de tempo, speedup e eficiência, obtidos para matrizes quadradas cuja ordem varia de 200 a 1000, utilizando 1, 2, 4 e 8 processadores.

O speedup é dado pela seguinte relação:

speedup = tempo seqüencial / tempo paralelo

A eficiência é dada pela seguinte relação:

eficiência = speedup / nº de processadores

Ordem da Matriz	Processadores (tempo real)
Ordem da Matriz	1	2	4	8
200	2.03	1.59	1.46	2.12
400	16.21	9.38	5.90	5.73
600	58.92	31.53	17.40	12.94
800	141.2	73.66	38.74	24.98
1000	282.06	143.10	73.07	44.03

Tabela 1: Tempo de execução em segundos

de p processadores para matriz de ordem n

Ordem da Matriz	*Processadores (speedup* e eficiência)**
	1		2		4		8
	Speedup	eficência	speedup	eficência	speedup	eficência	speedup	Eficência
200	1.00	100,00%	1.28	64%	1.39	35%	0.96	12%
400	1.00	100,00%	1.73	86%	2.75	69%	2.83	35%
600	1.00	100,00%	1.87	93%	3.39	85%	4.55	57%
800	1.00	100,00%	1.92	96%	3.64	91%	5.65	71%
1000	1.00	100,00%	1.97	99%	3.86	97%	6.41	80%

Tabela 2: speedup e eficiência de p processadores para matriz de ordem n

Os Gráficos das figuras 2, 3, 4 e 5 apresentam, respectivamente, a relação tempo de execução (em segundos) vs. ordem da matriz, speedup vs. ordem da matriz, speedup vs. processadores e eficiência vs. ordem da matriz. A partir destes gráficos são feitas as análises dos resultados obtidos.

Figura 2: Gráfico do tempo de execução para matriz de ordem n (Tabela 1)

Figura 3: Gráfico do speedup para matriz de ordem n (Tabela 2)

Figura 4: Gráfico do speedup para p processadores (Tabela 2)

Figura 5: Gráfico da eficiência de p processadores para matriz de ordem n (Tabela 2)

O gráfico da Figura 2 demonstra claramente que o tempo de processamento cresce à medida que a massa de dados aumenta, ou seja, a ordem n das matrizes cresce, e que este crescimento é inversamente proporcional ao número de processadores utilizados. Como exemplo, para n =1000, o tempo de processamento do algoritmo seqüencial é de quase 5 minutos, enquanto que utilizando uma máquina paralela com 8 processadores o tempo de execução é de alguns segundos. Isto mostra de forma inequívoca, como citado no início deste trabalho, que a utilização da computação paralela traz benefícios relevantes quando se utiliza uma grande massa de dados que geram um alto custo de processamento, isto para problemas que sejam passíveis de paralelização.

Os gráficos das Figuras 3 e 4 abordam o speedup obtido nos diversos experimentos, no primeiro é possível observar que, para valores de n pequenos, os resultados obtidos são bastante tímidos, em alguns casos chegam a ser menor que 1, e à medida que n aumenta, as curvas de speedup tendem a ficar próximas da situação ideal. Isto ocorre devido à influência da rede na transmissão/recepção dos dados, ou seja, o custo de comunicação dado por (10) é, em termos absolutos, bastante relevante se comparado ao custo do processamento dado por (5), pois este ultimo é da mesma ordem de grandeza tanto no paralelo quanto no seqüencial. Isto fica ainda mais evidente no gráfico da Figura 4, como pode ser visto na curva n = 200 , onde o ganho do speedup foi relativamente pequeno, com piores resultados para um maior números de processadores, como no caso de p = 8, isto porque o número de mensagens enviadas / recebidas é maior, o que ratifica o já exposto em relação à influência do custo de comunicação.

O gráfico da Figura 5 apresenta a eficiência obtida, que melhora à medida que a massa de dados aumenta, ou seja, a ordem n das matrizes cresce. Isto ocorre, também, devido ao custo de comunicação, como comentado no parágrafo anterior, entretanto este gráfico pode nos levar a crer que, para valores ainda maiores de n, os processamentos paralelos para todos os p processadores tendem a chegar a eficiência 100% . Esta não é uma afirmativa correta, pois nestes experimentos há que se considerar as decisões de implementação que limitam o tamanho do buffer a 1024 bytes e permitem que um mensagem seja enviada de uma única vez reduzindo os efeitos da rede. Para valores de n maiores, essa condição não seria possível, e a transmissão de dados teria que ser divida em diversas mensagens, aumentando significativamente o custo de comunicação, e quanto maior o valor de n, maior ainda esse custo., portanto a partir de um valor limite, a eficiência obtida tende a se manter e ou diminuir.

10 Conclusão do Trabalho

Neste trabalho foi apresentado um estudo e implementação de uma máquina paralela MIMD utilizando NOW, com o objetivo de demonstrar os benefícios e as restrições do uso desta ferramenta computacional. O problema apresentado como exemplo de utilização consistiu em efetuar a multiplicação de duas matrizes utilizando 2, 4 e 8 processadores. Uma abordagem mais formal apresenta a análise da complexidade de custo de processamento e de custo de comunicação (Seção 5), um estudo comparativo com outras estratégias (Seção 6) e os limites inferiores para os modelos PRAM e SIMD (Seção 7). Os experimentos realizados e apresentados nas Tabelas 1 e 2, dão suporte prático às análises e conclusões deste trabalho, ilustradas nos gráficos das Figuras 2, 3, 4 e 5.

Como podem ser vistos nos gráficos e nas análises efetuadas, o programa alcançou os objetivos esperados, dentro das decisões de projeto e condições de testes. A partir destas análises, poder chegar às seguintes conclusões:

O uso de máquinas paralelas é viável e traz benefícios práticos na sua utilização;
O custo de comunicação da rede interfere significativamente nos resultados obtidos, principalmente devido ao tráfego ser inconstante, pois depende de uma série de fatores;
Quanto maior o custo do processamento, em geral proporcional à massa de dados, melhores são os resultados obtidos com a paralelização;
A partir de um dado tamanho da massa de dados, o custo de comunicação aumenta significativamente, devido ao aumento do número de mensagens;
Para uma utilização mais abrangente do programa, algumas restrições de implementação (e não do algoritmo) devem ser estendidas para casos mais gerais.

REFERÊNCIAS

[Henessy e Patterson 95] Hennesy, J. e Patterson, D.A. Computer Architecture a quantitative approach. 2^nd Ed. Morgan Kauffman Publishers, Inc. San Francisco, California, 1995.

[Luchesi et al 79] Luchesi, C. L.; Simon, I. S.; Simon, J.; Kowaltowski, T. Aspectos Teóricos da Computação. Instituto de Matemática Aplicada, Rio de Janeiro, 1979.

[Quinn 94] Quinn, M. J.; Parallel Computing Theory and Practice, McGraw-Hill, 1994.

ANEXO I – Exemplo de Execução da Máquina Paralela

1. Com 2 processadores
mestre 2 6 3 3 6
Matriz A
|| 1 1 1 ||
|| 1 1 1 ||
|| 1 1 1 ||
|| 1 1 1 ||
|| 1 1 1 ||
|| 1 1 1 ||
Matriz B
|| 1 1 1 1 1 1 ||
|| 1 1 1 1 1 1 ||
|| 1 1 1 1 1 1 ||
Matriz C = A x B
|| 3 3 3 3 3 3 ||
|| 3 3 3 3 3 3 ||
|| 3 3 3 3 3 3 ||
|| 3 3 3 3 3 3 ||
|| 3 3 3 3 3 3 ||
|| 3 3 3 3 3 3 ||

Cada escravo executa:
Servidor em estado de espera...
Matriz A
|| 1 1 1 ||
|| 1 1 1 ||
|| 1 1 1 ||
Matriz B
|| 1 1 1 1 1 1 ||
|| 1 1 1 1 1 1 ||
|| 1 1 1 1 1 1 ||
Matriz C = A x B
|| 3 3 3 3 3 3 ||
|| 3 3 3 3 3 3 ||
|| 3 3 3 3 3 3 ||

Com 4 processadores

mestre 2 6 3 3 6
Matriz A
|| 1 1 1 ||
|| 1 1 1 ||
|| 1 1 1 ||: || 1 1 1 ||; || 1 1 1 ||; || 1 1 1 ||; || 1 1 1 ||; || 1 1 1 ||; Matriz B; || 1 1 1 1 1 1 1 1 ||; || 1 1 1 1 1 1 1 1 ||; || 1 1 1 1 1 1 1 1 ||; Matriz C = A x B; || 3 3 3 3 3 3 3 3 ||; || 3 3 3 3 3 3 3 3 ||; || 3 3 3 3 3 3 3 3 ||; || 3 3 3 3 3 3 3 3 ||; || 3 3 3 3 3 3 3 3 ||; || 3 3 3 3 3 3 3 3 ||; || 3 3 3 3 3 3 3 3 ||; || 3 3 3 3 3 3 3 3 ||
Cada escravo executa:

Servidor em estado de espera...

Matriz A

|| 1 1 1 ||

Matriz B

|| 1 1 1 1 1 1 1 1 ||

Matriz C = A x B

|| 3 3 3 3 3 3 3 3 ||

ANEXO II – Código Fonte dos Programas Mestre e Escravo

/* ------------------------------------------------------------------

Programa Mestre p/ multiplicação de matrizes - Trabalho 4 de PAA

Doutorado em Ciência da Computação - UFMG

Autor: José Pinheiro de Queiroz Neto - 2002201999

Orientador: Dr. Mario F. M. Campos (UFMG)

Co-Orientador: Dr. Rodrigo L. Carceroni (UFMG)

Propósito: Projetar um algoritmo paralelo para executar em uma

máquina multicomputadores a multiplicação de matrizes.

BH 07/09/02 */

/* -----------------------Comentarios---------------------------------*/

Este programa implementa o algoritmo Mestre para a multiplicação de

duas matrizes em uma máquina paralela (multicomputadores), utilizando

sockets para a comunicação entre as máquinas.

Sendo desenvolvido no ambiente solaris, e compilado no gcc

(gcc -lnsl -lsocket mestre.c -o mestre). A linha de comando é:

<executável <numprocessadores ALinhas AColunas BLinhas BColunas

Os testes foram efetuados utilizando 2, 4 e 8 máquinas Sun Sparc Ultra5,

com matrizes de teste de ordem 100 a ordem 1000.

/* ---------------Bibliotecas ---------------------------------------*/

#include "modulo.c"

int main (int argc, char *argv[]) {

int numproc, // Número de processadores utilizados

sd[8], // Vetor de sockets p/processadores

sinc=1, // Sincronismo para receber resultado

ALin, ACol, // Linhas e colunas da matriz A

BLin, BCol, // Linhas e colunas da matriz B

IniLin, FimLin, NLin, // Inicio,fim e número de linhas enviadas

i,j; // Variáveis auxiliares de contagem

char nomeproc[8][30], // Nome das máquinas utilizadas

A[LINHAS][COLUNAS], // Matriz de entrada A

B[LINHAS][COLUNAS], // Matriz de entrada B

C[LINHAS][COLUNAS]; // Matriz resultante C

/* Verifica argumentos da linha de comando */

if(argc < 6) {

printf("digite: %s <numproc ALin ACol BLin BCol\n",argv[0]);

exit(1);

}

/* Recebe argumentos nas variáveis de entrada */

numproc = atoi(argv[1]);

ALin = atoi(argv[2]);

ACol = atoi(argv[3]);

BLin = atoi(argv[4]);

BCol = atoi(argv[5]);

/* Verifica condição de multiplicação das matrizes */

if (ACol!=BLin){

printf("Números de Colunas de A diferente de Linhas de B\n");

exit(0);

}

/* CAMADA DE TRANSPORTE E DE REDE (TCP/IP) */

/* Define as máquinas e estabelece conexão */

nome_host(nomeproc);

for(i=0;i<numproc;i++)

sd[i] = cria_socket_cli(i,nomeproc);

printf("Conexao estabelecida!\n");

/* CAMADA DE APLICACÃO */

/* Gera Matrizes A e B */

GeraMatriz(ALin,ACol,A);

GeraMatriz(BLin,BCol,B);

/* Define o tamanho dos blocos para envio */

NLin = ALin/numproc;

IniLin = 0;

FimLin = NLin;

/* Envia um bloco da matriz A e toda a matriz B para cada processador */

for(j=0;j<numproc;j++){

envia_matriz(sd[j],IniLin,FimLin,ACol,A);

envia_matriz(sd[j],0,BLin,BCol,B);

IniLin = FimLin;

FimLin += NLin;

}

/* Recebe Matriz a matriz resultante C de forma sincronizada com o envio */

IniLin = 0;

FimLin = NLin;

for(j=0;j<numproc;j++){

send(sd[j], (void *)&sinc, sizeof(int),0);

recebe_matriz_result(sd[j],IniLin,FimLin,BCol,C);

IniLin = FimLin;

FimLin += NLin;

}

/* Imprime as matrizes A, B e C (debug) */

//imprime_matrizes(ALin,ACol,BLin,BCol,A,B,C);

/* Imprime a matriz resultante C = A x B */

imprime_matriz(ALin,BCol,C);

return 0;

}

/* ------------------------------------------------------------------

Programa Escravo p/ multiplicação de matrizes - Trabalho 4 de PAA

Doutorado em Ciência da Computação - UFMG

Autor: José Pinheiro de Queiroz Neto - 2002201999

Orientador: Dr. Mario F. M. Campos (UFMG)

Co-Orientador: Dr. Rodrigo L. Carceroni (UFMG)

Propósito: Projetar um algoritmo paralelo para executar em uma

máquina multicomputadores a multiplicação de matrizes.

BH 07/09/02 */

/* -----------------------Comentarios---------------------------------*/

Este programa implementa o algoritmo Escravo para a multiplicação de

duas matrizes em uma máquina paralela (multicomputadores), utilizando

sockets para a comunicação entre as máquinas.

Sendo desenvolvido no ambiente solaris, e compilado no gcc

(gcc -lnsl -lsocket escravo.c -o escravo). A linha de comando é:

<executável <numprocessador

Os testes foram efetuados utilizando 2, 4 e 8 máquinas Sun Sparc Ultra5,

com matrizes de teste de ordem 100 a ordem 1000.

/* ---------------Bibliotecas ---------------------------------------*/

#include "modulo.c"

int main (int argc, char *argv[]) {

int proc, // Número do processador deste escravo

sd,newSd, // Variaveis de sockets p/ coxexão

sinc, // Sincronismo para envio do resultado

ALin, ACol, // Linhas e colunas da matriz A

BLin, BCol, // Linhas e colunas da matriz B

i,j,cliLen; // Variáveis auxiliares

char A[LINHAS][COLUNAS], // Matriz de entrada A

B[LINHAS][COLUNAS], // Matriz de entrada B

C[LINHAS][COLUNAS]; // Matriz resultante C

struct sockaddr_in cliAddr; // Estrutura utilizada na conexão

/* Verifica argumentos da linha de comando */

if(argc < 2) {

printf("digite: %s <numero do processador\n",argv[0]);

exit(1);

}

/* CAMADA DE TRANSPORTE E DE REDE (TCP/IP) */

/* Cria o Socket para o processador escravo*/

proc = atoi(argv[1]);

sd = cria_socket_serv(proc);

/* Servidor Cria novo socket para cada conexão */

while(1) {

printf ("\nServidor em estado de espera...\n");

cliLen = sizeof(cliAddr);

newSd = accept(sd, (struct sockaddr *) &cliAddr, &cliLen);

if(newSd<0) {

perror("conexão não foi aceita ");

return ERROR;

}

/* CAMADA DE APLICACÃO */

/* Recebe o bloco de dados das matrizes A e B */

recebe_matriz(newSd,&ALin,&ACol,A);

recebe_matriz(newSd,&BLin,&BCol,B);

/* Executa a multiplicação C = A x B */

multiplica_matrizes(ALin,BCol,A,B,C);

/* Imprime matrizes A, B e C (debug) */

imprime_matrizes(ALin,ACol,BLin,BCol,A,B,C);

/* Envia matriz C após sinal de sincronismo */

recv(newSd,(void *)&sinc,sizeof(int),0);

envia_matriz_result(newSd,ALin,BCol,C);

}/* fim do while(1) */

close(newSd);

}

/* ------------------------------------------------------------------------

Cabeçalho do programa p/ multiplicação de matrizes - Trabalho 4 de PAA

Doutorado em Ciência da Computação - UFMG

Autor: José Pinheiro de Queiroz Neto - 2002201999

Orientador: Dr. Mario F. M. Campos (UFMG)

Co-Orientador: Dr. Rodrigo L. Carceroni (UFMG)

Propósito: Projetar um algoritmo paralelo para executar em uma

máquina multicomputadores a multiplicação de matrizes.

BH 07/09/02 */

/* --------------------- Bibliotecas ------------------------------------*/

#include <sys/types.h

#include <sys/socket.h

#include <netinet/in.h

#include <arpa/inet.h

#include <netdb.h

#include <stdio.h

#include <unistd.h /* close */

/* ---------------- Area de Definição de Variáveis ----------------------*/

#define SERVER_PORT 5433

#define MAX_PENDING 5

#define MAX_LINE 1024

#define COLUNAS 1000

#define LINHAS 1000

#define SUCCESS 0

#define ERROR 1

/* ---------------- Area de Declaracao de Funções -----------------------*/

int cria_socket_serv(int nproc);

void nome_host(char proc[8][30]);

int cria_socket_cli(int nproc, char nomeproc[8][30]);

void GeraMatriz(int Linhas, int Colunas, char Mat[LINHAS][COLUNAS]);

void envia_matriz(int sd, int IniLinhas, int FimLinhas, int Colunas,

char Mat[LINHAS][COLUNAS]);

void recebe_matriz(int sd, int *MatLin, int *MatCol,

char Mat[LINHAS][COLUNAS]);

void envia_matriz_result(int sd, int Linhas, int Colunas,

char Mat[LINHAS][COLUNAS]);

void recebe_matriz_result(int sd, int IniLinhas, int FimLinhas, int Colunas,

char Mat[LINHAS][COLUNAS]);

void multiplica_matrizes(int Lin, int Col, char A[LINHAS][COLUNAS],

char B[LINHAS][COLUNAS], char C[LINHAS][COLUNAS]);

void imprime_matriz(int Lin, int Col, char Mat[LINHAS][COLUNAS]);

void imprime_matrizes(int ALin, int ACol, int BLin, int BCol,

char A[LINHAS][COLUNAS], char B[LINHAS][COLUNAS], char C[LINHAS][COLUNAS]);

/* ------------------------------------------------------------------------

Módulo do programa p/ multiplicação de matrizes - Trabalho 4 de PAA

Doutorado em Ciência da Computação - UFMG

Autor: José Pinheiro de Queiroz Neto - 2002201999

Orientador: Dr. Mario F. M. Campos (UFMG)

Co-Orientador: Dr. Rodrigo L. Carceroni (UFMG)

Propósito: Projetar um algoritmo paralelo para executar em uma

máquina multicomputadores a multiplicação de matrizes.

BH 07/09/02 */

/* --------------------- Bibliotecas ------------------------------------*/

#include "cabeca.h"

/* ----------------- Area de Funções de Operações -----------------------*/

/* Função cria_socket_serv. Recebe como entrada o numero do processador,

cria o socket, mapeia o endereco do servidor para a porta utilizada,

cria um buffer para a fila de processos e retornar o número do

identificador do socket criado

int cria_socket_serv(int nproc){

struct sockaddr_in servAddr;

int sd;

/* cria o socket */

sd = socket(AF_INET, SOCK_STREAM, 0);

if(sd<0) {

perror("cannot open socket ");

return ERROR;

}

/* define o endereço e mapeia a porta do servidor */

servAddr.sin_family = AF_INET;

servAddr.sin_addr.s_addr = htonl(INADDR_ANY);

servAddr.sin_port = htons(SERVER_PORT+nproc);

if(bind(sd, (struct sockaddr *) &servAddr, sizeof(servAddr))<0) {

perror("cannot bind port ");

return ERROR;

}

/* cria fila de processos */

listen(sd,5);

return sd;

} /* fim de cria_socket_serv */

/* Função nome_host. Define o número do processador e o nome da máquina

a ser utilizada em um vetor de strings.*/

void nome_host(char proc[8][30]){

strcpy(proc[0],"ciclope");

strcpy(proc[1],"vampira");

strcpy(proc[2],"gambit");

strcpy(proc[3],"tempestade");

strcpy(proc[4],"wolverine");

strcpy(proc[5],"magneto");

strcpy(proc[6],"jubileu");

strcpy(proc[7],"jean");

}/* fim de nome_host*/

/* Função cria_socket_cli. Recebe como entrada o numero do processador e o

vetor de strings contendo os nomes das máquinas. Identifica o host pelo

nome da máquina, define o endereço do cliente, cria o socket, mapeia o

endereco do cliente para a porta utilizada, faz a conexão ao servidor

indicado pelo número do processador e retornar o número do identificador

do socket criado

int cria_socket_cli(int nproc, char nomeproc[8][30]){

struct sockaddr_in localAddr, servAddr;

struct hostent *h;

int sd, rc, i;

/* identifica o host da máquina */

h = gethostbyname(nomeproc[nproc]);

if(h==NULL) {

printf("host desconhecido '%s'\n",nomeproc[nproc]);

exit(1);

}

/* define o endereço do cliente */

servAddr.sin_family = h-h_addrtype;

memcpy((char *) &servAddr.sin_addr.s_addr, h-h_addr_list[0],

h-h_length);

servAddr.sin_port = htons(SERVER_PORT+nproc);

/* cria o socket do cliente */

sd = socket(AF_INET, SOCK_STREAM, 0);

if(sd<0) {

perror("client: nao foi possivel abrir o 'stream socket'\n");

exit(1);

}

/* mapeia o número da porta para o endereço */

localAddr.sin_family = AF_INET;

localAddr.sin_addr.s_addr = htonl(INADDR_ANY);

localAddr.sin_port = htons(0);

rc = bind(sd, (struct sockaddr *) &localAddr, sizeof(localAddr));

if(rc<0) {

printf("não é possivel mapear o endereco do TCP %u",SERVER_PORT+nproc);

perror("error ");

exit(1);

}

/* faz a conexão ao servidor */

rc = connect(sd, (struct sockaddr *) &servAddr, sizeof(servAddr));

if(rc<0) {

perror("client: nao foi possivel conectar ao servidor\n");

exit(1);

}

return sd;

}/* fim de cria_socket_cli */

/* Função GeraMatriz. Recebe como entrada o número de linhas e colunas e

determina os valores dos elementos da matriz. Neste exemplo a matriz

gerada é unitária para facilitar a verificação dos resultados.

void GeraMatriz(int Linhas, int Colunas, char Mat[LINHAS][COLUNAS]){

int i,j;

for(j=0;j<Colunas;j++)

for(i=0;i<Linhas;i++)

if(i%2 == 0)

Mat[i][j]=1;

else

Mat[i][j]=1;

}/* Fim de GeraMatriz */

/* Função envia_matriz. Recebe como entrada o número do identificador do

socket, o número de linhas inicial e final, o número de colunas e a

matriz de dados. Envia uma mensagem para escravo contendo a ordem

(linhas/colunas) da matriz e em seguida envia um bloco de linhas da

matriz, sendo enviado linha a linha.

void envia_matriz(int sd, int IniLinhas, int FimLinhas, int Colunas,

char Mat[LINHAS][COLUNAS]){

int i;

int Ordem[2];

char buf[MAX_LINE];

/* atualiza e envia vetor com linhas e colunas da matriz */

Ordem[0]=FimLinhas - IniLinhas;

Ordem[1]=Colunas;

send(sd, (void *)Ordem, sizeof(int)*2,0);

/* envia o numero de linhas desejados da matriz */

for(i=IniLinhas;i<FimLinhas;i++){

bzero(buf, MAX_LINE);

memcpy((char *)(buf), (char *)&Mat[i], Colunas);

send(sd, buf, MAX_LINE, 0);

}

}/* fim de envia_matriz */

/* Função recebe_matriz. Recebe como entrada o número do identificador do

socket, variáveis para receber o número de linhas e colunas e a matriz

de dados. Recebe uma mensagem contendo a ordem (linhas e colunas) da

matriz e em seguida recebe um bloco de linhas da matriz, sendo recebido

linha a linha.

void recebe_matriz(int sd, int *MatLin, int *MatCol, char Mat[LINHAS][COLUNAS]){

int cliLen, i=0;

int Ordem[2];

char buf[MAX_LINE];

/* recebe vetor com linhas e colunas da matriz e atualiza variáveis */

recv(sd,(void *)Ordem,sizeof(int)*2,0);

*MatLin=Ordem[0];

*MatCol=Ordem[1];

/* recebe o número de linhas desejados da matriz */

do {

bzero(buf, MAX_LINE);

cliLen=recv(sd, buf, MAX_LINE, 0);

memcpy((char *)&Mat[i], (char *)&buf, Ordem[1]);

i += 1;

} while (i<Ordem[0]);

}/* fim de recebe_matriz */

/* Função envia_matriz_result. Recebe como entrada o número do

identificador do socket, o número de linhas e colunas e a matriz de

dados. Envia um bloco de linhas da matriz, sendo enviado linha a linha.

void envia_matriz_result(int sd, int Linhas, int Colunas,

char Mat[LINHAS][COLUNAS]){

int i;

char buf[MAX_LINE];

/* envia o numero de linhas desejados da matriz */

for(i=0;i<Linhas;i++){

bzero(buf, MAX_LINE);

memcpy((char *)(buf), (char *)&Mat[i], Colunas);

send(sd, buf, MAX_LINE, 0);

}

}/* fim de envia_matriz_result */

/* Função recebe_matriz_result. Recebe como entrada o número do

identificador do socket, variáveis para receber o número de linhas e

colunas e a matriz de dados. Recebe um bloco de linhas da matriz

resultado, sendo recebido linha a linha.

void recebe_matriz_result(int sd, int IniLinhas, int FimLinhas,

int Colunas, char Mat[LINHAS][COLUNAS]){

int rc, i=0;

char buf[MAX_LINE];

/* recebe o número de linhas desejados da matriz */

for(i=IniLinhas;i<FimLinhas;i++){

bzero(buf, MAX_LINE);

rc=recv(sd, buf, MAX_LINE, 0);

memcpy((char *)&Mat[i], (char *)&buf, Colunas);

}

/* condicão de terminacão do recebimento */

if(rc<0){

perror("Dados recebidos");

close(sd);

}

}/* fim de recebe_matriz_result */

/* Função multiplica_matrizes. Recebe como entrada o número de linhas e

colunas, a matriz de dados A e matriz de dados B. Calcula e fornece a

matriz resultado C = A x B.

void multiplica_matrizes(int Lin, int Col, char A[LINHAS][COLUNAS],

char B[LINHAS][COLUNAS], char C[LINHAS][COLUNAS]){

int i,j,k;

/* inicializa matriz C */

for (j=0;j<Col;j++)

for (i=0;i<Lin;i++)

C[i][j]=0;

/* calcula C = A x B */

for (j=0;j<Col;j++)

for (i=0;i<Lin;i++)

for (k=0;k<Col;k++)

C[i][j]+=A[i][k]*B[k][j];

}/* fim de multiplica_matrizes */

/* Função imprime_matriz. Recebe como entrada o número de linhas e

colunas e a matriz de dados. Imprime os elementos da matriz

void imprime_matriz(int Lin, int Col, char Mat[LINHAS][COLUNAS]){

int i,j;

for (i=0;i<Lin;i++){

printf("||");

for (j=0;j<Col;j++)

printf(" %d", Mat[i][j]);

printf(" ||\n");

}

printf("\n");

}/* fim de imprime_matriz */

/* Função imprime_matrizes. Recebe como entrada o número de linhas e

colunas e a matrizes de dados de A, B e C. Chama a funcão imprime_matriz

para cada matriz de entrada.

void imprime_matrizes(int ALin, int ACol, int BLin, int BCol,

char A[LINHAS][COLUNAS], char B[LINHAS][COLUNAS], char C[LINHAS][COLUNAS]){

printf("Matriz A\n\n");

imprime_matriz(ALin,ACol,A);

printf("Matriz B\n\n");

imprime_matriz(BLin,BCol,B);

printf("Matriz C = A x B\n\n");

imprime_matriz(ALin,BCol,C);

}/* fim de imprime_matrizes */

ANEXO III – Código Fonte do Sequencial

/* -------------------------------------------------------------------

Programa Sequencial p/ multiplicação de matrizes - Trabalho 4 de PAA

Doutorado em Ciência da Computação - UFMG

Autor: José Pinheiro de Queiroz Neto - 2002201999

Orientador: Dr. Mario F. M. Campos (UFMG)

Co-Orientador: Dr. Rodrigo L. Carceroni (UFMG)

Propósito: Projetar um algoritmo sequencial para executar em uma

máquina e comparar com o resultado do algoritmo paralelo.

BH 07/09/02 */

/* -----------------------Comentarios---------------------------------*/

Este programa implementa o algoritmo Sequencial para a multiplicação de

duas matrizes para fins de comparacão com o algoritmo paralelo.

Sendo desenvolvido no ambiente solaris, e compilado no gcc

(gcc -o sequencial sequencial.c). A linha de comando é:

<executável

Os testes foram efetuados utilizando uma máquina Sun Sparc Ultra-5,

com matrizes de teste de ordem 100 a ordem 1000.

/* ---------------Bibliotecas ---------------------------------------*/

#include "modseq.c"

int main (int argc, char *argv[]) {

int i,j,k, // Variáveis auxiliares de contagem

ALin, ACol, // Linhas e colunas da matriz A

BLin, BCol; // Linhas e colunas da matriz B

char A[LINHAS][COLUNAS], // Matriz de entrada A

B[LINHAS][COLUNAS], // Matriz de entrada B

C[LINHAS][COLUNAS]; // Matriz resultante C

/* Verifica argumentos da linha de comando */

if(argc < 5) {

printf("digite: %s <ALinhas AColunas BLinhas BColunas\n",argv[0]);

exit(1);

}

/* Recebe argumentos nas variáveis de entrada */

ALin = atoi(argv[1]);

ACol = atoi(argv[2]);

BLin = atoi(argv[3]);

BCol = atoi(argv[4]);

/* Verifica condição de multiplicação das matrizes */

if (ACol!=BLin){

printf("Números de Colunas de A diferente de Linhas de B\n");

exit(0);

}

/* Gera Matrizes A e B */

GeraMatriz(ALin,ACol,A);

GeraMatriz(BLin,BCol,B);

/* Executa a multiplicação C = A x B */

multiplica_matrizes(ALin,BCol,A,B,C);

/* Imprime as matrizes A, B e C */

imprime_matrizes(ALin,ACol,BLin,BCol,A,B,C);

return 0;

}

/* ------------------------------------------------------------------------

Módulo do programa p/ multiplicação de matrizes - Trabalho 4 de PAA

Doutorado em Ciência da Computação - UFMG

Autor: José Pinheiro de Queiroz Neto - 2002201999

Orientador: Dr. Mario F. M. Campos (UFMG)

Co-Orientador: Dr. Rodrigo L. Carceroni (UFMG)

Propósito: Projetar um algoritmo sequencial para executar em uma

máquina e comparar com o resultado do algoritmo paralelo.

BH 07/09/02 */

/* --------------------- Bibliotecas ---------------------------------------*/

#include "cabeca.h"

/* ----------------- Area de Funções de Operações --------------------------*/

void GeraMatriz(int Linhas, int Colunas, char Mat[LINHAS][COLUNAS]){

int i,j;

for(j=0;j<Colunas;j++)

for(i=0;i<Linhas;i++)

if(i%2 == 0)

Mat[i][j]=1;

else

Mat[i][j]=1;

}/* Fim de GeraMatriz */

/* Função multiplica_matrizes. Recebe como entrada o número de linhas e

colunas, a matriz de dados A e matriz de dados B. Calcula e fornece a

matriz resultado C = A x B.

void multiplica_matrizes(int Lin, int Col, char A[LINHAS][COLUNAS],

char B[LINHAS][COLUNAS], char C[LINHAS][COLUNAS]){

int i,j,k;

/* inicializa matriz C */

for (j=0;j<Col;j++)

for (i=0;i<Lin;i++)

C[i][j]=0;

/* calcula C = A x B */

for (j=0;j<Col;j++)

for (i=0;i<Lin;i++)

for (k=0;k<Col;k++)

C[i][j]+=A[i][k]*B[k][j];

}/* fim de multiplica_matrizes */

/* Função imprime_matriz. Recebe como entrada o número de linhas e

colunas e a matriz de dados. Imprime os elementos da matriz

void imprime_matriz(int Lin, int Col, char Mat[LINHAS][COLUNAS]){

int i,j;

for (i=0;i<Lin;i++){

printf("||");

for (j=0;j<Col;j++)

printf(" %d", Mat[i][j]);

printf(" ||\n");

}

printf("\n");

}/* fim de imprime_matriz */

/* Função imprime_matrizes. Recebe como entrada o número de linhas e

colunas e a matrizes de dados de A, B e C. Chama a funcão imprime_matriz

para cada matriz de entrada.

void imprime_matrizes(int ALin, int ACol, int BLin, int BCol,

char A[LINHAS][COLUNAS], char B[LINHAS][COLUNAS], char C[LINHAS][COLUNAS]){

printf("Matriz A\n\n");

imprime_matriz(ALin,ACol,A);

printf("Matriz B\n\n");

imprime_matriz(BLin,BCol,B);

printf("Matriz C = A x B\n\n");

imprime_matriz(ALin,BCol,C);

}/* fim de imprime_matrizes */