Mathematik und Berechnung

Experimente mit Zufallsmatrizen

Große Matrizen voller Zufallszahlen, wiederholt diagonalisiert, um die Statistik ihrer Eigenwerte zu untersuchen.

Frage, die sie beantwortet: In welches Muster fallen die Eigenwerte einer Zufallsmatrix, und passt es zu anderen Gebieten der Mathematik und Physik?

Lässt aus: Tastet immer nur eine winzige Ecke eines unendlichen Raums möglicher Matrizen ab.

Läuft auf: etwa 10¹² FLOPS grob ein Universitätscluster, der viele große Matrizen erzeugt und diagonalisiertSeit: 1955 Wigners frühe Arbeit zur Eigenwertstatistik von Zufallsmatrizen

Experimente mit Zufallsgraphen

Graphen, die nach einer Zufallsregel Knoten für Knoten oder Kante für Kante erzeugt werden, um zu sehen, welche Eigenschaften, etwa Zusammenhang oder Clusterbildung, typischerweise auftreten.

Frage, die sie beantwortet: Wie sieht ein „typisches“ Netz unter dieser Regel zum Hinzufügen von Knoten und Kanten aus?

Lässt aus: Netzwerke der realen Welt sind selten so sauber wie die Regel, die das Modell erzeugt.

Läuft auf: etwa 10¹⁰ FLOPS grob Läuft auf einem Desktop für Graphen bis zu Millionen KnotenSeit: 1959 Erdős' und Rényis Zufallsgraphenmodell

Perkolationssimulation

Ein Gitter oder Netzwerk, dessen Knoten oder Verbindungen zufällig geöffnet werden; beobachtet wird der Punkt, an dem plötzlich ein zusammenhängender Pfad das ganze System durchspannt.

Frage, die sie beantwortet: Bei welcher Dichte wird ein Zufallsnetz plötzlich von einem Ende zum anderen zusammenhängend?

Lässt aus: Idealisierte Gitter verhalten sich sauberer als jedes echte poröse Material oder Netzwerk.

Läuft auf: etwa 10¹⁰ FLOPS grob ein Desktop-Rechner für große GitterdurchläufeSeit: 1957 Broadbents und Hammersleys Einführung der Perkolationstheorie

Suchen der experimentellen Mathematik

Numerische Brute-Force-Suche nach Mustern, Gegenbeispielen oder exakten Beziehungen zwischen Zahlen, weit über das hinaus, was sich von Hand prüfen ließe.

Frage, die sie beantwortet: Stimmt diese Vermutung für jeden Fall, den sich überhaupt prüfen lässt, und zeigt sich ein Muster?

Lässt aus: Keine Menge geprüfter Fälle ist ein Beweis, wie viele sich auch als zutreffend erweisen.

Läuft auf: etwa 10¹¹ FLOPS grob ein Universitätscluster, der tagelang an einer einzigen Suche läuftSeit: 1963 spätestens 1963, Computersuchen nach ganzzahligen Relationen und Primzahlmustern

Monte-Carlo-Schätzung von Konstanten

Zufallsstichproben, mit denen eine mathematische Konstante oder ein Integral geschätzt wird, etwa indem Punkte gestreut werden, um eine Fläche zu schätzen, als Übung und nicht für ein physikalisches Modell.

Frage, die sie beantwortet: Wie genau kann blindes Zufallssampling allein eine exakte mathematische Größe festlegen?

Lässt aus: Konvergiert weit langsamer als fast jedes ausgefeiltere numerische Verfahren.

Läuft auf: etwa 10⁹ FLOPS grob Läuft auf einem Laptop in Sekunden bis MinutenSeit: 1946 Ulams Idee von 1946; von Neumann schlug im März 1947 eine Version für elektronische Computer vor, und die Methode wurde 1949 erstmals veröffentlicht QuelleIm Simulationen-Baum: Monte-Carlo-Methode

Das interaktive Modell ausführen

Rechnerische Suchen der Zahlentheorie

Große Zahlen, die auf Primalität getestet, faktorisiert oder auf besondere Eigenschaften wie vollkommene Zahlen durchsucht werden, mit Algorithmen, die im großen Maßstab statt von Hand laufen.

Frage, die sie beantwortet: Hat diese riesige Zahl die gesuchte Eigenschaft, und wie weit lässt sich der Rekord bei der Suche treiben?

Lässt aus: Rekordsuchen sagen wenig über Zahlen, die noch niemand zu prüfen gedacht hat.

Läuft auf: etwa 10¹³ FLOPS grob ein verteiltes Volunteer-Computing-Projekt auf vielen gespendeten RechnernSeit: 1951 Lucas' Handtest für Mersenne-Primzahlen, 1951 erstmals per Computer ausgeführt

