Was bedeuten die Begriffe "CPU gebunden" und "I/O gebunden"?

Question

Was bedeuten die Begriffe "CPU gebunden" und "I/O gebunden"?

Answer 1

Es ist ziemlich intuitiv:

Ein Programm ist CPU-gebunden, wenn es schneller laufen würde, wenn die CPU schneller wäre, d. h., es verbringt den Großteil seiner Zeit damit, die CPU zu nutzen (Berechnungen durchzuführen). Ein Programm, das neue Ziffern von π berechnet, ist in der Regel CPU-gebunden, denn es rechnet einfach nur mit Zahlen.

Ein Programm ist I/O-gebunden, wenn es schneller laufen würde, wenn das I/O-Subsystem schneller wäre. Welches E/A-System genau gemeint ist, kann variieren; typischerweise verbinde ich es mit der Festplatte, aber natürlich sind auch Netzwerke oder Kommunikation im Allgemeinen üblich. Ein Programm, das eine große Datei nach bestimmten Daten durchsucht, könnte I/O-gebunden sein, da der Engpass dann das Lesen der Daten von der Festplatte ist (dieses Beispiel ist heutzutage mit Hunderten von MB/s, die von SSDs kommen, vielleicht etwas altmodisch).

Answer 2

CPU-Grenzen bedeutet, dass die Geschwindigkeit, mit der der Prozess voranschreitet, durch die Geschwindigkeit der CPU begrenzt ist. Eine Aufgabe, die Berechnungen mit einer kleinen Anzahl von Zahlen durchführt, z. B. die Multiplikation kleiner Matrizen, ist wahrscheinlich CPU-gebunden.

E/A-Grenze bedeutet, dass die Geschwindigkeit, mit der ein Prozess voranschreitet, durch die Geschwindigkeit des E/A-Subsystems begrenzt wird. Eine Aufgabe, die Daten von der Festplatte verarbeitet, z. B. das Zählen der Anzahl der Zeilen in einer Datei, ist wahrscheinlich I/O-gebunden.

Speicher gebunden bedeutet, dass die Geschwindigkeit, mit der ein Prozess voranschreitet, durch die verfügbare Speichermenge und die Geschwindigkeit des Speicherzugriffs begrenzt ist. Eine Aufgabe, die große Mengen von Daten im Speicher verarbeitet, z. B. die Multiplikation großer Matrizen, ist wahrscheinlich speicherbegrenzt.

Cache gebunden bedeutet, dass die Geschwindigkeit, mit der ein Prozess voranschreitet, durch die Menge und Geschwindigkeit des verfügbaren Cache begrenzt ist. Eine Aufgabe, die einfach mehr Daten verarbeitet, als in den Cache passen, ist cachegebunden.

I/O Bound wäre langsamer als Memory Bound wäre langsamer als Cache Bound wäre langsamer als CPU Bound.

Die Lösung für das Problem der E/A-Beschränkung besteht nicht unbedingt darin, mehr Speicherplatz zu schaffen. In manchen Situationen kann der Zugriffsalgorithmus so gestaltet werden, dass er die E/A-, Speicher- oder Cache-Beschränkungen umgeht. Siehe Cache-pflichtige Algorithmen .

Answer 3

Multi-Threading ist der Bereich, in dem es am wichtigsten ist

In dieser Antwort werde ich einen wichtigen Anwendungsfall der Unterscheidung zwischen CPU- und IO-gebundener Arbeit untersuchen: beim Schreiben von Multithreading-Code.

RAM I/O gebundenes Beispiel: Vektorsumme

Betrachten wir ein Programm, das alle Werte eines einzelnen Vektors summiert:

#define SIZE 1000000000
unsigned int is[SIZE];
unsigned int sum = 0;
size_t i = 0;
for (i = 0; i < SIZE; i++)
    /* Each one of those requires a RAM access! */
    sum += is[i]

Eine Parallelisierung durch gleichmäßige Aufteilung des Arrays auf die einzelnen Kerne ist auf modernen Desktops nur von begrenztem Nutzen.

