Effiziente Ressourcennutzung durch intelligente Übersetzer · © H. Falk, S. Plazar SW ubiquitärer Systeme – Effiziente Ressourcennutzung 2 Gliederung Eigenschaften von heutigen

© H. Falk, S. Plazar SW ubiquitärer Systeme – Effiziente Ressourcennutzung

Effiziente Ressourcennutzung durch intelligente Übersetzer

Sommersemester 2012

Sascha Plazar

Technische Universität Dortmund Lehrstuhl Informatik 12

Entwurfsautomatisierung für Eingebettete Systeme

© H. Falk, S. Plazar SW ubiquitärer Systeme – Effiziente Ressourcennutzung 2

Gliederung Eigenschaften von heutigen Systemen Eigenschaften von Speichern Scratchpad-Speicher und Caches Scratchpad-Allokation durch Compiler

Ganzzahlig-lineare Programmierung (ILP) Allokation von Funktionen & globalen Daten zur Energiereduktion ILP-Formulierung

Eigenschaften von Realzeit-Systemen Statisches Locken von Instruktions-Caches

Modellierung des kritischen Pfades Codepositionierung


Potential zur Ressourceneinsparung

Mögliche Maßnahmen eines Übersetzers: Dynamisches Power-Management Versetzen des Prozessors (oder anderer Komponenten) in

Sleep-, Idle- bzw. Run-Modus zur Laufzeit Dynamisches Anpassen der Betriebsspannung / Taktfrequenz Dynamic Voltage / Frequency Scaling

Compiler-Optimierungen Erzeugung von schnellem Code Erzeugung von kompaktem Code Ausnutzung spezialisierter Hardwarefeatures

z.B. (energie-) effizienter Speicher

3


Eigenschaften heutiger Systeme (1) Energieverbrauch mobiler Geräte:

[O. Vargas (Infineon), Minimum power consumption in mobile- phone memory subsystems, Pennwell Portable Design, Sep. 2005]

4


Eigenschaften heutiger Systeme (2)

Speicher-Subsystem ver-ursacht häufig weit mehr als 50% des gesamten Energieverbrauchs.

Tortendiagramme zeigen Durchschnitt über jeweils mehr als 160 verschie-dene Energie-Messungen

[M. Verma, P. Marwedel, Advanced Memory Optimization Techniques for Low-Power Embedded Processors, Springer, 2007]

34,8%

65,2%

ProzessorEnergieHauptspeicherEnergie

54,1%

4,1%

20,6%

10,3%

10,8%

ProzessorEnergieHauptspeicherEnergieScratchpadEnergieI-CacheEnergieD-CacheEnergie

ARM7 Mono-Prozessor ohne Cache:

ARM7 Multi-Prozessor mit Caches:

5


Eigenschaften heutiger Speicher (1)

2

4

8

2 4 5

Geschwindigkeit

Jahre 3 1

≥ Faktor 2 alle 2 Jahre

1 0

Geschwindigkeitsunterschied zwischen CPUs und DRAMs verdoppelt sich alle 2 Jahre.

Schnelle CPUs werden massiv durch langsame Speicher ausgebremst.

„Memory Wall”-Problem

[P. Machanik, Approaches to Addressing the Memory Wall, Technical Report, Universität Brisbane, Nov. 2003]

6



Energie

Zugriffszeit

Mit zunehmender Größe eines Speichers verbraucht ein Speicherzugriff überproportional mehr Energie.

Mit zunehmender Größe dauern Speicherzugriffe auch proportional länger.

Fertigungstechnologie von Speichern legt Nutzung kleiner Speicher nahe!

7



Speicher oft begrenzender Faktor Einsatz von Speicherhierarchien Häufig benutzte Daten/Code in kleinen schnellen Speichern Optimierung von Speicherzugriffsmustern

CPU

IFB

Haupt- speicher SPM

Cache

8


Scratchpad-Speicher

Scratchpads (SPMs) sind kleine, physikalisch separate Speicher. Sie sind meist auf dem selben Chip platziert wie der Prozessor

(sog. on-chip Speicher). Durch geringe Größe und on-chip Platzierung: extrem schnelle

und energieeffiziente Speicher Sind in den Adressraum des Pro-

