Hochsprachen-Compiler für adaptive Rechensysteme · Spekulation und Pipelining o Bedingung "i

1

V L S I

HochsprachenHochsprachen-Compiler-Compilerffürür

adaptiveadaptive Rechensysteme Rechensysteme

Andreas Koch Nico KasprzykTU Darmstadt TU BraunschweigFG Eingebettete Systeme Abt. Entwurf integrierterund ihre Anwendungen Schaltungen

2

V L S I

Koch / Kasprzyk - TU Darmstadt / TU Braunschweig - DFG SPPRR 04/2005

ÜbersichtÜbersicht

oo EinführungEinführung

oo ForschungsschwerpunkteForschungsschwerpunkte

oo EntwicklungsarbeitenEntwicklungsarbeiten

oo KooperationenKooperationen

oo AusblickAusblick

oo ZusammenfassungZusammenfassung

oo Controller-SyntheseController-Synthese

oo Hardware-PfadselektionHardware-Pfadselektion

oo Bit-orientierte OptimierungBit-orientierte Optimierung

1. Teil: Überblick

2. Teil: Details

3

V L S I


AufgabenstellungAufgabenstellung

oo Plattform:Plattform: Adaptiver Adaptiver Rechner Rechnerm Konventioneller Prozessor CPU

m Rekonfigurierbare Recheneinheit RCU

m Datenaustausch über gemeinsamen Speicher

oo Programmiersprache: CProgrammiersprache: Cm Voller Sprachumfang von „C“

l Einschließlich Zeiger und Bibliotheksaufrufe

oo Ziel: Automatischer CompilerZiel: Automatischer Compilerm Partitioniert automatisch auf CPU und RCU

l Nahtloser Wechsel der Ausführungsart

m Nutzt Rekonfigurierbarkeit aus

4

V L S I


Compiler COMRADECompiler COMRADE

HW-Kernels als CDFG

C code

Datenpfad Synthese• HW-Optimierung• Modulgenerierung

Datenpfad Synthese• HW-Optimierung• Modulgenerierung

Vorplatzierte Netzliste

ModulGeneratorBibliothek

Front-End Compiler• Architektur-unabhängige Optimierung• Dynamisches Profiling• Analyse und Visualisierung• Automatische HW/SW-Partitionierung

Front-End Compiler• Architektur-unabhängige Optimierung• Dynamisches Profiling• Analyse und Visualisierung• Automatische HW/SW-Partitionierung

Place & RouteXilinx Tools

Place & RouteXilinx Tools

FPGA bit stream

SW C CompilerSW C Compiler

SW-Teil+Interfacesals C Code

Runtime Bibl.RTEMS / API

HW-Umgebung„wrapper”

ACE-VHardwareACE-V

Hardware

Controller Synthese• LogikoptimierungController Synthese• Logikoptimierung

FloorplanningFloorplanning

Verilog

5

V L S I


Schwerpunkte 1Schwerpunkte 1

oo Verbesserte HW/SW-Verbesserte HW/SW-PartitionierungPartitionierung ¬¬m Weiterentwickeltes Berechnungsmodell

oo Synthese von dynamischen ControllernSynthese von dynamischen Controllern¬¬m Pipelined, spekulativ mit Berechnungsabbruch

oo RekonfigurationsmanagementRekonfigurationsmanagementm Verschmelzen von Konfigurationen, Scheduling

6

V L S I


Schwerpunkte 2Schwerpunkte 2

oo HW-spezifische OptimierungHW-spezifische Optimierungm Bit-orientierte Verfahren ¬

m Entfalten von Schleifen für maximaleSpezialisierung (ATS)

oo Automatische IP IntegrationAutomatische IP Integrationm Spezifikationssprache für Interface-Synthese

oo Referenzanwendung Referenzanwendung als als BenchmarkBenchmark für Compiler für Compilerm Manuell von C in HW implementiert

7

V L S I


RekonfigurationsmanagementRekonfigurationsmanagement

oo Exzessive Konfigurationszeit aktuellerExzessive Konfigurationszeit aktueller FPGAs FPGAsm Vereiteln oft Beschleunigung mittels RCU

oo Beobachtung und GrößenvergleichBeobachtung und Größenvergleichm Aus C generierte Kernels: ca. 3.000 Zellen

m Mittelgroße Commodity-FPGAs: ca. 17.000 Zellen

oo Idee: Packe mehrereIdee: Packe mehrere Kernels Kernels in eine Konfiguration in eine Konfigurationm Ziel: Minimale Anzahl von Rekonfigurationen

m Vollständige Rekonfigurationl Vermeidet bekannte Probleme bei partiellem Ansatz