Zum Beispiel, auf meinem Ubuntu 19.04, Lenovo ThinkPad P51 Laptop mit CPU: Intel Core i7-7820HQ CPU (4 Kerne / 8 Threads), RAM: 2x Samsung M471A2K43BB1-CRC (2x 16GiB) Ich erhalte Ergebnisse wie diese:

Plot-Daten .

Es ist jedoch zu beachten, dass es zwischen den einzelnen Läufen große Unterschiede gibt. Aber ich kann die Array-Größe nicht viel weiter erhöhen, da ich bereits bei 8GiB bin, und ich bin nicht in der Stimmung für Statistiken über mehrere Läufe heute. Dies schien jedoch ein typischer Lauf zu sein, nachdem ich viele manuelle Läufe durchgeführt hatte.

Benchmark-Code:

• POSIX C pthread Quellcode in der Grafik verwendet.

  Und hier ist ein C++-Version die zu analogen Ergebnissen führt.

• Handlungsskript

Ich kenne mich mit der Computerarchitektur nicht gut genug aus, um die Form der Kurve vollständig zu erklären, aber eines ist klar: Die Berechnung wird nicht 8x schneller, wie naiverweise erwartet, weil ich alle meine 8 Threads verwende! Aus irgendeinem Grund waren 2 und 3 Threads das Optimum, und wenn man mehr hinzufügt, wird alles nur noch viel langsamer.

Vergleichen Sie dies mit CPU-gebundener Arbeit, die tatsächlich 8 Mal schneller wird: Was bedeuten "real", "user" und "sys" in der Ausgabe von time(1)?

Der Grund dafür ist, dass sich alle Prozessoren einen einzigen Speicherbus teilen, der mit dem RAM verbunden ist:

CPU 1   --\    Bus    +-----+
CPU 2   ---\__________| RAM |
...     ---/          +-----+
CPU N   --/

Daher wird der Speicherbus schnell zum Engpass, nicht die CPU.

Dies geschieht, weil das Addieren von zwei Zahlen einen einzigen CPU-Zyklus in Anspruch nimmt, das Lesen des Speichers dauert etwa 100 CPU-Zyklen in 2016 Hardware.

Die pro Byte Eingabedaten geleistete CPU-Arbeit ist also zu gering, und wir nennen dies einen IO-gebundenen Prozess.

Die einzige Möglichkeit, die Berechnung weiter zu beschleunigen, besteht darin, einzelne Speicherzugriffe mit neuer Speicherhardware zu beschleunigen, z. B. Mehrkanaliger Speicher .

Ein Upgrade auf einen schnelleren CPU-Takt wäre zum Beispiel nicht sehr sinnvoll.

Andere Beispiele

• Die Matrixmultiplikation ist auf RAM und GPUs CPU-gebunden. Die Eingabe enthält:

  2 * N**2

  Zahlen, aber:

  N ** 3

  Multiplikationen durchgeführt werden, und das ist genug, damit sich die Parallelisierung für praktisch große N lohnt.

  Aus diesem Grund gibt es parallele CPU-Matrixmultiplikationsbibliotheken wie die folgende:

  • http://www.netlib.org/scalapack/pblas_qref.html
  • http://icl.cs.utk.edu/magma/software/

  Die Nutzung des Cache hat einen großen Einfluss auf die Geschwindigkeit von Implementierungen. Siehe zum Beispiel dies didaktisches GPU-Vergleichsbeispiel .

  Siehe auch:

  • Warum kann die GPU eine Matrixmultiplikation schneller durchführen als die CPU?
  • BLAS-Äquivalent einer LAPACK-Funktion für GPUs

• Die Vernetzung ist das prototypische Beispiel für die IO-Bindung.

  Selbst wenn wir ein einziges Byte an Daten senden, dauert es sehr lange, bis es sein Ziel erreicht.

  Die Parallelisierung kleiner Netzwerkanfragen wie HTTP-Anfragen kann einen enormen Leistungszuwachs bieten.

  Wenn das Netz bereits voll ausgelastet ist (z. B. beim Herunterladen eines Torrents), kann die Parallelisierung die Latenz noch verbessern (z. B. können Sie eine Webseite "gleichzeitig" laden).