Numerik chaotischer Attraktoren

Ein kleines System nichtlinearer Gleichungen, Schritt für Schritt integriert, um die empfindliche Abhängigkeit von Anfangsbedingungen und einen fraktalen Attraktor sichtbar zu machen.

Frage, die sie beantwortet: Warum wird ein einfaches deterministisches System unvorhersagbar?

Lässt aus: Numerische Rundung führt dazu, dass eine lange Trajektorie keine echte Bahn ist, sondern nur eine, die nahe an einer bleibt.

Läuft auf: etwa 10³ FLOPS grob ein paar Gleichungen, Sekunden auf einem Laptop.Seit: 1963 Lorenz' deterministischer nichtperiodischer Fluss, ein Konvektionsmodell, das auf einem Computer lief. QuelleIm Simulationen-Baum: Lorenz’ chaotische Konvektion

Nichtlineare Gitterexperimente

Eine Kette aus Massen mit nichtlinearen Federn wird in einer einzigen Schwingungsmode angestoßen und beobachtet: Verteilt sich die Energie gleichmäßig, wie es die Thermodynamik nahelegt?

Frage, die sie beantwortet: Teilt eine nichtlineare Kette ihre Energie gleichmäßig auf alle ihre Bewegungen auf?

Lässt aus: Die Ergebnisse hängen von der gewählten Kette und vom Anfangszustand ab.

Läuft auf: etwa 10³ FLOPS grob nach heutigen Maßstäben winzig; das Original verwendete ein paar Dutzend Massen.Seit: 1955 Fermis, Pastas und Ulams Studien nichtlinearer Probleme auf einem frühen Digitalrechner. Quelle

Numerische Soliton-Experimente

Eine nichtlineare Wellengleichung, auf einem Gitter gelöst, um zu beobachten, wie Pulse einander durchdringen und ihre Gestalt behalten, was lineare Wellen nicht tun.

Frage, die sie beantwortet: Warum durchdringen sich manche nichtlinearen Wellen unverändert?

Lässt aus: Es zeigt eine Familie von Gleichungen, nicht das allgemeine Verhalten nichtlinearer Wellen.

Läuft auf: etwa 10⁴ FLOPS grob ein eindimensionales Gitter, heute trivial.Seit: 1965 Zabusky und Kruskals Wechselwirkung von Solitonen in einem stoßfreien Plasma und die Wiederkehr von Anfangszuständen. Quelle

Rendering von Fraktalmengen

Eine einfache iterierte Formel, an jedem Ort der komplexen Ebene geprüft, ob sie davonläuft; so entsteht der Rand der Menge stabiler Punkte.

Frage, die sie beantwortet: Welche Form hat die Menge, in der eine einfache Iteration beschränkt bleibt?

Lässt aus: Fluchttests deuten die Zugehörigkeit nur an, und das Bild ist eine Abtastung mit endlicher Auflösung einer unendlich detaillierten Menge.

Läuft auf: etwa 10⁹ FLOPS grob tiefe Zooms brauchen Iteration mit erweiterter Genauigkeit an Millionen Punkten.Seit: 1980 Mandelbrots fraktale Aspekte der Iteration von z zu lambda z(1-z), erste Computerbilder der Mandelbrot-Menge. Quelle

Selbstorganisierte Kritikalität im Sandhaufen

Körner fallen auf ein Gitter und kippen weg, wenn der Haufen zu steil wird. So entstehen Lawinen jeder Größe ohne Feinabstimmung, als Modell dafür, wie Systeme einen kritischen Zustand erreichen.

Frage, die sie beantwortet: Warum treten Lawinen jeder Größe ohne jede Feinabstimmung auf?

Lässt aus: Ob echte Systeme dieselbe Skalierung teilen, ist umstritten.

Läuft auf: etwa 10⁹ FLOPS grob Lange Läufe auf großen Gittern, um die Skalierung zu sehen.Seit: 1987 Bak, Tang und Wiesenfelds selbstorganisierte Kritikalität: eine Erklärung für 1/f-Rauschen. Quelle

Berechnung von Nullstellen der Riemann'schen Zetafunktion

Die Werte der Zeta-Funktion entlang ihrer kritischen Geraden werden berechnet, um ihre Nullstellen zu finden und zu zählen und zu prüfen, ob sie dort liegen, wo die Hypothese es sagt.

Frage, die sie beantwortet: Liegen alle nichttrivialen Nullstellen der Zetafunktion auf einer Geraden?

Lässt aus: Eine endliche Prüfung kann, wie lang sie auch ist, nicht beweisen, dass jenseits davon keine Nullstelle abseits der Geraden existiert.

