Operador de reducción

En informática , el operador de reducción ^{[ 1 ]} es un tipo de operador que se usa comúnmente en programación paralela para reducir los elementos de un arreglo a 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 modelos de programación como MapReduce , donde se aplica ( mapea ) un operador de reducción a todos los elementos antes de reducirlos. Otros algoritmos paralelos usan operadores de reducción como operaciones primarias para resolver problemas más complejos. Muchos operadores de reducción se pueden usar para difusión para distribuir datos a todos los procesadores.

Teoría

Un operador de reducción permite dividir una tarea en varias subtareas calculando resultados parciales que se utilizan para obtener un resultado final. Permite ejecutar ciertas operaciones en serie en paralelo y reducir el número de pasos necesarios para dichas operaciones. El operador de reducción almacena el resultado de las subtareas en una copia privada de la variable. Estas copias privadas se combinan posteriormente en una copia compartida.

Un operador es un operador de reducción si:

Puede reducir una matriz a un único valor escalar. ^{[ 2 ]}
El resultado final debería poder obtenerse a partir de los resultados de las tareas parciales que se crearon. ^{[ 2 ]}

Estos dos requisitos se cumplen para los operadores conmutativos y asociativos que se aplican a todos los elementos de la matriz.

Algunos operadores que cumplen estos requisitos son la suma, la multiplicación y algunos operadores lógicos (y, o, etc.).

Un operador de reducción $\oplus$ puede aplicarse en tiempo constante a un conjunto de entrada $V=\left\{v_{0}={\begin{pmatrix}e_{0}^{0}\\\vdots \\e_{0}^{m-1}\end{pmatrix}},v_{1}={\begin{pmatrix}e_{1}^{0}\\\vdots \\e_{1}^{m-1}\end{pmatrix}},\dots ,v_{p-1}={\begin{pmatrix}e_{p-1}^{0}\\\vdots \\e_{p-1}^{m-1}\end{pmatrix}}\right\}$ de $p$ vectores con $m$ cada uno de los elementos. El resultado $r$ de la operación es la combinación de los elementos $r={\begin{pmatrix}e_{0}^{0}\oplus e_{1}^{0}\oplus \dots \oplus e_{p-1}^{0}\\\vdots \\e_{0}^{m-1}\oplus e_{1}^{m-1}\oplus \dots \oplus e_{p-1}^{m-1}\end{pmatrix}}={\begin{pmatrix}\bigoplus _{i=0}^{p-1}e_{i}^{0}\\\vdots \\\bigoplus _{i=0}^{p-1}e_{i}^{m-1}\end{pmatrix}}$ y debe almacenarse en un procesador raíz especificado al final de la ejecución. Si el resultado $r$ Debe estar disponible en cada procesador después de que el cálculo haya terminado; a menudo se le llama Allreduce. Un algoritmo secuencial óptimo de tiempo lineal para la reducción puede aplicar el operador sucesivamente de adelante hacia atrás, reemplazando siempre dos vectores con el resultado de la operación aplicada a todos sus elementos, creando así una instancia que tiene un vector menos. Necesita $(p-1)\cdot m$ pasos hasta que solo $r$ queda. Los algoritmos secuenciales no pueden tener un rendimiento mejor que el tiempo lineal, pero los algoritmos paralelos dejan cierto margen para optimizar.

Ejemplo

