Beispielprobleme für gleichzeitige Berechnungen

Question

Es gibt eine Vielzahl von Paradigmen und Methoden für die gleichzeitige Programmierung, die heute verwendet werden. Software Transaktionsspeicher, Akteure, Shared State Concurrency, Tuple-Räume und viele, viele mehr.

Was ich jedoch fehlt, ist eine Bibliothek von interessanten Testproblemen für Nebenläufigkeit. Ein bekanntes Beispiel ist das "Dining Philosophers Problem", das weder komplex genug noch motivierend oder realistisch ist. Dann gibt es viele parallele Algorithmen (Matrixmultiplikation, Rendering, allgemeine verschachtelte Datenparallelität), die nur eine Verteilung von Arbeit erfordern, aber keine echte Parallelität mit der Kommunikation zwischen Ausführungsfäden.

Kann mir also jemand auf einige interessante Problemstellungen hinweisen, die echte Parallelität in einer interaktiven, vielleicht sogar verteilten Umgebung erfordern, die einfach genug ist, um als Beispiele für Parallelitäts-Paradigmen zu dienen? Im Idealfall möchte ich eine Reihe von Problemen finden, die als "Mangel-Test" für Gleichzeitigkeits-Paradigmen dienen (oder ihre Unterschiede hervorheben, da jedes Paradigma seine Stärken und Schwächen hat).

Jede Hilfe ist sehr geschätzt :)

Answer 1

ich vorher genau dieses Problem in Betracht gezogen haben, die zuvor einige gleichzeitige Programmierung Paradigmen selbst vorgeschlagen haben: p

Die Schlussfolgerung, die ich dann erreicht ist, dass ein solcher Test-Set doesn scheinen nicht wirklich in einer sprachunabhängigen Weise zu existieren. Obwohl es hilfreich sein könnte, dass es existiert, scheint es einige ziemlich gute Gründe dafür zu geben (nach meinem besten Wissen).

Der Großteil des Fokus innerhalb der parallelen Programmierung ist tendenziell auf Datenparallelität, so dass die gleiche Operation parallel zu verschiedenen Teilen des gleichen Datensatzes angewendet wird. Die Art der Parallelisierung auf Task-Ebene (d. H. Verschiedene Aufgaben werden parallel ausgeführt, möglicherweise Daten gemeinsam nutzen), von denen ich denke, dass Sie sprechen, ist eigentlich nicht sehr viel getan. Ich denke, das liegt daran, dass es ziemlich hart ist. Aber ich denke, es ist auch ein bisschen schwierig, denn die meisten Probleme eignen sich nicht besonders gut für diese Art von Nebenläufigkeit. Die Beschreibung eines verteilten Systems im Hinblick auf Parallelitätsprimitive kann hilfreich sein, aber diese Systeme neigen dazu, entkoppelt zu werden, so dass es ein Protokoll (geschrieben oder impliziert) gibt, das ihre Kommunikation moderiert. Menschen neigen dazu, diese Art von Systemen nicht als offensichtlich "gleichzeitige" Programmier-Situationen zu betrachten, obwohl sie innerhalb des richtigen Rahmens betrachtet werden (dh unter Berücksichtigung von "Client" und "Server" als Agenten, die parallel zur Synchronisation arbeiten). .

Die einzigen Orte, an denen Sie einige Inspirationsquellen finden könnten, wären einzelne Implementierungen. Erlang, Occam (und Occam-pi), Alice, CML, Concurrent Haskell usw. haben wahrscheinlich kleine Testkorpusse, aber sowohl die Probleme als auch ihre Implementierungen werden darauf ausgerichtet sein, in einer bestimmten Sprache implementiert zu werden (weil sie es offensichtlich sind) implementierbar in dieser Sprache!). Vielleicht könnten Sie auch die Gemeinschaften, die an multi-party session types arbeiten, und verschiedene process calculi wie Pi-Kalkül, CCS und CSP sehen, um zu sehen, welche Arten von Systemen sie als Beispielmodelle verwenden. Die Idee einer sprachunabhängigen Standardmenge von Problemen zur Beschreibung gleichzeitiger Systeme ist ansprechend, aber an dieser Stelle etwas schwer fassbar, denke ich.