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 ${\displaystyle P_{1}}${\displaystyle P_{1}} und ${\displaystyle P_{2}}${\displaystyle P_{2}}. Die Menge der Variablen, auf die Abschnitt ${\displaystyle P_{i}}${\displaystyle P_{i}} lesend zugreift, sei mit ${\displaystyle I_{i}}${\displaystyle I_{i}} gegeben. Analog dazu bezeichnet ${\displaystyle O_{i}}${\displaystyle O_{i}} die Mengen der Variablen, die von Abschnitt ${\displaystyle P_{i}}${\displaystyle P_{i}} während der Ausführung verändert werden.

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

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

gilt.^[1]

• Nebenläufigkeit
• Parallele Programmierung

• 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 . 

1. ↑ B. Chapman, G. R. Gao, M. Sato, E. Ayguadé, D. Wang (Hrsg.): A Practical Programming Model for the Multi-Core Era - Springer. Springer-Verlag, 2008, S. 200, doi:10.1007/978-3-540-69303-1 (eingeschränkte Vorschau in der Google-Buchsuche). 

• Betriebssystemtheorie
• Parallelverarbeitung