MUSS irgendetwas auf einer Multi-Core-CPU gemacht werden?

45

Bei der Überlegung, wie multithread-freundlich unser Programm sein muss, fragte sich mein Team, ob auf einer Single-Core-CPU überhaupt etwas nicht möglich ist . Ich ging davon aus, dass die Grafikverarbeitung eine massive Parallelverarbeitung erfordert, sie argumentieren jedoch, dass Dinge wie DOOM auf Single-Core-CPUs ohne GPUs durchgeführt wurden.

Gibt es etwas, muss auf einem Multi-Core - Prozessor durchgeführt werden?

Angenommen, es gibt unendlich viel Zeit für Entwicklung und Ausführung.

Ben Leggiero
quelle
8
Während die folgenden Antworten größtenteils "Nein" zu sein scheinen, gibt es historisch gesehen Systeme, die buchstäblich ohne einen Co-Prozessor, der einige Aufgaben erledigt, nicht hätten funktionieren können. Ein gutes Beispiel, das ich kenne, ist der Nintendo DS, der eine 67-MHz-ARM9-CPU und eine 33-MHz-ARM7-CPU enthält (die auch für die Back-Kompatibilität beim Spielen von GBA-Spielen verwendet werden). Bei DS-Spielen kann der ARM7 Audio- und Wi-Fi-Kommunikation wiedergeben, da der ARM9 keine wichtigen Informationen auf dem Bildschirm verarbeiten und zeichnen kann, während er den Soundchip direkt mit Audio versorgt. Wie @jmite "unter welchen Bedingungen" angibt, kann mangelnde Geschwindigkeit mehrere CPUs erfordern.
Slipp D. Thompson
10
In meinem Job verwenden wir Multicore-Xeons und die Echtzeit-Linux-Erweiterungen von Xenomai, um die Audioverarbeitung mit geringer Latenz durchzuführen. Wir haben eine dreistufige Audio-Verarbeitungs-Pipeline, und jede Stufe erhält ihren eigenen Kern, der ~ 70% der Zyklen ausmacht. Aufgaben, die nicht in Echtzeit ausgeführt werden, verwenden den vierten Kern und die verbleibenden Zyklen der ersten drei. Dies wäre auf einer Single-Core-CPU nur möglich, wenn dieser Single-Core 3 Mal schneller wäre als ein Core auf einer aktuellen 4-Core-CPU. Angesichts der Tatsache, dass die aktuelle CPU mit 2 GHz läuft, ist dies möglicherweise schwierig zu erreichen.
Jeremy Friesner
19
Software auf einer Single-Core-CPU kann eine Multi-Core-CPU emulieren. Der Unterschied liegt fast ausschließlich in der Geschwindigkeit.
user253751
24
Eine Sache, die auf einem Multi-Core-System getan werden muss, ist das Testen von Multithread-Software. Denn manche Defekte treten (fast) nie auf einem Single-Core-System auf. Ich bin nicht sicher, ob dies als Antwort in
Frage kommt
13
@nikie Ein Single-Core-System kann auch Speicherreihenfolge und veraltete Caches emulieren - aber ich stelle mir vor, das wäre extrem ineffizient (wie 10 × Verlangsamung)
Nayuki

Antworten:

47

Wenn Ihnen die Laufzeit egal ist, können Sie alles, was Sie auf einem Multi-Core-Computer tun können, auch auf einem Single-Core-Computer tun. Eine Multi-Core-Maschine ist nur eine Möglichkeit, einige Arten von Berechnungen zu beschleunigen.

Wenn Sie ein Problem in der Zeit auf einer Mehrkernmaschine mit Kernen lösen können, können Sie es in der Zeit (oder weniger nach dem Amdahlschen Gesetz ) auf einer lösen . Der Single-Core-Computer kann einen Multi-Core-Computer mithilfe von Time-Slicing / Time-Sharing emulieren .TnTn