• Eine Dummy-C++-CPU-gebundene Operation, die eine Zahl nimmt und sie stark verdichtet:

  • Serie
  • parallel

• Die Sortierung scheint eine CPU zu sein, wie das folgende Experiment zeigt: Sind parallele C++17-Algorithmen bereits implementiert? die eine 4-fache Leistungsverbesserung für paralleles Sortieren zeigte, aber ich hätte auch gerne eine theoretische Bestätigung

• Der bekannte Coremark Benchmark von EEMBC prüft ausdrücklich, wie gut eine Reihe von Problemen skaliert. Ein Beispiel für ein Benchmark-Ergebnis, das zeigt, dass:

  Workload Name                                     (iter/s)   (iter/s)    Scaling
  ----------------------------------------------- ---------- ---------- ----------
  cjpeg-rose7-preset                                  526.32     178.57       2.95
  core                                                  7.39       2.16       3.42
  linear_alg-mid-100x100-sp                           684.93     238.10       2.88
  loops-all-mid-10k-sp                                 27.65       7.80       3.54
  nnet_test                                            32.79      10.57       3.10
  parser-125k                                          71.43      25.00       2.86
  radix2-big-64k                                     2320.19     623.44       3.72
  sha-test                                            555.56     227.27       2.44
  zip-test                                            363.64     166.67       2.18
  
  MARK RESULTS TABLE
  
  Mark Name                                        MultiCore SingleCore    Scaling
  ----------------------------------------------- ---------- ---------- ----------
  CoreMark-PRO                                      18743.79    6306.76       2.97

• el Verknüpfung eines C++-Programms kann bis zu einem gewissen Grad parallelisiert werden: Kann gcc beim Linken mehrere Kerne verwenden?

So finden Sie heraus, ob Sie CPU- oder IO-gebunden sind

Nicht-RAM-gebundene IO wie Festplatte, Netzwerk: ps aux , dann prüfen Sie, ob CPU% / 100 < n threads . Wenn ja, sind Sie IO-gebunden, z. B. durch Blockieren read s nur auf Daten warten und der Scheduler diesen Prozess überspringt. Verwenden Sie dann weitere Tools wie sudo iotop zu entscheiden, welches IO genau das Problem ist.

Oder, wenn die Ausführung schnell ist und Sie die Anzahl der Threads parametrieren, können Sie dies leicht aus time dass sich die Leistung mit zunehmender Anzahl von Threads für CPU-gebundene Arbeit verbessert: Was bedeuten "real", "user" und "sys" in der Ausgabe von time(1)?

RAM-IO-Bindung: schwieriger zu erkennen, da die RAM-Wartezeit in die CPU% Messungen, siehe auch:

• Wie prüft man, ob eine Anwendung cpu- oder speicherabhängig ist?
• https://askubuntu.com/questions/1540/how-can-i-find-out-if-a-process-is-cpu-memory-or-disk-bound

Einige Optionen:

• Intel Advisor Roofline (nicht kostenlos): https://software.intel.com/en-us/articles/intel-advisor-roofline ( Archiv ) "Ein Roofline-Diagramm ist eine visuelle Darstellung der Anwendungsleistung im Verhältnis zu den Hardware-Beschränkungen, einschließlich der Speicherbandbreite und der Berechnungsspitzen."

GPUs

GPUs haben einen IO-Engpass, wenn Sie die Eingabedaten aus dem regulären, von der CPU lesbaren RAM in die GPU übertragen.

Daher können GPUs nur bei CPU-gebundenen Anwendungen besser sein als CPUs.

Sobald die Daten jedoch an den Grafikprozessor übertragen werden, kann er diese Bytes schneller verarbeiten als die CPU, da der Grafikprozessor sie verarbeiten kann:

• hat mehr Datenlokalisierung als die meisten CPU-Systeme, so dass der Zugriff auf Daten für einige Kerne schneller erfolgen kann als für andere

• nutzt die Datenparallelität und opfert die Latenzzeit, indem es Daten, die nicht sofort verarbeitet werden können, einfach überspringt.

  Da die GPU mit großen parallelen Eingabedaten arbeiten muss, ist es besser, einfach zu den nächsten verfügbaren Daten zu springen, anstatt zu warten, bis die aktuellen Daten verfügbar sind, und alle anderen Operationen zu blockieren, wie es die CPU meistens tut

