1. Introducción/Filosofía
  2. Historia
  3. Ventajas y desventajas
  4. Conceptos clave
  5. Concurrencia vs Paralelismo
  6. Arquitectura de Von Neumann
  7. Metodologías de diseño
  8. Taxonomía de Flynn
  9. Arquitectura
  10. Tipos de paralelismo
  11. Patrones de control paralelos
  12. Paralelizacion Manual vs Automatica
  13. Sincronización
  14. Balanceador de carga
  15. Medidas de rendimiento
  16. Lenguajes de programacion
  17. Aplicaciones
  18. OpenMP
  19. Presentación y taller
  20. Bibliografía

Introducción

La computación paralela es el uso de múltiples recursos computacionales para resolver un problema. Se distingue de la computación secuencial en que varias operaciones pueden ocurrir simultáneamente.

El paralelismo clásico, o puesto de otra manera, el clásico uso del paralelismo, es el de diseño de programas eficientes en el ámbito científico. La simulación de problemas científicos es un área de gran importancia, los cuales requieren de una gran capacidad de procesamiento y de espacio de memoria, debido a las complejas operaciones que se deben realizar.

Otro uso clásico es el de las gráficas generadas por computadora. La generación de fotogramas requiere de una gran cantidad de cálculos matemáticos. Esto supone una tarea muy compleja para un solo procesador, luego es necesario que haya algún tipo de paralelismo, para distribuir la tarea para que esta sea realizada eficiente y eficazmente.

Filosofía

¿Que es computación paralela?

    En el sentido más simple, la computación paralela es el uso simultáneo de múltiples recursos computacionales para resolver un problema computacional:

  • Un problema se divide en partes discretas que se pueden resolver simultáneamente
  • Cada parte se descompone en una serie de instrucciones
  • Las instrucciones de cada parte se ejecutan simultáneamente en diferentes procesadores
  • Se emplea un mecanismo global de control/coordinación

¿Por qué se hace programación paralela?

    El hecho de que la progamación paralela sea un paradigma da cuenta de que existe una razón por la cual no ha dejado de ser necesaria o no ha sido totalmente automatizable, igualmente hay otras razones interesantes detrás para entender la existencia, actualidad y contemporaneidad de la programación paralela:

  • Ley de Moore: Esta ley propuesta por Gordon E. Moore en 1965 dice resumidamente que el número de transistores en un chip determinado se doblaría cada dos años. Esto quiere decir un aumento del rendimiento en los procesadores del alrededor del 50%, esto se traduce en escalar la velocidad de reloj de los procesadores, pero esta ley no es fidenigna desde el 2002 dónde solo ha habido un 20%, lo cuál sigue siendo un aumento considerable, sin embargo, no sería suficiente para que todos los avances en computación que se han logrado hasta el día y las necesidades de procesamiento en crecimiento exponencial puedan satisfacerse totalmente. Veamos en la gráfica adjunta que el problema principal es que la ley no puede continuar indeterminadamente porque esto implica un crecimiento exponencial, el cuál es imposible de mantener por espacio pero principalmente por el punto de la temperatura mismo, se puede ver que si esto fuese cierto llegaría muy pronto el año en que un solo procesador alcanzara la temperatura de la superficie del sol.
  • Overclocking infinito: El overclokcing tiene un límite a pesar de que existiera una refrigeración perpetúa y adecuada del procesador. Esto es debido a las corrientes parásitas que impiden una velocidad teoricamente inifinita a la cual los circuitos pueden cambiar entre estados, o de hecho sus transistres..
  • Automatización del paralelismo: Se dice en este paradigma que el éxito es inversamente proporcional al número de cores precisamente porque existen complejidades en el corazón del paralelismo que implican cosas que todavía no se pueden predecir ni con inteligencia artificial, en este mismo artículo de heco se menciona cuales son las posibles estrategias para atacar un problema de forma paralela, esto da cuenta de que existe una forma prácticamente determinada de abordarlos pero no se automatizarlos, a pesar de que sí existan algunas partes que son automatizables en el proceso.
  • Solución en el hardware: Un diseño adecuado del hardware permitiría que la paralelización siempre estuviera presente con respecto a los procesadores que se están usando de tal modo que alguno los problemas que son inherentes al paradigma pudieran evitarse. Esto ha resultado imposible hasta la fecha, de hecho, solo diseñar solamente algo tan efectivo y tradicional como se ha hecho en programación secuencial es algo que no existe hasta ahora. Existen algunas aproximaciones como OpenMP de las que hablaremos más adelante

