Gibt es eine abstrakte Maschine, die den Stromverbrauch erfassen kann?

Question

Bei der Meldung der algorithmischen Komplexität eines Algorithmus geht davon aus, dass die zugrunde liegenden Berechnungen auf einer abstrakten Maschine (z. B. RAM) durchgeführt werden, die sich einer modernen CPU annähert. Solche Modelle ermöglichen es uns, Zeit und Raumkomplexität von Algorithmen zu melden. Nun, mit der Ausbreitung Gpgpus, Man fragt sich, ob es bekannte Modelle gibt, in denen man auch den Stromverbrauch berücksichtigen kann.

Es ist bekannt, dass GPUs erheblich verbraucht werden, und bestimmte Anweisungen fallen in verschiedenen Kategorien des Stromverbrauchs, die auf ihrer Komplexität und ihrem Standort auf dem hoch entwickelten Chip basieren. Daher sind Anweisungen aus einer Sichtergie nicht aus Einheiten (oder sogar festen) Kosten. Eine triviale Erweiterung würde den Betriebskosten Gewichte zuweisen, aber ich suche ein leistungsstarkes Modell, bei dem ein Betrieb/Anweisungen möglicherweise kosten könnte nicht konstant Energieeinheiten, z. B. Polynommenge (oder sogar komplexer, z. ))

Gibt es solche Modelle, bei denen nicht triviale Kosten und Fehler eingebaut werden können?

Answer 1

Es gibt noch kein etabliertes Modell, aber dies ist derzeit ein Bereich aktiver Forschung. Einer der Experten auf der Seite von Algorithmen ist Kirk Pruhs. Seine Papiere mehr Informationen haben, und Sie können auch Durchsuchen Sie diese Präsentation.

Answer 2

Modelle für den Energieverbrauch

Die Geschwindigkeitskalierung ist (in letzter Zeit) eines der am häufigsten verwendeten Modell bei der Betrachtung des Energieverbrauchs. Es besteht darin, die Versorgungsspannung zu ändern. Durch die Senkung der Versorgungsspannung oder die Verarbeitungsaktuhrenfrequenz ist es möglich, einen wichtigen Stromverbrauch zu erzielen. Schnelle Geschwindigkeiten ermöglichen eine schnellere Ausführung, führen aber auch zu einem viel höheren (supra-linearen) Stromverbrauch.

Genauer gesagt löst ein Prozessor mit der Geschwindigkeit $ s $ $ s^3 $ Watt pro Zeiteinheit auf, daher konsumiert er $ s^3 mal d $ jule, wenn er während der $ D $ -Einheiten der Zeit betrieben wird.

Die Geschwindigkeitskalierung ist jedoch nicht die einzige in Betracht gezogene Energie. Es ist das, was genannt wird dynamisch Energie. Das statisch Energie ist die Leistung, die darauf zurückzuführen ist, dass der Prozessor "on" ist. Es ist möglich, dies loszuwerden statisch Durchführen, indem der Prozessor während der Leerlaufzeit abgeschaltet wird. Es hat jedoch Kosten. Es wurden viele Arbeiten zu diesem Thema geleistet, was sehr nahe kommt Ski -Mietproblem.

Normalerweise ist der Energieverbrauch die Summe der statischen und dynamischen Stromverbrauchszeiten der Ausführungszeit. Der größte Teil des Papiers konzentriert sich jedoch auf eines dieser Probleme.

Einführung von Fehlern in diesem Modell

Ich denke, dies ist der überraschendste Teil des Geschwindigkeitskalierungsmodells. Normalerweise würde man denken, dass je schneller Sie eine Aufgabe ausführen, desto wahrscheinlicher ist es, dass Sie die Ausführung nicht bestehen. Im Gegenteil, es wurde gezeigt, dass die Verringerung der Geschwindigkeit eines Prozessors die Anzahl der transienten Fehlerraten des Systems erhöht. Die Wahrscheinlichkeit von Ausfällen nimmt exponentiell zu, und diese Wahrscheinlichkeit kann bei großem Maßstab nicht vernachlässigt werden.

Intuitiv gibt es die Tatsache, dass je mehr Zeit Sie für eine Aufgabe ausgeben, desto mehr Chancen müssen Sie während der Ausführung dieser Aufgabe scheitern müssen. Es gibt jedoch mehr als das: Shatz und Wang in Dies, stellte fest, dass das Fehlermodell einer Poisson-Verteilung folgte. Der Parameter $ lambda $ der Poisson-Verteilung lautet dann: $$ lambda (f) = lambda_0 e^{d frac {fmax-f} {fmax-fmin}}, $$, wobei $ f $ ist Die Verarbeitungsgeschwindigkeit umfasst $ [fMin, fmax] $ und $ lambda_0 $ und $ d $ hängen konstant vom Systyem ab. Wenn Sie eine Aufgabe von Gewicht $ W $ betrachten, die mit Geschwindigkeit $ f $ ausgeführt wird, beträgt die Zuverlässigkeit der Ausführung für diese Aufgabe $ r (f) = e^{- lambda (f) times frac {w} { f}} $.

Dies ist Selbstreferenz, daher weiß ich nicht, ob sie hier geschätzt werden. Wenn Sie jedoch interessiert sind, finden Sie mehr Informationen darin Papier auf der dynamisch Teil des Energieverbrauchs.

Answer 3

Es gab Versuche, theoretisch den Energieverbrauch von Algorithmen zu analysieren (natürlich unter Verwendung realer Kosten pro Betrieb). Siehe zB [1]. Während die Ergebnisse überraschend genug sind-der schnellste Algorithmus ist nicht immer derjenige, der die geringste Energie nutzt-, bleiben einige Hindernisse.

Insbesondere die modernen Plattformen schalten bestimmte Funktionen aus, so dass die Betriebsenergiespikes beim Wieder eingeschaltet werden. Während im Prinzip in strenge Analysen möglich ist, wird es technisch (auch?) Schwierig. Außerdem wurde die Auswirkung von Cache -Fehlschlägen auf den gesamten Energieverbrauch nicht gut untersucht.

Es scheint, dass große Unterschiede zwischen Plattformen strenge Analysen widersetzen, die (ausnahmsweise) keine Einzelheiten ignorieren können, da allgemeine Modelle (dh vor dem Einstecken von Betonkonstanten/-funktionen) eine begrenzte Bedeutung haben.

---

1. Hannah Bayer und Markus E. Nebel: Bewertung von Algorithmen nach ihrem Energieverbrauch, Computerbarkeit in Europa, 2009