Wie kann ich sicher N Threads machen in etwa mit der gleichen Geschwindigkeit laufen?

https://stackoverflow.com/questions/641906

22-07-2019
|

Frage

Ich bin liebäugelt mit der Idee, eine Physik-Simulation Software zu schreiben, in dem jedes physisches Element in einem eigenen Thread simuliert werden würde.

Es hätte mehrere Vorteile dieses Ansatzes sein. Es wäre konzeptionell ganz in der Nähe, wie die reale Welt funktioniert. Es wäre viel einfacher, das System auf mehrere Maschinen zu skalieren.

Doch für diese Arbeit ich sicherstellen müssen, dass alle Threads mit der gleichen Geschwindigkeit, mit einer eher liberalen Auslegung des Begriffs ‚gleichen‘ laufen. Sagen Sie innerhalb von 1% der jeweils anderen.

Das ist, warum ich nicht unbedingt eine Thread.join () ähnliche Lösung benötigen. Ich will nicht, etwas uber-Steuerung der Schule Herrin, die alle Threads regelmäßig synchronisieren mit jedem anderen gewährleistet. Ich muß nur in der Lage sein, um die Laufzeit zu fragen (was auch immer es ist --- könnte Java, Erlang, oder was auch immer für dieses Problem am besten geeignet ist), um die Fäden zu einer mehr oder weniger gleichen Geschwindigkeit laufen zu lassen.

würden Anregungen äußerst geschätzt.

UPDATE 2009-03-16

Ich wollte allen danken, die diese Frage beantwortet haben, insbesondere alle, deren Antwort war im Wesentlichen „dies nicht tun“. Ich verstehe mein Problem jetzt viel besser Dank an alle Kommentare, und ich bin weniger sicher, ob ich sollte auch weiterhin, wie ich ursprünglich geplant. Dennoch fühlte ich, dass Peter Antwort war die beste Antwort auf die Frage selbst, weshalb ich es akzeptiert.

Lösung

Sie werden eine Art Synchronisation benötigen. CyclicBarrier Klasse hat, was Sie brauchen:

Eine Synchronisationshilfe, die eine ermöglicht Gewindesatz auf alle warten jeweils andere einen gemeinsamen Sperrpunkt zu erreichen. CyclicBarriers sind in Programmen nützlich die eine feste Größe Partei Fäden, die gelegentlich warten müssen, für einander. Die Barriere wird aufgerufen zyklisch, weil es kann wiederverwendet werden, nachdem die wartenden Threads freigegeben werden.

Nach jedem ‚tick‘ können Sie alle Ihre Fäden lassen, für andere warten, die langsamer waren. Wenn die verbleibende Fäden die Barriere erreichen, werden sie alle weiter.

Andere Tipps

Sie können nicht wirklich das tun, ohne Koordination. Was passiert, wenn ein Element beendet billiger Berechnungen als andere benötigen up (in einer möglicherweise nicht offensichtliche Art und Weise)?

Sie brauchen nicht unbedingt ein uber-Controller - Sie könnten nur pro Thread eine Art Schrittzähler halten und haben einen globalen Zähler den „langsamsten“ Thread anzeigt. (Wenn jeder Thread einige Arbeit getan hat, hätte es prüfen, ob es hinter den anderen gefallen war, und den Zähler aktualisieren, wenn so.) Wenn ein Thread merkt es ist ein langer Weg vor dem langsamsten Thread, es könnte nur kurz warten ( möglicherweise auf einem Monitor).

Genau das tun alle so oft zu viel Aufwand zu vermeiden, dass aufgrund gemeinsam genutzter Daten Anstoßes und ich denke, es könnte ziemlich gut funktionieren.

Themen gemeint sind völlig unabhängig voneinander ausgeführt werden, was bedeutet, sie in irgendeiner Weise zu synchronisieren, ist immer ein Schmerz. In Ihrem Fall benötigen Sie eine zentrale „Uhr“, denn es gibt keine Möglichkeit, die VM zu sagen, dass jeder Thread soll die gleiche Menge an ... äh bekommen ... was soll es bekommen? Die gleiche Menge an RAM? Wahrscheinlich keine Rolle spielt. Die gleiche Menge an CPU? Sind alle Ihre Objekte so ähnlich, dass jeder die gleiche Anzahl von Assembler-Anweisungen benötigt?

