Sincronización de hebras en paralelismo masivo

De Departamento de Informatica
Saltar a: navegación, buscar

Cuando se tratan grandes problemas que requieren de mucho procesamiento y cálculo, conviene utilizar estrategias que aceleren el proceso completo. Esto se puede llevar a cabo mediante la creación de hebras en paralelo, y por sobre todo si se utilizan masivamente. El problema radica en la sincronización de tantas hebras que corren en paralelo, lo cual se explicará a continuación, junto a una breve introducción al concepto de Computación Paralela.


Contenido

Computación Paralela

La computación paralela consiste en una técnica que se basa en el principio de tomar grandes problemas y dividirlos en numerosas partes más pequeñas, que se asignan y se ejecutan en distintos procesadores de manera simultánea, con el fin de resolver cada parte de forma paralela y así el problema total resolverlo con mayor eficiencia.

Para realizar este tipo de computación paralela se requiere de tres partes fundamentales, independiente de la arquitectura.

  • Dividir: tomar una tarea y dividirla en subtareas.
  • Asignar: asignar las subtareas para que los distintos procesadores las hagan.
  • Comunicación: si no hay no pueden ser procesadas a la vez.


Las estrategias más utilizadas en computación paralela suelen estar clasificadas en:

  • Paralelismo de Tareas: a cada procesador se le asignan distintas tareas.
  • Paralelismo de Datos: a cada procesador se le asignan un conjunto de datos sobre los cuales efectuar las tareas.


La computación paralela se puede llevar a cabo mediante:

  • Multiprocesadores: computadores que poseen dos o mas procesadores.
  • Multicomputadores: equivalente a un multiprocesador, pero compuesto por múltiples sistemas trabajando coordinadamente.


La computación paralela utiliza dos o mas elementos de procesamiento, que pueden ser CPU de uno o varios núcleos, sumando además de GPU (Graphic Processing Units) o algún otro tipo de acelerador. Todos estos elementos de procesamiento y sus recursos deben ser administrados para que puedan correr en forma paralela y ser utilizados en eficientemente.

Algunas de las tareas de los Sistemas Operativos que se utilizan en computación paralela son iguales a las tareas realizadas por un Sistema Operativo normal, como por ejemplo el manejo de memoria, el I/O, etc., pero existen otras tareas que estos Sistemas Operativos deben soportar. Por ejemplo, en un sistema de memoria distribuida donde no todas las CPU tienen acceso a toda la memoria del sistema, los datos deben ser transferidos entre las memorias. Los datos deben ser transmitidos dentro de mensajes, y el Sistema Operativos debe proveer funciones para enviar y recibir estos mensajes, o proveer funciones para que aplicaciones accedan a la interfaz de red en forma segura.

Otra de las tareas de los Sistemas Operativos en la computación paralela es mejorar la coordinación de los procesos entre las máquinas. Muchas veces los procesos que son parte de una aplicación paralela necesitan comunicarse y sincronizarse con alguna otra máquina. Alguno de los métodos utilizados para esto es la utilización de hardware u operaciones especiales de red.


Ventajas de la computación paralela

Mas rápida y mas precisa. Sirve principalmente para problemas de tiempo real, ya que divide las tareas y las realiza simultáneamente para luego coordinar e integrar la solución en un periodo de tiempo más corto.


Desventajas

Es importante saber que no todas las secciones de programas son completamente paralelizables, ya que no se pueden dividir en problemas más pequeños. Adicionalmente, se pierde tiempo en el proceso de sincronización de los procesadores, cuando se coordinan los accesos a los recursos que se comparten en la arquitectura implementada. En estos casos es necesario identificar si es conveniente paralelizar el programa.

Sincronización de Hebras

En programación paralela, las instrucciones a las hebras se producen en forma secuencial; pero si las secuencias de estos hilos se ejecutan en forma independientemente sus instrucciones se podrían intercalar y esto podría producir errores o resultados incorrectos. La sincronización se utiliza para impedir la ocurrencia de hilos no válidos. Por ejemplo, si consideramos un contador con varios subprocesos, cada hilo carga el contador en un registro e incrementa el registro antes de devolver el valor actualizado a la memoria. Si dos hilos cargaran el mismo valor en sus registros antes que uno retorne el valor actualizado, entonces se produciría un error.

Ejemplo
                     c == 0

          Thread 1               Thread 2
           r1 = c                 r1 = c         
            ++r1                   ++r1
           c = r1                 c = r1
                     c == 1


Véase también: Itineracion de hebras


Sincronización de Hebras en Paralelismo Masivo. Ejemplos.

El paralelismo masivo se refiere a casos de computación paralela aplicada a gran escala, por ejemplo en supercomputadores. Un problema que ocurre es que al tener una gran cantidad de hebras en ejecución y que realizan accesos a recursos compartidos, existan colisiones y operaciones aleatorias al no existir un orden en las operaciones. Por ello, es necesario utilizar alguna herramienta de control que evite lo anterior y pueda administrar de manera más ordenada las hebras. Sin embargo, al ser operaciones en las cuales se utilizan masivamente las hebras, no podemos hacer uso de semáforos o implementaciones similares, ya que esto solo disminuye la velocidad que se logra gana al realizar la ejecución de las hebras de forma paralela y ordenada.

CUDA: En CUDA se usa una función llamada __syncthreads() que funciona como una barrera que hace que todos los threads deban esperar a que el resto termine la ejecución de sus tareas y lleguen al mismo punto, una vez que todos los threads estén listos la barrera "se levanta" y sigue el flujo normal de la aplicación. Esto funciona como una ejecución por bloques de hebras.

//codigo con operaciones
__syncthreads()
a=a+1

en este caso por ejemplo el programa esperará a que todos los threads terminen y cuando esto ocurra solo en ese momento se ejecutará sumarle 1 a la variable a

OpenCL: OpenCL es una alternativa a CUDA desarrollada por Apple, es un estandar y es libre de derechos, principalmente es apoyada por AMD, en este caso el sistema de sincronización es similar a CUDA, se usa una función llamada barrier() la cual contiene la misma base que __syncthreads(), actuar de barrera y esperar a que todos los threads terminen sus tareas para continuar con el siguiente bloque de codigo, esta función puede recibir dos parametros CLK_LOCAL_MEM_FENCE o CLK_GLOBAL_MEM_FENCE, la primera se usa cuando solo estemos accediando a memoria local y la ultima para memoria global

//codigo con operaciones
barrier(CLK_LOCAL_MEM_FENCE | CLK_GLOBAL_MEM_FENCE)
a=a+1

MPI: Quiere decir Interfaz por paso de mensajes (en ingles) el cual es un protocolo en el cual computadoras (o en este caso, threads) pueden comunicarse entre ellos, es portable y esta implementado para casi toda arquitectura de memoria distribuida. Para lograr la sincronización se usa un metodo similar a los casos anteriores, existe la función mpi_barrier(comunicador)


Representación gráfica: cada nodo representa un thread o proceso, se muestra como la función hace que todos deban esperar a que el resto llegue al mismo punto para seguir la ejecución



Bibliografía Utilizada

"Encyclopedia of Parallel Computing", David Padua (Ed.), Springer Science+Business Media, 2011.

"Fundamentos de Sistemas Operativos", Silberschatz, Galvin, Gagne, Séptima Edición, 2005.


Enlaces Externos

http://stackoverflow.com/questions/6890302/barriers-in-opencl

http://www.mpitutorial.com/mpi-broadcast-and-collective-communication/#more-788

Herramientas personales
Espacios de nombres
Variantes
Acciones
Navegación
Herramientas