En informática , el operador de reducción [1] es un tipo de operador que se usa comúnmente en la programación paralela para reducir los elementos de una matriz en un solo resultado. Los operadores de reducción son asociativos y, a menudo (pero no necesariamente) conmutativos . [2] [3] [4] La reducción de conjuntos de elementos es una parte integral de los modelos de programación como Map Reduce , donde se aplica ( mapea ) un operador de reducción a todos los elementos antes de reducirlos. Otros algoritmos paralelosutilizar operadores de reducción como operaciones primarias para resolver problemas más complejos. Se pueden utilizar muchos operadores de reducción para la transmisión a fin de distribuir datos a todos los procesadores.
Teoría
Un operador de reducción puede ayudar a dividir una tarea en varias tareas parciales calculando resultados parciales que pueden usarse para obtener un resultado final. Permite realizar determinadas operaciones en serie en paralelo y reducir el número de pasos necesarios para esas operaciones. Un operador de reducción almacena el resultado de las tareas parciales en una copia privada de la variable. Estas copias privadas luego se fusionan en una copia compartida al final.
Un operador es un operador de reducción si:
- Puede reducir una matriz a un solo valor escalar. [2]
- El resultado final debe poder obtenerse a partir de los resultados de las tareas parciales que se crearon. [2]
Estos dos requisitos se satisfacen para los operadores conmutativos y asociativos que se aplican a todos los elementos de la matriz.
Algunos operadores que satisfacen estos requisitos son la suma, la multiplicación y algunos operadores lógicos (y, o, etc.).
Un operador de reducción se puede aplicar en tiempo constante en un conjunto de entrada de vectores con elementos cada uno. El resultado de la operación es la combinación de los elementos y debe almacenarse en un procesador raíz especificado al final de la ejecución. Si el resultadotiene que estar disponible en todos los procesadores una vez finalizado el cálculo, a menudo se denomina Allreduce. Un algoritmo de reducción de tiempo lineal secuencial óptimo puede aplicar el operador sucesivamente de adelante hacia atrás, reemplazando siempre dos vectores con el resultado de la operación aplicado a todos sus elementos, creando así una instancia que tiene un vector menos. Necesita pasos hasta solo es izquierda. Los algoritmos secuenciales no pueden funcionar mejor que el tiempo lineal, pero los algoritmos paralelos dejan algo de espacio para optimizar.
Ejemplo
Supongamos que tenemos una matriz . La suma de esta matriz se puede calcular en serie reduciendo secuencialmente la matriz en una sola suma utilizando el operador '+'. Comenzar la suma desde el principio de la matriz produce:
Dado que '+' es tanto conmutativo como asociativo, es un operador de reducción. Por lo tanto, esta reducción se puede realizar en paralelo utilizando varios núcleos, donde cada núcleo calcula la suma de un subconjunto de la matriz y el operador de reducción fusiona los resultados. El uso de una reducción de árbol binario permitiría calcular 4 núcleos, , , y . Entonces dos núcleos pueden calcular y y, por último, un solo núcleo calcula . Entonces, se puede usar un total de 4 núcleos para calcular la suma en pasos en lugar de los pasos necesarios para la versión de serie. Esta técnica de árbol binario paralelo calcula. Por supuesto, el resultado es el mismo, pero solo por la asociatividad del operador de reducción. La conmutatividad del operador de reducción sería importante si hubiera un núcleo maestro distribuyendo el trabajo a varios procesadores, ya que entonces los resultados podrían llegar al procesador maestro en cualquier orden. La propiedad de conmutatividad garantiza que el resultado será el mismo.
No ejemplo
La multiplicación de matrices no es un operador de reducción ya que la operación no es conmutativa. Si a los procesos se les permitiera devolver sus resultados de multiplicación de matrices en cualquier orden al proceso maestro, el resultado final que el maestro calcula probablemente será incorrecto si los resultados llegaron fuera de orden. Sin embargo, tenga en cuenta que la multiplicación de matrices es asociativa y, por lo tanto, el resultado sería correcto siempre que se aplicara el orden adecuado, como en la técnica de reducción de árbol binario.
Algoritmos
Algoritmos de árbol binomial
En cuanto a los algoritmos paralelos, existen dos modelos principales de cómputo paralelo, la máquina de acceso aleatorio paralelo como una extensión de la RAM con memoria compartida entre unidades de procesamiento y la computadora paralela síncrona masiva que tiene en cuenta la comunicación y la sincronización . Ambos modelos tienen diferentes implicaciones para la complejidad del tiempo , por lo que se mostrarán dos algoritmos.
Algoritmo PRAM
Este algoritmo representa un método ampliamente extendido para manejar entradas donde es una potencia de dos. El procedimiento inverso se utiliza a menudo para los elementos de radiodifusión. [5] [6] [7]
- porahacer
- porahacer en paralelo
- Siestá activo entonces
- si pocodese establece entonces
- colocara inactivo
- si no
- si pocodese establece entonces
- Siestá activo entonces
- porahacer en paralelo
El operador binario para vectores se define por elementos de manera que . El algoritmo asume además que al principio para todos y es una potencia de dos y usa las unidades de procesamiento . En cada iteración, la mitad de las unidades de procesamiento se vuelven inactivas y no contribuyen a otros cálculos. La figura muestra una visualización del algoritmo utilizando la suma como operador. Las líneas verticales representan las unidades de procesamiento donde tiene lugar el cálculo de los elementos de esa línea. Los ocho elementos de entrada se encuentran en la parte inferior y cada paso de la animación corresponde a un paso paralelo en la ejecución del algoritmo. Un procesador activo evalúa el operador dado en el elemento actualmente está sosteniendo y dónde es el índice mínimo que cumple , así que eso se está convirtiendo en un procesador inactivo en el paso actual. y no son necesariamente elementos del conjunto de entrada ya que los campos se sobrescriben y reutilizan para expresiones evaluadas previamente. Para coordinar los roles de las unidades de procesamiento en cada paso sin causar comunicación adicional entre ellas, el hecho de que las unidades de procesamiento estén indexadas con números de a se utiliza. Cada procesador mira su-th bit menos significativo y decide si permanecer inactivo o calcular el operador en su propio elemento y el elemento con el índice donde el -th bit no está establecido. El patrón de comunicación subyacente del algoritmo es un árbol binomial, de ahí el nombre del algoritmo.
Solo contiene el resultado al final, por lo tanto, es el procesador raíz. Para una operación Allreduce, el resultado debe distribuirse, lo que se puede hacer agregando una transmisión de. Además, el númerode procesadores está restringido a una potencia de dos. Esto se puede elevar aumentando el número de procesadores a la siguiente potencia de dos. También hay algoritmos que se adaptan mejor a este caso de uso. [8]
Análisis de tiempo de ejecución
Se ejecuta el bucle principal veces, el tiempo necesario para que la pieza se realice en paralelo está en como unidad de procesamiento combina dos vectores o se vuelve inactivo. Así, el tiempo paralelo para el PRAM es . La estrategia para manejar los conflictos de lectura y escritura se puede elegir tan restrictiva como una lectura exclusiva y una escritura exclusiva (EREW). La aceleración del algoritmo es y por lo tanto la eficiencia es. La eficiencia se ve afectada por el hecho de que la mitad de las unidades de procesamiento activas se vuelven inactivas después de cada paso, por lo que las unidades están activas en el paso .
Algoritmo de memoria distribuida
A diferencia del algoritmo PRAM, en el modelo de memoria distribuida , la memoria no se comparte entre las unidades de procesamiento y los datos deben intercambiarse explícitamente entre las unidades de procesamiento. Por lo tanto, los datos deben intercambiarse explícitamente entre unidades, como se puede ver en el siguiente algoritmo.
- porahacer
- porahacer en paralelo
- Siestá activo entonces
- si pocodese establece entonces
- enviara
- colocara inactivo
- si no
- recibir
- si pocodese establece entonces
- Siestá activo entonces
- porahacer en paralelo
La única diferencia entre el algoritmo distribuido y la versión PRAM es la inclusión de primitivas de comunicación explícitas, el principio operativo permanece igual.
Análisis de tiempo de ejecución
La comunicación entre unidades genera algunos gastos generales. Un análisis simple para el algoritmo utiliza el modelo BSP e incorpora el tiempo necesario para iniciar la comunicación y el tiempo necesario para enviar un byte. Entonces el tiempo de ejecución resultante es, como los elementos de un vector se envían en cada iteración y tienen un tamaño en total.
Algoritmo de canalización
Para los modelos de memoria distribuida, puede tener sentido utilizar la comunicación canalizada. Este es especialmente el caso cuando es pequeño en comparación con . Por lo general, las canalizaciones lineales dividen datos o tareas en partes más pequeñas y las procesan en etapas. A diferencia de los algoritmos de árbol binomial, el algoritmo canalizado utiliza el hecho de que los vectores no son inseparables, pero el operador puede ser evaluado para elementos individuales: [9]
- porahacer
- porahacer en paralelo
- Si
- enviara
- Si
- recibirde
- Si
- porahacer en paralelo
Es importante tener en cuenta que las operaciones de envío y recepción deben ejecutarse simultáneamente para que funcione el algoritmo. El vector de resultado se almacena enal final. La animación asociada muestra una ejecución del algoritmo en vectores de tamaño cuatro con cinco unidades de procesamiento. Dos pasos de la animación visualizan un paso de ejecución paralelo.
Análisis de tiempo de ejecución
El número de pasos en la ejecución paralela es , se necesita pasos hasta que la última unidad de procesamiento reciba su primer elemento y adicional hasta que se reciban todos los elementos. Por lo tanto, el tiempo de ejecución en el modelo BSP es, asumiendo que es el tamaño de bytes total de un vector.
Aunque tiene un valor fijo, es posible agrupar lógicamente elementos de un vector juntos y reducir . Por ejemplo, una instancia de problema con vectores de tamaño cuatro se puede manejar dividiendo los vectores en los dos primeros y los dos últimos elementos, que siempre se transmiten y calculan juntos. En este caso, se envía el doble del volumen en cada paso, pero el número de pasos se ha reducido aproximadamente a la mitad. Significa que el parámetro se reduce a la mitad, mientras que el tamaño total de bytes Se mantiene igual. El tiempo de ejecución para este enfoque depende del valor de , que se puede optimizar si y son conocidos. Es óptimo para, asumiendo que esto da como resultado una menor que divide al original.
Aplicaciones
La reducción es una de las principales operaciones colectivas implementadas en la interfaz de paso de mensajes , donde el rendimiento del algoritmo utilizado es importante y se evalúa constantemente para diferentes casos de uso. [10] Los operadores se pueden utilizar como parámetros para MPI_Reduce
y MPI_Allreduce
, con la diferencia de que el resultado está disponible en una unidad de procesamiento (raíz) o en todas. MapReduce se basa en gran medida en algoritmos de reducción eficientes para procesar grandes conjuntos de datos, incluso en grandes clústeres. [11] [12]
Algunos algoritmos de clasificación en paralelo usan reducciones para poder manejar conjuntos de datos muy grandes. [13]
Ver también
Referencias
- ^ Cláusula de reducción
- ^ a b c Solihin
- ^ Chandra p. 59
- ^ Cole, Murray (2004). "Sacando esqueletos del armario: un manifiesto pragmático para la programación paralela esquelética" (PDF) . Computación paralela . 30 (3): 393. doi : 10.1016 / j.parco.2003.12.002 .
- ^ Bar-Noy, Amotz; Kipnis, Shlomo (1994). "Difusión de múltiples mensajes en sistemas de envío / recepción simultáneos". Matemáticas aplicadas discretas . 55 (2): 95–105. doi : 10.1016 / 0166-218x (94) 90001-9 .
- ^ Santos, Eunice E. (2002). "Algoritmos óptimos y eficientes para la suma y la suma de prefijos en máquinas paralelas". Revista de Computación Paralela y Distribuida . 62 (4): 517–543. doi : 10.1006 / jpdc.2000.1698 .
- ^ Slater, P .; Cockayne, E .; Hedetniemi, S. (1 de noviembre de 1981). "Difusión de información en árboles". Revista SIAM de Computación . 10 (4): 692–701. doi : 10.1137 / 0210052 . ISSN 0097-5397 .
- ^ Rabenseifner, Rolf; Träff, Jesper Larsson (19 de septiembre de 2004). Algoritmos de reducción más eficientes para procesadores sin potencia de dos en sistemas paralelos de paso de mensajes . Avances recientes en máquinas virtuales paralelas e interfaz de paso de mensajes . Apuntes de conferencias en Ciencias de la Computación. 3241 . Springer, Berlín, Heidelberg. págs. 36–46. doi : 10.1007 / 978-3-540-30218-6_13 . ISBN 9783540231639.
- ^ Bar-Noy, A .; Kipnis, S. (1 de septiembre de 1994). "Diseño de algoritmos de difusión en el modelo postal para sistemas de paso de mensajes". Teoría de sistemas matemáticos . 27 (5): 431–452. CiteSeerX 10.1.1.54.2543 . doi : 10.1007 / BF01184933 . ISSN 0025-5661 . S2CID 42798826 .
- ^ Pješivac-Grbović, Jelena; Angskun, Thara; Bosilca, George; Fagg, Graham E .; Gabriel, Edgar; Dongarra, Jack J. (1 de junio de 2007). "Análisis de desempeño de operaciones colectivas MPI". Computación en clúster . 10 (2): 127–143. doi : 10.1007 / s10586-007-0012-0 . ISSN 1386-7857 . S2CID 2142998 .
- ^ Lämmel, Ralf (2008). "Modelo de programación MapReduce de Google - Revisado". Ciencia de la Programación de Computadores . 70 (1): 1–30. doi : 10.1016 / j.scico.2007.07.001 .
- ^ Senger, Hermes; Gil-Costa, Verónica; Arantes, Luciana; Marcondes, Cesar AC; Marín, Mauricio; Sato, Liria M .; da Silva, Fabrício AB (10 de junio de 2016). "Análisis de coste y escalabilidad BSP para operaciones de MapReduce". Concurrencia y Computación: Práctica y Experiencia . 28 (8): 2503–2527. doi : 10.1002 / cpe.3628 . hdl : 10533/147670 . ISSN 1532-0634 .
- ^ Axtmann, Michael; Bingmann, Timo; Sanders, Peter; Schulz, Christian (24 de octubre de 2014). "Práctica clasificación masiva paralela". arXiv : 1410,6754 [ cs.DS ].
Libros
- Chandra, Rohit (2001). Programación paralela en OpenMP . Morgan Kaufmann. págs. 59 –77. ISBN 1558606718.
- Solihin, Yan (2016). Fundamentos de la arquitectura multinúcleo paralela . Prensa CRC. pag. 75. ISBN 978-1-4822-1118-4.
enlaces externos
- Cláusula de reducción , referencia a la cláusula de reducción