Algoritmo paralelo para encontrar el tiempo máximo en usando procesadores

11

Se nos presentó en clase un algoritmo para encontrar el máximo en una matriz en paralelo en O(1) complejidad de tiempo con n2 computadoras.

El algoritmo fue:

Dado un conjunto A de longitud n:

  1. Haga una matriz B de longitud n e inicialícela con ceros con n computadoras.
  2. Compare cada 2 elementos y escriba 1 en B en el índice del mínimo con n2 computadoras.
  3. encuentre el índice con el 0 en A con n computadoras.

El profesor nos bromeó que podría hacerse con computadoras nlogn y con logn complejidad de tiempo.

Después de pensar mucho, no pude entender cómo hacerlo. ¿Alguna idea?

Gil
fuente

Respuestas:

9

Divida su matriz original en bloques de longitud . Ponga a cada procesador a cargo de cada bloque y encuentre el máximo utilizando el algoritmo habitual en time . Ahora necesitamos calcular el máximo de una matriz de longitud . Empareje los elementos y calcule los máximos por pares para reducir el tamaño de la matriz a la mitad. Repítalo veces para encontrar el máximo de toda la matriz.n/lognlognlognn/lognlogn

La misma idea también muestra que puede calcular el máximo en paralelo en tiempo constante usando computadoras para cada . (Ejercicio.)n1+ϵϵ>0

Yuval Filmus
fuente
El objetivo era encontrar un máximo en tiempo, noO(1)O(logn)
NightRa
Tómese la responsabilidad de demostrar un límite inferior de para el número de computadoras multiplicado por la complejidad del tiempo. Ω(n)
Yuval Filmus