Optimierung auf rekonfigurierbaren Rechensystemen

Transcrição

Bad Driburg, 2. Juli 2004
Zwischenkolloquium SPPRR
Opt im ierung auf
rekonfigurierbaren Rechensyst em en
M. Ghiath Khatib
Bernd Scheuermann
Hartmut Schmeck
Institut für Angewandte Informatik
und Formale Beschreibungsverfahren
Universität Karlsruhe (TH)
Mohammed Ghiath Khatib, Bernd Scheuermann, Hartmut Schmeck
Institut AIFB, Universität Karlsruhe (TH)
Gliederung
Gliederung
Einführung
Arbeit sprogram m
Ant Colony Opt im izat ion ( ACO)
ACO I m plem ent ierung auf FPGA
Zusam m enfassung, nächst e Schrit t e
2
Einführung
Einf ü hrung
Viele Optimierungsprobleme aus der Anwendungspraxis sind
NP- vollständig
Beispiele
Traveling Salesperson Problem (TSP)
– Quadratic Assignment Problem (QAP)
– Scheduling Probleme
– Placement and Routing
–
Algorithmen für solche Optimierungsprobleme umfassen:
–
exakte Verfahren (exponentielle Laufzeit)
•
•
•
–
Vollständige Enumeration
Branch and Bound/Cut
…
heuristische/probabilistische Verfahren (polynomielle Laufzeit)
•
•
•
•
Greedy- Verfahren
Naturanaloge Metaheuristiken
Tabu Search
…
3
Einführung
Möglichkeiten zur Verbesserung der Rechenleistung
–
Parallelisierung von Software zur Ausführung auf Parallelrechnern
–
Implementierung in Hardware (z.B. FPGAs, ASICs…). Ausnutzung
von Parallelität, Pipelining und ggf. dynamischer Rekonfiguration.
Betrachtung dynamisch veränderlicher Optimierungsprobleme
–
–
Änderung problembezogener Parameter zur Laufzeit, z.B.
•
Anzahl der Städte, Fahrzeiten in TSP
•
Vorgangsdauern beim Scheduling
Anforderung
•
•
–
Optimierungslauf nicht erneut starten
keine grundsätzlich neue HW- Implementierung
Stattdessen:
•
•
modifiziere aktuelle Lösungen und setze Optimierungslauf fort
dynamische, partielle Rekonfiguration der Hardware
4
Arbeitsprogramm
Arbeit sprogram m
Untersuchung des Potenzials dynamisch rekonfigurierbarer
Rechensysteme als Plattform für Optimierungsverfahren
Untersuchte Aspekte:
Effiziente Hardware- Realisierung von Optimierungsverfahren
– Entwurf von Sprachen und Modellen für den Entwurf von
Optimierungsverfahren auf dynamisch rekonfigurierbaren
Rechensystemen
– Ausnutzung dynamischer Rekonfiguration mit den Zielen:
–
•
•
–
Beschleunigung der Optimierungsverfahren
Anpassbarkeit der Hardware- Implementierung bei dynamischen
Problemänderungen
Schwerpunkt: Ameisenalgorithmen
Kooperationen:
Martin Middendorf, Universität Leipzig
– Hossam ElGindy, Oliver Diessel, University of New South Wales,
Sydney
–
5
Ant Colony Optimization
Ant Colony Opt im izat ion ( ACO)
Ant Colony Optimization (Ameisenalgorithmus)
inspiriert durch das Verhalten von Ameisen bei der Nahrungssuche
–
–
Goss, Aron, Deneubourg and Pasteels: 1989
Beckers, Deneubourg and Goss: 1992
Betrachtung in der Natur:
Ameisen erkunden anfangs
beide Wege.
Sie finden und bevorzugen
den kürzesten Weg.
Nest
Distanzen sind nicht bekannt.
Eingeschränktes
Sehvermögen
Nahrungsquelle
6
Erklä rung
Am eisen deponieren Duft st offe auf ihren Wegen
Am eisen bevorzugen Wege m it hoher Duft st offkonzent rat ion
Nest
Nahrungsquelle
7
Erklä rung
Am eisen deponieren Duft st offe auf ihren Wegen
Am eisen bevorzugen Wege m it hoher Duft st offkonzent rat ion
Duftstoffkonzentrationen unterliegen ständigen Schwankungen
Ameisen erneuern Duftstoffe
– Duftstoffe verdunsten
–
Nest
Nahrungsquelle
8
Standard ACO
Dorigo et al.: 1992/96/99
1
Items j
2 3 4
5
Plät ze i
1
2
3
ij
Suche nach guten Lösungen, z.B.
• Auftragsreihenfolge einer Maschine
• repräsentiert durch Permutationen von n Items.
Beispiel:
Items (2, 5, 3, 1, 4)
Plätze [1, 2, 3, 4, 5]
4
5
Duftstoffmatrix
Lösungserzeugung:
Folge von lokalen Entscheidungen
Markierung „ guter“ Entscheidungen durch
„ Duftstoffe“
9
Standard ACO
Lösungserzeugung: Folge von lokalen Entscheidungen
1
Items j
2 3 4
5
Auswahlmenge S
2
3
4
5
p1 j
1
Plät ze i
1
2
3
0
1
Zufallszahl r
4
5
Duftstoffmatrix
Für einen gegebenen Platz i wählt eine Ameise
Item j gemäß
ij
pij
ij
ih
ih
h S
10
Standard ACO
1
Items j
2 3 4
5
Plät ze i
1
Auswahlmenge S
2
4
5
p2 j
2
3
1
ij
4
0
1
5
Duftstoffmatrix
Item j gemäß
ij
pij
ij
ih
ih
h S
11
Standard ACO
1
Items j
2 3 4
5
Plät ze i
1
2
3
Auswahlmenge S
ij
1
2
4
p3 j
4
5
0
1
Duftstoffmatrix
Item j gemäß
ij
pij
ij
ih
ih
h S
12
Standard ACO
1
Items j
2 3 4
5
Plät ze i
1
2
3
ij
Auswahlmenge S
2
4
p4 j
4
5
Duftstoffmatrix
0
1
Item j gemäß
ij
pij
ij
ih
ih
h S
13
Standard ACO
1
Items j
2 3 4
5
Plät ze i
1
Neue erzeugte Lösung (3, 5, 1, 2, 4)
2
3
ij
4
Auswahlmenge S
4
p5 j
5
Duftstoffmatrix
0
1
Item j gemäß
ij
pij
ij
ih
ih
h S
14
Standard ACO
1
Items j
2 3 4
nach der Generierung von m Lösungen
5
Plät ze i
1
Pheromone Update:
Globale Verdunstung aller Duftstoffwerte:
2
3
ij
4
Erhöhung der Duftstoffwerte entlang der
besten Lösung :
5
Duftstoffmatrix
Wiederholen bis ein Abbruchkriterium erfüllt ist
Neue erzeugte Lösung
( 3, 5, 1, 2, 4)
15
Warum Am eisenalgorit hm en auf FPGAs?
Ameisenalgorithmen wurden erfolgreich für eine Vielfalt von
Optimierungsproblemen eingesetzt:
Quadratic Assignment Problem
– Scheduling- Probleme: Beste Ergebnisse für „ Resource Constrained
Project Scheduling Problem (RCPSP)“ , Merkle et al. 2000
– Vehicle Routing
– …
–
Besonderheiten von Ameisenalgorithmen:
–
–
–
–
–
Metaheuristisches Verfahren
Iterative Struktur
Akkumulierte Information über früheres Entscheidungsverhalten
Aktuell beste Lösungen jederzeit abrufbar
Häufig lange Rechenzeiten
16
Warum Am eisenalgorit hm en auf FPGAs?
Zusammenhang ACO, rekonfigurierbare Hardware
Problemlösung: Ameisen passen ihr Verhalten an ihre Umwelt an.
– Problemveränderung: Ameisen reagieren dynamisch auf
Veränderungen.
Abbildung dynamischer Veränderungen in dynamisch
rekonfigurierbare Hardware
–
Beispiele für metaheuristische Verfahren auf rekonfigurierbarer
Hardware:
–
Genetische Algorithmen, Implementierung auf…
•
•
Custom computing machines:
Graham et al. 1995/96 (Splash 2), Sitkoff et al. 1995 (ARMSTRONG)
FPGA: Scott et al. 1995/97, Bland et al. 1996/97, Kajitani 1998,
Aporntewan et al. 2001, Lei et al. 2002
Simulated Annealing auf FPGA: Abramson et al. 1998
– ACO auf RMesh: Merkle und Middendorf 2001
–
17
Problem e bei FPGA I m plem ent ierung von St andard ACO
Intuitiver Ansatz
Einhalten der Ressourceneinschränkungen der
Zielarchitektur:
–
–
–
FPGA
Rechenressourcen
Speicherressourcen
I/O Ressourcen
nxn
Duftstoff
Matrix
St andard ACO kann nicht problem los auf FPGA
implementiert werden
–
–
Verdunstung benötigt zahlreiche Multiplikationen
Berechnung der Auswahlwahrscheinlichkeiten
erfordert Präfixsummenberechnung für jede Zeile
Hoher Ressourcenbedarf
Lösungsvorschlag:
Variante des Standard ACO
„ Population- based Ant Colony Optimization“ (PACO)
18
ACO Implementierung auf FPGA
ACO I m plem ent ierung auf FPGA
Population- based ACO (PACO)
Testergebnisse ohne Heuristikunterstützung
Heuristikerweiterung
Testergebnisse mit Heuristikerweiterung
19
Population- based ACO (PACO) auf FPGA
Populat ion - based ACO ( PACO)
Guntsch und Middendorf 2002
Idee: - verwalte eine Population von k guten Lösungen
- Population ersetzt die Duftstoffmatrix
items j
2
5
3
3
item
1
1
3
3
1
2
2
3
5
1
2
3
4
4
4
4
1
2
1
5
4
5
5
1
2
2
5
Population
(hier k=3)
1
2
3
4
5
transform
4
3
Duftstoffmatrix
Duftstoff
Initialwert I
Plat z i
Plat z i
Lösung h
1,…, k
Duftstoff
Update- Wert
20
PACO Archit ekt ur auf FPGA
Lösungsqualitäten
Lösungen
Populat ions- Updat e
Populationsmodul
Generatormodul
Evaluationsmodul
Lösungsgenerator 1
Evaluation 1
Lösungsgenerator 2
Evaluation 2
Lösungsgenerator m
Evaluation m
Population
Vergleich
items
Beste Lösung der Iteration
21
Vergleich PACO vs. St andard ACO
PACO
Standard ACO
Komplexität pro Iteration
(Basis: SW, eine CPU)
O(kmn)
O(mn2 )
FPGA Ressourcenbedarf
O(mn log(n))
O(n 2 log(n))
Datentypen
Ganze Zahlen
Gleitpunktzahlen
PräfixsummenBerechnungen
keine
Für jede Entscheidung
PACO ist besser geeignet für eine FPGA- Implementierung
PACO biet et eine vergleichbare/ bessere Leist ung
als St andard ACO ( Gunt sch und Middendorf 2002)
22
Exkurs: Heurist ikunt erst ü t zung
Die Entscheidungen von Ameisen basieren auf
–
–
Duftstoffinformationen/Populationsdaten
Heuristische Informationen
Standard- Heuristik
ij
z.B. Traveling Salesperson Problem (TSP)
ij
1
dij
mit d ij = Distanz zwischen Stadt i und Stadt j
Auswahlwahrscheinlichkeiten:
ij
pij
ij
ih
ih
h S
Probleme bei der FPGA- Implementierung:
–
–
–
Schlechte Unterstützung Multiplikationen/Potenzberechnungen
Heuristikwerte i.d.R. Gleitpunktzahlen
Kombination der Heuristikdaten mit Populationsdaten
23
Test ergebnisse ohne Heurist ikunt erst ü t zung
Hier noch keine Verarbeit ung heurist ischer I nform at ion.
Ent scheidungen basieren nur auf Populat ionsdat en.
Parametereinstellungen für experimentelle
Untersuchungen:
– Populationsgröße k=3
– Zusätzliche Elitelösung => k´ =4
– Zielarchitekturen:
• Hardware- Variante: Xilinx Virtex 2 pro
• Software- Variante: 1540 MHz AMD Athlon PC
24
Laufzeit vergleich Hardware/ Soft ware - Variante
(A) Fixe Anzahl Lösungsgeneratoren (m=8)
Laufzeitvergleich Hardware vs. Software
Beschleunigung Hardware/Software
500
5
PACO Software
PACO Hardware
400
4
350
Beschleunigung
Zeit pro Iteration [ sec]
450
300
250
200
150
100
3
2
1
50
0
0
40
64
128
192
256
Größe der Probleminstanz (n)
320
40
64
128
192
256
Größe der Probleminstanz (n)
320
25
Laufzeit vergleich Hardware/ Soft ware - Variante
(B) Fixe Größe der Probleminstanz (n=64)
Laufzeitvergleich Hardware vs. Software
Beschleunigung Hardware/Software
350
PACO Software
PACO Hardware
300
10
250
Beschleunigung
Zeit pro Iteration [ sec]
12
200
150
100
8
6
4
2
50
0
0
2
4
8
12
16
24
Anzahl Lösungsgeneratoren (m)
32
2
4
8
12
16
24
Anzahl Lösungsgeneratoren (m)
32
26
Heurist ikerweit erung
Zeitverteilte Heuristik (Scheuermann et al. 2004)
Idee: Transformation heuristischer Information ij
in ganzahlige zeitlich wechselnde Heuristikvektoren
z.B. Traveling Salesperson Problem (TSP) mit n=8 Städten
Zeile i der Heuristikmatrix ij
i
Stadtindex
8,5
0,0
4,3
3,7
4,8
7,6
2,1
1,7
1
2
3
4
5
6
7
8
4
1
3
1
aktiver Vektor =>
1
3
6
5
4
7
6
l Heuristikvektoren
6
c
27
I nt egrat ion in best ehende Archit ekt ur
Populations- /Heuristikmodul
Populat ions- Updat e
1
Population
1
5
8
3 4 6
1 Heuristik
2
5
5
Generatormodul
Evaluationsmodul
5
Laufzeitkomplexität pro Iteration O((c+k)n), vs. O(kn) ohne Heuristik.
28
Test ergebnisse m it Heurist ikerweit erung
Parametereinstellungen der Softwaresimulationen:
Traveling Salesperson Problem (TSP)
TSPLIB Benchmark- Instanzen
Populationsgröße k=3
Zusätzliche Elitelösung => k´ =4
l=48 Heuristikvektoren der Größe c=3 (gute Kombination)
20 Wiederholungen
Zeitmessungen auf PCs mit 1,5 GHz Pentium 4 Prozessor
29
Vergleich zeitverteilte Heuristik vs.
Standard Heuristik und Candidate Lists
PACO- ZVH
PACO- SH
PACO- CL
TSP
TT[s]
AVG
TI[ms]
AVG
TI[ms]
AVG
TI[ms]
gr48
562,0
5099,45
0,567
5075,85
5,620
5075,45
2,603
eil101
2432,4
645,40
1,258
649,99
24,324
647,37
5,576
d198
9215,4
15942,83
2,414
15927,80
92,154
15970,00
11,418
rd400
39483,4
16553,78
4,962
15557,17
394,834
15483,90
23,778
ry48p
562,0
14547,70
0,533
14554,95
5,620
14518,45
2,603
ft70
1176,1
39071,65
0,801
39150,45
11,761
39189,65
3,917
kro124p
2377,9
36836,50
1,134
37057,75
23,779
37227,30
5,564
ftv170
6884,3
2836,05
1,134
2858,10
68,843
2866,70
9,981
ZVH: Zeitverteilte Heuristik
SH: Standard- Heuristik
CL: Candidate Lists
AVG: Durchschnittl. Tourlänge
TT: Gesamtlaufzeit pro Simulation
TI: Laufzeit pro Iteration
30
Zusammenfassung, nächste Schritte
Zusam m enfassung
Hardware- I m plem ent ierung eines Am eisenalgorit hm us auf FPGA
Redukt ion des Ressourcenbedarfs durch PACO anst elle von
Standard- ACO
Beschleunigung gegenüber Software- Variante durch
Parallelisierung und Pipelining
Effiziente Integration heuristischer Information
Nä chst e Schrit t e
Hardware- Implementierung der Heuristik
Generisches Framework für Ameisenalgorithmen auf FPGA
Ausnut zen dynam ischer Rekonfigurat ion zur
–
Beschleunigung des Verfahrens
–
Anpassung an dynamische Problemänderungen
31
Vielen Dank f ü r
ihre Aufm erksam keit
weitere Informationen:
www.aifb.uni- karlsruhe.de/optrek
32

Optimierung auf rekonfigurierbaren Rechensystemen

Transcrição

Documentos relacionados

Westfalenblatt 03.02.14

Widerrufsformular

Groß- und Kleinschreibung (Hahn)

Touren-Beschreibung

Angebot für begleitpersonen www.cAspAr-heinrich

Flyer - Evangelische Frauenhilfe in Westfalen eV

Leonardo Glass Cube

Mit dem Neujahrsturnier des TuS Bad Driburg

Turn- und Sportverein Bad Driburg 1893 e.V.

Samstag - Schnelle Schwaben