Läuft auf: etwa 10¹⁸ FLOPS grob Jahrzehnte an CPU-Zeit bei den größten Suchen.Seit: 1953 Turings Berechnungen der Riemannschen Zetafunktion. Quelle

Stellen von Pi per Computer

Reihen für Pi werden mit exakter Arithmetik auf enorme Stellenzahlen summiert und testen so sowohl die Zahl als auch die Maschine.

Frage, die sie beantwortet: Sehen die Ziffern von Pi zufällig aus, und kann man der Maschine in diesem Maßstab trauen?

Lässt aus: Die Ziffern beantworten keine offene Frage, und Prüfungen fangen Hardwarefehler nur ab, wenn die Methode unabhängig ist.

Läuft auf: etwa 10¹⁷ FLOPS grob Monate auf einem Server für Hunderte Billionen Stellen.Seit: 1950 Reitwiesners Bestimmung von Pi und e auf mehr als 2.000 Dezimalstellen mit dem ENIAC (veröffentlicht 1950, nachgedruckt in Pi: A Source Book). Quelle

KI-gestützte Entdeckung von Vermutungen

Maschinelles Lernen auf großen Tabellen mathematischer Objekte findet heraus, welche Eigenschaften zusammenhängen, und schlägt so eine Vermutung vor, die Mathematiker dann zu beweisen versuchen.

Frage, die sie beantwortet: Welche bislang unentdeckte Beziehung zwischen diesen mathematischen Größen lohnt es zu beweisen?

Lässt aus: Es legt nur Muster nahe und beweist selbst nichts, und manche Regelmäßigkeiten in den Daten können Artefakte der Datenerzeugung sein.

Läuft auf: etwa 10¹⁵ FLOPS grob Tage auf einigen GPUs pro Datensatz.Seit: 2021 Davies und Kollegen, Fortschritte in der Mathematik, indem menschliche Intuition durch KI geleitet wird. Quelle

Gelernte Suche nach Algorithmen und Konstruktionen

Ein spielendes System oder Sprachmodell sucht nach neuen Verfahren oder mathematischen Objekten, während ein Computer jeden Kandidaten auf Korrektheit prüft.

Frage, die sie beantwortet: Kann ein Programm einen schnelleren Algorithmus oder ein größeres Beispiel entdecken, als Menschen gefunden haben?

Lässt aus: Jedes Ergebnis ist ein einzelnes neues Beispiel, und die Suche deckt nur die Arten von Objekten ab, die ihre Entwickler als Spiel gefasst haben.

Läuft auf: etwa 10¹⁷ FLOPS grob Tage bis Wochen auf Beschleuniger-Clustern.Seit: 2022 Fawzi und Kollegen, AlphaTensor, entdeckt schnellere Algorithmen zur Matrixmultiplikation mit Reinforcement Learning. Quelle

Modellprüfung

Jeder erreichbare Zustand eines endlichen Systems, etwa eines Protokolls oder eines Schaltungsentwurfs, per Computer aufgezählt, um zu prüfen, dass eine Eigenschaft in allen gilt.

Frage, die sie beantwortet: Gibt es einen erreichbaren Zustand, in dem dieses Design seine eigenen Regeln bricht?

Lässt aus: Zustandsräume explodieren über das hinaus, was sich prüfen lässt, deshalb werden reale Entwürfe zuerst vereinfacht.

Läuft auf: etwa 10¹² FLOPS grob ein Universitätscluster, der einen großen, aber begrenzten Zustandsraum vollständig durchläuftSeit: 1981 Clarkes und Emersons Einführung des Model Checking

Suche beim automatisierten Beweisen von Sätzen

Eine Suche durch Ketten logischer Schlüsse, Schritt für Schritt vom Computer erzeugt, auf der Suche nach einem Beweis oder Gegenbeweis einer mathematischen Aussage.

Frage, die sie beantwortet: Gibt es eine gültige Kette logischer Schritte von den Axiomen zu dieser Aussage?

Lässt aus: Findet Beweise, die kein Mensch wählen würde, und manchmal gar keine in Reichweite.

Läuft auf: etwa 10¹¹ FLOPS grob ein Universitätscluster, der Stunden bis Tage suchtSeit: 1956 der Logic Theorist, ein frühes Programm zur automatischen Beweissuche

SAT und Constraint-Lösung

Millionen Kombinationen von Wahr-Falsch-Werten, systematisch durchsucht, um eine große Menge logischer Bedingungen zu erfüllen, genutzt zur Planung, Routenwahl oder Verifikation von Entwürfen.

