Algoritmos paralelos para encontrar el máximo
Sea n un entero positivo y sea a1, a2, ..., an
un vector de enteros. El problema del máximo es el de encontrar
el
mayor valor de entre a1, a2, ..., an.
En clase vimos un algoritmo que usa n procesadores en una arquitectura
PRAM para encontrar el máximo en log2 n pasos.
Después vimos
un algoritmo que usa n2 procesadores en una arquitectura
PRAM con
escritura común para encontrar el máximo en un
número constante de
pasos (digamos en 1 paso).
A continuación describimos un algoritmo que usa n procesadores
en una arquitectura PRAM con
escritura común para encontrar el máximo en log2
log2 n pasos. Suponga que k = log2 log2
n es un entero (dicho de otra forma, suponga que n = 22k).
Sea m la raíz cuadrada de n
(note que m = 22k-1).
Divida los n = m2 enteros en m grupos con m elementos cada
uno. De forma recursiva, utilice m procesadores para calcular el
máximo de cada grupo en k-1 = log2 log2 m
pasos. Al terminar esta etapa se tendrán m candidatos para ser
el máximo y se puede usar el algoritmo visto en clase para
calcular el máximo de ellos en 1 paso usando n = m2
procesadores. Todo el algoritmo se lleva (k-1)+1 = log2 log2
n pasos.
Pueden encontrar varios algoritmos paralelos que usan log2
log2 n pasos en el artículo O. Berkman, B. Schieber and U. Vishkin,
Optimal doubly logarithmic optimal parallel algorithms based on finding
all nearest smaller values.
J. of Algorithms 14 (1993) 344-370, el cual pueden descargar de aquí.