Hispanopedia WikiEn la computación paralela , la granularidad (o tamaño de grano ) de una tarea es una medida de la cantidad de trabajo (o computación ) 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 computación y T comm denota el tiempo de comunicación, entonces la granularidad G de una tarea se puede calcular como: [ 2 ]
La granularidad se suele medir en términos del número de instrucciones que se ejecutan en una tarea determinada. [ 1 ] Alternativamente, la granularidad también puede especificarse en términos del tiempo de ejecución de un programa, combinando el tiempo de cálculo y el tiempo de comunicación. [ 1 ]
Tipos de paralelismo
Según la cantidad de trabajo que realice una tarea paralela, el paralelismo se puede clasificar en tres categorías: paralelismo de grano fino, de grano medio y de grano grueso.
Paralelismo de grano fino
En el paralelismo de grano fino, un programa se divide en un gran número de tareas pequeñas. Estas tareas se asignan individualmente a muchos procesadores. La cantidad de trabajo asociada a una tarea paralela es baja y se distribuye uniformemente entre los procesadores. Por lo tanto, el paralelismo de grano fino facilita el equilibrio de carga . [ 3 ]
A medida que cada tarea procesa menos datos, aumenta el número de procesadores necesarios para completar el procesamiento. Esto, a su vez, incrementa 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 baja sobrecarga de comunicación, es la más adecuada para el paralelismo de grano fino.
Para los programadores es difícil 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 en 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 ]
Paralelismo de grano grueso
En el paralelismo de grano grueso, un programa se divide en tareas grandes. Debido a esto, se realiza una gran cantidad de cálculos en los procesadores. Esto puede provocar un desequilibrio de carga, donde ciertas tareas procesan la mayor parte de los datos mientras que otras permanecen inactivas. Además, el paralelismo de grano grueso no aprovecha el paralelismo del programa, ya que la mayor parte de los cálculos se realizan secuencialmente en un procesador. La ventaja de este tipo de paralelismo radica en 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 ]
Paralelismo de grano medio
El paralelismo de grano medio se utiliza en relación con el paralelismo de grano fino y el de grano grueso. El paralelismo de grano medio representa un compromiso entre ambos, donde el tamaño de las tareas 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 se incluyen 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 ]
Ejemplo
Consideremos una pila de 20 imágenes de 10x10 píxeles que deben procesarse, suponiendo que cada uno de los 100 píxeles puede procesarse de forma independiente. El procesamiento de 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 encargados del procesamiento de la imagen, estos pueden procesar una imagen de 10x10 píxeles en un solo ciclo de reloj. Con 20 procesadores, se necesitarían 5 ciclos de reloj por imagen. Cada procesador puede utilizarse al 100% de su tiempo disponible, pero el resultado del cálculo de cada píxel debe comunicarse y agregarse al final del procesamiento de cada imagen, lo que puede generar una gran sobrecarga (100 comunicaciones por imagen = 2000 en total).
Paralelismo de grano medio: Las imágenes se dividen en cuatro partes. Cada parte se procesa individualmente mediante un procesador a la vez, lo que requiere 25 ciclos de reloj (para 5x5 píxeles). Si se dispone de 20 procesadores para procesar la pila de 20 imágenes, se pueden procesar 5 imágenes en paralelo con 4 procesadores trabajando en cada una. Si se dispusiera de 100 procesadores, 80 podrían procesar la pila en paralelo, lo que requeriría 25 ciclos de reloj, mientras que 20 procesadores permanecerían inactivos sin ninguna tarea asignada. Una vez procesados los cuatro cuartos, se deben agregar los resultados (4 comunicaciones por imagen = 80 en total).
Paralelismo de grano grueso: Un solo procesador procesa una imagen completa en 100 ciclos de reloj. En este caso, solo se pueden usar 20 procesadores a la vez, completando el trabajo en 100 ciclos de reloj sin comunicación entre ellos.
La decisión sobre qué enfoque es el 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) y minimizar 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 el número de imágenes a procesar es alto en comparación con el número de trabajadores, no tiene sentido dividir las imágenes en unidades más pequeñas, ya que cada trabajador recibirá suficiente carga. Si el número de imágenes es pequeño en comparación con el número de trabajadores, algunos trabajadores podrían permanecer inactivos y desperdiciar tiempo de cálculo. Sin embargo, esto solo es un problema si el procesamiento de una sola imagen lleva mucho tiempo. Si el procesamiento es muy rápido, dividir el trabajo en unidades más pequeñas podría ralentizar la operación total, ya que el tiempo perdido en la comunicación es mayor que el tiempo ganado mediante la paralelización.
Niveles de paralelismo
La granularidad está estrechamente ligada al nivel de procesamiento. Un programa se puede dividir en 4 niveles de paralelismo:
- Nivel de instrucción.
- Nivel de bucle
- Nivel de subrutina y
- Nivel de programa
El mayor grado de paralelismo se alcanza a nivel de instrucción , seguido del paralelismo a nivel de bucle . Tanto a nivel de instrucción como de bucle, se logra un paralelismo de grano fino. El tamaño de grano típico a nivel de instrucción es de 20 instrucciones, mientras que a nivel de bucle es de 500 instrucciones. [ 1 ]
A 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 a nivel de subrutina. [ 1 ]
A nivel de programa , se lleva a cabo la ejecución paralela de programas. La granularidad puede estar en el rango de decenas de miles de instrucciones. [ 1 ] En este nivel se utiliza el paralelismo de grano grueso.
La siguiente tabla muestra la relación entre los niveles de paralelismo, el tamaño del grano y el grado de paralelismo.
Impacto de la granularidad en el rendimiento
La granularidad afecta el rendimiento de las computadoras paralelas. El uso de granos finos o tareas pequeñas resulta en un mayor paralelismo y, por lo tanto, aumenta la velocidad . Sin embargo, la sobrecarga de sincronización, las estrategias de planificación , etc., pueden afectar negativamente el rendimiento de las tareas de grano fino. Aumentar el paralelismo por sí solo no garantiza el mejor rendimiento. [ 5 ]
Para reducir la sobrecarga de comunicación, se puede aumentar la granularidad. Las tareas de grano grueso tienen menor sobrecarga de comunicación, pero a menudo provocan desequilibrio de carga. Por lo tanto, el rendimiento óptimo se logra entre los dos extremos del paralelismo de grano fino y grano grueso. [ 6 ]
Diversos estudios [ 5 ] [ 7 ] [ 8 ] han propuesto soluciones para determinar la granularidad óptima para el procesamiento paralelo. Encontrar el tamaño de grano ideal depende de varios factores y varía considerablemente según el problema.
Véase también
Citas
- 1 2 3 4 5 6 7 8 9 10 11 Hwang, Kai (1992). Arquitectura avanzada de computadoras: paralelismo, escalabilidad, programabilidad (1.ª ed.). McGraw-Hill Higher Education. ISBN 978-0070316225.
- 1 2 Kwiatkowski, Jan (9 de septiembre de 2001). "Evaluación de programas paralelos mediante la medición de su granularidad". Procesamiento paralelo y matemáticas aplicadas . Notas de clase en ciencias de la computación. Vol. 2328. págs. 145–153 . doi : 10.1007/3-540-48086-2_16 . ISBN 9783540437925.ISBN 9783540480860.
- ↑ Barney, Blaise. Introducción a la computación paralela .
- 1 2 Miller, Russ; Stout, Quentin F. (1996). Algoritmos paralelos para arquitecturas regulares: mallas y pirámides . Cambridge, Mass.: MIT Press. págs. 5–6 . ISBN 9780262132336.
- 1 2 Chen, Ding-Kai; Su, Hong-Men; Yew, Pen-Chung (1 de enero de 1990). "El impacto de la sincronización y la granularidad en los sistemas paralelos". Actas del 17.º simposio internacional anual sobre arquitectura de computadoras - ISCA '90 . Vol. 18. págs. 239–248 . CiteSeerX 10.1.1.51.3389 . doi : 10.1145/325164.325150 . ISBN 0-89791-366-3. S2CID 16193537 .
- ↑ Yeung, Donald; Dally, William J.; Agarwal, Anant. "Cómo elegir el tamaño de grano de una computadora paralela" (PDF) . Instituto Tecnológico de Massachusetts . pág. 2.
- ↑ McCreary, Carolyn; Gill, Helen (1 de septiembre de 1989). "Determinación automática del tamaño de grano para un procesamiento paralelo eficiente" . Communications of the ACM . 32 (9): 1073– 1078. doi : 10.1145/66451.66454 . ISSN 0001-0782 . S2CID 14807217 .
- ^ Kruatrachue, Boontee; Lewis, Ted (1 de enero de 1988). "Determinación del tamaño de grano para procesamiento paralelo" . Software IEEE . 5 (1): 23– 32. Código Bib : 1988ISoft...5a..23K . doi : 10.1109/52.1991 . ISSN 0740-7459 . S2CID 2034255 .
- Análisis de algoritmos paralelos