Daher kann der Grafikprozessor in Ihrer Anwendung schneller sein als eine CPU:

• hochgradig parallelisiert werden kann: verschiedene Datenpakete können gleichzeitig und getrennt voneinander verarbeitet werden
• eine ausreichend große Anzahl von Operationen pro Eingangsbyte erfordert (anders als z. B. bei der Vektoraddition, die nur eine Addition pro Byte durchführt)
• es gibt eine große Anzahl von Eingangsbytes

Diese Entwürfe zielten ursprünglich auf die Anwendung von 3D-Rendering ab, dessen Hauptschritte wie folgt aussehen Was sind Shader in OpenGL und wozu brauchen wir sie?

• Vertex-Shader: Multiplikation einer Reihe von 1x4-Vektoren mit einer 4x4-Matrix
• Fragment-Shader: Berechnung der Farbe jedes Pixels eines Dreiecks auf der Grundlage seiner relativen Position innerhalb des Dreiecks

und daraus schließen wir, dass diese Anwendungen CPU-gebunden sind.

Mit dem Aufkommen der programmierbaren GPGPU können wir mehrere GPGPU-Anwendungen beobachten, die als Beispiele für CPU-gebundene Operationen dienen:

• Bildverarbeitung mit GLSL-Shadern?

  

  Lokale Bildverarbeitungsvorgänge wie z. B. ein Unschärfefilter sind von Natur aus hochgradig parallel.

• Ist es möglich, eine Heatmap aus Punktdaten mit 60 Mal pro Sekunde zu erstellen?

  Plotten von Heatmap-Diagrammen, wenn die geplottete Funktion komplex genug ist.

  

• https://www.youtube.com/watch?v=fE0P6H8eK4I "Echtzeit-Fluiddynamik: CPU vs. GPU" von Jesús Martín Berlanga

  Lösen von partiellen Differentialgleichungen wie der Navier-Stokes-Gleichung der Strömungsdynamik:

  • hochgradig parallel sind, da jeder Punkt nur mit seinem Nachbarn interagiert
  • es gibt in der Regel genügend Operationen pro Byte

Siehe auch:

• Warum verwenden wir immer noch CPUs anstelle von GPUs?
• Worin sind GPUs schlecht?
• https://www.youtube.com/watch?v=_cyVDoyI6NE "CPU vs. GPU (Was ist der Unterschied?) - Computerphile"

CPython Global Intepreter Lock (GIL)

Als kurze Fallstudie möchte ich auf die Python Global Interpreter Lock (GIL) hinweisen: Was ist die globale Interpretersperre (GIL) in CPython?

Dieses Detail der CPython-Implementierung verhindert, dass mehrere Python-Threads CPU-gebundene Arbeit effizient nutzen können. Die CPython-Dokumente sagen:

CPython-Implementierung im Detail: In CPython kann aufgrund der Global Interpreter Lock nur ein Thread gleichzeitig Python-Code ausführen (auch wenn bestimmte leistungsorientierte Bibliotheken diese Einschränkung überwinden können). Wenn Sie möchten, dass Ihre Anwendung die Rechenressourcen von Multicore-Maschinen besser ausnutzt, empfehlen wir Ihnen die Verwendung von multiprocessing o concurrent.futures.ProcessPoolExecutor . Das Threading ist jedoch immer noch ein geeignetes Modell, wenn Sie mehrere E/A-gebundene Tasks gleichzeitig ausführen wollen.

Daher haben wir hier ein Beispiel, bei dem CPU-gebundener Inhalt nicht geeignet ist und E/A-gebundener schon.

JavaScript async und Node.js worker_threads

Die Situation ist ähnlich wie bei Python.

JavaScript ist grundsätzlich single threaded. Nicht sicher, ob dies Teil des Sprachstandards ist oder nicht (für Python ist es nicht, es gibt nicht einmal einen Sprachstandard neben der Referenz CPython Implementierung AFAIK).

