(Quando) sono pratiche pratiche parallele e come si scrive in modo efficiente?

Question

Sto lavorando su una libreria di parallelizzazione per il linguaggio di programmazione D. Ora che sono abbastanza soddisfatto delle primitive di base (foreach parallela, map, reduce e tasks/futures), sto iniziando a pensare ad alcuni algoritmi paralleli di più alto livello. Tra i candidati più ovvi per la parallelizzazione c'è l'ordinamento.

mia prima domanda è, sono parallelized versioni di algoritmi di ordinamento utili nel mondo reale, o sono per lo più accademico? Se sono utili, dove sono utili? Personalmente li userò raramente nel mio lavoro, semplicemente perché di solito leggo tutti i miei core al 100% usando un livello di parallelismo a grana molto più grossa di una singola chiamata sort().

In secondo luogo, sembra che l'ordinamento rapido sia quasi in modo imbarazzante parallelo per i grandi array, ma non riesco a ottenere gli aumenti quasi lineari che credo dovrei ottenere. Per un ordinamento rapido, l'unica parte intrinsecamente seriale è la prima partizione. Ho provato a parallelizzare un ordinamento rapido, dopo ogni partizione, ordinando i due sottoarray in parallelo. In pseudocodice semplificata:

// I tweaked this number a bunch. Anything smaller than this and the 
// overhead is smaller than the parallelization gains. 
const smallestToParallelize = 500; 

void quickSort(T)(T[] array) { 
    if(array.length < someConstant) { 
     insertionSort(array); 
     return; 
    } 

    size_t pivotPosition = partition(array); 

    if(array.length >= smallestToParallelize) { 
     // Sort left subarray in a task pool thread. 
     auto myTask = taskPool.execute(quickSort(array[0..pivotPosition])); 
     quickSort(array[pivotPosition + 1..$]); 
     myTask.workWait(); 
    } else { 
     // Regular serial quick sort. 
     quickSort(array[0..pivotPosition]); 
     quickSort(array[pivotPosition + 1..$]); 
    } 
} 

Anche per matrici molto grandi, dove il tempo prima partizione prende è trascurabile, posso solo ottenere circa un aumento di velocità del 30% su un dual core, rispetto ad una versione puramente seriale dell'algoritmo . Immagino che il collo di bottiglia sia l'accesso alla memoria condivisa. Qualche idea su come eliminare questo collo di bottiglia o cos'altro potrebbe essere il collo di bottiglia?

Edit: La mia piscina attività ha un numero fisso di thread, pari al numero di nuclei nel sistema meno 1 (poiché il filo principale fa anche lavoro). Inoltre, il tipo di attesa che sto utilizzando è un'aspettativa di lavoro, ad esempio se l'attività è avviata ma non terminata, il thread che chiama workWait() ruba altri lavori fuori dal pool e li esegue finché non viene completato quello in attesa. Se l'attività non è avviata, viene completata nel thread corrente. Ciò significa che l'attesa non è inefficiente. Finché c'è lavoro da fare, tutti i thread saranno tenuti occupati.

Answer 1

Tenete a mente che non sono un esperto di specie in parallelo, e la gente fanno carriere di ricerca di tipo parallelo, ma ...

1) sono utili nel mondo reale.

ovviamente lo sono, se avete bisogno di ordinare qualcosa di costoso (come archi o peggio) e voi non sono pegging tutti i core.

• pensare codice utente in cui è necessario risolvere una lunga lista dinamica di stringhe in base al contesto
• pensare qualcosa come Barnes-capanna n-corpi sim in cui è necessario ordinare le particelle

2) Quicksort sembra dare una velocità lineare, ma non lo è. Il passo della partizione è un collo di bottiglia sequenziale, lo vedrai con il tuo profilo e tenderà a chiudere a 2-3x su un quad core.

Se si desidera ottenere una buona velocità su un sistema più piccolo, è necessario assicurarsi che le spese generali per le attività siano molto piccole e, idealmente, si vorrà assicurarsi di non avere troppi thread in esecuzione, cioè non molto più di 2 su un dual core. Probabilmente un pool di thread non è la giusta astrazione.

Se si desidera ottenere buoni incrementi nella velocità su un sistema più grande avrete bisogno di guardare i tipi parallele basate scansione, ci sono documenti su questo. l'ordinamento bitonico è anche abbastanza facile parallelizzare come è l'unire sort. Può essere utile anche un ordinamento di tipo radix parallelo, ce n'è uno nella PPL (se non si è contrari a Visual Studio 11).

Answer 2

Non sono un esperto ma ... ecco quello che mi guardo:

Prima di tutto, ho sentito dire che, come regola generale, algoritmi che guardano piccoli pezzetti di un problema dall'inizio tende a funzionare meglio come algoritmi paralleli.

Guardando alla vostra implementazione, provate a fare in modo che lo switch parallelo/seriale vada diversamente: partizionate la matrice e ordinate in parallelo finché non avete N segmenti, quindi passate in serie. Se stai più o meno afferrando una nuova discussione per ogni caso parallelo, allora N dovrebbe essere ~ il tuo conteggio principale. OTOH se il tuo pool di thread è di dimensioni fisse e agisce come una coda di delegati di breve durata, allora userei N ~ 2+ volte il tuo core count (in modo che i core non restino inattivi perché una partizione finisce più velocemente).