DW
quelle
3
Ich bin mir nicht ganz sicher, ob das absolut richtig ist. Ich glaube nicht, dass es möglich ist, auf einem einzelnen Kern Fehler in Bezug auf die Speicherkonsistenz zu generieren (Ja, man könnte ein Multicache-System auf einem Unicore emulieren, aber eine solche Indirektion ist eine Art Betrug.). (Vielleicht ein Äquivalent zur Implementierung von Reg.-Swap durch Move-Ops in einem VLIW unter Ausnutzung des garantierten || Ismus?) Ich nehme an, dass es sogar auf einem Single-Thread-Core möglich wäre, Entropie aus der Multithread-Timing-Variabilität zu extrahieren, aber den Betrag von Die Entropie wäre pro Zeiteinheit kleiner (was genau wie die anderen Unterschiede nur eine Frage der Leistung ist).
Paul A. Clayton
6
@ PaulA.Clayton Memory Consistency Bugs sind normalerweise unerwünscht und gut geschriebene Software sollte sie nicht aufweisen. Wenn Sie jedoch wirklich wollten, könnten Sie sie auf einer einzelnen CPU emulieren. (Obwohl es langsam sein könnte)
user253751
4
Manchmal ist die Zeit auf einem einzelnen Kern mehr als mal länger als auf einem Core-Rechner, zum Beispiel für die Suche mit zufälligen Neustarts oder wenn die Teile auf den mehreren Kernen in den Cache passen, aber nicht auf dem einzelnen Kern. nnn
András Salamon
11
"Der Single-Core-Rechner kann einen Multi-Core-Rechner mithilfe von Time-Slicing / Time-Sharing emulieren." Und das schon seit den Anfängen des "modernen" Betriebssystems.
Leichtigkeit Rennen mit Monica
1
@ PaulA.Clayton Ich denke, Sie könnten Probleme mit der Speicherkonsistenz bekommen (wie ein nicht-atomares Inkrement), wenn Sie zwei verschiedene Prozesse hätten, die beide den gleichen gemeinsamen Speicher modifizierten. Sie brauchen nur präventives Multitasking. Dies ist natürlich im Allgemeinen der Grund, warum moderne Betriebssysteme nicht über Prozesse verfügen, die denselben beschreibbaren Speicher gemeinsam nutzen, es sei denn, sie fordern dies ausdrücklich an.
Patrick M
58

Die Frage ist: Unter welchen Bedingungen?

Es gibt sicherlich Probleme, bei denen, wenn wir die Frage "Können wir dieses Problem auf Hardware X in der vorgegebenen Zeit lösen" stellen, die Antwort "Nein" lautet.

Dies ist jedoch keine "zukunftssichere" Antwort: Dinge, die in der Vergangenheit in einem einzelnen Kern nicht schnell genug erledigt werden konnten, sind wahrscheinlich jetzt möglich, und wir können nicht vorhersagen, zu welcher Hardware die Zukunft fähig sein wird.

In Bezug auf die Rechenfähigkeit wissen wir, dass eine Single-Tape-Turing-Maschine alle Funktionen eines Single- oder Multi-Core-Computers verarbeiten kann. Abgesehen von der Laufzeit gibt es also keine Probleme, die ein Multi-Core-Computer lösen kann Single-Core kann nicht.

In Bezug auf die so etwas wie Grafiken, buchstäblich alles, was auf der GPU ist könnte auf der CPU durchgeführt werden ... wenn Sie bereit sind , lange genug zu warten.

