Cantidad de prefijo

En informática , una suma de prefijos, una suma acumulada, un escaneo inclusivo o simplemente un escaneo de una secuencia de números x0, x1, x2, ... es una secuencia de números y0, y1, y2, ..., que es un prefijo suma de la secuencia de entrada:

y0 = x0 _ _ y 1 = x 0 + x 1 y 2 \ u003d x 0 + x 1 + x 2 …

Por ejemplo, las sumas de prefijos de números naturales son números triangulares :

números de entrada	una	2	3	cuatro	5	6	…
prefijo suma	una	3	6	diez	quince	21	…

Las sumas de prefijos son triviales de calcular en modelos de cálculo secuencial, aplicando la fórmula y i = y i − 1 + x i para calcular cada valor de salida en orden secuencial. Sin embargo, a pesar de ser computacionalmente simples, las sumas de prefijos son una primitiva útil en algunos algoritmos como el tipo de conteo , [1] [2] y forman la base de la función de escaneo de orden superior en los lenguajes de programación funcional . Las sumas de prefijos también se han estudiado ampliamente en algoritmos paralelos , tanto como un problema de prueba para resolver como una primitiva útil para usar como subrutina en otros algoritmos paralelos. [3] [4] [5]

Teóricamente, la suma del prefijo requiere solo el operador asociativo binario ⊕ , lo que lo hace útil en muchos algoritmos, desde el cálculo de descomposiciones de puntos por pares bien separados hasta el procesamiento de cadenas. [6] [7]

Matemáticamente, la operación de tomar sumas de prefijos se puede generalizar de secuencias finitas a infinitas; en este sentido, el prefijo suma se conoce como suma parcial de la serie . La suma de prefijos o la suma parcial forma un mapeo lineal en espacios vectoriales de secuencias finitas o infinitas; sus operadores inversos son diferencias finitas.

Escaneo de una función de orden superior

En términos de programación funcional , la suma del prefijo se puede generalizar a cualquier operación binaria (no solo a la operación de suma ); la función de orden superior resultante de esta generalización se llama barrido y está estrechamente relacionada con la operación de convolución . Tanto las operaciones de exploración como las de comparación aplican una operación binaria dada a la misma secuencia de valores, pero se diferencian en que la exploración devuelve la secuencia completa de resultados de la operación binaria, mientras que el pliegue devuelve solo el resultado final. Por ejemplo, se puede generar una secuencia de números factoriales escaneando números naturales mediante la multiplicación en lugar de la suma:

números de entrada	una	2	3	cuatro	5	6	…
valores de prefijo	una	2	6	24	120	720	…

Escaneos inclusivos y exclusivos

Las implementaciones de escaneo de lenguaje y biblioteca pueden ser inclusivas o exclusivas . Un escaneo inclusivo incluye la entrada x i al calcular la salida y i ( ), mientras que un escaneo exclusivo no la incluye ( ). En el último caso, las implementaciones dejan y 0 sin definir o aceptan un valor especial " x -1 " con el que comenzar a escanear. Los escaneos exclusivos son más generales en el sentido de que un escaneo inclusivo siempre se puede implementar en términos de un escaneo exclusivo (combinando posteriormente x i con y i ), pero un escaneo exclusivo no siempre se puede implementar en términos de un escaneo inclusivo, como en el caso de la suma máxima del prefijo. ${\displaystyle y_{i}=\bigoplus _{j=0}^{i}x_{j))$ ${\displaystyle y_{i}=\bigoplus _{j=0}^{i-1}x_{j))$

La siguiente tabla enumera ejemplos de funciones de escaneo inclusivas y exclusivas proporcionadas por varios lenguajes de programación y bibliotecas:

Idiomas/bibliotecas	Escaneo inclusivo	Escaneo exclusivo
Haskell	scanl1	scanl
IPM	MPI_Scan	MPI_Exscan
C++	std::inclusive_scan	std::exclusive_scan
Scala	scan
Óxido	scan Archivado el 6 de junio de 2021 en Wayback Machine .

Algoritmos paralelos

Hay dos algoritmos clave para calcular la suma de prefijos en paralelo. El primer método implica menos profundidad y una mayor propensión a la paralelización , pero este método no es lo suficientemente eficiente. La segunda opción es más eficiente, pero requiere el doble de profundidad y ofrece menos opciones de paralelización. Ambos algoritmos se presentan a continuación.