Also mein Vorschlag, einen zentralen Takt zu verwenden ist, die Uhr zu jedem Prozess sendet Zecken. Alle Fäden in jedem Prozess die Zecken lesen (was absolut sein sollte), die Berechnung der Differenz zum letzten Tick sie sahen, und dann ihr internes Modell entsprechend aktualisieren.

Wenn ein Thread die Aktualisierung abgeschlossen ist, muss er sich schlafen gelegt; Warten auf den nächsten Tick. In Java verwendet wait () auf dem "Tick empfängt" Schloss und wacht alle Themen mit "notifyAll ()".

würde ich empfehlen Fäden nicht, wo immer möglich, weil sie nur später Probleme hinzufügen, wenn du nicht aufpasst. Wenn Physik-Simulationen tun könnten Sie Hunderte von Tausenden von Einzelobjekten für größere Simulationen verwenden. Sie können nicht möglicherweise erstellen so viele Threads auf jedem Betriebssystem, die ich kenne, und selbst wenn man könnte, es wäre wie Scheiße durchführen!

In Ihrem Fall könnten Sie eine Anzahl von Threads, erstellen und eine Ereignisschleife in jedem Thread stellen. Ein ‚Master‘ Thread könnte die Ausführungsreihenfolge und ein ‚Prozess‘ Ereignis für jeden Worker-Thread per Post aufwacht und macht sie einige Arbeit zu tun. Auf diese Weise werden die Fäden schlafen, bis Sie ihnen sagen, zu arbeiten.

Sie sollten in der Lage sein, den Master-Thread zu bekommen mit einer Rate ticken, dass Ihr alle Worker-Threads vor dem nächsten Tick abschließen können.

Ich glaube nicht, Threads die Antwort auf Ihr Problem, mit Ausnahme der Parallelisierung in eine kleine Anzahl von Arbeitsthreads (gleich die Anzahl der Kerne in der Maschine) sind, die jeweils linear eine Reihe von physikalischen Objekten sequenzieren. Sie kann immer noch den Master / ereignisgesteuerten Ansatz verwenden, auf diese Weise, aber Sie würden eine Menge des Kopfes entfernen.

Bitte nicht. Threads ist ein O / S Abstraktion ermöglicht das Auftreten von paralleler Ausführung. Mit mehrere und Multi-Core-CPUs, die O / S kann (muss aber nicht) verteilt Fäden zwischen den verschiedenen Kernen.

Das nächste, was zu Ihrer Skalierbarkeit Vision, die ich als praktikabel sehen ist Worker-Threads zu verwenden, zu dimensionieren etwa die Anzahl der Kerne entsprechen, die Sie haben, und verteilen Arbeit unter ihnen. Ein Rohentwurf: eine Klasse ActionTick definieren, die die Aktualisierung für ein Teilchen der Fall ist, und lassen den Arbeiter-Thread ActionTicks Pick aus einer gemeinsamen Warteschlange zu verarbeiten. Ich sehe mehrere Herausforderungen sogar mit einer solchen Lösung.

Threading Gemeinkosten: Sie Kontext-Overhead zwischen den verschiedenen Arbeitsthreads bekommen wechseln. Themen selbst sind teuer (wenn nicht sogar als verderblich wie Prozesse): Testleistung mit unterschiedlichen Gewindepoolgrößen. Das Hinzufügen von mehr Threads über die Anzahl der Kerne neigt Leistung zu reduzieren!
Synchronisationskosten: Sie mehrere Flecken des Anstoßes bekommen: Zugang zum Arbeitswarteschlange für einen, aber schlimmer noch, den Zugang zu der simulierten Welt. Sie müssen die Auswirkungen der einzelnen ActionTick begrenzen oder eine Menge Sperren / Entsperren implementieren.
Schwierigkeit der Physik Optimierung der. Sie möchten die Anzahl der Objekte / Partikel, die jeweils ActionTick schaut begrenzen (Entfernung cut-off? 3D-Baum-Unterteilung des Simulationsraum?). In Abhängigkeit von dem Simulationsbereich können Sie in der Lage sein, eine Menge Arbeit zu beseitigen, indem geprüft wird, ob alle Änderungen auch in einer Untergruppe von Gegenständen benötigt wird. Doing diese Art von Optimierungen ist einfacher, bevor Einzelteile arbeiten, anstatt als verteilte Algorithmus Warteschlangen. Aber dann, dass ein Teil Ihrer Simulation wird ein potentieller Skalierbarkeit Engpass.
Komplexität. Einfädeln und Parallelität führt mehrere Dosen von Würmern zu einer Lösung. Denken Sie immer an andere Optionen zuerst - aber wenn Sie sie benötigen, versuchen Fäden vor der eigenen Arbeit Artikel Planung erstellen, Sperren und Ausführungsstrategien ...

