Optimales Gatewaydesign mit genetischem Algorithmus und ganzzahliger linearer Programmierung


Doktorarbeit / Dissertation, 2008

136 Seiten, Note: sehr gut


Leseprobe

Inhaltsverzeichnis

1 Einleitung
1.1 Motivation
1.2 Schwerpunkt der Arbeit
1.3 Gliederung der Arbeit

2 Stand der Technik
2.1 Vernetzungstopologie
2.2 Gatewayfunktionalität
2.3 Gatewaydesign
2.4 Zusammenfassung und Trend

3 Gateway-Systemsynthese
3.1 FPGA-basiertes Gateway
3.1.1 Softwarelösung
3.1.2 Hardwarelösung
3.1.3 Heterogenes Design
3.2 Grundlagen der Entwurfsrepräsentation und Entwurfsmethodik
3.2.1 Entwurfsrepräsentation
3.2.2 Synthese und Analyse
3.2.3 Entwurfsmethodik
3.3 Modell zur Gateway-Systemsynthese
3.3.1 Einschränkung der Abstraktionsebenen
3.3.2 Entwurf auf Systemebene
3.4 Der Gateway-Systemgraph
3.4.1 Definitionen
3.4.2 Gateway-Funktionsgraph
3.4.3 Gateway-Architekturgraph
3.4.4 Gateway-Systemgraph
3.5 Gewichtung der Mappingkanten
3.5.1 Gewichtung von Funktionsblöcken
3.5.2 Gewichtung von Mikroprozessor IP-Cores
3.5.3 Softwaresynthese
3.6 Zusammenfassung

4 Optimales Gatewaydesign
4.1 Definitionen
4.2 Das Partitionierungsproblem
4.3 Partitionierungsalgorithmen
4.4 Mehrzieloptimierung
4.5 Optimierung des Gateway-Systemgraphen mit GA
4.5.1 EA-Struktur und Varianten
4.5.2 GA zur Systemoptimierung
4.5.3 Kodierung, Ablauf und Fitness
4.5.4 Parameter des GAs
4.5.5 Exploration des Entwurfsraums
4.5.6 Programmierung
4.6 Optimierung des Gateway-Systemgraphen mit ILP
4.6.1 Das Flussmodell
4.6.2 Aufstellung des Gleichungssystems
4.6.3 Lösung des Gleichungssystems
4.6.4 Exploration des Entwurfsraums
4.6.5 Programmierung
4.7 Kombination GA und ILP
4.8 Performanceanalyse GA vs ILP
4.8.1 Vorbereitung der Messungen
4.8.2 Ergebnis und Diskussion der Messungen
4.9 Neue Verfahren
4.9.1 Multi-Level-Verfahren
4.9.2 Particle Swarm Optimization (PSO)
4.10 Zusammenfassung

5 CAN to CAN automotive Gateway
5.1 Aufgabenstellung
5.2 Design des Systemgraphen
5.2.1 Beschreiben des Systemverhaltens
5.2.2 Festlegung der Architektur
5.2.3 Abbilden des Systemverhaltens
5.3 Optimierung und Exploration mittels GA
5.3.1 Darstellung der Eingangsdaten
5.3.2 Ausgabe und Einschränkung des Entwurfsraums
5.4 Optimierung und Exploration mittels ILP
5.4.1 Erstellen des Flussgraphen
5.4.2 Aufstellen des Gleichungssystems
5.4.3 Lösung des Gleichungssystems und Exploration
5.5 Interpretation der Ergebnisse
5.5.1 Lösung GA
5.5.2 Lösung ILP
5.6 Weitere Verfeinerung des Designs
5.7 Umsetzung
5.7.1 Versuchsaufbau
5.7.2 Umsetzung und Test des Designs
5.7.3 Die Gatewaykonfiguration
5.8 Zusammenfassung

6 Zusammenfassung und Ausblick
6.1 Zusammenfassung
6.2 Ausblick

A Messungen zu Kapitel
A.1 GA-Performance
A.2 ILP-Performance

B Ergebnisse GA Kapitel

C Virtex-II Entwicklungsboard

D FPGA-Floorplan

E TOP-VHDL-Datei

Veröffentlichungen und Patente

Abbildungsverzeichnis

Tabellenverzeichnis

Literaturverzeichnis

Danksagung

Ganz besonders möchte ich mich bei meinem Doktorvater und Erstgutachter Herrn Prof. Dr. Hans Peter Großmann für die hochschulseitige Betreuung bedanken.

Mein aufrichtiger Dank gilt ebenso Herrn PD Dr. Günter Stöhr für die freundliche Übernahme des Korreferats und für die vielen wertvollen Diskussionen.

Für die studentische Unterstützung während dieser Arbeit danke ich den Herren Frank Lex, Kai Hildebrandt und Yi Luo.

Meinen Vorgesetzten Frau Anke Kleinschmit und Herrn Hartmut Kolb danke ich für die Bereitstellung einer angenehmen und einzigartigen Arbeitsatmosphäre.

Nicht zuletzt möchte ich mich bei meiner Frau Sarah und meiner Tochter Zoi Anastasia für die Motivation und für das Verständnis während der Entstehung dieser Arbeit bedan- ken.

Kapitel 1 Einleitung

1.1 Motivation

Abbildung 1.1 zeigt eine Vernetzungstopologie mehrerer Bussysteme. Um Nachrichten zwischen den einzelnen Bussystemen austauschen zu können, müssen die Haupteinhei- ten E1- E3 eine Gatewayfunktionalität besitzen. Wie realisiert man eine Gatewayfunk- tionalität und wie sieht die Hard- und Software eines Gateways aus? Diese Frage stellt sich heutzutage jeder Steuergeräteentwickler in der Automobilbranche, da aufgrund des immer größeren Botschaftsaufkommens die Prozessoren in den Steuergeräten am Limit arbeiten.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 1.1: Vernetzung von Bussystemen

Diese Arbeit entstand während meiner Tätigkeit als Doktorand in dem Forschungsteam ’Steuergerätekonzepte und Applikation’ der DAIMLERCHRYSLER AG mit dem Ziel, ein optimales automotive Gateway für Motorsteuergeräte zu entwickeln. Die Motivation hierbei liegt in dem Design der Gatewayarchitektur mit einer optimalen hardware- und softwareseitigen Verteilung der Funktionalität.

1.2 Schwerpunkt der Arbeit

Der Schwerpunkt dieser Arbeit liegt in dem optimalen Design eines Gateways für FPGAs (engl. Field Programmable Gate Arrays). Dazu werden verschiedene Realisierungsalter- nativen aufgezeigt und eine neue, auf kombinatorischen Algorithmen basierende Me- thode vorgestellt. Durch Anwendung der entwickelten Methodik wird das Problem des Hardware/Software-CoDesigns gelöst und eine optimale Gatewaystruktur für das jewei- lige System erstellt. Grundlage dafür bildet ein Modell zur Gatewaysynthese auf Sys- temebene, welches auf einem bipartiten Graphen beruht. Eine Kombination aus evoluti- onärem/genetischem Algorithmus (GA) und ganzzahliger linearer Programmierung (engl. integer linear programming, ILP) optimiert diesen Graphen. Diese Algorithmenkombina- tion ermöglicht die Bestimmung einer optimalen Gatewayarchitektur mit optimaler Hard- und Softwareverteilung. Die korrekte Anwendung des Verfahrens auf unterschiedliche Problemstellungen, Problemgrößen und Anzahl an Optimierungskriterien sowie eine Per- formanceanalyse der einzelnen Algorithmen und die Anwendung auf eine reale Problem- stellung runden diese Dissertation ab. Wie anfangs erwähnt ist die Methodik auf den Ein- satz von FPGAs ausgelegt. Sie lässt sich jedoch auf Gateways jeglicher Bussysteme an- wenden. Grundkenntnisse bei der Anwendung von FPGAs, beim Entwurf von eingebet- teten Systemen, zur Graphentheorie und zu den Optimierungsverfahren werden hierbei vorausgesetzt.

1.3 Gliederung der Arbeit

Kapitel 2 ”Stand der Technik” geht auf aktuelle Vernetzungstopologien im Fahrzeug ein. Die steigende Komplexität von automotive Vernetzungen und die Integration mehrerer unterschiedlicher Bussysteme ins Fahrzeug erfordern immer mehr den Einsatz von Gateways mit erweitertem Funktionsumfang. Dieser wird in Kapitel 2 für ein Gateway eines Motorsteuergerätes definiert. Eine kurze Exkursion in die Hardware von Motorsteuergeräten und eine Trendanalyse beenden das Kapitel.

