Prefijo suma

Secuencia en informática

En informática , el prefijo suma , 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 los prefijos ( totales acumulados ) de la secuencia de entrada:

y ₀ = x ₀

y1 = x0 + x1_​​​

y2 = x0 + x1 + x2_​​​​

...

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

Las sumas de prefijo son triviales de calcular en modelos secuenciales de computación, utilizando la fórmula y _i = y _{i − 1} + x _i para calcular cada valor de salida en orden de secuencia. Sin embargo, a pesar de su facilidad de cálculo, las sumas de prefijo son un primitivo ú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 prefijo también se han estudiado mucho en algoritmos paralelos , tanto como un problema de prueba a resolver como un primitivo útil para ser utilizado como una subrutina en otros algoritmos paralelos. ^{[3] [4] [5]}

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

Matemáticamente, la operación de tomar sumas de prefijo se puede generalizar de secuencias finitas a infinitas; en ese contexto, una suma de prefijo se conoce como una suma parcial de una serie . La suma de prefijo o la suma parcial forman operadores lineales en los espacios vectoriales de secuencias finitas o infinitas; sus inversos son operadores de diferencia finita .

Escanear función de orden superior

En términos de programación funcional , el prefijo suma puede generalizarse 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 denomina escaneo y está estrechamente relacionada con la operación de plegado . Tanto la operación de escaneo como la de plegado aplican la operación binaria dada a la misma secuencia de valores, pero difieren en que el escaneo devuelve la secuencia completa de resultados de la operación binaria, mientras que el plegado devuelve solo el resultado final. Por ejemplo, la secuencia de números factoriales puede generarse mediante un escaneo de los números naturales utilizando la multiplicación en lugar de la suma:

Escaneos inclusivos y exclusivos