Historia

  • En 1958 Luigi Federico Menabrea habló sobre programación paralela y la necesidad de “branching” y “waiting”.
  • También en 1958 Investigadores de IBM discutieron el uso de paralelismo en cálculos numéricos por primera vez.
  • El interés por la computación paralela se remonta a finales de los años 50. Este interés se vio expresado en forma de supercomputadores, que aparecieron en los años 60 y 70. Estos computadores tenían procesadores de memoria compartida, con múltiples procesadores trabajando lado a lado con datos compartidos.
  • En 1962 Burroughs Corporation creó un computador de 4 procesadores que accedía a 16 módulos de memoria.
  • Luego en 1964 La fuerza aérea estadounidense financió el diseño del primer computador paralelo masivo ILLIAC IV. (256 procesadores)
  • Amdahl y Slotnick debatieron sobre la viabilidad del procesamiento en paralelo en 1967. De estos debates surgió la ley de Amdahl
  • Primera aplicación corriendo en ILLIAC IV(1976). Por esta razón este computador fue llamado “the most infamous of the supercomputers”, ya que solo fue completado en un 25%, tomó 11 años y 4 veces más al costo estimado.
  • A mediados de los 80, un nuevo tipo de computador paralelo fue creado cuando el proyecto “Concurrent Computation” de Caltech construyó un supercomputador para aplicaciones científicas. El sistema mostró que se podría lograr un rendimiento extremo usando microprocesadores regulares, disponibles en el mercado.
  • Empezando a los finales de los 80, los clusters surgieron para competir y con los MPP. Un cluster es un tipo de computador paralelo, construido usando múltiples computadores “off-the-shelf”, conectados usando una red “off-the-shelf”. Hoy en día, los clusters son la arquitectura dominante en los datacenters.
  • Para los MPP y clusters surgió el estándar MPI a mediados de los 90, que convergió de otras API. Para los multiprocesadores con memoria compartida, un proceso de convergencia similar se observó a finales de los 90, con el surgimiento de pthreads y OpenMP.
  • En la actualidad, la computación paralela se ha vuelto mainstream prácticamente, con la llegada de los procesadores de varios núcleos casi por defecto en la mayoría de dispositivos computacionales.
  • El software ha sido una parte activa en la evolución de la programación paralela. Los programas paralelos son más difíciles de escribir que los programas secuenciales, ya que se requiere que haya una comunicación y sincronización entre las tareas que se han paralelizado.

Ventajas

  • Resuelve problemas que no se podrían realizar en una sola CPU
  • Resuelve problemas que no se pueden resolver en un tiempo razonable
  • Permite ejecutar problemas de un orden y complejidad mayor
  • Permite ejecutar código de manera más rápida (aceleración)
  • Permite ejecutar en general más problemas
  • Obtención de resultados en menos tiempo
  • Permite la ejecución de varias instrucciones en simultáneo
  • Permite dividir una tarea en partes independientes

Desventajas

  • Mayor consumo de energía
  • Mayor dificultad a la hora de escribir programas
  • Dificultad para lograr una buena sincronización y comunicación entre las tareas
  • Retardos ocasionados por comunicación ente tareas
  • Número de componentes usados es directamente proporcional a los fallos potenciales
  • Condiciones de carrera
    • Múltiples procesos se encuentran en condición de carrera si el resultado de los mismos depende del orden de su llegada
    • Si los procesos que están en condición de carrera no son correctamente sincronizados, puede producirse una corrupción de datos

Conceptos Clave

Conceptos acerca de Tareas

Tarea:

Un problema complejo se subdivide en una cantidad discreta de tareas que representan trabajo computacional. Una tarea esta compuesta de un conjunto de instrucciones que seran ejecutadas por un procesador.


Granularidad:

Se refiere al tamaño de cada tarea y a la independiencia de las demás tareas, se dividen en dos categorías.
  • Gruesa: Cantidad relativamente grande de trabajo, alta independencia entre tareas y poca necesidad de sincronización.
  • Fina: Cantidades pequeñas de trabajo, poca independencia entre tareas, y una alta demanda de sincronización.


Scheduling:

Scheduling es el proceso en el que las tareas son asignadas a los procesos o hilos, y se les da un orden de ejecución. Este puede ser especificado en el código, en tiempo de compilación o dinámicamente en tiempo de ejecución. El proceso de scheduling debe tener en cuenta la dependencia entre tareas, ya que, aunque muchas pueden ser independientes, otras pueden requerir los datos producidos por otras tareas.


Conceptos acerca de Hilos

Hilo:

Un proceso pesado padre puede convertirse en varios procesos livianos hijos, ejecutados de manera concurrente. Cada uno de estos procesos livianos se conoce como hilo. Estos se comunican entre ellos a través de la memoria global.


Sincronizacion:

Los programas en paralelo necesitan la coordinación de procesos e hilos, para que haya una ejecución correcta. Los métodos de coordinación y sincronización en la programación paralela están fuertemente asociados a la manera en que los procesos o hilos intercambian información, y esto depende de cómo está organizada la memoria en el hardware.


Mapping:

Mapping en el proceso de asignación de procesos e hilos a unidades de procesamiento, procesadores o núcleos. Usualmente el mapping se hace por el sistema en tiempo de ejecución, aunque en ocasiones puede ser influenciado por el programador.

Otros conceptos

Balanceo de carga

Se refiere a la práctica de distribuir cantidades equitativas de trabajo entre las tareas, de modo que todas las tareas se mantengan ocupadas todo el tiempo.


Speedup:

Es un proceso para aumentar el rendimiento entre dos sistemas procesando el mismo problema. Es la mejora en la velocidad de ejecución de una tarea ejecutada en dos arquitecturas similares con diferentes recursos.

Overhead

Es la cantidad de tiempo requerido para coordinar tareas paralelas, en lugar de hacer un trabajo útil. Incluye factores como:
  • Tiempo de inicio de la tarea
  • Sincronización
  • Comunicaciones de datos
  • Sobrecarga de software impuesta por lenguajes paralelos, bibliotecas, sistema operativo, etc.
  • Tiempo de terminación de la tarea


