Universidad Nacional Autónoma de México

Facultad de Ingeniera

Programación Paralela
Problema de las n reinas

Proyecto 2

Grupo: 05

Equipo: 05

Integrantes:

Cardoso Rodrı́guez Francisco Adrián

Genis Cruz Lourdes Victoria

Medina Segura Fernando

Enero 2021
 Objetivos
Objetivo general

Que el alumno ponga en práctica los conceptos de la programación paralela a través de la implementación
de un algoritmo paralelo, ası́ mismo desarrolle su capacidad para responder preguntas acerca de un concepto
analizado a profundidad.

Objetivo del equipo

Aplicar los conceptos de paralelismo vistos en las clases prácticas y de teorı́a sobre un problema previa-
mente resuelto de manera serial como lo es el problema de las n reinas. Ası́ mismo familiarizarse con la
aproximación que el lenguaje C tiene con el paralelismo a través de OpenMP.

Introducción
Tradicionalmente desde el surgimiento de la computación el software ha sido escrito en forma serial. En
la programación serial un problema es dividido en grupos discretos de instrucciones donde los grupos eran
ejecutados secuencialmente uno después de otro, todo era ejecutado sobre un solo procesador. Solamente
después de que una instrucción acababa la siguiente podı́a empezar.

Un ejemplo de la vida real serı́a un banco que tiene una fila y solamente un cajero, hasta que uno termina
lo que quiere hacer en el cajero otro no puede usarlo. El problema se complica cuando en vez de tener una
fila, se tienen varias pero se sigue teniendo un solo cajero, haciendo todo más lento.

Aplicando ese ejemplo a la computación se llegó a la conclusión que al ejecutar una sola instrucción se
estaba desperdiciando una buena cantidad de recursos de hardware porque la tecnologı́a seguı́a mejorando
pero la programación serial la frenaba, para muchos problemas se llegaba a un tope causado por la forma
de programar. A medida que los problemas se hacı́an más pesados y voluminosos, también lo hacı́a la
cantidad de tiempo de ejecución de estos.

Regresando al ejemplo, ¿Cómo se puede mejorar la velocidad en que las dos filas tratan de llegar al cajero?
Fácil, abriendo otro cajero completamente independiente que permita que existan dos filas con dos cajeros
trabajando al mismo tiempo. Esto, viéndolo desde una perspectiva de software se llama programación
paralela.

La programación paralela puede ser confundida con la programación concurrente, esta última parte de
la idea de que se pueden tener múltiples procesos corriendo en un solo procesador, estos procesos a su vez
tienen hilos que permiten la división máxima del programa a ejecutar.

Un hilo es una secuencia de instrucciones atómica, o en otras palabras, indivisibles, es lo mı́nimo que
precisa un proceso para desarrollarse, si estos hilos se trataran de dividir aún más el proceso a realizar
perderı́a sentido.
 Entonces, un programa concurrente es aquel formado por varios procesos que se ejecutan en un solo
procesador siguiendo una técnica conocida como paralelismo temporal, que no tiene que ver con la progra-
mación paralela en realidad ¿Entonces por qué se le llama ası́? Para el ojo humano es muy probable que no
se pueda distinguir un programa concurrente de uno paralelo, la diferencia principal entre estos dos radica
en que el programa concurrente va dando permisos a los distintos procesos para ocupar el procesador por
periodos cortos de tiempo, dando la idea de que se ejecutan al mismo tiempo cuando no es realmente ası́.
En cambio, la programación paralela necesita de varios procesadores y de procesos independientes para
llevarse a cabo.
 Antecedentes
La programación paralela sigue un esquema de paralelismo espacial, no temporal como en la programación
concurrente, y esto se puede entender como la existencia de varios procesadores fı́sicos que trabajan de
forma simultánea y están conectados mediante una red.

Una variable de este tipo de programación es la programación distribuida, que sigue la misma técnica
que la paralela con la diferencia de que la red que une a los procesadores se extiende a distintos puntos
geográficos.

En la programación paralela se tienen varios procesos ejecutándose sobre distintos procesadores, lo que
trae una serie de ventajas y desventajas.

Ventajas

Eficiencia en el procesamiento.

Aumento de velocidad de ejecución.

Posibilidad de realizar programas más complejos.

Hacer más con menos código.

Desventajas

Muchas veces la implementación paralela de algún algoritmo puede resultar innecesariamente com-
plicada y a veces no solamente no se ven cambios, si no que directamente la versión paralela es peor
que lo que se hacı́a de forma serial.

