Suma de prefijo

En informática , la suma de prefijos , suma acumulativa , escaneo inclusivo o simplemente escaneo de una secuencia de números x ₀ , x ₁ , x ₂ , ... es una segunda secuencia de números y ₀ , y ₁ , y ₂ , ... , las sumas de prefijos ( totales acumulados ) de la secuencia de entrada:

y ₀ = x ₀

y ₁ = x ₀ + x ₁

y ₂ = x ₀ + x ₁ + x ₂

...

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

Las sumas de prefijos son triviales de calcular en modelos de computación secuenciales, utilizando la fórmula y _i = y _{i − 1} + x _i para calcular cada valor de salida en orden secuencial. Sin embargo, a pesar de su facilidad de cálculo, las sumas de prefijos son una primitiva útil en ciertos algoritmos como el ordenamiento por conteo , ^{[ 1 ] [ 2 ]} y forman la base de la función de orden superior de escaneo en lenguajes de programación funcional . Las sumas de prefijos también se han estudiado mucho en algoritmos paralelos , tanto como un problema de prueba a resolver como una primitiva útil para ser utilizada como subrutina en otros algoritmos paralelos. ^{[ 3 ] [ 4 ] [ 5 ]}

En abstracto, una suma de prefijos solo requiere un operador asociativo binario ⊕ , lo que la hace útil para muchas aplicaciones, desde el cálculo de descomposiciones de pares bien separadas de puntos hasta el procesamiento de cadenas. ^{[ 6 ] [ 7 ]}

Matemáticamente, la operación de sumas prefijas puede generalizarse de secuencias finitas a infinitas; en ese contexto, una suma prefija se conoce como suma parcial de una serie . La suma prefija o suma parcial constituye operadores lineales en los espacios vectoriales de secuencias finitas o infinitas; sus inversos son operadores de diferencias finitas .

En términos de programación funcional , la suma de prefijos se puede generalizar a cualquier operación binaria (no solo a la suma ); la función de orden superior resultante de esta generalización se llama escaneo y está estrechamente relacionada con la operación de plegado . Tanto el escaneo como el plegado aplican la operación binaria dada a la misma secuencia de valores, pero se diferencian en que el escaneo devuelve toda la secuencia de resultados de la operación binaria, mientras que el plegado devuelve solo el resultado final. Por ejemplo, la secuencia de números factoriales se puede generar mediante un escaneo de los números naturales utilizando la multiplicación en lugar de la suma:

Existen dos algoritmos clave para calcular una suma de prefijos en paralelo. El primero ofrece un intervalo más corto y mayor paralelismo , pero no es eficiente en términos de recursos computacionales. El segundo es eficiente en términos de recursos computacionales, pero requiere el doble de tiempo y ofrece menor paralelismo. Estos se presentan a continuación.

Algoritmo 1: Menor intervalo, mayor paralelismo

Hillis y Steele presentan el siguiente algoritmo de suma de prefijos paralelo: ^{[ 9 ]}

para i <- 0 hasta log 2 ( n ) hacer para j <- 0 hasta n - 1 hacer en paralelo si j < 2 i entonces x i +1 j <- x i j sino x i +1 j <- x i j + x i j - 2 i

En lo anterior, la notación${\displaystyle x_{j}^{i}}$significa el valor del j -ésimo elemento del array x en el paso de tiempo i .

Con un solo procesador, este algoritmo se ejecutaría en un tiempo de O ( n log n ) . ^{[ 10 ]} Sin embargo, si la máquina tiene al menos n procesadores para ejecutar el bucle interno en paralelo, el algoritmo en su conjunto se ejecuta en un tiempo de O (log n ) , el número de iteraciones del bucle externo.

Algoritmo 2: Eficiente en el trabajo

Una suma de prefijos paralela eficiente en términos de trabajo se puede calcular siguiendo los siguientes pasos. ^{[ 3 ] [ 11 ] [ 12 ]}