Sección crítica

Un proceso tiene un segmento de código llamado sección crítica cuando este puede modificar o leer información de memoria compartida con otros procesos. Dos procesos no pueden ejecutar su seccion critica al mismo tiempo.

Concurrencia vs Paralelismo

Concurrencia

Capacidad de operar actividades al mismo tiempo. Es decir se pueden tener varios procesos corriendo cada uno en un procesador o puede haber varios proceso que corran solo en un procesador

Paralelismo

Son muchas actividades teniendo lugar al mismo tiempo, “la cualidad o el estado de ser paralelo”. El hecho de ser paralelo implica que solo se pueden tener varios procesos corriendo cada uno en un procesador.

Arquitectura de Von Neumann

Se caracterizaba por guardar las instrucciones de los procesos y los datos en una memoria electronica, a diferencia de como se modelaban los computadores de la epoca a través de una conexion de cables

Componentes principales

  • Memoria
  • Unidad de control
  • Unidad Aritmetica Logica
  • Entradas/Salidas

Memoria de acceso aleatorio

En la memoria de acceso aleatorio se almacenaban los datos y los programas que estaban siendo ejecutados

  • Las instrucciones del programa son datos codificados que le dicen al computador que es lo que tiene que hacer
  • Los datos son simplemente informacion que sera usada por el programa

Metodologias de diseño

Cuando se diseña un algoritmo paralelo es necesario tener en cuenta:

  1. Los tiempos de las comunicaciones.
  2. Maximizar el procesamiento en cada nodo o unidad de procesamiento.
  3. Los costes de implementar el algoritmo.
  4. Tiempos de planificación (scheduler).

Metodologia foster

Consiste en cuatro etapas
  1. Particionamiento: En el dominio de los datos o de funciones.
  2. Comunicaciones: Se hace por medio de distintos medios o paradigmas tales como la memoria o paso de mensajes
  3. Aglomeración: Las tareas o datos son agrupados teniendo en cuenta posibles dependencias
  4. Mapeo: Los grupos son asignados a una unidad de procesamiento
En la siguiente imagen se puede ver descrito el proceso de forma gráfica:

Taxonomia de Flynn

Single Instruction, Single Data (SISD)

hay un elemento de procesamiento, que tiene acceso a un único programa y a un almacenamiento de datos. En cada paso, el elemento de procesamiento carga una instrucción y la información correspondiente y ejecuta esta instrucción. El resultado es guardado de vuelta en el almacenamiento de datos. Luego SISD es el computador secuencial convencional, de acuerdo al modelo de von Neumann.

Multiple Instruction, Single Data (MISD)

hay múltiples elementos de procesamiento, en el que cada cual tiene memoria privada del programa, pero se tiene acceso común a una memoria global de información. En cada paso, cada elemento de procesamiento de obtiene la misma información de la memoria y carga una instrucción de la memoria privada del programa. Luego, las instrucciones posiblemente diferentes de cada unidad, son ejecutadas en paralelo, usando la información (idéntica) recibida anteriormente. Este modelo es muy restrictivo y no se ha usado en ningún computador de tipo comercial.

Single Instruction, Multiple Data (SIMD):

Hay múltiples elementos de procesamiento, en el que cada cual tiene acceso privado a la memoria de información (compartida o distribuida). Sin embargo, hay una sola memoria de programa, desde la cual una unidad de procesamiento especial obtiene y despacha instrucciones. En cada paso, cada unidad de procesamiento obtiene la misma instrucción y carga desde su memoria privada un elemento de información y ejecuta esta instrucción en dicho elemento. Entonces, la instrucción es síncronamente aplicada en paralelo por todos los elementos de proceso a diferentes elementos de información. Para aplicaciones con un grado significante de paralelismo de información, este acercamiento puede ser muy eficiente. Ejemplos pueden ser aplicaciones multimedia y algoritmos de gráficos de computadora.

Multiple Instruction, Multiple Data (MIMD):

hay múltiples unidades de procesamiento, en la cual cada una tiene tanto instrucciones como información separada. Cada elemento ejecuta una instrucción distinta en un elemento de información distinto. Los elementos de proceso trabajan asíncronamente. Los clusters son ejemplo son ejemplos del modelo MIMD.

Tipos de paralelismo

Paralelismo a nivel de bit:

Se habla de paralelismo al nivel de bit, cuando se aumenta el tamaño de la palabra del procesador (tamaño de la cadena de bits a procesar). 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.
Ejemplo: En un procesador de 8-bits sumar dos números de 16bits tomaría dos instrucciones. En un procesador de 16-bits esa operación requiere solo una instrucción.

Nota: este método está “estancado” desde el establecimiento de las arquitecturas de 32 y 64 bits.

Paralelismo a nivel de instrucción

Este tipo de paralelismo consiste en cambiar el orden de las intrucciones de un programa y juntarlas en grupos para posteriormente ser ejecutados en paralelo sin alterar el resultado final del programa.

Pipelining

El pipelining proviene de la idea de que en una tubería no es necesario esperar a que todo el agua dentro salga, para que pueda entrar más. Los procesadores modernos tienen un 'pipeline' que separa las instrucciones en varias etapas, donde cada etapa corresponde a una acción diferente que necesita la salida de la anterior.