Las implementaciones de escaneo en lenguajes de programación y bibliotecas pueden ser inclusivas o exclusivas . Un escaneo inclusivo incluye la entrada x _i cuando se calcula la salida y _i (es decir, ) mientras que un escaneo exclusivo no lo hace (es decir, ). En el último caso, las implementaciones dejan y _{0 sin definir o aceptan un valor "} x ₋₁ " separado con el que inicializar el escaneo. Cualquier tipo de escaneo se puede transformar en el otro: un escaneo inclusivo se puede transformar en un escaneo exclusivo desplazando la matriz producida por el escaneo a la derecha por un elemento e insertando el valor de identidad a la izquierda de la matriz. Por el contrario, un escaneo exclusivo se puede transformar en un escaneo inclusivo desplazando la matriz producida por el escaneo a la izquierda e insertando la suma del último elemento del escaneo y el último elemento de la matriz de entrada a la derecha de la matriz. ^[8] ${\textstyle y_{i}=\bigoplus _{j=0}^{i}x_{j}}$ ${\textstyle y_{i}=\bigoplus _{j=0}^{i-1}x_{j}}$

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

El modelo de programación paralela OpenMP basado en directivas admite escaneo tanto inclusivo como exclusivo a partir de la versión 5.0.

Algoritmos paralelos

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

Algoritmo 1: menor lapso, más paralelo

Representación de circuito de una suma de prefijo en paralelo de 16 entradas altamente paralela

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

para  i <- 0 a floor(log 2 ( n )) hacer  para  j <- 0 a n - 1 hacer en paralelo  si  j < 2 i  entonces  xyo + 
1j< -xYo, 
yo De lo contrario  xyo + 
1j< -xYo, 
yo+ xyo 
j -2 yo

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

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

Algoritmo 2: Trabajo eficiente

Representación de circuito de una suma de prefijo en paralelo de 16 entradas que funciona de manera eficiente

Se puede calcular una suma de prefijos paralelos eficiente en el trabajo mediante los siguientes pasos. ^{[3] [10] [11]}

1. Calcular 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. Calcular recursivamente la suma del prefijo w ₀ , w ₁ , w ₂ , ... de la secuencia z ₀ , z ₁ , z ₂ , ...
3. Expresar 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 situada a la mitad de la secuencia w , o bien se suma el valor anterior a un valor en la secuencia x .

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

Discusión

Cada uno de los algoritmos anteriores se ejecuta en tiempo O (log n ) . Sin embargo, el primero requiere exactamente log ₂ n pasos, mientras que el segundo requiere 2 log ₂  n − 2 pasos. Para los ejemplos de 16 entradas ilustrados, el algoritmo 1 es 12 vías paralelas (49 unidades de trabajo divididas por un lapso de 4) mientras que el algoritmo 2 es solo 4 vías paralelas (26 unidades de trabajo divididas por un lapso de 6). Sin embargo, el algoritmo 2 es eficiente en el trabajo: realiza solo un factor constante (2) de la cantidad de trabajo requerida por el algoritmo secuencial, mientras que el algoritmo 1 es ineficiente en el trabajo: realiza asintóticamente más trabajo (un factor logarítmico) que el que se requiere secuencialmente. En consecuencia, es probable que el algoritmo 1 funcione mejor cuando hay disponible un paralelismo abundante, pero es probable que el algoritmo 2 funcione mejor cuando el paralelismo es más limitado.

Los algoritmos paralelos para sumas de prefijos a menudo se pueden generalizar a otras operaciones de escaneo en operaciones binarias asociativas , ^{[3] [4]} y también se pueden calcular de manera eficiente en hardware paralelo moderno como una GPU . ^[12] La idea de construir en hardware una unidad funcional dedicada a calcular la suma de prefijos de múltiples parámetros fue patentada por Uzi Vishkin . ^[13]

Muchas implementaciones paralelas siguen un procedimiento de dos pasos en el que las sumas de prefijos parciales se calculan en el primer paso en cada unidad de procesamiento; luego, se calcula la suma de prefijos de estas sumas parciales y se transmite de nuevo a las unidades de procesamiento para un segundo paso utilizando el prefijo ahora conocido como valor inicial. Asintóticamente, este método requiere aproximadamente dos operaciones de lectura y una operación de escritura por elemento.

Implementaciones concretas de algoritmos de suma de prefijos

La implementación de un algoritmo de suma de prefijos paralelos, al igual que otros algoritmos paralelos, debe tener en cuenta la arquitectura de paralelización de la plataforma. Más específicamente, existen múltiples algoritmos que están adaptados para plataformas que funcionan con memoria compartida , así como algoritmos que son adecuados para plataformas que utilizan memoria distribuida y que dependen del paso de mensajes como la única forma de comunicación entre procesos.

Memoria compartida: algoritmo de dos niveles

El siguiente algoritmo supone un modelo de máquina de memoria compartida ; todos los elementos de procesamiento (PE) tienen acceso a la misma memoria. Una versión de este algoritmo se implementa en la biblioteca de plantillas estándar de múltiples núcleos (MCSTL), ^{[14] [15]} una implementación paralela de la biblioteca de plantillas estándar de C++ que proporciona versiones adaptadas para el cálculo paralelo de varios algoritmos.

Para calcular simultáneamente la suma del prefijo sobre los elementos de datos y los elementos de procesamiento, los datos se dividen en bloques, cada uno de los cuales contiene elementos (para simplificar, suponemos que divide ). Tenga en cuenta que, aunque el algoritmo divide los datos en bloques, solo los elementos de procesamiento se ejecutan en paralelo a la vez. ${\displaystyle n}$ ${\displaystyle p}$ ${\displaystyle p+1}$ ${\displaystyle {\frac {n}{p+1}}}$ ${\displaystyle p+1}$ ${\displaystyle n}$ ${\displaystyle p+1}$ ${\displaystyle p}$

En un primer barrido, cada PE calcula una suma de prefijo local para su bloque. No es necesario calcular el último bloque, ya que estas sumas de prefijo solo se calculan como compensaciones de las sumas de prefijo de los bloques siguientes y, por definición, el último bloque no es siguiente.

Los desplazamientos que se almacenan en la última posición de cada bloque se acumulan en una suma de prefijo propia y se almacenan en las posiciones siguientes. Al ser un número pequeño, es más rápido hacer esto secuencialmente; para un número grande , este paso también se puede realizar en paralelo. ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle p}$

