Anwendung und Optimierung eines Plazierungssystems für FPGAs basierend auf einem fuzzygesteuerten genetischen Algorithmus
- Art: Diplomarbeit
- Autor: Matthias Bodenstein
- Abgabedatum: Februar 1997
- Umfang: 178 Seiten
- Dateigröße: 5,3 MB
- Note: 1,0
- Institution / Hochschule: Technische Universität Carolo-Wilhelmina zu Braunschweig Deutschland
- ISBN (eBook): 978-3-8324-1763-5
-
ISBN (Paperback) :
978-3-8324-1763-5 P - ISBN (CD) :978-3-8324-1763-5 CD
- Sprache: Deutsch
- Prämierung:
- Arbeit zitieren: Bodenstein, Matthias Februar 1997: Anwendung und Optimierung eines Plazierungssystems für FPGAs basierend auf einem fuzzygesteuerten genetischen Algorithmus, Hamburg: Diplomica Verlag
- Schlagworte: Optimierung, Plazierungsproblem, Fuzzy-Regler, genetischer Algorithmus
In den Warenkorb
38,00 €
Diplomarbeit von Matthias Bodenstein
Einleitung:
Das Plazierungsproblem bei FPGA-Chips stellt eine interessante Optimierungsaufgabe dar, zu der es bislang noch keine optimale Lösungsstrategie gibt. Der FloorPlanner versucht das Problem durch Einsatz eines genetischen Algorithmusses (GA) zu lösen, dessen Parameter dynamisch durch einen Fuzzy-Regler gesteuert werden. Er wurde 1995 von HENRIK PUTZER im Rahmen einer Diplomarbeit entwickelt, konnte aber bisher nur wenig praktisch eingesetzt werden. Diese Arbeit hat nun das Ziel, diesen letzten Schritt zu vollenden, und den FloorPlanner praxistauglich zu machen. Das beinhaltet im Wesentlichen die folgenden Punkte:
- Implementierung der Güteberechnung für verschiedene Bewertungskriterien, mit denen sich eine konkrete Plazierung beurteilen läßt.
- Erweiterung der genetischen Operatoren des Gas.
- Optimierung des Fuzzy-Reglers.
- Test und Performancebeurteilung des optimierten Fuzzy-Reglers.
Zum Verständnis dieser Arbeit wird empfohlen, die zugrundeliegende Diplomarbeit [9] zu lesen, auf die an vielen Stellen verwiesen wird.
Gang der Untersuchung:
In Kapitel 2 werden alle neu implementierten Erweiterungen des FloorPlanners zusammengefaßt. Erstens ist das die Implementierung der Güteberechnungen für den aus insgesamt 8 Elementen bestehenden Bewertungsvektor.
In Kapitel 3 werden mit Hilfe von Tests die GA-Parameter für einen GA mit statischen Parameter optimiert. Dieser optimierte GA kann dann später für Vergleiche mit fuzzy-geregelten GAs verwendet werden, um den durch den Fuzzy-Regler erzielten Performancegewinn besser beurteilen zu können.
Kapitel 4 befaßt sich mit dem eigentlichen Kern dieser Arbeit, der Optimierung des Fuzzy-Reglers, wobei zwei verschiedene Strategien verfolgt werden sollen. Mit der ersten Strategie sollen einzelne Fuzzy-Regeln bzw. kleine Mengen von Fuzzy-Regeln einzeln darauf getestet werden, ob ihr Einsatz lohnenswert ist. Der optimierte Fuzzy-Regler setzt sich dann aus der Kombination der im Test erfolgreichen Einzelregeln zusammen.
Bei der zweiten Strategie wird hingegen der Fuzzy-Regler intuitiv manuell zusammengesetzt und gegebenenfalls noch weiter optimiert.
In Kapitel 5 werden schließlich die gewonnenen Ergebnisse interpretiert und ein Ausblick für den weiteren Einsatz des FloorPlanners gegeben.
Inhaltsverzeichnis:
| 1. | Einleitung | 1 |
| 1.1 | Das Plazierungsproblem | 2 |
| 2. | Erweiterungen des FloorPlanners | 5 |
| 2.1 | Der Bewertungsvektor | 5 |
| 2.1.1 | Die besten Netze | 5 |
| 2.1.2 | Die schlechtesten Netze | 6 |
| 2.1.3 | Güte aller Netze | 6 |
| 2.1.4 | Packgüte | 6 |
| 2.1.5 | Bestrafung für zu große Designs | 8 |
| 2.1.6 | Bestrafung für Nichtroutbarkeit | 8 |
| 2.1.7 | Die gewichtete Summe | 8 |
| 2.1.8 | Normierung der Teilbewertungen | 9 |
| 2.2 | Neue genetische Operatoren | 10 |
| 2.2.1 | Translokation | 10 |
| 2.2.2 | Invertierung | 11 |
| 2.3 | Sonstige Erweiterungen | 12 |
| 2.3.1 | Mutationsraten > 1 | 12 |
| 2.3.2 | Auswertung der Fuzzy-Regler Ausgabe | 12 |
| 3. | Optimierung der GA-Parameter | 13 |
| 3.1 | Vorgehensweise | 13 |
| 3.2 | Reproduzierbarkeit von Ergebnissen | 14 |
| 3.3 | Durchführung der GA-Optimierung | 16 |
| 3.3.1 | Normierung der Teilbewertungen | 16 |
| 3.3.2 | SNF-Datei Auswahl | 18 |
| 3.3.3 | Test einzelner genetischer Operatoren | 19 |
| 3.3.4 | Kombination von Mutation und Crossing-Over | 22 |
| 3.3.5 | Gewichtung der genetischen Operatoren | 24 |
| 3.3.6 | Einstellung der Intensität | 25 |
| 3.3.7 | Rechenzeit des GAs | 26 |
| 3.3.8 | Einstellung der Populationsgröße | 28 |
| 4. | Optimierung des Fuzzy-Reglers | 31 |
| 4.1 | Vorgehensweise | 31 |
| 4.1.1 | Optimierungsstrategien | 32 |
| 4.1.2 | Einzelschritte der Optimierung | 34 |
| 4.2 | Umrechnung der Fuzzy-Ausgabevariablen | 35 |
| 4.3 | Analyse der Chromosomen | 39 |
| 4.4 | Partitionierung der Fuzzy-Variablen | 44 |
| 4.5 | Defuzzyfizierung | 45 |
| 4.6 | Randbedingungen der Tests | 46 |
| 4.7 | Test des neutralen Fuzzy-Reglers | 48 |
| 4.8 | Test einzelner Fuzzy-Regeln | 52 |
| 4.8.1 | Test 1 | 53 |
| 4.8.2 | Test 2 | 63 |
| 4.8.3 | Test 3 | 69 |
| 4.8.4 | Test 4 | 80 |
| 4.8.5 | Ergebnisse der Tests 1 bis 4 | 87 |
| 4.9 | Test von Fuzzy-Reglern | 88 |
| 4.9.1 | Test 5 (merge.fcd) | 89 |
| 4.9.2 | Test 6 (fuzzyl.fcd) | 92 |
| 4.9.3 | Test 7 (simple.fcd) | 97 |
| 4.9.4 | Test 8 (shockwave.fcd) | 100 |
| 4.9.5 | Ergebnisse der Tests 5 bis 8 | 104 |
| 4.10 | Rücktests mit dem optimierten Fuzzy-Regler | 105 |
| 4.10.1 | Test 9.1 (neutral.fcd) | 107 |
| 4.10.2 | Test 9.2 (merge.fcd ) | 111 |
| 4.11 | Überprüfung der Validität der Ergebnisse | 115 |
| 4.12 | Ergebnisse der Optimierung | 118 |
| 5. | Abschließende Bemerkungen | 119 |
| 5.1 | Erweiterungsmöglichkeiten des FloorPlanners | 119 |
| 5.1.1 | Reichweiten von Mutationsoperatoren | 119 |
| 5.1.2 | Defuzzyfizierung | 120 |
| 5.1.3 | Die Schockwellenstrategie | 120 |
| 5.2 | Ausblick | 121 |
| 5.3 | Weiteres Vorgehen | 121 |
| A. | SNF-Dateien | 123 |
| A.1 | addroddlow.snf | 123 |
| A.2 | alu.snf | 126 |
| A.3 | dpregs.snf | 131 |
| B. | Fuzzy-Regler | 134 |
| B.1 | neutral.fcd | 134 |
| B.2 | merge.fcd | 139 |
| B.3 | fuzzy1.fcd | 144 |
| B.4 | simple.fcd | 150 |
| B.5 | shockwave.fcd | 157 |
| C. | Hilfsprogramme | 162 |
| C.1 | minmaxdur.cc | 162 |
| C.2 | standabw | 162 |
| C.3 | multi2fp | 162 |
| C.4 | chparam.cc | 163 |
| C.5 | autofp | 163 |
| D. | Fehler im System | 164 |
| D.1 | Ein PARAMOG-Fehler | 164 |
| E. | Die beigelegte Diskette | 165 |
In den Warenkorb
38,00 €
Link zur Arbeit:
http://www.diplom.de/ean/9783832417635
Arbeit zitieren:
Bodenstein, Matthias Februar 1997: Anwendung und Optimierung eines Plazierungssystems für FPGAs basierend auf einem fuzzygesteuerten genetischen Algorithmus, Hamburg: Diplomica Verlag
Schlagworte:
Optimierung, Plazierungsproblem, Fuzzy-Regler, genetischer Algorithmus
Entdecken Sie mehr zum Thema