Ejemplo: Un pipeline de 5 etapas: fetch (buscar la instrucción), decode (decodificarla), execute (ejecutarla), write (escribir en memoria el resultado de la operación).

En el gráfico anterior se observa el procesamiento de dos instrucciones sin pipeline, tomando un tiempo de 8 ciclos, y con pipeline reduciendo este tiempo a solo 5 ciclos.


Paralelismo a nivel de datos

Cada procesador realiza la misma tarea sobre un subconjunto independiente de datos.
Ej: Dos granjeros se dividen el área de césped a podar.

El caso clásico de paralelismo de datos, es el cálculo de pi por partes usando el método de monte carlo:

Ejemplo hecho en python

Paralelismo a nivel de tareas

Cada hilo realiza una tarea distinta e independiente de las demás.
Ej: Un granjero poda el césped, el otro cosecha.

Patrones de diseño paralelo

Los patrones se han establecido como buenas practicas a la hora de realizar ingeniería de software.

Los patrones de control en el caso de la programación paralela son maneras de combinar la distribución de los procesos y el acceso a los datos para la solucion de un problema.

Fork-Join

En este patrón de diseño se generan dos ejecuciones concurrentes, que empieza inmediatamente después de que el fork es llamado en código, después, se usa join para combinar estas dos ejecuciones concurrentes en una. Cada join puede unirse entonces a su fork correspondiente y lo hace antes de las otras terminen.

Map

Map es un patrón que replica una función sobre todos los elementos de un conjunto de entrada. La función que está siendo replicada se llama función elemental, dada que la misma se aplica a una coleccion real de datos.

Stencil

Stencil es un generalización del patron de Map, en el cual una función elemental tiene acceso no solo a un elemento del conjunto de entrada sino también a un conjunto de "vecinos"

Como la estructura de datos no es infinita se deben tener en cuenta el manejo de excepciones para los bordes de la misma.

Reducción

Una reducción combina cada elemento de una colección en uno solo utilizado una función asociativa conocida como función combinatoria. Como es asociativa las tareas se pueden distribuir de muchas maneras y si la función resultara ser también conmutativa el número de posibilidides aumentaría aún más.

Scan

Scan realiza las reducciones de cada elemento perteneciente a una estructura. En otras palabras cada elemento de salida es la reduccion de un elemento de entrada. A traves de una función sucesora se avanza de un estado al otro haciendo folds en el proceso asociativo.

ParBegin - ParEnd

Parbegin y Parend originalmente propuesto por Dijsktra es un patrón para lenguajes estructurados en bloque como Pascal y permiten una especificación explicita del paralelismo, todo lo que esté contenido entre ambos será ejecutado en hilos separados en tanto se necesite y se genera un grafo de precedencia como el que se ve en la imagen, donde se muestra simplemente el orden de las instrucciones a ejecutar.

Maestro / Esclavo

Es usada cuando se tienen dos o más procesos que necesitan ejecutarse simultanea y continuamente pero a diferentes velocidades. Si estos procesos corren en un único ciclo, pueden suceder problemas de temporización graves. Estos problemas de temporización ocurren cuando una parte del ciclo tarda más en ejecutarse de lo esperado. Si esto sucede, la sección restante del ciclo se atrasa. El patrón Maestro/Esclavo consiste en múltiples ciclos en paralelo. Un ciclo actúa como el maestro y los otros como esclavos. El ciclo maestro controla a todos los demás.

SPMD - SIMD

Esto viene de la taxonomia Flynn SPMD (Single Program, Multiple Data), múltiples procesadores autónomos ejecutan simultáneamente el mismo programa en puntos independientes, SIMD (Single instructon, multiple data) está basado en organizar los datos relevantes al problema en estructuras de datos iterativas como arreglos y en definir la computación en términos de una secuencia de actualizaciones paralelas en paralelo con estas estructuras de datos.

Creación de hilos y procesos

Los hilos se distinguen de los tradicionales procesos en que los procesos son generalmente independientes, llevan bastante información de estados, e interactúan sólo a través de mecanismos de comunicación dados por el sistema. Por otra parte, muchos hilos generalmente comparten otros recursos directamente. En muchos de los sistemas operativos que proveen facilidades para los hilos, es más rápido cambiar de un hilo a otro dentro del mismo proceso, que cambiar de un proceso a otro.

Arquitecturas de memoria de computación paralela

Memoria compartida

  • Los procesos comparten un espacio de memoria común
  • Escriben y leen de manera asíncrona
  • No es necesario especificar cómo se comunican los datos entre las tareas
  • Se usan semáforos o locks para controlar el acceso a la memoria compartida
Uniform Memory Access (UMA):
  • Lo más comúnmente representado hoy por las máquinas Symmetric Multiprocessor (SMP)
  • Procesadores idénticos
  • Igual acceso y tiempos de acceso a la memoria
  • Si un procesador actualiza una ubicación en memoria compartida, todos los demás procesadores saben sobre la actualización, esto es llamado coherencia del caché
Non-Uniform Memory Access (NUMA)
  • Hecho mediante la vinculación física de dos o más SMP
  • Un SMP puede acceder directamente a la memoria de otro SMP
  • No todos los procesadores tienen igual tiempo de acceso a toda la memoria
  • El acceso a la memoria es más lento
  • Si se mantiene la coherencia del caché

Memoria distribuida