jmite
quelle
3
@ JanDvorak Ich würde eigentlich sagen, dass dies von der GPU überhaupt nicht gemacht wird;)
TomTom
15
Wenn die Zeit keine Einschränkung darstellt, können Sie alle Berechnungen mit der Hand, dem Stift und dem Papier durchführen.
Kathreadler
2
@mathreadler Ja, weil das Gehirn Turing Complete ist. Etwas, das sich in eine lange Debatte über Physics Stackexchange verwandelte.
JBentley
4
Eigentlich @JanDvorak, VGA zu erzeugen ist ganz einfach und kann in Software auf einem niedrigen 16 MHz Mikrocontroller, wie dieses Projekt zeigt , erfolgen: pyroelectro.com/tutorials/arduino_basic_vga
Axello
3
@mathreadler Das ist eigentlich eine kompliziertere Frage als es zunächst erscheint. Eine kurze Antwort könnte "Ja" lauten, da eine spezialisierte Maschine einen Computer konstruieren kann, ohne dass dazu vollständige Werkzeuge erforderlich sind. Eine längere Antwort könnte "nein" sein, da die Fähigkeit, eine Turing-Maschine zu konstruieren, bedeuten kann, dass sich eine größere Turing-Maschine in einem "Initialisierungs" -Zustand befindet, in dem sie den Rest der Zustandsmaschine konstruiert. Die vollständige Antwort ist noch komplizierter, da wir noch nie ein Turing Complete-Gerät konstruiert haben. Wir haben abstrakte Ideen für Maschinen entwickelt, die ...
Cort Ammon
17

Wie andere Antworten gezeigt haben, kann eine einzelne CPU immer mehrere CPUs emulieren, indem sie die Zeit aufteilt und die Rolle jeder virtuellen CPU spielt. Diese Emulation berechnet mit Sicherheit die richtigen Antworten.

In der realen Welt kann die Ausführungszeit wichtig sein. Dies könnte den Unterschied zwischen einer mittelmäßigen Bildrate und einem herausragenden visuellen Erlebnis bedeuten. Oder die Differenz zwischen Gewinn und Verlust im Handel.

Eine pathologische Situation, in der ein Multiprozessor erheblich schneller als ein Uniprozessor ist, ist, dass die Verarbeitung eine Datenpipeline ist, die Kontextumschaltung teuer ist und der Maschinencode für jede Pipelinestufe gerade noch in den Cache einer CPU passt.

Lassen Sie mich mit einigen Zahlen illustrieren. Angenommen, Sie haben eine Daten-Pipeline (3D-Rendering usw.) mit 4 Verarbeitungsstufen, jede Stufe verfügt über 256 KB Programmcode und Sie haben bequemerweise 4 CPUs mit 256 KB L2-Cache. Wenn Sie versuchen, diese Verarbeitung auf einer einzelnen CPU auszuführen, ist das Wechseln zwischen den vier Tasks teuer und mit erheblichen Cache-Fehlern verbunden. Wenn Sie es jedoch auf einem 4-Core-System ausführen, kann die Berechnung möglicherweise sehr reibungslos sein, Cache-Fehler sind minimal und Kontextwechsel sind nicht vorhanden. (Nebenbei bemerkt bezieht sich dies auf den Begriff des Fixierens bestimmter Anwendungen auf bestimmte Kerne, z. B. nur Betriebssystemkernoperationen in einem Kern oder TCP / IP-Verarbeitung usw.)

Nayuki
quelle
7

Es ist viel schwieriger, wirklich schändliche Datenrennen mit einer einzigen CPU zu entwickeln. Ich meine, klar, Sie können zwischen Wörtern reißen, wenn Sie eine einzelne CPU unterbrechen, aber können Sie exotische Szenarien erstellen, in denen es keine einzelne Verschachtelung von Threads gibt, die das tun, was Sie wollen?

Okay, vielleicht zählt das Erstellen heimtückischer Bugs nicht als gültige Verwendung von Weiterentwicklungen mit mehreren Codes. Wie sich herausstellt, gibt es nicht viel, was Multicore leisten kann, wenn ein einzelner Kern nicht genügend Zeit hat. Der Grund ist einfach. Wenn Sie versuchen, diese bösen Datenrennen zu vermeiden, müssen Sie Synchronisierungspunkte in Ihrem Code haben. Wenn Sie Ihren Code als ein Berechnungsgitter modellieren, bei dem die Eingaben vollständig und synchronisiert sein müssen, bevor Sie die Ausgaben berechnen und produzieren können, ist es leicht zu erkennen, dass eine einzelne CPU einfach entlang des Gitters arbeiten und den nächsten verfügbaren Arbeitsblock berechnen kann .

