Aprendendo MPI/SimGrid

Reuniões

<2019-08-26> Apresentação dos resultados parciais

Demonstração dos resultados parciais obtidos até o momento (Conjunto de Julia Seq + 1D).
Sugestões para criação de análises de tempo/desempenho dos experimentos.
Convesa sobre tópicos mais avançados (3Blue1Brown).

Modelo PCAM

Apresentação de conceitos para construção de programas paralelos:

Particionamento
Comunicação
Aglomeração
Mapeamento

Etapas:

Particionamento / Comunicação: Focam na escabilidade de uma solução.
- Procurar algoritmos que oferecem um paralelismo extremo;
- A maior concorrência possível entre as unidades de processamento;
Aglomeração / Mapeamento: Focam na preocupação com desempenho.
- Necessita de conhecimentos de configuração da plataforma de execução.
- Como mapear para os recursos computacionais.
- Como balancear a carga.

Provavelmente esse tipo de técnica pode ser aplicada de maneira cíclica.

Particionamento

Objetivo: Descobrir oportunidades de paralelismo.

Identificar operações que podem ser utilizadas em paralelo.
Identificar a menor operação possível, a menor granulidade (grão).

Um tamanho muito pequeno para operação poderia causar problemas, como: comunicação excessiva e tarefas demais.

Particionamento de dados (decomposição de domínio)

Objetivo: Particionamento do problema com enfoque em seus dados. Cada pedaço do problema terá os dados e suas operações, usualmente dividos num mesmo tamanho.

Particionamento de operações (decomposição funcional)

Objetivo: Particionamento do problema com enfoque em suas operações. Divide-se as operações que podem ser executadas de maneira concorrente, criando partes funcionais.

Comunicação

Objetivo: Fase essencial para que os processos conversem entre si, compartilhando informações; no entanto, a comunicação implica em sincronização, o que prejudica o alto desempenho.

Definições

Local: Necessita dados de poucas partições vizinhas.
Global: Necessita dados de todas as partições.
Assíncrona : O emissor não sabe quando os dados serão utilizados, apenas os envia.
Síncrona : Emissor e receptor estão cientes quando a operação acontece.

Aglomeração

Objetivo : Tornar o algortimo mais realista, considerando os limites impostos pela plataforma alvo. E também, obter um programa eficiente na plataforma, aumentando a localidade do cálculo. Benefícios :

Impacto em diretivas de comunicação.
Benefícios da replicação de dados e operações.
Necessidade da redução drástica do número total de tarefas (uma por unidade de processamento).

Mapeamento

Objetivo : Definir onde cada tarefa será executada. É uma tarefa complexa, pois:

Deve ser explícito em supercomputadores de alto desempenho.
Soluções simples podem ser empregados; entretanto, com um baixo desempenho.

Mapeamento simples

Pré-condições :

Custo computacional das tarefas é estático (ao longo do tempo)
Custo computacional das tarefas é homogêneo (entre as partições)
Supercomputador tem capidade homogênea, e a rede de interconexão também.

Aglomeramos as partições para ter uma por núcleo, assim evitamos ao máximo a comunicação.

Mapeamento mais complexo

Cenário onde as partições tem custos computacionais diferentes (heterogêneas), ainda que sejam estáticas ao longo do tempo de execução.

Algoritmos de balanceamento de carga

Estes algoritmos permitem equilibrar o cálculo, e também encontrar a melhor granulidade.

Bisseção recursiva (Barnes-Hut, centralizado/distribuído)

Simples : unicamente pelas coordenadas.
Melhor : método de balanceamento (somente comunicações).
Bisseção recursiva : para malhas irregulares.

Balanceamento de carga local

Algoritmo distribuído.

Escalonamento de tarefas

Existe um maestro escalonador que define em quais núcleos de processamento as tarefas irão executar.

Funcionamento : poll of problems O maestro equipa-se de uma heurística de escalonamento, onde ele decide durante a execução onde mapear as tarefas.

SimGrid

Instalação no Mac OSX

Instalação da biblioteca C Boost:

Entre no site oficial da biblioteca Boost e baixe a versão 1.70:

https://www.boost.org/users/history/version_1_70_0.html

Na pasta em que o arquivo foi salvo:

tar -xzf boost_1_70_0.tar.gz
cd boost_1_70_0

E então, configure:

./bootstrap.sh --prefix=/usr/local/include

Compile os arquivos e instale a biblioteca:

./b2
./b2 install

Download do SIMGRID no site oficial:

Site oficial

Extrair o arquivo:

tar -xvf SimGrid-x.x.x.tar.gz

Entrar no diretório:

cd SimGrid-x.x.x

Gerar todos os makefiles (assumindo que você deseja instalar no folder /usr/local):