zessors nahtlos eingeblendet: Zugriff über Erkennen einer

am Bus anliegenden Adres-se aus SPM-Adressbereich (simpler Adress-Decoder):

Scratchpad-Speicher

0x000…

0xFFF… SPM

select

9


Aufbau mengenassoziativer Caches

Tag Index

Adresse

Tag- Speicher

Daten- Speicher

Tag- Speicher

Daten- Speicher

Way 0 Way 1

= =

Datum

10


Eigenschaften von Scratchpad-Speichern (1)

Stromverbrauch im Vergleich zu Hauptspeicher: Messungen an realer Hardware (Atmel ARM7-Evaluationsboard)

zeigen, dass z.B. ein Lade-Befehl um Faktor 3 weniger Strom ver-braucht, wenn sowohl Lade-Befehl als auch zu ladendes Datum im SPM anstatt im (off-chip) Hauptspeicher liegen:

Stromverbrauch Lade-Befehl

48.2 50.9 44.4 53.1

11677.2 82.2

1.16

0

50

100

150

200

Prog Main/ DataMain

Prog Main/ DataSPM

Prog SPM/ DataMain

Prog SPM/ DataSPM

mA

Haupt-SpeicherARM7 +SPM

11



Energieverbrauch im Vergleich zu Caches: Größe und Anzahl von Tag-Speichern, Vergleichern und Multi-

plexern hängt von Größe des gecacheten Speicherbereichs ab. Energieverbrauch dieser HW-Komponenten beträchtlich:

0

1

2

3

4

5

6

7

8

9

256 512 1024 2048 4096 8192 16384

Speicher-Größe

Ener

gie

pro

Zugr

iff [

nJ]

ScratchpadCache, 2way, 4GB spaceCache, 2way, 16 MB spaceCache, 2way, 1 MB space