Algoritmo 1: menos profundidad, más propenso a la paralelización

Hillis y Steele presentan el siguiente algoritmo de suma de prefijos paralelos: [8]

para hacer _

obtengo 0

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

para hacer en paralelo

j\obtiene 0

n-1

si entonces

{\ estilo de visualización j<2^{i))

{\displaystyle x_{j}^{i+1}\obtiene x_{j}^{i))

más

x_{j}^{i+1}\obtiene x_{j}^{i}+x_{j-2^{i}}^{i}

La notación significa el valor del j -ésimo elemento de la matriz x en el paso i . ${\ Displaystyle x_ {j}^{i}}$

Dados n procesadores para completar cada iteración del ciclo interno en tiempo constante, el algoritmo se ejecuta en tiempo O (log n ) .

Algoritmo 2: eficiente

Un algoritmo eficiente de cálculo de suma de prefijos paralelos se puede implementar de la siguiente manera: [3] [9] [10]

Calcule las sumas de pares consecutivos de elementos en los que el primer elemento del par tiene un índice par: z 0 \ u003d x 0 + x 1 , z 1 \ u003d x 2 + x 3 , etc.
Calcule recursivamente la suma de prefijos w 0 , w 1 , w 2 , ... , de la secuencia z 0 , z 1 , z 2 , ...
Exprese cada miembro de la sucesión y 0 , y 1 , y 2 , ... como la suma de hasta dos miembros de estas sucesiones intermedias: y 0 = x 0 , y 1 = z 0 , y 2 = z 0 + x 2 , y 3 = w 0 , etc. Cada valor de y i , excepto el primero, se calcula copiando desde una posición la mitad de la secuencia w , o sumando el valor de la secuencia x al valor anterior de y-1 yo .

Si la secuencia de entrada tiene un tamaño n , entonces la recurrencia continúa hasta una profundidad de O (log n ) , que también está limitada por el tiempo de ejecución en paralelo de este algoritmo. El número de operaciones de algoritmo es O ( n ) y se pueden implementar en una computadora de memoria compartida paralela abstracta (PRAM) con procesadores O ( n /log n ) sin ninguna desaceleración asintótica mediante la asignación de múltiples índices a cada procesador en variantes de algoritmo, para los que tienen más elementos que procesadores. [3]

Comparación de algoritmos

Cada uno de los algoritmos anteriores se ejecuta en O (log n ) . Sin embargo, el primero toma exactamente log 2 n pasos, mientras que el segundo requiere 2 log 2 n − 2 pasos. Para los ejemplos de 16 entradas que se muestran, el algoritmo 1 es 12 en paralelo (49 unidades de trabajo divididas por 4), mientras que el algoritmo 2 es solo 4 en paralelo (26 unidades de trabajo divididas por 6). Sin embargo, el Algoritmo 2 es eficiente en el trabajo, solo realiza un factor constante (2) de la cantidad de trabajo requerido por el algoritmo secuencial y el Algoritmo 1 es ineficiente, realiza asintóticamente más trabajo (un factor logarítmico) que el requerido secuencialmente. Por lo tanto, el algoritmo 1 es preferible cuando es posible un gran número de procesos paralelos; de lo contrario, el algoritmo 2 tiene prioridad.

Los algoritmos paralelos para sumas de prefijos a menudo se pueden generalizar a otras operaciones de exploración binaria asociativa, [3] [4] , y también se pueden calcular de manera eficiente en hardware paralelo moderno como la GPU (Unidad de procesamiento de gráficos). [11] La idea de crear un bloque funcional en hardware diseñado para calcular una suma de prefijos de parámetros múltiples fue patentada por Uzi Vishkin . [12]

Muchas implementaciones simultáneas utilizan un procedimiento de dos etapas en el que la suma del prefijo parcial se calcula en la primera etapa para cada bloque de procesamiento; la suma del prefijo de estas sumas parciales luego se calcula y retroalimenta a las unidades de procesamiento para el segundo paso, utilizando el prefijo ahora conocido como el valor inicial. Asintóticamente, este método toma aproximadamente dos lecturas y una escritura para cada elemento.

Implementaciones de algoritmos para calcular sumas de prefijos

