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.
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.
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
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.
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.
- - 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.
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.