Die ”Gateway Systemsynthese” in Kapitel 3 befasst sich mit der Synthese auf Systeme- bene. Für dieses heutzutage wenig erforschte Gebiet wird eine graphenbasierte Methodik eingeführt, welche es ermöglicht, das Gatewayverhalten auf Systemebene in einem bipar- titen Graphen darzustellen. Die Grundlagen für diese Methodik werden anfangs erläutert. Sie befassen sich mit den unterschiedlichen Designmöglichkeiten für Gateways in FPGAs sowie der Theorie der Entwurfsraumrepräsentation und Entwurfsmethodik.

Kapitel 4 ”Optimales Gatewaydesign” widmet sich der Optimierung der graphenbasier- ten Darstellung des Systems. Die Komplexität des Optimierungsproblems ist NP-voll- ständig und daher nicht in deterministischer Zeit zu berechnen. Diese Problematik wird anhand eines Partitionierungsproblems dargestellt, gefolgt von der Vorstellung zugehöri- ger Partitionierungsalgorithmen. Zur Lösung des Partitionierungsproblems für das Gate- way wird eine neue Methodik bestehend aus der Kombination aus genetischem Algorith- mus und ganzzahliger linearer Programmierung vorgestellt, sowie ein Verfahren zur mehr- dimensionalen Entwurfsraumexploration mit klassischen Einzieloptimierungsverfahren. Die Algorithmen und deren Umsetzung sind im Detail erläutert. Eine Performanceanaly- se der einzelnen Verfahren und die Vorstellung neuer mathematischer Mehrzieloptimie- rungsverfahren schließen das Kapitel ab.

Die Anwendung des erarbeiteten Verfahrens wird in Kapitel 5 ”CAN to CAN automo- tive Gateway” anhand einer realen Problemstellung vorgestellt. Dabei soll ein FPGA- basiertes Gateway für ein Motorsteuergerät der Mercedes Benz S-Klasse entwickelt wer- den. Die in Kapitel 3 eingeführte Methodik zum Erstellen des Systemgraphen und das in Kapitel 4 vorgestellte Verfahren zur Exploration des Entwurfsraums und Bestimmung der optimalen Lösung finden hierbei ihren Einsatz. Die Implementierung des optimalen Gateways erfolgt auf einer Entwicklungsplattform mit einem Xilinx Virtex-II FPGA.

Kapitel 2 Stand der Technik

2.1 Vernetzungstopologie

Der Trend zu mehr Elektronik im Fahrzeug hält nach wie vor ununterbrochen an. Die im- mer größer werdende Komplexität der Systeme tendiert zu einer Verteilung dieser Kom- plexität auf mehrere Steuergeräte. Diese Entwicklung wird sich in Zukunft beschleunigt fortsetzen. Betrachtet man ein typisches Auto der Oberklasse mit seinen wesentlichen Steuergeräten, erkennt man eine Busstruktur, welche in unterschiedliche Funktionsberei- che unterteilt ist. Jeder Bereich verfügt über sein eigenes Netz mit der geeigneten Bustech- nologie. Die Netze sind über ein oder mehrere Gateways miteinander verbunden, sodass essentielle Daten in allen Bereichen zur Verfügung stehen. Heute werden teils über 70 Steuergeräte und bis zu sechs unterschiedliche Bussysteme in Premiumfahrzeugen ver- baut. Bild 2.1 zeigt eine typische Steuergeräte-Architektur eines Oberklassenfahrzeugs, wobei die Anordnung der einzelnen Gateways sowie die Art und Anzahl der Bussysteme je nach Automobilhersteller und Fahrzeugtyp variiert.

Das von Bosch und Intel 1981 entwickelte CAN (engl. Controller Area Network) hat sich mittlerweile als weltweites Standard-Bussystem im Antriebsstrang, Fahrwerk und Innenraum durchgesetzt, wobei das LIN (engl. Local Interconnect Network) immer mehr zur Kommunikation von intelligenten Sensoren und Aktoren eingesetzt wird. Das CAN- Datenbussytem ist bis zu einer Datenübertragungsrate von 1 Mbit/s spezifiziert, jedoch aufgrund fahrzeugtypischer Randbedingungen momentan auf 500 kbit/s begrenzt. Der LIN-Bus arbeitet mit einer maximalen Bandbreite von 19,6 kbit. Für hohe Bandbreiten in multimedialen Anwendungen (bis 25 Mbit/s) findet der 1998 von der MOST Co- operation entwickelte MOST-Bus (engl. Media Oriented System Transport-Bus) seinen Einsatz. Ebenfalls erwähnen sollte man das zukunftsorientierte echtzeitfähige Bussystem FlexRay (10 Mbit/s) für X-by-Wire-Systeme. Es soll zukünftig die neuen Anforderun- gen im Kraftfahrzeug hinsichtlich Echtzeit, Fehlertoleranz, Flexibilität und Skalierbarkeit erfüllen. Das Aufzeigen aller existierenden Bussysteme und Protokolle würde den Rah- men an dieser Stelle sprengen. Für eine detaillierte Beschreibung der genannten Bussys- teme sei auf[1]bis[5]verwiesen.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.1: Vernetzung im Fahrzeug

Für die Art der Vernetzung mit Gateways gibt es zwei grundlegende Einsatzvarianten. Die eine ist der Einsatz eines Gateways als sogenanntes zentrales Gateway. Hier werden die vorhanden Bussysteme im Fahrzeug über ein einziges zentrales Gateway miteinander verbunden. Dieser Ansatz wird aufgrund seiner vielen Nachteile hinsichtlich Hard- und Softwareanforderungen, Preis/Leistung sowie Fehlerausbreitung und Testbarkeit eher sel- ten verwendet. Bei der zweiten Variante spricht man von einer Backbone-Architektur. Da- bei übernehmen einzelne lokale Gateways, welche über einen Backbone-Bus miteinander verbunden sind, die Protokollumsetzung. Dieser dezentrale Ansatz ermöglicht eine modu- lare Vernetzung und bietet daher einen entscheidenden Kosten- und Konstruktionsvorteil bei der vorhandenen Variantenvielfalt. In heutigen Fahrzeugen der Oberklasse werden oft Hybrid-Vernetzungen beider Alternativen gebildet und komplette Gateways direkt in Steuergeräte, wie zum Beispiel in das Motorsteuergerät, integriert.

2.2 Gatewayfunktionalität

Die eher spärliche Literatur über Gateways und ihre Funktionalität beschreibt sie meis- tens allgemein als Protokollwandler. Im Rahmen einer Neustrukturierung der Vernet- zung in den neuen Fahrzeuggenerationen wird sich der Funktionalitätsumfang der Ga- teways enorm erweitern. Dazu wird an dieser Stelle das Gateway eines aktuellen Mo- torsteuergerätes betrachtet und dessen Aufgaben definiert. Es übernimmt Funktionen wie Botschafts- und Signalrouting, Signalextraktion, Protokollwandlung, Diagnose und Netz- werkmanagement.

Definition 2.1 (Botschaftsrouting) Unter Botschaftsrouting versteht man das direkte Umkopieren einer Botschaft zwischen zwei oder mehreren Bussystemen. Hierbei kann bei nachrichtenorientierten Bussystemen die Botschaftsidentifikation wahlweise beibehalten oder modifiziert werden.

Definition 2.2 (Signalrouting) Beim Signalrouting werden aus einer oder mehreren Nachrichten aus einem oder verschiedenen Bussystemen einzelne Signalinformationen extrahiert, in eine neue Nachricht verpackt und auf ein oder mehrere Bussysteme gerou- tet. Ein Signal kann dabei je nach abzubildendem Range aus einem oder mehreren Bits bestehen.

Definition 2.3 (Signalextraktion) Bei der Signalextraktion werden wie beim Signalrouting Signalinformationen aus einer oder mehreren Nachrichten aus einem oder verschiedenen Bussystemen extrahiert und in der Gatewayapplikation weiterverarbeitet bzw. dem Steuergerät zugeführt.

Definition 2.4 (Protokollwandlung) Die Protokollwandlung ist für den Datenaustausch zwischen unterschiedlichen Bussystemen notwendig. Sie sorgt für den reibungslosen Informationsaustausch zwischen unterschiedlichen Protokollen.

