Análise de Algoritmos Paralelos e Seriais

Universidade Federal do Rio Grande do Norte (UFRN), 2020.

Análise por:

• Oziel Alves

Objetivos

Analisar e avaliar o comportamento, eficiência e speedup dos algoritmos em relação ao seu tempo de execução, tamanho do problema analisado e resultados obtidos. Os cenários irão simular a execução dos algoritmos para 2, 4 e 8 cores, no caso dos algoritmos paralelos, com alguns tamanhos de problema definidos empiricamente, sendo o menor tamanho estabelecido com o objetivo de atingir o tempo mínimo de execução determinado pela referência da Análise (30 segundos).

Dependências

G++ Compiler

É necessário para a compilação dos programam, visto que são feitos em c++.

# Instalação no Ubuntu 20.04 LTS:
sudo apt-get install g++

MPI - Message Passing Interface

É necessário para a compilação e execução dos códigos paralelos que utilizam MPI.

# Instalação no Ubuntu 20.04 LTS:
sudo apt-get install -y mpi 

Compilação e Execução

Instaladas as dependências, basta executar o shellcript determinado para a devida bateria de execuções na raiz do repositório:
Serão realizadas 5 execuções com 4 tamanhos de problema , em 3 quantidades de cores (2, 4 e 8).

# Para o algorítimo que calcula o pi de forma serial
./Pi-Tapezio/pi_serial_start.sh

# Para o algorítimo que calcula o pi de forma paralela
./Pi-Tapezio/pi_paralelo_start.sh

# Para o algorítimo que calcula a integral de forma serial
./Pi-Tapezio/trapezio_serial_start.sh

# Para o algorítimo que calcula a integral de forma paralela
./Pi-Tapezio/trapezio_paralelo_start.sh

# Para o algorítimo que ordena uma lista gerada de forma serial
./OETSort/OETS_serial_start.sh

# Para o algorítimo que ordena uma lista gerada de forma paralela
./OETSort/OETS_paralelo_start.sh

# Para o algorítimo que realiza a multiplicação de duas matrizes M x M em ordem aleatória de forma serial
./Multz/multz1_serial_start.sh

# Para o algorítimo que realiza a multiplicação de duas matrizes M x M utilizando o princío da localidade de forma serial
./Multz/multz2_serial_start.sh

# Para o algorítimo que realiza a multiplicação de duas matrizes M x M utilizando o princío da localidade de forma paralela
./Multz/multz_paralelo_start.sh

Obs.: Caso seja necessário conceder permissão máxima para os scripts, execute:
chmod 777 [NOME DO SCRIPT].sh.

Arquivo com Resultados

Após o termino das execuções do script é possível ter acesso aos arquivos .txt na pasta ./Pi-Tapezio/pi, ./Pi-Tapezio/trapezio, ./OETSort/serial, ./OETSort/serial, ./Multz/serial e ./Multz/paralelo, de acordo com o script executado. Os dados coletados foram utilizados para da análise.

Condições de Testes

Informações sobre a máquina utilizada

• Dell Inspiron 14-inc 7460

• Processador: Intel Core i7 7500U (até 3.5 GHz) Dual Core Cache 4M. (FSB)4 GT/s OPI (Integra HyperThreading para trabalhar com até 4 threads de uma vez)

• Número de Cores/Threads: 2/4

• Memória: 8 GB tipo DDR4 – 2133MHz

• Sistema: Ubuntu 20.04.1 LTS

Apresentação dos Algoritmos

Cálculo do Pi - Método de Monte Carlo

Cálculo da Integral - Regra do Trapézio

Odd-Even Transposition Sort

Multiplicação de Matrizes Quadradas

Softwares utilizados

~$: g++ --version
g++ (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0
Copyright (C) 2019 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

~$: python3 --version
Python 3.6.4

~$: grip --version
Grip 4.2.0