Esta arquitectura se basa en múltiples procesadores con su propia memoria física privada, las tareas pueden operar solo con información local y se necesita de la comunicación para obtener información remota, a través también de procesadores remotos Hay cuatro implementaciones que pueden servir como ejemplo conocidas para esta arquitectura tales como: múltiples sistemas operativos, Middlewares, clusters y grids. Las razones por las que se prefiere esta arquitectura en ciertos escenarios es porque en principio se pueden añadir tantas unidades de procesamiento como la red pueda soportar, pero las limitaciones recaen directamente en ella.

  • También llamado modelo de paso de mensajes
  • requieren una red de comunicación para conectar la memoria entre procesadores
  • Las tareas intercambian datos por medio del paso y recepción de mensajes
  • Los procesadores tienen su propia memoria local. Las direcciones de memoria en un procesador no se asignan a otro procesador, por lo que no hay concepto de espacio de direcciones global en todos los procesadores.
  • Debido a que cada procesador tiene su propia memoria local, funciona independientemente. Los cambios que hace en su memoria local no tienen ningún efecto en la memoria de otros procesadores. Por lo tanto, el concepto de coherencia de caché no se aplica.
  • Cuando un procesador necesita acceso a los datos de otro procesador, suele ser la tarea del programador definir explícitamente cómo y cuándo se comunican los datos. La sincronización entre tareas también es responsabilidad del programador.

Ejemplos de memoria distribuida

  • Clusters: Colección de computadores que se encuentran interconectados mediante redes de alta velocidad (Ethernet, SCI, Myrinet, Infiniband) Existe una categorización hecha por la organización TOP500 que lleva cuenta de los clusteres más poderosos de la tierra con capacidad de procesamiento del órden de gigaflops. Estos generalmente están basados en una arquitectura MIMD.
  • Grids: Computadores de múltiples dominios administrativos conectados para solucionar una tarea determinada.

Hibrido memoria distribuida-comopartida

  • Es la combinación entre memoria compartida y memoria distribuida, con sus ventajas en común.
  • Su principal ventaja es su escalabilidad.
  • Su principal desventaja es que la complejidad de programación aumenta.

Hilos

  • Un proceso pesado puede convertirse en varios procesos livianos ejecutados de manera concurrente.
  • Se pueden describir como una subrutina dentro del programa principal.
  • Se comunican entre ellos a través de la memoria global.

Datos en paralelo

  • También conocido como PGAS (Partitioned Global Address Space)
  • Una serie de tareas trabajan de manera colectiva en la misma estructura de datos
  • Las tareas realizan la misma operación, pero cada una en su partición pero cada tarea trabaja en una partición diferente de ésta

Sincronización

  • Administrar la secuencia de trabajo y las tareas que lo realizan es una consideración crítica del diseño para la mayoría de los programas paralelos.
  • Puede ser un factor significativo en el desempeño del programa, pues un diseño de sincronización adecuado reduce el tiempo overhead.
  • A menudo requiere "serialización" de segmentos del programa.

Sincronización Mínima:

  1. Identificar suficiente concurrencia en la descomposición del problema.
  2. Decidir cómo manejarla: distribución estática o dinámica.
  3. Determinar el grado de granularidad y cómo explotar la concurrencia.
  4. Reducir serialización y costes de sincronización.

1. Identificar suficiente concurrencia

Paralelismo por Tareas:
  • Grandes tareas (procedimientos) pueden realizarse en paralelo
  • No suele haber muchas tareas, no aumenta con el tamaño del problema
  • Dificultad para aplicar balanceo de carga
Paralelismo por Datos:
  • Más escalable, proporcional al tamaño del problema
  • Es factible aplicar balanceo de carga

2. Manejando concurrencia

Técnicas estáticas:
  • Asignación basada en la entrada
  • Bajo overhead
  • Siempre que sea posible, es preferible
Técnicas dinámicas:
  • Adapta el balanceo en tiempo de ejecución
  • Aumenta la comunicación y el overhead

3. Determinación de la granularidad

Grano grueso: pocas oportunidades de balanceo de carga. Grano fino: mayor overhead, mayor comunicación, más sincronización.

4. Reducir la serialización

Sincronización de eventos:
  • Global versus punto a punto
  • Sincronización a bajo nivel produce mayor cantidad de sincronizaciones
Exclusión mutua:
  • Regiones críticas pequeñas
  • Dispersar las regiones críticas en el tiempo

Tipos de sincronización:

Barrier

  • Todas las tareas están involucradas
  • Cada tarea realiza su trabajo hasta que alcanza la barrera. Después, se detiene o "bloquea".
  • Cuando la última tarea llega a la barrera, todas las tareas se sincronizan.
Lo que sucede a partir de aquí varía. Algunas veces, una sección del código debe ser ejecutada en serie. En otros casos, las tareas se liberan automáticamente para continuar su trabajo.

Lock / semaphore

  • Puede involucrar cualquier número de tareas
  • Se utiliza para serializar el acceso a datos globales o a una sección de código. Sólo una tarea a la vez se puede ejecutar.
  • La primera tarea en llegar al lock "lo bloquea". Esta tarea puede acceder de forma segura (en serie) a los datos protegidos o al código.
  • Otras tareas pueden intentar adquirir el lock pero deben esperar hasta que la tarea que posee el bloqueo lo libere.