[R. Banakar et al., Comparison of Cache- and Scratch-Pad based Memory Systems..., Report #762, Universität Dortmund, Sep. 2001]

12



Energieverbrauch im Vergleich zu Caches: Energieverbrauch von Caches hängt zusätzlich stark vom Grad

der Assoziativität ab:

Vorsicht: Technologie bei diesem Diagramm unterschiedlich zur letzten Folie. Daher Abweichungen in absoluten Zahlen-werten!

13


Scratchpad-Allokation

Motivation: Caches entscheiden autonom in Hardware, welche Inhalte ein-

und auszulagern sind SPMs können dies mangels autonomer Hardware nicht Wer entscheidet, welche sinnvollen Inhalte (Code, Daten) im SPM

gespeichert werden sollen?

Compiler führt SPM-Allokation durch, da dieser Eigenschaften des generierten Assemblercodes kennt und optimale Entscheidung treffen kann.

Optimierungsproblem: Welche Teile eines Assembler-Programms sollen in den SPM eingelagert werden, so dass ein Kriterium minimiert wird und der SPM nicht überfüllt wird?

14


Ganzzahlig lineare Programmierung Modellierungstechnik für lineare Optimierungsprobleme Optimierung einer Zielfunktion z Beachtung von Nebenbedingungen n1, ..., nm

Zielfunktion und Nebenbedingungen sind lineare Ausdrücke über den ganzzahligen Entscheidungsvariablen x1, ..., xn

→ minimieren oder maximieren

Optimale Lösung sog. ILPs (Integer Linear Programs) mit Hilfe von Standard-Solvern (z.B. lp_solve, cplex); Komplexität: im worst-case exponentiell, üblicherweise aber „OK”.

Konstanten A, b, c ∈ ℝ Variablen x ∈ ℤ

15


SPM-Allokation: Energiereduktion Funktionen & Globale Variablen (1) Ziel: Verschiebung des Codes von kompletten Funktionen und von

globalen Variablen in den SPM (lokale Variablen liegen üblicherweise auf dem Stack und werden daher nicht betrachtet)

Compiler ermittelt zur Übersetzungszeit, welche Funktionen und globalen Variablen den SPM belegen.

Diese SPM-Belegung bleibt zur Ausführungszeit eines optimierten Programms statisch, d.h. der SPM-Inhalt ändert sich zur gesamten Ausführungszeit nicht.

16


SPM-Allokation: Energiereduktion Funktionen & Globale Variablen (2) Definitionen: S Größe des verfügbaren SPMs in Bytes. MO = {mo1, ..., mon} Menge aller für die Verschiebung auf

= F ∪ V den SPM in Frage kommender Speicherobjekte (memory objects), d.h. Funktionen F bzw. globale Variablen V.

Si Größe von Speicherobjekt moi in Bytes. xi Binäre Entscheidungsvariable zu moi

xi = 1 ⇔ moi wird in SPM verschoben

17


SPM-Allokation: Energiereduktion Funktionen & Globale Variablen (3) Definitionen (Fortsetzung): ni Gesamt-Anzahl von Ausführungen bzw.

Zugriffen auf moi ∆ei Eingesparte Energie, wenn moi von

Hauptspeicher in SPM verschoben wird, pro einzelner Ausführung von moi ∈ F bzw. pro einzelnem Zugriff auf moi ∈ V.

∆Ei Gesamte eingesparte Energie, wenn moi von Hauptspeicher in SPM verschoben wird, pro kompletter Ausführung des zu optimierenden Programms (= ni * ∆ei)

18


SPM-Allokation: Energiereduktion Funktionen & Globale Variablen (4) Bestimmung der Parameter: Vor der eigentlichen Scratchpad-Optimierung eines Programms

findet ein Simulationsdurchlauf statt, um zur Optimierung notwendige Parameter zu ermitteln.

Ein solcher Simulationsdurchlauf erzeugt ein Laufzeit-Profil des zu optimierenden Programms. Daher heißt diese Simulation vor einer Optimierung auch Profiling.

ni: Profilingdurchlauf liefert Ausführungs- und Zugriffshäufigkeiten für moi.

19


SPM-Allokation: Energiereduktion Funktionen & Globale Variablen (5) Bestimmung der Parameter (Fortsetzung): S: Vom Anwender vorgegeben, konstant Si: Entweder Summe über die Größe aller Instruktionen einer

Funktion, oder Summe über die Größen aller Teil-Variablen, z.B. bei Feldern oder Strukturen

∆ei: Für moi ∈ V: Energiemodell liefert Differenz zwischen Zugriff auf Hauptspeicher und SPM Für moi ∈ F: Energiemodell liefert Differenz ∆eIFetch zwischen Instruction Fetch aus Hauptspeicher und SPM. Profiling des zu optimierenden Programms liefert Anzahl ni,instr ausgeführter Instruktionen für moi. ∆ei = ni,instr * ∆eIFetch.

20


SPM-Allokation: Energiereduktion Funktionen & Globale Variablen (6) ILP-Formulierung: Zielfunktion: Maximiere Energieeinsparung für gesamtes

Programm

Nebenbedingung: Einhaltung der Kapazität des SPMs

[S. Steinke, Untersuchung des Energieeinsparungspotenzials in eingebetteten Systemen durch energieoptimierende Compilertechnik, Dortmund 2002]

21


SPM-Allokation: Energiereduktion Funktionen & Globale Variablen (7) Ergebnisse (MultiSort-Benchmark):

Cyc

les

[x10

0]

Ene

rgy

(CP

U +

Mem

ory)

[µJ]

64b SPM zu klein, um für globale Variablen / Funktio- nen ausgenutzt zu werden.

Bis 1kB SPM stetige Verbesserung von Energie & Laufzeit wg. Einlagerung von mehr MOs in den SPM.

Ab 2kB SPM leichte Ver-schlechterungen, da keine weiteren MOs mehr in SPM eingelagert werden können (alle MOs bereits im SPM enthalten), der Energiever-brauch größerer SPMs aber technologiebedingt ansteigt.

22


SPM-Allokation: Energiereduktion Funktionen & Globale Variablen (8) Nachteile: Verschiebung kompletter Funktionen unter Umständen nachteilig:

Ganze Funktionen haben viel Code und benötigen viel SPM-Platz. Einzelne Code-Teile einer Funktion (z.B. Code außerhalb von Schleifen) werden nur selten ausgeführt, führen daher nur zu ge-ringer Energieeinsparung, werden aber dennoch auf SPM gelegt.

(Knappe) SPM-Kapazität wird nur suboptimal ausgenutzt.

Ziel: Verschiebung des Codes von einzelnen Basisblöcken anstatt von

kompletten Funktionen in den SPM.

23


Basisblock: Eine maximal lange Folge von Assembler-Befehlen, deren Abarbeitung stets beim ersten Befehl beginnt, und die nur über den letzten Befehl verlassen werden kann.

Ist der Sprung am Ende von b bedingt, so hat b zwei Nachfolger

b1 und b2, die ausgeführt werden, wenn der bedingte Sprung entweder genommen wird oder nicht:

b: ... jnz %d_0, b2

b1: ... b2: ...

Eigenschaften von Basisblöcken

24


Eigenschaften von Realzeit-Systemen

Ubiquitäre Systeme oft mit (harten) Zeitschranken Größtmögliche Laufzeit von Programmen muss bekannt sein Worst-Case Execution Time (WCET)

BCETreal WCETreal Tatsächlich

25


Eigenschaften von Realzeit-Systemen

Ubiquitäre Systeme oft mit (harten) Zeitschranken Größtmögliche Laufzeit von Programmen muss bekannt sein Worst-Case Execution Time (WCET)

BCETreal WCETreal

WCETobs

WCETest

Tatsächlich

Beobachtet

26


Eigenschaften von Realzeit-Systemen: Wechsel des kritischen Pfades (1)

main

a

b

c

d

10 Taktzyklen

50 Taktzyklen

80 Taktzyklen

65 Taktzyklen

120 Taktzyklen

27


main

a

b

c

d

Initialer WCEP: main, a, b, c Länge des WCEP: WCETest = 205

Σ = 205 Taktzyklen

10 Taktzyklen

50 Taktzyklen

80 Taktzyklen

65 Taktzyklen

120 Taktzyklen


28


80 Taktzyklen

main

a

b

c

d

10 Taktzyklen

50 Taktzyklen

65 Taktzyklen

120 Taktzyklen

Initialer WCEP: main, a, b, c Länge des WCEP: WCETest = 205

40


Σ = 205 Taktzyklen

29


main

a

b

c

d

Neuer WCEP: main, d, c WCEP Wechsel durch Optimierung!

40 80 Taktzyklen

10 Taktzyklen

50 Taktzyklen

65 Taktzyklen

120 Taktzyklen


Σ = 195 Taktzyklen

30



Speicher oft begrenzender Faktor Einsatz von Speicherhierarchien Häufig benutzte Daten/Code in kleinen schnellen Speichern Optimierung von Speicherzugriffsmustern

CPU

IFB

Haupt- speicher SPM

Cache

31


Statisches Locken von Instruktions-Caches: WCET-Reduktion (1) Cache-Inhalt oft nur schwer vorhersagbar Ungünstiges Speicherlayout führt zu Cache-Misses

32



33



34



35


Statisches Locken von Instruktions-Caches: WCET-Reduktion (1) Cache-Inhalt oft nur schwer vorhersagbar Ungünstiges Speicherlayout führt zu Cache-Misses Starke Überabschätzung der WCET Überdimensionierte Hardware

36


Cache-Inhalt oft nur schwer vorhersagbar Ungünstiges Speicherlayout führt zu Cache-Misses Starke Überabschätzung der WCET Überdimensionierte Hardware

Idee Cache-Inhalte werden fixiert Blöcke können nicht mehr verdrängt werden

X

Statisches Locken von Instruktions-Caches: WCET-Reduktion (1)

37


Vorgehen Auswahl von Basisblöcken für maximale WCETest Redutkion Einfaches Knappsack-Problem nicht ausreichend Wechsel des kritischen Pfades muss beachtet werden Modellierung des Kontrollflusses per ILP


Definitionen Kosten eines Basisblocks bi:

modelliert die WCETest von bi, wenn bi im Hauptspeicher liegt bzw. in Cache gelockt wird

38


A

C B

D

E

Azyklische Teilgraphen: (Reduzierbare) Schleifen:

B

A

C

D

E

Innerster Schleifenkörper in L ist azyklischer Teilgraph

Schleife L falten Kosten von L: Mit der nächsten

umliegenden Schleife fortfahren

[V. Suhendra et al., WCET Centric Data Allocation to Scratchpad Memory, RTSS 2005]

= WCET eines jeden Pfades, der in A startet

Loop L B, C, D


39


ILP-Formulierung (Fortsetzung) Globaler Kontrollfluss (Funktionsaufrufe): modelliert WCET von F Addiere zu jedem Basisblock, der F aufruft

Kosten für Laden + Locken in den Cache:

: Größe Cachezeile [Bytes] : Locking Overhead pro Zeile [Zyklen]


40


ILP-Formulierung (Fortsetzung) Annahme: main ist Programmeinsprung modelliert WCET des Programms Zielfunktion: Reduktion der System Gesamt-WCET

Mapping Basisblöcke auf Cachezeilen nicht betrachtet


41


40%

50%

60%

70%

80%

90%

100%

110%

DSPstone Mediabench misc MRTC UTDSP Average

Rel

ativ

e W

CE

T est

10% Locked 10% Cached

Statisches Locken von Instruktions-Caches: Ergebnisse 4-fach assoziativer Cache – ARM926EJS

100%: WCETest für System ohne Cache

-29,5%

-19,8%

-35,4%

42


40%

50%

60%

70%

80%

90%

100%

110%

DSPstone Mediabench misc MRTC UTDSP Average

Rel

ativ

e W

CE

T est

20% Locked 20% Cached

Statisches Locken von Instruktions-Caches: Ergebnisse 4-fach assoziativer Cache – ARM926EJS

-39,6%

-29,2% -39,5%

-48,2%

100%: WCETest für System ohne Cache [S. Plazar et al., WCET-aware Static Locking of Instruction Caches - CASES’11]

43


Codepostitionierung Instruction Fetch Buffer soll Pipeline Stalls vermeiden Sprungvorhersage versucht, Sprungziel zu bestimmen Programmcode wird vorab geladen Intelligentes Umordnen von Basisblöcken Reduziere Anzahl falsch vorhergesagter Sprünge Reduziere Anzahl unbedingter Sprünge

CPU

IFB

Haupt- speicher SPM

Cache

44


Beispiel Speicherlayout TriCore TC1796: Sprungziel falsch vorhergesagt Führt zu unnötig hoher WCET durch Reihe von Pipeline Stalls

2WS

L3: jlez %d10, L4

L5: mul.f %d8, 7 j L7

L4: add %d8, -1

L7: ...

.code16

p red ict ed

Codepostitionierung (2)

45


L3: jlez %d10, L4

L5: mul.f %d8, 7 j L7

L4: add %d8, -1

L7: ...

.code16

p red ict ed

L3: jgtz %d10, L5

L4: add %d8, -1

L7: ...

.code16

j L7

L5: mul.f %d8, 7

p red ict ed

Beispiel Speicherlayout TriCore TC1796: Sprungziel falsch vorhergesagt Führt zu unnötig hoher WCET durch Reihe von Pipeline Stalls 3 Taktzyklen können eingespart werden

2WS 1WS

2WS

Codepostitionierung (2)

46


Codepostitionierung (3) Ergebnisse

70%

75%

80%

85%

90%

95%

100%

105%EA ILP

Rel

ativ

e W

CE

T est

-6,7%

-20%

-8,9%

-24,7%

Optimierungszeit EA: ø 9 Stunden / max. 6 Tage Optimierungszeit ILP: ø 3 Minuten / max. 39 Minuten

WCETest bei höchster Optimierungsstufe ohne Code Positioning

47


Schnelle Prozessoren ausgebremst durch langsame Speicher Speicher verbrauchen ähnlich viel Energie wie Prozessoren Reduktion des Energieverbrauchs und der Laufzeit von Software

durch Übersetzer

Speicherbasierte Optimierungen Ganzzahlig-lineare Programmierung als Optimierungstechnik Allokation von Code/Daten in SPM erzielt beträchtliche

Energieeinsparungen bereits für kleine SPMs Gelockte Caches ermöglichen WCETest Reduktion verglichen mit

normalem Cache Code-Positionierung erhöht die Effizienz von IFB zur WCETest

Reduktion

Zusammenfassung

48

Documents

Effiziente Ressourcennutzung durch intelligente Übersetzer · © H. Falk, S. Plazar SW ubiquitärer Systeme – Effiziente Ressourcennutzung 2 Gliederung Eigenschaften von heutigen