La implementación del algoritmo de cálculo paralelo de suma de prefijos, al igual que otros algoritmos paralelos, debe tener en cuenta la arquitectura de paralelización de la plataforma . Hay muchos algoritmos que se adaptan a las plataformas de memoria compartida , así como algoritmos que se adaptan bien a las plataformas de memoria distribuida , mientras usan la mensajería como la única forma de comunicación entre procesos.

Memoria compartida: Algoritmo de dos niveles

El siguiente algoritmo asume un modelo de máquina de memoria compartida ; todos los elementos de procesamiento PE (del inglés Processing Elements) tienen acceso a la misma memoria. Una variante de este algoritmo se implementa en la biblioteca de plantillas estándar multinúcleo (MCSTL) [13] [14] , una implementación paralela de la biblioteca de plantillas estándar de C++ que proporciona versiones adaptadas para la computación paralela de varios algoritmos.

Para calcular simultáneamente la suma de prefijos de elementos de datos con elementos de procesamiento, los datos se dividen en bloques, cada uno de los cuales contiene elementos (por simplicidad, supondremos que es divisible por ). Tenga en cuenta que aunque el algoritmo divide los datos en bloques, solo los elementos de procesamiento funcionan en paralelo. $norte$ $pags$ $p+1$ ${\frac{n}{p+1}}$ $norte$ $p+1$ $p+1$ $pags$

En el primer bucle, cada PE calcula una suma de prefijos locales para su bloque. No es necesario calcular el último bloque, ya que estas sumas de prefijos solo se calculan como compensaciones de las sumas de prefijos de los bloques posteriores y, por definición, el último bloque no es adecuado.

Los desplazamientos que se almacenan en la última posición de cada bloque se acumulan en su propia suma de prefijos y se almacenan en posiciones posteriores. Si es pequeño, entonces el algoritmo secuencial se ejecuta lo suficientemente rápido; para los grandes, este paso se puede realizar en paralelo. $pags$ $pags$ $pags$

Ahora pasemos al segundo ciclo. Esta vez, no es necesario procesar el primer bloque, ya que no es necesario tener en cuenta el desplazamiento del bloque anterior. Sin embargo, ahora se incluye el último bloque y las sumas de prefijos para cada bloque se calculan utilizando las compensaciones de los bloques de suma de prefijos calculados en el ciclo anterior.

