408
7 Optimierung
n
: Anzahl der Tasks,
EC j : Anzahl ausgeführter Zyklen von Task j,
L : Anzahl von Spannungsstufen des Zielprozessors,
V i : die i-te Spannungsstufe, 1 ≤ i ≤ L,
f i : die Taktfrequenz für Versorgungsspannung V i ,
d
: die globale Deadline, an der alle Tasks beendet sein müssen,
SC j : die durchschnittliche Schalthäufigkeit während der Ausführung von Task j
(SC i besteht aus der tatsächlichen Kapazität C L und der Schalthäufigkeit α
(siehe Gleichung (3.14) auf Seite 159)).
Damit lässt sich das Spannungsskalierungs-Problem als ein Ganzzahliges Lineares Programmierproblem (ILP)-Problem beschreiben (siehe Seite 425). Hierzu
führen wir Variablen X i, j ein, welche die Anzahl von Zyklen beschreiben, die bei
einer bestimmten Spannung ausgeführt werden:
X i, j : Anzahl der Taktzyklen, die Task j bei Spannung V i ausführt
Das ILP-Modell macht die folgenden vereinfachenden Annahmen:
• Es gibt nur einen Zielprozessor, der mit einer begrenzten Anzahl von diskreten
Spannungen betrieben werden kann.
• Der Zeitaufwand für Spannungs- und Frequenzumschaltungen ist vernachlässigbar.
• Die größtmögliche Zyklenanzahl für jede Task ist bekannt.
Unter diesen Annahmen kann das ILP-Problem wie folgt beschrieben werden: Minimiere
E =
n
j=1
L
i=1
SC j ∗ X i, j ∗ V
2
i
(7.17)
unter den Randbedingungen
∀j :
L
i=1
X i, j = EC j
(7.18)
und
n
j=1
L
i=1
X i, j
f i
≤ d
(7.19)
Das Ziel ist es, die Anzahl X i, j an Zyklen zu finden, die eine Task j bei Spannung
V j ausgeführt wird. Wir haben weiter oben bereits festgestellt, dass keine Task jemals
mehr als zwei Spannungen benötigen wird. Mit diesem Modell zeigen Ishihara
und Yasuura, dass die Effizienz üblicherweise gesteigert werden kann, wenn Tasks
aus einer größeren Anzahl von Spannungsstufen wählen können. Wenn ein großer