1. Calcula las sumas de pares consecutivos de elementos en los que el primer elemento del par tiene un índice par: z ₀ = x ₀ + x ₁ , z ₁ = x ₂ + x ₃ , etc.
2. Calcula recursivamente la suma de prefijos w ₀ , w ₁ , w ₂ , ... de la secuencia z ₀ , z ₁ , z ₂ , ...
3. Expresa cada término de la secuencia final y ₀ , y ₁ , y ₂ , ... como la suma de hasta dos términos de estas secuencias intermedias: y ₀ = x ₀ , y ₁ = z ₀ , y ₂ = z ₀ + x ₂ , y ₃ = w ₁ , etc. Después del primer valor, cada número sucesivo y _i se copia desde una posición que está a la mitad de la distancia en la secuencia w , o es el valor anterior sumado a un valor en la secuencia x .

Si la secuencia de entrada tiene n pasos, la recursión continúa hasta una profundidad de O (log n ) , que también es el límite del tiempo de ejecución paralela de este algoritmo. El número de pasos del algoritmo es O ( n ) , y puede implementarse en una máquina de acceso aleatorio paralela con O ( n /log n ) procesadores sin ralentización asintótica alguna, asignando múltiples índices a cada procesador en las rondas del algoritmo en las que hay más elementos que procesadores. ^{[ 3 ]}

Concrete implementations of prefix sum algorithms

An implementation of a parallel prefix sum algorithm, like other parallel algorithms, has to take the parallelization architecture of the platform into account. More specifically, multiple algorithms exist which are adapted for platforms working on shared memory as well as algorithms which are well suited for platforms using distributed memory, relying on message passing as the only form of interprocess communication.

Shared memory: Two-level algorithm

The following algorithm assumes a shared memory machine model; all processing elements (PEs) have access to the same memory. A version of this algorithm is implemented in the Multi-Core Standard Template Library (MCSTL),^[15][16] a parallel implementation of the C++ standard template library which provides adapted versions for parallel computing of various algorithms.

In order to concurrently calculate the prefix sum over n data elements with p processing elements, the data is divided into ${\displaystyle p+1}$ blocks, each containing ${\displaystyle {\frac {n}{p+1}}}$ elements (for simplicity we assume that ${\displaystyle p+1}$ divides n). Note, that although the algorithm divides the data into ${\displaystyle p+1}$ blocks, only p processing elements run in parallel at a time.

In a first sweep, each PE calculates a local prefix sum for its block. The last block does not need to be calculated, since these prefix sums are only calculated as offsets to the prefix sums of succeeding blocks and the last block is by definition not succeeded.

Los desplazamientos p que se almacenan en la última posición de cada bloque se acumulan en una suma de prefijo propia y se almacenan en sus posiciones subsiguientes. Si p es un número pequeño, es más rápido hacerlo de forma secuencial; si p es grande , este paso también se puede realizar en paralelo.

Se realiza un segundo barrido. En esta ocasión, no es necesario procesar el primer bloque, ya que no requiere tener en cuenta el desplazamiento del bloque anterior. Sin embargo, en este barrido se incluye el último bloque y se calculan las sumas de prefijo para cada bloque, considerando los desplazamientos de los bloques de suma de prefijo calculados en el barrido anterior.