Vorab: Ich habe nicht mit einem massiven Simulationssoftware, um nur einige Bastler Code gearbeitet.

Wie Sie erwähnen, gibt es viele „dies nicht tun“ Antworten. Die meisten scheinen Themen wie OS Themen von Java verwendet zu lesen. Da Sie Erlang in Ihrem Beitrag erwähnt, würde Ich mag eine Erlang zentrierte Antwort senden.

Die Modellierung diese Art von Simulation mit Prozessen (oder Aktoren, Mikrofäden, grünen Fäden, wie sie manchmal genannt werden) muß nicht notwendigerweise eine Synchronisation. Im Wesentlichen haben wir ein paar (wahrscheinlich Tausende oder Hunderttausende) Physik Objekte, die simuliert werden müssen. Wir wollen diese Objekte so realistisch wie möglich simulieren, aber es ist wahrscheinlich auch eine Art Echtzeit-Aspekt beteiligt (nicht obwohl sein müssen, müssen Sie diese in Ihrer Frage nicht erwähnt).

Eine einfache Lösung für jedes Objekt zum Laichen eines Erlang Prozess sein würde, schickte Zecken alle von ihnen und die Ergebnisse der Simulation sammeln, bevor mit dem nächsten Tick fortfahren. Dies ist in der Praxis zu synchronisieren allem. Es ist natürlich eher eine deterministische Lösung und garantiert keine Echtzeit-Eigenschaften. Es ist auch nicht-trivial, wie die Prozesse miteinander reden würden die Daten, die sie für die Berechnungen benötigen. Sie müssen wahrscheinlich sie in kluger Weise (Kollisionsgruppen usw.) zu gruppieren, haben hibernated Prozesse für Schlaf Objekte (die Erlang ordentlich Unterstützung hat), etc. Dinge zu beschleunigen.

Um Echtzeit-Eigenschaften erhalten Sie wahrscheinlich benötigen, um die Berechnungen durch die Prozesse (Handelsgenauigkeit für Geschwindigkeit) durchgeführt, um zurückhalten. Dies könnte vielleicht durch Aussenden getan werden Zecken ohne für Antworten warten, und lassen die Objekt-Prozesse zu jeder Antwort zurück zu kreuzen mit ihrer aktuellen Position und andere Daten, die Sie benötigen (auch wenn es nur an der angenähert werden könnten Zeit). Wie DJClayworth sagt, dies zu Fehlern führen könnte, in der Simulation zu akkumulieren.

ich in gewisser Hinsicht denke, die Frage wirklich ist, wenn es möglich ist, die Stärke der Parallelität zu verwenden irgendeine Art von Vorteile zu erlangen hier . Wenn Sie die Synchronisation benötigen, ist es ein ziemlich starkes Zeichen dafür, dass Sie nicht brauchen, Parallelität zwischen den einzelnen Physik-Objekt. Da Sie im Wesentlichen eine Menge Rechenzeit wegzuwerfen, indem für andere Prozesse warten. Sie könnten Parallelität bei der Berechnung verwenden, aber das ist eine andere Diskussion, denke ich.

Hinweis: keine dieser Ideen nimmt die eigentlichen Physik-Berechnungen berücksichtigt. Dies ist nicht Erlang starke Seite und vielleicht in einer C-Bibliothek durchgeführt werden könnte oder was auch immer Ihre Fantasie schlägt, je nach der Art des Merkmals, die Sie wollen.

