En ciencias de la computación , la suma de prefijo , suma acumulativa , escaneo incluido , o simplemente exploración de una secuencia de números x 0 , x 1 , x 2 , ... es una segunda secuencia de números y 0 , y 1 , y 2 ,. .. , las sumas de prefijos ( totales acumulados ) de la secuencia de entrada:
- y 0 = x 0
- y 1 = x 0 + x 1
- y 2 = x 0 + x 1 + x 2
- ...
Por ejemplo, las sumas de prefijo de los números naturales son los números triangulares :
números de entrada 1 2 3 4 5 6 ... sumas de prefijo 1 3 6 10 15 21 ...
Las sumas de prefijos son triviales para calcular en modelos secuenciales de cálculo, 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 una primitiva útil en ciertos algoritmos como el ordenamiento de conteo , [1] [2] y forman la base de la función de escaneo de orden superior en los lenguajes de programación funcionales . Las sumas de prefijos también se han estudiado mucho en algoritmos paralelos , tanto como un problema de prueba a resolver como como una primitiva útil para ser utilizada como subrutina en otros algoritmos paralelos. [3] [4] [5]
De manera abstracta, una suma de prefijo requiere solo un operador asociativo binario ⊕ , lo que lo 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 prefijos 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 prefijos o la suma parcial forman operadores lineales en los espacios vectoriales de secuencias finitas o infinitas; sus inversos son operadores de diferencias finitas .
Función de escaneo 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 denomina escaneo y está estrechamente relacionada con la operación de plegado . Tanto las operaciones de escaneo como las 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 solo devuelve el resultado final. Por ejemplo, la secuencia de números factoriales puede generarse mediante un escaneo de los números naturales usando la multiplicación en lugar de la suma:
números de entrada 1 2 3 4 5 6 ... productos de prefijo 1 2 6 24 120 720 ...
Escaneos inclusivos y exclusivos
Las implementaciones del lenguaje de programación y de la biblioteca del escaneo 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 −1 " separado con el que se puede inicializar el escaneo. 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 que ⊕ sea máx .
La siguiente tabla enumera ejemplos de las funciones de escaneo inclusivas y exclusivas que proporcionan algunos lenguajes de programación y bibliotecas:
Algoritmos paralelos
Hay dos algoritmos clave para calcular una suma de prefijo en paralelo. El primero ofrece un tramo más corto y más paralelismo, pero no es eficiente en el trabajo. El segundo es eficiente en el trabajo, pero requiere el doble de espacio y ofrece menos paralelismo. Estos se presentan a su vez a continuación.
Algoritmo 1: tramo más corto, más paralelo
Hillis y Steele presentan el siguiente algoritmo de suma de prefijos paralelos: [8]
- porahacer
- porahacer en paralelo
- Siluego
- demás
- Siluego
- porahacer en paralelo
En lo anterior, la notación significa el valor del j- ésimo elemento de la matriz x en el paso de tiempo i .
Con un solo procesador, este algoritmo se ejecutaría en un tiempo O ( n log n ) . Sin embargo, si la máquina tiene al menos n procesadores para realizar el ciclo interno en paralelo, el algoritmo como un todo se ejecuta en el tiempo O (log n ) , el número de iteraciones del ciclo externo.
Algoritmo 2: eficiente en el trabajo
Una suma de prefijos paralelos eficiente en el trabajo se puede calcular mediante los siguientes pasos. [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 = x 0 + x 1 , z 1 = x 2 + x 3 , etc.
- Calcule recursivamente la suma del prefijo w 0 , w 1 , w 2 , ... de la secuencia z 0 , z 1 , z 2 , ...
- Exprese cada término de la secuencia final y 0 , y 1 , y 2 , ... como la suma de hasta dos términos de estas secuencias intermedias: y 0 = x 0 , y 1 = z 0 , y 2 = z 0 + x 2 , y 3 = w 0 , etc. Después del primer valor, cada número sucesivo y i se copia desde una posición a la mitad de la secuencia w , o se agrega el valor anterior a un valor en la secuencia x .
Si la secuencia de entrada tiene n pasos, entonces la recursividad 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 en 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 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 toma exactamente log 2 n pasos, mientras que el segundo requiere 2 log 2 n - 2 pasos. Para los ejemplos de 16 entradas ilustrados, el algoritmo 1 es un paralelo de 12 vías (49 unidades de trabajo divididas por un tramo de 4) mientras que el algoritmo 2 es solo un paralelo de 4 vías (26 unidades de trabajo divididas por un tramo de 6). Sin embargo, el algoritmo 2 es eficiente en el trabajo: realiza solo un factor constante (2) de la cantidad de trabajo requerido por el algoritmo secuencial, mientras que el algoritmo 1 es ineficaz en el trabajo: realiza asintóticamente más trabajo (un factor logarítmico) del requerido. secuencialmente. En consecuencia, es probable que el algoritmo 1 funcione mejor cuando hay abundante paralelismo disponible, 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 . [11] La idea de construir en hardware una unidad funcional dedicada a calcular la suma de prefijo multiparámetro fue patentada por Uzi Vishkin . [12]
Muchas implementaciones paralelas siguen un procedimiento de dos pasadas donde las sumas de prefijos parciales se calculan en la primera pasada en cada unidad de procesamiento; la suma del prefijo de estas sumas parciales se calcula y se retransmite a las unidades de procesamiento para una segunda pasada utilizando el prefijo ahora conocido como valor inicial. Asintóticamente, este método toma aproximadamente dos operaciones de lectura y una operación de escritura por elemento.
Implementaciones concretas de algoritmos de suma de prefijos
Una implementación de un algoritmo de suma de prefijos en paralelo, como 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 trabajan en memoria compartida , así como algoritmos que son adecuados para plataformas que usan memoria distribuida , confiando en el paso de mensajes como la única forma de comunicación entre procesos.
El siguiente algoritmo asume 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), [13] [14] una implementación paralela de la biblioteca de plantillas estándar C ++ que proporciona versiones adaptadas para la computación paralela de varios algoritmos.
Para calcular simultáneamente la suma del prefijo sobre elementos de datos con elementos de procesamiento, los datos se dividen en bloques, cada uno conteniendo elementos (por simplicidad asumimos 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.
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 prefijos solo se calculan como compensaciones de las sumas de prefijos de los bloques sucesivos y, por definición, el último bloque no es exitoso.
La las compensaciones 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 sucesivas. Para siendo un número pequeño, es más rápido hacerlo de forma secuencial, para una gran , este paso también podría realizarse en paralelo.
Se realiza un segundo barrido. Esta vez, el primer bloque no tiene que procesarse, ya que no necesita tener en cuenta el desplazamiento de un bloque anterior. Sin embargo, en este barrido se incluye el último bloque en su lugar y las sumas de prefijo para cada bloque se calculan teniendo en cuenta las compensaciones de bloque de suma de prefijo calculadas en el barrido anterior.
function prefix_sum ( elementos ) { n : = tamaño ( elementos ) p : = número de elementos de procesamiento prefix_sum : = [ 0 .. .0 ] de tamaño n no paralelas i = 0 a p - 1 { // i: = índice de PE actual de j = i * n / ( p + 1 ) a ( i + 1 ) * n / ( p + 1 ) - 1 hacer { / / Esto solo almacena la suma del prefijo de los bloques locales store_prefix_sum_with_offset_in ( elementos , 0 , prefix_sum ) } } x = 0 para i = 1 a p { x + = prefix_sum [ i * n / ( p + 1 ) - 1 ] // Construir la suma prefijo sobre la primera p bloques prefix_sum [ i * n / ( p + 1 )] = x / / Guarde los resultados para usarlos como compensaciones en el segundo barrido } no paralelas i = 1 a p { // i: = índice de PE actual de j = i * n / ( p + 1 ) a ( i + 1 ) * n / ( p + 1 ) - 1 do { compensado : = prefix_sum [ i * n / ( p + 1 )] // Calcula la suma del prefijo tomando la suma de los bloques anteriores como offset store_prefix_sum_with_offset_in ( elementos , offset , prefix_sum ) } } return prefix_sum }
Memoria distribuida: algoritmo Hypercube
El algoritmo Hypercube Prefix Sum [15] está bien adaptado para plataformas de memoria distribuida y funciona con el intercambio de mensajes entre los elementos de procesamiento. Se asume tener elementos del procesador (PE) que participan en el algoritmo igual al número de esquinas en un dimensional hipercubo .
A lo largo del algoritmo, cada PE se ve como una esquina en un hipotético hipercubo con conocimiento de la suma total del prefijo así como la suma del prefijo de todos los elementos hasta él mismo (según los índices ordenados entre los PE), ambos en su propio hipercubo.
- 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.
- El algoritmo continúa unificando hipercubos que son adyacentes a lo largo de una dimensión. Durante cada unificación, se intercambia y agrega entre los dos hipercubos, lo que mantiene el invariante de que todos los PE en las esquinas de este nuevo hipercubo almacenan la suma total del prefijo de este hipercubo recién unificado en su variable . Sin embargo, solo el hipercubo que contiene los PE con un índice más alto también agrega esto a su variable local , manteniendo el invariante que solo almacena el valor de la suma del prefijo de todos los elementos en los PE con índices menores o iguales a su propio índice.
en un -híper cubo dimensional con PE en las esquinas, el algoritmo debe repetirse veces para tener el los hipercubos de dimensión cero se unifican en uno -Hipercubo dimensional. Suponiendo un modelo de comunicación dúplex donde el de dos PE adyacentes en diferentes hipercubos se pueden intercambiar en ambas direcciones en un paso de comunicación, esto significa startups de comunicación.
i : = Índice de propio procesador de elemento ( PE ) m : = prefijo suma de locales elementos de este PE d : = número de dimensiones de la hiper cubox = m ; // Invariante: El prefijo suma a este PE en el subcubo actual σ = m ; // Invariante: la suma de prefijo de todos los elementos en el subcubo actualfor ( k = 0 ; k <= d - 1 ; k ++ ) { y = σ @ PE ( i xor 2 ^ k ) // Obtenga la suma total del prefijo del subcubo opuesto a lo largo de la dimensión k σ = σ + y // Agrega la suma del prefijo de ambos subcubos if ( i & 2 ^ k ) { x = x + y // Solo agregue la suma del prefijo del otro subcubo, si este PE es el índice más alto. } }
Tamaños de mensajes grandes: árbol binario canalizado
El algoritmo de árbol binario canalizado [16] es otro algoritmo para plataformas de memoria distribuida que es especialmente adecuado para mensajes de gran tamaño.
Como el algoritmo del hipercubo, asume una estructura de comunicación especial. Los elementos de procesamiento (PE) se organizan hipotéticamente en un árbol binario (por ejemplo, un árbol de Fibonacci) con numeración infija de acuerdo con su índice dentro de los PE. La comunicación en un árbol de este tipo siempre se produce 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 son menos que y los índices de todos los nodos en el subárbol derecho son mayores que . Índice de los padres es mayor que cualquiera de los índices de PE j 's subárbol si PE j es un hijo izquierdo y el más pequeño si PE j es un hijo derecho. Esto permite el siguiente razonamiento:
- La suma del prefijo local del subárbol izquierdo debe agregarse para calcular la suma del prefijo local de PE j.
- La suma del prefijo local del subárbol derecho debe agregarse para calcular la suma del prefijo local de PE de nivel superior h que se alcanzan en una ruta que contiene una conexión secundaria izquierda (lo que significa).
- La suma total del prefijo de PE j es necesario para calcular las sumas totales de prefijos en el subárbol derecho (p. ej. para el nodo de índice más alto del subárbol).
- PE j debe incluir la suma total del prefijo del primer nodo de orden superior que se alcanza a través de una ruta ascendente que incluye una conexión secundaria derecha para calcular su suma de prefijo total.
Tenga en cuenta la distinción entre sumas de prefijo local de subárbol y total. Los puntos dos, tres y cuatro pueden hacer creer que formarían una dependencia circular, pero este no es el caso. Los PE de nivel inferior pueden requerir la suma de prefijo total de los PE de nivel superior para calcular su suma de prefijo total, pero los PE de nivel superior solo requieren sumas de prefijos locales de subárbol para calcular su suma de prefijo total. El nodo raíz como nodo de nivel más alto solo requiere la suma de prefijo local de su subárbol izquierdo para calcular su propia suma de prefijo. Cada PE en la ruta desde PE 0 a la PE raíz solo requiere la suma de prefijo local de su subárbol izquierdo para calcular su propia suma de prefijo, mientras que cada nodo en la ruta desde PE p-1 (último PE) a la raíz PE requiere la suma de prefijo total de su padre para calcular su propia suma de prefijo total.
Esto conduce a un algoritmo de dos fases:
Fase ascendente
Propagar la suma del prefijo local del subárbola su padre para cada PE j .
Fase descendente
Propagar la suma de prefijo total exclusivo (PE j exclusivo así como los PE en su subárbol izquierdo)de todos los PE de índice más bajo que no están incluidos en el subárbol direccionado de PE j a PE de nivel inferior en el subárbol hijo izquierdo de PE j . Propagar la suma del prefijo inclusivoal subárbol hijo derecho de PE j .
Tenga en cuenta que el algoritmo se ejecuta en paralelo en cada PE y los PE se bloquearán al recibirlos hasta que sus hijos / padres les proporcionen los paquetes.
k : = número de paquetes en un mensaje m de un PE m @ { izquierda , derecha , padre , esto } : = // Mensajes en los diferentes PEx = m @ esto// Fase ascendente - Calcular sumas de prefijos locales del subárbol para j = 0 a k - 1 : // Canalización: Para cada paquete de un mensaje si hasLeftChild : bloqueo de recepción m [ j ] @ left // Esto reemplaza el m [j] local con la m [j] recibida // Suma de prefijo local inclusivo agregado de los PE de índice inferior x [ j ] = m [ j ] ⨁ x [ j ] if hasRightChild : bloqueando recibir m [ j ] @ right // No agregamos m [j] en la suma del prefijo local, ya que los hijos correctos tienen índices más altos PEs envían x [ j ] ⨁ m [ j ] al padre else : send x [ j ] a los padres// Fase descendente para j = 0 a k - 1 : m [ j ] @ this = 0 if hasParent : bloqueando recibir m [ j ] @ parent // Para un hijo izquierdo m [j] es la suma del prefijo exclusivo de los padres, para un hijo derecho la suma del prefijo inclusivo x [ j ] = m [ j ] ⨁ x [ j ] enviar m [ j ] a la izquierda // La suma total del 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 del prefijo de todos los PE más pequeños o iguales que este PE
Canalización
Si el mensaje de longitud puede dividirse en Los paquetes y el operador ⨁ se pueden utilizar en cada uno de los paquetes de mensajes correspondientes por separado, es posible la canalización . [dieciséis]
Si el algoritmo se utiliza 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 están esperando. Si hay elementos de procesamiento y se utiliza un árbol binario equilibrado, el árbol tiene niveles, la longitud del camino desde 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 se limita a Inauguración. Suponiendo un tiempo de inicio de la comunicación de y un tiempo de transmisión bytewise de , la fase ascendente y descendente se limitan a en un escenario no canalizado.
Tras la división en k paquetes, cada uno de tamaño y enviándolos por separado, el primer paquete todavía necesita para 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 funcionar en paralelo y cada tercera operación de comunicación (recibir a la izquierda, recibir a la derecha, enviar a los padres) envía un paquete al siguiente nivel, de modo que una fase se pueda completar en las operaciones de comunicación y ambas fases juntas necesitan que es favorable para mensajes de gran tamaño .
El algoritmo se puede optimizar aún más haciendo uso de comunicación de modelo telefónico o full-duplex y superponiendo las fases ascendente y descendente. [dieciséis]
Estructuras de datos
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. [17] Sin embargo, un artículo anterior de 1982 [18] presenta una estructura de datos llamada Árbol de Sumas Parciales (ver Sección 5.1) que parece superponerse a los árboles de Fenwick; en 1982, el término prefijo-suma 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 subarreglos rectangulares arbitrarios. Esta puede ser una primitiva útil en las operaciones de convolución de imágenes . [19]
Aplicaciones
La ordenación por recuento es un algoritmo de ordenación de enteros que utiliza la suma de prefijo de un histograma de frecuencias clave 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 usa con frecuencia como parte de la ordenación por base , un algoritmo rápido para ordenar números enteros que tienen una magnitud menos restringida. [1]
La clasificación de la lista , 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. dado por el valor de la suma de su prefijo; Al combinar la clasificación de listas, sumas de prefijos y recorridos de Euler , muchos problemas importantes en los á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 acarreo de bits de la suma se puede representar como una operación de exploración 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. Entonces, cada bit del número de salida se puede encontrar como el exclusivo o de dos bits de entrada con el bit de acarreo correspondiente. Mediante el uso de un circuito que realiza las operaciones del algoritmo de suma prefijo paralelo, es posible diseñar un sumador que los usos de O ( n ) puertas lógicas y O (log n ) pasos de tiempo. [3] [9] [10]
En el modelo de computación de máquina de acceso aleatorio en paralelo , las sumas de prefijos se pueden usar para simular algoritmos paralelos que asumen la capacidad de que múltiples procesadores accedan 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 clasificación , se puede ordenar un conjunto de solicitudes de acceso a la memoria en paralelo en una secuencia de modo que los accesos a la misma celda sean contiguos dentro de la secuencia; Las operaciones de exploración se pueden utilizar para determinar cuál de los accesos tiene éxito en la escritura en las celdas solicitadas y para distribuir los resultados de las operaciones de lectura de memoria a varios procesadores que solicitan el mismo resultado. [20]
En el Ph.D. de Guy Blelloch . tesis, [21] las operaciones de prefijo en paralelo forman parte de la formalización del modelo de paralelismo de datos proporcionado por máquinas como la Connection Machine . La máquina de conexión CM-1 y CM-2 proporcionaron una red hipercúbica en la que se pudo implementar el algoritmo 1 anterior, mientras que el CM-5 proporcionó una red dedicada para implementar el algoritmo 2. [22]
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 posición de un solo bit, un número n se puede convertir en el valor del código Gray en la posición n de la secuencia simplemente tomando el valor exclusivo o de n y n / 2 (el número formado al desplazar n hacia la derecha en una posición de un solo bit). La operación inversa, decodificar un valor x codificado en Gray en un número binario, es más complicada, pero puede expresarse 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 exclusivo o de x con cada uno de los números formados al desplazar x hacia la izquierda en un número de bits que es una potencia de dos. . [23]
El prefijo paralelo (usando la multiplicación como operación asociativa subyacente) también se puede usar para construir algoritmos rápidos para la interpolación de polinomios paralelos . En particular, se puede utilizar para calcular los coeficientes de diferencia dividida de la forma de Newton del polinomio de interpolación. [24] 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 los algoritmos paralelos para los sistemas de Vandermonde . [25]
Ver también
- Computación de propósito general en unidades de procesamiento de gráficos
Referencias
- ↑ a b Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2001), "8.2 Ordenar contando", Introducción a los algoritmos (2ª ed.), MIT Press y McGraw-Hill , págs. 168-170, ISBN 0-262-03293-7.
- ^ Cole, Richard; Vishkin, Uzi (1986), "Lanzamiento de moneda determinista con aplicaciones para la clasificación de lista paralela óptima", Información y control , 70 (1): 32-53, doi : 10.1016 / S0019-9958 (86) 80023-7
- ^ a b c d e Ladner, RE; Fischer, MJ (1980), "Cálculo de prefijos en paralelo", Journal of the ACM , 27 (4): 831–838, CiteSeerX 10.1.1.106.6247 , doi : 10.1145 / 322217.322232 , MR 0594702.
- ^ a b c Tarjan, Robert E .; Vishkin, Uzi (1985), "Un algoritmo de biconnectividad paralela eficiente", SIAM Journal on Computing , 14 (4): 862–874, doi : 10.1137 / 0214061 CS1 maint: parámetro desalentado ( enlace ).
- ^ Lakshmivarahan, S .; Dhall, SK (1994), Paralelismo en el problema del prefijo , Oxford University Press , ISBN 0-19508849-2.
- ^ Blelloch, Guy (2011), Sumas de prefijos y sus aplicaciones (Notas de clase) (PDF) , Carnegie Mellon University.
- ^ 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.
- ^ Hillis, W. Daniel; Steele, Jr., Guy L. (diciembre de 1986). "Algoritmos de datos en paralelo". Comunicaciones de la ACM . 29 (12): 1170-1183. doi : 10.1145 / 7902.7903 .
- ^ a b Ofman, Yu. (1962),Об алгоритмической сложности дискретных функций, Doklady Akademii Nauk SSSR (en ruso), 145 (1): 48–51, MR 0168423 CS1 maint: parámetro desalentado ( enlace ). Traducción al inglés, "Sobre la complejidad algorítmica de las funciones discretas", Física soviética Doklady 7 : 589–591 1963.
- ^ a b Khrapchenko, VM (1967), "Estimación asintótica del tiempo de adición de un sumador paralelo", Problemy Kibernet. (en ruso), 19 : 107–122. Traducción al inglés en Syst. Teoría Res. 19 ; 105-122, 1970.
- ^ Sengupta, Shubhabrata; Harris, Mark; Zhang, Yao; Owens, John D. (2007). Escanee primitivas para computación con 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 .
- ^ Vishkin, Uzi (2003). Prefijos de sumas y aplicación de las mismas . Patente de Estados Unidos 6.542.918.
- ^ Singler, Johannes. "MCSTL: la biblioteca de plantillas estándar de varios núcleos" . Consultado el 29 de marzo de 2019 .
- ^ Singler, Johannes; Sanders, Peter; Putze, Felix (2007). "MCSTL: la biblioteca de plantillas estándar de varios núcleos". Procesamiento paralelo Euro-Par 2007 . Apuntes de conferencias en Ciencias de la Computación. 4641 . págs. 682–694. doi : 10.1007 / 978-3-540-74466-5_72 . ISBN 978-3-540-74465-8. ISSN 0302-9743 .
- ^ 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.
- ^ a b c Sanders, Peter; Träff, Jesper Larsson (2006). "Algoritmos de prefijo (escaneo) paralelo para MPI". Avances recientes en máquinas virtuales paralelas e interfaz de paso de mensajes . Apuntes de conferencias en Ciencias de la Computación. 4192 . págs. 49–57. doi : 10.1007 / 11846802_15 . ISBN 978-3-540-39110-4. ISSN 0302-9743 .
- ^ Fenwick, Peter M. (1994), "Una nueva estructura de datos para tablas de frecuencias acumulativas", Software: Practice and Experience , 24 (3): 327–336, doi : 10.1002 / spe.4380240306
- ^ Shiloach, Yossi; Vishkin, Uzi (1982b), "Un algoritmo de flujo máximo paralelo O ( n 2 log n )", Journal of Algorithms , 3 (2): 128-146, doi : 10.1016 / 0196-6774 (82) 90013-X
- ^ Szeliski, Richard (2010), "Tabla de áreas sumadas (imagen integral)", Visión por computadora: Algoritmos y aplicaciones , Textos en Ciencias de la Computación, Springer, pp. 106-107, ISBN 9781848829350.
- ^ 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 CS1 maint: parámetro desalentado ( enlace ).
- ^ Blelloch, Guy E. (1990). Modelos vectoriales para computación en paralelo de datos . Cambridge, MA: MIT Press. ISBN 026202313X. OCLC 21761743 .
- ^ 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 .
- ^ Warren, Henry S. (2003), Hacker's Delight , Addison-Wesley, pág. 236, ISBN 978-0-201-91465-8.
- ^ 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 , 30 (2): 268–288, doi : 10.1007 / BF02017348.
- ^ Eğecioğlu, O .; Gallopoulos, E .; Koç, C. (1989), "Cálculo rápido de diferencias divididas e interpolación paralela de Hermite", Journal of Complexity , 5 (4): 417–437, doi : 10.1016 / 0885-064X (89) 90018-6
enlaces externos
- Weisstein, Eric W. "Suma acumulativa" . MathWorld .