Supongamos que tenemos un array $[2,3,5,1,7,6,8,4]$ La suma de este arreglo se puede calcular en serie reduciendo secuencialmente el arreglo a una sola suma mediante el operador '+'. Comenzando la suma desde el principio del arreglo se obtiene: ${\Bigg (}{\bigg (}{\Big (}{\big (}\,(\,(2+3)+5)+1{\big )}+7{\Big )}+6{\bigg )}+8{\Bigg )}+4=36.$ Dado que '+' es conmutativo y 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 del array y el operador de reducción combina los resultados. Utilizando una reducción de árbol binario, se podrían utilizar 4 núcleos para calcular ${\textstyle (2+3)}$ , ${\textstyle (5+1)}$ , ${\textstyle (7+6)}$ , y ${\textstyle (8+4)}$ Entonces dos núcleos pueden calcular $(5+6)$ y $(13+12)$ y, por último, un solo núcleo de computación $(11+25)=36$ . Por lo tanto, se pueden usar un total de 4 núcleos para calcular la suma en ${\textstyle \log _{2}8=3}$ pasos en lugar de la $7$ pasos necesarios para la versión serial. Esta técnica de árbol binario paralelo calcula ${\textstyle {\big (}\,(2+3)+(5+1)\,{\big )}+{\big (}\,(7+6)+(8+4)\,{\big )}}$ Por supuesto, el resultado es el mismo, pero solo debido a la asociatividad del operador de reducción. La conmutatividad del operador de reducción sería importante si existiera un núcleo maestro que distribuyera el trabajo a varios procesadores, ya que en ese caso los resultados podrían regresar al procesador maestro en cualquier orden. La propiedad de conmutatividad garantiza que el resultado será el mismo.

IEEE 754-2019 define 4 tipos de reducciones de suma y 3 tipos de reducciones de producto escalado. Dado que las operaciones son operadores de reducción, la norma especifica que "las implementaciones pueden asociarse en cualquier orden o evaluarse en cualquier formato más amplio". ^{[ 5 ]}

Ninguno de los ejemplos

La multiplicación de matrices no es un operador de reducción, ya que no es conmutativa. Si se permitiera a los procesos devolver los resultados de la multiplicación de matrices al proceso maestro en cualquier orden, el resultado final que este calculara probablemente sería incorrecto si los resultados llegaran desordenados. Sin embargo, cabe destacar que la multiplicación de matrices es asociativa y, por lo tanto, el resultado sería correcto siempre que se respetara el orden adecuado, como en la técnica de reducción mediante árboles binarios.

Algoritmos

Algoritmos de árbol binomial

En cuanto a los algoritmos paralelos, existen dos modelos principales de computación paralela: la máquina de acceso aleatorio paralelo (PRAM), una extensión de la RAM con memoria compartida entre unidades de procesamiento, y la computadora paralela síncrona masiva , que considera la comunicación y la sincronización . Ambos modelos tienen implicaciones diferentes en la complejidad temporal ; por lo tanto, se mostrarán dos algoritmos.

algoritmo PRAM

Este algoritmo representa un método ampliamente extendido para manejar entradas donde $p$ es una potencia de dos. El procedimiento inverso se usa a menudo para elementos de difusión. ^{[ 6 ]}^{[ 7 ]}^{[ 8 ]}

para

k\gets 0

a

\lceil \log _{2}p\rceil -1

hacer

para

i\gets 0

a

p-1

hacerlo en paralelo

si

p_{i}

entonces está activo

si bit

k

de

i

entonces está establecido

colocar

p_{i}

inactivo

de lo contrario si

i+2^{k}<p

x_{i}\gets x_{i}\oplus ^{\star }x_{i+2^{k}}

El operador binario para vectores se define elemento a elemento de tal manera que ${\begin{pmatrix}e_{i}^{0}\\\vdots \\e_{i}^{m-1}\end{pmatrix}}\oplus ^{\star }{\begin{pmatrix}e_{j}^{0}\\\vdots \\e_{j}^{m-1}\end{pmatrix}}={\begin{pmatrix}e_{i}^{0}\oplus e_{j}^{0}\\\vdots \\e_{i}^{m-1}\oplus e_{j}^{m-1}\end{pmatrix}}.$