cmake -DCMAKE_INSTALL_PREFIX=/usr/local -Denable_smpi=on -Denable_documentation=off

Alterar no arquivo CmakeCache.txt de /usr/bin/python para /usr/bin/python3

Compilar os arquivos:

make

Executar os testes:

make check

Instalar bibliotecas e executáveis:

sudo make install

Versões para instalação

Boost 1.17.0 *Cmake 3.15.1 Python 3+

Descrevendo as plataformas de simulação

Para utilização do SMPI é necessário descrever qual a topologia do ambiente, e para isso utiliza-se um arquivo XML contendo informações dos hosts e dos links que os interligam.

Três hosts

Uma das topologias mais simples que foram apresentadas, contém 3 hosts conectados através de 3 links, onde existe um host com muito poder computacional (host2), 40 vezes mais que o host0, e o link2 possuindo 5 vezes mais velocidade que o link1.

<?xml version='1.0'?>
<!DOCTYPE platform SYSTEM "http://simgrid.gforge.inria.fr/simgrid/simgrid.dtd">
<platform version="4.1">
   <zone id="AS0" routing="Full">
     <host id="host0" speed="1Gf"/>
     <host id="host1" speed="2Gf"/>
     <host id="host2" speed="40Gf"/>
     <link id="link0" bandwidth="125MBps" latency="100us"/>
     <link id="link1" bandwidth="50MBps" latency="150us"/>
     <link id="link2" bandwidth="250MBps" latency="50us"/>
     <route src="host0" dst="host1"><link_ctn id="link0"/><link_ctn id="link1"/></route>
     <route src="host1" dst="host2"><link_ctn id="link1"/><link_ctn id="link2"/></route>
    <route src="host0" dst="host2"><link_ctn id="link0"/><link_ctn id="link2"/></route>
  </zone>
</platform>

Cluster homogêneo com um crossbar switch

Uma plataforma de processamento paralelo muito comum é um cluster homogêneo, contendo N hosts conectados em um switch que é muito mais rápido que as conexões, portanto sua latência e banda são desconsideradas.

<?xml version='1.0'?>
<!DOCTYPE platform SYSTEM "http://simgrid.gforge.inria.fr/simgrid/simgrid.dtd">
<platform version="4.1">
    <zone id="AS0" routing="Full">
        <cluster id="my_cluster" prefix="host-" suffix=".hawaii.edu" radical="0-255" speed="1Gf" bw="125Mbps" lat="5us"/>
    </zone>
</platform>

Cluster homogêneo com um backbone compartilhado

Uma plataforma de processamento paralelo muito comum é um cluster homogêneo conectado a um meio de comunicação compartilhado, um backbone, que contém capacidade de banda finita.

<?xml version='1.0'?>
<!DOCTYPE platform SYSTEM "http://simgrid.gforge.inria.fr/simgrid/simgrid.dtd">
<platform version="4.1">
  <zone id="AS0" routing="Full">
    <cluster id="my_cluster" prefix="host−" suffix=".hawaii.edu" radical="0−255" speed="1Gf" bw="125Mbps" lat="50us" bb_bw="2.25Gbps" bb_lat="500us"/>
  </zone>
</platform>

Dois clusters conectados

É possível conectar clusters e de fato construir ambientes de procesamento paralelo com hierarquias.

<?xml version='1.0'?>
<!DOCTYPE platform SYSTEM "http://simgrid.gforge.inria.fr/simgrid/simgrid.dtd">
<platform version="4.1">
  <zone id="AS0" routing="Full">
    <cluster id="my_cluster_1" prefix="C1−" suffix=".hawaii.edu" radical="0−15" speed="1Gf" bw="125Mbps" lat="50us" bb_bw="2.25Gbps" bb_lat="500us" />
    <cluster id="my_cluster_2" prefix="C2−" suffix=".hawaii.edu" radical="0−31" speed="2Gf" bw="125Mbps" lat="50us" />
    <link id="internet_backbone" bandwidth="0.01Gbps" latency="22500us" />
    <zoneRoute src="my_cluster_1" dst="my_cluster_2" gw_src="C1−my_cluster_1_router.hawaii.edu" gw_dst="C2−my_cluster_2_router.hawaii.edu" symmetrical="YES">
      <link_ctn id="internet_backbone" />
    </zoneRoute>
  </zone>
</platform>

Comandos comuns do MPI

MPI_Init

Inicializa o ambiente de execução do MPI.

int MPI_Init(int *argc, char ****argv)

MPI_Comm_rank

Determina o rank do processo com o comunicador.

int MPI_Comm_rank(MPI_Comm comm, int **rank)

Input:

MPI_Comm comm - Communicator (handler)

Output:

int **rank - Rank of the calling process in group of comm (integer).

MPI_Comm_size

Retorna o número de processos associados a um comunicador.

