Was bedeutet "echte Parallelität"?

28

Ich höre oft Sätze wie "echte Nebenläufigkeitssemantik" und "echte Nebenläufigkeitsäquivalenzen" ohne Referenzen. Was bedeuten diese Begriffe und warum sind sie wichtig?

Was sind einige Beispiele für echte Gleichzeitigkeiten und wozu sind sie erforderlich? ZB in welchen Fällen sind sie besser anwendbar als mehr Standardäquivalenzen (Bisimulation, Spurenäquivalenz usw.)?

Daniil
quelle

Antworten:

23

Der Begriff "echte Parallelität" taucht in der theoretischen Untersuchung der gleichzeitigen und parallelen Berechnung auf. Dies steht im Gegensatz zur Verschachtelung von Parallelität. Echte Parallelität ist Parallelität, die nicht auf Interleaving reduziert werden kann. Parallelität ist verschachtelt, wenn bei jedem Berechnungsschritt nur eine atomare Rechenaktion (z. B. ein Nachrichtenaustausch zwischen Sender und Empfänger) stattfinden kann. Parallelität ist wahr, wenn mehr als eine solche atomare Aktion in einem Schritt stattfindet.

Die einfachste Möglichkeit, beide zu unterscheiden, besteht darin, die Regel für die parallele Komposition zu betrachten. In einer Interleaving-basierten Umgebung würde dies ungefähr so ​​aussehen:

PPP|QP|Q

Diese Regel erzwingt, dass nur ein Prozess in einer parallelen Komposition eine atomare Aktion ausführen kann. Für eine echte Parallelität wäre eine Regel wie die folgende geeigneter.

PPQQP|QP|Q

Mit dieser Regel können beide Teilnehmer einer parallelen Komposition atomare Aktionen ausführen.

Warum sollte man sich für verschachtelte Parallelität interessieren, wenn die Parallelitätstheorie eigentlich die Untersuchung von Systemen ist, die Rechenschritte parallel ausführen? Die Antwort ist, und das ist eine großartige Einsicht, dass bei einfachen Formen der Nachrichtenübermittlung die echte Nebenläufigkeit und die Interleaving-basierte Nebenläufigkeit nicht kontextabhängig voneinander unterscheidbar sind. Mit anderen Worten verhält sich verschachtelte Nebenläufigkeit so weit wie Beobachter sehen können wie echte Nebenläufigkeit. Interleaving ist eine gute Zerlegung der tatsächlichen Nebenläufigkeit. Da Interleaving in Proofs einfacher zu handhaben ist, wird häufig nur die einfachere Interleaving-basierte Parallelität (z. B. CCS undπ-Calculi). Diese Einfachheit verschwindet jedoch bei gleichzeitiger Berechnung mit umfangreicheren Beobachtungsformen (z. B. zeitgesteuerte Berechnung): Der Unterschied zwischen wahrer Nebenläufigkeit und verschachtelter Nebenläufigkeit wird beobachtbar.

Standardäquivalenzen wie Bisimulationen und Traces haben die gleichen Definitionen für echte und Interleaving-basierte Parallelität. Sie können jedoch je nach dem zugrunde liegenden Kalkül unterschiedliche Prozesse gleichsetzen oder auch nicht.

Lassen Sie mich informell erklären, warum Interleaving und wirklich gleichzeitige Interaktion in einfachen Prozesskalkülen nicht zu unterscheiden sind. Die Einstellung ist ein CCS- oder ähnlicher Kalkül. Sagen wir, wir haben ein Programmπ

P=x¯ | y¯ | x.y.a¯ | y.b¯
Dann haben wir die folgende wirklich gleichzeitige Reduktion: Dieser Reduktionsschritt kann durch die folgenden verschachtelten Schritte verglichen werden: Der einzige Unterschied zwischen beiden ist, dass der erstere einen Schritt macht, während der letztere zwei. Einfache Kalküle können jedoch nicht die Anzahl der Schritte erkennen, die zum Erreichen eines Prozesses erforderlich sind.
Py.a¯ | b¯
Px¯ | x.y.a¯ | b¯y.a¯ | b¯

