Peinlich parallele Algorithmen erklärt

Bei der parallelen Programmierung ist ein peinlich paralleler Algorithmus ein Algorithmus, der keine Kommunikation oder Abhängigkeit zwischen den Prozessen erfordert. Im Gegensatz zu verteilten Computerproblemen, die eine Kommunikation zwischen Aufgaben erfordern - insbesondere bei Zwischenergebnissen - sind peinlich parallele Algorithmen in Serverfarmen, denen die in einem echten Supercomputer-Cluster verwendete spezielle Infrastruktur fehlt, einfach auszuführen.

Aufgrund der Natur peinlich paralleler Algorithmen eignen sie sich gut für große, internetbasierte verteilte Plattformen und leiden nicht unter einer parallelen Verlangsamung. Das Gegenteil von peinlich parallelen Problemen sind inhärent serielle Probleme, die überhaupt nicht parallelisiert werden können.

Der Idealfall von peinlich parallelen Algorithmen kann wie folgt zusammengefasst werden:

  • Alle Unterprobleme oder Aufgaben werden definiert, bevor die Berechnungen beginnen.
  • Alle Unterlösungen werden an unabhängigen Speicherorten (Variablen, Array-Elemente) gespeichert.
  • Somit ist die Berechnung der Unterlösungen völlig unabhängig.
  • Wenn die Berechnungen eine anfängliche oder endgültige Kommunikation erfordern, nennen wir sie fast peinlich parallel.

Viele mögen sich die Etymologie des Begriffs „peinlich“ fragen. In diesem Fall hat peinlich nichts mit Verlegenheit zu tun; Tatsächlich bedeutet dies eine Überfülle - hier bezieht es sich auf Parallelisierungsprobleme, die „peinlich einfach“ sind.

Ein häufiges Beispiel für ein peinlich paralleles Problem ist das 3D-Video-Rendering, das von einer Grafikverarbeitungseinheit ausgeführt wird, wobei jeder Frame oder jedes Pixel ohne gegenseitige Abhängigkeit verarbeitet werden kann. Einige andere Beispiele wären Proteinfaltungssoftware, die auf jedem Computer ausgeführt werden kann, wobei jede Maschine einen kleinen Teil der Arbeit erledigt, alle Teilmengen, Zufallszahlen und Monte-Carlo-Simulationen generiert.