8

V L S I


Vorgehen 1Vorgehen 1

oo VorgehenVorgehenm Trivial

l Alle Kernels passen in eine Konfiguration

m Komplizierterl Aufteilen auf mehrere Konfigurationen

l Möglicherweise auch überlappend

oo AusgangsdatenAusgangsdatenm Dynamischer Kernel-Ausführungs-Trace

m Statische Programmstruktur

m Größen der HW-Kernels, Platz auf dem FPGA

èèZwei Verfahren realisiertZwei Verfahren realisiertm Enge Kooperation mit van der Veen/Fekete

9

V L S I


Vorgehen 2Vorgehen 2oo Optimale LösungOptimale Lösung

m Dynamische Programmierung

m Wertet Trace auf ganzer Länge aus

m Laufzeit: 0,5...2s, in Extremfällen 10...90s

oo HeuristikHeuristikm Clustering-basierter Ansatz

m Analysiert statische Programmstrukturl Mögliche Transitionen zwischen Kernels in CFG

l Unabhängig von Ausführungslänge

m Laufzeit: maximal 0,3s

m In der Regel ca. 20% schlechter als Optimum

oo Ergebnis bei nicht-trivialen ProblemenErgebnis bei nicht-trivialen Problemenm Bei realen Beispielen bis zu 99.99% Reduktion

Eingereicht zur FPL‘05

10

V L S I


FloorplanningFloorplanning

oo BerechneteBerechnete Kernel Kernel in Konfigurationen packen in Konfigurationen packen

oo Layout-SchemaLayout-Schemam Regulär via RLOC für Datenpfade (Anreihung, MSB-LSB)

m Platzierungsregionen für Controller

oo Synthetisiert MuxeSynthetisiert Muxe zum/vom System-Interface zum/vom System-Interface

Interface- CPU- Speicher (MARC)

Kernel-InterfaceMuxe

Datenpfade

Controller

11

V L S I


BenchmarkBenchmark für Compiler für Compileroo WaveletWavelet-Bildkompression in C-Bildkompression in C

m Honeywell ACS BenchmarkSuite: versatility

oo ReferenzimplementierungReferenzimplementierung in in Verilog Verilogm 6241 Virtex Slices, 9 BlockRAMs

oo Aufnahme inAufnahme in ReCoLib ReCoLib geplant geplant

ACE-V RCU33 MHz

6.6ms1.1 W

18.9ms

SunUltraSPARC

III+900 MHz

52.0 W

6.7ms

24.0ms

256x256

512x512

Wavelet Transform

Quantisierung/Huffman/RLE

Ausführungszeit Leistungsaufnahme

12

V L S I


EntwicklungsarbeitenEntwicklungsarbeiten

oo Umgebung zur SystemsimulationUmgebung zur Systemsimulationm Interaktion CPU-RCU-Speicher

m Automatische Regressionstests

oo Integration von LogiksyntheseIntegration von Logiksynthesem Zunächst: UCB SIS

m Danach: UCLA RASP Erweiterungen

oo Erweiterte Basis für ModulgeneratorenErweiterte Basis für Modulgeneratorenm Charakterisierung aus Java-Beschreibungen (JHDL)

l Timing und Topologie

oo Migration von bestehender ACE-V PlattformMigration von bestehender ACE-V Plattformm Benutzung der ADM-XRC direkt aus Linux-PC

m Inbetriebnahme von ADM-XP V2pro Plattform

13

V L S I


VeröffentlichungenVeröffentlichungen

oo GädkeGädke H., Koch A. H., Koch A.WaveletWavelet--basedbased Image Image Compression on the Reconfigurable Compression on the Reconfigurable Computer ACE-V Computer ACE-VIntlIntl.. Conf Conf.. On Field On Field--Programmable LogicProgrammable Logic (FPL), (FPL), Antwerpen Antwerpen, 09-04, 09-04

oo Lange H., Koch A.Lange H., Koch A.Hardware/Software-Hardware/Software-Codesign by AutomaticCodesign by Automatic Embedding Embedding of Complex of Complex IP IP Cores CoresIntlIntl.. Conf Conf.. On Field On Field--Programmable LogicProgrammable Logic (FPL), (FPL), Antwerpen Antwerpen, 09-04, 09-04

oo Rock M., Koch A.Rock M., Koch A.ArchitectureArchitecture--Independent MetaIndependent Meta--Optimization byOptimization by Aggressive Aggressive Tail Tail Splitting SplittingConference onConference on High-Performance Computer High-Performance Computer Architecture Architecture (HPCA), (HPCA), Pisa Pisa, 08-04, 08-04

