Encontro 16 - Estudo do MPI_Reduce e MPI_Allreduce

No encontro desta semana foi estudado o MPI_Reduce e MPI_Allreduce


Participaram deste encontro: Adriano, Augusto, Henrico, Henrique, Jonathan, Sander e Uillian.

Encontro 15 - Haar Wavelets

No encontro desta semana foi trabalhado a paralelização do algoritmo de Haar Wavelets da 7ª Maratona de Programação Paralela(WSCAD - SSC 2012).

Haar Wavelets

A transformada de Haar é um método de compressão de dados, usado em análise e processamento de sinais. 

Participaram deste envontro: Augusto, Henrico e Sander.

Encontro 14 - Pós Maratona e Bucket Sort

O encontro desta semana marcou o reinicio do GEMPP neste semestre, onde tratamos os seguintes assuntos:

1. Discussão sobre a participação das equipes na maratona de programação.
2. Analise do Problema A da maratona (Bucket Sort)

A discussão sobre a participação das equipes na maratona serviu para mostrar para os membros do GEMPP que não puderam participar da competição como ela ocorre de fato. Falamos sobre o procedimento de aplicação, que durante a manhã tivemos o warmup onde tivemos a possibilidade de fazer e executar um problema, simulando o momento real da maratona, no warmup foi também o momento de tirar todas as nossas dúvidas.Na parte da tarde deu-se a maratona de fato, onde recebemos 5 problemas e tivemos por volta de 4 horas para buscar obter o melhor speedup. Comentou-se também sobre a premiação que as duas equipes do GEMPP recebeu, o que serve de incentivo para uma nova participação na próxima edição da maratona de programação paralela.

Na analise do problema do bucket sort discutimos as implementações das duas equipes durante a maratona,  e pensamos em buscar uma melhor solução. Uma das alternativas pensadas foi alterar o método de ordenação de cada balde, a tentativa foi utilizar a função qsort, porém infelizmente não conseguimos realizar esta alteração pois não conseguimos pensar numa função de comparação.

Dessa forma ficamos então com o mesmo speedup obtido durante a maratona de programação paralela:

UNIPAMPA2: 10
UNIPAMPA1: 4

Para 12 threads.

Participaram do encontro os alunos:

Adriano, Augusto, Henrique, Jonathan, Sander e Uillian.

7th Marathon of Parallel Programming - Resultados

Na última semana ocorreu a 7° Maratona de Programação Paralela no LNCC em Petrópolis. O GEMPP-UNIPAMPA marcou presença com a participação de 2 equipes:

• UNIPAMPA1 - Arthur e Uillian
• UNIPAMPA2 - Henrique, Sander e Leandro

A maratona foi realizada no dia 17 de Outubro. Pela parte da manhã realizou-se o warmup, onde os participantes puderam conhecer o ambiente e testar com um problema.

Na parte da tarde das 14:00h até as 18:15h ocorreu de fato a maratona, onde cada equipe recebeu um conjunto de 5 problemas e teve de buscar o melhor speedup. Em breve divulgaremos a lista dos problemas, que também serão abordados em futuros encontros do GEMPP.

Os resultados foram divulgados na quinta-feira (18/10), e teve as seguintes colocações e suas premiações:

1. UFF - Processador Intel Core i7 + Placa Mãe Intel
2. UNIPAMPA1 - Processador Intel Core i7
3. UNIPAMPA2 - SSD 180gb 

Também durante a maratona a equipe do Olhar Digital fez gravações as quais foram mostradas no programa de domingo 21 de Outubro na RedeTV. A reportagem pode ser visualizada na integra:

Clique aqui para visualizar

Encontro 13 - Utilização de MPI

Nesta reunião, o grupo discutiu e debateu sobre implementações e aplicações de MPI em problemas previamente estudados e paralelizados em OpenMP.
Foram estudados 3 algoritmos já vistos em encontros passados e foram propostas soluções e observadas diferenças de implementação com processamento paralelo utilizando MPI - Multiplicação de Matrizes, Conjunto de Mandelbrot e Permutation Flowshop Scheduling.

