GEMPP UNIPAMPA

16 de junho de 2012

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

25 de maio de 2012

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.

18 de maio de 2012

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

Roteiro do Encontro

Atualizar o site.
SpeedUp.
Eficiência.
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.

11 de maio de 2012

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