Azul Systems verfügt über eine Appliance, die Tausende von Cachekohärenten CPUs unterstützt. Ich würde gerne wissen, welche Änderungen an einem Betriebssystem vorgenommen werden müssen, um Tausende gleichzeitig ablaufender Threads zu planen.Kernel-Scheduling für 1024 CPUs
Sie fragen nach möglichen Änderungen am Betriebssystem, also nehme ich an, dass es ein bedeutendes Technikerteam gibt.
Es gibt auch ein paar Stücke von Informationen clarififying, die die Problemparameter helfen würde definieren:
Wie viel IPC (Inter Kommunikationsprozess) benötigen Sie?
Müssen sie wirklich Threads sein, oder können sie Prozesse sein?
Wenn sie Prozesse sind, ist es in Ordnung, wenn sie miteinander über Sockets reden müssen, und nicht mit Shared Memory?
Was ist die Speicherarchitektur? Sind Sie gerade SMP mit 1024 Kernen, oder gibt es hier eine andere NUMA (Non-Uniform Memory Architecture) oder MMP? Wie sind Ihre Seitentabellen?
Wenn ich nur die allerkleinsten Informationen über Azul-Systeme kenne, würde ich annehmen, dass Sie sehr wenig IPC haben und dass ein einfaches Modell "einen Kern pro Kern ausführen" tatsächlich gut funktioniert. Wenn Prozesse miteinander kommunizieren müssen, können sie Sockets erstellen und Daten auf diese Weise übertragen. Unterstützt Ihre Hardware dieses Modell? (Sie würden am Ende wahrscheinlich auch eine IP-Adresse pro Kern benötigen, und bei 1024 IP-Adressen könnte dies mühsam sein, obwohl sie alle NAT-behandelt werden könnten, und vielleicht ist das nicht so eine große Sache). Natürlich würde dieses Modell zu einigen Ineffizienzen führen, wie zusätzlichen Seitentabellen und einem angemessenen RAM-Overhead, und könnte sogar von Ihrem Hardwaresystem nicht unterstützt werden.
Selbst wenn "1 Kern pro Kern" nicht funktioniert, könnten Sie wahrscheinlich 1024/8 Kernel ausführen, und es ist gut, wenn jeder Kernel 8 physische CPUs steuert.
Das heißt, wenn Sie 1 Thread pro Kern in einem traditionellen SMP-Rechner mit 1024 Kernen (und nur ein paar physischen CPUs) laufen lassen wollten, würde ich erwarten, dass der altmodische O (1) Scheduler das ist, was Sie tun würden wollen. Es ist wahrscheinlich, dass Ihre CPU [0] im Kernel fast zu 100% endet und die Interrupt-Behandlung durchführt, aber das ist gut für diesen Anwendungsfall, es sei denn, Sie benötigen mehr als einen Kern, um Ihre Arbeitslast zu bewältigen.
Die Planung von Tausenden von Threads ist keine große Sache, aber sie auf hunderte von CPUs zu planen ist. Was Sie in erster Linie brauchen, sind sehr feingliedrige Locking- oder besser Lock-Free-Datenstrukturen und Algorithmen. Sie können es sich nicht leisten, 200 CPUs warten zu lassen, während eine CPU einen kritischen Abschnitt ausführt.
Meine ungebildete Vermutung wäre, dass es eine Run-Queue pro Prozessor und einen Work-Stealing-Algorithmus gibt, wenn ein Prozessor im Leerlauf ist. Ich konnte sehen, dass dies in einem M: N-Modell funktioniert, bei dem es einen einzigen Prozess pro CPU und leichte Prozesse als Arbeitselemente gibt. Dies würde dann einem Work-Stealing-Threadpool ähneln, etwa dem in der Fork-Join-Bibliothek von Java-7.
Wenn Sie es wirklich wissen wollen, gehen Sie zu Solaris Internals oder greifen Sie auf den Solaris-Kernel-Code zu. Ich lese immer noch Design & Impl von FreeBSD, wobei Solaris Internals der nächste auf meiner Liste ist, also kann ich nur wilde Vermutungen atm machen.
Ich bin ziemlich sicher, dass die SGI Altix, die wir bei der Arbeit haben, (die ccNUMA verwendet) spezielle Hardware für Cache-Kohärenz verwendet.
Es ist ein enormer Aufwand verbunden, 4mb Cache pro Kern kohärent zu halten. Es ist unwahrscheinlich, dass dies nur in Software geschieht.
in einem Array von 256 CPU benötigen Sie 768 MB RAM, nur um die Cache-Invalidierungs-Bits zu halten. 12 MB Cache/128 Bytes pro Cachezeile * 256² Kerne.
Die Änderung des Betriebssystems ist eine Sache, aber die Verwendung von unverändertem Anwendungscode ist eine Verschwendung von Hardware. Beim Überschreiten eines Limits (abhängig von der Hardware) ist der Aufwand, Kohärenz und Synchronisation zu halten, um generischen Code auszuführen, einfach zu viel. Sie können es tun, aber es wird sehr teuer sein. Auf der Betriebssystemseite benötigen Sie ein komplexes Affinitätsmodell, d. H. Keine CPUs zu überspringen, nur weil Sie beschäftigt sind. Planen von Threads basierend auf der Hardwaretopologie - kooperierende Threads auf CPUs, die "nahe" sind, um Penalties zu minimieren. Einfache Arbeit Diebstahl ist keine gute Lösung, Sie müssen Topologie berücksichtigen. Eine Lösung ist das hierarchische Stehlen von Arbeit - stehlen Sie Arbeit nach Entfernung, teilen Sie die Topologie nach Sektoren und versuchen Sie, von der nächsten zuerst zu stehlen. Etwas das Schlossproblem berühren; Sie werden immer noch Spin-Locks und dergleichen verwenden, aber mit völlig verschiedenen Implementierungen. Dies ist wahrscheinlich das meist patentierte Feld in CS in diesen Tagen. Aber wieder müssen Sie speziell für solche massiven Umfang programmieren. Oder du benutzt es einfach zu wenig. Keine automatischen "Parallelizer" werden es für Sie tun.
Linux-Skalierung zu machen war ein langes und laufendes Projekt. Der erste Multiprozessor-fähige Linux-Kernel hatte eine einzige Sperre, die den gesamten Kernel (Big Kernel Lock, BKL) schützte, was zwar einfach, aber nur begrenzt skalierbar war.
Anschließend wurde die Verriegelung feinkörniger gemacht, d. H. Es gibt viele Sperren (Tausende?), Die jeweils nur einen kleinen Teil der Daten abdecken. Es gibt jedoch Grenzen in Bezug darauf, wie weit dies erreicht werden kann, da eine feinkörnige Verriegelung dazu neigt, kompliziert zu sein, und der Sperr-Overhead beginnt, den Leistungsvorteil aufzufressen, insbesondere wenn man bedenkt, dass die meisten Multi-CPU-Linux-Systeme relativ wenig CPUs haben.
Eine andere Sache ist, dass der Kernel so weit wie möglich per-CPU-Datenstrukturen verwendet. Dies ist sehr wichtig, da es die Cache-Kohärenz-Performance-Probleme mit gemeinsam genutzten Daten vermeidet, und natürlich gibt es keinen Locking-Overhead. Z.B. Jede CPU hat ihren eigenen Prozessplaner, der nur gelegentlich globale Synchronisation erfordert.
Auch einige Algorithmen werden im Hinblick auf Skalierbarkeit ausgewählt. Z.B. einige gelesene Daten werden durch Read-Copy-Update (RCU) anstatt traditioneller Mutexe geschützt; Dadurch können Leser während einer gleichzeitigen Aktualisierung fortfahren.
Wie bei Speicher versucht Linux, Speicher von demselben NUMA-Knoten zu reservieren, auf dem der Prozess ausgeführt wird. Dies bietet eine bessere Speicherbandbreite und Latenz für die Anwendungen.
Es gibt Hunderttausende von Schlössern. Die Datenstrukturen inode und dnode enthalten jeweils eine separate Sperre. Das ist ok. Unlocked oder Locked-and-Not-Warte-On-Sperren verbrauchen nur ein paar Bytes RAM und keine anderen Ressourcen. – Joshua
Der einfachste Weg, dies zu tun ist, jeden Prozess/Thread an ein paar CPUs zu binden, und dann müssten nur diese CPUs um eine Sperre für diesen Thread konkurrieren. Offensichtlich müsste es eine Möglichkeit geben, Threads zu verschieben, um die Last auszugleichen, aber bei einer NUMA-Architektur müssen Sie dies so weit wie möglich minimieren.
Sogar auf Dual-Core-Intel-Systemen bin ich mir ziemlich sicher, dass Linux bereits "Tausende" von Threads mit nativen Posix-Threads verarbeiten kann.
(Glibc und der Kernel müssen beide so konfiguriert werden, um dies zu unterstützen, aber ich glaube, die meisten Systeme haben dies heutzutage standardmäßig).
Ja, Altix Maschinen haben sogenannte "verteilte Verzeichnis" CC. – janneb