Multiplicação de Matrizes

Em nossa paralelização posterior, foram utilizados duas marcações #pragma que paralelizaram a multiplicação, dando desempenho. A modificação de paradigma em MPI exige modificações no código, dividindo a matriz de multiplicação para que seja distribuída a execução entre os processos.

Mandelbrot

Foram observadas semelhanças entre implementações em OpenMP e MPI (ambos dividindo tarefas para diferentes threads/processos).

Permutation Flowshop Scheduling

Foram apresentadas soluções para o problema em MPI e constatada a ineficiência (baixo speedUp) do OpenMP nesse caso.

Encontro 12 - Odd Even Sort

Ainda no objetivo da paralelização do Bubble Sort, neste encontro foi testada a abordagem Odd-Even (Par e Ímpar) paralelizada na ordenação de um vetor numérico.

A paralelização do Bubble Sort ocorreu bem, porém foi encontrada uma falha em alguns casos de testes, quando duas threads tentavam a Swap em uma mesma posição do vetor, ocorreram perdas de dados e portanto, não foi possível garantir a integridade do vetor.

Após pesquisa, foi-se decidida a tentativa de alteração para o enfoque "Par Ímpar", que avalia as trocas em dois momentos, primeiramente nas posições pares e em seguida nas posições ímpares. Garantindo que não será acessada uma mesma posição do vetor no mesmo momento.

A aplicação do algoritmo foi eficiente e rendeu um speedUp de 1,61 vezes mais rápido do algoritmo paralelo com duas threads sobre o mesmo algoritmo sequencial.

Algoritmo em Paralelo

void par_impar(int a[], int N){
    int i, j, metade, swap, ultimoPar, ultimoImpar;
    for(j=0;j<N;j++){
        #pragma omp parallel for private(i, swap)
        for(i=0;i<N-1;i=i+2){
            if(a[i] > a[i+1]){
                swap = a[i];
                a[i] = a[i+1];
                a[i+1] = swap;
            }
        }
        #pragma omp parallel for private(i, swap)
        for(i=1;i<N-2;i=i+2){
            if(a[i] > a[i+1]){
                swap = a[i];
                a[i] = a[i+1];
                a[i+1] = swap;
            }
        }
    }
}

Tempos

O algoritmo sequencial executou em 43.001s .
O algoritmo paralelizado executou em 26.092 .

Encontro 11 - Bubble sort

Encontro 10 - Permutation Flowshop Scheduling

Roteiro do Encontro

- Reorganizar o foco do grupo
- Escolher um problema da 6ª Maratona de Programação Paralela ( 2011 )
- Paralelizar

Permutation Flowshop Scheduling

Permutation Flowshop Scheduling (PFS) have as goal the deployment of an optimal schedule for N jobs on M machines. It is a NP-hard problem: N! possibilities. Each ni job (1 ≤ i ≤ N) must be schedule, in any time, on a mj machine (1 ≤ j ≤ M). That is because a job has M operations and its jth operation must be processed in mj machine. So, one job can start on mj machine if its mj-1 operation is completed and mj machine is free. Each operation has its own time (tj). For PFS the operating sequence of the jobs are the same on every machine. That is the input job queue must be the same for all machines. Solving the PFS problem means determining the permutation which gives the smallest makespan value to schedule N jobs on M machine.

