La ricorsione può essere eseguita in parallelo? Avrebbe senso?

Questo è possibile ma una pessima idea; calcolare il numero di thread che si generano quando si calcola fib (16), per esempio, e quindi moltiplicare per il costo di un thread. I fili sono follemente costosi; fare questo per il compito che descrivi è come assumere un dattilografo diverso per digitare ogni personaggio di un romanzo.

Detto questo, gli algoritmi ricorsivi sono spesso buoni candidati per la parallelizzazione, in particolare se dividono il lavoro in due lavori più piccoli che possono essere eseguiti indipendentemente. Il trucco è sapere quando smettere di parallelizzare.

In generale, si desidera parallelizzare solo attività "imbarazzanti in parallelo". Cioè attività che sono computazionalmente costose e possono essere calcolate indipendentemente . Molte persone dimenticano la prima parte. I thread sono così costosi che ha senso solo crearne uno quando c'è una enorme quantità di lavoro da fare per loro, e inoltre che puoi dedicare un intero processore alla thread . Se si dispone di 8 processori, fare 80 thread li costringerà a condividere il processore, rallentandone tremendamente ognuno di essi. È meglio fare solo 8 thread e consentire ad ognuno di accedere al 100% al processore quando si ha un'attività imbarazzante parallela da eseguire.

Le librerie come la Task Parallel Library in .NET sono progettate per capire automaticamente quanto il parallelismo sia efficiente; potresti considerare la ricerca del suo design se questo argomento ti interessa.

La domanda ha due risposte, in realtà.

La ricorsione può essere eseguita in parallelo? Avrebbe senso?

Sì, certo. Nella maggior parte dei casi (tutti?), Un algoritmo ricorsivo può essere riscritto in un modo senza ricorsione, portando ad un algoritmo che è abbastanza spesso facilmente parallelizzabile. Non sempre, ma spesso.

Pensa Quicksort, o iterando attraverso un albero delle directory. In entrambi i casi è possibile utilizzare una coda per contenere tutti i risultati intermedi. sottodirectory trovate. La coda può essere elaborata in parallelo, creando eventualmente più voci fino a quando l'attività è stata completata con successo.

Che dire dell'esempio di fib() ?

Sfortunatamente, la funzione Fibonacci è una cattiva scelta, perché i valori di input completati dipendono da risultati precedentemente calcolati. Questa dipendenza rende difficile farlo in parallelo se inizi ogni volta con 1 e 1 .

Tuttavia, se è necessario eseguire calcoli di Fibonacci più spesso, potrebbe essere una buona idea memorizzare (o memorizzare) i risultati precalcolati per evitare tutti i calcoli fino a quel momento. Il concetto alla base è abbastanza simile ai tavoli arcobaleno.

Diciamo che memorizzi nella cache ogni 10 coppie di numeri di Fibo fino a 10.000. Avvia questa routine di inizializzazione su un thread in background. Ora, se qualcuno chiede Fibo numero 5246, l'algoritmo preleva la coppia da 5240 e inizia il calcolo da quel punto in poi. Se la coppia 5240 non è ancora lì, aspettala.

In questo modo il calcolo di molti numeri di fibo scelti casualmente potrebbe essere fatto in modo molto efficiente e in parallelo, perché è molto improbabile che due thread debbano calcolare gli stessi numeri - e anche allora, non sarebbe un gran problema .

Certo che è possibile, ma per un esempio così piccolo (e, in effetti, per molti che sono molto più grandi) la quantità di codice di controllo plumbing / concorrenza che dovresti scrivere oscurerebbe il codice aziendale al punto che non sarebbe una buona idea a meno che tu non abbia davvero, davvero, davvero bisogno che i numeri di Fibonacci vengano calcolati molto velocemente.

È quasi sempre più leggibile e mantenibile la possibilità di formulare normalmente l'algoritmo e quindi lasciare un'estensione della libreria / lingua della concorrenza come TBB o GCD prenditi cura di come distribuire effettivamente i passaggi ai thread.

Nel tuo esempio stai calcolando fib (3) due volte, il che porta alla doppia esecuzione dell'intera fib (1) e fib (2), per numeri superiori è anche peggio.

Otterrai probabilmente velocità rispetto alla soluzione non ricorsiva, ma costerà molto di più in risorse (processori) che ne vale la pena.

Sì, può! Il mio esempio più semplice che posso darti è immaginare un albero binario di numeri. Per qualche motivo vuoi sommare tutti i numeri in un albero binario. Beh, per fare ciò, è necessario aggiungere valore del nodo radice al valore del nodo sinistro / destro .... ma il nodo stesso potrebbe essere la radice di un altro albero (un albero secondario dell'albero originale)
Invece di calcolare la somma del sottoalbero sinistro, quindi la somma del diritto ... quindi aggiungerli al valore della radice ... puoi calcolare la somma del sottoalbero sinistro e destro in parallelo.

Un problema è che l'algoritmo ricorsivo standard per la funzione fibonacci è semplicemente pessimo, dal momento che il numero di chiamate per calcolare fib (n) è uguale a fib (n), che è in rapida crescita. Quindi mi rifiuterei davvero di discuterne.

Diamo un'occhiata ad un algoritmo ricorsivo più ragionevole, Quicksort. Ordina un array facendo quanto segue: Se l'array è piccolo, ordinarlo usando Bubblesort, Insertion sort o altro. Altrimenti: scegli un elemento dell'array. Metti tutti gli elementi più piccoli da un lato, tutti gli elementi più grandi dall'altro lato. Ordina il lato con gli elementi più piccoli. Ordina il lato con gli elementi più grandi.

Per evitare una ricorsione arbitrariamente profonda, il metodo usuale è che la funzione di ordinamento rapido eseguirà una chiamata ricorsiva per il più piccolo dei due lati (quello con meno elementi) e gestirà il lato più grande stesso.

Ora hai un modo molto semplice per usare più thread: invece di fare una chiamata ricorsiva per ordinare il lato più piccolo, inizia una discussione; quindi ordina la metà più grande, quindi attendi che il filo finisca. Ma le discussioni iniziali sono costose. In questo modo si misura quanto tempo impiega in media per ordinare n elementi, rispetto al tempo necessario per creare un thread. Da ciò si trova il più piccolo n tale che valga la pena creare un nuovo thread. Quindi se il lato più piccolo che deve essere ordinato è inferiore a quella dimensione, si effettua una chiamata ricorsiva. Altrimenti, dividi quella metà in una nuova discussione.