Frage, die sie beantwortet: Gibt es irgendeine Belegung von Werten, die alle diese Bedingungen gleichzeitig erfüllt?

Lässt aus: Manche Instanzen sind so schwer, dass kein noch so guter Solver rechtzeitig fertig wird.

Läuft auf: etwa 10¹¹ FLOPS grob eine Workstation bis zu einem Cluster, je nach ProblemgrößeSeit: 1962 das Davis-Putnam-Verfahren zur Erfüllbarkeitssuche

Modellierung kryptografischer Angriffe

Ein Code oder Schlüsselaustausch-Verfahren, das in der Simulation millionenfach angegriffen wird, per Brute Force, statistischer Verzerrung oder einer modellierten Schwachstelle, um zu messen, wie viel Aufwand das Knacken wirklich kostet.

Frage, die sie beantwortet: Wie viele Operationen wären tatsächlich nötig, um dies zu brechen, und ist diese Zahl noch sicher groß?

Lässt aus: Testet nur die Angriffe, die der Analyst zu modellieren dachte, nicht den, den noch niemand gefunden hat.

Läuft auf: etwa 10¹⁴ FLOPS grob ein verteilter Cluster aus vielen Maschinen, der Angriffsversuche ausführtSeit: 1976 spätestens 1976, rechnerische Analyse der Stärke von Chiffren und Schlüsselaustausch

Simulation von Seitenkanal-Lecks

Stromaufnahme, Zeitverhalten oder elektromagnetische Abstrahlung eines Geräts werden modelliert, während es eine kryptografische Operation ausführt, um zu sehen, was ein Lauscher von außen daraus lernen könnte.

Frage, die sie beantwortet: Wie viel vom geheimen Schlüssel sickert durch das physikalische Verhalten des Geräts, nicht durch die Mathematik?

Lässt aus: Laborbedingungen fangen sauberere Signale ein, als ein verrauschtes echtes Gerät üblicherweise preisgibt.

Läuft auf: etwa 10¹⁰ FLOPS grob eine Workstation, die die Leistungs- oder Zeitspur eines Geräts modelliertSeit: 1996 Kochers Nachweis von Timing-Angriffen auf kryptografische Implementierungen

Verifikation von Sicherheitsprotokollen

Jede Nachricht, die ein Angreifer in einem Kommunikationsprotokoll senden, wiedereinspielen oder fälschen könnte, per Computer aufgezählt, um zu prüfen, ob sich ihm ein Geheimnis oder eine Identität entlocken lässt.

Frage, die sie beantwortet: Kann irgendeine Nachrichtenfolge dieses Protokoll dazu bringen, ein Geheimnis preiszugeben oder eine gefälschte Identität zu akzeptieren?

Lässt aus: Prüft das Protokoll wie spezifiziert, nicht die Abkürzungen, die eine echte Implementierung nimmt.

Läuft auf: etwa 10¹¹ FLOPS grob eine Workstation bis zu einem Cluster, der den Nachrichtenraum eines Protokolls prüftSeit: 1989 das Dolev-Yao-Modell, eine grundlegende Basis für die Protokollverifikation

Computergestützter Beweis durch erschöpfende Fallprüfung

Ein Theorem, reduziert auf eine endliche Liste von Fällen, jeder per Programm verifiziert, weil kein Mensch sie alle prüfen könnte.

Frage, die sie beantwortet: Lässt sich ein Beweis vollenden, indem eine Maschine jeden Fall prüft?

Lässt aus: Das Vertrauen verlagert sich auf das Programm, die Hardware und das Argument der Fallreduktion.

Läuft auf: etwa 10⁹ FLOPS grob etwa tausend Stunden auf einem Großrechner für das Original; heute weit weniger.Seit: 1977 Appels und Hakens Beweis, dass jede ebene Landkarte vierfärbbar ist, mit computergeprüfter Reduzierbarkeit. Quelle

Validierte Numerik

Berechnungen mit garantierten Schranken, sodass ein numerisches Ergebnis eine mathematische Aussage beweist, etwa die Existenz eines chaotischen Attraktors.

Frage, die sie beantwortet: Lässt sich ein berechnetes Ergebnis als richtig beweisen, nicht nur als wahrscheinlich genau?

Lässt aus: Schranken können über lange Zeiträume explodieren, sodass sich Beweise auf kurze oder gutartige Probleme beschränken.

Läuft auf: etwa 10⁹ FLOPS grob Intervallarithmetik multipliziert den Aufwand mit einem bescheidenen Faktor.Seit: 2002 Tuckers strenger ODE-Löser und Smales 14. Problem: der Beweis, dass der Lorenz-Attraktor existiert. Quelle

