Peinlich parallel - Embarrassingly parallel
Beim Parallel Computing ist eine peinlich parallele Arbeitslast oder ein Problem (auch als peinlich parallelisierbar , perfekt parallel , herrlich parallel oder angenehm parallel bezeichnet ) ein Problem, bei dem wenig oder kein Aufwand erforderlich ist, um das Problem in mehrere parallele Aufgaben aufzuteilen. Dies ist häufig der Fall, wenn zwischen diesen parallelen Aufgaben wenig oder keine Abhängigkeit oder Notwendigkeit für die Kommunikation zwischen diesen oder deren Ergebnissen besteht.
Somit unterscheiden sich diese von verteilten Rechenproblemen , die eine Kommunikation zwischen Aufgaben erfordern, insbesondere eine Kommunikation von Zwischenergebnissen. Sie sind einfach auf Serverfarmen durchzuführen, denen die spezielle Infrastruktur fehlt, die in einem echten Supercomputer- Cluster verwendet wird. Sie eignen sich daher gut für große, internetbasierte verteilte Plattformen wie BOINC und leiden nicht unter paralleler Verlangsamung . Das Gegenteil von peinlich parallelen Problemen sind inhärent serielle Probleme , die überhaupt nicht parallelisiert werden können.
Ein übliches Beispiel für ein peinlich paralleles Problem ist das 3D-Video-Rendering, das von einer Grafikverarbeitungseinheit gehandhabt wird , bei der jeder Frame (Vorwärtsverfahren) oder Pixel ( Raytracing- Verfahren) ohne gegenseitige Abhängigkeit gehandhabt werden kann. Einige Formen des Passwortknackens sind eine weitere peinlich parallele Aufgabe, die sich leicht auf Zentraleinheiten , CPU-Kerne oder Cluster verteilen lässt .
Etymologie
„Peinlich“ wird hier im gleichen Sinne gebraucht wie in der Wendung „eine Peinlichkeit des Reichtums “, also ein Überfluss – hier sind Parallelisierungsprobleme gemeint, die „peinlich einfach“ sind. Der Begriff kann auch Verlegenheit auf Seiten von Entwicklern oder Compilern implizieren: "Weil so viele wichtige Probleme hauptsächlich aufgrund ihrer intrinsischen Rechenkomplexität ungelöst bleiben, wäre es peinlich, keine parallelen Implementierungen von polynomialen Homotopie- Fortsetzungsverfahren zu entwickeln." Der Begriff taucht erstmals in der Literatur in einem 1986 erschienenen Buch über Multiprozessoren des MATLAB -Erfinders Cleve Moler auf , der behauptet, den Begriff erfunden zu haben.
Ein alternativer Begriff, erfreulicherweise parallel , hat sich durchgesetzt, vielleicht um die negative Konnotation von Peinlichkeit zu vermeiden zugunsten einer positiven Reflexion über die Parallelisierbarkeit der Probleme: "Natürlich ist an diesen Programmen überhaupt nichts peinlich."
Beispiele
Einige Beispiele für peinlich parallele Probleme sind:
- Monte-Carlo-Analyse
- Verteilte relationale Datenbankabfragen mit verteilter Satzverarbeitung .
- Numerische Integration
- Bereitstellung statischer Dateien auf einem Webserver für mehrere Benutzer gleichzeitig.
- Die Mandelbrot-Menge , Perlin-Rauschen und ähnliche Bilder, bei denen jeder Punkt unabhängig berechnet wird.
- Rendering von Computergrafiken . Bei der Computeranimation kann jeder Frame oder jedes Pixel unabhängig gerendert werden (siehe paralleles Rendern ).
- Brute-Force-Suchen in der Kryptographie . Bemerkenswerte Beispiele aus der Praxis sind Distributed.net und Proof-of-Work- Systeme, die in Kryptowährung verwendet werden .
- BLAST sucht in der Bioinformatik nach mehreren Abfragen (aber nicht nach einzelnen großen Abfragen).
- Groß angelegte Gesichtserkennungssysteme , die Tausende von beliebigen erworbenen Flächen (beispielsweise ein Wertpapier oder ein Überwachungsvideo über vergleichen Closed-Circuit Television ) mit ähnlich großer Anzahl von zuvor gespeicherten Flächen (zB eine Rogues Gallery oder ähnlicher Merkliste ).
- Computersimulationen, die viele unabhängige Szenarien vergleichen.
- Genetische Algorithmen .
- Ensemble-Berechnungen der numerischen Wettervorhersage .
- Ereignissimulation und Rekonstruktion in der Teilchenphysik .
- Der Marschquadrat- Algorithmus.
- Siebschritt des quadratischen Siebes und des Zahlenfeldsiebs .
- Baumwachstumsschritt der Random Forest Machine Learning-Technik.
- Diskrete Fourier-Transformation, bei der jede Harmonische unabhängig berechnet wird.
- Konvolutionelle neuronale Netzwerke, die auf GPUs ausgeführt werden .
- Hyperparameter-Gittersuche im maschinellen Lernen.
- Parallele Suche in der Constraint-Programmierung
Implementierungen
- In R (Programmiersprache) – Das Paket Simple Network of Workstations (SNOW) implementiert einen einfachen Mechanismus zur Verwendung einer Reihe von Workstations oder eines Beowulf-Clusters für peinlich parallele Berechnungen.
Siehe auch
- Das Gesetz von Amdahl definiert den Wert P , der für peinlich parallele Probleme fast oder genau gleich 1 wäre.
- Karte (paralleles Muster)
- Multiprocessing
- Massiv parallel
- Paralleles Rechnen
- Prozessorientierte Programmierung
- Shared-Nothing-Architektur (SN)
- Symmetrisches Multiprocessing (SMP)
- Verbindungsmaschine
- Zellularer Automat
- CUDA-Framework
- Manycore-Prozessor
- Vektorprozessor
Verweise
-
^
Herlihy, Maurice; Shavit, Nir (2012). Die Kunst der Mehrprozessorprogrammierung, überarbeiteter Nachdruck (überarbeitete Hrsg.). Sonst. s. 14. ISBN 9780123977953. Abgerufen am 28. Februar 2016 .
Einige Rechenprobleme sind „peinlich parallel“: Sie lassen sich leicht in Komponenten aufteilen, die gleichzeitig ausgeführt werden können.
- ^ Abschnitt 1.4.4 von: Foster, Ian (1995). Entwerfen und Erstellen von Parallelprogrammen . Addison-Wesley. ISBN 9780201575941. Archiviert vom Original am 01.03.2011.
- ^ Alan Chalmers; Erik Reinhard; Tim Davis (21. März 2011). Praktisches paralleles Rendering . CRC-Presse. ISBN 978-1-4398-6380-0.
- ^ Matloff, Norman (2011). Die Kunst der R-Programmierung: Eine Tour durch statistisches Softwaredesign , S. 347. Keine Stärke. ISBN 9781593274108 .
- ^ Leykin, Anton; Verschelde, Jan; Zhuang, Yan (2006). Parallele Homotopie-Algorithmen zur Lösung polynomialer Systeme . Verfahren des ICMS . Skript zur Vorlesung Informatik. 4151 . S. 225–234. doi : 10.1007/11832225_22 . ISBN 978-3-540-38084-9.
- ^ Moler, Cleve (1986). Heide, Michael T. (Hrsg.). Matrixberechnung auf Multiprozessoren mit verteiltem Speicher . Hypercube-Multiprozessoren . Gesellschaft für Industrielle und Angewandte Mathematik, Philadelphia. ISBN 978-0898712094.
- ^ Der Intel Hypercube Teil 2 wurde im Cleve's Corner-Blog auf der MathWorks-Website neu veröffentlicht
- ^ Kepner, Jeremy (2009). Paralleles MATLAB für Multicore- und Multinode-Computer , S.12. SIAM. ISBN 9780898716733 .
- ^ Erricos John Kontoghiorghes (21. Dezember 2005). Handbuch des parallelen Rechnens und der Statistik . CRC-Presse. ISBN 978-1-4200-2868-3.
- ^ Yuefan Deng (2013). Angewandtes paralleles Rechnen . Weltwissenschaft. ISBN 978-981-4307-60-4.
- ^ Josefsson, Simon; Percival, Colin (August 2016). "Die scrypt passwortbasierte Schlüsselableitungsfunktion" . tools.ietf.org . Abgerufen 2016-12-12 .
- ^ SeqAnswers-Forum
- ^ Wie wir unsere Gesichtserkennung 25-mal schneller gemacht haben (Entwickler-Blog-Post)
- ^ Shigeyoshi-Tsutsui; Pierre Collet (5. Dezember 2013). Massively Parallel Evolutionary Computing auf GPGPUs . Springer Wissenschaft & Wirtschaftsmedien. ISBN 978-3-642-37959-8.
- ^ Youssef Hamadi; Lakhdar Sais (5. April 2018). Handbuch des Parallel Constraint Reasoning . Springer. ISBN 978-3-319-63516-3.
- ^ Paket Simple Network of Workstations (SNOW)
Externe Links
- Peinlich parallele Berechnungen , Entwicklung eines Rechenclusters im Beowulf-Stil
- " Star-P: Hochproduktives paralleles Rechnen "