Definition 2.5 (Diagnose) Die Diagnose umfasst die vom Fahrzeughersteller definierte Diagnosefunktionalität. Sie ermöglicht eine einfache Bestimmung fehlerhafter Aggregate und Sensoren im Fahrzeug.

Definition 2.6 (Netzwerkmanagement) Das flächendeckend eingeführte OSEK-Netz- werkmanagement dient zur Verwaltung und Diagnose von Fahrzeugnetzen. Detaillierte Funktionalitäten sind im OSEK-Netzwerkmanagement Standard[6]zu finden.

Diese Funktionalitäten werden auf der Anwendungsebene des hierarchisch aufgebauten ISO-OSI-Schichtmodells realisiert. Das ISO-OSI-Modell (engl. International Standardi- zation Organisation-Open System Interconnect-Model) ist eine international anerkann- te Methode zur funktionalen Beschreibung komplexer Kommunikationssysteme[7]. Zur Realisierung eines automotive Gateways werden vereinfacht die Schichten eins, zwei und sieben verwendet. Die ersten beiden Schichten beschreiben die physikalischen Eigen- schaften sowie den Zugriff auf das jeweilige Bussystem. Schicht sieben stellt die eigent- liche Gatewayfunktionalität dar.

2.3 Gatewaydesign

Seit der Serieneinführung des CAN-Protokolls 1989 mit drei Busteilnehmern ist die An- zahl heute - je nach Fahrzeugkategorie - auf über 70 Steuergeräte und mehrere Bussys- teme angestiegen. Die Anforderungen an die Gateways und deren Elektronik steigt dazu adäquat. Begonnen mit 8 Bit Mikroprozessoren und externen Bustreibern bestehen heut- zutage Steuergeräte und Gateways aus 32 Bit Risk-Mikrocontrollern, Power-PCs (engl. power personal computer, PPC) oder digitalen Signalprozessoren (engl. digital signal processor, DSP).

Für die meisten Gatewayapplikationen werden Mikrocontroller mit integrierten Bustrei- bern eingesetzt. Dadurch kann die Anzahl an Bauelementen reduziert und somit Kos- ten eingespart werden. Durch die extrem steigende Botschaftsanzahl stößt man häufig bei Steuergeräten mit integriertem Gateway oder Zentralgateways an die Grenzen der zur Verfügung stehenden Rechenleistung. Zur Lösung dieses Problems werden Kombi- nationen aus mehreren Prozessoren eingesetzt. Das Motorsteuergerät der S-Klasse Baureihe 221 besteht z. B. aus zwei PPCs. Einer für die Motor- und der andere für die Gatewayapplikation. Die Aufgabe des Gateway-PPCs besteht in der Entlastung des Host-Prozessors von allen interruptlastigen Gatewayaufgaben, welche die Verarbeitung der eigentlichen Motorapplikation zu sehr verlangsamen würden. Weiterhin bietet er ei- ne Schnittstellen- und Peripherieerweiterung für das Steuergerät. Es ist relativ schwer, nach einem Schaltungsentwurf für ein Gateway den richtigen Prozessor/Mikrocontrol- ler auf dem Markt zu finden. Entwickelt man z. B. ein CAN-Gateway mit zwei CAN-Bus Schnittstellen, wird man von der Variantenvielfalt regelrecht überwältigt. Entscheidet man sich für einen bestimmten Mikrocontroller, werden zu 99 Prozent nicht alle Peripherie- komponenten des Mikrocontrollers benötigt. Man bezahlt somit Geld für nicht benutztes Silizium und muss die nicht benötigte Peripherie oft noch softwareseitig deaktivieren oder in einen sogenannten Safe-Mode versetzen, was wiederum einen Softwareoverhead zur Folge hat. Der Wunsch eines jeden Entwicklungsingenieurs ist es, ein individuell für seine Applikation zugeschnittenes Gateway ohne Hardware-/Software-Overhead und erhöhte Kosten zu designen.

Die Umsetzung dieses Wunsches wird in dieser Arbeit mittels der relativ jungen Techno- logie der FPGAs (engl. Field Programmable Gate Array) erfolgen. FPGAs sind Bausteine zum Aufbau digitaler Logikschaltungen und wurden in den frühen Neunzigern eingeführt. “Field Programmable“ bedeutet, dass die Funktionalität im Baustein durch den Anwender und nicht durch den Hersteller bestimmt wird. Sie vereinen die Vorteile von Mikroprozes- soren und ASICs. Mikroprozessoren sind durch ihre programmierbare Funktionalität sehr flexibel, jedoch lassen sie aufgrund ihrer Struktur keine parallelen oder unverzögerten Operationen zu. ASICs hingegen sind für solche Aufgaben zwar geeignet aber hinsicht- lich Entwurfszeiten und Flexibilität von Nachteil. In Markus Wannemachers Werk “Das FPGA-Kochbuch“[8]werden die wichtigsten Grundlagen, Entwurfsprinzipien, Baustei- ne und Werkzeuge in verständlicher und kompakter Weise dargestellt.

2.4 Zusammenfassung und Trend

Wie dieses Kapitel zeigt, steigt die Funktionalität im Fahrzeug und somit der Anteil an Elektrik und Elektronik enorm an. Die komplexe Vernetzung verschiedenster Bussysteme setzt immer höhere Maßstäbe an das Design von Gateways. Aufgrund der hohen Sys- temkomplexität nahm die Verlässlichkeit der Elektronik in den letzten Jahren rapide ab und die Fehlerhäufigkeit aufgrund falsch ausgelegter oder nicht hinreichend getesteter Systeme stieg an. Im Jahr 2002 waren 50 Prozent aller Fahrzeugpannen auf Elektronik- fehler zurückzuführen. Daher geht der Trend in der nächsten Automobildekade in Rich- tung Reduktion der Steuergeräte bei zunehmender Funktionalität. Dies setzt eine bessere Nutzung von Systemressourcen, eine bessere Lastverteilung auf die verschiedenen Steu- ergeräte und eine Überarbeitung der Systemarchitektur voraus. Aufgrund der Aktualität dieser Thematik befassen sich viele Forschungseinrichtungen und Hochschulen mit dem Problem der optimalen Lastverteilung in verteilten Systemen. Des Weiteren erfordern die bevorstehenden Innovationen aus den Bereichen Multimedia, Telematik und Infotain- ment Hochleistungs-Gateways, welche die hohen Bandbreiten bewältigen können. Daher bleiben die Anforderungen an immer leistungsfähigere Gateways erhalten. Wie man ein optimales Gateway designed, wird in den folgenden Kapiteln beschrieben.

Kapitel 3 Gateway-Systemsynthese

In diesem Kapitel wird ein graphenbasiertes Modell zur Gateway-Systemsynthese hergeleitet. Dazu bilden unterschiedliche FPGA-basierte Ansätze sowie die Theorie der Entwurfsraumrepräsentation und Entwurfsmethodik die Grundlage. Das Modell visualisiert eine Vorgehensweise beim FPGA-basierten Gatewaydesign von der Verhaltensbeschreibung bis hin zur strukturellen Beschreibung auf Systemebene.

3.1 FPGA-basiertes Gateway

Es gibt drei grundsätzliche Methoden um ein Gateway in einem FPGA zu designen. Die erste und einfachste Möglichkeit basiert auf einem Prozessor IP-Core (engl. Intellectual Property-Core) und den zugehörigen Peripherie-Bibliotheken. Die IP-Core-Bezeichnung stammt aus der Halbleiterindustrie - speziell aus dem Gebiet des Chipentwurfs - und steht für die wiederverwendbare Beschreibung eines Bauelements. Das Design des Gateways wird hier mittels einer Entwicklungsumgebung erstellt. Die einzelnen Peripheriemodule können wie bei den meisten Entwicklungsumgebungen komfortabel grafisch oder manuell in einer Hardware-Modellierungssprache miteinander verbunden werden. Da die gesamte Funktionalität des Gateways in einer Softwarehochsprache programmiert ist, wird diese Methode als ”Softwarelösung” bezeichnet.

Die zweite Alternative ist die eigenständige Programmierung des kompletten Gateways in einer Hardware-Modellierungssprache wie z. B. VHDL (engl. Very High Speed In- tegrated Circuit Description Language) oder VERILOG. Hiermit kann der Anwender individuell für seine Aufgabenstellung erforderliche Hardware kreieren. Dies reicht je nach Funktionalitätsumfang und Geschick des Programmierers von einfachen kombina- torischen Logikfunktionen bis hin zum komplexen Prozessorentwurf. Dieses Design wird als ”Hardwarelösung” bezeichnet.

