Programmazione funzionale e architettura multicore

Question

Ho letto da qualche parte che la programmazione funzionale è adatta per sfruttare la tendenza multi-core nell'informatica. Non ho davvero avuto l'idea. È legato al calcolo lambda e all'architettura von neumann?

Answer 1

La programmazione funzionale minimizza o elimina gli effetti collaterali e quindi è più adatta alla programmazione distribuita. ovvero elaborazione multicore.

In altre parole, molti pezzi del puzzle possono essere risolti indipendentemente su nuclei separati contemporaneamente senza doversi preoccupare di un'operazione che influisce su un'altra quasi quanto fareste in altri stili di programmazione.

Answer 2

Una delle cose più difficili nella gestione dell'elaborazione parallela è il blocco delle strutture dati per prevenire la corruzione. Se due thread dovessero mutare contemporaneamente una struttura di dati senza averla bloccata perfettamente, si potrebbe ottenere qualsiasi cosa, dai dati non validi a un deadlock.

Al contrario, i linguaggi di programmazione funzionale tendono a enfatizzare i dati immutabili. Qualsiasi stato viene mantenuto separato dalla logica e una volta creata una struttura dati non può essere modificata. La necessità di blocco è notevolmente ridotta.

Un altro vantaggio è che alcuni processi che si parallelizzano molto facilmente, come l'iterazione, sono astratti in funzioni. In C ++, potresti avere un ciclo for che esegue l'elaborazione dei dati su ogni elemento in un elenco. Ma il compilatore non ha modo di sapere se quelle operazioni possono essere eseguite in modo sicuro in parallelo - forse il risultato di una dipende da quello precedente. Quando viene utilizzata una funzione come map () o reduce () , il compilatore può sapere che non c'è dipendenza tra le chiamate. È quindi possibile elaborare più articoli contemporaneamente.

Answer 3

  

Ho letto da qualche parte che la programmazione funzionale è adatta per sfruttare la tendenza multi-core nell'informatica ... Non ho davvero avuto l'idea. È legato al calcolo lambda e all'architettura von neumann?

L'argomento dietro la convinzione che hai citato è che la programmazione puramente funzionale controlla gli effetti collaterali che rendono molto più facile e sicuro introdurre il parallelismo e, quindi, che i linguaggi di programmazione puramente funzionali dovrebbero essere vantaggiosi nel contesto dei computer multicore.

Sfortunatamente, questa convinzione era stata da tempo smentita per diversi motivi:

