PARALELISMO

Caracterización del Paralelismo  

En general, la eficiencia de una máquina, para resolver un problema dado, depende de la implementación del algoritmo de resolución. En particular, las máquinas paralelas ofrecen un poder de cálcul o enorme, pero explotar todas sus potencialidades no es fácil. Por otro lado, los problemas tienen diferentes características factibles a explotar, cuando se desean desarrollar aplicaciones paralelas para resolverlos. La mejor implementación secuencial de resolución de un problema dado no conlleva obligatoriamente al mejor algoritmo paralelo, ya que para desarrollar un algoritmo paralelo se deben explotar lo que denominaremos las fuentes de paralelismo del problema. Básicamente, existen dos modos de ver el paralelismo.

•  Modo Concurrente: supongamos una aplicación paralela compuesta de tareas, donde además, existe una estructura de intercambio de información entre las tareas. Los sistemas concurrentes buscan ejecutar simultáneamente las que se pueden (si no existen dependencia entre ellas, etc.). La red de intercambio de información es asimétrica y los intercambios asincrónicos. Los problemas de asignación de tareas y gestión de la red de interconexión son dos de los problemas más importantes a resolver. Este enfoque implica que las tareas a paralelizar deben ser explícitamente definidas
•  - Modo Paralelo: las tareas de la aplicación se organizan en forma de una estructura regular como una tabla. Las tareas son lo más parecido posible entre ellas, y la red de interconexión es síncrona y simétrica espacialmente. Muchas veces, esto conlleva a que las aplicaciones pasen por una fase de pre-tratamiento para espaciarlas y transformarlas en tareas simétricas. Es más fácil construir máquinas paralelas para que exploten este modo. Normalmente, en este caso, el paralelismo es implícito, por lo que extraer su paralelismo es uno de los problemas fundamentales a resolver.

Para ambos modos se han desarrollado diferentes lenguajes de programación, ambientes de desarrollo, etc.

Perfil de Paralelismo

 El perfil de paralelismo de una aplicación es definido como la “cantidad de paralelismo” que una aplicación posee. Dicha cantidad esta caracterizada por dos parámetros: grado y grano de paralelismo

 Granularidad;  El grano de paralelismo es definido como el tamaño promedio de las acciones (tamaño promedio de una tarea elemental) en termino de:

•  - Número de instrucciones ejecutadas. 
• - Número de palabras de memorias usadas.
•  - Duración de su tiempo de ejecución. 

 También puede definirse como la cantidad de procesamiento que una tarea realiza antes de necesitar comunicarse con otra tarea. Por supuesto, un grano puede crecer o decrecer agrupando o desagrupando tareas. Esto establece una relación entre el tiempo de cálculo con respecto al número de eventos de comunicación (granularidad de la aplicación). Así, la granularidad, es la relación entre la computación y la comunicación, a lo interno de una aplicación. Una granularidad pequeña (grano fino) implica más comunicación y cambios de contextos entre las tareas (es una aplicación con comunicación intensiva). Una granularidad grande (grano fuerte) implica menos comunicación, pero puede que potenciales tareas concurrentes queden agrupadas, y por consiguiente, ejecutadas secuencialmente. Así, la determinación del grano ideal, para una aplicación dada, es importante, para definir la mejor relación entre paralelismo (grano pequeño) y comunicación (grano grande). El problema de determinación del tamaño óptimo del grano para una aplicación dada es un problema de optimización del tipo MaxMin (Maximizar paralelismo y Minimizar comunicación), y debe estar vinculado a la máquina donde se ejecuta la aplicación. El paralelismo a grano fuerte, es normalmente usado en las arquitecturas tipo MIMD, mientras que el paralelismo a grano fino es especialmente usado en las máquinas SIMD.

 Grado de Paralelismo 