O algoritmo inicial utilizado para esse problema é o seguinte:

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

    int i, j;
    FILE *in, *out;
    int makespan, min_makespan;
    int seq[101];
    int cont_n;

    in = fopen("pfs.in", "r");
    out = fopen("pfs.out", "w");

    while (1) {
        memset(tasks, 0, sizeof(tasks));

        fscanf(in, "%d%d", &n, &m);
        if (n == 0 || m == 0)
            break;
        for (i = 0; i < n; i++) {
            for (j = 0; j < m; j++)
                fscanf(in, "%d", &tasks[i].i[j]);
        }
        min_makespan = 0;

        // generate first sequence
        for (i = 0; i < n; i++)
            seq[i] = i;

        do {
            for (i = 0; i < m; i++)
                machines[i] = -1;
            makespan = 0;
            for (i = 0; i < n; i++) {
                memset(tasks[i].exec, 0, sizeof(tasks[i].exec));
                tasks[i].maq = 0;
            }

            cont_n = 0;

            // simulate permutation flow job schedule
            while (cont_n < n) {

                // schedule each task on a machine
                for (i = cont_n; i < n; i++) {
                    if (machines[tasks[seq[i]].maq] < 0) {
                        machines[tasks[seq[i]].maq] = seq[i];
                    }
                }

                //run task
                for (i = 0; i < m; i++) {
                    if (machines[i] >= 0) {
                        tasks[machines[i]].exec[i]++;
                        if (tasks[machines[i]].exec[i]
                                >= tasks[machines[i]].i[i]) {
                            // free a machine
                            tasks[machines[i]].maq++;
                            if (tasks[machines[i]].maq >= m)
                                cont_n++;
                            machines[i] = -1;
                        }
                    }
                }
                makespan++;
            }

            // calculate makespan
            if (!min_makespan || makespan < min_makespan)
                min_makespan = makespan;

            // generate another sequence
            cont_n = 1;
            while (cont_n) {
                i = n - 1;
                seq[i]++;
                while (seq[i] >= n) {
                    for (j = i; j < n; j++)
                        seq[j] = 0;
                    if ((i - 1) >= 0)
                        seq[--i]++;
                }
                cont_n = 0;
                for (i = 0; i < n && !cont_n; i++)
                    for (j = i + 1; j < n && !cont_n; j++)
                        if (seq[i] == seq[j])
                            cont_n = 1;
            }
            cont_n = 1;
            for (i = 0; i < n - 1 && cont_n; i++)
                if (seq[i] > seq[i + 1])
                    cont_n = 0;
            if (cont_n)
                break;

#ifdef DEBUG
            for (i = 0; i < n; i++)
                printf("%d ", seq[i]);
            printf("\n");
            fflush(stdout);
#endif

        } while (1);

        fprintf(out, "%d\n", min_makespan);
        fflush(out);
    }

    fclose(in);
    fclose(out);

    return EXIT_SUCCESS;
}

Paralelização

Durante a reunião foram discutidas diferentes abordagem para a solução desse problema. A dificuldade de encontrar uma maneira de definir as condições de parada fez com que sua solução fosse adiada para o próximo encontro.

Convite para Defesa de Projeto de TCC

Nesta sexta-feira (29/06), ocorre a defesa do projeto do Trabalho de Conclusão de Curso  de dois integrantes do GEMPP.  Os alunos Arthur  (Orientado pela Prof. Márcia Cera e Co-orientação de Fábio Rossi) e Henrique (Orientado pela Prof. Márcia Cera), irão defender seus projetos. Ambos  estão trabalhando com programação paralela.

O aluno Arthur está trabalhando com programação paralela para memória distribuída (MPI-1 e MPI-2) enquanto que o aluno Henrique está trabalhando com programação paralela em memória compartilhada através da API OpenMP.


Fica a dica para o pessoal que participa do GEMPP, e a todos que se interessam pela área. No link abaixo podem ser encontradas maiores informações.

https://docs.google.com/spreadsheet/pub?key=0AsL79aha84XEdDFNN2N2OHphQk5QMHF1RXBLNDNTNFE&single=true&gid=7&output=html
A defesa começará as 17:30 hs na sala 204 com o Arthur, e logo em seguida é a apresentação do Henrique. 

Todos estão convidados a participar da defesa!

Como Montar seu Cluster Beowulf em Casa