Se realiza un segundo barrido. Esta vez no es necesario procesar el primer bloque, ya que no necesita tener en cuenta el desplazamiento de un bloque anterior. Sin embargo, en este barrido se incluye el último bloque y las sumas de prefijo para cada bloque se calculan teniendo en cuenta los desplazamientos de bloque de suma de prefijo calculados en el barrido anterior.

función prefijo_suma ( elementos ) { n := tamaño ( elementos ) p := número de elementos a procesar prefijo_suma := [ 0. . .0 ] de tamaño n do parallel i = 0 a p - 1 { // i := índice del PE actual de j = i * n / ( p + 1 ) a ( i + 1 ) * n / ( p + 1 ) - 1 do { // Esto solo almacena la suma del prefijo de los bloques locales store_prefix_sum_with_offset_in ( elements , 0 , prefix_sum ) } } x = 0 para i = 1 a p { // Acumulación serial de la suma total de bloques x += prefix_sum [ i * n / ( p + 1 ) - 1 ] // Construye la suma del prefijo sobre los primeros p bloques prefix_sum [ i * n / ( p + 1 )] = x // Guarda los resultados para usarlos como desplazamientos en el segundo barrido } do parallel 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 )] // Calcular la suma del prefijo tomando la suma de los bloques anteriores como desplazamiento                                                                                                                        almacenar_suma_de_prefijo_con_desplazamiento_en ( elementos , desplazamiento , suma_de_prefijo ) } } devolver suma_de_prefijo }       

Mejora: En caso de que el número de bloques sea demasiado grande y haga que el paso serial tome mucho tiempo al implementar un solo procesador, se puede utilizar el algoritmo de Hillis y Steele para acelerar la segunda fase.

Memoria distribuida: algoritmo de hipercubo

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

Diferentes hipercubos para distintos números de nodos

A lo largo del algoritmo, cada PE se ve como una esquina en un hipercubo hipotético con conocimiento de la suma total de prefijos así como de la suma de prefijos de todos los elementos hasta él mismo (según los índices ordenados entre los PE), ambos en su propio hipercubo. ${\displaystyle \sigma }$ ${\displaystyle x}$

• El algoritmo comienza asumiendo que cada PE es la esquina única de un hipercubo de dimensión cero y, por lo tanto , y son iguales a la suma del prefijo local de sus propios elementos. ${\displaystyle \sigma }$ ${\displaystyle x}$
• El algoritmo continúa unificando hipercubos que son adyacentes a lo largo de una dimensión. Durante cada unificación, se intercambia y se agrega entre los dos hipercubos, lo que mantiene la invariante de que todos los PE en las esquinas de este nuevo hipercubo almacenan la suma total de prefijos de este hipercubo recién unificado en su variable . Sin embargo, solo el hipercubo que contiene los PE con índice más alto también agrega esto a su variable local , manteniendo la invariante que 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. ${\displaystyle \sigma }$ ${\displaystyle \sigma }$ ${\displaystyle \sigma }$ ${\displaystyle x}$ ${\displaystyle x}$

En un hipercubo de dimensión cero con elementos de proceso en las esquinas, el algoritmo debe repetirse varias veces para que los hipercubos de dimensión cero se unifiquen en un hipercubo unidimensional. Suponiendo un modelo de comunicación dúplex donde los datos de dos elementos de proceso adyacentes en diferentes hipercubos se pueden intercambiar en ambas direcciones en un solo paso de comunicación, esto significa que se inicia la comunicación. ${\displaystyle d}$ ${\displaystyle 2^{d}}$ ${\displaystyle d}$ ${\displaystyle 2^{d}}$ ${\displaystyle d}$ ${\displaystyle \sigma }$ ${\displaystyle d=\log _{2}p}$

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

Mensajes de gran tamaño: árbol binario segmentado

El algoritmo de árbol binario canalizado ^[17] es otro algoritmo para plataformas de memoria distribuida que es especialmente adecuado para mensajes de gran tamaño.

Al igual que el algoritmo del hipercubo, se supone que existe 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 un árbol de este tipo siempre se produce entre los 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 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 de PE _{j si PE j} es un hijo izquierdo y menor si PE _j es un hijo derecho. Esto permite el siguiente razonamiento: ${\displaystyle \mathbb {[l...j-1]} }$ ${\displaystyle j}$ ${\displaystyle \mathbb {[j+1...r]} }$ ${\displaystyle j}$

Intercambio de información entre elementos de procesamiento durante la fase ascendente (azul) y descendente (rojo) en el algoritmo de suma de prefijos de árbol binario segmentado.

• La suma del prefijo local del subárbol izquierdo debe agregarse para calcular la suma del prefijo local de PE _j . ${\displaystyle \mathbb {\oplus [l..j-1]} }$ ${\displaystyle \mathbb {\oplus [l..j]} }$
• La suma del prefijo local del subárbol derecho debe agregarse para calcular la suma del prefijo local del PE de nivel superior _h al que se llega en una ruta que contiene una conexión de hijos izquierdos (lo que significa ). ${\displaystyle \mathbb {\oplus [j+1..r]} }$ ${\displaystyle h>j}$
• La suma total de prefijos de PE _j es necesaria para calcular las sumas totales de prefijos en el subárbol derecho (por ejemplo, para el nodo de índice más alto en el subárbol). ${\displaystyle \mathbb {\oplus [0..j]} }$ ${\displaystyle \mathbb {\oplus [0..j..r]} }$
• PE _j debe incluir la suma total del prefijo 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 total del prefijo. ${\displaystyle \mathbb {\oplus [0..l-1]} }$

Nótese la distinción entre las sumas de prefijos locales de subárbol y totales. 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 pueden 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 locales de su subárbol izquierdo para calcular su propia suma de prefijos. Cada PE en la ruta desde el PE ₀ hasta el PE raíz solo requiere la suma de prefijos locales de su subárbol izquierdo para calcular su propia suma de prefijos, mientras que cada nodo en la ruta desde el PE _p-1 (último PE) hasta la _raíz del PE requiere la suma total de prefijos de su padre para calcular su propia suma total de prefijos.

Esto conduce a un algoritmo de dos fases:

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

Fase descendente
Propagar la suma total de prefijos exclusiva (PE exclusiva _j así como los PE en su subárbol izquierdo) de todos los PE de índice inferior que no están incluidos en el subárbol direccionado de PE _j a los PE de nivel inferior en el subárbol hijo izquierdo de PE _j . Propagar la suma de prefijos inclusiva al subárbol hijo derecho de PE _j . ${\displaystyle \mathbb {\oplus [0..l-1]} }$ ${\displaystyle \mathbb {\oplus [0..j]} }$

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

k := número de paquetes en un mensaje m de un PE m @ { left , right , parent , this } := // Mensajes en los diferentes PE                  x = m @ esto    // Fase ascendente: calcular las sumas de prefijos locales de subárboles para j = 0 a k - 1 : // Canalización: para cada paquete de un mensaje si tieneLeftChild : bloqueo de recepción m [ j ] @ left // Esto reemplaza el m[j] local con el m[j] recibido // Suma de prefijo local inclusivo agregado de los PE de índice inferior x [ j ] = m [ j ] ⨁ x [ j ]                   si hasRightChild : bloqueo recibe m [ j ] @ right // No agregamos m[j] a la suma del prefijo local, ya que los hijos correctos son PE de índice más alto envía x [ j ] ⨁ m [ j ] al padre de lo contrario : envía x [ j ] al padre                  // Fase descendente para j = 0 a k - 1 : m [ j ] @ this = 0         si tieneParent : bloqueo recibir m [ j ] @ padre // Para un hijo izquierdo m[j] es la suma de prefijo exclusiva de los padres, para un hijo derecho la suma de prefijo inclusiva x [ j ] = m [ j ] ⨁ x [ j ] enviar m [ j ] a la izquierda // La suma total de prefijo de todos los PE más pequeños que este o cualquier PE en el subárbol izquierdo enviar x [ j ] a la derecha // La suma total de prefijo de todos los PE más pequeños o iguales que este PE                        

Canalización

Si el mensaje m de longitud n se puede dividir en k paquetes y el operador ⨁ se puede utilizar en cada uno de los paquetes de mensajes correspondientes por separado, es posible la segmentación . ^[17]

Si se utiliza el algoritmo sin canalización, siempre hay solo dos niveles (los PE emisores y los PE receptores) del árbol binario en funcionamiento mientras todos los demás PE esperan. Si hay p elementos de procesamiento y se utiliza un árbol binario equilibrado, el árbol tiene niveles, la longitud de la ruta de a es, por lo tanto, 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 los inicios. Suponiendo un tiempo de inicio de la comunicación de y un tiempo de transmisión byte a byte de , la fase ascendente y descendente están limitadas a en un escenario sin canalización. ${\displaystyle \log _{2}p}$ ${\displaystyle PE_{0}}$ ${\displaystyle PE_{\mathbb {root} }}$ ${\displaystyle \log _{2}p-1}$ ${\displaystyle \log _{2}p-1}$ ${\displaystyle T_{\mathbb {start} }}$ ${\displaystyle T_{\mathbb {byte} }}$ ${\displaystyle (2\log _{2}p-2)(T_{\mathbb {start} }+n\cdot T_{\mathbb {byte} })}$

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

El algoritmo se puede optimizar aún más haciendo uso de la comunicación full-duplex o modelo telefónico y superponiendo la fase ascendente y descendente. ^[17]

Estructuras de datos

Cuando un conjunto de datos se puede actualizar dinámicamente, se puede almacenar en una estructura de datos de árbol 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. ^[18] Sin embargo, un artículo anterior de 1982 ^[19] presenta una estructura de datos llamada Árbol de sumas parciales (consulte la Sección 5.1) que parece superponerse a los árboles 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 . ^[20]

Aplicaciones

El ordenamiento por conteo es un algoritmo de ordenamiento de números enteros que utiliza la suma de prefijos de un histograma de frecuencias de claves para calcular la posición de cada clave en la matriz de salida ordenada. Se ejecuta en tiempo lineal para claves enteras que son más pequeñas que el número de elementos y se utiliza con frecuencia como parte del ordenamiento por radix , un algoritmo rápido para ordenar números enteros que están menos restringidos en magnitud. ^[1]

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

Una aplicación temprana de los algoritmos de suma de prefijos en paralelo 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 en 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 entonces como el o exclusivo de dos bits de entrada con el bit de acarreo correspondiente. Al utilizar un circuito que realiza las operaciones del algoritmo de suma de prefijo en paralelo, es posible diseñar un sumador que utiliza O ( n ) puertas lógicas y O (log n ) pasos de tiempo. ^{[3] [10] [11]}

En el modelo de computación de máquina de acceso aleatorio paralelo , las sumas de prefijos se pueden utilizar para simular algoritmos paralelos que suponen la capacidad de varios procesadores para acceder a la misma celda de memoria al mismo tiempo, en máquinas paralelas que prohíben el acceso simultáneo. Por medio de una red de ordenación , un conjunto de solicitudes de acceso a memoria paralelas se puede ordenar en una secuencia de modo que los accesos a la misma celda sean contiguos dentro de la secuencia; las operaciones de escaneo se pueden utilizar entonces para determinar cuáles de los accesos logran escribir en sus celdas solicitadas y para distribuir los resultados de las operaciones de lectura de memoria a varios procesadores que solicitan el mismo resultado. ^[21]

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

En la construcción de códigos Gray , secuencias de valores binarios con la propiedad de que los valores de secuencia consecutivos difieren entre sí en una sola posición de bit, un número n se puede convertir en el valor de código Gray en la posición n de la secuencia simplemente tomando el o exclusivo de n y n /2 (el número formado al desplazar n a la derecha en una sola posición de bit). La operación inversa, decodificar un valor codificado en Gray x en un número binario, es más complicada, pero se puede expresar como la suma de prefijo de los bits de  x , donde cada operación de suma dentro de la suma de prefijo se realiza módulo dos. Una suma de prefijo de este tipo se puede realizar de manera eficiente utilizando las operaciones booleanas bit a bit disponibles en las computadoras modernas, calculando el o exclusivo de 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. ^[24]

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

La suma de prefijos se utiliza para equilibrar la carga como un algoritmo de bajo costo para distribuir el trabajo entre múltiples procesadores, donde el objetivo primordial es lograr una cantidad igual de trabajo en cada procesador. Los algoritmos utilizan 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 procesador con el número . ^[27] 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 corta en un número de piezas, correspondiente al número de procesadores. ^[28] ${\displaystyle [{\frac {prefixSumValue_{i}}{{totalWork}/{numberOfProcessors}}}]}$

Véase también

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

Referencias

1. Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001), "8.2 Ordenamiento por conteo", Introducción a los algoritmos (2.ª ed.), MIT Press y McGraw-Hill , págs. 168-170, ISBN 0-262-03293-7.
2. Cole, Richard; Vishkin, Uzi (1986), "Lanzamiento de moneda determinista con aplicaciones para la clasificación óptima de listas paralelas", Información y control , 70 (1): 32–53, doi : 10.1016/S0019-9958(86)80023-7
3. Ladner, RE; Fischer, MJ (1980), "Cálculo de prefijos paralelos", Journal of the ACM , 27 (4): 831–838, CiteSeerX 10.1.1.106.6247 , doi :10.1145/322217.322232, MR  0594702, S2CID  207568668 .
4. Tarjan, Robert E. ; Vishkin, Uzi (1985), "Un algoritmo eficiente de biconectividad paralela", SIAM Journal on Computing , 14 (4): 862–874, CiteSeerX 10.1.1.465.8898 , doi :10.1137/0214061 .
5. Lakshmivarahan, S.; Dhall, SK (1994), Paralelismo en el problema del prefijo , Oxford University Press , ISBN 0-19508849-2.
6. Blelloch, Guy (2011), Sumas de prefijos y sus aplicaciones (notas de clase) (PDF) , Carnegie Mellon University.
7. Callahan, Paul; Kosaraju, S. Rao (1995), "Una descomposición de conjuntos de puntos multidimensionales con aplicaciones a k-vecinos más cercanos y campos potenciales de n-cuerpos", Journal of the ACM , 42 (1): 67–90, doi : 10.1145/200836.200853 , S2CID  1818562.
8. "Joyas de la GPU 3".
9. Hillis, W. Daniel; Steele, Jr., Guy L. (diciembre de 1986). "Algoritmos de datos paralelos". Comunicaciones de la ACM . 29 (12): 1170–1183. doi : 10.1145/7902.7903 .
10. Ofman, Yu. (1962), Об алгоритмической сложности funciones de disco, Doklady Akademii Nauk SSSR (en ruso), 145 (1): 48–51, SEÑOR  0168423Traducción al español, "Sobre la complejidad algorítmica de funciones discretas", Soviet Physics Doklady 7 : 589–591 1963.
11. Khrapchenko, VM (1967), "Estimación asintótica del tiempo de adición de un sumador paralelo", Problemy Kibernet. (en ruso), 19 : 107-122Traducción al inglés en Syst. Theory Res. 19 ; 105–122, 1970.
12. Sengupta, Shubhabrata; Harris, Mark; Zhang, Yao; Owens, John D. (2007). Primitivas de escaneo para computación GPU. Proc. 22.º Simposio ACM SIGGRAPH/EUROGRAPHICS sobre hardware gráfico. págs. 97–106. Archivado desde el original el 3 de septiembre de 2014. Consultado el 29 de noviembre de 2007 .
13. Vishkin, Uzi (2003). Sumas de prefijo y su aplicación. Patente de EE. UU. 6.542.918.
14. Singler, Johannes. "MCSTL: La biblioteca de plantillas estándar multinúcleo" . Consultado el 29 de marzo de 2019 .
15. Singler, Johannes; Sanders, Peter; Putze, Felix (2007). "MCSTL: La biblioteca de plantillas estándar multinúcleo". Euro-Par 2007 Procesamiento paralelo . Apuntes de clase en informática. Vol. 4641. págs. 682–694. doi :10.1007/978-3-540-74466-5_72. ISBN 978-3-540-74465-8. ISSN  0302-9743.
16. Ananth Grama; Vipin Kumar; Anshul Gupta (2003). Introducción a la Computación Paralela. Addison-Wesley. págs.85, 86. ISBN 978-0-201-64865-2.
17. Sanders, Peter; Träff, Jesper Larsson (2006). "Algoritmos de prefijo paralelo (escaneo) para MPI". Avances recientes en máquinas virtuales paralelas e interfaces de paso de mensajes . Apuntes de clase en informática. Vol. 4192. págs. 49–57. doi :10.1007/11846802_15. ISBN 978-3-540-39110-4. ISSN  0302-9743.
18. Fenwick, Peter M. (1994), "Una nueva estructura de datos para tablas de frecuencia acumulada", Software: Practice and Experience , 24 (3): 327–336, doi :10.1002/spe.4380240306, S2CID  7519761
19. Shiloach, Yossi; Vishkin, Uzi (1982b), "Un algoritmo de flujo máximo paralelo O ( n ²  log  n )", Journal of Algorithms , 3 (2): 128–146, doi :10.1016/0196-6774(82)90013-X
20. Szeliski, Richard (2010), "Tabla de áreas sumadas (imagen integral)", Computer Vision: Algorithms and Applications, Textos en Ciencias de la Computación, Springer, pp. 106-107, ISBN 9781848829350.
21. Vishkin, Uzi (1983), "Implementación de acceso simultáneo a direcciones de memoria en modelos que lo prohíben", Journal of Algorithms , 4 (1): 45–50, doi :10.1016/0196-6774(83)90033-0, MR  0689265.
22. Blelloch, Guy E. (1990). Modelos vectoriales para computación paralela de datos . Cambridge, MA: MIT Press. ISBN 026202313X.OCLC 21761743  .
23. Leiserson, Charles E .; Abuhamdeh, Zahi S.; Douglas, David C.; Feynman, Carl R.; Ganmukhi, Mahesh N.; Hill, Jeffrey V.; Hillis, W. Daniel ; Kuszmaul, Bradley C.; St. Pierre, Margaret A. (15 de marzo de 1996). "La arquitectura de red de la máquina de conexión CM-5". Revista de computación paralela y distribuida . 33 (2): 145–158. doi :10.1006/jpdc.1996.0033. ISSN  0743-7315.
24. Warren, Henry S. (2003), El deleite del hacker, Addison-Wesley, pág. 236, ISBN 978-0-201-91465-8.
25. Eğecioğlu, O.; Gallopoulos, E.; Koç, C. (1990), "Un método paralelo para la interpolación rápida y práctica de Newton de alto orden", BIT Computer Science and Numerical Mathematics , 30 (2): 268–288, doi :10.1007/BF02017348, S2CID  9607531.
26. Eğecioğlu, O.; Gallopoulos, E.; Koç, C. (1989), "Cálculo rápido de diferencias divididas e interpolación de Hermite paralela", Journal of Complexity , 5 (4): 417–437, doi :10.1016/0885-064X(89)90018-6
27. Becker, Aaron; Zheng, Gengbin; Kalé, Laxmikant V. (2011). "Equilibrio de carga, memoria distribuida". Enciclopedia de computación paralela . Boston, MA: Springer US. p. 1046. doi :10.1007/978-0-387-09766-4_504. ISBN 978-0-387-09765-7.
28. Sanders, Peter; Mehlhorn, Kurt; Dietzfelbinger, Martin; Dementiev, Roman (2019). "Load Balancing" (PDF) . Algoritmos secuenciales y paralelos y estructuras de datos . Cham: Springer International Publishing. pág. 419–434. doi :10.1007/978-3-030-25209-0_14. ISBN 978-3-030-25208-3.

Enlaces externos

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