Eine weitere Methode ist das ”heterogene Design”, bestehend aus einer Kombination der ersten beiden Möglichkeiten. Hierbei wird die Gesamtfunktionalität einerseits in Softwa- re auf einem Softprozessor IP-Core und andererseits in Hardware mit anwenderspezifischen Modulen realisiert. Die exakte Umsetzung sowie die Funktionsweise der einzelnen Methoden bilden die Basis des FPGA-basierten Gatewaydesigns. Sie werden im Detail vorgestellt und hinsichtlich ihrer Eigenschaften analysiert.

3.1.1 Softwarelösung

Der Einsatz von IP-Cores beim Schaltungsdesign ermöglicht dem Entwickler die Ent- wurfszeiten (engl. Time-To-Market) neuer FPGA-Designs drastisch zu reduzieren. IP- Cores sind oft verwendete, meist große und komplexe Funktionseinheiten. Bild 3.1 zeigt eine Gatewaylösung mit einem Softprozessor und verschiedenen Peripheriemodulen.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.1: Softwarelösung FPGA-Gateway

Prozessor IP-Cores sind als PPCs, DSPs und als 8/16 Bit Mikroprozessoren erhältlich. Peripheriemodule existieren für alle gängigen Bussysteme. Man unterscheidet zwischen harten und weichen IP-Cores. Harte Cores sind für bestimmte FPGA-Familien ausgelegt und besitzen ein fest vorgegebenes Layout. Dadurch ist ihre Performance und Flächenaus- nutzung für die jeweiligen Familien angepasst. Nachteilig hingegen ist die Unflexibilität gegenüber neuen Produktreihen. Weiche IP-Cores (engl. Soft IPs) basieren auf einer syn- thetisierbaren Beschreibungsform wie z. B. VHDL oder VERILOG. Sie sind im Vergleich zu harten IPs für den Einsatz auf unterschiedlichen FPGA-Typen konzipiert. Dementspre- chend ist deren Performance und Adaptionsaufwand meistens größer als bei den harten IPs.

Die Softwarelösung findet bevorzugt ihren Einsatz in den Entwicklungsphasen eines Pro- jektes, um die prinzipielle Machbarkeit bestimmter Systemfunktionalitäten in FPGAs nachzuweisen und zu testen. Aufgrund der immer kürzeren Entwicklungszeiten und stei- genden Funktionalitätsumfängen eines Produktes setzen Entwickler immer mehr auf den Einsatz von getesteten IP-Cores. Gerade das Erstellen von IPs für Bussysteme ist sehr auf- wendig und erfordert in der automotive Industrie das Erfüllen von hohen Qualitätsstan- dards. Die FPGA-internen Controller und Manager für die an das Gateway angeschlosse-

3.1 FPGA-basiertes Gateway

nen Bussysteme werden daher meistens als fertige IP-Cores integriert. Bei der Auslegung eines FPGA-Systems spielen die beiden Faktoren Performance und Flächenausnutzung eines Designs die wichtigste Rolle. Sie sind für die Architektur des Gateways und die Wahl des FPGA-Bausteins verantwortlich. Daher wird jede Realisierungsmöglichkeit anhand dieser Faktoren bewertet.

Der Vorteil der Softwarelösung liegt darin, dass der Entwickler nicht unbedingt fundierte Kenntnisse in den Hardware-Modellierungssprachen besitzen muss. Die komplette Funktionalität wird mit dem Prozessor IP in Form einer Programmierhochsprache, meistens ”C”, realisiert. Der Instruktionscode für den Mikroprozessor wird hierbei in FPGA-internen Speicherzellen gespeichert. Dadurch ist die Flächennutzung des Designs unabhängig von der Funktionalität und nur durch die Größe und Anzahl dieser Speicherzellen beschränkt. Dies erleichtert die Wahl eines geeigneten FPGAs.

Schwieriger ist die Berechnung der Performance. Die Performance eines Systems be- schreibt sein Echtzeitverhalten hinsichtlich der an das Gateway angeschlossenen Bussys- teme. Die FPGA-interne Gateway-Designfrequenz fDesign darf hierbei einen minimalen Wert, welcher die Funktionssicherheit des Gateways gewährleistet, nicht unterschreiten:

Abbildung in dieser Leseprobe nicht enthalten

fio ist die maximale Eingangs-/Ausgangsfrequenz der Schnittstelle vom FPGA zum Physical Layer Treiber des Bussystems mit der höchsten Übertragungsrate. Bei paralleler Schnittstelle zum Physical Layer Treiber entspricht fio dem Quotienten aus maximaler Frequenz und Anzahl der Leitungen.

Die maximale Designfrequenz ist durch die maximale FPGA-Frequenz und durch das Design an sich beschränkt. Da bei der Softwarelösung der komplette Funktionalitätsumfang auf dem Prozessor IP realisiert wird, kann die Anzahl der benötigten Design-Taktzyklen nur durch Softwaresynthese des Funktionscodes bestimmt werden. Die Vorgehensweise bei der Softwaresynthese ist in Kapitel 3.5.3 beschrieben. Die benötigten Taktzyklen NDesign der Softwarelösung lassen sich aus der Summe der Anzahl an Takten der prozessorspezifischen Assemblerinstruktionen und der maximalen Anzahl an Takten des Bus IP-Cores berechnen. NDesign muss für den kritischen Softwarepfad und den Bus IP-Core mit der größten Anzahl an benötigten Takten kalkuliert werden.

Abbildung in dieser Leseprobe nicht enthalten

3.1 FPGA-basiertes Gateway

3.1.2 Hardwarelösung

Bei der Hardwarelösung besteht das Gateway Design nicht nur aus einem Mikroprozessor IP-Core und Peripherie, sondern es ist aus einzelnen Hardware-Funktionsblöcken zusam- mengestellt.

Definition 3.1 (Funktionsblock) Ein Funktionsblock ist ein anwenderspezifisches Ob- jekt, welches eine oder mehrere Funktionen bereitstellt. Der Funktionsblock nimmt Daten- und Kontrollsignale über eine fest definierte Schnittstelle entgegen bzw. leitet diese wei- ter. Zusätzlich verfügt er über Attribute, die sein Verhalten und seine Eigenschaften näher festlegen.

Jede Gatewayfunktionalität lässt sich durch einen oder mehrere Funktionsblöcke beschreiben. Die Granularität ist hierbei dem Anwender überlassen und abhängig von der Abstraktionsebene der Beschreibungsform des jeweiligen Designs.

Definition 3.2 (Granularität) Die Granularität charakterisiert den Detaillierungsgrad einer Beschreibungsform. Sie ist abhängig von der Abstraktionsebene und dem Verfeinerungsgrad der zu beschreibenden Funktionalität.

Erläuterung: Bei der Darstellung eines Bus IP-Cores als ein einziger Funktionsblock handelt es sich um eine grob granulare Darstellungsform. Eine verfeinerte Darstellung eines Bus IP-Cores aus mehreren Funktionsblöcken mit jeweils einem geringeren Funk- tionsumfang pro Block, z. B. einem Nachrichten- oder Bitvergleich, entspricht einer fein granularen Beschreibung.

Funktionsblöcke ermöglichen eine hierarchische Darstellungsform. Dies bedeutet, dass ein Funktionsblock durch Verfeinerung aus mehreren Blöcken dargestellt werden kann. Diese befinden sich dementsprechend auf einer niedrigeren Abstraktionsebene der Be- schreibungsform. Abbildung 3.2 zeigt den Aufbau einer Bus-Basis-Konstellation. Zur Erläuterung ihrer Funktionsweise wird eine grob granulare Darstellungsform gewählt.

Eine Bus-Basis-Konstellation ist eine Kombination von Funktionsblöcken, welche not- wendig sind, um ein beliebiges Bussystem in einem FPGA zu realisieren. Die grob gra- nularen Blöcke sind dabei universell einsetzbar. In Referenz zum ISO-OSI-Schichtmodell wird die Bitübertragungsschicht durch den Physical Layer Treiber, die Sicherungsschicht durch den jeweiligen Bus IP-Core und die Anwendungsschicht durch die restlichen Funk- tionsblöcke realisiert. Der Physical Layer Treiber ist verantwortlich für die physikalische Wandlung des Bussignals in ein serielles oder paralleles digitales TTL-Signal auf FPGA- Seite. Der Bus IP-Core ist der Controller eines Bussystems. Er sorgt für die Initialisierung, Synchronisation und Steuerung des Bussystems. Das Verpacken, Zwischenspeichern und Weiterleiten von Informationen gehört dabei zu seinen Hauptaufgaben, außerdem das ge- samte Nachrichtenhandling.