Aufzählung von Turingmaschinen

Jedes kleine Programm einer minimalen Maschine wird ausgeführt, um zu sehen, welche halten und welche ewig laufen, und das am längsten laufende haltende Programm jeder Größe zu finden.

Frage, die sie beantwortet: Wie lange kann ein winziges Programm laufen, bevor es anhält?

Lässt aus: Unentscheidbarkeit bedeutet, dass manche Maschinen nie klassifiziert werden können, egal wie lange sie laufen.

Läuft auf: etwa 10¹⁵ FLOPS grob Milliarden Maschinen, mit Beweisen für die nicht haltenden.Seit: 1965 Lin und Rados Computerstudien zu Problemen von Turingmaschinen. Quelle

Statistisches Model Checking

Ein System mit Zufallsverhalten, viele Male simuliert, um mit statistischer Sicherheit abzuschätzen, wie wahrscheinlich es eine Eigenschaft verletzt.

Frage, die sie beantwortet: Wie wahrscheinlich ist es, dass ein zufälliges System eine Sicherheitsregel verletzt?

Lässt aus: Statistische Läufe liefern eine Wahrscheinlichkeit mit Konfidenzniveau, keinen Beweis, und seltene Fehler brauchen Importance Sampling.

Läuft auf: etwa 10⁹ FLOPS grob Tausende bis Millionen gezogene Ausführungen.Seit: 2002 Younes und Simmons' probabilistische Verifikation diskreter Ereignissysteme mittels Akzeptanzstichproben. Quelle

Fuzz-Testing

Ein Programm bekommt riesige Mengen zufälliger oder mutierter Eingaben, um jene zu finden, die es zum Absturz bringen; es simuliert damit gewissermaßen eine feindliche oder achtlose Welt.

Frage, die sie beantwortet: Welche Eingabe bringt diese Software zum Absturz?

Lässt aus: Es findet nur Fehler, die zufällige Eingaben erreichen, und ein Programm kann jahrelang bestehen, während sich ein Bug hinter einem seltenen Fall versteckt.

Läuft auf: etwa 10¹⁴ FLOPS grob Maschinenjahre an CPU-Zeit für eine große Codebasis.Seit: 1990 Miller, Fredriksen und So, empirische Studie zur Zuverlässigkeit von UNIX-Werkzeugen. Quelle

Symbolische Ausführung

Ein Programm wird mit unbekannten Eingaben als Symbolen ausgeführt, wobei die Bedingungen jedes Pfads gesammelt werden; dann findet ein Solver Werte, die jeden Zweig nehmen.

Frage, die sie beantwortet: Welche Eingaben lassen jeden Pfad dieses Programms laufen, und erreicht einer einen Fehler?

Lässt aus: Die Zahl der Pfade wächst exponentiell mit der Programmgröße, deshalb werden große nur teilweise abgedeckt.

Läuft auf: etwa 10¹² FLOPS grob Stunden Solver-Zeit pro Programm, steil wachsend mit der Zahl der Pfade.Seit: 1976 Kings symbolische Ausführung und Programmtest. Quelle

Abstrakte Interpretation

Ein Programm wird auf Mengen möglicher Werte ausgeführt, etwa auf Bereichen statt auf Einzelwerten, um Eigenschaften zu beweisen, die für jede Eingabe gelten.

Frage, die sie beantwortet: Kann dieses Programm bei irgendeiner Eingabe je durch null teilen oder überlaufen?

Lässt aus: Die sichere Näherung löst Fehlalarme aus, sodass Menschen jede Warnung weiterhin prüfen müssen.

Läuft auf: etwa 10¹¹ FLOPS grob Stunden auf einer Workstation für eine große Avionik-Codebasis.Seit: 1977 Cousots abstrakte Interpretation, ein einheitliches Verbandsmodell für die statische Analyse von Programmen. Quelle

Bounded Model Checking

Das Verhalten eines Entwurfs bis zu einer festen Zahl von Schritten wird als logische Formel geschrieben und einem Erfüllbarkeitslöser übergeben, um irgendeinen kurzen Weg zu einem Fehler zu finden.

Frage, die sie beantwortet: Kann dieser Schaltkreis oder dieses Programm innerhalb einer bestimmten Zahl von Schritten einen Fehlerzustand erreichen?

Lässt aus: Es beweist nichts jenseits der Schrittschranke, solange kein gesondertes Argument zeigt, dass sie ausreicht.

Läuft auf: etwa 10¹³ FLOPS grob Stunden auf einem Server pro Immobilie.Seit: 1999 Bieres, Cimattis, Clarkes und Zhus symbolisches Model Checking ohne BDDs. Quelle

