Ich habe gerade einen Artikel über einen Durchbruch bei der Matrixmultiplikation gelesen; ein Algorithmus, der O ist (n^2.373). Aber ich denke Matrixmultiplikation ist etwas, das parallelisiert werden kann. Wenn wir jemals mit der Produktion von Prozessoren mit tausend Kernen beginnen, wird das dann irrelevant werden? Wie würden sich die Dinge ändern?Werden Algorithmen auf der Big-o-Notation von Parallelität beeinflusst?
Wenn Quantencomputer irgendwann zu etwas Praktischem kommt, dann wird sich die Komplexität der Algorithmen ändern.
In der Zwischenzeit teilt die Parallelisierung eines Algorithmus mit einer festen Anzahl von Prozessoren gerade seine Laufzeit proportional (und das, im besten Fall, wenn keine Abhängigkeiten zwischen den auf jedem Prozessor ausgeführten Aufgaben bestehen). Das heißt, die Laufzeit wird durch eine Konstante geteilt, und so bleibt die Komplexität gleich.
Parallele Ausführung ändert nicht die Grundlagen der Komplexität für einen bestimmten Algorithmus - im besten Fall nehmen Sie nur die Zeit für eine bestimmte Größe und dividieren durch die Anzahl der Kerne. Dies kann die Zeit für eine gegebene Größe um einen konstanten Faktor reduzieren, hat jedoch keine Auswirkung auf die Komplexität des Algorithmus.
Zur gleichen Zeit ändert sich die parallele Ausführung manchmal welche Algorithmus (e) Sie für bestimmte Aufgaben verwenden möchten. Einige Algorithmen, die in seriellem Code gut funktionieren, teilen sich nicht sehr gut in parallele Aufgaben auf. Andere, die eine höhere Komplexität haben, könnten bei praktischen Problemen schneller sein, weil sie besser parallel laufen.
Für eine extrem große Anzahl von Kernen kann die Komplexität der Berechnung selbst zweitrangig werden, um einfach die notwendigen Daten von/zu allen Kernen zu erhalten, um die Berechnung durchzuführen. Die meisten Berechnungen von big-O berücksichtigen diese Effekte nicht für eine serielle Berechnung, aber sie können für parallele Berechnungen sehr wichtig werden, insbesondere für einige Modelle paralleler Maschinen, die keinen einheitlichen Zugriff auf alle Knoten ermöglichen.
Von Amdahl's law, für die gleiche Größe des Problems, wird die Parallelisierung zu einem Punkt der abnehmenden Rendite mit der Erhöhung der Anzahl der Kerne (theoretisch) kommen. In der Realität wird der Overhead der Parallelisierung ab einem bestimmten Grad der Parallelisierung tatsächlich die Leistung des Programms verringern.
Allerdings, durch Gustafson's law, hilft die Erhöhung der Anzahl der Kerne tatsächlich, wie die Größe des Problems zunimmt. Das ist die Motivation hinter Cluster-Computing. Da wir mehr Rechenleistung haben, können wir das Problem mit Hilfe der Parallelisierung in größerem Maßstab oder besser mit Präzision angehen.
Algorithmen, die wir lernen, wie sie sind, können oder können nicht parallelisiert werden. Manchmal muss ein separater Algorithmus verwendet werden, um die gleiche Aufgabe effizient parallel auszuführen. In jedem Fall muss die Big-O-Notation für den Parallelfall erneut analysiert werden, um den Effekt der Parallelisierung auf die zeitliche Komplexität des Algorithmus zu berücksichtigen.
Dieser Algorithmus ist nur ein theoretischer Durchbruch; Soweit ich weiß, wird sogar der Coppersmith-Winograd-Algorithmus in der Praxis nicht verwendet. – sdcvvc
Es gibt n log^2 (n) -Algorithmus für maschenbasierte Architektur, mit n Prozessor, für Matrixmultiplikation (theoretisch), auch gibt es zu viele Algorithmen, die unabhängig von ihrem normalen "O" sind, wenn Sie parallel denken wollen Algorithmen sollten Sie über andere Wege nachdenken, normale Wege sind normalerweise nutzlos. –