Introdução

      Aqui vai um rápido tutorial para auxiliar na montagem de um cluster caseiro. Este tutorial foi montado após a instalação do Cluster Beowulf do GEMPP.

      Um cluster é definido como um agregado, conjunto de máquinas para computação paralela distribuída. Cluster é um termo bastante utilizado para definir a utilização de dois ou mais computadores independentes, interligados via rede, que trabalham em conjunto trocando informações entre si em torno de uma única tarefa.

      Os cluster são divididos em:

• Alta Disponibilidade: Mantém um serviço de forma estável pelo maior tempo possível.
• Alta Performance: O cluster é designado para prover grande poder computacional.

   Cluster Beowulf são clusters de desempenho escaláveis, baseados numa infraestrutura de hardware comum, rede privada e software 'open source' (Linux).  Para Clusters Beowulf, existe um servidor responsável ("frontend") por controlar todo o cluster, principalmente quanto à distribuição de tarefas e processamento. 

Equipamentos necessários

      Para  montagem do cluster, você precisará ter em mãos:

• 2 ou mais computadores.
• CD/DVD de distribuição Linux.
• Switch.
• Computadores interligados através do switch.
• Cabo UTP conectorizado. (De preferência homologado).

Instalação

    Demonstraremos a instalação do cluster, utilizando três computadores (1 frontend, 2 slaves). A instalação do cluster pode ser dividida em duas etapas: a instalação e configuração do servidor; e a instalação e configuração dos nodos "slaves". Primeiro será descrita a configuração necessária para ambos, e depois as configurações separadas.

• Instalação do Sistema Operacional (em nosso caso, Debian Squeeze, 6.0.5). A instalação deve contemplar somente o sistema básico. (SSH, Servidor Web, ambiente gráfico...) devem ser instalados em separado ao finalizar a instalação.

• Após a instalação do SO, se faz necessário instalar os pacotes que serão essenciais: 

         SSH: Necessário para acessar os nodos:
                       # apt-get install openssh-server && apt-get install ssh
       GCC e G++: Utilizado para compilação dos códigos fonte:
                      # apt-get install gcc && apt-get install g++
       NFS: Network File System, utilizado para configuração do sistema de arquivos:
                       # apt-get install nfs-kernel-server      

Configuração da Rede:

# vim /etc/network/interfaces 

•  No servidor:                  auto eth0
                                             iface eth0 inet static
                                             address 172.0.0.2
                                             netmask 255.255.255.0 
                                             network 172.0.0.0
                                             broadcast 172.0.0.255
                                             gateway 172.0.0.1
  
• no01:                                 auto eth0
                                             iface eth0 inet static
                                             address 172.0.0.3
                                             netmask 255.255.255.0 
                                             network 172.0.0.0
                                             broadcast 172.0.0.255
                                             gateway 172.0.0.1
   
  
     
•  no02:                               auto eth0
                                             iface eth0 inet static
                                             address 172.0.0.4
                                             netmask 255.255.255.0 
                                             network 172.0.0.0
                                             broadcast 172.0.0.255
                                             gateway 172.0.0.1

Configuração do Hostname:

• Editar o arquivo /etc/hostname inserindo o nome do "nó" caso não possua.

Configuração Hosts:

• Editar o arquivo /etc/hosts inserindo o nome e ip dos nodos do cluster, por exemplo:
  
  frontend 172.0.0.2
  no01         172.0.0.3
  no02         172.0.0.4
• Reiniciar o Serviço: /etc/init.d/networking restart

Configuração NFS:

•  No Servidor: Editar o arquivo /etc/exports inserindo as seguintes linhas:
  
  /usr *(rw,sync,no_root_squash)
                                /lib *(rw,sync,no_root_squash)
                                /home *(rw,sync,no_root_squash)

• No Cliente:
  
  • Montar o NFS: 
  • # mount  frontend:/usr  /usr -t nfs
  • # mount  frontend:/lib  /lib -t nfs
  • # mount  frontend:/home  /home -t nfs
  • Editar o arquivo /etc/fstab inserindo as seguintes linhas: 
  frontend:/usr  /usr  nfs defaults 0 0
  frontend:/lib  /lib  nfs defaults 0 0
  frontend:/home  /home  nfs defaults 0 0
   