Eigenschaftsbasiertes Zufallstesten

Eine Regel, die immer gelten sollte, wird festgelegt; der Computer erzeugt viele Zufallsfälle und schrumpft jeden Fehlschlag auf ein kleines Gegenbeispiel.

Frage, die sie beantwortet: Hält sich dieser Code auf einer breiten Palette von Eingaben an seine eigene Spezifikation?

Lässt aus: Zufällige Fälle erreichen eine seltene Bedingung womöglich nie, und die aufgeschriebene Eigenschaft ist vielleicht nicht die, auf die es ankommt.

Läuft auf: etwa 10⁹ FLOPS grob Minuten auf einem Laptop für Tausende Fälle.Seit: 2000 Claessens und Hughes' QuickCheck, ein leichtgewichtiges Werkzeug für Zufallstests von Haskell-Programmen. Quelle

Verifikation neuronaler Netze

Constraint-Löser beweisen, dass für jede Eingabe in einem Bereich die Ausgabe eines neuronalen Netzes innerhalb von Schranken bleibt, statt Stichproben zu testen.

Frage, die sie beantwortet: Kann eine kleine Änderung an einer Eingabe das Netz jemals zu einer falschen Antwort bringen?

Lässt aus: Beweise skalieren nur auf kleine Netze, und die Menge der prüfbaren Störungen ist schmal.

Läuft auf: etwa 10¹³ FLOPS grob Stunden bis Tage auf einem Server für ein kleines Netz.Seit: 2017 Katz und Kollegen, Reluplex, ein SMT-Solver zur Verifikation tiefer neuronaler Netze. Quelle

Simulation von Rechnerarchitekturen

Pipeline, Caches und Sprungvorhersage eines geplanten Prozessors, Befehl für Befehl modelliert, um die Geschwindigkeit eines Chips abzuschätzen, bevor er gebaut wird.

Frage, die sie beantwortet: Wie schnell würde dieser Prozessorentwurf echte Programme ausführen, bevor auch nur ein Stück Silizium geschnitten ist?

Lässt aus: Vereinfacht so viel vom echten Chip, dass das endgültige Silizium immer ein wenig vom Modell abweicht.

Läuft auf: etwa 10¹¹ FLOPS grob ein Universitätscluster, der Benchmark-Programme durch das Modell laufen lässtSeit: 1990 spätestens 1990, taktgenaue Prozessorsimulatoren für die Architekturforschung

Simulation verteilter Systeme und Konsens

Viele Computer, die einander Nachrichten mit Verzögerungen, Verlusten und Ausfällen schicken, um zu testen, ob ein verteilter Algorithmus sich weiterhin auf die richtige Antwort einigt.

Frage, die sie beantwortet: Erreicht dieser Algorithmus weiterhin die richtige Einigung, wenn Nachrichten verloren gehen, sich verzögern oder Knoten abstürzen?

Lässt aus: Eingespeiste Ausfälle sind die, die der Entwickler vorhergesehen hat, nicht die, die im Betrieb unerwartet auftreten.

Läuft auf: etwa 10¹⁰ FLOPS grob ein Cluster, der Hunderte virtueller Knoten simuliertSeit: 1978 Lamports frühe Arbeit zu Ordnung und Ausfall in verteilten Systemen

Simulation von Speichersystemen

Festplatten, Laufwerke und Dateisysteme, modelliert danach, wie sie Daten ablegen, ausfallen und sich erholen, um ein Speicherdesign zu testen, bevor echte Laufwerke gekauft und gefüllt werden.

Frage, die sie beantwortet: Wie leistungsfähig und ausfallsicher ist dieses Speicherdesign, in einem Maßstab, der zu teuer ist, um ihn vorher real zu testen?

Lässt aus: Echte Laufwerke fallen auf unordentlichere, stärker korrelierte Weise aus als die zufällige Ausfallrate des Modells.

Läuft auf: etwa 10¹⁰ FLOPS grob eine Workstation bis zu einem kleinen Cluster, der ein Speicher-Array modelliertSeit: 1988 spätestens 1988, Simulationsmodelle zur Zuverlässigkeit von Festplatten-Arrays

Simulation von Betriebssystem-Schedulern

Ein Strom von Rechenaufgaben, die modelliert eintreffen und um einen Prozessor konkurrieren, durchgespielt mit verschiedenen Scheduling-Regeln, um zu sehen, welche am fairsten oder schnellsten ist.

Frage, die sie beantwortet: Welche Reihenfolge der Aufgabenschlange erledigt die meiste Arbeit oder ist für jede Aufgabe am fairsten?

Lässt aus: Synthetische Arbeitslasten entsprechen selten der unregelmäßigen Mischung von Aufgaben, auf die eine echte Maschine trifft.