Operaciones de comunicación sincrónica

  • Incluye sólo aquellas tareas que ejecutan una operación de comunicación
  • Cuando una tarea realiza una operación de comunicación, se requiere alguna forma de coordinación con las otras tareas que participan en la comunicación.
  • Antes de que una tarea pueda realizar una operación de envío, primero debe recibir un aviso del receptor sobre si está disponible para enviar.

Se utilizan las funciones send y recieve para coordinar las acciones.

Un ejemplo que ilustra esta técnica es el handshake que establece la comunicación usando el protocolo http.

Balanceador de carga

Se refiere a la práctica de distribuir cantidades aproximadamente iguales de trabajo entre las tareas, de modo que todas las tareas se mantengan ocupadas todo el tiempo. Se puede considerar una minimización del tiempo de inactividad de la tarea.

  • Asignar el trabajo que recibe cada tarea equitativamente
  • Puede ser un factor significativo en el desempeño del programa
  • A menudo requiere "serialización" de segmentos del programa.

Asignación de trabajo dinámico

Ciertas clases de problemas producen desequilibrios de carga incluso si los datos están distribuidos uniformemente entre las tareas

  • Cuando la cantidad de trabajo que realiza cada tarea es variable o no se puede predecir, puede ser útil usar un planificador - task pool approach. Cuando cada tarea termina su trabajo, espera en una cola para obtener una nueva pieza de trabajo.
  • Puede ser necesario diseñar un algoritmo que detecte y maneje desequilibrios de carga como ocurren dinámicamente dentro del código.

Paralelismo automatico vs manual

Paralelismo automatico

  • El compilador analiza el codigo fuente e identifica oportunidades de paralelismo
  • Los ciclos son los objetivos mas frecuentes para una paralelizacion automatica
  • El analisis incluye identificar inhibidores al paralelismo y posiblemente un costo en, si el paralelismo puede o no mejorar el rendimiento
  • un ejemplo de este tipo puede ser OpenMP

Paralelismo manual

  • Usando las directivas del compilador el programador explicitamente le dice al compilador como quiere paralelizar el codigo
  • Se puede usar o complementar en algun grado con paralelizacion automatica

Medidas de rendimiento

Tiempo de respuesta

Es el tiempo que tarda en ejecucion el programa A.

MIPS - MFLOPS

MIPS - Millones de operaciones por segundo. MFLOPS - Millones de operaciones de punto flotante por segundo.

Eficiencia

La eficiencia del programa se mide en el costo de ejecucion.

SpeedUp

El SpeedUp resresenta la ganacia que se obtiene en la version paralela del programa respecto a la version secuencial del mimo.

Ley de Amdahl

El incremento de velocidad de un programa utilizando múltiples procesadores en computación paralela está limitada por la fracción secuencial del programa. Sea f el porcentaje paralelizado del programa expresado en decimal, la ley de Amdahl dice que llega un punto en el cual sin importar que el numero de procesadores sea muy alto , el speedup se va a comportar de manera lineal ; esto de acuerdo al porcentaje que este paralelizado el codigo. El speedup de un programa con un fragmento paralelizado se calcula con :

Lenguajes de programacion

Aplicaciones

Computación grafica

Ciertas clases de problemas producen desequilibrios de carga incluso si los datos están distribuidos uniformemente entre las tareas

Aproximación y cálculo de constantes y/o funciones numéricas.

Worldwide LHC Computing Grid (WLCG) es una colaboración global de centros de computación. Fue lanzado en 2002 para proporcionar un recurso para almacenar, distribuir y analizar los 15 petabytes (15 millones de gigabytes) de datos generados cada año por el Large Hadron Collider (LHC).

Predicción del clima y cambio climático

Uno de los primeros usos exitosos de la computación paralela fue la predicción del tiempo. La información, como la temperatura, la humedad y las precipitaciones, se ha recolectado y utilizado para predecir el clima durante más de 500 años. En 1904, el físico y meteorólogo noruego Vilhelm Bjerknes propuso un modelo de ecuaciones diferenciales para la predicción meteorológica que incluía siete variables, incluyendo temperatura, lluvia y humedad.

Análisis de imágenes multiespectro

Las imágenes satelitales consisten en grandes cantidades de datos. Por ejemplo, las imágenes Landsat 7 consta de siete tablas de datos, donde cada entrada en una tabla representa una longitud de onda magnética diferente (azul, verde, rojo o infrarrojo térmico) para un píxel de 30 metros cuadrados de la superficie de la Tierra.

Astronomía

Hay muchas aplicaciones de los supercomputadores a la astronomía, incluyendo el uso de un supercomputador para simular eventos en el futuro, o pasado, para probar teorías astronómicas. La Universidad de Minnesota Supercomputer Center simuló lo que una explosión de supernova que se origina en el borde de una gigantesca nube de gas molecular interestelar parecería 650 años después de la explosión.

Renderizado de imagenes y animación

Diagnóstico de enfermedades mentales

El proyecto RePhrase incluido en el programa Horizonte 2020 de la UE tuvo como objetivo trabajar en la mejora del desarrollo de software para arquitecturas paralelas y heterogéneas. Los resultados de esta investigación encontraron aplicación en diversos campos, como en la mejora de procesos industriales de fabricación, la monitorización del tráfico ferroviario y la optimización de aplicaciones para el diagnóstico de enfermedades mentales. Este último consistía en el procesamiento por computador de imágenes capturadas mediante resonancia magnética del cerebro, con el objetivo de conseguir diagnósticos más rápidos en el caso de enfermedades como la la esquizofrenia, el trastorno bipolar o la depresión.

