Description and Specialization of Coarse-grained Reconfigurable ArchitecturesJulio Alexandrino de Oliveira Filho
Description and Specialization of Coarse-grained Reconfigurable Architectures
Julio Alexandrino de Oliveira Filho
Begrüßung Sehr geehrte Prodekanin Professor Landerl (Vorsitz), sehr geehrte Professoren, (Profs. Rosenstiel, Schilling und Hauck), liebe Zuhörer, Ich stelle Ihnen heute meine Promotionsarbeit vor, mit dem Titel „Description and Specialization of Coarse grained Reconfigurable Architectures“. Der Titel ist auf English, sowie an der Dissertation, ich werde Ihnen aber auf Deutsch vortragen. === To discuss: What other information should be included in the title cover ? General Structure: Intro : General motivation , Grundlage Objective of the work State of the art – Problems and existing solutions My solutions CGADL Custom Instructions Results ‹#› 10.02.2010 Non final version
10. Februar 2010
2 Beschreibung grobgranularer Arrays mit CGADL Spezialisierung grobgranularer Arrays durch spezialisierte Befehle Gliederung Ergebnisse Motivation und Grundlagen Stand der Technik
Ich werde zuerst Motivation und Grundlage meiner Arbeit vorstellen, und dann ein Blick in der Stand der Technik. Danach, werde ich in den zwei Hauptthemen meiner Arbeit, die Beschreibung und die Spezialisierung grobgranularer Architekturen, detailiert eingehen. Zum Schluß, werde ich Ergebnisse und Zusammenfassung presentieren. Zuerst einige Wörten zur Motivation und Grundlagen 10.02.2010 Non final version ‹#›
Performanz Niedriger Verbrauch ASIC CPLD FPGA Spezialisierung der Architektur Flexibilität Time-to-Market Standard- prozessoren DSP ASIP Umprogrammierung nach der Herstellung Eingebettete Systeme 10. Februar 2010 3 Grobgranulare rekonfigurierbare Hardware
Eingebettete Rechnersysteme, wie z. B. Mobiltelephone, Videocameras und Navigationsgeräten sind ein Teil unsere Leben. Diese Geräte mussen klein und portabel sein, mussen nach der Herstellung flexibel bleiben, mussen eine geringere Energieverbrauch haben, und trotzdem mussen sie eine hohe Performanz anbienten. All diese teilweise entgegengesetzt Anforderungen machen den Entwurf diesen Geräten schwierig und langsam. Um diese Anforderungen zu bewältigen, haben Entwickler eingebetteter Systemen eine breite Auswahl an Bausteine, die von Allgemeine- und Domäne-spezifische Prozessoren bis hin zu FPGAs und ASICs sich ausbreitet. Diese Auswahlpallete stellt ein Kompromiss dar, zwischen Performanz und Flexibilität, Niedrieger Verlustleistungsverbrauch und Time-to-Market. In die letzte 10 Jahren, ist eine neue Technologie auf die Markt gekommen, die das Beste alle dieser Welt verspricht: die grobgranulare rekonfigurierbare Hardware. UBERGANG : Das Design dieser Bausteine ist das Thema dieser Arbeit. Aber, wie sehen grobgranulare rekonfigurierbare Systemen aus ? Message of this slide : - Motivieren grobgranulare rekonfigurierbare Architekturen Seit einige Jahren, sind Rechnersystemen nicht mehr an Desktop-PCs eingeschränkt, sondern sie sind Teil unsere Alltagsgeräten, sowie mobile Telephones, personal assistants, mikrowelle ovens, automobile, etc... Diese so gennante eingebettete Systemen haben sehr unterschiedliche Anwendungen, und dessen High-End Natur bringt viele Anforde
Grobgranulare rekonfigurierbare Arrays 10. Februar 2010 4 PE PE PE PE PE PE Verbindungsnetzwerk Funktionseinheit Konfigurationsspeicher Registersatz Speicher “Configurable Reconfigurable Core” CRC [Oppold et al. 2005] Beispiele Industrie DRP von NEC ULIW von Silicon Hive XPP von PACT ARRIX von MathStar Universität ADRES von IMEC CRC (Tübingen) WPPA (Erlangen) Morphosys PE PE PE PE PE PE Takt 1 PE PE PE PE PE PE 2 PE PE PE PE PE PE 3
CGRAs besteht in der Regeln aus ein Array von Prozessorelemente, die PEs, die durch eine Verbindungsneztwerk umgegeben und verbunden sind, und Speicher- und Ein/Ausgabekomponenten. Die PEs bestehen jenachdem aus ein oder mehrere Funktionseinheiten, eine Konfigurationsspeichern und lokale Datenspeicher, wie z.B. Registersätze. Hier in Tübingen, wurde diese allgemeine Idee für CGRAs in eine Modell beschrieben, das (1) während der Entwurf konfiguriert werden kann (z.B. In der Anzahl PEs) und (2) während der Ausführung auf neue Funktionalitäten rekonfiguriert werden kann. Dieses Modell ist deswegen CRC Modell gennant. Übergang Weitere Beispiele sind ... Message of this slide : Erklären was sind grobgranulare rekonfigurierbare Architekturen. Vorteile dieser Architekturen CRC Model hier? Die Struktur, oder „die Architektur“ grobgranularer rekonfigurierbarer Bausteine kann sehr gut representiert werden durch das CRC Modell, entwickelt hier an der Universität Tübingen von unsere ehemalige Kollege Tobias Oppold. Dieses Array funktioniert so dass jede PE führt ein Teil der Anwendung aus, und Daten sind über die Verbindungsnetzwerk ausgetauscht. Die funktionalität jeder PE kann mittels der Konfigurationsspeichern rekonfiguriert werden, so dass die Array kann für unterschiedliche Anwendungen umprogrammiert werden. In die modernsten Bausteine, diese Rekonfiguration kann sogar auf jede Taktschritt stattfinden, sodass die Array wird konfiguriert nur auf dieses Teil der
Entwurf grobgranularer Arrays 10. Februar 2010 5 PE PE PE PE PE PE Verbindungsnetzwerk Speicher PE PE PE PE PE PE PE PE PE PE PE PE PE Modell Vorlage Instanz Beschreibung Spezialisierung Beschreibung auf hoher Abstraktionsebene Steigerung der Produktivität in der Entwurfsphase Verringerung der Fläche und Verlustleistung Ziele dieser Arbeit
Der Ausgangspunkt zur Entwicklung eine CGRA ist ein Modell, so wie z.B. das bereit erklärte CRC-Modell. Das Modell wird festgelegt durch der Beschreibung einer Architekturvorlage. Die Vorlage ist eine konkrete Spezifikation wo viele Aspekten, z.B. die interne Struktur der Pes festgesetzt sind. Trotzdem, stehen viele Aspekte einer Vorlage noch flexibel, und konnen an hand von Parametern schnell geändert werden. So z.B. kann eine Vorlage festlegen, dass ein PE ein interne Registersatz hat. Die Menge an Registern in dieser Satz kann aber noch eingestellt werden mittels eine Wertbelegung eines Parameters Die Wertbelegung alle Parameter impliziert eine konkrete Spezifikation, wo alle Aspekten der Architektur festgelegt sind. Wir nennen diese Spezifikation eine Instanz. Eine Instanz kann bewertet, validiert, und synthetisiert (implementiert) werden. Anwendungen konnen auf eine Instanz abbgebildet und simuliert werden. Wir nennen „Spezialisierung“ die Suche nach eine für eine Anwendungsmenge optimale Architekturinstanz. Im diesen Umfeld kann ich die Zielsetzung meiner Arbeit formulieren: Das erstes Ziel meiner Arbeit war die Beschreibung CGRAs auf eine hohe Abstraktionsebene um die Produktivität der Entwurfsphase zu steigern. Auf eine hohere Abstraktionsebene, können aber einige Aspekte des Entwurfs versteckt bleiben. Das zweites Ziel meiner Arbeit war die Entwicklung von Methoden und Tools zur Spezialisierung CGRAs um eine optimale Fläche und Verlustleistungsverbrauch zu
Stand der Technik: Beschreibung 10. Februar 2010 6 Sprache Benutzt von Synthese Simulation Rekonfiguration Koordinaten-system Heterogenität Skalierbarkeit Netzwerk-verbindungen Verilog KressArray CRC VHDL ADRES Morphosys SystemC CRC LISA CoWare Proprietär ULIW (TIM) ADRES (XML) k.A. k.A. k.A. k.A. k.A. MAML WPPAs komplex
Ich habe aktuelle Beschreibungssprachen untersucht, um CGRAs auf hohe Abstraktionsebene zu beschreiben. Diese Tabele zusammenfasst die Ergebnisse diese erste Untersuchung. Hardware- und Systemebeschreibungsprachen, wie Verilog...., sowohl auch Architekturenbeschreibungsprachen, wie ..., sind für Synthese und Simulation geeignet, unterstützen aber nicht die Beschreibung viele spezifische Aspekten CGRAs, wie ... Es gibt Referenzen zum Sprachen die CGRAs beschreiben, wie TIM und ADDRESS. Die sind aber proprietäre und stehen keine Details zur Verfügung. Zuletzt, haben wir eine Extension von der MAML Sprache gefunden, die teilweise diese Aspekten unterstutzen. In aber eine sehr komplexe, teilerweise Mathematische Formulierung. 10.02.2010 Non final version ‹#›
Stand der Technik: Spezialisierung
10. Februar 2010 7 Bewertung Parametrisierung Vorlage Instanz Architektur Leitlinie DRP Einen zentralen Konfigurationskontroller benutzen ADRES Array an VLIW Prozessor koppeln Kim et al. 2005 Kritische Ressourcen teilen Bansal et al. 2003 Mehrere FUs pro PE einbetten Entwurfsraumexploration Entwurfsleitlinien Der Parameterraum ist zu groß! Bewertung dauert zu lang!
Spezialisierung findet am meistens statt durch eine Entwurfsraumexploration. Explain DSE prozess: . Probleme – Mei Kommentiert. Verschiedene Arbeiten versuchen diese DSE umzugehen mit Design Leitlinien. Z.B. Diese sind in der Regel Interessante Arbeiten, mit gute Aussagen, aber nicht allgemein genug UND Sie betrachten nicht, die Anwendungen und konnen nicht systematisch Angewendet werden. 10.02.2010 Non final version ‹#›
Mein Beitrag 10. Februar 2010 8 Beschreibung Problem : Aktuelle Beschreibungsprachen sind nicht geeignet Problem : Entwurfsraumexploration zu aufwändig und Entwurfsleitlinien sind nicht überall effektiv Spezialisierung Lösung: CGADL Eine Beschreibungsprache für grobgranulare rekonfigurierbare Arrays Lösung: Spezialisierte Befehle zur Spezialisierung grobgranularer rekonfigurierbarer Arrays
Small sentences. Message of this slide : Problemen des Designs Beschreibung Spezialisierung Alles als „ Ich werde zeigen dass die aktuelle Beschreibungsarten sind Problematisch „ Ich werde zeigen dass die aktuelle Spezialisierung ist Problematisch 10.02.2010 Non final version ‹#›
10. Februar 2010
9 Beschreibung grobgranularer Arrays mit CGADL Spezialisierung grobgranularer Arrays durch spezialisierte Befehle Ergebnisse
Message of this slide : Schritten für das Design grobgranularer arrays Erklären Begriffe für Beschreibung und Spezialisierung Schritten: Beschreibung des Templates Specializierung als Instanz 10.02.2010 Non final version ‹#›
CGADL untestützt besonders Parametrisierbare Vorlage Rekonfigurierbarkeit Heterogenität und Skalierbarkeit Räumliche Verteilung von PEs Netzwerkverbindungen Coarse-Grained Architecture Description Language - CGADL 10. Februar 2010 10 CGADL ist eine Sprache zur Beschreibung grobgranularer rekonfigurierbarer Architekturen „ CGADL: An Architecture Description Language for Coarse-Grained Reconfigurable Arrays“ – IEEE Transactions in VLSI, Oliveira et al., 2009
CGADL ist eine Sprache zur Beschreibung grob-granularer rekonfigurierbarer Architekturen. Sein Ziel is Ein Context Memory ist ein Element, mit dem der Designer die Rekonfigurierbarkeit des Array modelieren kann. Die Funktinalität einer FU ist von Designer beschrieben. 10.02.2010 Non final version ‹#›
Parametrisierung und Rekonfigurierbarkeit
10. Februar 2010 11
Hier ist ein Teil einer im CGADL beschrieben Spezifikation. Einfach um das Gefühl der Sprache zu geben. Ich kann aber zwei Elementen der Sprache hier im Aufmerksamkeit rufen. Mit CGADL kann der Entwickler leicht Parametern und deren Wertbereich deklarieren, die fast überall in der Beschreibung eingesetzt werden können. CGADL bietet auch Konstrukte, die zur Modelierung der Hardware-Rekonfigurierbarkeit beiträgt, wie z.B. FSM und Konfigurationsspeicher. 10.02.2010 Non final version ‹#›
Heterogenität und Skalierbarkeit 10. Februar 2010 12 a a a a aBlock = [ a a a a ] bBlock = [ b c ] c b cBlock = [ aBlock , bBlock ] a a a a c b ARRAY (width_param,2,bBlock) width_param = 1 c b width_param = 3 c b c b c b oder
In CGADL können Arrays mit einem einfachen Notation sehr schnell und übersichtlich zusammengestellt werden. Teil der Array kann als Blöcke deklariert werden und bereit deklarierten Blöcken können kombiniert werden um neue Arrays zu beschreiben. Die Geometrie des Arrays kann parametrisiert sein und dadurch kann das Array sehr leicht skaliert werden Pe1 in PE. 10.02.2010 Non final version ‹#›
Räumliche Verteilung von PEs und Netzwerkverbindungen 10. Februar 2010 13 PE PE PE PE PE PE PE PE PE 0 1 m 0 1 2 pe(0,1) REL_COORD(-1,0) (2,0:end) RULE { PE IN (1:end–1,1:end-1) (REL_COORD(-1,0)[2], REL_COORD(0,1)[3], REL_COORD(1,0)[0], REL_COORD(0,-1)[1]); } my_Connection_Rule PE PE PE PE PE PE PE PE PE 0 1 3 0 1 2 PE PE PE 2 PE PE PE PE 3 „An Architecture Description Language for Coarse-Grained Reconfigurable Arrays“ – Int. Conf. Hw/Sw Codesign (CODES), Oliveira et al., Austria, 2007
CGADL unterstützt die Beschreibung der räumliche Verteilung der PEs anhand von eine Koordinaten System. Das heißt, PEs können durch absolute, oder relative Koordinaten referenziert werden, und man kann Gruppen von PEs bezeichnen, die in eine Region des Arrays sich befindet. Das ist eine mächtige Werkzeug zur Beschreibung der Netzwerkverbindung. In CGADL, man kann Regionen in eine Array bilden so dass alle PEs innerhalb dieser Region gleichartig Verbunden sind. Die Beschreibung der Netzwerkverbindung entspricht dann eine Verbindungsregeln, die zu alle PEs in eine Region angewendet werden soll. 10.02.2010 Non final version ‹#›
Vergleich mit anderen Beschreibungssprachen Sprache Benutzt von Synthese Simulation Rekonfiguration Koordinaten-system Heterogenität Skalierbarkeit Netzwerk-verbindungen Verilog KressArray CRC VHDL ADRES Morphosys SystemC CRC LISA CoWare Proprietär ULIW (TIM) ADRES (XML) k.A. k.A. k.A. k.A. k.A. MAML WPPAs komplex CGADL Diese Arbeit einfach 10. Februar 2010 14
10.02.2010 Non final version ‹#›
10. Februar 2010
15 Beschreibung grobgranularer Arrays mit CGADL Spezialisierung grobgranularer Arrays durch spezialisierte Befehle Ergebnisse
Übergang zur Spezialisierte Befehle Das Problem mit eine hohere Abstraktionsebene in der Beschreibung ist dass in der Regeln kann das Ergebinsse der Implementierung sich etwa verschlechtern, weil einige Aspekte des Entwurfs von Entwickler abstraiert sind. 10.02.2010 Non final version ‹#›
Anwendungsabbildung
10. Februar 2010 16 Anwendung als Datenflussgraph Trilineare Interpolation (Ray Casting) Beschränkung 1 Sample pro Taktzyklus 28 PEs 12 Stufen (Pipeline) Abbildung Arch1
Um die Spezialisierung CGRAs durch spezialisierte Befehle besser erklären zu können, werfen wir zuerst ein Blick auf wie typischerweise Anwendungen auf diesen Architekturen abgebildet werden. Anwendungen sind durch Datenflußgraphen representiert, wo Knoten stellen Operationen dar, und die Kanten stellen Datenabhängigkeiten dar. Hier ist als Anwendungsbeispiel die Trilineare Interpolation ... 10.02.2010 Non final version ‹#›
Spezialisierte Befehle 10. Februar 2010 17 14 PEs 6 Stufen (Pipeline) 1,36 91,3 Arch2
Die Trilineare Interpolation, sowohl auch viele andere Anwendungen, haben in deren DFG Operationsgruppen, die regelmäßig und in gleiche zusammensetzung auftauchen. Meine Idee war diese Operationsgruppen, oder s.g. Instruktionsmustern, zu benutzen um spezialisierte Befehle zu Entwerfen. Für die Trilineare Interpolation, wenn die angedeutet Instruktionsmustern als spezialisierte Befehle integriert sind, kann man .. Übergang – Wie kann man dann spezialisierte Befehle in dem Entwurf CGRAs berücksichtigen? 10.02.2010 Non final version ‹#›
Entwurf mit spezialisierten Befehlen 10. Februar 2010 18 Architektur Anwendungen DFG aller Anwendungen Spezialisierte Befehle Erkennung Selektion Komposition Datenpfade als Graphen Instruktions-muster CGADL Abschätzung der Fläche CRC Modell Bewertung: Fläche Verlustleistung Performanz Simulation Synthese
Ich habe Methoden, Tools und Algorithmen entwickeln, um Instruktionsmustern aus einer Anwendungsmenge zu Extrairen, d.h. in einer Anwendungsmenge diese Instruktionsmustern zu Erkennen, Selektieren und Komponieren Die Ausgabe dieser Methodologie sind Graphen, die Datenpfaden von spezialiserte Befehle entsprechen. Diese Datenpfaden können von Entwickler im CGADL beschrieben werden. …. Übergang: Ich werde auf jeder dieser Phase, Erkennung, Selektion und Komposition, ins Detail eingehen. 10.02.2010 Non final version ‹#›
Erkennung von Instruktionsmustern 10. Februar 2010 19 Beschränkungen für den Entwurf eines PEs Maximale Latenz Maximale Fläche 2 x Herstellungsbedingt Anzahl Eingabe <= 3 Anzahl Ausgabe <= 2 Zu viele Eingaben! Zu groß ! Dauert zu lange ! Gute Kandidaten
Der erster Schritt Instrukionsmustern zu extraieren ist es, die Instruktionsmustern zu erkennen. Ich habe ein Method entwickelt die geeignete Operationsgruppen in ein DFG erkennt, und zwar mit Berücksichtigung von Beschränkungen, wie … oder … So sind bei dieser Method Instruktionsmustern, die z.B. zu viele Eingaben haben, oder zu groß sind, oder zu lang dauern, eliminiert. Erkennt sind dann nur Instruktionsmustern, die zur realisierbare spezialisierte Befehlen führen kann. Übergang Bereits erkannten Instruktionen mussen noch selektiert werden… 10.02.2010 Non final version ‹#›
Instruktionsmuster Abdeckung 50% 50% 50% oder 50% 100% Selektion 10. Februar 2010 20
Die Selektion definiert welche Instruktionsmuster tatsächlich gebraucht werden, spezialisierte Befehle zu generieren. Instruktionsmustern sind selektiert anhand deren Abdeckung. Die Abdeckung misst der Anteil einer Anwendung die als spezialisierte Befehle ausgeführt werden kann, wenn diese Instruktionsmuster implementiert wird. Zum Beispiel... Ich habe Algorithmen und Methoden entwickelt, um die Abdeckung Instruktionsmuster zu messen, und auch um eine minimale Satz Instruktionsmuster zu selektieren, der eine maximale Abdeckung bietet. 10.02.2010 Non final version ‹#›
Comments