El grado de paralelismo es definido como el número de acciones (tareas) que se pueden ejecutar en paralelo durante la ejecución de una aplicación. Es decir, corresponde a una medida del número de operaciones que se pueden ejecutar simultáneamente, y refleja el número de procesadores a utilizar en paralelo durante la ejecución de la aplicación. Puede ser calculado estáticamente, según la estructura de la aplicación, o dinámicamente, a partir de medidas durante la ejecución. El grado de paralelismo puede ser diferente a través de las diferentes partes de un programa, por lo que se habla de un grado de paralelismo máximo, mínimo y promedio. El grado máximo es el límite superior en cuanto al número de procesadores que podrían utilizarse. Con ese número de procesadores la ejecución de la aplicación quizás sería la más rápida posible, pero su eficacidad podría ser mediocre si ese valor máximo excede en mucho al grado promedio de paralelismo (muchos procesadores pasarían inactivos durante gran parte de la ejecución del programa).

. Fuentes de Paralelismo 

Las máquinas paralelas tienen por finalidad explotar el paralelismo inherente en las aplicaciones paralelas. Todas las aplicaciones no tienen el mismo tipo ni la misma cantidad de paralelismo. El primer aspecto tiene que ver con una característica   cualitativa: la manera como el paralelismo puede ser explotado, denominado fuente de paralelismo. Básicamente, existen tres tipos de paralelismo de control, de datos y de flujo. Muchas aplicaciones usan los tres tipos de paralelismo al mismo tiempo.

 Paralelismo de Control 

Consiste en hacer cosas diferentes al mismo tiempo.  Este tipo de paralelismo surge de la constatación natural de que una aplicación paralela está compuesta de acciones que se pueden hacer al mismo tiempo. Las acciones (tareas o procesos) pueden ser ejecutadas de manera más o menos independiente sobre diferentes procesadores. El paradigma de programación divide y vencerás es típico de esta fuente de paralelismo.
 En este enfoque se requiere una primera fase de descomposición del programa en tareas, para después definir cuáles se pueden ejecutar simultáneamente o se deben ejecutar secuencialmente. Los criterios importantes a considerar son el número de tareas, el grano de paralelismo, y las dependencias entre las diferentes tareas. Una dependencia surge cuando una acción (tarea) se debe terminar para que otra continúe. Existen dos clases de dependencias:

•  - Dependencia de Control de Secuencia: Es el secuenciamiento clásico de los algoritmos secuenciales. 
• - Dependencia de Control de Comunicación: Es cuando una tarea envía información a otra tarea, la cual no puede continuar hasta recibir dicha información.

 Los dos casos de dependencias deben optimizar el siguiente criterio a la hora de asignar las tareas a los procesadores: minimizar los lapsos de tiempo que pasan los procesadores desocupados, o a la espera, debido a dichas dependencias. Bajo la noción de manejo de recursos, la explotación de paralelismo de control consiste en manejar las dependencias entre las tareas de una aplicación, para obtener una asignación de ellas, tan eficaz como sea posible.

Las principales limitaciones que se encuentran en este paralelismo son las siguientes :

•  - Dependencias Temporales: ligadas al problema de secuenciamiento y comunicación entre las tareas. 
• - Dependencias Espaciales: ligadas al número limitado de recursos. Si no existen suficientes procesadores, un fenómeno de cuello de botella se produce, tal que es necesario ejecutar secuencialmente parte del trabajo. 
• - Sobrecosto por la gestión de los granos: cuando el tamaño del grano de paralelismo es muy pequeño, los tiempos de gestión (activación, suspensión, etc.) son cada vez más grandes con respecto al trabajo efectuado por el sistema para ejecutar las tareas.
•  - El tamaño de las tareas que se ejecutan concurrentemente debe ser similar. Un desequilibrio en el mismo puede conllevar a tiempos en los que sólo pocos procesadores están trabajando.
•  - En máquinas de memorias distribuidas o máquinas con jerarquía de memoria, hay que añadir el problema de comunicación típico de estas arquitecturas.

 Las características básicas a considerar en este paralelismo son:

