Alt-F4 #27 – Entwerfen des Unnötigen 12.03.2021
übersetzt von dexteritas, lektoriert von Nanogamer7
Diese Woche setzt pocarski seinen Ausflug in den Fließband-Wahnsinn fort, indem er einen Blick auf Universal-Balancierer wirft. Das Ergebnis ist ebenso verrückt wie nutzlos, also weißt du, dass wir uns auf einen Leckerbissen freuen können!
Universal 8-8: Perfekt ausgeglichen, wie es alles sein sollte pocarski
Letztens habe ich einen Haufen Computerteile mit Fließbändern und Teilerfließbändern hergestellt. Diese Woche werde ich meine ungesunde Besessenheit mit dem Herumschieben von Gegenständen fortsetzen, indem ich etwas herstelle, das tatsächlich zumindest ein wenig praktisch ist: einen Balancierer. Nun, warum sollte ich einen ganzen Artikel über die Konstruktion eines Balancierers schreiben? Das liegt daran, dass der Balancierer, den wir heute herstellen werden, kein gewöhnlicher Balancierer ist!
Dieser Artikel wird nicht sehr tief in die Prinzipien des Balancierer-Designs gehen, da wir größtenteils vorgefertigte und bekannte Blueprints verwenden werden. Allerdings sind nicht alle Balancierer gleich, so dass du einige Begriffe kennen musst:
- Eingangsbalanciert: Zieht aus allen Eingängen gleichmäßig. Besonders wichtig, wenn viele Eingänge in wenige Ausgänge zusammengeführt werden.
- Ausgangsbalanciert: Gibt an alle Ausgänge gleichmäßig ab. Besonders wichtig bei der Aufteilung von wenigen Eingängen auf viele Ausgänge.
- Durchsatz-begrenzt: Hat interne Engpässe. Ein Beispiel für ein durchsatzbegrenztes System wäre die Zusammenführung von zwei Fließbändern zu einem und die anschließende Aufteilung in zwei Bänder. Ein solches System hat einen maximalen Durchsatz von einem Band, obwohl sowohl am Eingang als auch am Ausgang zwei Bänder vorhanden sind.
- Durchsatz-unbegrenzt: Das Gegenteil von durchsatzbegrenzt, hat keine internen Engpässe. Wenn X Bänder durchlaufen können, werden sie auch durchlaufen.
Alle Baupläne aus diesem Artikel (und ein paar Extras) findest du hier.
Die Prämisse
Stelle dir folgendes vor: Du bist ein neuer Spieler und hast gerade von diesen Dingen namens „Balancierer“ gehört, und wie nützlich sie sind.
Du willst ein Fließband in drei ausgleichen. Dafür solltest du einen 1-3 Balancierer verwenden, aber die kennst du noch nicht, also versuchst du es stattdessen mit einem 4-4 Balancer, an dem nur ein Eingang und drei Ausgänge angeschlossen sind. Statt des erwarteten Ausgangsverhältnisses von 1:1:1 erhältst du ein Verhältnis von 1:1:2 und bist sehr enttäuscht:
Mit diesem Artikel habe ich mir das Ziel gesetzt, einen Balancer zu bauen, für den diese Art von Intuition funktioniert; mit anderen Worten, unabhängig von der Eingangs-/Ausgangskonfiguration sind alle Ausgänge immer gleich, und alle Eingänge werden gleichmäßig entnommen. Diese Art von Balancierer ist als „universeller Balancierer“ bekannt, ein Konzept, das erstmals in diesem Beitrag vom Reddit-Benutzer u/tzwaan, einem der Moderatoren des Factorio-Subreddit, untersucht und benannt wurde.
Universal-Balancierer können, was kein Balancierer können sollte: Unabhängig von der Konfiguration sind sie input-balanciert, output-balanciert und gleichzeitig durchsatzunbegrenzt! Dies ist eine Reihe von Eigenschaften, von denen man bisher dachte, dass sie nur ein 2-2-Balancer besitzt, der nur ein einzelner Teiler ist. Der Nachteil ist, dass sie groß werden.
Konstruktionsprinzipien
Lasst uns darüber nachdenken, wie man einen 4-4 Balancer in einen 3-3 Balancer umwandeln kann. Das geschieht, indem der zusätzliche Ausgang in den ersten Fließbandteiler zurückgeschleift wird. Wir werden diese Idee als unser Grundprinzip verwenden:
Wir wollen das folgende Verhalten: Wenn ein Ausgang überläuft, möchten wir, dass die überschüssigen Elemente automatisch in die Eingänge des Balancers zurückfließen, um den vollen Durchsatz an allen Ausgängen aufrechtzuerhalten. Wie würden wir das machen?
Ganz einfach, wir verwenden Prioritätsteilerfließbänder. Indem wir die nicht-prioritären Ausgänge anschließen, sodass ihre Gegenstände auf die Schleife gelegt werden, garantieren wir, dass der Überlauf, und nur der Überlauf, in die Schleife geht. Wir müssen auch die Elemente in der Schleife mit den Eingängen zusammenführen. Dafür brauchen wir wieder Prioritätsteiler, aber dieses Mal mit Eingangspriorität. Wir setzen die Schleife als den nicht priorisierten Eingang, damit die Elemente auf der Schleife die Eingänge in keiner Weise beeinträchtigen:
Nach einigen Tests entdecken wir ein großes Problem. Wenn die Schleifenobjekte versuchen, ein Band zu betreten, das bereits voll ist, stauen sie sich einfach bis zum Abtrennungspunkt und blockieren den Überlauf, wodurch wir wieder am Anfang stehen:
Um hier Abhilfe zu schaffen, müssen wir sicherstellen, dass jedes Element der Schleife zu jedem einzelnen Ausgang der Schleife gelangen kann. Das kann auf viele Arten geschehen, aber für unsere Bedürfnisse suchen wir nach der kleinsten Anzahl von Verteilern. Zufälligerweise ist der sparsamste Weg, dies zu erreichen, ein weiterer Balancer. Fügen wir ihn der Schleife hinzu:
Wir haben jetzt einen voll funktionsfähigen universellen 4-4 Balancierer. Er kann aber noch verbessert werden. Aufgrund der Mechanik des Balancierers brauchen wir eigentlich keine vier Fließbänder, die in einer Schleife zurücklaufen. Im Allgemeinen benötigen wir drei Fließbänder weniger, als für unseren Balancierer vorgesehen sind. Das bedeutet, dass wir unseren Balancierer optimieren können, indem wir die durchlaufenden Fließbänder auf zwei komprimieren und sie dann wieder aufteilen:
Jetzt können wir die Komponenten umherschieben, bis wir etwas Kleines erhalten, etwa so:
Dieser Balancierer, ist zwar ziemlich lang, aber nur sechs breit, was bedeutet, dass man ihn in einen Standard-Vierbandbus einbauen kann und gerade genug Platz hat, um sie nebeneinander zu kacheln. Es ist wichtig zu beachten, dass dies nicht mein Design ist, obwohl es auf einem von mir basiert. Leider habe ich den Namen des Designers verloren, sodass ich keine angemessene Würdigung geben kann.
Erweiterte Konstruktion
Nun wollen wir etwas Größeres ausprobieren: einen universellen 8-8. Wir beginnen mit den gleichen Schritten wie bei unserem 4-4, nur dass wir stattdessen 8-8 Balancierer verwenden. Das ist das Ergebnis:
Leider ist der universelle 8-8, den wir auf diese Weise erhalten, unvollkommen. Anders als der Standard-4-4-Balancer ist der Standard-8-8-Balancer durchsatzbegrenzt, was den gesamten universellen 8-8-Balancer durchsatzbegrenzt macht. Hier ist eine der Ursachen, die ihn zum Engpass machen:
Wie du sehen kannst, sind sechs Bänder des Eingangs und des Ausgangs verfügbar, aber weniger als sechs kommen durch. Glücklicherweise lässt sich dies leicht beheben, indem man den Kernbalancierer einfach durch einen durchsatzunbegrenzten ersetzt:
Beachte, dass der sekundäre Balancierer durchsatzbegrenzt bleiben kann, da seine einzige Aufgabe darin besteht, den Elementen den Zugriff auf alle Bänder zu ermöglichen. Nun könnten wir versuchen, unseren Loopback-Komprimierungstrick anzuwenden, aber wir müssten acht Bänder auf fünf komprimieren und dann wieder auf acht aufteilen. Das erfordert viel mehr Splitter, als wir brauchen, wenn wir die Komprimierung überspringen und die acht Bänder direkt ausgleichen. Da wir blaue Bänder verwenden, können wir die acht blauen Bänder des Loopbacks in ein paar zwei Kacheln breite Korridore auf beiden Seiten quetschen:
Das Ganze ist nicht wiederzuerkennen, aber das liegt daran, dass der sekundäre Balancierer jetzt in einer Linie mit dem Hauptbalancierer liegt, was bedeutet, dass wir es mit bis zu zwölf Fließbändern zu tun haben, die in einen acht Kacheln breiten Raum geschoben werden, was den sekundären Balancierer zwingt, sich extrem zu verteilen. Wenn wir von blauen Fließbändern auf rote Fließbändern herunterstufen, können wir auch das Fließband komplett weglassen und einfach ein paar blaue Untergrundfließbänder verwenden, um acht rote Fließbänder in einen Raum von vier zu bekommen. Das macht auch ein Abstufen zu gelben Fließbändern einfach, wir müssen aber immer noch einige rote und blaue Untergrundfließbänder verwenden:
Es ist definitiv möglich, ein gelbes Fließbanddesign ohne blaue Untergrundfließbänder zu realisieren, aber das würde das ganze Ding viel länger machen. Es ist auch möglich, sowohl das rote als auch das gelbe Design ohne jegliche übergeordnete Untergrundfließbänder zu realisieren, aber das würde die ganze Sache um 33 % breiter und wer weiß wie viel länger machen.
Abschließende Erklärungen
Ich habe absichtlich einige Rätsel in diesem Artikel gelassen, da einige zu umständlich waren, um sie hier zu erklären, und einige verstehe ich selbst nicht so gut. Das ist der Teil, in dem ich (versuche), sie aufzuklären, also faire Warnung, es kommt technisches Zeug.
- Woher weiß man, dass ein Balancierer die effizienteste Art ist, Gegenstände auf Fließbänder zu verteilen?
Lasst uns dies mittels Induktion beweisen. Stellen wir uns zunächst vor, dass wir bereits den effizientesten möglichen Verteiler über 2N-1 Fließbänder haben, wir nennen ihn den „kleinen Verteiler“. Nun fügen wir eine Reihe von Verteilern hinzu, um jeden seiner Ausgänge in 2 zu teilen. Wir haben nun einen 2N-1-2N-Verteiler. Um die richtige Anzahl von Eingängen zu haben, kopieren wir den kleinen Verteiler und speisen seine Ausgänge in die verbleibenden Eingänge der hinzugefügten Reihe an Verteilern ein. Wir haben nun einen 2N-2N-Verteiler mit der kleinstmöglichen Anzahl von Verteilern. Jetzt sagen wir einfach, dass ein 2-2-Verteiler ein einzelner Teiler ist, was offensichtlich am effizientesten ist. Dieser effiziente Algorithmus zur Erzeugung von Umverteilern ist identisch mit dem einfachstmöglichen Algorithmus zur Erzeugung von Balancern, und du kannst dich frei fühlen, das selbst zu testen.
- Wie garantieren Sie die Eingangsbalancierung?
Wenn bei einem N-N-Balancer keine Ausgänge überlastet sind, haben alle Ausgänge den gleichen Durchsatz, unabhängig von den Eingängen. Wenn keine Eingänge überlastet sind, haben alle den gleichen Durchsatz, unabhängig von den Ausgängen. Solange der Loopback über genügend Kapazität verfügt, um alle fehlenden Eingänge zu versorgen, findet ein Eingangsausgleich statt.
- Warum drei Bänder weniger in der Rückschleife?
Um ehrlich zu sein, verstehe ich das selbst nicht ganz. Es ist ein experimentell gewonnenes Ergebnis und es hat etwas damit zu tun, dass drei die kleinste Zahl ist, die 2N nicht teilt, was drei offene Ausgänge zum schlimmsten Fall macht, mit dem der Loopback umgehen muss. Ich kann mir allerdings nicht erklären, warum eins und zwei nicht den vollen Loopback-Durchsatz benötigen. Wenn sich jemand freiwillig meldet und mir bei den Berechnungen helfen möchte, wäre ich sehr dankbar.
Zusammenfassung
Dies war ein mehr oder weniger oberflächlicher Einblick in die Welt des universellen Balancierens. Wir hätten tiefer eintauchen können, z. B. in die N-3-Theorie, aber ich glaube nicht, dass universelle Ausgleicher nützlich genug sind, um das zu rechtfertigen. Sie sind wirklich mehr ein Spielzeug und eine nette Kuriosität als etwas, das auf reale Probleme anwendbar ist. Mir fallen nur zwei potentielle Anwendungsfälle für einen Universalbalancer ein, zum einen das Be- und Entladen von Zügen mit variabler Länge und zum anderen, dass man sich nicht durch Blaupausenbücher von Balancern blättern möchte. Universal-Balancierer (und eigentlich alle Balancierer) sind einfach zu groß für zu wenig Nutzen, und man sollte stattdessen sowieso prioritätsbasierte Fließbandteiler verwenden. Der universelle 8-8 Balancierer ist ein Experiment, was man mit Fließbändern machen kann (es ist fast so, als ob er ein geistiger Nachfolger des Förderband-Addierers und des Speichers ist) und ist nicht dazu gedacht, in irgendeiner sinnvollen Weise verwendet zu werden. Wenn du eine Nische dafür findest, lass es mich bitte wissen, denn ich bin selbst sehr neugierig, wozu dieses Ungetüm nützlich sein kann. Du kannst auch gerne versuchen, die vorgestellten Designs kleiner zu machen, wenn du ein absoluter Verrückter bist und viel zu viel Freizeit hast.
Beitragen
Wie immer suchen wir nach Leuten, die zu Alt-F4 beitragen wollen, sei es mit einem Artikel oder durch Hilfe bei Übersetzungen. Wenn du etwas Interessantes im Kopf hast, das du mit der Community in einer eleganten Art teilen möchtest, hier kannst du das tun. Falls du dir unsicher bist, beantworten wir gerne Fragen zu Inhalt und Struktur. Falls das nach etwas klingt, woran du interessiert bist, tritt unserem Discord bei, um es nicht zu verpassen!