Muchas veces los procesos no son correctamente divididos por lo que no se aprovechan todos los
procesadores (núcleos).

Dificultad en generar la comunicación y sincronización de los procesos.

Limitaciones de hardware o software.

La relación costo-beneficio no siempre es positiva.

Y lo más importante, no todo es paralelizable porque no todo puede trabajar de forma independiente.

Para el correcto funcionamiento del paralelismo es necesario que los procesadores/núcleos compartan
recursos e información, por lo que debe existir alguna forma de comunicación. Estos procesadores pueden
estar fuerte o débilmente acoplados, o sea, pueden estar mejor o peor coordinados, pueden ser más o menos
independientes y pueden comunicarse más o menos información.

Para los sistemas de multiprocesadores debe existir alguna forma de distribución de la memoria, existen
dos, la memoria compartida y la memoria distribuida.
 En la memoria compartida los procesadores tienen una pequeña memoria caché para funcionar pero
para ejecutar un programa comparten la memoria entre sı́, o sea, las direcciones de memoria son únicas e
idénticas sin importar que procesador se tenga como perspectiva.

En la memoria distribuida cada procesador tiene su propia memoria con sus propias direcciones de
memoria pero estos se conectan mediante una red con el resto de los procesadores. Esta red se basa en
alguna topologı́a, algunas más eficientes que otras. Además de eso, los procesadores son capaces de reconocer
la diferencia entre su memoria privada y la de algún otro procesador.

Este tipo de memorias tienen sus propias formas de comunicarse, en el caso de la memoria compartida
existen herramientas tales como semáforos, regiones crı́ticas y monitores. Mientras que del lado de la
memoria distribuida existen los canales y las llamadas a procedimientos remotos.

Otros dos conceptos importantes son la granularidad y el balance de carga. La granularidad ayuda a
entender que tan independientes son los procesadores entre sı́, en otras palabras, que tan capaces son
de realizar un trabajo sin necesidad de hacer algún llamado a otro procesador, entender la granularidad
es importante para encontrar la forma más eficiente de dividir un problema y generar que el tiempo
de ejecución de cada conjunto de instrucciones sea el mı́nimo. Una granularidad gruesa implica mucha
independencia y una granularidad fina hace referencia a procesos o procesadores menos independientes,
dando la sensación de una ejecución serial y no paralela. El balance de carga es la manera de repartir
las tareas entre el número de procesadores que se tienen disponibles, este balance puede ser estático
(previamente asignado) o dinámico (asignado durante ejecución).

Tipos de paralelismo

Paralelismo algorı́tmico
Este paralelismo parte de la idea de la existencia de tareas independientes que ejecutan diferentes
secciones de un algoritmo, ignorando el orden preestablecido de las instrucciones.

Paralelismo geométrico
En este caso el paralelismo se aplica para tareas independientes y exactamente iguales, esto no implica
que sea sobre los mismos datos, en otras palabras lo que se desea realizar en cada tarea es lo mismo
pero los datos de entrada y los de salida pueden ser diferentes.

Paralelismo Farm o paralelismo Manager-Workers

El paralelismo Farm es aquel en el que un procesador es el ”manager se dedica a dividir las tareas
2

entre los demás ”workers”, una vez que estos workers terminan su tarea envı́an los resultados al
manager para que se les asigne una nueva tarea.

Paralelismo a nivel de instrucción

Consiste en cambiar el orden de las instrucciones de un programa para posteriormente juntarlas en
grupos pequeños que se ejecutarán de forma paralela sin alterar la salida final del programa. Las
tareas que son independientes se ejecutan distintos núcleos pero si no lo son pertenecen a 3 tipos
distintos de dependencias.

• Dependencia de flujo: Una tarea requiere sı́ o sı́ de datos de otra tarea para avanzar.
• Anti-dependencia: La tarea 1 requiere de algo de la tarea 2.
• Dependencia de salida: Cuando dos tareas usan la misma información a modificar.
 Paralelismo a nivel de bit
Se refiere al aumento del tamaño de la cadena de bits con la que el procesador puede trabajar, este
aumento reduce el número de instrucciones que tiene que ejecutar el procesador en variables cuyos
tamaños sean mayores a la longitud de la cadena.

Paralelismo a nivel de ciclo

Si en un ciclo no existe dependencia entre cada iteración estas se pueden realizar de forma paralela
y no se altera el resultado final.