Gleichzeitig hat die folgende zweite verschachtelte Reduktionssequenz: Dies ist jedoch auch eine Reduktionssequenz in einer wirklich gleichzeitigen Einstellung, solange keine echte Parallelität erzwungen wird (d. h verschachtelte Ausführungen sind zulässig, auch wenn mehr als eine Interaktion gleichzeitig möglich ist.P

Py¯ | y.a¯ | y.b¯a¯ | y.b¯
Martin Berger
quelle
Danke, tolle Antwort! Können Sie mir bitte einige Referenzen zur weiteren Lektüre geben?
Daniil
@ Daniil Ich fürchte, ich habe keine guten Referenzen zur Hand. Zum Teil ist es Folklore, zum Teil wurde es in den frühen Tagen der Parallelitätstheorie untersucht, bevor ich anfing. Wenn Sie ein bisschen Mathe machen möchten, können Sie die grundlegenden Ergebnisse selbst ermitteln. Nehmen Sie einen einfachen Prozesskalkül, z. B. den asynchronen Kalkül, und statten Sie ihn mit wirklich gleichzeitigen Reduktionen aus. Zeigen Sie, dass zwei Prozesse im neuen Kalkül durch Ihren bevorzugten (schwachen) Äquivalenzbegriff genau dann gleichgesetzt werden, wenn sie im Verschachtelungskalkül gleichgesetzt werden. π
Martin Berger
0

Um die Wahrheit zu sagen, habe ich selbst nach einer Antwort gegoogelt. Was ist die Semantik hier? Wir weisen der Beschreibung "Prozessalgebra" eine Bedeutung "Übergangssystem" zu; dh bedeutung ist das Übergangssystem, das aus der anfänglichen Systembeschreibung unter Verwendung definierter SOS-Regeln generiert wird. Somit verlieren wir unter Verwendung der Verschachtelungssemantik die gesamte gleichzeitige Struktur in dem erhaltenen Übergangssystem.

Eine andere Antwort könnte sein, dass es sich nicht um einen "beobachtbaren Unterschied" handelt, sondern um einen Unterschied in der "Beobachtbarkeit". Mit einer Interleaving-Semantik können wir nur lineare Läufe beobachten. Unter Verwendung einer echten Parallelität können wir "gleichzeitige Läufe" beobachten (vgl. das Petrinetzbuch von W.Reisig'13).

Trotzdem habe ich einige Zweifel an dem, was ich oben gesagt habe, und es wäre interessant, tiefere Einsichten zu hören. Dh mit Lamport-Vektoruhren, wie viel von der Relativitätstheorie auf die Parallelitätstheorie übertragen werden kann.

Leonid Dworzanski
quelle
1
Dass der Schritt von einem parallelen Programm zu einem Übergangssystem verlustbehaftet erfolgen kann, wurde schon früh beobachtet. John Reynolds formulierte das, was jetzt als Reynolds-Kriterium bekannt ist, um zu charakterisieren, wann die Verschachtelungssemantik für gemeinsam genutzte variable gleichzeitige Programme genau ist. Vaughan Pratt untersuchte die tatsächliche Parallelität als Modell P 1986 und zeigte zusammen mit Gordon Plotkin, wann die Parteilichkeit der Reihenfolge der Handlungen beobachtbar ist. P & P, 1987 .
Kai
@ Kai, die Referenzen sind sehr dankbar! Ich schreibe sie auf, falls die Verknüpfungen unterbrochen werden: Vaughan Pratt, Modellieren der Parallelität mit Teilaufträgen; G. Plotkin V. Pratt, Teams können Pomsets sehen. > kann verlustbehaftet gemacht werden Natürlich wollte ich nur einzelne Begriffe in "syntaktische Beschreibung / Semantik / Bedeutung" klarstellen.
Leonid Dworzanski