SSH sem senha:

• Repetir o procedimento abaixo para todos os nós.

•  Gerar chave pública:  # ssh-keygen -t rsa
• Ao ser perguntado o arquivo onde será salvo, definir:
• /home/"usuario"/.ssh/id_rsa_"nomedonó" 

• Copiar todas as chaves geradas de forma concatenada para o authorized_keys.
  
  •  cat /home/"usuario"/.ssh/id_rsa_"nomedonó" >> /home/"usuario"/.ss/authorized_keys

Instalação MPI no Servidor

• O MPI deve ser instalado somente no Servidor.
• # apt-get install libopenmpi-dev
• # apt-get install mpi-default-bin

•  O MPI também pode ser instalado manualmente. Para isto, basta baixar o tar.gz do site do openmpi e instalar.                    

Sites e documentos interessantes e que foram utilizados no desenvolvimento deste tutorial:

Referências

NFS -> http://nfs.sourceforge.net/nfs-howto/
OpenMPI -> http://www.open-mpi.org/
Debian -> http://www.debian.org/
Cluster Beowulf -> http://www.infowester.com/cluster.php



A partir de então, é só partir para brincadeira =)
Dúvidas podem ser tiradas através do e-mail af.lorenzon@gmail.com.
                        

Encontro 8 - Quicksort

Roteiro do Encontro

Ordenação Rápida - Quick Sort

A ordenação rápida (Quick Sort) se basei em um conceito simples de divisão e conquista. Possui inúmeras aplicações em diferentes estruturas que necessitam de ordenação, em nosso caso de estudo usaremos um arquivo binário gerado com um gerador de sequências. Ele irá gerar por padrão 1000 palavras de 8 caracteres  para que seja ordenadas pelo algoritmo Quick Sort. O objetivo será paralelizar a ordenação, fazendo com que possamos reduzir esse tempo de ordenação consideravelmente.

O algoritmo inicial utilizado para esse problema é o seguinte:

int main(void) {

char *keys;

long int N, i;

FILE *file;

if ((file = fopen("quicksort.in", "r")) == NULL) {

perror("quicksort.in");

exit(1);

}

fscanf(file, "%ld", &N);

keys = (char*) malloc(N * 8);

if (keys == NULL) {

perror("Memory allocation");

exit(EXIT_FAILURE);

}

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

fscanf(file, "%s", keys + (i * 8));

fclose(file);

    

    qsort(keys, N, 8, (int(*)(const void *, const void *)) strcmp);

if ((file = fopen("quicksort.out", "w")) == NULL) {

perror("quicksort.out");

exit(1);

}

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

fprintf(file, "%s\n", keys + (i * 8));

fclose(file);

free(keys);

return EXIT_SUCCESS;

}

Paralelização

Durante a reunião foram discutidas diferentes abordagem para a solução desse problema. Inicialmente foi sugerido a modificação de função de leitura e foram anotados resultados efetivos nessa modificação, porém ainda não atingindo o objetivo principal. A paralelização foi decidida e será implementada em uma reunião futura.

Encontro 7 - Métricas de Desempenho e Coleta de Dados

Roteiro do Encontro

1. Atualizar o site. 
2. SpeedUp. 
3. Eficiência. 
4. Execução e Coleta de dados.

• Atualizar o Site
  No encontro de hoje começamos a criação e atualização deste site. Utilizando a plataforma Blogger do Google. 
• SpeedUp
  Buscamos entender como medir o speedUp de um programa paralelo, que é dado pela seguinte formula:
  

  

  Fonte: Wikipédia

  Onde T1 é o tempo do programa sequencial e Tp é o tempo do programa em paralelo.
• Eficiência
  Assim como para o speedup estudamos como calculamos a eficiência de um programa em paralelo.
