Quali sono esempi canonici di calcolo parallelo?

Question

Sto scrivendo un articolo per testare una nuova applicazione che dimostrerà i vantaggi del calcolo parallelo (rispetto alla versione serializzata tradizionale di questa applicazione). Voglio usare il canonical examples per il calcolo parallelo nella mia carta.

Il mio primo esempio è the parallel computation of pi. Mi piacerebbe idealmente un esempio in cui ogni iterazione richiede molto tempo (a causa dell'overhead aggiuntivo associato alla parallelizzazione); il mio primo pensiero è una simulazione bayesiana con campionamento MCMC e Gibbs.

Quali altri problemi vengono generalmente discussi in questo contesto? Quali sono buoni esempi di grandi problemi embarassingly parallel?

Answer 1

Un esempio che ho usato in passato per un problema parallelo imbarazzante è la visualizzazione del set di mandelbrot. Ogni pixel può essere calcolato indipendentemente.

Anche la vita di Conway è interessante, in quanto ogni valore della "prossima" scheda può essere calcolato indipendentemente, ma dipenderà dai bit pertinenti della scheda "corrente" già eseguita.

Answer 2

Il conteggio delle parole sembra essere l'esempio canonico di MapReduce.

http://en.wikipedia.org/wiki/MapReduce#Example

Answer 3

Pochi più -

• moltiplicare le matrici
• Inversione matrici
• FFT
• stringa corrispondente
• rendering scene 3d (tramite conversione della linea di scansione o ray tracing)

Answer 4

Il mio esempio preferito è la simulazione di monte carlo.

Answer 5

Trovare collisioni nelle funzioni di hash utilizzando Paul C. van Oorschot e Michael J. Weiner's method (PDF) si presenta spesso in varie impostazioni crittografiche.

Answer 6

Vorrei suggerire che esempi canonici di calcolo parallelo e problemi embarassingly parallele sono, se non completamente, quindi quasi, insiemi disgiunti. Per dirla in altro modo, le persone che lavorano nella computazione parallela non sono terribilmente eccitate per problemi imbarazzanti e paralleli; li chiamiamo così perché ci vergogneremmo di lavorarci sopra.

sarei cercando, se fossi in te, in questi (una lista non del tutto originale):

• algebra lineare su grandi matrici dense, entrambi gli approcci diretti e iterativi;
• algebra lineare su matrici sparse enormi
• approcci ramificati e vincolati a problemi di programmazione lineare (e correlati);
• corrispondenza di sequenza per bioinformatica (al di fuori del mio campo, potrei averlo espresso male);
• ottimizzazione continua.

Mi aspetto che ce ne siano molti altri.

EDIT: Si può essere interessati a this list of problems che sono stati selezionati per l'analisi comparativa la prossima generazione di europei (accademici) supercomputer. Ti darà un'idea di dove sta andando quella nicchia.

Answer 7

Le simulazioni di dinamiche molecolari consentono di modificare la dimensione del problema fino all'esaurimento delle risorse del computer (ovvero 256 particelle contro 256.000.000 di particelle). La sua veramente un esempio "canonica" se si esegue le simulazioni MD sotto NVT condizioni ;-)

Answer 8

Si consiglia di dare un'occhiata al sommario di Parallel Programming in C with MPI and OpenMP

Answer 9

ho usato l'insieme di Mandelbrot demo di spiegare al mio mamma di cosa parla la programmazione parallela: http://www.ateji.com/px/demo.html

Tutti gli esempi che si menzionano sono per lo più codici dati paralleli pesanti. Probabilmente vorrai menzionare anche codici orientati alle attività, come i server che rispondono a molte richieste in parallelo, e flussi di dati o esempi di programmazione del flusso (MapReduce è un buon rappresentante di questa classe).