int MPI_Comm_size(MPI_Comm comm, int **size)

Input:

MPI_Comm comm - Communicator (handler)

Output:

int **size - Number of processes in the group of comm (integer).

MPI_Get_processor_name

Retorna um identificador único para o processo.

int MPI_Get_processor_name(char **name, int **resultlen)

Ouput:

char **name - A unique specifier for the actual (as opposed to virtual) node.

int **resultlen - Length (in characters) of result returned in name.

MPI_Finalize

Termina o ambiente de execução do MPI

MPI_Finalize()

MPI_Send

Envia uma mensagem bloqueante.

int MPI_Send(const void **buf, int count, MPI_Datatype datatype, int dest ,int tag, MPI_Comm comm)

Input:

const void **buf - Initial address of send buffer (choice). int count - Number of elements send (nonnegative integer). MPI_Datatype datatype - Datatype of each send buffer element (handle). int dest - Rank of destination (integer). int tag - Message tag (integer). MPI_Comm comm - Communicator (handle).

MPI_Recv

Recebe uma mensagem bloqueante.

int MPI_Recv(void **buf, int count, MPI_Datatype datatype, int source, int tag, MPI_Comm comm, MPI_Status **status)

Input:

int count - Maximum number of elements to receive (integer). MPI_Datatype datatype - Datatype of each receive buffer entry (handle). int source - Rank of source (integer). int tag - Message tag (integer). MPI_Comm comm - Communicator (handle).

Output:

void **buf - Initial address of receive buffer (choice). MPI_Status **status - Status object (status).

Primeiro programa usando SMPI

Contextualização : Consiste em um programa onde os processos passam uma mensagem adiante em uma topologia de anel, e após todas mensagens serem enviadas e o nodo #0 receber a mensagem, ele imprime o tempo gasto na tela.

Código em C

#include <stdio.h>
#include <stdlib.h>
#include <mpi.h>

#define N (1024 * 1024 * 1)