3.1 FPGA-basiertes Gateway

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.2: Hardwarelösung FPGA-Gateway (Bus-Basis-Konstellation)

Die Schnittstelle vom Bus IP-Core zum konfigurierbaren Gateway-Manager (engl. Configurable Gateway-Manager, CGM) bildet der Receive/Transmit-Handler (Rx/Tx-Handler). Er ist für die Initialisierung der Bus IPs zuständig und steuert die Nachrichtenkommunikation zwischen dem Bus IP und einem oder mehreren CGMs. Der CGM ist die Steuerzentrale im Gateway. Er bestimmt die Funktionalität des Gateways anhand von den im ROM hinterlegten Informationen und entscheidet was mit einer eintreffenden Nachricht geschieht. Das Design des CGMs ist je nach Bussystem und Funktionsumfang unterschiedlich, jedoch immer modular strukturiert (siehe Bild 3.2). Abhängig vom Bussystem können weitere Module integriert oder entfernt werden.

Für jedes im Gateway implementierte Bussystem bestimmen alleine die in den ROMs kodierten Informationen dessen Verhalten. Ein FPGA besitzt je nach Aufbau intern de- finierte RAM-Bereiche von bestimmter Anzahl und Größe. Bei den FPGA-Familien des Herstellers Xilinx werden sie als Block-RAMs - oder kurz BRAMs (engl. Block Random Access Memory) bezeichnet und haben meist eine Größe von 18 kbit je Block. Die An- zahl variiert bei kleinen FPGAs von vier bis zu über 200 bei großen. Diese RAM-Zellen können vom Anwender beliebig verwendet werden, wie in diesem Design beispielswei- se als ROM-Zellen. Die ROM-Inhalte werden über eine ASCII-Initialisierungsdatei be- schrieben und direkt in den Bitstream des FPGAs integriert. Dabei ist die Kodierung der Gatewayfunktionalität in den ROMs dem Anwender selbst überlassen. Die Schnittstelle zwischen dem CGM bzw. den einzelnen Funktionalitäten und den ROM-Zellen wirkt sich entscheidend auf die Performance des Systems aus.

Als Beispiel werde ein nachrichtenorientiertes Bussystem gewählt, bei welchem jede Nachricht eine 11 Bit große Identifikationsnummer (ID) besitzt. Hier bietet es sich an, die IDs direkt als Adressleitungen des ROMs zu verwenden. Somit besitzt jede mögliche Nachricht ihre eigene Speicherzelle im ROM. Dadurch ist die Zugriffsgeschwindigkeit

3.1 FPGA-basiertes Gateway

enorm hoch, da man auf komplizierte Polling-Algorithmen verzichten kann. Die Spei- chertiefe ist abhängig von der Größe der BRAMs. Bei einem 18 kbit BRAM und einer 11 Bit ID stehen maximal 9 Bit zur Kodierung der Funktionalität zur Verfügung. Verwen- det man davon fünf zur Kodierung des Zielbussystems und 4 Bit zur Funktionalitätsde- kodierung, so lassen sich mit der empfangenen Nachricht 16 verschiedene Operationen ausführen und 32 mögliche Bussysteme adressieren. Die Dekodierung des ROM-Inhaltes findet im CGM statt.

Mit der Bus-Basis-Konstellation kann jedes beliebige Gateway erstellt werden. Dabei un- terscheidet man zwischen zwei Designalternativen. Einerseits gibt es das geschwindig- keitsoptimierte, zum anderen das flächen-/kostenoptimierte Design. Das geschwindigkeits- optimierte Design ist geeignet für Gateways mit sehr hohen Datenraten oder einer hohen Anzahl an angeschlossenen Bussystemen. Es ist eine parallele Implementierung, bei der für jedes an das Gateway angeschlossene Bussystem eine Bus-Basis-Konstellation ver- wendet wird. Auch hier darf die FPGA-interne Systemfrequenz einen minimalen Wert, welcher die Funktionssicherheit des Gateways gewährleistet, nicht unterschreiten (For- mel 3.1). Die Anzahl der Taktzyklen NDesign bei dieser parallelen Implementierung wird von demjenigen Funktionsblock bestimmt, der am meisten Taktzyklen zum Verarbeiten einer Nachricht benötigt. Hierbei wird angenommen, dass die Empfangs- und Senderou- tinen der Bus IPs und der Rx/Tx-Handler identische Taktzyklen benötigen und in den Funktionsblöcken ebenfalls parallelisiert sind. Dann ergibt sich:

Abbildung in dieser Leseprobe nicht enthalten

Durch diese parallele Implementierung erreicht man eine maximale Performance des Ga- teways, was jedoch einen enormen Flächenbedarf zur Folge hat. Da der Flächenverbrauch äquivalent zu den Kosten ist, werden für Gateways mit geringen Datenraten und/oder geringer Anzahl an angeschlossenen Bussystemen bestimmte Vorgänge durch sequenzi- ell arbeitende Funktionsblöcke ersetzt. Das flächen-/kostenoptimierte Design besitzt nur einen Rx/Tx-Handler und einen CGM mit ROMs. Hierbei muss bei dem Design der ein- zelnen Funktionsblöcke äußerste Vorsicht geboten werden, damit es nicht zu Datenkol- lisionen oder sogar zum Datenverlust kommt. Für jedes Bussystem ist weiterhin ein ei- gener Bus IP-Core vorhanden. Die internen Design-Taktzyklen werden folgendermaßen bestimmt:

Abbildung in dieser Leseprobe nicht enthalten

Hierbei wird angenommen, dass die Empfangs- und Senderoutinen der Bus IPs identische Taktzyklen benötigen und in den Funktionsblöcken parallelisiert sind. Bei der Berechnung der Design-Taktzyklen sind parallele und sequenzielle Vorgänge unterschiedlich betrach- tet. Die exakte Kalkulation der Designfrequenz eines FPGA-Gateways muss individuell durchgeführt werden, da jeder Entwickler seine Funktionsblöcke unterschiedlich konstru- iert.

3.1.3 Heterogenes Design

Das Heterogene Design ist eine hybride Lösung aus der Softwarelösung und der Hardwa- relösung. Sie kann die unterschiedlichsten Konstellationen annehmen. Der Prozessor erle- digt hierbei Aufgaben des CGMs und/oder Aufgaben des Rx/TX-Handlers. Mittels dieser Lösung kann man jede Gatewayfunktion entweder in Hardware oder in Software reali- sieren. Die hybride Lösung ist das am schwersten zu entwickelnde Design aufgrund der Problematik beim Verteilen der einzelnen Aufgaben. Welche Funktionen sollen in Soft- ware mittels des Prozessors realisiert werden und welche als Hardware in Form von Funk- tionsblöcken? Dieses Problem ist auch unter dem Begriff Hardware/Software-CoDesign bekannt. Bei der exakten Verteilung der einzelnen Funktionen kann ein optimales Design erstellt werden. Um diese Problematik zu lösen, muss ein Verfahren entwickelt werden, welches das gesamte Gateway beschreibt und eine optimale Architektur mit zugehöriger Hardware/Software-Partitionierung liefert.

Die im nächsten Kapitel vorgestellten Grundlagen der Entwurfsrepräsentation und Entwurfsmethodik dienen als Basis zur Entwicklung eines solchen Verfahrens.

3.2 Grundlagen der Entwurfsrepräsentation und Ent- wurfsmethodik

3.2.1 Entwurfsrepräsentation

Es gibt viele Ansätze, die verschiedenen Dimensionen des Entwurfs miteinander in sys- tematischer Weise zu einem Entwurfsmodell zu verknüpfen. Das am weitesten verbrei- tete ist das 1983 von Gajski und Kuhn entwickelte Y-Modell, das 1985 von Walker und Thomas weiter verfeinert wurde. Im Y-Modell (siehe Abbildung 3.3) ist der Grad der Verfeinerung eines Entwurfs in Abstraktionsebenen und die Repräsentationen in Sichten dargestellt. Die in Form eines Ypsilons angeordneten Achsen repräsentieren die Sichten. Dabei bilden die vom Ursprung ausgehenden konzentrische Kreise die Abstraktionsebe- nen.