• Le prestazioni assolute di dati puramente funzionali le strutture sono povere . Quindi la programmazione puramente funzionale è un grande passo iniziale nella direzione sbagliata nel contesto delle prestazioni (che è l'unico scopo della programmazione parallela).

• Le strutture di dati puramente funzionali si ridimensionano perché stressano le risorse condivise tra cui allocatore / GC e larghezza di banda della memoria principale. I programmi puramente parallelizzati, quindi, spesso ottengono scarse accelerazioni all'aumentare del numero di core.

• La programmazione puramente funzionale rende le prestazioni imprevedibili. Quindi i veri programmi puramente funzionali vedono spesso le prestazioni degradazione quando parallelizzate perché la granularità è effettivamente casuale.

Ad esempio, il bastardo quicksort a due righe spesso citato dalla comunità Haskell in genere corre migliaia di volte più lentamente di un vero quicksort sul posto scritto in un linguaggio più convenzionale come F #. Inoltre, sebbene sia possibile parallelizzare facilmente l'elegante programma Haskell, è improbabile che si verifichi alcun miglioramento delle prestazioni perché tutte le copie non necessarie rendono un singolo core saturo l'intera larghezza di banda della memoria principale di una macchina multicore, rendendo inutile il parallelismo. In effetti, nessuno è mai riuscito a scrivere in Haskell alcun tipo di ordinamento parallelo generico che sia competitivo. I tipi più avanzati forniti dalla libreria standard di Haskell sono in genere centinaia di volte più lenti delle alternative convenzionali.

Tuttavia, la definizione più comune di programmazione funzionale come uno stile che enfatizza l'uso di funzioni di prima classe risulta in realtà molto utile nel contesto della programmazione multicore perché questo paradigma è ideale per il factoring di programmi paralleli. Ad esempio, vedere la nuova funzione Parallel.For di ordine superiore nello spazio dei nomi System.Threading.Tasks in .NET 4.

Answer 4

Quando non ci sono effetti collaterali, l'ordine di valutazione non ha importanza. È quindi possibile valutare le espressioni in parallelo.

Answer 5

L'argomento di base è che è difficile parallelizzare automaticamente linguaggi come C / C ++ / etc perché le funzioni possono impostare variabili globali. Considera due chiamate di funzione:

a = foo(b, c);
d = bar(e, f);

Sebbene foo e bar non abbiano argomenti in comune e l'uno non dipenda dal codice di ritorno dell'altro, potrebbero comunque avere dipendenze perché foo potrebbe impostare una variabile globale (o un altro effetto collaterale) da cui dipende la barra.

I linguaggi funzionali garantiscono che foo e bar siano indipendenti: non ci sono globi e effetti collaterali. Pertanto foo and bar possono essere eseguiti in sicurezza su core diversi, automaticamente, senza l'intervento del programmatore.

Answer 6

Tutte le risposte di cui sopra vanno all'idea chiave che "nessuna memoria mutabile condivisa" è un attivatore chiave per eseguire in parallelo parti di un programma. In realtà non risolve il problema altrettanto difficile di trovare cose da eseguire in parallelo. Ma le espressioni più chiare tipiche della funzionalità nei linguaggi funzionali rendono teoricamente più semplice estrarre il parallelismo da un'espressione sequenziale.

In pratica, penso che il "nessun archivio mutabile condiviso" la proprietà delle lingue in base alla garbage collection e alla semantica copy-on-change semplifica l'aggiunta di thread. Il miglior esempio è probabilmente Erlang, che combina semantica quasi funzionale con thread espliciti.

Answer 7

Questa è una domanda un po 'vaga. Un vantaggio delle CPU multi-core è che è possibile eseguire un programma funzionale e lasciarlo collegarsi in serie senza preoccuparsi di influenzare qualsiasi elaborazione in corso che ha a che fare con altre funzioni che la macchina sta svolgendo.

La differenza tra un server multi-U e una CPU multi-core in un server o PC è il risparmio di velocità che si ottiene avendo lo stesso BUS, consentendo una comunicazione migliore e più veloce ai core.

modifica: dovrei probabilmente qualificare questo post dicendo che nella maggior parte degli script che faccio, con o senza più core, raramente vedo un problema nel ottenere i miei dati attraverso il parallelismo hacker, come l'esecuzione di più piccoli script contemporaneamente in il mio script, quindi non sono rallentato da cose come aspettare il caricamento degli URL e cosa no.

doppia modifica: inoltre, molti linguaggi di programmazione funzionale hanno biforcuto varianti parallele per decenni. Questi utilizzano meglio il calcolo parallelo con un certo miglioramento della velocità, ma non hanno mai preso piede.

Answer 8

La mancanza del termine tecnico / scientifico è dovuta al fatto che il programma funzionale non condivide i dati. I dati vengono copiati e trasferiti tra le funzioni, quindi non ci sono dati condivisi nell'applicazione.

E i dati condivisi sono ciò che causa metà del mal di testa con il multithreading.

Answer 9

Il libro Programming Erlang: Software for a Concurrent World di Joe Armstrong (il creatore di Erlang ) parla un po 'dell'uso di Erlang per sistemi multicore (/ multiprocessore). Come afferma l'articolo di Wikipedia:

  

La creazione e la gestione dei processi è banale in Erlang, mentre i thread sono considerati un argomento complicato e soggetto a errori nella maggior parte delle lingue. Sebbene tutta la concorrenza sia esplicita in Erlang, i processi comunicano utilizzando il passaggio di messaggi anziché le variabili condivise, il che elimina la necessità di blocchi.