int main(int argc, char *argv[])
{
  int size, rank;
  struct timeval start, end;
  char hostname[256];
  int hostname_len;

  MPI_Init(&argc, &argv);

  MPI_Comm_rank(MPI_COMM_WORLD, &rank);
  MPI_Comm_size(MPI_COMM_WORLD, &size);
  MPI_Get_processor_name(hostname,&hostname_len);

  // Allocate a 10MiB buffer
  char *buffer = malloc(sizeof(char) * N);

  // Communicate along the ring
  if (rank == 0) {
        gettimeofday(&start,NULL);
        printf("Rank %d (running on '%s'): sending the message rank %d\n",rank,hostname,1);
	MPI_Send(buffer, N, MPI_BYTE, 1, 1, MPI_COMM_WORLD);
       	MPI_Recv(buffer, N, MPI_BYTE, size-1, 1, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
        printf("Rank %d (running on '%s'): received the message from rank %d\n",rank,hostname,size-1);
  	gettimeofday(&end,NULL);
  	printf("%f\n",(end.tv_sec*1000000.0 + end.tv_usec -
		 	start.tv_sec*1000000.0 - start.tv_usec) / 1000000.0);

  } else {
       	MPI_Recv(buffer, N, MPI_BYTE, rank-1, 1, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
        printf("Rank %d (running on '%s'): receive the message and sending it to rank %d\n",rank,hostname,(rank+1)%size);
	MPI_Send(buffer, N, MPI_BYTE, (rank+1)%size, 1, MPI_COMM_WORLD);
  }

  MPI_Finalize();
  return 0;
}

Para simular esse código utilizando o SIMGRID é necessário mais dois arquivos: o arquivo de configuração da plataforma e o arquivo de configuração dos hosts, que basicamente lista todos os hosts disponíveis.

Configuração da plataforma

    <?xml version='1.0'?>
<!DOCTYPE platform SYSTEM "http://simgrid.gforge.inria.fr/simgrid/simgrid.dtd">
<platform version="4.1">
    <zone id="AS0" routing="Full">
        <cluster id="my_cluster" prefix="host-" suffix=".hawaii.edu" radical="0-255" speed="1Gf" bw="125Mbps" lat="5us"/>
    </zone>
</platform>

Lista de hosts

host-0.hawaii.edu
host-1.hawaii.edu
host-2.hawaii.edu
host-3.hawaii.edu
host-4.hawaii.edu
host-5.hawaii.edu
host-6.hawaii.edu
host-7.hawaii.edu
host-8.hawaii.edu
host-9.hawaii.edu
host-10.hawaii.edu
host-11.hawaii.edu
host-12.hawaii.edu
host-13.hawaii.edu
host-14.hawaii.edu
host-15.hawaii.edu
host-16.hawaii.edu
host-17.hawaii.edu
host-18.hawaii.edu
host-19.hawaii.edu
host-20.hawaii.edu
host-21.hawaii.edu
host-22.hawaii.edu
host-23.hawaii.edu
host-24.hawaii.edu
host-25.hawaii.edu
host-26.hawaii.edu
host-27.hawaii.edu
host-28.hawaii.edu
host-29.hawaii.edu
host-30.hawaii.edu
host-31.hawaii.edu
host-32.hawaii.edu
host-33.hawaii.edu
host-34.hawaii.edu
host-35.hawaii.edu
host-36.hawaii.edu
host-37.hawaii.edu
host-38.hawaii.edu
host-39.hawaii.edu
host-40.hawaii.edu
host-41.hawaii.edu
host-42.hawaii.edu
host-43.hawaii.edu
host-44.hawaii.edu
host-45.hawaii.edu
host-46.hawaii.edu
host-47.hawaii.edu
host-48.hawaii.edu
host-49.hawaii.edu
host-50.hawaii.edu
host-51.hawaii.edu
host-52.hawaii.edu
host-53.hawaii.edu
host-54.hawaii.edu
host-55.hawaii.edu
host-56.hawaii.edu
host-57.hawaii.edu
host-58.hawaii.edu
host-59.hawaii.edu
host-60.hawaii.edu
host-61.hawaii.edu
host-62.hawaii.edu
host-63.hawaii.edu
host-64.hawaii.edu
host-65.hawaii.edu
host-66.hawaii.edu
host-67.hawaii.edu
host-68.hawaii.edu
host-69.hawaii.edu
host-70.hawaii.edu
host-71.hawaii.edu
host-72.hawaii.edu
host-73.hawaii.edu
host-74.hawaii.edu
host-75.hawaii.edu
host-76.hawaii.edu
host-77.hawaii.edu
host-78.hawaii.edu
host-79.hawaii.edu
host-80.hawaii.edu
host-81.hawaii.edu
host-82.hawaii.edu
host-83.hawaii.edu
host-84.hawaii.edu
host-85.hawaii.edu
host-86.hawaii.edu
host-87.hawaii.edu
host-88.hawaii.edu
host-89.hawaii.edu
host-90.hawaii.edu
host-91.hawaii.edu
host-92.hawaii.edu
host-93.hawaii.edu
host-94.hawaii.edu
host-95.hawaii.edu
host-96.hawaii.edu
host-97.hawaii.edu
host-98.hawaii.edu
host-99.hawaii.edu
host-100.hawaii.edu
host-101.hawaii.edu
host-102.hawaii.edu
host-103.hawaii.edu
host-104.hawaii.edu
host-105.hawaii.edu
host-106.hawaii.edu
host-107.hawaii.edu
host-108.hawaii.edu
host-109.hawaii.edu
host-110.hawaii.edu
host-111.hawaii.edu
host-112.hawaii.edu
host-113.hawaii.edu
host-114.hawaii.edu
host-115.hawaii.edu
host-116.hawaii.edu
host-117.hawaii.edu
host-118.hawaii.edu
host-119.hawaii.edu
host-120.hawaii.edu
host-121.hawaii.edu
host-122.hawaii.edu
host-123.hawaii.edu
host-124.hawaii.edu
host-125.hawaii.edu
host-126.hawaii.edu
host-127.hawaii.edu
host-128.hawaii.edu
host-129.hawaii.edu
host-130.hawaii.edu
host-131.hawaii.edu
host-132.hawaii.edu
host-133.hawaii.edu
host-134.hawaii.edu
host-135.hawaii.edu
host-136.hawaii.edu
host-137.hawaii.edu
host-138.hawaii.edu
host-139.hawaii.edu
host-140.hawaii.edu
host-141.hawaii.edu
host-142.hawaii.edu
host-143.hawaii.edu
host-144.hawaii.edu
host-145.hawaii.edu
host-146.hawaii.edu
host-147.hawaii.edu
host-148.hawaii.edu
host-149.hawaii.edu
host-150.hawaii.edu
host-151.hawaii.edu
host-152.hawaii.edu
host-153.hawaii.edu
host-154.hawaii.edu
host-155.hawaii.edu
host-156.hawaii.edu
host-157.hawaii.edu
host-158.hawaii.edu
host-159.hawaii.edu
host-160.hawaii.edu
host-161.hawaii.edu
host-162.hawaii.edu
host-163.hawaii.edu
host-164.hawaii.edu
host-165.hawaii.edu
host-166.hawaii.edu
host-167.hawaii.edu
host-168.hawaii.edu
host-169.hawaii.edu
host-170.hawaii.edu
host-171.hawaii.edu
host-172.hawaii.edu
host-173.hawaii.edu
host-174.hawaii.edu
host-175.hawaii.edu
host-176.hawaii.edu
host-177.hawaii.edu
host-178.hawaii.edu
host-179.hawaii.edu
host-180.hawaii.edu
host-181.hawaii.edu
host-182.hawaii.edu
host-183.hawaii.edu
host-184.hawaii.edu
host-185.hawaii.edu
host-186.hawaii.edu
host-187.hawaii.edu
host-188.hawaii.edu
host-189.hawaii.edu
host-190.hawaii.edu
host-191.hawaii.edu
host-192.hawaii.edu
host-193.hawaii.edu
host-194.hawaii.edu
host-195.hawaii.edu
host-196.hawaii.edu
host-197.hawaii.edu
host-198.hawaii.edu
host-199.hawaii.edu
host-200.hawaii.edu
host-201.hawaii.edu
host-202.hawaii.edu
host-203.hawaii.edu
host-204.hawaii.edu
host-205.hawaii.edu
host-206.hawaii.edu
host-207.hawaii.edu
host-208.hawaii.edu
host-209.hawaii.edu
host-210.hawaii.edu
host-211.hawaii.edu
host-212.hawaii.edu
host-213.hawaii.edu
host-214.hawaii.edu
host-215.hawaii.edu
host-216.hawaii.edu
host-217.hawaii.edu
host-218.hawaii.edu
host-219.hawaii.edu
host-220.hawaii.edu
host-221.hawaii.edu
host-222.hawaii.edu
host-223.hawaii.edu
host-224.hawaii.edu
host-225.hawaii.edu
host-226.hawaii.edu
host-227.hawaii.edu
host-228.hawaii.edu
host-229.hawaii.edu
host-230.hawaii.edu
host-231.hawaii.edu
host-232.hawaii.edu
host-233.hawaii.edu
host-234.hawaii.edu
host-235.hawaii.edu
host-236.hawaii.edu
host-237.hawaii.edu
host-238.hawaii.edu
host-239.hawaii.edu
host-240.hawaii.edu
host-241.hawaii.edu
host-242.hawaii.edu
host-243.hawaii.edu
host-244.hawaii.edu
host-245.hawaii.edu
host-246.hawaii.edu
host-247.hawaii.edu
host-248.hawaii.edu
host-249.hawaii.edu
host-250.hawaii.edu
host-251.hawaii.edu
host-252.hawaii.edu
host-253.hawaii.edu
host-254.hawaii.edu
host-255.hawaii.edu

Execução do programa

Após a criação desse arquvio, basta compilar e executar o código.

smpicc -O4 roundtrip.c -o roundtrip

smpirun -np 16 -hostfile ./cluster_hostfile.txt -platform ./cluster_crossbar.xml ./roundtrip

A flag -np serve para explicitar o número de processos MPI que

serão utilizados.

A flag -hostfile serve para adicionar a listagem de hosts disponíveis.
A flag -plataform serve para explicitar a configuração da plataforma que será usada no experimento.

Computando um conjunto de Julia

O que é? Um Conjunto de Julia nada mais é do que dois conjuntos complementares definidos por uma função matemática.

/begin{cases} z_0 = z z_n+1 = z_n^2 + c /end{cases}

onde c = -0.79 + 0.15i, onde diferentes valores para c geram diferentes conjuntos de Julia.

Implementação sequencial

Nessa implementação haviam alguns requisitos para serem respeitados:

Receber um número N inteiro positivo como paramêtro de entrada para a solução.
Alocação de um vetor do tipo unsigned char de N * (2 * N) * 3 elementos.
Preenchimento desse vetor com os valores (RGB) correspondentes ao conjunto de Julia.

Foi utilizada uma função auxiliar compute_julia_pixel() para gerar os valores RGB para o pixels, conforme um conjunto de Julia. Após a criação desse vetor unidimensional que contém todos os pixels do conjunto de Julia, foi criado um arquivo de imagem do tipo bpm para visualização do conjunto.

Código em C

int main(int argc, char *argv[]) {
    /* 
     *   Size of an Julia's set image => argv[1]
     *
     *   HEIGTH => n pixels
     *   WIDTH => 2n pixels
     */
    int n = atoi(argv[1]);

    if (n < 0) {
        printf("N should be a positive number!\n");
        return 0;
    }

    int width = 2 * n;
    int heigth = n;
    int rgb_pixels = 3;
    int pixels_size = width * heigth * rgb_pixels;
    unsigned char *pixels = malloc(sizeof(unsigned char) * pixels_size);
    float tint_bias = 1.0;

    // Compute pixels
    for (int x = 0; x < width; x++) {
        for (int y = 0; y < heigth; y++) {
            int result = compute_julia_pixel(x, y, width, heigth, tint_bias, &pixels[rgb_pixels * ((y * width) + x)]);
        }
    }

    // Write file with the pixels value
    FILE *fp;
    fp = fopen("julia.bpm", "w");
    int res = write_bmp_header(fp, width, heigth);
    fwrite(pixels, sizeof(char), pixels_size, fp);
    fclose(fp);

    return 0;
}

Foi utilizado um vetor de 1-D para salvar todos os pixels da imagem que corresponde ao conjunto de Julia. Através de uma organização por linhas, onde cada linha da imagem é salva em sequência (row-major scheme) de modo que uma imagem com largura N, o pixel(i,j) seja salvo no vetor na posição Array[i * N + j]; entretanto, como esse array possui a dimensão de N * 2N * 3 foi necessário deslocar o vetor em 3 posições, portanto, para localizar o valor RGB do pixel(i,j) em questão, basta deslocar o vetor da seguinte maneira: Array[RGB * ((i * N) + j)], onde R = 1, G = 2 e B = 3.

Compilando e executando

Para compilar, basta:

make sequential

E para executar, basta passar o número N (que deve ser um número par), onde N que corresponde a altura da imagem, e 2 * N corresponde a largura da imagem que será gerada.

./sequential_julia 100

Implementação paralela usando um vetor de 1-D

Nessa implementação a ideia principal era distribuir o processamento dos pixels através de N processos, rodando sobre a arquitetura MPI, utilizando o simulador SIMGRID.

Solução

O problema foi repartido da seguinte maneira:

Cada processo N, de um total de X processos, calculou uma parte igual dos pixels da imagem. Dado uma imagem com altura L e largura 2L, então cada processo N acabou calculando 2L * (L/X) * 3 pixels da imagem; entranto, guardam esses pixels em um vetor de 2L * X * 3 posições.
Após o cálculo de determinada região da imagem ser feito de forma distribuída, coube ao primeiro processo escrever sua parte em um arquivo de nome julia1d.bpm e mais o header específico dos arquivos de tipo BPM.
Os outros processos tiveram o trabalho de gravar 2L * (L/X) * 3 pixels ao final do arquivo.
Cada processo N tem como responsabilidade enviar a mensagem “go ahead!” para que o próximo processo execute.

Código em C

int main(int argc, char *argv[]) {
    /* 
     *   Size of an Julia's set image => argv[1]
     *
     *   HEIGTH => n pixels
     *   WIDTH => 2n pixels
     */
    int n = atoi(argv[1]);

    if (n < 0) {
        printf("N should be a positive number!\n");
        return 0;
    }

    int size, rank;
    char hostname[1024];
    int hostname_len;

    MPI_Init(&argc, &argv);

    MPI_Comm_rank(MPI_COMM_WORLD, &rank);
    MPI_Comm_size(MPI_COMM_WORLD, &size);
    MPI_Get_processor_name(hostname, &hostname_len);

    int width = 2 * n;
    int heigth = n;
    int rows = n / size;
    int rgb_pixels = 3;
    int pixels_size = width * rows * rgb_pixels;
    float tint_bias = 1.0;
    unsigned char *pixels_row = malloc(sizeof(char) * pixels_size);

    int initial_heigth_pos = (((rank) % size) * rows);
    int last_heigth_pos = (((rank + 1) == size) ? (size * rows) : (((rank + 1) % size) * rows));

    for (int x = 0; x < width; x++) {
        for (int y = initial_heigth_pos, row = 0; y < last_heigth_pos && row < rows; y++, row++) {
            int result = compute_julia_pixel(x, y, width, heigth, tint_bias, &pixels_row[rgb_pixels * ((row * width) + x)]);
        }
    }

    char message[10] = "Go ahead!";
    char *buffer = malloc(sizeof(char) * 11);

    if (rank == 0) {
        FILE *fp;
        fp = fopen("julia1d.bpm", "w");
        // Write BPM Header
        int res = write_bmp_header(fp, width, heigth);
        // Write pixel values
        fwrite(pixels_row, sizeof(char), pixels_size, fp);
        fclose(fp);
        // Send a message to the next process
        MPI_Send(message, sizeof(message), MPI_BYTE, 1, 1, MPI_COMM_WORLD);
    } else {
        MPI_Recv(buffer, sizeof(buffer), MPI_BYTE, rank - 1, 1, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
        // Open and save all pixels at EOF
        FILE *fp;
        fp = fopen("julia1d.bpm", "a");
        fwrite(pixels_row, sizeof(char), pixels_size, fp);

        // Free pointers
        fclose(fp);
        // The last process doesnt send an MPI Message
        if (!is_last_process(rank, size)) {
            MPI_Send(message, sizeof(message), MPI_BYTE, (rank + 1) % size, 1, MPI_COMM_WORLD);
        }
    }

    MPI_Finalize();
}

Compilando e executando

Para compilar, basta:

make 1d

E agora, basta rodar o comando smpirun para executar o programa, em uma plataforma alvo. Segue abaixo o exemplo de execução de uma imagem 2000x1000 pixels.

smpirun -np 5 -hostfile ./simple_cluster_hostfile.txt -platform ./simple_cluster.xml ./1D_parallel_julia 1000

Implementação paralela usando um vetor de 2-D

Nessa implementacão a ideia principal era distribuir o processamento dos pixels através de N processos, entretanto com uma particularidade em relação a anterior, agora cada processo ficará responsável por calcular os pixels de uma determinada faixa de altura e largura da imagem, fazendo assim com que os dados sejam distrubidos em uma espécie de plano cartesiano.

Solução

O problema foi repartido da seguinte mandeira:

Cada processo N, de um total de X processos, calculou uma parte igual dos pixels da imagem. Dado uma imagem com altura L e largura 2L, assumiu-se que L dividido pela raíz quadrada de X é um número inteiro. Sabendo disso, cada processo N ficou uma fatia de N / sqrt(X) de altura e 2 * N / sqrt(X) de largura.
Após o cálculo de todos as regiões, cada processo teve que escrever apenas uma linha por vez da fatia que calculou.

Código em C

int main(int argc, char *argv[]) {
    /* 
     *   Size of an Julia's set image => argv[1]
     *
     *   HEIGTH => n pixels
     *   WIDTH => 2n pixels
     */
    int n = atoi(argv[1]);

    if (n < 0) {
        printf("N should be a positive number!\n");
        return 0;
    }

    int size, rank;
    char hostname[1024];
    int hostname_len;

    MPI_Init(&argc, &argv);

    MPI_Comm_rank(MPI_COMM_WORLD, &rank);
    MPI_Comm_size(MPI_COMM_WORLD, &size);
    MPI_Get_processor_name(hostname, &hostname_len);

    int width = 2 * n;
    int heigth = n;
    int matrix_dim = sqrt(size);
    int row_size = n / matrix_dim;
    int column_size = (2 * n) / matrix_dim;
    int rgb_pixels = 3;
    float tint_bias = pow(rank, 2); 
    int pixels_cell_size = row_size * column_size * rgb_pixels;
    unsigned char* pixels_cell = malloc(sizeof(unsigned char) * pixels_cell_size);    

    MPI_Comm new_comm;
    int coord[2];

    get_process_coord(new_comm, coord, matrix_dim, rank);

    // Set coordenates
    int initial_heigth_pos = coord[0] * row_size;
    int last_heigth_pos = (coord[0] + 1) * row_size;
    int initial_width_pos = coord[1] * column_size;
    int last_width_pos = (coord[1] + 1) * column_size;

    // Compute pixels from the respective tile    
    for (int x = initial_width_pos, column = 0; x < last_width_pos && column < column_size; x++, column++) {
        for (int y = initial_heigth_pos, row = 0; y < last_heigth_pos && row < row_size; y++, row++) {
            int result = compute_julia_pixel(x, y, width, heigth, tint_bias, &pixels_cell[rgb_pixels * ((row * column_size) + column)]);
        }
    }

    char message[10] = "Go ahead!";
    char *buffer = malloc(sizeof(char) * 11);

    if (rank == 0) {
        // First process should write the BMP Header
        FILE *fp;
        fp = fopen("julia2d.bmp", "w");
        // Write BPM Header
        int res = write_bmp_header(fp, width, heigth);
        int tile_size = column_size * rgb_pixels;
        int section_size = row_size;
        // Write first section and close the file
        fwrite(&pixels_cell, sizeof(char), tile_size, fp);
        fclose(fp);
        // Send message to process 1
        MPI_Send(message, sizeof(message), MPI_BYTE, 1, 1, MPI_COMM_WORLD);
        for (int j = 1; j < section_size; j++) {
            // Receive a message from the last process at line, then write the next section
            MPI_Recv(buffer, sizeof(message), MPI_BYTE, matrix_dim - 1, 1, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
            fp = fopen("julia2d.bmp", "a");
            fwrite(&pixels_cell[rgb_pixels * (j * column_size)], sizeof(char), tile_size, fp);
            fclose(fp);
            // Send message to process 1
            MPI_Send(message, sizeof(message), MPI_BYTE, 1, 1, MPI_COMM_WORLD);
        }
        // Send a message to the process that has a rank equals to matrix dimension (NxN)
        MPI_Send(message, sizeof(message), MPI_BYTE, matrix_dim, 1, MPI_COMM_WORLD);
    } else if (rank % matrix_dim == 0) {
        int tile_size = column_size * rgb_pixels;
        int section_size = row_size;
        FILE *fp;
        // The first process of each row should write the first section and they always receive the message
        // from the last process of the previous row
        MPI_Recv(buffer, sizeof(message), MPI_BYTE, rank - matrix_dim, 1, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
        fp = fopen("julia2d.bmp", "a");
        fwrite(&pixels_cell, sizeof(char), tile_size, fp);
        fclose(fp);
        // Send a message to next process
        MPI_Send(message, sizeof(message), MPI_BYTE, rank + 1, 1, MPI_COMM_WORLD);
        for (int j = 1; j < section_size; j++) {
            // Receive a message from the last process of the current row
            MPI_Recv(buffer, sizeof(message), MPI_BYTE, rank + matrix_dim - 1, 1, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
            fp = fopen("julia2d.bmp", "a");
            fwrite(&pixels_cell[rgb_pixels * (j * column_size)], sizeof(char), tile_size, fp);
            fclose(fp);
            // Send a message to next process
            MPI_Send(message, sizeof(message), MPI_BYTE, rank + 1, 1, MPI_COMM_WORLD);
        }
        if (is_not_last_process_in_cartesian_plan(rank, matrix_dim, size)) {
            MPI_Send(message, sizeof(message), MPI_BYTE, rank + matrix_dim, 1, MPI_COMM_WORLD);
        }
    } else if ((rank + 1) % matrix_dim == 0) {
        int tile_size = column_size * rgb_pixels;
        int section_size = row_size;
        FILE *fp;
        for (int j = 0; j < section_size; j++) {
            // Receive a message from the previous process
            MPI_Recv(buffer, sizeof(message), MPI_BYTE, rank - 1, 1, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
            fp = fopen("julia2d.bmp", "a");
            fwrite(&pixels_cell[rgb_pixels * (j * column_size)], sizeof(char), tile_size, fp);
            fclose(fp);
            // The last process of each row should send a message to the first one
            MPI_Send(message, sizeof(message), MPI_BYTE, (rank + 1) - matrix_dim, 1, MPI_COMM_WORLD);
        }
    } else {
        int tile_size = column_size * rgb_pixels;
        int section_size = row_size;
        FILE *fp;
        for (int j = 0; j < section_size; j++) {
            // If isn't a boundire process in the cartesion plan distribution, receive a message from the previous process
            MPI_Recv(buffer, sizeof(message), MPI_BYTE, rank - 1, 1, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
            fp = fopen("julia2d.bmp", "a");
            fwrite(&pixels_cell[rgb_pixels * (j * column_size)], sizeof(char), tile_size, fp);
            fclose(fp);
            // And send a message to the next process
            MPI_Send(message, sizeof(message), MPI_BYTE, rank + 1, 1, MPI_COMM_WORLD);
        }
    }
    
    MPI_Finalize();
}

Compilando e executando

Para compilar, basta:

make 2d

E agora, basta rodar o comando smpirun para executar o programa, em uma plataforma alvo. Segue abaixo o exemplo de execução de uma imagem 2000x1000 pixels.

Note que 300 / sqrt(9) é um número natural.

smpirun -np 9 -hostfile ./simple_cluster_hostfile.txt -platform ./simple_cluster.xml ./2D_parallel_julia 300

Files

labBook.org

Latest commit

History

labBook.org

File metadata and controls

Aprendendo MPI/SimGrid

Reuniões

<2019-08-26> Apresentação dos resultados parciais

Modelo PCAM

Particionamento

Particionamento de dados (decomposição de domínio)

Particionamento de operações (decomposição funcional)

Comunicação

Definições

Aglomeração

Mapeamento

Mapeamento simples

Mapeamento mais complexo

Algoritmos de balanceamento de carga

Bisseção recursiva (Barnes-Hut, centralizado/distribuído)

Balanceamento de carga local

Escalonamento de tarefas

SimGrid

Instalação no Mac OSX

Instalação da biblioteca C Boost:

Download do SIMGRID no site oficial:

Extrair o arquivo:

Entrar no diretório:

Gerar todos os makefiles (assumindo que você deseja instalar no folder /usr/local):

Alterar no arquivo CmakeCache.txt de /usr/bin/python para /usr/bin/python3

Compilar os arquivos:

Executar os testes:

Instalar bibliotecas e executáveis:

Versões para instalação

Descrevendo as plataformas de simulação

Três hosts

Cluster homogêneo com um crossbar switch

Cluster homogêneo com um backbone compartilhado

Dois clusters conectados

Comandos comuns do MPI

MPI_Init

MPI_Comm_rank

MPI_Comm_size

MPI_Get_processor_name

MPI_Finalize

MPI_Send

MPI_Recv

Primeiro programa usando SMPI

Código em C

Configuração da plataforma

Lista de hosts

Execução do programa

Computando um conjunto de Julia

Implementação sequencial

Código em C

Compilando e executando

Implementação paralela usando um vetor de 1-D

Solução

Código em C

Compilando e executando

Implementação paralela usando um vetor de 2-D

Solução

Código em C

Compilando e executando