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

20

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?

Riko Jacob
quelle
Dies antwortet überhaupt nicht, aber jedes Modell für aktuelle und kommende Supercomputer, sondern bettet Fehler / Fehlertoleranz ein.
Sylvain Peyronnet
Schauen Sie sich Flynns Taxonomie an. Laut Wikipedia basieren "alle Top 10 und die meisten der TOP500-Supercomputer auf einer MIMD-Architektur". en.wikipedia.org/wiki/MIMD
Mohammad Al-Turkistany
können Sie den Satz klarstellen: "Andererseits sollte Kommunikation eine Rolle spielen , insbesondere die Bestrafung von extrem kleinen Paketen für alle anderen Rechenknoten." ist das ein Tippfehler? sollte es drängen ? Könnte eine Antwort auf diese Frage parallele Entwurfsmuster sein, z. B. Mapreduce, Hoares CSP? siehe auch cache
ahnungslose

Antworten:

9

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.

Aaron Sterling
quelle
Danke für den Hinweis. Ich habe den Eindruck, dass er sich nicht so sehr mit der Definition eines Modells befasst, das eine theoretische Analyse ermöglicht. Übersehen ich etwas? Vielleicht sollte ich ihn direkt kontaktieren.
Riko Jacob
@Riko Jacob: Ich stimme zu, dass Hendrickson eher ein Praktiker als ein Modellbauer ist. Ich dachte, er hätte eine großartige Intuition für das, was gebraucht wurde. Wenn Sie Artikel über Modelle wünschen, interessieren Sie sich vielleicht mehr für den Workshop über Theorie und Vielkerne . Ich finde jedoch keines dieser Modelle zufriedenstellend, und es würde mich sehr interessieren, was Sie sich einfallen lassen. :-)
Aaron Sterling
8

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.

Rasmus Pagh
quelle
4

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 .logx

Suresh Venkat
quelle
Nachdem ich es durchgesehen habe, sehe ich es wie einen Vorgänger des Cache-vergessenden Modells aus. Ich habe auch keine Ideen zur Parallelverarbeitung gesehen. Habe ich hier etwas verpasst?
Riko Jacob
Ich denke, es geht mehr um hierarchische Speichermodelle, das stimmt.
Suresh Venkat