function prefix_sum ( elementos ) { n := tamaño ( elementos ) p := número de elementos de procesamiento prefix_sum := [ 0. . .0 ] de tamaño n do paralelo i = 0 a p - 1 { // i := índice del PE actual de j = i * n / ( p + 1 ) a ( i + 1 ) * n / ( p + 1 ) - 1 do { // La suma de prefijos de los bloques locales se almacena aquí store_prefix_sum_with_offset_in ( elements , 0 , prefix_sum ) } } x = 0 for i = 1 to p { x += prefix_sum [ i * n / ( p + 1 ) - 1 ] // Construyendo una suma de prefijos sobre los primeros p bloques prefix_sum [ i * n / ( p + 1 )] = x / / Guardando resultados para usar como compensaciones en el segundo ciclo } do paralelo i = 1 a p { // i := índice del PE actual de j = i * n / ( p + 1 ) a ( i + 1 ) * n / ( p + 1 ) - 1 do { offset : = prefix_sum [ i * n / ( p + 1 )] // Calcula la suma del prefijo como el desplazamiento de la suma de los bloques anteriores store_prefix_sum_with_offset_in ( elements , offset , prefix_sum ) } } devolver prefix_sum } Memoria Distribuida: El Algoritmo Hipercubo

El algoritmo de suma de prefijos de hipercubo [15] está bien adaptado para plataformas de memoria distribuida y utiliza el intercambio de mensajes entre elementos de procesamiento. Se supone que el algoritmo involucra PE igual al número de esquinas en el hipercubo bidimensional . ${\ estilo de visualización p = 2 ^ {d}}$ $d$

A lo largo del algoritmo, cada PE se trata como una esquina en un hipotético hipercubo con conocimiento del prefijo común sum , así como del prefijo sum de todos los elementos hasta sí mismo (según los índices ordenados entre los PE), cada uno en su propio hipercubo. $\sigma$ $X$

El algoritmo parte de la suposición de que cada PE es la única esquina de un hipercubo de dimensión cero y, por tanto, son iguales a la suma del prefijo local de sus propios elementos. $\sigma$ $X$
El algoritmo continúa fusionando hipercubos adyacentes en una dimensión. Durante cada fusión, se intercambia y se suma entre los dos hipercubos, lo que conserva la invariante de que todos los PE en las esquinas de este nuevo hipercubo almacenan el prefijo común suma del hipercubo fusionado en su variable . Sin embargo, solo un hipercubo que contiene PE de mayor índice agrega esto a su variable local mientras mantiene el invariante. almacena solo el valor de la suma del prefijo de todos los elementos en el PE con índices menores o iguales a su propio índice. $\sigma$ $\sigma$ $\sigma$ $X$ $X$

En un hipercubo bidimensional con esquinas PE, el algoritmo debe repetirse una vez para que los hipercubos de dimensión cero se fusionen en un hipercubo unidimensional . Suponiendo un modelo de comunicación dúplex , en el que dos PE adyacentes en diferentes hipercubos se pueden intercambiar en ambas direcciones en un paso de comunicación, esto significa que se inicia la comunicación. $d$ ${\ estilo de visualización 2^{d))$ $d$ ${\ estilo de visualización 2^{d))$ $d$ $\sigma$ $d=\log _{2}p$

i := índice del propio elemento procesador ( PE ) m : = prefijo suma de elementos locales de este PE d : = número de dimensiones del hipercubo x = m ; // Invariante: suma del prefijo PE en el cubo anidado actual σ = m ; // Invariante: prefijo suma de todos los elementos en el subcubo actual for ( k = 0 ; k <= d - 1 ; k ++ ){ y = σ @ PE ( i xor 2 ^ k ) // Obtenga la suma total del prefijo del subcubo opuesto sobre la dimensión k σ = σ + y / / Prefijo de suma sumas de ambos cubos anidados if ( i & 2 ^ k ){ x = x + y // Sumando el prefijo sum de otro cubo anidado solo si este PE es un índice más alto } } Grandes tamaños de mensajes: un árbol binario canalizado

El algoritmo de tubería de árbol binario [16] es otro algoritmo para plataformas de memoria distribuida que es particularmente adecuado para mensajes de gran tamaño.

Al igual que el algoritmo del hipercubo, asume una estructura de comunicación especial. Los PE se ubican hipotéticamente en un árbol binario (por ejemplo, un árbol de Fibonacci) con numeración infija según su índice en el PE. La comunicación en dicho árbol siempre ocurre entre los nodos padre e hijo.

La numeración infija asegura que, para cualquier PE j dado , los índices de todos los nodos accesibles por su subárbol izquierdo sean menores que y los índices de todos los nodos en el subárbol derecho sean mayores que . El índice del padre es mayor que cualquiera de los índices en el subárbol PE j si PE j es el hijo izquierdo, y menor que cualquiera de los índices en el subárbol PE j . Esto permite el siguiente razonamiento: $\mathbb {[l...j-1]}$ $j$ $\mathbb {[j+1...r]}$ $j$

La suma del prefijo local del subárbol izquierdo debe combinarse para calcular la suma del prefijo local de PE j . $\mathbb {\oplus [l..j-1]}$ $\mathbb {\oplus [l..j]}$
La suma del prefijo local del subárbol derecho debe concatenarse para calcular la suma del prefijo local PE h del nivel superior que se alcanza en la ruta que contiene el hijo izquierdo (es decir, ). $\mathbb {\oplus [j+1..r]}$ ${\ estilo de visualización h> j}$
El total de prefijos para PE j es necesario para calcular el total de prefijos en el subárbol derecho (por ejemplo, para el nodo de índice más alto en el subárbol). $\mathbb {\oplus[0..j]}$ $\mathbb {\oplus [0..j..r]}$
PE j debe incluir la suma del prefijo común del primer nodo de orden superior al que se llega por un camino ascendente que involucra la unión de los hijos derechos para calcular su suma del prefijo común. $\mathbb {\oplus[0..l-1]}$

Tenga en cuenta la diferencia entre la suma de prefijos locales y generales del subárbol. Los puntos dos, tres y cuatro pueden hacer que formen una dependencia circular, pero no es así. Los PE de nivel inferior pueden requerir la suma de prefijo total de los PE de nivel superior para calcular su suma de prefijo común, pero los PE de nivel superior solo requieren la suma de prefijo local del subárbol para calcular su suma de prefijo común. El nodo raíz, como el nodo de nivel más alto, solo requiere la suma de prefijos locales de su subárbol izquierdo para calcular su propia suma de prefijos. Cada PE en la ruta desde el PE 0 hasta el PE raíz solo necesita la suma del prefijo local de su subárbol izquierdo para calcular su propia suma de prefijo, mientras que cada nodo en la ruta desde el PE p-1 (último PE) hasta la raíz del PE necesita el total suma de prefijo de su padre para calcular su propia suma de prefijo total.

Esto conduce a un algoritmo de dos fases:

Fase ascendente
Propaga la suma del prefijo local de un subárbol a su padre para cada PE j . $\mathbb {\oplus [l..j..r]}$

Fase descendente
Propagación del prefijo de suma exclusivo (PE exclusivo j , así como el PE en su subárbol izquierdo) suma de todos los PE de índice inferior que no están incluidos en el subárbol direccionado de PE j , a los PE de niveles inferiores de la izquierda subárbol hijo de PE j . Extendiendo el prefijo inclusivo sum ⊕ [0…j] al subárbol hijo derecho PE j . $\mathbb {\oplus[0..l-1]}$

Vale la pena señalar que el algoritmo se ejecuta en cada PE y los PE esperarán hasta que se hayan recibido todos los paquetes de todos los niños/padres.

k := número de paquetes en un mensaje m de un PE m @ { left , right , parent , this } := // Mensajes a diferentes PEs x = m @ esto // Fase ascendente: calcule la suma del prefijo del subárbol local para j = 0 a k - 1 : // Canalización: por ráfaga de mensaje si hasLeftChild : bloqueo de recepción m [ j ] @ izquierda // Reemplazo de m [j] local con m [ j recibido ] // Suma acumulativa de prefijos locales inclusivos de PE con índices más bajos x [ j ] = m [ j ] ⨁ x [ j ] if hasRightChild : blocking receive m [ j ] @ right // No fusionamos m[j] en una suma de prefijo local ya que los hijos correctos son PE con índices más altos envía x [ j ] ⨁ m [ j ] al padre else : send x [ j ] al padre // Fase descendente para j = 0 a k - 1 : m [ j ] @ this = 0 if hasParent : blocking receive m [ j ] @ parent // Para el hijo izquierdo, m[j] es la suma del prefijo exclusivo del padre, para el hijo derecho, el prefijo inclusivo sum x [ j ] = m [ j ] ⨁ x [ j ] enviar m [ j ] a la izquierda // Suma total de prefijos de todos los PE menores que este o cualquier PE en el subárbol izquierdo enviar x [ j ] a la derecha // Suma total de prefijos de todos los PE menores o iguales a este PE Transporte

La canalización se puede aplicar cuando el mensaje de longitud se puede dividir en partes y el operador ⨁ se puede aplicar a cada parte por separado. [dieciséis] $metro$ $norte$ $k$

Si el algoritmo se usa sin tubería, entonces solo dos capas (el PE emisor y el PE receptor) se ejecutan en el árbol en un momento dado, mientras que el resto de los PE están esperando. Si se utiliza un árbol binario equilibrado de elementos de procesamiento que contienen niveles, la longitud de la ruta es de a , que corresponde al número máximo de operaciones de comunicación ascendente no paralelas. Del mismo modo, los enlaces de enlace descendente también están limitados al mismo valor. Teniendo en cuenta el tiempo de inicio de la comunicación y el tiempo de transferencia de bytes, obtenemos que las fases están limitadas en el tiempo en la transferencia no canalizada. Al dividirse en partes, cada una de las cuales tiene elementos y los envía de manera independiente, la primera parte requerirá pasar a como parte del prefijo local suma y dicho tiempo será válido para la última parte si . $pags$ ${\ estilo de visualización \ log _ {2} p}$ $PE_{0}$ $PE_{\mathbb {raíz} }$ ${\ estilo de visualización \ log _ {2} p-1}$ $T_{\mathbb {inicio} }$ $T_{\mathbb {byte} }$ $(2\log _{2}p-2)(T_{\mathbb {inicio} }+n\cdot T_{\mathbb {byte} })$ $k$ ${\frac{n}{k))$ $(\log _{2}p-1)(T_{\mathbb {inicio} }+{\frac {n}{k))\cdot T_{\mathbb {byte} })$ $PE_{\mathbb {raíz} }$ $k>\log _{2}p$

En otras partes, todos los PE pueden funcionar en paralelo y cada tercera operación de interacción (recibir a la izquierda, recibir a la derecha, enviar al padre) envía un paquete al siguiente nivel, por lo que se puede realizar una fase para las operaciones de interacción y ambas . requieren las fases juntas , lo cual es un muy buen indicador de la longitud del mensaje . $2\log _{2}p-1+3(k-1)$ $(4\cdot \log _{2}p-2+6(k-1))(T_{\mathbb {inicio} }+{\frac {n}{k))\cdot T_{\mathbb {byte}})$ $norte$

El algoritmo se puede optimizar aún más mediante el uso de un modelo de comunicación full dúplex o de telecomunicaciones y la superposición de las fases ascendente y descendente. [dieciséis]

Estructuras de datos

Si un conjunto de datos necesita actualizarse dinámicamente, puede almacenarse en un árbol de Fenwick . Tal estructura de datos permite no solo encontrar cualquier valor de la suma del prefijo en tiempo logarítmico, sino también cambiar cualquier valor de un elemento en la matriz. [17] . Dado que el término suma de prefijos aún no era muy utilizado en 1982, apareció el trabajo [18] , donde se introdujo una estructura de datos denominada Árbol de suma parcial (5.1), que reemplazó el nombre del árbol de Fenwick.

Para calcular las sumas de subarreglos rectangulares arbitrarios en arreglos multidimensionales, la tabla de áreas sumadas se representa mediante una estructura de datos basada en sumas de prefijos. Tal tabla puede ser útil en problemas de convolución de imágenes . [19]

Aplicaciones

La ordenación por conteo es un algoritmo de ordenación de enteros que utiliza la suma del prefijo del histograma de frecuencia clave para calcular la posición de cada tecla en la matriz de salida ordenada. Se ejecuta en tiempo lineal para claves enteras que son menores que la cantidad de elementos y, a menudo, se usa como parte de radix sort , un algoritmo rápido para clasificar números enteros que tienen una magnitud menos limitada. [una]

La clasificación de listas , la tarea de transformar una lista vinculada en una matriz que contiene la misma secuencia de elementos, se puede considerar como sumas de prefijos en secuencias de unos, y luego hacer coincidir cada elemento con una posición en la matriz derivada del valor de su prefijo. suma. Muchos problemas de árboles importantes se pueden resolver en algoritmos paralelos mediante la combinación de clasificación de listas, sumas de prefijos y recorridos de Euler . [cuatro]

El cálculo paralelo de sumas de prefijos también se utiliza en el desarrollo de sumadores binarios , circuitos lógicos que pueden sumar dos números binarios de n bits. En este caso, la secuencia de bits de acarreo de suma se puede representar como una operación de escaneo en una secuencia de pares de bits de entrada, usando una función mayoritaria para combinar el acarreo dado con esos dos bits. Cada bit del número de salida se puede encontrar como un disyuntor exclusivo de los dos bits de entrada, con el bit wrap correspondiente. De esta forma es posible construir un sumador que utilice O ( n ) puertas y O (log n ) pasos de tiempo. [3] [9] [10]

En el modelo de máquina informática de acceso aleatorio paralelo, las sumas de prefijos se pueden usar para modelar algoritmos paralelos que permiten que múltiples procesadores accedan a la misma ubicación de memoria al mismo tiempo en máquinas paralelas que prohíben el acceso simultáneo. A través de una red de clasificación , un conjunto de solicitudes de acceso a la memoria concurrentes se pueden ordenar en una secuencia, de modo que el acceso a la misma celda sea contiguo dentro de la secuencia. Luego, las operaciones de escaneo se pueden usar para determinar cuál de los accesos de escritura a las celdas solicitadas tuvo éxito y distribuir los resultados de las operaciones de lectura de memoria entre múltiples procesadores que solicitan el mismo resultado. [veinte]

En la tesis doctoral de Guy Blallock [21] , las operaciones de prefijo paralelo son parte de la formalización del modelo de paralelismo de datos proporcionado por máquinas como Connection Machine . La máquina de conexión CM-1 y CM-2 proporcionaron una red de hipercubo en la que se podía implementar el Algoritmo 1 antes mencionado, mientras que CM-5 proporcionó una red para implementar el Algoritmo 2. [22]

Al construir códigos Gray , secuencias de valores binarios con la propiedad de que los valores de secuencias consecutivas difieren entre sí en una posición de bit, el número n se puede convertir al valor del código Gray en la posición n simplemente tomando el XOR de n y n /2 (el número formado al desplazar n a la derecha una posición de bit). La operación inversa, decodificar el valor codificado en Gray de x en un número binario, es más compleja, pero se puede expresar como una suma de prefijos de los bits de x , donde cada operación de suma dentro de la suma de prefijos se realiza módulo dos. Una suma de prefijos de este tipo se puede realizar de manera eficiente utilizando las operaciones lógicas bit a bit disponibles en las computadoras modernas al calcular un "o" exclusivo o x con cada uno de los números formados al desplazar x a la izquierda por un número de bits que es una potencia de dos.

El prefijo paralelo (usando la multiplicación como la principal operación asociativa) también se puede usar para construir algoritmos de interpolación de polinomios paralelos rápidos . En particular, se puede utilizar para calcular los coeficientes de división de una diferencia en la forma de Newton de un polinomio de interpolación. [23] Este enfoque basado en prefijos también se puede utilizar para obtener diferencias divididas generalizadas para la interpolación de Hermite (confluente) , así como algoritmos paralelos para los sistemas de Vandermonde .

Véase también

GPGPU

Notas

↑ 1 2Cormen , Thomas H .; Leiserson, Charles E .; Rivest, Ronald L. & Stein, Clifford (2001), 8.2 Counting Sort, Introducción a los algoritmos (2.ª ed.), MIT Press y McGraw-Hill , p. 168–170, ISBN 0-262-03293-7 .
↑ Cole, Richard & Vishkin, Uzi (1986), Lanzamiento de monedas determinista con aplicaciones para la clasificación óptima de listas paralelas , Information and Control Vol. 70(1): 32–53 , DOI 10.1016/S0019-9958(86)80023-7
↑ 1 2 3 4 5 Ladner, RE y Fischer, MJ (1980), Cómputo de prefijos paralelos , Journal of the ACM volumen 27 (4): 831–838 , DOI 10.1145/322217.322232 .
↑ 1 2 3 Tarjan, Robert E. & Vishkin, Uzi (1985), Un algoritmo de biconectividad paralela eficiente , SIAM Journal on Computing Vol. 14 (4): 862–874 , DOI 10.1137/0214061 .
↑ Lakshmivarahan, S. & Dhall, SK (1994), Parallelism in the Prefix Problem , Oxford University Press , ISBN 0-19508849-2 , < https://archive.org/details/parallelcomputin0000laks > .
↑ Blelloch, Guy (2011), Prefix Sums and Their Applications (Lecture Notes) , Carnegie Mellon University , < https://www.cs.cmu.edu/afs/cs/academic/class/15750-s11/www/handouts /PrefixSumBlelloch.pdf > Archivado el 14 de junio de 2021 en Wayback Machine .
↑ Callahan, Paul & Kosaraju, S. Rao (1995), Descomposición de conjuntos de puntos multidimensionales con aplicaciones a k-vecinos más cercanos y campos de potencial de n cuerpos , Journal of the ACM vol . 42(1): 67– 90 , DOI 10.1145/200836.200853 .
↑ Hillis, W. Daniel; Steele, Jr., Guy L. Algoritmos paralelos de datos // Comunicaciones del ACM . - 1986. - diciembre ( vol. 29 , no. 12 ). - P. 1170-1183 . doi : 10.1145 / 7902.7903 .
↑ 1 2 Ofman, Yu. (1962), Doklady Akademii Nauk SSSR T. 145 (1): 48–51 . Traducción al inglés, "Sobre la complejidad algorítmica de las funciones discretas", Soviet Physics Doklady 7 : 589–591 1963.
↑ 1 2 Khrapchenko, VM (1967), Estimación asintótica del tiempo de adición de un sumador paralelo, Problemy Kibernet. T. 19: 107–122 . Traducción al inglés en Syst. Teoría Res. 19 ; 105-122, 1970.
↑ Sengupta, Shubhabrata; Harris, Marcos; Zhang, Yao; Owens, John D. (2007). Primitivos de escaneo para computación GPU . proc. 22º Simposio ACM SIGGRAPH/EUROGRAPHICS sobre hardware gráfico. páginas. 97-106. Archivado desde el original el 3 de septiembre de 2014 . Consultado el 21-04-2020 . Parámetro obsoleto utilizado |deadlink=( ayuda )
↑ Viskin, Uzi (2003). Sumas prefijadas y una aplicación de las mismas . Patente estadounidense 6.542.918. Archivado desde el original el 22 de mayo de 2013 . Consultado el 21-04-2020 . Parámetro obsoleto utilizado |deadlink=( ayuda )
↑ Singler, Johannes MCSTL: La biblioteca de plantillas estándar multinúcleo . Consultado el 29 de marzo de 2019. Archivado desde el original el 3 de noviembre de 2016. (indefinido)
↑ Soltero, Johannes; Sanders, Pedro; Putze, Félix. MCSTL: Biblioteca de plantillas estándar multinúcleo // Euro-Par 2007 Procesamiento paralelo. - 2007. - T. 4641. - S. 682-694. — (Apuntes de clase en informática). — ISBN 978-3-540-74465-8 . -doi : 10.1007 / 978-3-540-74466-5_72 .
↑ Ananth Grama; Vipin Kumar; Anshul Gupta. Introducción a la Computación Paralela . - Addison-Wesley , 2003. - S. 85, 86. - ISBN 978-0-201-64865-2 .
↑ 1 2 3 Sanders, Pedro; Traff, Jesper Larsson. Algoritmos de prefijo paralelo (escaneo) para MPI // Avances recientes en la máquina virtual paralela y la interfaz de paso de mensajes . - 2006. - vol. 4192. - Pág. 49-57. — (Apuntes de clase en informática). - ISBN 978-3-540-39110-4 . -doi : 10.1007/ 11846802_15 .
↑ Fenwick, Peter M. (1994), Una nueva estructura de datos para tablas de frecuencias acumulativas , Software: Practice and Experience , volumen 24 (3): 327–336 , DOI 10.1002/spe.4380240306
↑ Shiloach, Yossi & Vishkin, Uzi (1982b), An O ( n 2 log n ) algoritmo paralelo de flujo máximo , Journal of Algorithms Vol. 3 (2): 128–146 , DOI 10.1016/0196-6774(82)90013 -X
↑ Szeliski, Richard (2010), Tabla de área sumada (imagen integral) , Computer Vision: Algorithms and Applications , Texts in Computer Science, Springer, p. 106–107, ISBN 9781848829350 , < https://books.google.com/books?id=bXzAlkODwa8C&pg=PA106 > .
↑ Vishkin, Uzi (1983), Implementación del acceso simultáneo a direcciones de memoria en modelos que lo prohíben , Journal of Algorithms Vol. 4 (1): 45–50 , DOI 10.1016/0196-6774(83)90033-0 .
↑ Blelloch, Guy E. Modelos vectoriales para computación en paralelo de datos (catalán) . -Cambridge , MA: MIT Press , 1990. -ISBN 026202313X .
↑ Leiserson, Charles E .; Abuhamdeh, Zahi S.; Douglas, David C.; Feynman, Carl R.; Ganmukhi, Mahesh N.; Colina, Jeffrey V.; Hillis, W.Daniel; Kuszmaul, Bradley C.; S t. Pierre, Margaret A. La arquitectura de red de la máquina de conexión CM-5 // Journal of Parallel and Distributed Computing: revista. - 1996. - 15 de marzo ( vol. 33 , no. 2 ). - P. 145-158 . — ISSN 0743-7315 . -doi : 10.1006/ jpdc.1996.0033 .
↑ Eğecioğlu, O.; Gallopoulos, E. & Koç, C. (1990), Un método paralelo para la interpolación de Newton de alto orden rápida y práctica , BIT Computer Science and Numerical Mathematics Vol. 30 (2): 268–288 , DOI 10.1007/BF02017348 .

Enlaces

Weisstein, Eric W. Suma acumulativa en el sitio web Wolfram MathWorld .