Wenn Sie nachweisen können, dass Ihr Algorithmus von einer Turing-Maschine gelöst werden kann (das ist praktisch jeder Algorithmus, den wir interessieren), können Sie nachweisen, dass der Algorithmus nicht nur von einer einzelnen Kern-CPU ausgeführt werden kann, sondern von einer Zustandsmaschine mit einem sehr langen Stück Klebeband zur Erinnerung!

Der CHESS Race Detector nutzt dies tatsächlich, um Race Cases zu finden. Es führt alle Singlethread-Prozesse aus und untersucht systematisch alle möglichen Interleaves zwischen Threads. Dabei wird versucht, Fälle zu finden, in denen ein Test aufgrund eines Race-Falls fehlschlägt. CHESS hängt davon ab, dass Sie jede Multithread-Anwendung auf einem einzigen Kern ausführen können.

Die Fälle, in denen Sie Multicore benötigen, treten auf, wenn Sie anfangen, die Grenzen der Hardware zu erweitern. Die offensichtliche ist, wenn Sie Zeitbeschränkungen haben. Einige Probleme mit Echtzeitbeschränkungen lassen sich nicht mit einem einzelnen Kern lösen, da sie den Takt eines einzelnen Kerns nicht schnell genug antreiben können. Es gibt einen Grund, warum CPUs auf 4 GHz angestiegen sind und sich dann etwas beruhigt haben und mehr Kerne bei niedrigeren Geschwindigkeiten bevorzugen.

Eine exotischere Version dieser Zeitbeschränkung gibt es in Echtzeitsystemen. In einigen harten Echtzeitsystemen ist der Service von Interrupts so anspruchsvoll, dass Sie tatsächlich eine Multi-Core-CPU auswählen müssen, mit der Sie die Interrupts auf die Kerne aufteilen können, oder Sie stoßen auf zeitliche Einschränkungen.

Eine weitere Grenze ergibt sich bei Datenbussen. Betrachten Sie das Blue Gene / P als Beispiel. JUGENE, ein spezieller Blue Gene / P-Supercomputer, hat 144 Terabyte Speicher. Sie stellen einfach keine einzelnen CPU-Computer her, die auf den gesamten Speicher zugreifen können.

Cort Ammon
quelle
1
Betreff: Sie stellen einfach keine einzelnen CPU-Computer her, die auf [so viel] Speicher zugreifen können. "Nicht" ist nicht dasselbe wie "Kann nicht". Sie können einen Uniprozessor mit 144 Terabyte oder mehr Hauptspeicher entwerfen und erstellen. Der einzige Grund, warum dies nicht der Fall ist, ist die sinkende Rendite: Der inkrementelle, praktische Wert der Erweiterung eines Uni-Prozessor-Designs um mehr Speicher erreicht irgendwann einen Höhepunkt und sinkt dann mit zunehmender Speichergröße, während die inkrementellen Kosten konstant bleiben .
Solomon Slow
@jameslarge Das wäre der Grund, warum dieser Satz in den Teil meiner Antwort kam, in dem es um praktische Hardware im wirklichen Leben ging, und warum er nicht in den ersten 2/3 der Antwort auftauchte, in der die theoretischen Kapazitäten besprochen wurden.
Cort Ammon
"Don't" vs. "Can't" wird durch zwei Systeme in meinem Keller dargestellt. Wenn ich ihren Hardwarekonfigurationen physisch so viel Speicher hinzufügen könnte, könnten ihre CPUs auf jedes Byte "zugreifen". Aber ich kann nicht, also können sie nicht. Die Fähigkeiten der CPUs sind nicht praktikabel.
user2338816
Ich habe mir so etwas wie diese Antwort überlegt. Es scheint, dass Rennbedingungen in einer Single-Core-Umgebung unmöglich sind (oder 100% der Zeit passieren). Für eine praktische Anwendung theoretisiere ich, dass ein Softwareentwickler eine einzigartige Form des Kopierschutzes entwickeln könnte, indem er einen seltsamen Race-Condition-Test codiert, der immer die spezifische Zielhardware weitergibt, aber auf emulierter Hardware, die von einem einzelnen Kern ausgeführt wird, fehlschlägt . In diesem Fall würde die Emulation durch ein Mehrkernsystem wahrscheinlich manchmal, aber unzuverlässig vergehen.
Dan Henderson
6