Paralelismo funcional
El paralelismo funcional trata de resolver las dependencias entre conjuntos de instrucciones para
poder hacer más eficiente el trabajo sobre las tareas independientes, porque si se resuelven esas
dependencias puede dar a lugar a tener más tareas independientes haciendo que el paralelismo tenga
una granularidad más gruesa.

Métricas de desempeño

Las métricas de desempeño sirven, como lo dice su nombre, para medir el desempeño de una solución
paralela a algún problema comparándola con su versión secuencial para ayudar a determinar si vale la pena
o no paralelizar, algunos ejemplos de estas métricas son:

Tiempos de procesamiento y de comunicación

Medición del tiempo que tardan una aplicacion paralela en comparación con su versión serial, puede
verse como la suma del tiempo de procesamiento y el tiempo de comunicación entre procesadores.

Speedup
Es la relación entre el tiempo de ejecución de un programa que se ejecuta en un solo procesador sobre
el tiempo de ejecución en n procesadores, esta métrica solamente toma en cuenta aspectos temporales.

Eficiencia
La eficiencia asocia de forma matemática el tiempo que n procesadores realizan un trabajo en com-
paración con un solo procesador, se calcula como el recı́proco de n. Este valor refleja que tan bien se
aprovecha el hardware del sistema.

Fracción serial
Relaciona otras dos métricas de desempeño, el speedup y la fracción serial con el propósito de tomar
factores extras al tiempo, como lo es el hardware.
 Diseño de programas paralelos

El paralelismo requiere de la participación activa del programador puesto que es un proceso casi siempre
manual, para muchos es considerado un nivel más complejo de abstracción pues requiere que se piense no
solamente en la solución del problema, si no en como cada parte del problema se comunica y como trabajan
de forma dependiente o independiente. Existen compiladores o pre-procesadores que ayudan a este trabajo,
y pueden trabajar de manera automática o por instrucción del programador, en el caso del lenguaje C se
suele recurrir a la API OpenMP que sirve para mediante escritura de código, convertir bloques seriales a
paralelos, conociendo bien su funcionamiento y del programa en si mismo.

Modelo PCAM

Propuesto por Ian Foster, el modelo PCAM existe para ayudar en la realización de programas de natu-
raleza paralela, este modelo se puede resumir en cuatro aspectos:

Partición
El problema se debe partir de la mejor forma posible en tareas pequeñas, ignorando por el momento
cantidad de procesadores, organización de memoria, sincronización etc. El enfoque va en la división
y en encontrar oportunidades de código paralelizable. La división del problema se conoce como
descomposición, y esta puede ser de dominio o funcional.

Comunicación
Se busca la coordinación de las tareas y como se van a comunicar las distintas partes del programa,
identificando las dependencias. Los tipos de comunicación son: local/global, estructurada, estáti-
ca/dinámica y sı́ncrona/ası́ncrona.

Aglomeración
La aglomeración es el proceso inverso de la partición, es determinar como es que las tareas previamente
divididas se juntarán y cuales no, buscando mantener el sistema sin afectaciones.

Mapeo
Asignar los distintos bloques de tareas a los procesadores o hilos, como estos se distribuirán sobre el
sistema paralelo.
 Lenguajes de programación paralelos

Un lenguaje paralelo se caracteriza por tener implementado de alguna forma paralelismo, secuencialidad,
comunicación, sincronización y no determinismo.

El no determinismo hace referencia a que el orden en el que ocurren los eventos en el paralelismo es
completamente arbitrario.

En este caso, que se trabajó con lenguaje C, no es necesario explicar como funciona el paralelismo en
lenguajes con otros paradigmas como el orientado a objetos.
Descripción del algoritmo
 Paralelización del algoritmo
Tipo de paralelismo

Métricas de desempeño

Formas de comunicación

Granularidad
Implementación en C con OpenMP
 Pruebas de rendimiento
Versión secuencial

Pruebas para varias instancias

Gráficos
 Conclusiones
Cardoso Rodrı́guez Francisco Adrián:

Genis Cruz Lourdes Victoria:

Medina Segura Fernando:

Autoevaluación general del equipo
 Bibliografı́a

https://hpc.llnl.gov/training/tutorials/introduction-parallel-computing-tutorial

https://www.geeksforgeeks.org/introduction-to-parallel-computing/

https://ferestrepoca.github.io/paradigmas-de-programacion/paralela/paralela_teoria/index.
html