Bernstein-Bedingung

Die Bernstein-Bedingung ist ein Begriff aus der Informatik, speziell aus dem Bereich Multiprocessing, und beschreibt, unter welchen Bedingungen zwei Programmabschnitte bei paralleler Ausführung das gleiche Ergebnis wie bei sequentieller Ausführung produzieren.

Gegeben seien zwei Programmabschnitte $P_{1}$ und $P_{2}$. Die Menge der Variablen, auf die Abschnitt $P_{i}$ lesend zugreift, sei mit $I_{i}$ gegeben. Analog dazu bezeichnet $O_{i}$ die Mengen der Variablen, die von Abschnitt $P_{i}$ während der Ausführung verändert werden.

Die Bernstein-Bedingung besagt nun, dass die Abschnitte $P_{1}$ und $P_{2}$ genau dann parallel ausgeführt werden können, ohne dass dies das Ergebnis dieser oder nachfolgender Berechnungen ändert, wenn

• $I_{1}\cap O_{2}=\emptyset$,
• $I_{2}\cap O_{1}=\emptyset$, und
• $O_{1}\cap O_{2}=\emptyset$

gilt.

Siehe auch

• Nebenläufigkeit
• Parallele Programmierung

Literatur

• A. J. Bernstein: Analysis of Programs for Parallel Processing. In: IEEE Transactions on Electronic Computers. EC-15, Nr. 5, 1. Oktober 1966, ISSN 0367-7508, S. 757–763, doi:10.1109/PGEC.1966.264565.