Parallelamente imbarazzante - Embarrassingly parallel
Nel calcolo parallelo , un carico di lavoro o un problema imbarazzantemente parallelo (chiamato anche imbarazzante parallelizzabile , perfettamente parallelo , deliziosamente parallelo o piacevolmente parallelo ) è uno in cui è necessario uno sforzo minimo o nullo per separare il problema in una serie di attività parallele. Questo è spesso il caso in cui c'è poca o nessuna dipendenza o necessità di comunicazione tra queste attività parallele o di risultati tra di loro.
Pertanto, questi sono diversi dai problemi di calcolo distribuito che richiedono la comunicazione tra i compiti, in particolare la comunicazione di risultati intermedi. Sono facili da eseguire su server farm che non dispongono dell'infrastruttura speciale utilizzata in un vero cluster di supercomputer . Sono quindi adatti a grandi piattaforme distribuite basate su Internet come BOINC e non soffrono di rallentamenti paralleli . L'opposto dei problemi imbarazzanti paralleli sono intrinsecamente problemi seriali , che non possono essere affatto parallelizzati.
Un esempio comune di un problema imbarazzante parallelo è il rendering video 3D gestito da un'unità di elaborazione grafica , in cui ogni fotogramma (metodo forward) o pixel ( metodo ray tracing ) può essere gestito senza interdipendenza. Alcune forme di password cracking sono un'altra attività parallela imbarazzante che può essere facilmente distribuita su unità di elaborazione centrale , core CPU o cluster.
Etimologia
"Imbarazzante" è usato qui nello stesso senso della frase "un imbarazzo della ricchezza ", che significa una sovrabbondanza, qui riferendosi a problemi di parallelizzazione che sono "imbarazzantemente facili". Il termine può anche implicare imbarazzo da parte di sviluppatori o compilatori: "Poiché così tanti importanti problemi rimangono irrisolti principalmente a causa della loro intrinseca complessità computazionale, sarebbe imbarazzante non sviluppare implementazioni parallele di metodi di continuazione dell'omotopia polinomiale ". Il termine si trova per la prima volta in letteratura in un libro del 1986 sui multiprocessori del creatore di MATLAB Cleve Moler , che afferma di aver inventato il termine.
Un termine alternativo, piacevolmente parallelo , ha guadagnato un certo uso, forse per evitare le connotazioni negative dell'imbarazzo a favore di una riflessione positiva sulla parallelizzabilità dei problemi: "Naturalmente, non c'è assolutamente nulla di imbarazzante in questi programmi".
Esempi
Alcuni esempi di problemi imbarazzanti paralleli includono:
- Analisi Montecarlo
- Query di database relazionali distribuiti utilizzando l' elaborazione di insiemi distribuiti .
- Integrazione numerica
- Servire file statici su un server web a più utenti contemporaneamente.
- L' insieme di Mandelbrot , il rumore di Perlin e immagini simili, dove ogni punto viene calcolato indipendentemente.
- Rendering di computer grafica . Nell'animazione al computer , ogni fotogramma o pixel può essere renderizzato in modo indipendente (vedi rendering parallelo ).
- Ricerche a forza bruta in crittografia . Esempi notevoli del mondo reale includono sistemi distribuiti.net e proof-of-work utilizzati nella criptovaluta .
- BLAST cerca in bioinformatica per più query (ma non per singole query di grandi dimensioni).
- Sistemi di riconoscimento facciale su larga scala che confrontano migliaia di volti acquisiti arbitrariamente (ad esempio, un video di sicurezza o di sorveglianza tramite televisione a circuito chiuso ) con un numero altrettanto elevato di volti precedentemente memorizzati (ad esempio, una galleria di ladri o una lista di controllo simile ).
- Simulazioni al computer che confrontano molti scenari indipendenti.
- Algoritmi genetici .
- Calcoli complessivi di previsioni meteorologiche numeriche .
- Simulazione e ricostruzione di eventi in fisica delle particelle .
- L' algoritmo delle piazze in marcia .
- Passo di setacciatura del crivello quadratico e del crivello del campo numerico .
- Fase di crescita degli alberi della tecnica di apprendimento automatico della foresta casuale .
- Trasformata discreta di Fourier in cui ogni armonica è calcolata indipendentemente.
- Reti neurali convoluzionali in esecuzione su GPU .
- Ricerca con griglia iperparametrica nell'apprendimento automatico.
- Ricerca parallela nella programmazione con vincoli
implementazioni
- In R (linguaggio di programmazione) – Il pacchetto Simple Network of Workstations (SNOW) implementa un semplice meccanismo per utilizzare un set di workstation o un cluster Beowulf per calcoli imbarazzanti paralleli.
Guarda anche
- La legge di Amdahl definisce il valore P , che sarebbe quasi o esattamente uguale a 1 per problemi imbarazzanti paralleli.
- Mappa (modello parallelo)
- Multielaborazione
- Massicciamente parallelo
- Calcolo parallelo
- Programmazione orientata al processo
- Architettura del nulla condiviso (SN)
- Multiprocessing simmetrico (SMP)
- Macchina di connessione
- Automa cellulare
- Quadro CUDA
- Processore a molti core
- Processore vettoriale
Riferimenti
-
^
Herlihy, Maurice; Shavit, Nir (2012). L'arte della programmazione multiprocessore, ristampa rivista (rivisto ed.). Altrove. pag. 14. ISBN 9780123977953. Estratto il 28 febbraio 2016 .
Alcuni problemi computazionali sono “imbarazzantemente paralleli”: possono essere facilmente suddivisi in componenti che possono essere eseguiti contemporaneamente.
- ^ Sezione 1.4.4 di: Foster, Ian (1995). Progettare e costruire programmi paralleli . Addison-Wesley. ISBN 9780201575941. Archiviato dall'originale il 01/03/2011.
- ^ Alan Chalmers; Erik Reinhard; Tim Davis (21 marzo 2011). Rendering parallelo pratico . CRC Press. ISBN 978-1-4398-6380-0.
- ^ Matloff, Norman (2011). L'arte della programmazione R: un tour della progettazione di software statistici , p.347. Niente amido. ISBN 9781593274108 .
- ^ Leykin, Anton; Verschelde, Jan; Zhuang, Yan (2006). Algoritmi di omotopia parallela per risolvere sistemi polinomiali . Atti dell'ICMS . Appunti delle lezioni di Informatica. 4151 . pp. 225-234. doi : 10.1007/11832225_22 . ISBN 978-3-540-38084-9.
- ^ Moler, Cleve (1986). Heath, Michael T. (ed.). Calcolo di matrici su multiprocessori a memoria distribuita . Multiprocessori Hypercube . Società per la matematica industriale e applicata, Filadelfia. ISBN 978-0898712094.
- ^ L'ipercubo Intel parte 2 ripubblicato sul blog di Cleve's Corner sul sito web di The MathWorks
- ^ Kepner, Jeremy (2009). MATLAB parallelo per computer multicore e multinodo , p.12. SIAM. ISBN 9780898716733 .
- ^ Erricos John Kontoghiorghes (21 dicembre 2005). Manuale di calcolo parallelo e statistica . CRC Press. ISBN 978-1-4200-2868-3.
- ^ Yuefan Deng (2013). Calcolo parallelo applicato . Scientifico mondiale. ISBN 978-981-4307-60-4.
- ^ Josefsson, Simone; Percival, Colin (agosto 2016). "La funzione di derivazione della chiave basata su password scrypt" . tools.ietf.org . Estratto 12-12-2016 .
- ^ Forum di SeqAnswers
- ^ Come abbiamo reso il nostro riconoscimento facciale 25 volte più veloce (post sul blog degli sviluppatori)
- ^ Shigeyoshi Tsutsui; Pierre Collet (5 dicembre 2013). Calcolo evolutivo massicciamente parallelo su GPGPU . Springer Scienza e Business Media. ISBN 978-3-642-37959-8.
- ^ Youssef Hamadi; Lakhdar Sais (5 aprile 2018). Manuale di ragionamento sui vincoli paralleli . Springer. ISBN 978-3-319-63516-3.
- ^ Pacchetto Simple Network of Workstations (SNOW)
link esterno
- Calcoli imbarazzanti paralleli , progettazione di un cluster di calcolo in stile Beowulf
- " Star-P: calcolo parallelo ad alta produttività "