•  - Un programa paralelo consiste de una o más tareas, algunas de las cuales pueden ejecutarse concurrentemente mientras que otras dependen de la ejecución previa de otras tareas. 
• - Una tarea encapsula un programa secuencial y normalmente requiere comunicarse con su ambiente u otras tareas del mismo programa (compartiendo espacios de memoria o enviando mensajes).
•  - El tamaño de las tareas debe ser lo suficientemente grande, para que el tiempo para iniciar la ejecución de una tarea no sea importante.
•  - Se deben resolver los problemas de planificación de la ejecución de las tareas, de asignación de las tareas a los procesadores, etc., con la idea de reducir sus tiempos de ejecución. 
• - Las tareas pueden ser asignadas a los procesadores según diferentes criterios: distribuyendo la carga de trabajo, minimizando los costos de comunicación entre ellas, etc.

Paralelismo de Datos 

La explotación del paralelismo de datos proviene de la constatación de que ciertas aplicaciones actúan sobre estructuras de datos regulares (vectores, matrices, etc.), repitiendo un mismo cálculo sobre cada elemento de la estructura. Así, normalmente, se habla de programas que manipulan estructuras de datos regulares. La idea es explotar la regularidad de los datos, realizando en paralelo un mismo cálculo sobre datos distintos, por ejemplo: “aumentarle el salario a todos los empleados con más de 5 años de servicio”.
 En este tipo de paralelismo se asocian directamente los datos a los procesadores. Como los cálculos se realizan en paralelo sobre procesadores idénticos, es posible centralizar el control. Al ser los datos similares, la operación a repetir toma el mismo tiempo sobre todos los procesadores, y el controlador puede enviar de manera síncrona la operación a ejecutar a todos los procesadores. Normalmente, este es un tipo de paralelismo de grano fino, por lo cual se requieren plataformas del tipo SIMD.
 Las principales limitaciones que se encuentran en este paralelismo son las siguientes:

•  - Manejo de Vectores: si el tamaño de la máquina es más pequeño que el tamaño de los datos vectoriales, hay que descomponerlos, lo que agrega un tiempo extra de asignación y de gestión de tareas. 
• - Manejo de Escalares: las aplicaciones que manipulan datos vectoriales, usan frecuentemente datos escalares. Cuando se procesa el escalar, sólo un procesador trabaja y el resto permanece ocioso.
•  - Operaciones de difusión y reducción: estas operaciones sobre los datos vectoriales normalmente no son realizadas en paralelo, aunque realmente esto depende de la topología de la plataforma.

 Algunos aspectos son importantes a considerar cuando se desea explotar este tipo de paralelismo. Dichos aspectos son los siguientes:

a) Distribución de los Datos: Los datos son normalmente numerosos, mucho mayor al número de procesadores en el sistema. Esto obliga a que los datos sean repartidos entre los diferentes procesadores disponibles. La regularidad de las estructuras de datos permite distribuirlos de manera regular.

 b) Ejecución Síncrona : El paralelismo de datos es clásicamente usado en máquinas SIMD con control centralizado, por lo que se puede ver como un flujo de control sobre múltiples datos. En este caso, la sincronización es automática al existir un sólo controlador.

 c) Dependencia de Datos

d) Perfil de Paralelismo de Datos :Existen dos operaciones básicas en el paralelismo de datos, a través de las cuales se puede expresar todo el paralelismo encontrado en él: ϕ-notación y β-reducción. ϕ- notación es descrita por una función f de dimensión n y n vectores del mismo tamaño. ϕ- notación aplica en paralelo la función f sobre el conjunto de vectores.


 ϕ y β son lo suficientemente generales como para expresar un gran número de operaciones sobre datos regulares, como vectores y matrices, al tratar de explotar el paralelismo de datos.