El algoritmo asume además que al principio $x_{i}=v_{i}$ a pesar de $i$ y $p$ es una potencia de dos y utiliza las unidades de procesamiento $p_{0},p_{1},\dots p_{n-1}$ En cada iteración, la mitad de las unidades de procesamiento se vuelven inactivas y no contribuyen a los cálculos posteriores. La figura muestra una visualización del algoritmo utilizando la suma como operador. Las líneas verticales representan las unidades de procesamiento donde se realiza 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 $p_{i}$ evalúa el operador dado en el elemento $x_{i}$ Actualmente se mantiene y $x_{j}$ dónde $j$ es el índice mínimo que cumple $j>i$ , de modo que $p_{j}$ se está convirtiendo en un procesador inactivo en el paso actual. $x_{i}$ y $x_{j}$ no son necesariamente elementos del conjunto de entrada $X$ ya que los campos se sobrescriben y se reutilizan para expresiones evaluadas previamente. Para coordinar las funciones 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 $0$ a $p-1$ se utiliza. Cada procesador mira su $k$ -ésimo bit menos significativo y decide si se vuelve inactivo o calcula el operador en su propio elemento y el elemento con el índice donde el $k$ El bit -ésimo no está activado. El patrón de comunicación subyacente del algoritmo es un árbol binomial, de ahí el nombre del algoritmo.

Solo $p_{0}$ al final contiene el resultado, por lo tanto es el procesador raíz. Para una operación Allreduce el resultado debe distribuirse, lo que se puede hacer agregando una difusión desde $p_{0}$ . Además, el número $p$ El número de procesadores está restringido a ser una potencia de dos. Esto se puede solucionar aumentando el número de procesadores a la siguiente potencia de dos. También existen algoritmos más específicos para este caso de uso. ^{[ 9 ]}

Análisis del tiempo de ejecución

Se ejecuta el bucle principal $\lceil \log _{2}p\rceil$ veces, el tiempo necesario para la parte realizada en paralelo es en ${\mathcal {O}}(m)$ como unidad de procesamiento, combina dos vectores o se vuelve inactiva. Por lo tanto, el tiempo paralelo $T(p,m)$ para el PRAM es $T(p,m)={\mathcal {O}}(\log(p)\cdot m)$ La estrategia para manejar conflictos de lectura y escritura puede elegirse tan restrictiva como lectura exclusiva y escritura exclusiva (EREW). La aceleración $S(p,m)$ del algoritmo es ${\textstyle S(p,m)\in {\mathcal {O}}\left({\frac {T_{\text{seq}}}{T(p,m)}}\right)={\mathcal {O}}\left({\frac {p}{\log(p)}}\right)}$ y por lo tanto la eficiencia es ${\textstyle E(p,m)\in {\mathcal {O}}\left({\frac {S(p,m)}{p}}\right)={\mathcal {O}}\left({\frac {1}{\log(p)}}\right)}$ La eficiencia se ve afectada porque la mitad de las unidades de procesamiento activas se vuelven inactivas después de cada paso, por lo que ${\frac {p}{2^{i}}}$ Las unidades están activas en el paso $i$ .

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 ellas. Por lo tanto, los datos deben intercambiarse explícitamente entre las unidades, como se puede observar en el siguiente algoritmo.

para

k\gets 0

a

\lceil \log _{2}p\rceil -1

hacer

para

i\gets 0

a

p-1

hacerlo en paralelo

si

p_{i}

entonces está activo

si bit

k

de

i

entonces está establecido

enviar

x_{i}

a

p_{i-2^{k}}

colocar

p_{k}

inactivo

de lo contrario si

i+2^{k}<p

recibir

x_{i+2^{k}}

x_{i}\gets x_{i}\oplus ^{\star }x_{i+2^{k}}

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 de funcionamiento sigue siendo el mismo.

Análisis del tiempo de ejecución