Wenn Sie einen Prozess beobachten möchten, der auf einem einzelnen Verarbeitungselement ausgeführt wird, ohne dessen Echtzeitverhalten (oder so wenig wie möglich) zu stören, wie zum Beispiel für das Benchmarking oder die Aktivitätsprotokollierung, benötigen Sie wahrscheinlich eine separate Verarbeitungsressource.

Yves Daoust
quelle
Schönes, prägnantes Beispiel für etwas, das eine präzise Emulation erfordert, wenn nicht mehrere Prozessoren
Ben Leggiero
Hey, ist das dein Account? Möchtest du es vielleicht zusammenführen?
Evil
4

Die anderen Antworten halten an der eingeschränkten Auffassung von Parallelität als "verteilte Nebenläufigkeit" fest. Dies gibt einige Antworten: In einem sauberen Berechnungsmodell à la Turing bieten mehrere Kerne keinen Vorteil. Der einzige Vorteil ist die Effizienz.

Es ist die eine Sache , mehrere Verarbeitungseinheiten (Dekubitus) tun , dass ein einzelner kann man nicht, aber: ausführen Operationen parallel , also gleichzeitig .

Das ist sehr nützlich, wenn Sie mehrere Programme gleichzeitig ausführen. Zugegeben, es kommt nur selten vor, dass Sie unbedingt mehr als die gleichzeitige Ausführung benötigen, und die meisten Verwendungen sind auf eine höhere Effizienz zurückzuführen. Aber da ist dieser Unterschied.

Angenommen, Sie müssen Datensensordaten aus mehreren Quellen in Echtzeit verarbeiten. Was auch immer das genau für Ihre Anwendung bedeutet, eine PU kann nur so viele Eingabestreams gleichzeitig verarbeiten, ohne dass das Antwortzeitlimit überschritten wird. Sie benötigen also mehrere PUs, sobald Sie zu viele Sensoren für Ihre aktuelle PU-Generation haben.

Ein überzeugendes Beispiel im klassischen Bereich sind Portfolio-Algorithmen . Angenommen, Sie haben ein Problem, für das Sie mehrere (sagen wir ) Algorithmen mit orthogonalen Kosten haben. gute fälle von einem sind schlechte fälle für andere. Sie können jedoch nicht schnell feststellen, welches für eine bestimmte Eingabe am besten geeignet ist.k

Sie können alle Algorithmen parallel ausführen und den Vorgang abbrechen, sobald er abgeschlossen ist. Wenn Sie mindestens PUs haben, erhalten Sie die minimale Laufzeit aller Algorithmen im Portfolio. Mit nur einer PU würden Sie das fache erhalten, vorausgesetzt, ein fairer Scheduler plus den gesamten Overhead.k kkkk

Raphael
quelle
0