OpenMP

Es una interfaz de programa de aplicación (API) que se puede utilizar para dirigir explícitamente paralelismo de memoria compartida multi-procesos. Está compuesto por:

  • Directivas de compilación
  • Runtime Library Routines
  • Variables de entorno

Estructura general de OpenMP en C++

						
#include <omp.h>
int main () {
int var1, var2, var3;
//Código en serie...

//Comienzo de la región paralela hace fork del conjunto de threads
#pragma omp parallel private(var1, var2) shared(var3)
{
	//Región paralela ejecutada por todos los threads
	//otras directivas OpenMP
	//Todos los threads se juntan en el thread master
}
//Continuación del código...
}
						
					

Ejemplo región paralela

						
#include <omp.h>
#include <stdio.h>
int main(int argc, char *argv[])
{
	/* Cada thread tiene una variable id privada (tid) */
	int nthreads, tid;

	#pragma omp parallel private(tid)
	{
	/* Se asigna y se imprime el id de cada thread  */
	tid = omp_get_thread_num();
	printf("Hello World desde el thread = %d\n", tid);
	/* Solo el thread master ejecuta lo siguiente */
	if (tid == 0)
	{
		nthreads = omp_get_num_threads();
		printf("El numero de threads es = %d\n", nthreads);
	}
	}
}
						
					
  • Un programa "Hello World" simple
  • Cada hilo ejecuta todo el código encerrado en la región paralela
  • Las rutinas de la biblioteca OpenMP se utilizan para obtener identificadores de subprocesos y número total de subprocesos
  • Output:
    World desde el thread = 2
    Hello World desde el thread = 1
    Hello World desde el thread = 4
    ...
    El numero de threads es = x

Parallel For

						
#include <omp.h>
#include <stdio.h>

#define N       1000
#define CHUNKSIZE   100

int main(int argc, char *argv[])
{

	int i, chunk;
	float a[N], b[N], c[N];

	for (i=0; i < N; i++)
	a[i] = b[i] = i * 1.0;
	chunk = CHUNKSIZE;

	#pragma omp parallel for \
	shared(a,b,c,chunk) private(i) \
	schedule(static,chunk)

	for (i=0; i < N; i++)
	c[i] = a[i] + b[i];
}
						
					
    Programa simple de adición de vectores
  • Las matrices A, B, C y la variable N serán compartidas por todos los subprocesos.
  • Variable i será privada para cada hilo; Cada hilo tendrá su propia copia única.
  • Las iteraciones del bucle "For" se distribuirán dinámicamente en trozos de tamaño "CHUNK".
  • Los hilos no se sincronizarán al completar sus trabajos individuales (NOWAIT).

Sincronización en OpenMP

						
#include <omp.h>
int main(int argc, char *argv[])
{
	int x;
	x = 0;

	#pragma omp parallel shared(x)
	{
	#pragma omp critical
	x = x + 1;
	}
	/* Final de la región paralela */
}
						
					
    Sincronización por medio del comando "critical"
  • El comando CRITICAL especifica una región de código que debe ser ejecutada por un solo hilo a la vez.
  • Si un subproceso está ejecutándose actualmente dentro de una región CRÍTICA y otro subproceso llega a esa región CRÍTICA e intenta ejecutarla, se bloqueará hasta que el primer subproceso salga de esa región CRÍTICA.
  • todos los hilos del equipo intentarán ejecutarse en paralelo. Sin embargo, debido a la construcción CRÍTICA que rodea el incremento de x, sólo un hilo podrá leer, incrementar o escribir x en cualquier momento

Ejemplo de Programación Paralela en Java

						
public class CajeraThread extends Thread {
	private String nombre;
	private Cliente cliente;
	private long initialTime;
	// Constructor, getter & setter

	@Override
	public void run() {
		System.out.println("La cajera " + this.nombre + " COMIENZA A PROCESAR LA COMPRA DEL CLIENTE "
					+ this.cliente.getNombre() + " EN EL TIEMPO: "
					+ (System.currentTimeMillis() - this.initialTime) / 1000
					+ "seg");
		for (int i = 0; i < this.cliente.getCarroCompra().length; i++) {
			this.esperarXsegundos(cliente.getCarroCompra()[i]);
			System.out.println("Procesado el producto " + (i + 1)
			+ " del cliente " + this.cliente.getNombre() + "->Tiempo: "
			+ (System.currentTimeMillis() - this.initialTime) / 1000
			+ "seg");
		}
		System.out.println("La cajera " + this.nombre + " HA TERMINADO DE PROCESAR "
						+ this.cliente.getNombre() + " EN EL TIEMPO: "
						+ (System.currentTimeMillis() - this.initialTime) / 1000
						+ "seg");
	}

	private void esperarXsegundos(int segundos) {
		try {
			Thread.sleep(segundos * 1000);
		} catch (InterruptedException ex) {
			Thread.currentThread().interrupt();
		}
	}
}
						
					
    Supermercado

    En este ejemplo elaborado mediante el uso de objetos en java se simula el proceso de compra en un supermercado, para esto se tiene la clase cliente y la clase cajero que es la que se va a paralelizar mediante la herencia de la clase Thread.