Läuft auf: etwa 10⁹ FLOPS grob Läuft auf einem Laptop oder einer Workstation in Sekunden bis MinutenSeit: 1968 spätestens 1968, Simulationsstudien zu Scheduling-Strategien von Prozessoren

Suche zur Optimierung von Compilern und Programmen

Riesige Zahlen kleiner Variationen eines Codestücks, ausprobiert und gemessen, auf der Suche nach der schnellsten oder kürzesten Version, die noch dieselbe Aufgabe erfüllt.

Frage, die sie beantwortet: Welche von allen gleichwertigen Schreibweisen dieses kleinen Codestücks ist tatsächlich die schnellste?

Lässt aus: Die gefundenen Programme sind manchmal so ungewöhnlich, dass es keine Erklärung dafür gibt, warum sie funktionieren.

Läuft auf: etwa 10¹⁰ FLOPS grob ein Cluster, der einen großen Raum von Code-Varianten durchsuchtSeit: 2006 spätestens 2006, Superoptimierungssuche über kurze Befehlsfolgen

Empirische Leistungstests von Algorithmen

Ein Algorithmus, tausendfach über zufällig erzeugte oder reale Eingaben wachsender Größe ausgeführt, um zu messen, wie seine Laufzeit tatsächlich wächst, statt sie auf dem Papier zu beweisen.

Frage, die sie beantwortet: Wie wächst die Laufzeit dieses Algorithmus in der Praxis tatsächlich, bei den Eingaben, die er wirklich sehen wird?

Lässt aus: Ein schlimmster Fall, der in den Testeingaben fehlt, bleibt unentdeckt, bis er eintritt.

Läuft auf: etwa 10⁹ FLOPS grob Läuft auf einer Workstation über viele erzeugte TesteingabenSeit: 1970 spätestens 1970, systematische empirische Tests der Laufzeiten von Algorithmen

Programmausführung durch Sprachmodelle

Ein Sprachmodell schreibt Zwischenzustände Schritt für Schritt aus, während es nachverfolgt, was ein Programm berechnen würde.

Frage, die sie beantwortet: Kann ein Sprachmodell das Ausführen von Code nachahmen?

Lässt aus: Die Ausgabe ist nicht garantiert korrekt, und lange Programme scheitern.

Läuft auf: etwa 10¹⁴ FLOPS grob Inferenz pro AnfrageSeit: 2021 Show your work: scratchpads for intermediate computation with language models (2021) Quelle

Simulation von Blockchain-Konsens

Ein Netzwerk von Knoten, die unter Verzögerungen Blöcke erzeugen und teilen, um zu testen, wie Blockgröße, Timing und Angreifer Sicherheit und Durchsatz beeinflussen.

Frage, die sie beantwortet: Wie sicher und schnell ist eine Blockchain bei Netzwerkverzögerung und Angriff?

Lässt aus: Das Verhalten echter Knoten und echte Netzwerktopologien sind nur teilweise gemessen.

Läuft auf: etwa 10⁸ FLOPS grob ereignisgesteuerte Läufe mit Tausenden Knoten.Seit: 2016 Gervais und Kollegen, Sicherheits- und Leistungsanalyse von Proof-of-Work-Blockchains mit einem Simulator. Quelle

Parallele diskrete Ereignissimulation

Eine Simulation von Ereignissen in der Zeit wird auf viele Prozessoren verteilt, die jeweils ihre eigene Uhr vorantreiben und zurückrollen, wenn eine verspätet eintrifft.

Frage, die sie beantwortet: Wie lässt sich eine riesige ereignisgesteuerte Simulation, etwa eines Netzwerks oder Schlachtfelds, auf vielen Maschinen schnell ausführen?

Lässt aus: Rollbacks können sich kaskadenartig fortsetzen, und die Beschleunigung hängt stark davon ab, wie eng die Ereignisse gekoppelt sind.

Läuft auf: etwa 10¹⁴ FLOPS grob Stunden auf einem Supercomputer für Milliarden von Ereignissen.Seit: 1985 Jeffersons virtuelle Zeit, der Time-Warp-Mechanismus für optimistische Synchronisation. Quelle

Simulation der Architektur von Grafikprozessoren

Kerne, Warps und Speicher eines Grafikprozessors werden Takt für Takt modelliert und führen echte Programme aus, um einen Entwurf zu bewerten, bevor er gebaut wird.

Frage, die sie beantwortet: Wie würde sich eine Designänderung auf die Geschwindigkeit paralleler Programme auf einem Grafikchip auswirken?

