diegohuesos / mpi-parallel-words-bag

Parallel program implemented with MPI and serial program implemented in C++.

Experimento de paralelización de conteo de palabras de distintos libros implementado en lenguaje de programación C++ y el estándar MPI

Instituto Tecnológico Autónomo de México

Cómputo Paralelo y en la Nube

Profesor

Dr. José Octavio Gutiérrez García

Integrantes

Diego Hernández Delgado - 176262

Isaías Jesús García Moreno - 179474

Introducción

El presente proyecto consiste en la comparación entre la eficiencia de la implementación serial y la implementación paralela de un algoritmo de conteo de palabras conocido como Bolsa de palabras.

Objetivos

• Implementar el algoritmo Bolsa de palabras de forma serial en lenguaje de programación C++, medir su tiempo de ejecución y almacenar los resultados.

• Implementar el algoritmo Bolsa de palabras de forma paralela en lenguaje de programación C++ y el estándar MPI, medir su tiempo de ejecución y almacenar los resultados.

• Cada prueba debe ser ejecutada diez veces y se debe calcular el promedio de los tiempos de ejecución.

• Comparar la eficiencia de la implementación serial y la implementación paralela del algoritmo de Bolsa de palabras, mediante la obtención de la gráfica de speedups.

• Realizar un análisis de resultados y determinar las conclusiones correspondientes.

Estructura del proyecto

• .vscode/

  • c_cpp_properties.json
  • settings.json
  • tasks.json

• Books/

  • dickens_a_christmas_carol.txt
  • dickens_a_tale_of_two_cities.txt
  • dickens_oliver_twist.txt
  • shakespeare_hamlet.txt
  • shakespeare_romeo_juliet.txt
  • shakespeare_the_merchant_of_venice.txt

• computo_paralelo_bolsa_de_palabras.ipynb

• parallel_output.csv

• Parallel_Words_Bag.cpp

• Parallel_Words_Bag.exe

• README.md

• run_parallel.bat

• run_serial.bat

• serial_output.csv

• Serial_Words_Bag.cpp

• Serial_Words_Bag.exe

• vocabulario.csv

Ejecución del experimento

Para la implementación del algoritmo de Bolsa de palabras en lenguaje de programación C++ se utilizó la biblioteca de MPI para la paralelización del algoritmo.

Para ejecutar el proceso completo del experimento, se debe ejcutar el archivo run_serial.bat y, posteriormente, se debe ejecutar el archivo run_parallel.bat.

Argumentos:

• El número de procesos corresponde con el número de libros a ejecutar para que cada proceso cuente las palabras de un libro en particular. En este caso el número de procesos es 6.

• El número de puntos se itera entre los siguientes valores: 100, 100000, 200000, 300000, 400000, 600000, 800000, 1000000

Explicación detallada de la implementación

--

Estrategia de paralelización

--

Instrucciones de ejecución

--

Interpretación y análisis de resultados

El speedup observado en la implementación paralela debería ser, en principio, directamente proporcional al número de cores utilizados.

Gráficas del Speed up

Conclusiones

El speed-up es evidente porque la división el trabajo de forma paralela reduce el tiempo de ejecución.

Descripción del equipo donde se ejecutaron las pruebas

Hardware

• Computadora: Laptop Huawei Matebook 14
• Procesador: AMD Ryzen 5 3600 6-Core Processor
• Memoria RAM: 16 GB
• Disco duro: SSD 1 TB WD Blue SN550 NVMe M.2 2280
• Cores físicos: 6
• Cores lógicos: 12
• Velocidad del procesador: 3.6 GHz
• Velocidad de la memoria RAM: 3200 MHz

Software

• Sistema Operativo: Windows 11
• IDE: Visual Studio Code
• Lenguajes de programación: C++, Bash, Python
• Biblioteca de paralelización: MPI
• Compilador: g++
• Versión de C++: C++17
• Versión de Python: 3.8.5

Referencias

• MPI

• C++

• G++

• Python

• Bash

• Google Colab

• Robey, Robert, and Yuliana Zamora. Parallel and High Performance Computing. Simon and Schuster, 2021.

• Tuomanen, Brian. Hands-On GPU Programming with Python and CUDA: Explore high- performance parallel computing with CUDA. Packt Publishing Ltd, 2018.

• Wilt, Nicholas. The CUDA handbook: A comprehensive guide to gpu programming. Pearson Education, 2013.