JavaScript hat die async Schlüsselwort, das es ermöglicht, die Ausführung anzuhalten, und dann mit der Ausführung von etwas anderem zu beginnen. Sie können Dinge schreiben wie:

async function myfunc(init) {
  ret = init
  for (let i = 0; i < 1000000; i++) {
    ret += i*i + 2*i + 3
  }
  return ret;
}

async function doNetworkRequest(init) {
  // Some native method that gets network data.
}

const [first, second, myfunc_ret1, myfunc_ret2] = await Promise.all([
  doNetworkRequest('example.com'),
  doNetworkRequest('example2.com'),
  myfunc(1),
  myfunc(2),
])

où await sagt "warte, bis all diese asynchronen Dinge beendet sind, bevor du weitermachst".

Allerdings ist nur eine der async Methoden gleichzeitig auf Ihrer CPU laufen können, so dass die CPU-intensive Arbeit von myfunc wird dadurch überhaupt nicht beschleunigt.

Der prototypische IO-gebundene Vorgang des Netzwerkzugriffs kann jedoch beschleunigt werden, da hier beide Netzwerkanfragen nacheinander abgefeuert werden und einfach gewartet wird, bis beide zurückkommen, während die Server/Netzwerke die Arbeit erledigen.

Die Tatsache, dass es in der Sprache ein eigenes Schlüsselwort dafür gibt, async ist aufschlussreich: Es überrascht nicht, dass Netzwerkanfragen in dem vom Browser dominierten Kontext von JavaScript sehr wichtig sind.

Mit dem Aufkommen von Node.js begannen die Leute jedoch, auch die CPU-Arbeitslast mehr und mehr zu parallelisieren, und sie kamen zu einer ähnlichen Lösung wie CPython: separate Prozesse anstelle von Threads zu erstellen. Dies wird mit dem worker_threads Bibliothek die:

• nimmt einen JavaScript-Skriptpfad als Eingabe und startet eine neue Interpreterinstanz, um es auszuführen
• Da sich die Prozesse keinen Speicherplatz teilen, werden Nachrichten zwischen den Instanzen mit einem Nachrichtensystem übermittelt.

https://medium.com/@Trott/using-worker-threads-in-node-js-80494136dbb6 enthält ein gutes Beispiel.

Die Dokumentation von worker_threads weist noch einmal auf den Unterschied hin, der bereits an anderer Stelle in dieser Antwort erwähnt wurde:

Worker (Threads) sind nützlich für die Durchführung CPU-intensiver JavaScript-Operationen. Bei E/A-intensiver Arbeit sind sie nicht sehr hilfreich. Die in Node.js eingebauten asynchronen E/A-Operationen sind effizienter als Workers es sein können.

Im Browser gibt es auch Web Workers, ich bin mir nicht sicher, wie sie mit der Implementierung von Node zu vergleichen sind: Was ist der Unterschied zwischen Web Workers und Worker Threads?

Answer 4

CPU-gebunden bedeutet, dass das Programm von der CPU (Central Processing Unit) eingeengt wird, während E/A gebunden bedeutet, dass das Programm durch E/A (Eingabe/Ausgabe) einen Engpass hat, z. B. beim Lesen oder Schreiben auf der Festplatte, im Netzwerk usw.

Im Allgemeinen versucht man bei der Optimierung von Computerprogrammen, den Engpass zu finden und zu beseitigen. Zu wissen, dass Ihr Programm die CPU belastet, hilft, damit Sie nicht unnötig etwas anderes optimieren.

(Und mit "Engpass" meine ich das, was Ihr Programm langsamer macht als es sonst wäre.)

Answer 5

Man kann denselben Gedanken auch anders formulieren:

• Wenn die Beschleunigung der CPU Ihr Programm nicht beschleunigt, kann es sein, dass E/A gebunden.

• Wenn eine Beschleunigung der E/A (z. B. durch Verwendung einer schnelleren Festplatte) nicht hilft, ist Ihr Programm möglicherweise CPU-lastig.

(Ich habe "kann sein" verwendet, weil man auch andere Ressourcen berücksichtigen muss. Der Speicher ist ein Beispiel).