Es sei an dieser Stelle darauf hingewiesen, dass die im Y-Diagramm verwendeten Be- zeichnungen vom Original abweichen können. Das Modell zeigt die Aufteilung in funk- tionelle, strukturelle und physikalische Sichten. In der funktionellen Sicht wird das Ver- halten des Entwurfs unabhängig von dessen Implementierung beschrieben. Die struk- turelle Sicht hingegen zeigt die logische Struktur bzw. abstrakte Implementierung des Entwurfsgegenstandes. Aufgabe der physikalischen Sicht ist die Darstellung der jeweili- gen Abstraktionsebene in ihrer physikalischen Sichtweise. Dies entspricht der Form einer konkreten Implementierung mit realen Objekten. Es gibt viele Versionen des Y-Modells, da jeder Entwickler sich hinsichtlich seiner Problemstellung eigene erforderliche Sich- ten und Abstraktionsebenen zusammenstellt. Heute kommen mit steigender Häufigkeit

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.3: Y-Modell

heterogene Designs mit Hardware- und Softwarekomponenten zum Einsatz. Bild 3.4 visualisiert ein Modell zum Entwurf heterogener Systeme[15].

Das Wasserfallmodell zeigt, dass Abstraktionsebenen und Sichten in gewisser Weise orthogonal zueinander sind. Schon in der strukturellen Entwurfsrepräsentation auf Systemebene erfolgt eine Aufteilung in Hardware- und Softwarekomponenten. Das Modell ist hierbei auf die funktionelle und strukturelle Sicht beschränkt. Die rechte Seite des Wasserfallmodells ist eine Ableitung aus dem Y-Modell, wobei die linke Seite eine Abstraktionsäquivalente für den Softwareentwurf darstellt. Auf eine detaillierte Beschreibung der einzelnen Abstraktionsebenen beider Modelle sei auf[13]und[15]verwiesen. Die für das Gatewaydesign relevanten Abstraktionsebenen und Sichten werden im Modell zur Gateway-Systemsynthese in Kapitel 3.3 beschrieben.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.4: Wasserfallmodell

3.2.2 Synthese und Analyse

Der Begriff der Synthese und Analyse lässt sich anhand der beschriebenen Modelle ver- anschaulichen. Ein Entwurfsschritt von einem festgelegten Punkt im Modell in Richtung des Entwurfziels bezeichnet man als Syntheseschritt. Die Vorgehensweise von der Verhal- tensbeschreibung (funktionelle Sicht) hin zur strukturellen Sicht oder von der strukturel- len hin zur physikalischen Sicht ist beispielsweise ein Syntheseschritt. Äquivalent dazu ist der Entwurfsschritt von einer Abstraktionsebene einer Sicht zu einer Abstraktions- ebene derselben Sicht mit höherem Detaillierungsgrad. Ein Syntheseschritt ist dadurch gekennzeichnet, dass der Detaillierungsgrad steigt und der Abstraktionsgrad sinkt. Die entgegengesetzten Vorgehensweisen bezeichnet man als Analyse.

3.2.3 Entwurfsmethodik

Eine traditionelle und heute noch vor allem im Hardwareentwurf verwendete Entwurfs- methodik ist das ”Erfassen und Simulieren”. Man beginnt mit einer formalen Beschrei- bung des Systems, welche in eine Blockstruktur, der Architektur, umgesetzt wird. Desi- gner wandeln die einzelnen Blöcke in Logik um, die anschließend simuliert und verifiziert werden.

Seit einigen Jahren hat sich die Logiksynthese als integraler Bestandteil des Hardwareent- wurfs etabliert und das System wird durch eine ausführbare Verhaltensbeschreibung spe- zifiziert. Diese Entwurfsmethodik wird als ”Beschreiben und Synthetisieren” bezeichnet und ist im Vergleich zum ”Erfassen und Simulieren (Entwurf per Hand)” eine wesentlich schnellere und qualitativ bessere Entwurfsart. Auf Logikebene werden dabei funktionale Einheiten wie z. B. Multiplizierer und Addierer automatisch und optimiert generiert. Das ”Beschreiben und Synthetisieren” findet ebenfalls seinen Einsatz bei der Architektursyn- these. Sie wird auch als High-Level-Synthese bezeichnet, da sie sich in einer höheren Ab- straktionsebene wie die Logiksynthese befindet (siehe Abbildung 3.4). Die funktionelle Beschreibung auf Architekturebene erfolgt durch synthetisierbare Daten- und Kontroll- flussgraphen, welche durch die drei Syntheseaufgaben Allokation, Ablaufplanung und Bindung transformiert werden. Dabei ist die Aufgabe der Allokation die Festlegung der zur Implementierung benötigten funktionalen Komponenten. Der Detaillierungsgrad der Komponenten ist abhängig von der jeweiligen Abstraktionsebene. Durch die Ablaufpla- nung wird die zeitliche Abfolge des spezifizierten Verhaltens auf den einzelnen Kompo- nenten festgelegt, sodass zu jedem Zeitpunkt bekannt ist, welche Operation wann aus- geführt wird. Die Bindung ordnet abschließend den Aufgaben die entsprechenden bei der Allokation festgelegten Komponenten zu. Das ”Beschreiben und Synthetisieren” wird ebenfalls beim Softwareentwurf eingesetzt. Dabei wird die Verhaltensbeschreibung des Systems durch eine ablauffähige Programmiersprache, z. B. C oder C++, dargestellt.

Bei der Synthese auf Systemebene gibt es momentan noch keine ausgereiften Methoden. Dennoch scheint sich hier ein Paradigma durchzusetzen, welches sich durch ”Spezifizie- ren, Explorieren und Verfeinern” beschreiben lässt[12]. In der Spezifikationsphase wird die Spezifikation des Gesamtsystems erstellt. Sie beinhaltet in erster Linie die Beschrei- bung der Funktionalität, Verifikation kritischer Systemeigenschaften sowie die Untersu- chung und Exploration verschiedener Realisierungsvarianten. Die Explorationsphase ver- gleicht die unterschiedlichen Realisierungsvarianten im Entwurfsraum. Hier werden die zu implementierenden Funktionalitäten auf mögliche Komponenten eines heterogenen Systems gemapped. In der anschließenden Verfeinerungsphase erhöht man den Detaillie- rungsgrad der Funktionalität und verteilt diese erneut auf die verschiedenen Hardware- und Softwarekomponenten. Die Exploration und Verfeinerung kann solange wiederholt werden, bis eine komplette strukturelle Beschreibung des Systems vorliegt, d. h. die Gra- nularität wird ständig erhöht.

3.3 Modell zur Gateway-Systemsynthese

Ziel ist es, ein optimales FPGA-Gateway zu designen. Wie in Kapitel 3.1 beschrieben, kann ein Gateway aus einer reinen Hardwarelösung, einer reinen Softwarelösung oder aus einem heterogenen Design bestehen. Gesucht wird eine Beschreibungsform, die alle Möglichkeiten in Betracht zieht und eine optimale Lösung liefert. Als Basismodell hierfür wird das Wasserfallmodell verwendet, da es heterogene Strukturen zulässt.

3.3.1 Einschränkung der Abstraktionsebenen

Der erste Schritt beim Gateway-Modelldesign ist die Eingrenzung der zu behandelnden Abstraktionsebenen. Dies erreicht man durch die Definition der Grenzen zum vorhande- nen automatisierten Entwicklungsfluss (engl. Designflow). Hardwareseitig wird die Ver- haltensbeschreibung auf Architekturebene mittels einer Hardware-Modellierungssprache (VHDL oder VERILOG) programmiert und softwareseitig auf Modulebene mit einer Programmierhochsprache (C oder C++). Ein Automatismus von der Architektur/Modul- Verhaltensbeschreibung bis zur untersten Abstraktionsebene ist somit hardware- und soft- wareseitig durch Compiler und Synthesewerkzeuge in heutigen Entwicklungsumgebun- gen gegeben. Dieser Automatismus grenzt die Sichten und Abstraktionsebenen für das Gateway-Synthesemodell auf die Systemebene ein. Die Grenzen sind in Bild 3.5 darge- stellt. Folglich besitzt das Gateway-Synthesemodell als Eingangsparameter die Verhal- tensbeschreibung des Gateways und liefert nach der Synthese ein optimales Design mit der entsprechenden Hardware-/Software-Partitionierung. Diese Partitionierung dient als Eingangsvektor für den schon existierenden automatisierten Designflow.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.5: Automatismus im Wasserfallmodell

