Perché non c'è un parallelismo implicito in Haskell?

Question

Haskell è funzionale e puro, quindi in pratica ha tutte le proprietà necessarie a un compilatore per poter affrontare implicit parallelism.

considerare questo esempio banale:

f = do 
    a <- Just 1 
    b <- Just $ Just 2 
    --^The above line does not utilize an `a` variable, so it can be safely 
    -- executed in parallel with the preceding line 
    c <- b 
    --^The above line references a `b` variable, so it can only be executed 
    -- sequentially after it 
    return (a, c) 
    -- On the exit from a monad scope we wait for all computations to finish and 
    -- gather the results 

Schematicamente il piano di esecuzione può essere descritto come:

   do 
       | 
     +---------+---------+ 
     |     | 
    a <- Just 1  b <- Just $ Just 2 
     |     | 
     |     c <- b 
     |     | 
     +---------+---------+ 
       | 
      return (a, c) 

Perché non c'è tale funzionalità implementate nel compilatore con una bandiera o ancora un pragma? Quali sono le ragioni pratiche?

Answer 1

Questo è un argomento a lungo studiato.Mentre è possibile derivare implicitamente il parallelismo nel codice Haskell, il problema è che c'è troppo parallelismo, a grana troppo fine, per l'hardware corrente.

Così finisci per spendere gli sforzi per la contabilità, non per eseguire le cose più velocemente.

Dal momento che non abbiamo infinita hardware parallelo, è tutta una questione raccogliendo la granularità destra - troppo grossolana e ci saranno processori inattivi, troppo fi ne e le spese generali sarà inaccettabile.

Quello che abbiamo è un parallelismo a grana più grossa (scintille) adatto a generare migliaia o milioni di attività parallele (quindi non a livello di istruzioni), che mappano sulla mera manciata di nuclei che in genere abbiamo a disposizione oggi.

Si noti che per alcuni sottoinsiemi (ad esempio elaborazione di array) esistono librerie di parallelizzazione completamente automatiche con modelli di costo stretti.

Per informazioni sullo sfondo, vedere http://research.microsoft.com/en-us/um/people/tharris/papers/2007-fdip.pdf, dove viene introdotto un approccio automatico all'inserimento di par in programmi Haskell arbitrari.

Answer 2

Mentre il blocco di codice non può essere il miglior esempio a causa di dati impliciti dipendenza tra la a e b, vale la pena notare che questi due binding commutare dal fatto che

f = do 
    a <- Just 1 
    b <- Just $ Just 2 
    ... 

darà gli stessi risultati

f = do 
    b <- Just $ Just 2 
    a <- Just 1 
    ... 

quindi questo potrebbe ancora essere parallelizzato in modo speculativo. Vale la pena notare che questo non ha bisogno di avere nulla a che fare con le monadi. Potremmo, ad esempio, valutare tutte le espressioni indipendenti in un blocco let in parallelo o potremmo introdurre una versione di let che farebbe così. Lo lparallel library per Common Lisp lo fa.

Ora, non sono affatto un esperto in materia, ma questa è la mia comprensione del problema. Un grosso ostacolo è determinante quando è vantaggioso parallelizzare la valutazione di più espressioni. C'è un sovraccarico associato all'avvio di thread separati per la valutazione e, come mostra il tuo esempio, può causare in lavoro sprecato. Alcune espressioni potrebbero essere troppo piccole per valutare la valutazione parallela . A quanto mi risulta, una metrica completamente precisa del costo di un'espressione pari a equivale a risolvere il problema di interruzione, pertanto si è relegati a utilizzare un approccio euristico per determinare in parallelo come valutare .

Quindi non è sempre più veloce lanciare più core su un problema. Anche quando mette in parallelo esplicitamente un problema con le numerose librerie Haskell disponibili, spesso non vedi molta accelerazione solo valutando le espressioni in parallelo a causa della pesante allocazione e utilizzo della memoria e del carico collettore immondizia e cache della CPU. Finisci per aver bisogno di un bel layout di memoria compatto e per attraversare i tuoi dati in modo intelligente. Avendo 16 thread tra gli elenchi collegati, lo ti strozzerà semplicemente sul tuo bus di memoria e potrebbe effettivamente rallentare le cose.

Per lo meno, quello che le espressioni possono essere efficacemente parallelized è qualcosa che è non ovvio per molti programmatori (almeno non è a questo), in modo da ottenere un compilatore per farlo in modo efficace non è banale .

Answer 3

Risposta breve: A volte la riproduzione di materiale in parallelo risulta essere più lenta, non più veloce. E capire quando è e quando non è una buona idea è un problema di ricerca irrisolto.

Tuttavia, si può ancora "utilizzare improvvisamente tutti quei core senza mai preoccuparsi di thread, deadlock e condizioni di gara". Non è automatico; hai solo bisogno di dare al compilatore qualche suggerimento su dove farlo! :-D

Answer 4

Uno dei motivi è perché Haskell non è rigido e non valuta nulla per impostazione predefinita. In generale, il compilatore non sa che il calcolo della a e b termina, quindi, cercando di calcolare sarebbe spreco di risorse:

x :: Maybe ([Int], [Int]) 
x = Just undefined 
y :: Maybe ([Int], [Int]) 
y = Just (undefined, undefined) 
z :: Maybe ([Int], [Int]) 
z = Just ([0], [1..]) 
a :: Maybe ([Int], [Int]) 
a = undefined 
b :: Maybe ([Int], [Int]) 
b = Just ([0], map fib [0..]) 
    where fib 0 = 1 
      fib 1 = 1 
      fib n = fib (n - 1) + fib (n - 2) 

considerarlo per le seguenti funzioni

main1 x = case x of 
       Just _ -> putStrLn "Just" 
       Nothing -> putStrLn "Nothing" 

(a, b) parte non ha bisogno da valutare Non appena si ottiene che x = Proprio _ si può procedere al ramo - da qui sarà lavoro per tutti i valori, ma a

main2 x = case x of 
       Just (_, _) -> putStrLn "Just" 
       Nothing -> putStrLn "Nothing" 

Questa funzione impone la valutazione delle tuple. Quindi x terminerà con errore mentre il resto funzionerà.

main3 x = case x of 
       Just (a, b) -> print a >> print b 
       Nothing -> putStrLn "Nothing" 

Questa funzione stampa prima il primo elenco e quindi il secondo. Funzionerà per z (risultante nella stampa di un flusso infinito di numeri ma Haskell può gestirli). b finirà per esaurire la memoria.

Ora in generale non si sa se il calcolo si interrompe o meno e quante risorse consumerà. liste infinite sono perfettamente bene in Haskell:

main = maybe (return()) (print . take 5 . snd) b -- Prints first 5 Fibbonacci numbers 

Quindi la deposizione delle uova le discussioni per valutare l'espressione in Haskell potrebbe tentare di valutare qualcosa che non è destinato a essere valutati pienamente - dire l'elenco di tutti i numeri primi - ma i programmatori usano come parte della struttura .Gli esempi sopra riportati sono molto semplici e si potrebbe obiettare che il compilatore potrebbe notarli - tuttavia non è possibile in generale a causa del problema di Halting (non si può scrivere un programma che accetta un programma arbitrario e il suo input e controlla se termina) - quindi non è ottimizzazione sicura.

Inoltre, che è stato menzionato da altre risposte, è difficile prevedere se il sovraccarico di thread aggiuntivi valga la pena di essere coinvolti. Anche se GHC non genera nuovi thread per le scintille che utilizzano il threading verde (con un numero fisso di thread del kernel, tranne alcune eccezioni), è comunque necessario spostare i dati da un core all'altro e sincronizzarli tra loro che possono essere piuttosto costosi.

Tuttavia Haskell ha una parallelizzazione guidata senza rompere la purezza del linguaggio tramite par e funzioni simili.

Answer 5

In realtà c'era un tale tentativo ma non su hardware comune a causa della bassa quantità disponibile di core. Il progetto si chiama . Gestisce il codice Haskell con un alto livello di parallelismo. Nel caso in cui sia mai stato rilasciato come proper 2 GHz ASIC core, avremmo avuto un importante passo avanti nella velocità di esecuzione di Haskell.