Ejemplo de Programación Paralela en Java

						
public class MainThread {

	public static void main(String[] args) {

		Cliente cliente1 = new Cliente("Cliente 1", new int[] { 2, 2, 1, 5, 2, 3 });
		Cliente cliente2 = new Cliente("Cliente 2", new int[] { 1, 3, 5, 1, 1 });

		// Tiempo inicial de referencia
		long initialTime = System.currentTimeMillis();
		CajeraThread cajera1 = new CajeraThread("Cajera 1", cliente1, initialTime);
		CajeraThread cajera2 = new CajeraThread("Cajera 2", cliente2, initialTime);

		cajera1.start();
		cajera2.start();
	}
}
						
					
    Supermercado

    Se inicializan los dos hilos, luego se imprime en pantalla cada vez que se pasen los productos en cada cajero.
    Se puede observar como se realiza de forma paralela la compra en cada cajero.

Ejemplo de Programación Paralela en Java

						
La cajera Cajera 1 COMIENZA A PROCESAR LA COMPRA DEL CLIENTE Cliente 1 EN EL TIEMPO: 0seg
La cajera Cajera 2 COMIENZA A PROCESAR LA COMPRA DEL CLIENTE Cliente 2 EN EL TIEMPO: 0seg
Procesado el producto 1 del cliente Cliente 2->Tiempo: 1seg
Procesado el producto 1 del cliente Cliente 1->Tiempo: 2seg
Procesado el producto 2 del cliente Cliente 2->Tiempo: 4seg
Procesado el producto 2 del cliente Cliente 1->Tiempo: 4seg
Procesado el producto 3 del cliente Cliente 1->Tiempo: 5seg
Procesado el producto 3 del cliente Cliente 2->Tiempo: 9seg
Procesado el producto 4 del cliente Cliente 2->Tiempo: 10seg
Procesado el producto 4 del cliente Cliente 1->Tiempo: 10seg
Procesado el producto 5 del cliente Cliente 2->Tiempo: 11seg
La cajera Cajera 2 HA TERMINADO DE PROCESAR Cliente 2 EN EL TIEMPO: 11seg
Procesado el producto 5 del cliente Cliente 1->Tiempo: 12seg
Procesado el producto 6 del cliente Cliente 1->Tiempo: 15seg
La cajera Cajera 1 HA TERMINADO DE PROCESAR Cliente 1 EN EL TIEMPO: 15seg
						
					
    Supermercado

    Resultados obtenidos al ejecutar el programa para los casos de ejemplo descritos en el main haciendo uso de dos hilos de trabajo.

Bibliografía

  1. http://proparalelaydistribuida.blogdiario.com/tags/lenguajes-paralelos/
  2. http://informatica.uv.es/iiguia/ALP/materiales/1_1_a_ComputacionParalela.pdf
  3. http://lahuen.dcc.uchile.cl/mm_wiki/lib/exe/fetch.php?media=cpar:1-modelos.pdf
  4. http://www.cs.buap.mx/~mtovar/doc/ProgConc/ProgramacionParalela.pdf
  5. http://www.saber.ula.ve/bitstream/123456789/15969/1/com_par.pdf
  6. https://computing.llnl.gov/tutorials/parallel_comp/
  7. http://lsi.ugr.es/jmantas/pdp/tutoriales/tutorial_mpi.php?tuto=03_pi
  8. http://ocw.uc3m.es/ingenieria-informatica/arquitectura-de-computadores-ii/materiales-de-clasee/mc-f-002-iii
  9. Rauber, T., & Runger, G. (n.d.). Parallel programming: For multicore and cluster systems. Springer Books.
  10. Intro to parallel programming. Udacity course.
  11. Whitson, G. P. (2016). Parallel Computing. Salem Press Encyclopedia Of Science,
  12. Presentaciones profesor Cesar Pedraza - Computación paralela y Distribuida
  13. https://www.cs.purdue.edu/homes/ayg/book/Slides/
  14. https://computing.llnl.gov/tutorials/parallel_comp/
  15. http://web.mit.edu/vex/www/Parallel.pdf
  16. http://hdl.handle.net/10045/25282
  17. https://webdocs.cs.ualberta.ca/~paullu/C681/parallel.timeline.html
  18. https://es.wikipedia.org/wiki/Computaci%C3%B3n_paralela
  19. http://webdelprofesor.ula.ve/ingenieria/gilberto/paralela/07_ModelosDeProgramacionParalela.pdf
  20. http://webdelprofesor.ula.ve/ingenieria/gilberto/paralela/05_LeyDeAmdahlYMoore.pdf
  21. http://repositoriodigital.uns.edu.ar/bitstream/123456789/2001/1/MgTesis%20Weinbach%20-%20Paradigmas%20de%20Programacion
    %20en%20Paralelo.pdf
  22. McCOLL M., ROBISON A., REINDERS J., Structured Parallel Programming Patterns for Efficient Computation (2012)
  23. https://jarroba.com/multitarea-e-hilos-en-java-con-ejemplos-thread-runnable/
  24. https://www.agenciasinc.es/Noticias/La-UE-impulsa-la-computacion-paralela-para-aplicaciones-biomedicas