La comunicación entre unidades genera cierta sobrecarga. Un análisis simple para el algoritmo utiliza el modelo BSP e incorpora el tiempo. $T_{\text{start}}$ era necesario iniciar la comunicación y $T_{\text{byte}}$ el tiempo necesario para enviar un byte. Entonces, el tiempo de ejecución resultante es $\Theta ((T_{\text{start}}+n\cdot T_{\text{byte}})\cdot log(p))$ , como $m$ Los elementos de un vector se envían en cada iteración y tienen tamaño $n$ en total.

Algoritmo de canalización

Para los modelos de memoria distribuida, puede tener sentido utilizar la comunicación en paralelo. Esto es especialmente cierto cuando $T_{\text{start}}$ es pequeño en comparación con $T_{\text{byte}}$ Por lo general, las tuberías lineales dividen los datos o las tareas en partes más pequeñas y las procesan en etapas. A diferencia de los algoritmos de árbol binomial, el algoritmo en tubería utiliza el hecho de que los vectores no son inseparables, pero el operador puede evaluarse para elementos individuales: ^{[ 10 ]}

para

k\gets 0

a

p+m-3

hacer

para

i\gets 0

a

p-1

hacerlo en paralelo

si

i\leq k<i+m\land i\neq p-1

enviar

x_{i}^{k-i}

a

p_{i+1}

si

i-1\leq k<i-1+m\land i\neq 0

recibir

x_{i-1}^{k+i-1}

de

p_{i-1}

x_{i}^{k+i-1}\gets x_{i}^{k+i-1}\oplus x_{i-1}^{k+i-1}

Es importante tener en cuenta que las operaciones de envío y recepción deben ejecutarse simultáneamente para que el algoritmo funcione. El vector de resultados se almacena en $p_{p-1}$ Al final, la animación correspondiente muestra la 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 en paralelo.

Análisis del tiempo de ejecución

El número de pasos en la ejecución paralela es $p+m-2$ , se necesita $p-1$ pasos hasta que la última unidad de procesamiento recibe su primer elemento y adicional $m-1$ hasta que se reciban todos los elementos. Por lo tanto, el tiempo de ejecución en el modelo BSP es ${\textstyle T(n,p,m)=\left(T_{\text{start}}+{\frac {n}{m}}\cdot T_{\text{byte}}\right)(p+m-2)}$ , suponiendo que $n$ es el tamaño total en bytes de un vector.

A pesar de $m$ tiene un valor fijo, es posible agrupar lógicamente los elementos de un vector y reducirlos. $m$ 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 de volumen en cada paso, pero el número de pasos se ha reducido aproximadamente a la mitad. Esto significa que el parámetro $m$ se reduce a la mitad, mientras que el tamaño total en bytes $n$ permanece igual. El tiempo de ejecución $T(p)$ para este enfoque depende del valor de $m$ , que se puede optimizar si $T_{\text{start}}$ y ${\textstyle T_{\text{byte}}}$ son conocidos. Es óptimo para ${\textstyle m={\sqrt {\frac {n\cdot (p-2)\cdot T_{\text{byte}}}{T_{\text{start}}}}}}$ , suponiendo que esto resulte en un valor menor $m$ 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. ^{[ 11 ]} Los operadores pueden usarse como parámetros para MPI_Reducey MPI_Allreduce, con la diferencia de que el resultado está disponible en una (raíz) unidad de procesamiento o en todas ellas.

OpenMP ofrece una cláusula de reducción para describir cómo se recopilan los resultados de las operaciones paralelas. ^{[ 12 ]}

MapReduce depende en gran medida de algoritmos de reducción eficientes para procesar grandes conjuntos de datos, incluso en clústeres enormes. ^{[ 13 ]}^{[ 14 ]}

Algunos algoritmos de ordenación paralela utilizan reducciones para poder manejar conjuntos de datos muy grandes. ^{[ 15 ]}

Véase también

Referencias