función prefix_sum ( elementos ) { n := tamaño ( elementos ) p := número de elementos a procesar prefix_sum := [ 0. . .0 ] de tamaño n hacer paralelo i = 0 a p - 1 { // i := índice del PE actual desde j = i * n / ( p + 1 ) hasta ( i + 1 ) * n / ( p + 1 ) - 1 hacer { // Esto solo almacena la suma del prefijo de los bloques locales almacenar_prefijo_sum_con_desplazamiento_en ( elementos , 0 , prefijo_sum ) } } x = 0 para i = 1 a p { // Acumulación serial de la suma total de bloques x += prefijo_sum [ i * n / ( p + 1 ) - 1 ] // Construir la suma del prefijo sobre los primeros p bloques prefijo_sum [ i * n / ( p + 1 )] = x // Guardar los resultados para usarlos como desplazamientos en el segundo barrido } hacer paralelo i = 1 a p { // i := índice del PE actual desde j = i * n / ( p + 1 ) hasta ( i + 1 ) * n / ( p + 1 ) - 1 hacer { desplazamiento := suma_prefijo [ i * n / ( p + 1 )] // Calcular la suma del prefijo tomando la suma de los bloques precedentes como desplazamientoalmacenar_suma_prefijo_con_desplazamiento_en ( elementos , desplazamiento , suma_prefijo ) } } devolver suma_prefijo }

Mejora: En caso de que el número de bloques sea excesivo y el paso secuencial resulte lento al utilizar un solo procesador, se puede emplear el algoritmo de Hillis y Steele para acelerar la segunda fase.

Memoria distribuida: algoritmo de hipercubo

El algoritmo de suma de prefijos de hipercubo ^{[ 17 ]} está bien adaptado para plataformas de memoria distribuida y funciona con el intercambio de mensajes entre los elementos de procesamiento. Supone tener${\displaystyle p=2^{d}}$Elementos de procesador (PE) que participan en el algoritmo igual al número de esquinas en un hipercubo d -dimensional .

A lo largo del algoritmo, cada PE se considera una esquina en un hipercubo hipotético con conocimiento de la suma total de prefijos σ, así como de la suma de prefijos x de todos los elementos hasta sí mismo (de acuerdo con los índices ordenados entre los PE), ambos en su propio hipercubo.

• El algoritmo comienza asumiendo que cada PE es el único vértice de un hipercubo de dimensión cero y, por lo tanto, σ y x son iguales a la suma de prefijos locales de sus propios elementos.
• El algoritmo continúa unificando hipercubos adyacentes en una dimensión. Durante cada unificación, σ se intercambia y agrega entre los dos hipercubos, manteniendo la invariante de que todos los PE en las esquinas de este nuevo hipercubo almacenan la suma total de prefijos de este hipercubo unificado en su variable σ . Sin embargo, solo el hipercubo que contiene los PE con índice mayor también agrega este σ a su variable local x , manteniendo la invariante de que x solo almacena el valor de la suma de prefijos de todos los elementos en los PE con índices menores o iguales a su propio índice.

En un hipercubo d -dimensional con${\displaystyle 2^{d}}$PE en las esquinas, el algoritmo debe repetirse d veces para tener el${\displaystyle 2^{d}}$Los hipercubos de dimensión cero se unifican en un hipercubo de dimensión d . Suponiendo un modelo de comunicación dúplex donde la σ de dos PE adyacentes en diferentes hipercubos se puede intercambiar en ambas direcciones en un paso de comunicación, esto significa${\displaystyle d=\log _{2}p}$empresas emergentes de comunicación.

i : = Índice del propio elemento procesador ( PE ) m : = suma de prefijos de los elementos locales de este PE d : = número de dimensiones del hipercubox = m ; // Invariante: La suma de prefijos hasta este PE en el subcubo actual σ = m ; // Invariante: La suma de prefijos de todos los elementos en el subcubo actualpara ( k = 0 ; k <= d -1 ; k ++ ) { y = σ @ PE ( i xor 2 ^ k ) // Obtener la suma total de prefijos del subcubo opuesto a lo largo de la dimensión k σ = σ + y // Agregar la suma de prefijos de ambos subcubosif ( i & 2 ^ k ) { x = x + y // Solo se agrega la suma del prefijo del otro subcubo, si este PE es el de mayor índice. } }

Tamaños de mensajes grandes: árbol binario en paralelo

El algoritmo de árbol binario segmentado ^{[ 18 ]} es otro algoritmo para plataformas de memoria distribuida que es especialmente adecuado para tamaños de mensajes grandes.

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

La numeración infija garantiza que para cualquier PE _j dado , los índices de todos los nodos alcanzables por su subárbol izquierdo${\displaystyle \color {Azul}{[l\dots j-1]}}$son menores que j y los índices${\displaystyle \color {Blue}{[j+1\dots r]}}$de todos los nodos en el subárbol derecho son mayores que j . El índice del padre es mayor que cualquiera de los índices en el subárbol de PE _{j si PE j} es un hijo izquierdo y menor si PE _j es un hijo derecho. Esto permite el siguiente razonamiento:

• La suma del prefijo local${\displaystyle \color {Azul}{\oplus [l\dots j-1]}}$del subárbol izquierdo debe agregarse para calcular la suma del prefijo local de PE _j${\displaystyle \color {Azul}{\oplus [l\dots j]}}$.
• La suma del prefijo local${\displaystyle \color {Blue}{\oplus [j+1\dots r]}}$del subárbol derecho debe agregarse para calcular la suma de prefijos locales de PE _h de nivel superior que se alcanzan en una ruta que contiene una conexión de hijos izquierdos (lo que significa${\displaystyle h>j}$).
• La suma total de prefijos${\displaystyle \color {Red}{\oplus [0\dots j]}}$de PE _j es necesario para calcular las sumas totales de prefijos en el subárbol derecho (por ejemplo${\displaystyle \color {Red}{\oplus [0\dots j\dots r]}}$para el nodo de índice más alto en el subárbol).
• PE _j debe incluir la suma total del prefijo${\displaystyle \color {Red}{\oplus [0\dots l-1]}}$del primer nodo de orden superior al que se llega a través de una ruta ascendente que incluye una conexión de hijos derechos para calcular su suma de prefijo total.

Nótese la distinción entre sumas de prefijos locales de subárbol y sumas totales de prefijos. Los puntos dos, tres y cuatro pueden llevar a creer que formarían una dependencia circular , pero este no es el caso. Los PE de nivel inferior podrían requerir la suma total de prefijos de los PE de nivel superior para calcular su suma total de prefijos, pero los PE de nivel superior solo requieren sumas de prefijos locales de subárbol para calcular su suma total de prefijos. El nodo raíz, como nodo de nivel más alto, solo requiere la suma de prefijos local de su subárbol izquierdo para calcular su propia suma de prefijos. Cada PE en la ruta desde PE ₀ hasta el PE raíz solo requiere la suma de prefijos local de su subárbol izquierdo para calcular su propia suma de prefijos, mientras que cada nodo en la ruta desde PE _p-1 (último PE) hasta el PE _raíz requiere la suma total de prefijos de su padre para calcular su propia suma total de prefijos.

Esto da lugar a un algoritmo de dos fases:

Fase ascendente

Propagar la suma de prefijos locales del subárbol${\displaystyle \color {Blue}{\oplus [l\dots j\dots r]}}$a su padre para cada PE _j .

Fase descendente

_{Propagar la suma total de prefijos exclusivos (PE j} exclusivo , así como los PE en su subárbol izquierdo)${\displaystyle \color {Red}{\oplus [0\dots l-1]}}$de todos los PE de índice inferior que no están incluidos en el subárbol dirigido del PE _j a los PE de nivel inferior en el subárbol hijo izquierdo del PE _j . Propagar la suma de prefijos inclusivos${\displaystyle \color {Red}{\oplus [0\dots j]}}$al subárbol hijo derecho de PE _j .

Tenga en cuenta que el algoritmo se ejecuta en paralelo en cada PE y que los PE se bloquearán al recibir paquetes hasta que sus hijos/padres les proporcionen los mismos.

k := número de paquetes en un mensaje m de un PE m @ { izquierda , derecha , padre , este } := // Mensajes en los diferentes PEx = m @ este// Fase ascendente: Calcular sumas de prefijos locales de subárbol para j = 0 a k - 1 : // Pipelining: Para cada paquete de un mensaje si hasLeftChild : blocking receive m [ j ] @ left // Esto reemplaza el m[j] local con el m[j] recibido // Agregación de la suma de prefijos locales inclusivos de los PE de índice inferior x [ j ] = m [ j ] ⨁ x [ j ]if hasRightChild : blocking receive m [ j ] @ right // No agregamos m[j] a la suma del prefijo local, ya que los hijos derechos son PE de índice superior send x [ j ] ⨁ m [ j ] to parent else : send x [ j ] to parent// Fase descendente para j = 0 a k - 1 : m [ j ] @ this = 0if hasParent : blocking receive m [ j ] @ parent // Para un hijo izquierdo m[j] es la suma de prefijos exclusivos de los padres, para un hijo derecho la suma de prefijos inclusivos x [ j ] = m [ j ] ⨁ x [ j ] send m [ j ] to left // La suma total de prefijos de todos los PE menores que este o cualquier PE en el subárbol izquierdo send x [ j ] to right // La suma total de prefijos de todos los PE menores o iguales que este PE

Tuberías

Si el mensaje m de longitud n se puede dividir en k paquetes y el operador ⨁ se puede usar en cada uno de los paquetes de mensaje correspondientes por separado, es posible el procesamiento en paralelo . ^{[ 18 ]}

Si el algoritmo se utiliza sin segmentación, siempre hay solo dos niveles (los PE emisores y los PE receptores) del árbol binario en funcionamiento mientras todos los demás PE están esperando. Si hay p elementos de procesamiento y se utiliza un árbol binario balanceado, el árbol tiene${\displaystyle \log _{2}p}$niveles, la longitud del camino desde${\displaystyle PE_{0}}$a${\displaystyle PE_{\mathrm {raíz} }}$es por lo tanto${\displaystyle \log _{2}p-1}$que representa el número máximo de operaciones de comunicación no paralelas durante la fase ascendente, asimismo, la comunicación en la ruta descendente también está limitada a${\displaystyle \log _{2}p-1}$startups. Suponiendo un tiempo de inicio de comunicación de${\displaystyle T_{\mathrm {start} }}$y un tiempo de transmisión byte a byte de${\displaystyle T_{\mathrm {byte} }}$, las fases ascendente y descendente se limitan a${\displaystyle (2\log _{2}p-2)(T_{\mathrm {start} }+n\cdot T_{\mathrm {byte} })}$en un escenario sin procesamiento en paralelo.

Al dividirse en k paquetes, cada uno de tamaño${\displaystyle {\tfrac {n}{k}}}$y enviándolos por separado, el primer paquete aún necesita${\displaystyle (\log _{2}p-1)\left(T_{\mathrm {start} }+{\frac {n}{k}}\cdot T_{\mathrm {byte} }\right)}$ser propagado a${\displaystyle PE_{\mathrm {raíz} }}$como parte de una suma de prefijo local y esto volverá a ocurrir para el último paquete si${\displaystyle k>\log _{2}p}$Sin embargo, entretanto, todos los PE a lo largo de la ruta pueden trabajar en paralelo y cada tercera operación de comunicación (recibir izquierda, recibir derecha, enviar al padre) envía un paquete al siguiente nivel, de modo que una fase puede completarse en${\displaystyle 2\log _{2}p-1+3(k-1)}$operaciones de comunicación y ambas fases juntas necesitan${\displaystyle (4\cdot \log _{2}p-2+6(k-1))\left(T_{\mathrm {start} }+{\frac {n}{k}}\cdot T_{\mathrm {byte} }\right)}$lo cual es favorable para tamaños de mensaje grandes n .

El algoritmo se puede optimizar aún más utilizando comunicación dúplex completo o en modelo telefónico y superponiendo la fase ascendente y la descendente. ^{[ 18 ]}

Cuando un conjunto de datos puede actualizarse dinámicamente, puede almacenarse en una estructura de datos de árbol de Fenwick . Esta estructura permite tanto la búsqueda de cualquier valor de suma de prefijo individual como la modificación de cualquier valor de matriz en tiempo logarítmico por operación. ^{[ 19 ]} Sin embargo, un artículo anterior de 1982 ^{[ 20 ]} presenta una estructura de datos llamada Árbol de sumas parciales (véase la Sección 5.1) que parece superponerse a los árboles de Fenwick; en 1982 el término suma de prefijo aún no era tan común como lo es hoy.

Para matrices de dimensiones superiores, la tabla de áreas sumadas proporciona una estructura de datos basada en sumas de prefijos para calcular sumas de submatrices rectangulares arbitrarias. Esto puede ser una primitiva útil en operaciones de convolución de imágenes . ^{[ 21 ]}

El algoritmo de ordenación por conteo es un algoritmo de ordenación de enteros que utiliza la suma de prefijos de un histograma de frecuencias de claves para calcular la posición de cada clave en el array de salida ordenado. Se ejecuta en tiempo lineal para claves enteras menores que el número de elementos y se utiliza frecuentemente como parte de la ordenación por radix , un algoritmo rápido para ordenar enteros con menor restricción de magnitud. ^{[ 1 ]}

La clasificación de listas , el problema de transformar una lista enlazada en un arreglo que representa la misma secuencia de elementos, puede verse como el cálculo de una suma de prefijos en la secuencia 1, 1, 1, ... y luego el mapeo de cada elemento a la posición del arreglo dada por el valor de su suma de prefijos; al combinar la clasificación de listas, las sumas de prefijos y los recorridos de Euler , muchos problemas importantes sobre árboles pueden resolverse mediante algoritmos paralelos eficientes. ^{[ 4 ]}

Una de las primeras aplicaciones de los algoritmos de suma de prefijos paralelos fue el diseño de sumadores binarios , circuitos booleanos que pueden sumar dos números binarios de n bits. En esta aplicación, la secuencia de bits de acarreo de la suma se puede representar como una operación de escaneo sobre la secuencia de pares de bits de entrada, utilizando la función de mayoría para combinar el acarreo anterior con estos dos bits. Cada bit del número de salida se puede encontrar como la operación OR exclusiva de dos bits de entrada con el bit de acarreo correspondiente. Al utilizar un circuito que realiza las operaciones del algoritmo de suma de prefijos paralelo, es posible diseñar un sumador que utiliza O ( n ) compuertas lógicas y O (log n ) pasos de tiempo. ^{[ 3 ] [ 11 ] [ 12 ]}

En el modelo de computación de máquina de acceso aleatorio paralelo , las sumas de prefijos se pueden usar para simular algoritmos paralelos que asumen la capacidad de múltiples procesadores para acceder a la misma celda de memoria al mismo tiempo, en máquinas paralelas que prohíben el acceso simultáneo. Mediante una red de ordenación , un conjunto de solicitudes de acceso a memoria paralelas se puede ordenar en una secuencia de manera que los accesos a la misma celda sean contiguos dentro de la secuencia; luego se pueden usar operaciones de escaneo para determinar cuáles de los accesos tienen éxito al escribir en las celdas solicitadas y para distribuir los resultados de las operaciones de lectura de memoria a múltiples procesadores que solicitan el mismo resultado. ^{[ 22 ]}

En la tesis doctoral de Guy Blelloch , ^{[ 23 ]} las operaciones de prefijo paralelas forman parte de la formalización del modelo de paralelismo de datos proporcionado por máquinas como Connection Machine . Connection Machine CM-1 y CM-2 proporcionaron una red hipercúbica en la que se podía implementar el Algoritmo 1 anterior, mientras que CM-5 proporcionó una red dedicada para implementar el Algoritmo 2. ^{[ 24 ]}

En la construcción de códigos Gray , secuencias de valores binarios con la propiedad de que los valores consecutivos de la secuencia difieren entre sí en una sola posición de bit, un número n puede convertirse en el valor del código Gray en la posición n de la secuencia simplemente tomando la operación OR exclusiva 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 un valor codificado en Gray x en un número binario , es más compleja, pero puede expresarse como la 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 puede realizarse de manera eficiente utilizando las operaciones booleanas bit a bit disponibles en las computadoras modernas, calculando la operación OR exclusiva de x con cada uno de los números formados al desplazar x a la izquierda un número de bits que es potencia de dos. ^{[ 25 ]} 

El prefijo paralelo (que utiliza la multiplicación como operación asociativa subyacente) también puede emplearse para construir algoritmos rápidos para la interpolación polinómica paralela . En particular, puede utilizarse para calcular los coeficientes de diferencias divididas de la forma de Newton del polinomio de interpolación. ^{[ 26 ]} Este enfoque basado en prefijos también puede emplearse para obtener las diferencias divididas generalizadas para la interpolación de Hermite (confluente) , así como para algoritmos paralelos para sistemas de Vandermonde . ^{[ 27 ]}

Los algoritmos de prefijo paralelo también pueden utilizarse para la paralelización temporal de métodos de estimación bayesiana recursiva , incluidos los filtros bayesianos, los filtros de Kalman , así como los suavizadores correspondientes. ^{[ 28 ]} La idea central es que, por ejemplo, las soluciones a los problemas de filtrado bayesiano/de Kalman se escriben en términos de un operador de filtrado asociativo adecuadamente definido , de modo que las "sumas" de prefijo del operador de filtrado dan la solución de filtrado. Esto permite que los algoritmos de prefijo paralelo se apliquen para calcular las soluciones de filtrado y suavizado. Una idea similar también funciona para la paralelización de una clase de solucionadores de ecuaciones diferenciales probabilísticas ^{[ 29 ]} en el contexto de la numérica probabilística .

En el contexto del control óptimo , se pueden utilizar algoritmos de prefijo paralelo para la paralelización de la ecuación de Bellman y las ecuaciones de Hamilton-Jacobi-Bellman (ecuaciones HJB), incluyendo sus casos especiales de regulador lineal-cuadrático . ^{[ 30 ] [ 31 ]} Aquí, la idea es que podemos definir un operador asociativo para una combinación de funciones de valor condicional (condicionadas al punto final), y las sumas de prefijo de este operador dan soluciones a las ecuaciones de Bellman o HJB.

La suma de prefijos se utiliza para el balanceo de carga como un algoritmo de bajo costo para distribuir el trabajo entre múltiples procesadores, donde el objetivo principal es lograr una cantidad igual de trabajo en cada procesador. El algoritmo utiliza una matriz de pesos que representan la cantidad de trabajo requerida para cada elemento. Después de calcular la suma de prefijos, el elemento de trabajo i se envía para su procesamiento a la unidad de procesamiento con el número [ ⁠ prefixSumValue _i / totalWork / numberOfProcessors ⁠ ] . ^{[ 32 ]} Gráficamente, esto corresponde a una operación donde la cantidad de trabajo en cada elemento está representada por la longitud de un segmento lineal, todos los segmentos se colocan secuencialmente en una línea y el resultado se divide en un número de piezas, correspondiente al número de procesadores. ^{[ 33 ]}

A continuación se muestra una tabla de consulta de cuartos de cuadrado con el resto descartado para los dígitos del 0 al 18; esto permite la multiplicación de números hasta 9×9 .

Por ejemplo, si quisieras multiplicar 9 por 3, observarías que la suma y la diferencia son 12 y 6 respectivamente. Al buscar ambos valores en la tabla, obtendrías 36 y 9, cuya diferencia es 27, que es el producto de 9 y 3.

• Computación de propósito general en unidades de procesamiento gráfico
• Escaneo segmentado
• Tabla de áreas sumadas

• Weisstein, Eric W. "Suma acumulativa" . MathWorld .