oo KasprzykKasprzyk N., Koch A. N., Koch A.Verbesserte Hardware-Software-Verbesserte Hardware-Software-PartitionierungPartitionierung für für Adaptive Adaptive Computer ComputerArchitecture ofArchitecture of Computing Systems (ARCS): Workshop Computing Systems (ARCS): Workshop on Dynamically on DynamicallyReconfigurableReconfigurable Systems, Augsburg, 03-04 Systems, Augsburg, 03-04

oo KasprzykKasprzyk N., N., van van der der Veen Veen J.C., Koch A. J.C., Koch A.Configuration Merging for AdaptiveConfiguration Merging for Adaptive Computer Computer Applications ApplicationsIntlIntl.. Conf Conf.. On Field On Field--Programmable LogicProgrammable Logic (FPL), (FPL), Tampere Tampere, 08-05, 08-05

14

V L S I


SPPRR KooperationenSPPRR Kooperationen

oo Uni Tübingen (Uni Tübingen (OppoldOppold/Rosenstiel)/Rosenstiel)m Configurable Reconfigurable Core (CRC)

Abstrahierte Speicherschnittstellen

oo TU Braunschweig (TU Braunschweig (vanvan der der Veen Veen//FeketeFekete))m ReCoNodes

Rekonfigurationsmanagement

m ReCoLibBenchmark und Referenzimplementierung

15

V L S I


Nächste ProjektphaseNächste Projektphase

oo Back-Back-EndEnd Tools Toolsm Floorplanning

m Intelligentere Modulbibliothek

oo Integration/Ausnutzung von TeilsystemenIntegration/Ausnutzung von Teilsystemenm Schleifenoptimierung

l OMEGA, Stensgaard Pointer Analyse

l Aggressive Tail Splitting

m IP Block Interface Synthese

èè Untersuche Interaktion der VerfahrenUntersuche Interaktion der Verfahrenm Damit gezielte Optimierungsschritte

oo Entwicklung: Engere CPU-RCU IntegrationEntwicklung: Engere CPU-RCU Integrationm SoC-Ansatz auf V2pro-basierter Plattform

m Speicher-Interface MARC im SoC-Kontext

16

V L S I


ZusammenfassungZusammenfassung

oo Kern-CompilerKern-Compilerm Macht gute Fortschritte

m Kompletter Fluss in Simulation

oo Erste Ergebnisse leiten weitere ForschungErste Ergebnisse leiten weitere Forschungm Beispiel: Analysen der Kernel-Größen

l Rekonfigurationsmanagement

oo ForschungsrichtungForschungsrichtungm Bessere Back-End Tools erforderlich

l Aggressive Tail Splitting

l Bitbreitenreduktion

17

V L S I

Technische DetailsTechnische Details

18

V L S I


Hardware-AuswahlHardware-Auswahl

S1

S2

S3

H1

H2

H3

S1

S2

S3

H1

H2

H3

1

2

3

S1

S2

S3

H1

H2

H3

oo Pfadbasierte Auswahl Pfadbasierte Auswahl in in drei Schrittendrei Schritten

ÊÊ SchleifenduplikationSchleifenduplikationm Erzeugt HW-Kandidaten und SW-Teil

ËË Pfadselektion Pfadselektion im im CFGCFGm Basiert unter anderem auf

l Ausführungshäufigkeit

l HW-Charakteristika

l HW-SW Kommunikationsaufwand

m Isoliert SW-Regionen aus HW-Kandidaten

ÌÌ HW-HW-EntscheidungEntscheidungm Basiert auf geschätztem Speed-Up Faktor

m Erzeugt tatsächliche HW-Kernel

19

V L S I


ÊÊ DuplikationDuplikation von Regionen von RegionenS1

S2

S3

H1

H2

H3

(1) (2)

A

VZ1

VZ2

B A' B' A B'' B

oo Erzeugung von HW-Kandidaten im CFGErzeugung von HW-Kandidaten im CFG

oo DuplikationDuplikation von relevanten Regionen von relevanten Regionenm In HW und SW

oo Relevante SchleifenRelevante Schleifenm Häufig verwendet

m Auch geschachtelt

oo FunktionsaufrufeFunktionsaufrufem Problematisch

m Abhilfe: Inliningl Profile-basiert

20

V L S I


S1

S2

S3

H1

H2

H3

ËË PfadselektionPfadselektion

SW HW

oo Kernalgorithmus istKernalgorithmus istm Iterativ

m Konstruktiv

oo Beachtet Anforderungen an CFG-BlöckeBeachtet Anforderungen an CFG-Blöckem Dürfen nur in HW ausführbare Operationen

enthalten

oo Aufbau von PfadenAufbau von Pfadenm Verbinde zunächst Eintritt mit Austritt

m Bevorzuge dann Pfade mit hoherAusführungsanzahl

oo ErgebnisErgebnism HW-Pfade bilden zusammen HW-Kandidat

m Verbliebene werden zu SW-Subregionen

21

V L S I


ÌÌ Behandele SW-Behandele SW-SubregionenSubregionen

SW HW

SW

SWa1=b1

c5=a7

S1

S2

S3

H1

H2

H3oo BerechnungsmodellBerechnungsmodell

m CPU und RCU sind gegenseitigeDienstleister

m Gleichen füreinander Schwächen aus

oo Also: SW-Also: SW-SubregionenSubregionenm Aus HW-Kandidat isolieren

m Auf CPU verlagern

oo DatenabhängigkeitenDatenabhängigkeitenzwischenzwischenm HW-Kandidaten

m SW-Subregionen

22

V L S I


Verschiebe SW-Verschiebe SW-SubregionenSubregionen

SW HW

SW

SWa1=b1

c5=a7

S1

S2

S3

H1

H2

H3oo Erweitere Erweitere SW-SW-Teil der AnwendungTeil der Anwendung

m Um Anweisungen aus SW-Subregionen

m Aus HW-Kandidaten “aufrufbar”

oo DatenabhängigkeitenDatenabhängigkeitenm Bedingen Kommunikation

zwischen CPU und RCU

oo ProblemProblemm Bei hohem Datenaufkommen

m Zu viel Kommunikationszeit

23

V L S I


KommunikationsaufwandKommunikationsaufwand

oo Art Art der der SW-SW-SubregionenSubregionenm Pfade passen nicht mehr auf RCU

m System- und Bibliotheksfunktionen (nicht inline-bar)

m HW-ungeeignete Operationen (z.B. derzeit noch Fliesskomma)

oo Untersuchung über Untersuchung über allealle möglichen möglichen HW-HW-KandidatenKandidatenm Größere Kernels haben oft weniger HW/SW Kommunikation

m Bei Selektion von Kernels aus Kandidaten beachtenl Stark von CPU-RCU-Kopplung abhängig

Benchmark XC4000 mit 1333 CLBs Virtex mit 5120 CLBsVariablen Transfers Variablen Transfers

versatility 25 6.588.800 67 15.344.861adpcm 16 101.320 0 0capacity 15 31.602 19 41.924des 53 53.560 12 5.304pegwit 38 3.169.887 0 0

24

V L S I


Effekt der KandidatenauswahlEffekt der Kandidatenauswahl

0%

20%

40%

60%

80%

100%

versatility

adpcmcapacity

despegwit

Anteil von in HW ausgeführten Instruktionen

all 1333kernel 1333all 5120kernel 5120

oo Basismaß für jedes ProgrammBasismaß für jedes Programmm Gesamtanzahl ausgeführter Instruktionen

oo Ein Qualitätsmaß für Ein Qualitätsmaß für Kernel-Kernel-SelektionSelektionm Wieviel davon hinterher auf HW ausgelagert?

oo VergleicheVergleichem all: Über alle HW-Kandidatenm kernels: Nur tatsächlich ausgewählte Kernels

25

V L S I


Controller-Controller-Synthese Synthese 11

oo DynamischesDynamisches Scheduling Scheduling der HW-Operatoren der HW-Operatoren

oo Spekulativ mit BerechnungsabbruchSpekulativ mit Berechnungsabbruchm Macht fehlspekulierte Pipeline-Zweige für neue Daten frei

oo Modell: Erweitertes Modell: Erweitertes PetriPetri-Netz-Netzm Up-Token

l Traditioneller Datenfluss

l Bewegung in Datenflussrichtung

m Down-Tokenl Steuert Berechnungsabbruch

l Entgegengesetzte Bewegung

l Löscht Up-Token aus

26

V L S I


Controller-Synthese 2Controller-Synthese 2oo Lokale Abhängigkeiten der HW-OperatorenLokale Abhängigkeiten der HW-Operatoren

m Gesetzte Daten-Up-Tokens der Vorgänger

m Freie Plätze im Nachfolger

m Kontroll-Down-Tokens der Nachfolger

oo HW-Operatoren mit variabler HW-Operatoren mit variabler LatenzLatenz

m Tokens wandern über Kontrollsignalel START

l DONE

l CANCEL Op

CLEAR

DONE

STARTUp

Up

Dn

27

V L S I


read(S) read(i)

mux

+

mux

write(S)

+1<100

C

SpekulationSpekulation und Pipelining und Pipelining

oo Beispiel für i=2Beispiel für i=2m Grüne Pfeile sind Vergangenheit

oo Up-Up-TokenToken wird erzeugt wird erzeugtm Wenn alle Vorgänger aktiv

m Ausnahme: Multiplexer

m Multiplexer für i und S aktiviert auf rechten Eingang

oo EinfacheEinfache Datenfluss Datenfluss-Vorwärtsbewegung vollzogen-Vorwärtsbewegung vollzogen

int S=0;for(i=1;i<100;i++) S+=i;printf( “%d“, S );

28

V L S I


read(S) read(i)

mux

+

mux

write(S)

+1<100

C


oo Bedingung "i<100" ist TRUEBedingung "i<100" ist TRUEm Operationen in Schleife sind noch einmal auszuführen

m Berechnung von S noch nicht beendetl Down-Token unterbindet Write

29

V L S I


read(S) read(i)

mux

+

mux

write(S)

+1<100

C


oo „+“ und „+1“ ausführbar„+“ und „+1“ ausführbarm Up-Token aller Vorgänger sind aktiv

oo Down-Down-TokenToken pflanzt sich von Controller in DFG fort pflanzt sich von Controller in DFG fort

oo writewrite(S)(S)m Könnte ausgeführt werden, da Vorgänger aktiv

m Aber ...

30

V L S I


read(S) read(i)

mux

+

mux

write(S)

+1<100

C


oo Daten-Up-Daten-Up-Token Token trifft auf Down-trifft auf Down-TokenTokenm Up-Token wird ausgelöscht

m write(S) wird nicht ausgeführt

oo „i“-Multiplexer übernimmt neuen Wert„i“-Multiplexer übernimmt neuen Wertm Könnte nächste Iteration in kompliziertere Pipeline beginnen

oo i zur Berechnung von S verwendeti zur Berechnung von S verwendetm In alter Iteration

31

V L S I


Controller-Controller-KomplexitätKomplexität

0

50

100

150

200

250

ri.11bq.70

bRe.46

bRe.34

ee.40ee.31

ee.19h.12

f22.28

f22.21

f22.14

versatility

#HW-Modules #Register

0102030405060708090

100

gI.52gI.44gA

.51gR

.23gM

.86gM

.59gSD

.38gA

M.64

gAM

.52gA

M.39

pegwit

oo Für jede Abhängigkeit (Daten,Für jede Abhängigkeit (Daten, Kontroll Kontroll, Speicher), Speicher)m Kante im CDFG

m Zwei Register (Up, Down) Ù max. n * (n-1) Register

oo Aber in realen ProgrammenAber in realen Programmenm CDFG ist kein vollständiger Graph Ù vertretbarer Aufwand

32

V L S I


Bit-Bit-orientierte Optimierungorientierte Optimierung

oo Bit-Bit-BreitenreduktionBreitenreduktionm Verkleinerung der HW-Module, weniger Verdrahtung

oo Ausnutzung von Konstanten auf Bit-EbeneAusnutzung von Konstanten auf Bit-Ebenem Kleine und potentiell schnellere HW-Module

l Aufgebrochene Carry-Chains etc.

oo ErlaubtErlaubtm Kleinere RCU-Fläche oder größerer HW-Instruktionsanteil

Klassifizierung der Bits

0%10%20%30%40%50%60%70%80%90%

100%

versatility adpcm capacity des pegwit

ignoriertkonstantverändert

33

V L S I


ParallelisierungParallelisierung

oo Benötigt unterschiedliche Benötigt unterschiedliche Analyse-Analyse-VerfahrenVerfahren, z.B., z.B.m Pointer-Aliasing (Steensgard)

m Feldzugriffe (OMEGA)

oo In COMRADEIn COMRADEm Analyseinfrastruktur existiert

m Wird aber erst rudimentär für Optimierungen ausgenutzt

oo Beispiel für Beispiel für OMEGA in COMRADE:OMEGA in COMRADE: Scalarization Scalarizationm Ersetze serielle Speicherzugriffe durch parallele Register

m Einsparung bei Versatilityl 40% der Lesezugriffe

l 1% der Schreibzugriffe

oo GrundlageGrundlage fürfür SchleifenoptimierungenSchleifenoptimierungenm Echte parallele Ausführung innerhalb von HW-Kernels

m Ersetze einzelne Speicherzugriffe durch Strided Streams

34

V L S I


Vielen Dank für IhreVielen Dank für IhreAufmerksamkeit!Aufmerksamkeit!

Documents

Hochsprachen-Compiler für adaptive Rechensysteme · Spekulation und Pipelining o Bedingung "i