↑ "Cláusula de reducción" . www.dartmouth.edu . Dartmouth College. 23 de marzo de 2009. Consultado el 26 de septiembre de 2016 .
1 2 3 Solihin, Yan (2016). Fundamentos de la arquitectura multinúcleo paralela . CRC Press. pág. 75. ISBN 978-1-4822-1118-4.
↑ Chandra, Rohit (2001). Programación paralela en OpenMP . Morgan Kaufmann. págs. 59–77 . ISBN 1558606718.
↑ 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 . hdl : 20.500.11820/8eb79d42-de83-4cfb-9faa-30d9ac3b3839 .
↑ IEEE Computer Society (22 de julio de 2019). "9.4 Operaciones de reducción". Norma IEEE para aritmética de punto flotante . IEEE STD 754-2019. IEEE. págs. 1–84 . doi : 10.1109/IEEESTD.2019.8766229 . ISBN 978-1-5044-5924-2Norma IEEE 754-2019.
↑ Bar-Noy, Amotz; Kipnis, Shlomo (1994). "Difusión de múltiples mensajes en sistemas simultáneos de envío/recepción". 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". Journal of Parallel and Distributed Computing . 62 (4): 517– 543. doi : 10.1006/jpdc.2000.1698 .
↑ Slater, P.; Cockayne, E.; Hedetniemi, S. (1981-11-01). "Diseminación de información en árboles". SIAM Journal on Computing . 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 un número de procesadores que no es potencia de dos en sistemas paralelos de paso de mensajes». Avances recientes en máquinas virtuales paralelas e interfaces de paso de mensajes . Lecture Notes in Computer Science. Vol. 3241. Springer, Berlín, Heidelberg. pp. 36–46 . doi : 10.1007/978-3-540-30218-6_13 . ISBN 9783540231639.
↑ Bar-Noy, A.; Kipnis, S. (1994-09-01). "Diseño de algoritmos de difusión en el modelo postal para sistemas de paso de mensajes". Mathematical Systems Theory . 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. (2007-06-01). "Análisis de rendimiento de operaciones colectivas MPI". Cluster Computing . 10 (2): 127– 143. CiteSeerX 10.1.1.80.3867 . doi : 10.1007/s10586-007-0012-0 . ISSN 1386-7857 . S2CID 2142998 .
↑ "10.9. Reducción — Ejemplos de interfaz de programación de aplicaciones OpenMP" . passlab.github.io .
↑ Lämmel, Ralf (2008). "El modelo de programación MapReduce de Google: una revisión". Science of Computer Programming . 70 (1): 1– 30. doi : 10.1016/j.scico.2007.07.001 .
↑ Senger, Hermes; Gil-Costa, Veronica; Arantes, Luciana; Marcondes, Cesar AC; Marín, Mauricio; Sato, Liria M.; da Silva, Fabrício AB (2016-06-10). "Análisis de costos y escalabilidad de BSP para operaciones MapReduce". Concurrency and Computation: Practice and Experience . 28 (8): 2503– 2527. doi : 10.1002/cpe.3628 . hdl : 10533/147670 . ISSN 1532-0634 . S2CID 33645927 .
↑ Axtmann, Michael; Bingmann, Timo; Sanders, Peter; Schulz, Christian (24-10-2014). "Clasificación masivamente paralela práctica". arXiv : 1410.6754 [ cs.DS ].

[1] "Cláusula de reducción" . www.dartmouth.edu . Dartmouth College. 23 de marzo de 2009. Consultado el 26 de septiembre de 2016 .

[:1-2] 1 2 3 Solihin, Yan (2016). Fundamentos de la arquitectura multinúcleo paralela . CRC Press. pág. 75. ISBN 978-1-4822-1118-4.

[:0-3] Chandra, Rohit (2001). Programación paralela en OpenMP . Morgan Kaufmann. págs. 59–77 . ISBN 1558606718.

[4] 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 . hdl : 20.500.11820/8eb79d42-de83-4cfb-9faa-30d9ac3b3839 .