. Hinweis: Ich weiß nicht, jeden Fall, in dem diese (vor allem nicht von mir) geschehen ist, so kann ich nicht garantieren, dass dies eine fundierte Beratung

Auch mit perfekter Software, Hardware wird verhindert, dass Sie dies zu tun. Hardware-Threads haben in der Regel nicht fair Leistung. Über einen kurzen Zeitraum, haben Sie Glück, wenn Threads innerhalb + -10% Leistung laufen.

Das ist natürlich, Ausreißer. Einige Chipsätzen werden einige Kerne in Energiesparmodus und andere laufen nicht. Ich glaube, eines der Blue Gene Forschung Maschinen Planung von Hardware-Threads Software gesteuert hatte anstelle von Sperren.

Erlang wird standardmäßig versuchen und ihre Prozesse gleichmäßig verteilt über die zur Verfügung stehenden Threads. Es wird auch standardmäßig versuchen Threads auf allen verfügbaren Prozessoren zu laufen. Also, wenn Sie genug runnable Erlang Prozesse haben, dann werden Sie eine relativ ausgewogene Balance erhalten.

Ich bin kein Threading-Experte, aber ist nicht der Sinn der Threads, die sie voneinander unabhängig sind - und nicht deterministisch

Ich glaube, Sie haben ein grundlegendes Missverständnis in Frage, wo Sie sagen:

Es wäre konzeptionell ganz in der Nähe, wie die reale Welt funktioniert

Die reale Welt funktioniert nicht überhaupt in einer fadenartigen Art und Weise. Themen in den meisten Maschinen sind nicht unabhängig und nicht eigentlich sogar die gleichzeitige (die OS wird stattdessen kontext schaltend). Sie bieten den größten Nutzen, wenn es eine Menge IO ist oder das Warten auftritt.

Am wichtigsten ist, die die reale Welt „verbrauchen mehr Ressourcen“ nicht als komplexere Dinge passieren. Denken Sie an dem Unterschied zwischen zwei Objekten aus einer Höhe fallen, eine fällt glatt und die andere eine Art von komplexer Taumelbewegung durch die ...

würde ich eine Art „Taktgenerator“ machen - und würde jedes neue Objekt / Thread dort registrieren. Die Uhr wird alle registrierten Objekte benachrichtigen, wenn die delta-t bestanden hat. Allerdings bedeutet dies nicht, dass Sie einen separaten Thread für jedes Objekt benötigen. Im Idealfall haben Sie so viele Threads als Prozessoren. Von einem Design Punkt könnte Sie die Ausführung der Objekt-Aufgaben durch einen Vollstrecker oder einen Gewinde-Pool trennen, z.B. wenn ein Objekt der Zecke Ereignis empfängt, geht es zu einem Thread-Pool und Zeitplan selbst für die Ausführung.

Zwei Dinge haben, um zu geschehen, dies zu erreichen. Sie müssen sicherstellen, thah Sie die gleiche Anzahl von Threads pro CPU-Kern haben, und Sie brauchen eine Art Synchronisation.

Das sync kann ziemlich einfach sein, wie „Zyklus-done“ Variable für jeden Thread überprüft, während der Berechnung durchgeführt wird, aber Sie können es nicht vermeiden.

Arbeiten bei Steuerung für Motoren i etwas Mathematik verwendet habe Geschwindigkeit bei stabilem Zustand zu halten. Das System hat die PID-Regelung, Proportional-Integral-Differenzial. Aber das ist analog / digital-System. Vielleicht ähnlich bestimmen können, wie Mus Zeit jeder Thread ausgeführt werden müssen, aber die größte Spitze kann ich Ihnen, dass alle Threads jeweils eine Taktsynchronisation haben.

Ich bin zuerst Ich bin kein Einfädeln Experten zugeben, aber das klingt wie ein sehr falscher Weg Simulation zu nähern. Wie andere schon zu viele Threads kommentiert haben, die rechnerisch teuer. Außerdem, wenn Sie zu tun planen, was ich denke, Sie tun denken, Ihre Simulation herausstellen kann statistische Ergebnisse produzieren (möglicherweise keine Rolle, ob Sie ein Spiel zu machen).

würde ich mit ein paar Arbeitsthreads gehen verwendet, um diskrete Schritte der Simulation berechnet werden.

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow