Come ridurre l'overhead di parallelizzazione di Haskell?

Question

Sto cercando di capire le prestazioni di parallelizzazione di Haskell.

Ho una lunga lista (lunghezza> 1000) che sto valutando in parallelo, usando il parallelo parMap.

Ecco l'output completo statistiche utilizzando +RTS -s per un singolo filo (EDIT: previsti completo uscita):

 54,248,802,288 bytes allocated in the heap 
      324,451,424 bytes copied during GC 
      2,970,272 bytes maximum residency (4 sample(s)) 
       52,064 bytes maximum slop 
        217 MB total memory in use (1 MB lost due to fragmentation) 

              Tot time (elapsed) Avg pause Max pause 
     Gen 0  251 colls,  0 par 1.45s 1.49s  0.0059s 0.0290s 
     Gen 1   4 colls,  0 par 0.03s 0.05s  0.0125s 0.0319s 

     TASKS: 4 (1 bound, 3 peak workers (3 total), using -N1) 

     SPARKS: 6688 (0 converted, 0 overflowed, 0 dud, 1439 GC'd, 5249 fizzled) 

     INIT time 0.00s ( 0.03s elapsed) 
     MUT  time 19.76s (20.20s elapsed) 
     GC  time 1.48s ( 1.54s elapsed) 
     EXIT time 0.00s ( 0.00s elapsed) 
     Total time 21.25s (21.78s elapsed) 

     Alloc rate 2,745,509,084 bytes per MUT second 

     Productivity 93.0% of total user, 90.8% of total elapsed 

     gc_alloc_block_sync: 0 
     whitehole_spin: 0 
     gen[0].sync: 0 
     gen[1].sync: 0 

Se corro su due fili, utilizzando +RTS -N2, ottengo:

 54,336,738,680 bytes allocated in the heap 
      346,562,320 bytes copied during GC 
      5,437,368 bytes maximum residency (5 sample(s)) 
       120,000 bytes maximum slop 
        432 MB total memory in use (0 MB lost due to fragmentation) 

              Tot time (elapsed) Avg pause Max pause 
     Gen 0  127 colls, 127 par 2.07s 0.99s  0.0078s 0.0265s 
     Gen 1   5 colls,  4 par 0.08s 0.04s  0.0080s 0.0118s 

     Parallel GC work balance: 41.39% (serial 0%, perfect 100%) 

     TASKS: 6 (1 bound, 5 peak workers (5 total), using -N2) 

     SPARKS: 6688 (6628 converted, 0 overflowed, 0 dud, 0 GC'd, 60 fizzled) 

     INIT time 0.00s ( 0.01s elapsed) 
     MUT  time 25.31s (13.35s elapsed) 
     GC  time 2.15s ( 1.03s elapsed) 
     EXIT time 0.01s ( 0.01s elapsed) 
     Total time 27.48s (14.40s elapsed) 

     Alloc rate 2,146,509,982 bytes per MUT second 

     Productivity 92.2% of total user, 175.9% of total elapsed 

     gc_alloc_block_sync: 19922 
     whitehole_spin: 0 
     gen[0].sync: 1 
     gen[1].sync: 0 

e quattro thread:

 54,307,370,096 bytes allocated in the heap 
      367,282,056 bytes copied during GC 
      8,561,960 bytes maximum residency (6 sample(s)) 
      3,885,784 bytes maximum slop 
        860 MB total memory in use (0 MB lost due to fragmentation) 

              Tot time (elapsed) Avg pause Max pause 
     Gen 0  62 colls, 62 par 2.45s 0.70s  0.0113s 0.0179s 
     Gen 1   6 colls,  5 par 0.20s 0.07s  0.0112s 0.0146s 

     Parallel GC work balance: 40.57% (serial 0%, perfect 100%) 

     TASKS: 10 (1 bound, 9 peak workers (9 total), using -N4) 

     SPARKS: 6688 (6621 converted, 0 overflowed, 0 dud, 3 GC'd, 64 fizzled) 

     INIT time 0.01s ( 0.01s elapsed) 
     MUT  time 37.26s (10.95s elapsed) 
     GC  time 2.65s ( 0.77s elapsed) 
     EXIT time 0.01s ( 0.01s elapsed) 
     Total time 39.94s (11.76s elapsed) 

     Alloc rate 1,457,427,453 bytes per MUT second 

     Productivity 93.4% of total user, 317.2% of total elapsed 

     gc_alloc_block_sync: 23494 
     whitehole_spin: 0 
     gen[0].sync: 10527 
     gen[1].sync: 38 

Quindi, secondo il tempo trascorso (TH l'ultimo numero in ogni uscita), con due core il programma prende ~ 66% della versione a thread singolo e con quattro core impiega il 54% delle volte. Questa accelerazione non è male, ma molto peggiore del miglioramento lineare teoricamente previsto con il numero di core, il che comporterebbe un runtime del 25% con quattro core.

Ora, guardando le uscite statistiche di cui sopra, posso vedere che l'effettivo tempo di CPU di lavoro per il programma (le righe che iniziano con MUT) aumenta notevolmente con l'utilizzo di più core. Con 1, 2 e 4 core ottengo un tempo di CPU di 19,76, 25,31 e 37,26, e questo aumento è ciò che è - credo - mangiando le mie prestazioni di parallelizzazione.

I motivi tipici di tale sovraccarico runtime CPU con più core che mi vengono in mente sono:

• troppo fine granularità della distribuzione del carico di lavoro. Tuttavia, ho provato lo stesso programma usando parListChunked dal pacchetto parallel, con una dimensione del blocco pari a 10. Ma il risultato è molto simile, quindi per il momento non penso che il sovraccarico sia dovuto a una granularità troppo fine.
• Garbage collection: questo è stato un grande killer per le prestazioni del mio codice in passato, ma poiché ho aumentato la dimensione del GC a 100 Mb il tempo totale trascorso in GC è piuttosto ridotto, come mostrato nelle statistiche sopra.

Quali sono altri motivi per un sovraccarico così forte e come posso attenuarli?

Answer 1

vedo persone stanno votando per chiudere la questione perché non c'è abbastanza dettagli, ma credo che la risposta può essere trovata utilizzando le informazioni già fornite (anche se i dettagli sono sempre i benvenuti.)

Il mio naso mi dice che sei limitato dal throughput della memoria. Cercherò di descrivere perché penso di sì, ma non sono un esperto di hardware, quindi potrei essere parzialmente o totalmente sbagliato. Dopo tutto, si basa sul mio personale set di miti dell'architettura hardware.

lascia supporre che il limite sta nel mezzo 50-100Gb al secondo (non sono sicuro che sia il numero corretto, per favore correggetemi se avete migliore.)

si assegnano 54IT in 10 secondi (il caso -N4), quindi hai un throughput di 5 Gb/sec. È piuttosto alto, ma di solito non è un problema su se stesso.

La maggior parte delle allocazioni di solito sono di breve durata, e sono convertite in GC una volta riempita l'area di assegnazione gen0 (nursery).Per impostazione predefinita, la dimensione del vivaio è 512 Kb, quindi tutte le allocazioni si verificano nella cache L2. Quindi i dati di vita brevi non entreranno mai nella memoria principale, è per questo che è quasi gratis.

Ma hai aumentato le dimensioni del vivaio a 100 Mb. Non si adatta alla cache L2 e sarà trasferito nella memoria principale. Questo è già un brutto segno.

Bene, 5 Gb/sec è lontano dal limite. Ma c'è una ragione per cui hai aumentato la dimensione del nido d'infanzia - i tuoi dati non sono di breve durata. Sarà usato da qualche altra parte dopo un certo ritardo. Ciò significa che questo 54Gb verrà caricato dalla memoria principale alle cache prima o poi. Quindi hai almeno un throughput di 10 Gb/sec.

È ancora lontano dal limite, ma si noti che è lo scenario migliore - sequenza sequenziale di accesso alla memoria. In realtà si accede alla memoria in ordine casuale, quindi le stesse linee della cache vengono caricate e scaricate più volte e si raggiungono facilmente 100 Gb/sec.

Per risolvere il problema, è necessario identificare perché i nostri dati non sono di breve durata e provare a risolverlo. Se ciò non è possibile, puoi provare ad aumentare la località dei dati e modificare il modello di accesso alla memoria per renderlo sequenziale.

Mi piacerebbe sapere cosa pensano gli esperti di hardware sulla mia spiegazione ingenua :)