Die Parallelisierbarkeit zweier oder mehrerer Abschnitte oder Iterationen eines Ablaufs oder von Ereignissen ist die Beurteilung, ob diese nebenläufig ausgeführt/berechnet werden können, ohne zu einem abweichenden Resultat zu führen.
„Aktionen können nebenläufig ausgeführt werden, wenn keine das Resultat des anderen benötigt.“
Die Programmabschnitte dürfen also nicht kausal voneinander abhängen. Anders ausgedrückt sind mehrere Transaktionen oder Prozesse/Threads genau dann parallelisierbar, wenn die parallele, verzahnte oder in umgekehrter Reihenfolge stattfindende Ausführung zum selben Resultat führt wie das sequentielle Ausführen.
Sind die Programmabschnitte (teilweise) voneinander abhängig, so müssen sie bezüglich dieser Abhängigkeiten synchronisiert werden, was eine Sequentialisierung (bzgl. dieser Abhängigkeit) bewirkt.
„Viele praxisrelevante Probleme besitzen Lösungsverfahren, die direkt in einen parallelen Algorithmus umgesetzt werden können. Man sagt in diesem Fall, daß das Problem eine natürliche Parallelität besitzt.“
Verfahren zur Parallelisierung sind[3]
- Binärbaummethode,
- list ranking,
- pointer doubling,
- parallel prefix,
- symmetry breaking.
Belege
Bearbeiten- ↑ Systemprogrammierung, Prozesssynchronisation: Nichtsequentialität, Wolfgang Schröder-Preikschat, Lehrstuhl Informatik 4, 6. November 2013
- ↑ „Parallele Algorithmen“, B. Monien, J. Schulze, S. Grothklags, Skriptum Uni Paderborn, 2001 (mit umfangreichem Literaturverzeichnis)
- ↑ Spezialvorlesung "Parallele Algorithmen", Uni Potsdam, Didaktik der Informatik