3.3.2 Entwurf auf Systemebene

Auf Systemebene wird der Syntheseprozess als Systemsynthese bezeichnet. Das Gebiet der Systemsynthese ist derzeit noch wenig erforscht, daher existiert auch noch kein Konsens über einheitliche Definitionen und über das Aufgabenspektrum. Deshalb wird der Begriff der Gateway-Systemsynthese hier eingeführt und definiert.

Definition 3.3 (Gateway-Systemsynthese) Unter Gateway-Systemsynthese wird das Problem verstanden, eine Gateway-Spezifikation auf Systemebene auf eine heterogene HW/SW- Struktur abzubilden. Dies verlangt folgende Vorgehensweise:

- Beschreiben des Systemverhaltens
- Festlegung möglicher Architekturen
- Abbilden des Systemverhaltens auf die festgelegten Architekturen
- Optimierung des Systems
- Exploration des Entwurfsraums
- Finden einer optimalen Lösung

Die ersten drei Aufgaben der Gateway-Systemsynthese werden in den Unterkapiteln des Kapitels 3 behandelt, die Optimierung des Systems, Exploration des Entwurfsraums und das Finden einer optimalen Lösung im Folgekapitel 4. Durch Definition 3.3 ergibt sich das in Bild 3.6 dargestellte Modell zur Gateway-Systemsynthese.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.6: Modell zur Gateway-Systemsynthese (Systemgraph)

Für das Beschreiben des Systemverhaltens eines Gateways würde sich eine datenflussori- entierte Beschreibungsform anbieten. Sie besitzt jedoch den Nachteil, dass sie keine Kon- trollstrukturen abbilden kann, welche aufgrund der Komplexität und Intelligenz heutiger Gateways erforderlich sind. Die Lösungen bieten hier sogenannte Kontroll-/Datenfluss- graphen (engl. control data flow graph (CDFG)). CDFGs sind heterogene Modelle, die es erlauben, die Gatewayfunktionalität in Form von steuerungs- und datenflussorientierten Komponenten zu beschreiben. Die Festlegung möglicher Architekturen resultiert aus dem Hardwareaufbau des Gateways bzw. der zur Verfügung stehenden Komponenten. Diese Arbeit spezialisiert sich auf ein FPGA-basiertes Gateway, daher bestehen die möglichen Architekturen aus IP-Cores und/oder anwenderspezifischen Funktionsblöcken. Für die Darstellung der jeweiligen Architekturmöglichkeiten bietet sich ebenfalls eine grafische Form an. Diese kann als Graph oder Schaltplan erfolgen. Das Abbilden des Systemver- haltens auf die festgelegten Architekturen wird mit Hilfe von Mappingkanten umgesetzt. Sie beschreiben mögliche hardwareseitige Implementierungsvarianten einer Funktion des Systemverhaltens.

Für die ersten drei Schritte der Gateway-Systemsynthese wird eine grafische Beschrei- bungsform gewählt. Die in Teich’s ”Digitale Hardware/Software-Systeme” beschriebene Graphentheorie dient hierfür als Grundlage[15]. Das Beschreiben des Systemverhaltens und der möglichen Architekturen sowie das Abbilden der Funktionalität auf diese kann in Form eines Gateway-Systemgraphen dargestellt werden. Die folgenden Kapitel beschrei- ben die Transformation der Verhaltensbeschreibung in einen Systemgraphen.

3.4 Der Gateway-Systemgraph

Bei der Erstellung des Gateway-Systemgraphen werden die ersten drei Aufgaben der Gateway-Systemsynthese umgesetzt. Diese sind: Beschreiben des Systemverhaltens, Festlegung möglicher Architekturen und das Abbilden des Systemverhaltens auf die festgelegten Architekturen. Der Graph ist bipartit und besteht aus einem Gateway-Funktionsgraphen, einem Gateway-Architekturgraphen und den zugehörigen Mappingkanten.

3.4.1 Definitionen

Die an dieser Stelle aufgeführten Definitionen bilden die Grundlage für die in den weiteren Kapiteln behandelten Verfahren und Modelle. Sie sind aus[15]abgeleitet und entsprechend für die in dieser Arbeit verwendeten Nomenklaturen abgewandelt.

Definition 3.4 (Gateway-Funktionsgraph) Ein Gateway-Funktionsgraph GF (VF , EF ) ist ein gerichteter, azyklischer Kontroll-/Datenflussgraph (CDFG) mit Knotenmenge VF und Kantenmenge EF , in dem jeder Knoten vi ∈ VF eine vom Gateway zu verrichtende Aufgabe und jede Kante e = (vi, vj ) ∈ EF eine Daten-/Kontrollflussabhängigkeit dar- stellt.

Als Beispiel wird der in Abbildung 3.7(a) dargestellte Funktionsgraph betrachtet. Es be- stehen Daten-/Kontrollflussabhängigkeiten zwischen Knoten v1 und v2 und zwischen v1 und v3.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.7: a) Gateway-Funktionsgraph und b) Gateway-Architekturgraph

Definition 3.5 (Gateway-Architekturgraph) Der Gateway-Architekturgraph GA(VA, EA) ist ein gerichteter Graph mit Knotenmenge VA und Kantenmenge EA, in dem jeder Knoten vi ∈ VA eine Hardwarekomponente (IP-Core oder anwenderspezifischer Funkti- onsblock) und jede Kante e = (vi, vj ) ∈ EA einen Daten- oder Kontrollfluss darstellt.

Abbildung in dieser Leseprobe nicht enthalten

3.4 Der Gateway-Systemgraph

Der in Abbildung 3.7(b) dargestellte Architekturgraph zeigt vier Hardwaremodule v1 bis v4, die gerichtet untereinander Daten- oder Kontrollsignale austauschen können. Knoten v2 kann z. B. von Knoten v1 unidirektional Daten-/Kontrollsignale empfangen und an Knoten v3 senden. Zwischen Knoten v1, v3 und v3, v4 existieren bidirektionale Verbin- dungen.

Definition 3.6 (Gateway-Systemgraph) Der Gateway-Systemgraph GS (VS , ES ) ist ein bipartiter Graph, bestehend aus einem Gateway-Funktionsgraphen GF (VF , EF ), einem Gateway-Architekturgraphen GA(VA, EA) und einer Menge von Mappingkanten EM . Ei- ne Mappingkante e = (vi, vj ) ∈ EM weist einem Gateway-Funktionsgraphenknoten vi ∈ VF eine oder mehrere Hardwarekomponenten vj ∈ VA des Gateway-Architekturgraphen zu.

3.4.2 Gateway-Funktionsgraph

Der Gateway-Funktionsgraph dient zum Beschreiben der Funktionsweise eines Gate- ways. Er visualisiert in einer vom Benutzer definierten Granularität das Gatewayverhal- ten. Es empfiehlt sich, anfangs eine grobgranulare Darstellung zu wählen, die in späteren Iterationsschritten beliebig verfeinert werden kann. Das Design des Graphen lässt sich in drei Zonen darstellen. Die Ereigniszone beschreibt das aufgetretene Ereignis. In Zo- ne zwei, der Verarbeitungszone, findet die gatewayinterne Ereignisverarbeitung statt. Sie dient zur Identifikation des Ereignisses und der Bestimmung der zu verrichtenden Aktion in Zone drei. Die Aktionszone führt die entsprechende Funktion aus. Beim Entwurf des Funktionsgraphen werden die Zonen beginnend bei der ersten bis hin zur dritten Zone designed.

Beispiel: Bild 3.8(a) zeigt den Funktionsgraphen eines Gateways mit zwei Bussystemen. Knoten v1 und v2 der Ereigniszone stellen den Empfang von Nachrichten auf zwei unterschiedlichen Bussystemen dar. In der Verarbeitungszone findet in Knoten v3 und v4 die Nachrichtenübernahme und Identifikation statt. Die Aktionszone beschreibt in den Knoten v5 bis v8 vier mögliche Gatewayfunktionalitäten (siehe Kapitel 2.2). Diese Methodik ermöglicht die Darstellung des gesamten Gatewayverhaltens.

3.4.3 Gateway-Architekturgraph