Von einem CS-POV unterscheidet sich "Multicore" theoretisch nicht wesentlich von "Distributed Computing". Das Grundkonzept sind "unabhängige Rechenelemente (die parallel rechnen". Eine leichte Umformulierung der Frage ("Multicore" ist nicht wirklich ein theoretisches Konzept in CS) führt zu einigen anderen Möglichkeiten. Wie in anderen Antworten ausgeführt, ist sequentielle Programmierung Entspricht der parallelen Programmierung von einem CS-POV. Dies geht zurück auf die Definition des theoretischen Systems für das Rechnen, nämlich einer Turing-Maschine. Die theoretische Analyse der CS-Leistung erfolgt letztendlich in Bezug auf TMs, bei denen die Unterscheidung zwischen parallel und sequentiell nicht wirklich gilt ( obwohl es eine grobe Analogie zu Multitape-TMs gibt ).

Wenn man diese Frage weniger abstrakt betrachtet, ist verteiltes Rechnen in der Tat für einige Probleme mit Fehlertoleranz überlegen oder möglicherweise sogar fast erforderlich . In diesem Bereich gibt es ein Konzept, das gilt, wenn / wo die unabhängigen Rechenelemente einen gewissen Grad an Unzuverlässigkeit aufweisen (dies ist nicht wirklich eine universell anwendbare Annahme für alle Kontexte). Hier gibt es mehrere Fälle, in denen die Fehlertoleranz durch unabhängige Rechenelemente verbessert wird oder sogar unabhängige Rechenelemente erfordert .

  • Bedenken Sie, dass jeder Prozessor eine unabhängige "[x]%" Wahrscheinlichkeit hat, während der Berechnung auszufallen. Es kann ein System entwickelt werden, bei dem durch Kommunikation die Gesamtfehlertoleranz des Systems einzelnen Komponenten überlegen ist. Dies wurde vor vielen Jahrzehnten zB in Space-Shuttle-Systemen angewendet. In jüngerer Zeit gibt es grundlegende Protokolle, die dafür entwickelt wurden, zB Paxos , um das sogenannte Konsensproblem zu lösen . Ein bodenständigeres Beispiel ist Google, das über zahlreiche proprietäre Algorithmen verfügt, um seine Supercomputer im Wesentlichen aus einzelnen unzuverlässigen Elementen zusammen mit fehlertoleranten Algorithmen aufzubauen.

  • Bei Bitcoin werden verteilte Transaktionen zur Berechnung des Hauptbuchs verwendet, und dies ist nicht nur auf reine Verarbeitungslastprobleme zurückzuführen. Der Algorithmus wurde sorgfältig entwickelt, um beschädigte Knoten zu vereiteln. Kurz gesagt, es "löst" / implementiert das Problem der byzantinischen Generäle, bei dem es nicht nur darum geht, die parallele Leistung zu maximieren, sondern auch darum, dass unabhängige Einheiten sich gegenseitig "überprüfen" und "algorithmisch / kryptografisch / sicher" ungültige Berechnungen, auch als "Betrug" oder "Betrug" bezeichnet, ablehnen. Korruption".

  • Eine klassische Analyse der Parallelität kommt zu dem Schluss, dass es ungefähr 7 "grundlegende" Problemmustertypen gibt, die in bestimmte parallele Ausführungszusammenbrüche zerlegt werden. siehe Die Landschaft der Parallelrechnungsforschung: Ein Blick von Berkeley

  • Es gibt hier einige Elemente einer offenen theoretischen Frage bezüglich der Leistung, die in den meisten anderen Antworten angesprochen werden. Die Frage, ob es Probleme gibt, die "von Natur aus schneller" als sequentiell sind, wird auch grob als das P =? NC-Problem bezeichnet, bei dem NC als die Klasse der "effizient parallelisierbaren" Algorithmen und P als "effiziente [sequentielle] Algorithmen" betrachtet wird "

vzn
quelle
1
Ich liebe diese Antwort! Ich habe viel aus Ihren Beispielen gelernt: D
Ben Leggiero
+1 für Fehlertoleranz in geschäftskritischen Umgebungen mit Strahlung, -1 für fehlende Kappen und Redundanz.
Cees Timmerman