Quanto velocemente si può ottenere "la ricerca del massimo in un array"?

Question

Questa domanda proviene da una discussione che è stata toccata da quest'altra domanda: Parallelize already linear-time algorithm. È non compiti.

Viene fornita una serie di numeri N e una macchina con processori P e una memoria condivisa CREW (lettura simultanea, memoria scrittura esclusiva).

Qual è il più stretto limite superiore sull'algoritmo più veloce per trovare il numero più grande nella matrice? [Ovviamente, anche: qual è l'algoritmo stesso?]

Non mi riferisco alla quantità totale di lavoro svolto [che può mai essere inferiore a O (N)].

Answer 1

Penso che sia O(N/P') + O(Log2(P')), dove P'=min{N,P}. I processori P' cercano max di N/P' elementi, seguiti da Log2 accoppiamenti a coppie eseguiti in parallelo. Le prime unioni P'/2 vengono eseguite da processori pari, next 'P'/4 '- da processori in posizioni divisibili per 8, quindi per 16 e così via.

ModificaP' viene introdotto per coprire il caso quando si dispone di più nodi del processore rispetto agli elementi che è necessario cercare.

Answer 2

ho il sospetto che ciò è O (N/P) + O (P)

• Condividere il lavoro tra i processori P ha un costo di O (P)
• combinando il lavoro svolto da P processori ha anche i costi di O (P)
• Un perfetto ricerca parallell di N elementi dai processori P ha costo di tempo di O (N/P)

mio algoritmo ingenuo sarebbe quello di

• voce scrittura 0 in una cella CREW etichettato come "risultato"
• inizio P ricerche completamente indipendenti, ciascuno attraverso 1/P esimo degli elementi N
• al termine di ogni spinloop utilizzo di ricerca CAS per sostituire "risultato" con risultato della ricerca parziale, se è più grande. (A seconda della definizione di CREW potrebbe non essere necessario lo spinloop)

Answer 3

Cook, Dwork e Reischuk hanno dimostrato che qualsiasi algoritmo CREW per trovare il massimo di n elementi deve essere eseguito in Omega (lg n), anche con un numero illimitato di processori e memoria illimitata. Se ricordo bene, nel loro articolo appare un algoritmo con un limite superiore corrispondente:

Stephen Cook, Cynthia Dwork e Rüdiger Reischuk. Limiti di tempo superiore e inferiore per macchine ad accesso casuale parallele senza scritture simultanee. SIAM Journal on Computing, 15 (1): 87-97, 1986.

Answer 4

Quello che segue è ottimale legato:

Se p = < n/log n si può fare a O (n/p) di tempo; altrimenti è O (log n) vale a dire quando p> n/log n non guadagni nulla rispetto a p = n/log n.

Proof - limite inferiore:

rivendicazione 1: Non si può mai fare più veloce di Ω (n/p), in quanto i processori p può dare solo aumento di velocità di p

rivendicazione 2: Non si può mai fare più veloce di Ω (log n), a causa del modello di CREW (vedere la carta di non perdonata); se si desidera verificare se un array 0-1 ha almeno un 1, è necessario O (log n) tempo.

Proof - limite superiore:

rivendicazione 3: È possibile trovare il massimo utilizzando n/log n processori e in O (log n)

Dimostrazione: E 'facile trovare la massima utilizzando i processori n e log n time; ma in effetti, in questo algoritmo la maggior parte dei processori è inattivo per la maggior parte del tempo; mediante un adeguato incastro a coda di rondine, (vedi ad esempio il libro sulla complessità di Papadimitriou) il loro numero può essere ridotto a n/log n.

---

Ora, dato inferiore a n/log n processori si possono dare lavoro assegnato a K processori a 1 processore, questo divide requisito processore da K e si moltiplica il tempo richiesto da K.

Sia K = (n/log n)/p; l'algoritmo precedente viene eseguito nel tempo O (K log n) = O (n/p) e richiede n/(log n * K) = p processori.

---

Modificato: Ho appena realizzato che quando p < = n/log n, l'algoritmo di dasblinkenlight ha lo stesso tempo di esecuzione asintotico:

n/p log + p < = n/p + log (n/log n) < = n/p + log n < = n/p + n/p < = 2n/p = O (n/p)

in modo da poter usare tale algoritmo, che ha complessità O (n/p) quando p < = n/log n e O (log n) altrimenti.

Answer 5

Per P = N^2 è O (1).

inizializzazione matrice booleana CannotBeMax [i] = FALSE

Proc (i, j) imposta CannotBeMax [i] = A [i] < A [j]

Max è A [CannotBeMax [i ] == FALSE]

Si noti che tutte le scritture simultanee tentano di scrivere informazioni identiche in modo che la risposta sia coerente, indipendentemente da quale operazione riesce.