Zur Darstellung der zur Verfügung stehenden Hardwareressourcen des Gateways dient der Gateway-Architekturgraph. Die einzelnen Knoten des Graphen entsprechen poten- tiellen allozierbaren Hardwaremodulen zur Abarbeitung der im Funktionsgraphen defi- nierten Aufgaben, wobei Hardwaremodule im FPGA Funktionsblöcke oder IP-Cores sein können. Die Granularität des Graphen lässt sich nur durch Veränderung der jeweiligen Granularität der Funktionsblöcke variieren, da IP-Cores aus einem fest vorgegebenen De- sign bestehen. Der Architekturgraph kann äquivalent mit einem elektrischen Schaltplan in

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.8: a) Drei-Zonen-Funktionsgraph und b) Gateway-Architekturgraph

vereinfachter Form verglichen werden. Bild 3.8(b) zeigt einen zum in Bild 3.8(a) passenden Architekturgraphen. Hierbei sind die Knoten v1 bis v8 Funktionsblöcke und Knoten v9 ein Mikroprozessor IP-Core. Die Kanten beschreiben den möglichen Kommunikationsfluss zwischen den einzelnen Ressourcen.

3.4.4 Gateway-Systemgraph

Durch das Mapping der einzelnen Knoten des Funktionsgraphen auf die Ressourcen des Architekturgraphen entsteht der bipartite Gateway-Systemgraph. Die Mappingkanten EM des Systemgraphen bilden das Bindeglied zwischen Funktions- und Architekturgraph. Sie weisen den einzelnen Knoten des Funktionsgraphen Hardwareressourcen des Architekturgraphen zu, auf denen die entsprechenden Funktionen realisierbar sind. Abbildung 3.9 zeigt einen Gateway-Systemgraphen bestehend aus dem zuvor beschriebenen Funktionsund Architekturgraphen. Es ist zu erkennen, dass sich trotz grobgranularer Darstellung und minimaler Knotenzahl ein komplexer Graph bildet. Der Gateway-Systemgraph wird im Folgenden auch als Spezifikation bezeichnet.

Die Gewichtung der Mappingkanten beinhaltet Informationen über die Implementierung der jeweiligen Funktion auf einer Ressource. Hier wurden beispielsweise die Gewichtun- gen [Taktzyklen/Ressourcengröße] benutzt. Die Taktzyklen geben Auskunft darüber, wie viele Systemtakte zur Abarbeitung der zu realisierenden Funktion von einer Ressource benötigt werden. Die Ressourcengröße ist ein Maß des Platzbedarfes für die allokierte Hardwareressource im FPGA. Diese Informationen dienen als Grundlage für die spätere Optimierung des Graphen und zur Exploration des Entwurfsraums. Die Wahl der Art und

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.9: Beispiel Gateway-Systemgraph GS (VS ,ES )

Anzahl der Gewichte ist dem Benutzer überlassen. Sie ist abhängig davon, nach welchen Kriterien das Gateway designed und optimiert werden soll. Bei FPGA-Systemen sind vor allem die Eigenschaften Performance und Kosten interessant, wobei Kosten proportional zur Ressourcengröße sind. Eine weitere oft benötigte Gewichtung ist die Leistungsaufnahme. Gerade bei automotive Applikationen spielt der Stromverbrauch eine bedeutende Rolle. In dem vorgestellten Beispiel-Systemgraphen kann aufgrund der zwei Gewichtungen das Design nach den Kriterien Performance (Taktzyklen) und Flächenverbrauch (Ressourcengröße) optimiert werden. Die Schwierigkeit besteht im Aufstellen der Gewichtung der Mappingkanten und wird im Folgenden erläutert.

3.5 Gewichtung der Mappingkanten

Wie im Kapitel Gateway-Systemgraph beschrieben, besteht eine der Schwierigkeiten beim Systemgraphendesign in der Festlegung der Gewichtung der Mappingkanten. Die Ge- wichtung besteht aus einer oder mehreren Größen und beschreibt die Eigenschaft der Implementierung eines Funktionsgraphenknotens auf einen Ressourcenknoten. Sie spie- len bei der späteren Optimierung des Systemgraphen eine entscheidende Rolle und tragen zum Auffinden optimaler Lösungen bei. Bei einem FPGA-basierten Design sind die Sys- temeigenschaften Performance, Flächenverbrauch und Leistungsaufnahme von Interesse,

Abbildung in dieser Leseprobe nicht enthalten

daher beschränkt man sich auf diese Gewichte. Für dessen Festlegung wird nachfolgend zwischen der Gewichtung für Funktionsblöcke und für Mikroprozessor IP-Cores unter- schieden.

3.5.1 Gewichtung von Funktionsblöcken

Die Gewichtung der Funktionsblöcke hängt vom Aufbau und des zu realisierenden Funk- tionsumfangs ab. Die Performance eines Funktionsblocks kann auf zwei unterschiedliche Arten bestimmt werden. Die erste Methodik ist das Analysieren der Hardwarebeschrei- bungssprache. Hierbei wird eine Codeanalyse durchgeführt, indem man den Code in se- quentielle und parallele Routinen aufteilt und die Taktzyklen der einzelnen Routinen be- rechnet. Der Aufwand ist proportional zum Funktionsumfang und somit zur Granularität. Die zweite Art ist die Verhaltenssimulation des Funktionsblocks mittels einer speziellen Entwicklungsumgebung. Anhand der Simulation kann die benötigte Taktzahl des Blocks zur Abarbeitung der zu verrichtenden Funktion ermittelt werden. Diese Methodik wird ebenfalls zur Bestimmung der Leistungsaufnahme verwendet. Die erste Methode bietet sich bei feingranularen Funktionsblöcken mit geringem Funktionsumfang an. Bei kom- plexeren Blöcken steigt die Fehlerquote dieser Analyse, daher wird eine Verhaltenssimu- lation empfohlen. Die Anzahl der erforderlichen Taktzyklen wird als numerischer Wert in die entsprechende Mappingkante eingetragen. Zur Bestimmung des Flächenverbrauchs eines Funktionsblocks gibt nur dessen Hardwaresynthese Aufschluss. Ein Synthese-Tool liefert die benötigte Anzahl an Gatter bzw. Slices, welche im FPGA benötigt werden, um diesen Funktionsblock zu realisieren. Das Ergebnis wird ebenfalls der entsprechenden Mappingkante zugewiesen.

3.5.2 Gewichtung von Mikroprozessor IP-Cores

Die Mappingkantengewichtung von Funktionsgraphenknoten auf IP-Cores ist für das Kri- terium Flächenverbrauch relativ einfach. Die Größe eines Mikroprozessors IP-Cores ist meistens im Datenblatt angegeben. Sollte dies nicht der Fall sein, muss wie bei Funkti- onsblöcken eine Hardwaresynthese durchgeführt werden. Den Leistungsverbrauch erhält man mittels geeigneter Tools. Die Gewichtung Taktzyklen/Performance ist im Vergleich zu den bisher genannten Verfahren weitaus aufwendiger. Für die Durchführung muss der Anwender einschlägige Erfahrungen mit dem eingesetzten Mikroprozessor IP-Core und dessen Programmierung besitzen. Das Bestimmen der Taktzyklen erfolgt mit Hilfe der Softwaresynthese.

[...]

Ende der Leseprobe aus 136 Seiten

Details

Titel
Optimales Gatewaydesign mit genetischem Algorithmus und ganzzahliger linearer Programmierung
Hochschule
Universität Ulm
Note
sehr gut
Autor
Jahr
2008
Seiten
136
Katalognummer
V129310
ISBN (eBook)
9783640352791
ISBN (Buch)
9783640352920
Dateigröße
3244 KB
Sprache
Deutsch
Schlagworte
Optimales, Gatewaydesign, Algorithmus, Programmierung
Arbeit zitieren
Wolfgang Hauer (Autor), 2008, Optimales Gatewaydesign mit genetischem Algorithmus und ganzzahliger linearer Programmierung, München, GRIN Verlag, https://www.grin.com/document/129310

Kommentare

  • Noch keine Kommentare.
Im eBook lesen
Titel: Optimales Gatewaydesign mit genetischem Algorithmus und ganzzahliger linearer Programmierung



Ihre Arbeit hochladen

Ihre Hausarbeit / Abschlussarbeit:

- Publikation als eBook und Buch
- Hohes Honorar auf die Verkäufe
- Für Sie komplett kostenlos – mit ISBN
- Es dauert nur 5 Minuten
- Jede Arbeit findet Leser

Kostenlos Autor werden