Altre modifiche:

• saltare l'myTask.wait(); a livello locale e piuttosto hanno una funzione wrapper che attende su tutte le attività.
• Eseguire un'implementazione seriale separata della funzione che evita il controllo della profondità.

Answer 3

"La mia prima domanda è, sono versioni parallele di algoritmi di ordinamento utili nel mondo reale" - dipende dalla dimensione del set di dati su cui si sta lavorando nel lavoro reale. Per piccoli insiemi di dati la risposta è no. Per i set di dati più grandi dipende non solo dalla dimensione del set di dati, ma anche dall'architettura specifica del sistema.

Uno dei fattori limitanti che impediscono l'aumento previsto delle prestazioni è il layout della cache del sistema. Se i dati possono essere contenuti nella cache L1 di un core, allora c'è poco da guadagnare ordinando su più core quando si incorre nella penalità della mancanza della cache L1 tra ogni iterazione dell'algoritmo di ordinamento.

Lo stesso ragionamento si applica ai chip con più cache L2 e architetture NUMA (accesso non uniforme alla memoria). Quindi più core vuoi distribuire l'ordinamento, la più piccola costante di Pono di parallelismo dovrà essere aumentata di conseguenza.

Un altro fattore limitante identificato è l'accesso alla memoria condivisa o il conflitto sul bus di memoria. Poiché il bus di memoria può soddisfare solo un certo numero di accessi di memoria al secondo; avere core aggiuntivi che essenzialmente non fanno altro che leggere e scrivere nella memoria principale, metterà molto stress al sistema di memoria.

L'ultimo fattore che dovrei sottolineare è il pool di thread stesso in quanto potrebbe non essere efficiente come si pensa. Poiché sono presenti thread che rubano e generano lavoro da una coda condivisa, tale coda richiede metodi di sincronizzazione; e in base a come vengono implementati, possono causare sezioni seriali molto lunghe nel codice.

Answer 4

Non so se le risposte qui sono più applicabili o se i miei suggerimenti sono applicabili a D.

Comunque ...

Supponendo che D consente, c'è sempre la possibilità di fornire prefetch suggerimenti per le cache. Il nucleo in questione richiede che i dati che presto (non immediatamente) dovranno essere caricati in un determinato livello di cache. Nel caso ideale i dati saranno stati recuperati dal momento in cui il core inizia a lavorarci. Più probabilmente il processo di precaricamento sarà più o meno lungo la strada che, per lo meno, si tradurrà in meno stati di attesa rispetto a se i dati fossero stati recuperati "a freddo"."

Resterai ancora vincolato dalla capacità di throughput complessiva da cache a RAM, quindi avrai bisogno di organizzare i dati in modo tale che tanti dati siano nelle cache esclusive del core che può spendere una buona quantità di tempo lì prima di dover scrivere dati aggiornati

Il codice e i dati devono essere organizzati secondo il concetto di linee di cache (unità di recupero di 64 byte ciascuna) che è l'unità di dimensioni più piccole in una cache. in quanto per due core il lavoro deve essere organizzato in modo tale che il sistema di memoria funzioni la metà di tanto per core (supponendo una scalabilità del 100%) come prima quando solo un core funzionava e il lavoro non era stato organizzato. tanto e così via.E 'una bella sfida ma non assolutamente impossibile, semplicemente depenalizzata ds su quanto sei fantasioso nel ristrutturare il lavoro. Come sempre, ci sono soluzioni che non possono essere concepite ... finché qualcuno non fa proprio questo!

Non so come WYSIWYG D sia paragonato a C - che uso - ma in generale penso che il processo di sviluppo di applicazioni scalabili sia migliorato da quanto lo sviluppatore può influenzare il compilatore nella generazione del codice macchina attuale. Per le lingue interpretate ci sarà così tanto lavoro di memoria da parte dell'interprete che si rischia di non essere in grado di discernere i miglioramenti dal "rumore di fondo" generale.

Una volta ho scritto un shellsort multi-thread che correva il 70% più velocemente su due core rispetto a uno e il 100% su tre core rispetto a uno. Quattro core funzionavano più lentamente di tre. Quindi conosco i dilemmi che affronti.

Answer 5

Desidero indicare l'ordinamento esterno [1] che si trova ad affrontare problemi simili. Solitamente, questa classe di algoritmi viene utilizzata principalmente per far fronte a grandi volumi di dati, ma il loro punto principale è che essi dividono grandi blocchi in problemi più piccoli e non correlati, che sono quindi davvero ottimi da eseguire in parallelo. Hai "solo" bisogno di ricucire insieme i risultati parziali successivi, il che non è altrettanto parallelo (ma relativamente economico rispetto alla selezione effettiva).

Un ordinamento di unione esterno funzionerebbe anche molto bene con una quantità sconosciuta di thread. Devi solo dividere il carico di lavoro in modo arbitrario e dare ogni pezzo di n elementi a un thread ogni volta che c'è un inattivo, fino a quando tutte le tue unità di lavoro sono terminate, a quel punto puoi iniziare a unirle.

[1] http://en.wikipedia.org/wiki/External_sorting