En la computación paralela , la granularidad (o tamaño de grano ) de una tarea es una medida de la cantidad de trabajo (o cálculo ) que realiza esa tarea. [1]
Otra definición de granularidad tiene en cuenta la sobrecarga de comunicación entre múltiples procesadores o elementos de procesamiento. Define la granularidad como la relación entre el tiempo de cálculo y el tiempo de comunicación, donde el tiempo de cálculo es el tiempo necesario para realizar el cálculo de una tarea y el tiempo de comunicación es el tiempo necesario para intercambiar datos entre procesadores. [2]
Si T comp es el tiempo de cálculo y T comm denota el tiempo de comunicación, entonces la granularidad G de una tarea se puede calcular como: [2]
La granularidad se mide generalmente en términos de la cantidad de instrucciones que se ejecutan en una tarea particular. [1] Alternativamente, la granularidad también se puede especificar en términos del tiempo de ejecución de un programa, combinando el tiempo de cálculo y el tiempo de comunicación. [1]
Dependiendo de la cantidad de trabajo que realiza una tarea paralela, el paralelismo se puede clasificar en tres categorías: paralelismo de grano fino, de grano medio y de grano grueso.
En el paralelismo de grano fino, un programa se divide en una gran cantidad de tareas pequeñas. Estas tareas se asignan individualmente a muchos procesadores. La cantidad de trabajo asociado con una tarea paralela es baja y el trabajo se distribuye uniformemente entre los procesadores. Por lo tanto, el paralelismo de grano fino facilita el equilibrio de carga . [3]
Como cada tarea procesa menos datos, la cantidad de procesadores necesarios para realizar el procesamiento completo es alta, lo que a su vez aumenta la sobrecarga de comunicación y sincronización.
El paralelismo de grano fino se aprovecha mejor en arquitecturas que admiten una comunicación rápida. La arquitectura de memoria compartida , que tiene una sobrecarga de comunicación baja, es la más adecuada para el paralelismo de grano fino.
Es difícil para los programadores detectar el paralelismo en un programa, por lo tanto, generalmente es responsabilidad de los compiladores detectar el paralelismo de grano fino. [1]
Un ejemplo de un sistema de grano fino (fuera del dominio de la computación paralela) es el sistema de neuronas de nuestro cerebro . [4]
Connection Machine (CM-2) y J-Machine son ejemplos de computadoras paralelas de grano fino que tienen un tamaño de grano en el rango de 4-5 μs. [1]
En el paralelismo de grano grueso, un programa se divide en tareas grandes. Debido a esto, una gran cantidad de cálculos se lleva a cabo en los procesadores. Esto puede provocar un desequilibrio de carga, en el que ciertas tareas procesan la mayor parte de los datos mientras que otras pueden estar inactivas. Además, el paralelismo de grano grueso no aprovecha el paralelismo en el programa, ya que la mayor parte de los cálculos se realizan de forma secuencial en un procesador. La ventaja de este tipo de paralelismo es la baja sobrecarga de comunicación y sincronización.
La arquitectura de paso de mensajes tarda mucho tiempo en comunicar datos entre procesos, lo que la hace adecuada para el paralelismo de grano grueso. [1]
Cray Y-MP es un ejemplo de computadora paralela de grano grueso que tiene un tamaño de grano de aproximadamente 20 s. [1]
El paralelismo de grano medio se utiliza en comparación con el paralelismo de grano fino y el de grano grueso. El paralelismo de grano medio es un compromiso entre el paralelismo de grano fino y el de grano grueso, donde el tamaño de la tarea y el tiempo de comunicación son mayores que en el paralelismo de grano fino y menores que en el de grano grueso. La mayoría de las computadoras paralelas de propósito general entran en esta categoría. [4]
Intel iPSC es un ejemplo de computadora paralela de grano medio que tiene un tamaño de grano de aproximadamente 10 ms. [1]
Considere una pila de 20 imágenes de 10 x 10 píxeles que deben procesarse, suponiendo que cada uno de los 100 píxeles puede procesarse independientemente de los demás. Procesar 1 píxel requiere 1 ciclo de reloj.
Paralelismo de grano fino: cada píxel será procesado individualmente por un procesador a la vez. Suponiendo que hay 100 procesadores responsables de procesar la imagen, los 100 procesadores pueden procesar una imagen de 10x10 en un solo ciclo de reloj. Con 20 procesadores, se necesitarían 5 ciclos de reloj por imagen. Cada procesador puede utilizarse durante el 100% de su tiempo disponible, pero el resultado de cada cálculo de píxel debe comunicarse y agregarse al final de cada procesamiento de imagen, lo que puede causar una gran sobrecarga (100 comunicaciones por imagen = 2000 en total).
Paralelismo de grano medio: las imágenes se dividen en cuartos. Cada cuarto será procesado individualmente por un procesador a la vez, lo que requiere 25 ciclos de reloj (para 5x5 píxeles). Suponiendo que hay 20 procesadores responsables de procesar la pila de 20 imágenes, se pueden procesar 5 imágenes en paralelo con 4 procesadores trabajando en cada imagen. Si hubiera 100 procesadores disponibles, 80 podrían procesar la pila en paralelo, lo que requiere 25 ciclos de reloj, mientras que 20 procesadores permanecen inactivos sin ningún trabajo asignado. Una vez que se han procesado los cuatro cuartos, se deben agregar los resultados (4 comunicaciones por imagen = 80 en total).
Paralelismo de grano grueso: una imagen completa es procesada por un solo procesador que tarda 100 ciclos de reloj. En este caso, solo se pueden utilizar 20 procesadores a la vez, y completan el trabajo en 100 ciclos de reloj sin ninguna comunicación.
La decisión sobre qué enfoque es mejor depende de la carga de trabajo y las unidades de procesamiento disponibles. El objetivo debe ser maximizar la paralelización (dividir el trabajo en suficientes unidades para distribuirlo uniformemente entre la mayoría de los procesadores disponibles) mientras se minimiza la sobrecarga de comunicación (relación entre el tiempo dedicado a la comunicación y el tiempo dedicado al cálculo). En nuestro ejemplo, si la cantidad de imágenes a procesar es alta en comparación con la cantidad de trabajadores, no tiene sentido dividir las imágenes en unidades más pequeñas, ya que cada trabajador recibirá suficiente carga. Si la cantidad de imágenes es pequeña en comparación con la cantidad de trabajadores, algunos trabajadores pueden permanecer inactivos y desperdiciar tiempo de cálculo. Sin embargo, esto solo es un problema si procesar una sola imagen lleva mucho tiempo. Si el procesamiento es muy rápido, dividir el trabajo en unidades más pequeñas puede hacer que la operación total sea más lenta, ya que el tiempo perdido en la comunicación es mayor que el tiempo ganado a través de la paralelización.
La granularidad está estrechamente relacionada con el nivel de procesamiento. Un programa se puede dividir en cuatro niveles de paralelismo:
La mayor cantidad de paralelismo se logra en el nivel de instrucción , seguido del paralelismo en el nivel de bucle . En el nivel de instrucción y bucle, se logra un paralelismo de grano fino. El tamaño de grano típico en el nivel de instrucción es de 20 instrucciones, mientras que el tamaño de grano en el nivel de bucle es de 500 instrucciones. [1]
En el nivel de subrutina (o procedimiento), el tamaño de grano suele ser de unos pocos miles de instrucciones. El paralelismo de grano medio se logra en el nivel de subrutina. [1]
A nivel de programa , se lleva a cabo la ejecución paralela de programas. La granularidad puede ser del orden de decenas de miles de instrucciones. [1] En este nivel se utiliza paralelismo de grano grueso.
La siguiente tabla muestra la relación entre los niveles de paralelismo, el tamaño de grano y el grado de paralelismo.
La granularidad afecta el rendimiento de las computadoras paralelas. El uso de granos finos o tareas pequeñas da como resultado un mayor paralelismo y, por lo tanto, aumenta la velocidad . Sin embargo, la sobrecarga de sincronización, las estrategias de programación , etc. pueden afectar negativamente el rendimiento de las tareas de grano fino. El aumento del paralelismo por sí solo no puede brindar el mejor rendimiento. [5]
Para reducir la sobrecarga de comunicación, se puede aumentar la granularidad. Las tareas de grano grueso tienen menos sobrecarga de comunicación, pero a menudo causan desequilibrio de carga. Por lo tanto, se logra un rendimiento óptimo entre los dos extremos del paralelismo de grano fino y de grano grueso. [6]
Varios estudios [5] [7] [8] han propuesto su solución para ayudar a determinar la mejor granularidad para facilitar el procesamiento en paralelo. Encontrar el mejor tamaño de grano depende de varios factores y varía mucho de un problema a otro.
{{cite journal}}: Requiere citar revista |journal=( ayuda )