Lässt aus: Details echter Chips sind geheim oder unbekannt, sodass das Modell die Zahlen bestehender Entwürfe nur grob trifft.

Läuft auf: etwa 10¹² FLOPS grob Stunden bis Tage Host-Zeit pro Sekunde simulierter Ausführung.Seit: 2009 Bakhoda und Kollegen, Analyse von CUDA-Arbeitslasten mit einem detaillierten GPU-Simulator. Quelle

FPGA-beschleunigte Systemsimulation

Ein Chipdesign wird auf viele rekonfigurierbare Schaltkreise geladen, die es taktgenau mit Megahertz-Geschwindigkeit ausführen und dabei ganze Server und deren Netzwerke simulieren.

Frage, die sie beantwortet: Wie werden sich dieser Prozessor und sein Cluster verhalten, wenn sie echte Software ausführen, bevor sie gebaut sind?

Lässt aus: Es ist weit langsamer als der echte Chip, und ein Design, das nicht auf die Schaltkreise passt, lässt sich nicht ausführen.

Läuft auf: etwa 10¹⁵ FLOPS grob Tage auf einer Cloud aus Hunderten rekonfigurierbarer Schaltkreise.Seit: 2018 Karandikar und Kollegen, FireSim, FPGA-beschleunigte taktgenaue Scale-out-Systemsimulation in der öffentlichen Cloud. Quelle

Vollsystemsimulation

Ein ganzer Computer mit Prozessoren, Speicher, Festplatten und Netzwerkkarten wird gut genug simuliert, um ein unverändertes Betriebssystem zu booten und dessen Programme auszuführen.

Frage, die sie beantwortet: Wie verhält sich echte Software auf einer Maschine, die es noch nicht gibt oder die sich beliebig anhalten und wiederholen lässt?

Lässt aus: Das Zeitverhalten wird der Geschwindigkeit zuliebe genähert, deshalb liefert es keine exakte Leistung, nur das funktionale Verhalten.

Läuft auf: etwa 10¹¹ FLOPS grob Nahezu in Echtzeit auf einem Server pro simulierter Maschine.Seit: 2002 Magnusson und Kollegen, Simics, eine Plattform zur Simulation ganzer Systeme. Quelle

Leichtgewichtige Netzwerkemulation

Dutzende oder Hunderte virtuelle Hosts und Switches führen auf einem Laptop echte Netzwerksoftware aus, verbunden durch emulierte Kabel mit festgelegter Geschwindigkeit und Verzögerung.

Frage, die sie beantwortet: Funktioniert dieses Netzsteuerprogramm auf einer ganzen Topologie, bevor es eingesetzt wird?

Lässt aus: Der eigene Prozessor des Wirts wird von allen virtuellen Knoten geteilt, deshalb werden schnelle Verbindungen ausgebremst.

Läuft auf: etwa 10¹⁰ FLOPS grob Echtzeit auf einer einzigen Workstation.Seit: 2010 Lantz, Heller und McKeowns A network in a laptop, schnelles Prototyping für softwaredefinierte Netzwerke. Quelle

Simulated Annealing

Ein Computer kühlt ein Modell aus Atomen oder einen Entwurf langsam ab und akzeptiert dabei manchmal schlechtere Anordnungen, um eine gute Lösung für ein schwieriges Optimierungsproblem zu finden.

Frage, die sie beantwortet: Was ist eine nahezu beste Anordnung oder ein nahezu bester Zeitplan unter astronomisch vielen Möglichkeiten?

Lässt aus: Es garantiert nicht die beste Antwort, und die Ergebnisse hängen vom Abkühlplan ab.

Läuft auf: etwa 10¹² FLOPS grob Stunden auf einer Workstation für eine Chip-Platzierung.Seit: 1983 Kirkpatrick, Gelatt und Vecchi, Optimierung durch Simulated Annealing. Quelle

Approximative Bayessche Berechnung

Ein Simulator wird mit vielen Probewerten für Parameter ausgeführt, und jene, die Daten nahe an den beobachteten erzeugen, werden behalten; das ergibt ein Bild davon, welche Werte plausibel sind.

Frage, die sie beantwortet: Welche Einstellungen eines komplizierten Modells könnten die Daten erzeugt haben, die wir beobachten?

Lässt aus: Das Ergebnis hängt davon ab, welche Zusammenfassungen der Daten verwendet werden und wie nah eine Übereinstimmung sein muss, um zu zählen.

Läuft auf: etwa 10¹³ FLOPS grob Millionen Simulatorläufe auf einem Cluster.Seit: 1997 Die Ableitung von Koaleszenzzeiten aus DNA-Sequenzdaten mittels Simulation von Tavaré und Kollegen. Quelle