Was ist das richtige theoretische Modell, um Algorithmen für aktuelle und kommende Hochleistungscomputer zu entwerfen?

Diese Frage ähnelt einer allgemeineren Frage nach dem richtigen theoretischen Modell eines Computers zum Entwerfen von Algorithmen und Datenstrukturen.
Ich frage hier speziell nach aktuellen Hochleistungscomputern (wie den als Top 500 aufgelisteten ) oder sogar nach kommende Supercomputer.

Angesichts der Tatsache, dass diese Computer in der Regel mit riesigen Datenmengen arbeiten (es scheint, dass einige Leute solche Maschinen hauptsächlich verwenden, weil sie über einen enormen kombinierten Hauptspeicher verfügen), gibt es Aspekte des I / O-Modells (das 1988 von Aggarwal und Vitter eingeführt wurde ) und seiner parallelen Version , sollte die PEM ( Arge, Goodrich, Nelson und Sitchinava im Jahr 2008 ) anwesend sein. Auf der anderen Seite sollte Kommunikation eine Rolle spielen, insbesondere die Bestrafung von extrem kleinen Paketen an alle anderen Rechenknoten.

Wie Sie sich vielleicht vorstellen können, habe ich keine Angst, dass mir beim Erstellen eines neuen Modells die Ideen ausgehen, aber ich bin ein wenig besorgt, dass ich dabei frühere Versuche übersehen könnte, insbesondere weil ich den Eindruck habe, dass die Jahre 1980 bis 1995 oder so gab es viele solcher Modellierungsversuche (wie BSP- oder Brückenmodelle), die anscheinend nicht weit verbreitet waren.

Welche Modelle sollte ich mir genauer ansehen?

Bruce Hendrickson hielt auf der PODC 2009 einen phänomenalen Vortrag über diese Themen. (Seine Folien scheinen nicht online zu sein, aber vielleicht möchten Sie ihn fragen, ob Sie sie sehen könnten.) Ich glaube, es gibt noch kein "richtiges" Modell - Bonus für Sie! - aber ich würde vorschlagen, dass Sie sich seine Papiere ansehen, insbesondere die auf der Seite " Graphs and Architectures" , wo er versucht, herauszufinden, wie man mit riesigen Graphen mit geringer Struktur (dh "modernen" Datensätzen) auf Maschinen mit mehreren Threads umgeht.

Unklar ist, wie sich Caches entwickeln werden. Die Arbeit von Nikos Hardavellas aus dem Jahr 2009 betrachtet diese Dinge aus einer Systemperspektive , einschließlich Überlegungen zu physikalischen Grenzen für skalierbare Speichersysteme. Die Arbeit stellt kein Modell als solches vor, kann aber Hinweise geben.

Ein Modell, das hierarchische Modelle gut erfasst (denken Sie an lokale Kerne, gemeinsam genutzten On-Chip-Speicher und globalen Speicher), ist ein STOC 87-Artikel von Aggarwal et al . Ich glaube nicht, dass es jemals etwas angezogen hat, aber es ist eine interessante Lektüre. Die Hauptidee ist, dass der Zugriff auf den Speicherort x Zeit benötigt .$\lceil \log x\rceil$