• Execução e coleta de dados
  Nesta etapa fizemos a execução dos problemas feitos nos encontros anteriores, coletamos os tempos e obtemos o speedup e a eficiência de cada um. Os dados estão nas postagens de cada encontro.

Encontro 6 - Encontrando o valor de Pi

Roteiro do Encontro

• Implementação do Algoritmo de geração de valor aproximado de pi;
• Paralelização do algoritmo de pi;
• Execução e Coleta de Dados;

Implementação do Algoritmo

O algoritmo de cálculo de pi se baseia no seguinte enunciado:

   Uma forma de se calcular o valor aproximado de π é através do seguinte método:

• Sub-escreva um círculo dentro de um quadrado;
• Gere pontos randomicamente dentro do quadrado;
• Determine o número de pontos dentro do quadrado que também estão no círculo;
• Seja r o número de pontos no círculo dividido pelo número de pontos no quadrado;
• π ~ 4.r
• Note que quanto mais pontos forem gerados, melhor será a aproximação.

npoints = 10000
circle_count = 0
do j = 1,npoints
   generate 2 random numbers between 0 and 1
xcoordinate = random1;
   ycoordinate = random2
if (xcoordinate, ycoordinate) inside circle then
circle_count = circle_count + 1
end do
PI = 4.0*circle_count/npoints

Implementação Paralela, Execução e Coleta dos Dados

 A primeira versão paralela desenvolvida foi a seguinte:

---------------------------------------------------------------------------------------------------------------------------------------
npoints = 10000
circle_count = 0
#pragma omp parallel for private(x, y, npoints) reduction(+:circle_count)
   do j = 1,npoints
       generate 2 random numbers between 0 and 1
       x = random1;
       y = random2
       if (x, y) inside circle then
             circle_count = circle_count + 1
   end do
PI = 4.0*circle_count/npoints
---------------------------------------------------------------------------------------------------------------------------------------
As aplicações foram executadas sobre o ambiente de testecontendo o SO Ubuntu (kernel 3.2.0-23) rodando sob um computador com processador Intel Core i7 2630QM, 2.0~2.9 GHz.e 8Gb memória DDR3.  Para os testes foi utilizado número de pontos/iterações igual a 1000000 na aplicação acima e 1000000000 para o teste abaixo.
Analisando a tabela de eficiência e speedup do algoritmo acima, notamos que ao invés de obter aumento de desempenho, perdemos em desempenho. Porque?

Num Threads	Tempo	Eficiência	SpeedUp
1	0,556	-	-
2	4,596	0,024	0,1209747607
3	5,72	0,029	0,0972027972
4	6,443	0,03	0,0862952041
5	6,678	0,041	0,0832584606
6	7,623	0,0043	0,0729371638
7	7,717	0,005	0,0720487236
8	7,775	0,0057	0,071511254

A resposta está no manual da função de geração de números aleatórios rand();
Baseado nisso, desenvolvemos uma nova versão paralela, que pode ser visualizada no algoritmo abaixo:
---------------------------------------------------------------------------------------------------------------------------------------
 #pragma omp parallel for private(i) reduction(+:pi)
        for(i=0; i< NUM_PONTOS; i++){
                pi += 4.0/(4.0*i+1.0);
                pi -= 4.0/(4.0*i+3.0);
        }
---------------------------------------------------------------------------------------------------------------------------------------
A tabela abaixo nos mostra os resultados obtidos para a execução da aplicação acima em nosso ambiente de teste.

Num Threads	Tempo	Eficiência	SpeedUp
1	15,825	-	-
2	8,238	0,9604879825	1,920975965
3	5,727	0,9210756068	2,7632268203
4	4,35	0,9094827586	3,6379310345
5	4,837	0,654331197	3,2716559851
6	4,504	0,5855905861	3,5135435169
7	4,594	0,4921014988	3,4447104919
8	4,436	0,4459253832	3,5674030658

Encontro 4 - Otimização de Executáveis com gcc

Neste encontro abordamos as opções de otimização de executáveis oferecidas pelo compilador gcc.