[5] IEEE Computer Society (22 de julio de 2019). "9.4 Operaciones de reducción". Norma IEEE para aritmética de punto flotante . IEEE STD 754-2019. IEEE. págs. 1–84 . doi : 10.1109/IEEESTD.2019.8766229 . ISBN 978-1-5044-5924-2Norma IEEE 754-2019.

[6] Bar-Noy, Amotz; Kipnis, Shlomo (1994). "Difusión de múltiples mensajes en sistemas simultáneos de envío/recepción". Matemáticas Aplicadas Discretas . 55 (2): 95– 105. doi : 10.1016/0166-218x(94)90001-9 .

[7] Santos, Eunice E. (2002). "Algoritmos óptimos y eficientes para la suma y la suma de prefijos en máquinas paralelas". Journal of Parallel and Distributed Computing . 62 (4): 517– 543. doi : 10.1006/jpdc.2000.1698 .

[8] Slater, P.; Cockayne, E.; Hedetniemi, S. (1981-11-01). "Diseminación de información en árboles". SIAM Journal on Computing . 10 (4): 692– 701. doi : 10.1137/0210052 . ISSN 0097-5397 .

[9] Rabenseifner, Rolf; Träff, Jesper Larsson (19 de septiembre de 2004). «Algoritmos de reducción más eficientes para un número de procesadores que no es potencia de dos en sistemas paralelos de paso de mensajes». Avances recientes en máquinas virtuales paralelas e interfaces de paso de mensajes . Lecture Notes in Computer Science. Vol. 3241. Springer, Berlín, Heidelberg. pp. 36–46 . doi : 10.1007/978-3-540-30218-6_13 . ISBN 9783540231639.

[10] Bar-Noy, A.; Kipnis, S. (1994-09-01). "Diseño de algoritmos de difusión en el modelo postal para sistemas de paso de mensajes". Mathematical Systems Theory . 27 (5): 431– 452. CiteSeerX 10.1.1.54.2543 . doi : 10.1007/BF01184933 . ISSN 0025-5661 . S2CID 42798826 .

[11] Pješivac-Grbović, Jelena; Angskun, Thara; Bosilca, George; Fagg, Graham E.; Gabriel, Edgar; Dongarra, Jack J. (2007-06-01). "Análisis de rendimiento de operaciones colectivas MPI". Cluster Computing . 10 (2): 127– 143. CiteSeerX 10.1.1.80.3867 . doi : 10.1007/s10586-007-0012-0 . ISSN 1386-7857 . S2CID 2142998 .

[12] "10.9. Reducción — Ejemplos de interfaz de programación de aplicaciones OpenMP" . passlab.github.io .

[13] Lämmel, Ralf (2008). "El modelo de programación MapReduce de Google: una revisión". Science of Computer Programming . 70 (1): 1– 30. doi : 10.1016/j.scico.2007.07.001 .

[14] Senger, Hermes; Gil-Costa, Veronica; Arantes, Luciana; Marcondes, Cesar AC; Marín, Mauricio; Sato, Liria M.; da Silva, Fabrício AB (2016-06-10). "Análisis de costos y escalabilidad de BSP para operaciones MapReduce". Concurrency and Computation: Practice and Experience . 28 (8): 2503– 2527. doi : 10.1002/cpe.3628 . hdl : 10533/147670 . ISSN 1532-0634 . S2CID 33645927 .

[15] Axtmann, Michael; Bingmann, Timo; Sanders, Peter; Schulz, Christian (24-10-2014). "Clasificación masivamente paralela práctica". arXiv : 1410.6754 [ cs.DS ].

[ 1 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

Teoría

Ejemplo

Ninguno de los ejemplos

Algoritmos

Algoritmos de árbol binomial

algoritmo PRAM

Análisis del tiempo de ejecución

Algoritmo de memoria distribuida

Análisis del tiempo de ejecución

Algoritmo de canalización

Análisis del tiempo de ejecución

Aplicaciones

Véase también

Referencias

Articulos relacionados