Encontro 3 - Mandelbrot com parallel for

Roteiro do Encontro

1. Estudo do problema do Mandelbrot.
2. Estudo de caso para a aplicação paralela.
3. Paralelização do código com parallel for.

• Estudo do problema do Mandelbrot.
  Conjunto de Mandelbrot é um fractal, definido a partir do seguinte algoritmo sequencial.
  Onde para cada pixel da imagem irá calcular se ele pertence ou não ao conjunto de mandelbrot, se ele pertence o pixel será pintado de preto, caso contrario será branco.
  A imagem é gerada com o opencv, então para executar o algoritmo ele é necessario.
  Exemplo de imagem gerada a partir do algoritmo:
  

  

  Clique para ampliar. (Fonte: wikipédia)

• Estudo de caso para a aplicação paralela.
  Já com nosso algoritmo sequencial pronto passamos a analisar as possibilidades de paralelização, onde detectamos as seguintes características em nosso código:
• O calculo que define se um ponto pertence ou não ao conjunto é completamente independente, ou seja, para calcular um ponto não precisa esperar o resultado de outro ponto.
• Temos dois laços for aninhados. Nesses laços que estará percorrendo todos os pontos da imagem, como o calculo de todos os pontos não apresentam dependências podemos criar uma distribuição de pontos para cada thread da forma que acharmos adequada.
• Surgiram várias idéias de distribuição do trabalho, entre elas: uma linha por thread, um bloco por thread, um ponto por thread.
• Paralelização do código com parallel for.
  Decidimos então utilizar a diretiva parallel for do openmp para paralelizar, definimos a área paralela do código a área correspondente aos laços for.

Encontro 2 - Multiplicação de Matrizes

Roteiro do Encontro

• Implementação de um algoritmo para multiplicar matrizes;
• Paralelização do algoritmo;
• Coleta de dados;

Implementação do Algoritmo

     Para multiplicar as matrizes A e B, devemos verificar se o número de colunas da matriz A é igual ao número de linhas da matriz B. Este requisito é básico e não deve ser violado.

Implementamos em C o seguinte algoritmo para multiplicação de matrizes:

programa multiplica_matrizes_sequencial;
   matriz mat1, mat2, mat3;
   inteiro linha, coluna, i, acumula;
   "leia mat1";
   "leia mat2";
   "verifique se numero de colunas de mat1 é igual numero de linhas de mat2";
   para linha de 1 até "numero de linhas de mat1" faça
     para coluna de 1 até "numero de colunas de mat2" faça
       acumula=0;
       para i de 1 até "numero de colunas de mat1" faça
         acumula=acumula+mat1[linha][i]*mat2[i][coluna];
       fimpara;
       mat3[linha][coluna]=acumula;
     fimpara;
   fimpara;
   imprima mat3;
fim programa;

Paralelização do Algoritmo

Paralelizamos o primeiro laço com openMP, usando "#pragma omp for".

Coleta de Dados

Os testes foram executados no SO Ubuntu (kernel 3.2.0-24) rodando sob um computador com processador Intel Core i7 2630QM, 2.0~2.9 GHz, com 8Gb memória DDR3.

Matriz	Tempo Sequencial	Tempo 2 Threads	Tempo 4 Threads
1000x1000	15,416 s	7,554 s	4,12 s
2000x2000	2 min 14,89 s	1 min 4,846 s	36,115 s

Encontro 1 - Definição do Dia e Hora dos Encontros

Esta data marca o inicio das atividades do Grupo de Estudos para Maratonas de Programação Paralela da Unipampa.
Neste dia ficou definido que os encontros ocorrerão todas as sextas-feiras das 13:30 - 16:30 horas na sala 301 da Unipampa.
Como primeira atividade aos participantes, foi realizada uma breve introdução sobre a programação em OpenMP, enfocando alguns apectos básicos da API.

Participaram deste encontro: Arthur Lorenzon, Augusto Vargas, Henrique Gressler, Márcia Cera e Uillian Ludwig.