FPGA Praktikum
WS2000/2001
2.Woche:
FPGA Hintergrund
Reconfigurable Computing:
pattern matching
Aufgaben
Was ist ein FPGA?
 In den nächsten Wochen werde ich genauer auf die
Architektur von FPGAs eingehen.
 Bis dahin ist ein FPGA einfach eine Zieltechnologie in der
sich Schaltungen realisieren lassen, die z.B. in einer
Hardwarebeschreibungssprache entwickelt wurden.
 Im folgenden erläutere ich die Bedeutung von FPGAs im
Vergleich zu den anderen verbreiteten Zieltechnologien.
Zieltechnologien
 ASIC
 Gate Array
 FPGA
Einmal programmierbar
mehrmals programmierbar
dynamisch rekonfigurierbar
ASIC
 Application Specific Integrated Circuit
 Ein vollständig nach Kundenwunsch hergestellter
Schaltkreis
 Hohe Einstiegskosten
DM 5.000 für 2µm Technologie, multi project wafer
DM 500.000 für 0.13 µm Technologie
 Niedrige Produktionskosten
tausende von Chips auf einem Wafer für DM 2000 - DM 6000
ASIC
 Alle Freiheitsgrade der Technologie können zur
Optimierung genutzt werden
 Beste Implementierung für eine fest vorgegebene
Schaltung
 Fehlerbehebung und nachträgliche Änderungen oder
Optimierungen sind sehr teuer
 Der Chip muß so entworfen werden, daß er in allen in
Frage kommenden Anwendungen verwendet werden
kann.
 Einsatzbereich: Standardschaltungen mit hohen
Stückzahlen. (Prozessoren, Speicher, FPGAs, ...)
Gate Array
 Beim Gate Array werden die meisten
Herstellungsschritte kundenunabhängig durchgeführt.
 Die Lage der IO-Pads, Transistoren, etc. sind
standardisiert, der Kunde kann nur noch die
Verdrahtung beeinflussen.
 Dadurch bleiben auch bei modernsten Technologien die
Einstiegskosten unter DM 100.000
 Die Produktionskosten sind mit denen von ASICs
vergleichbar.
Gate Array
 Die Vor- und Nachteile sind denen von ASICs sehr
ähnlich, allerdings weniger gravierend:
 Der Kunde kann alle elektrischen Optimierungen
vornehmen, hat jedoch keine detaillierte Kontrolle über
das Layout.
 Änderungen sind etwas weniger kosten- und
zeitintensiv.
 Gate Arrays verlieren zur Zeit deutlich Marktanteile an
ASICs und FPGAs
FPGAs
 Field Programmable Gate Arrays
 Bei FPGAs wird der Chip so gefertigt, daß die Schaltung
vom Kunden selbst bestimmt werden kann. Und zwar
entweder:
einmalig (Antifuse: Quicklogic)
mehrmals (Flash: Actel)
dynamisch, im System
(SRAM: Actel, Altera, Atmel, DynaChip, Lucent, Xilinx)
FPGAs: Antifuse
 Chip wird durch das gezielte Brennen von
Schmelzbrücken konfiguriert und kann danach nicht
mehr verändert werden.
 Fast keine Einstiegskosten, dafür höhere
Produktionskosten als beim ASIC
 Fehlerbehebung und Updates sind für neu ausgelieferte
Platinen problemlos möglich. Bereits produzierte Chips
können jedoch nicht mehr verändert werden.
 Einsatzbereich: ASIC Ersatz für kleinere Stückzahlen
FPGAs: Flash
 Flash oder EPROM basierte FPGAs lassen sich einige
tausend mal neu konfigurieren, behalten aber ihre
Konfiguration auch ohne Stromversorgung
 Mit geringem zusätzlichem Schaltungsaufwand lassen
sich Updates beim Kunden ausführen
 Die einzige existierende FPGA Familie mit dieser
Technologie ist leider recht teuer (Actel proASIC)
 Das ändern der Konfiguration ist relativ langsam
(mehrere Sekunden)
FPGAs: SRAM
 Zur Zeit dominierende Technologie.
 Beim einschalten des Systems wird die Konfiguration aus
einem externen Speicher in den FPGA geladen.
 Es werden zusätzliche externe Komponenten benötigt.
 Der Chip kann beliebig oft und sehr schnell
umkonfiguriert werden.
 Bei einigen FPGA-Familien auch teilweise und während
des Betriebs.
FPGAs: SRAM
 SRAM basierte FPGAs haben dadurch neben dem Update
beim Kunde noch weiter Möglichkeiten:
 Anpassen der Schaltung auf eine Probleminstanz (z.B.
eine Schaltung, die nach einem speziellen DNA-Muster
sucht)
 Die Verwendung mehrerer Schaltungen nacheinander in
der selben Hardware.
 Laden der neuesten Konfiguration über ein Netzwerk.
(wie z.B. beim Handy)
 Buzzword: Reconfigurable Computing
Wie groß sind FPGAs?
 Zur Zeit:

8.000
 100.000
 200.000
 300.000
 1.600.000
Gatter
Gatter
Gatter
Gatter
Gatter
+
3KByte
+
8KByte
+ 70KByte
+ 36KByte
+ 104KByte
 Nächstes Jahr 10.000.000 Gatter
RAM
RAM
RAM
RAM
RAM
für
für
für
für
für
$
8
$
26
$ 420
$ 380
$6.000
Wie schnell ist so ein FPGA?
 Anwendungsbeispiele für Virtex-E FPGAs
 32 Bit Prozessoren:
20-40 MHz synthetisiert, single cycle
50-75 MHz synthetisiert, pipeline
über 100 MHz machbar wenn wirklich gute Designer viel Grips
hineinstecken
 200 MHz DDR SRAM Controller
 622 Mbps serieller Link
Welche FPGA Familie ist die
beste für mich?
 Die Unterschiede zwischen den Herstellern werde ich in
den nächsten Wochen erläutern.
 Ansonsten gilt in der Regel: Für ein neues Projekt immer
die neueste FPGA Familie verwenden
 Das liegt daran, daß FPGAs sehr große Chips sind, und
große Chips lassen sich in kleineren Technologien billiger
herstellen.
Neuer ist billiger
250
XC4000
(0,5/5V)
Preis/$
200
XC4000XL
(0,35/3,3V)
150
XC4000XLA
(0,35/3,3V)
Spartan
(0,35/5V)
100
50
Spartan XL
(0,25/3,3V)
0
Virtex
(0,18/2,5V)
0
50
Gatter/1000
100
Virtex-E
(0,15/1,8V)
Spartan II
(0,18/2,5V)
Und wer hat den schnellsten?
 Es gibt eine Webseite die sich mit diesem Problem
befaßt:
 http://rk.gsfc.nasa.gov/richcontent/MAPLDCon99/
K-Bowl/K-Bowl.htm
 Hier sind die Ergebnisse:
Actel
Altera
Dynachip
Quicklogic
Vantis
Xilinx
Reconfigurable Computing
Reconfigurable Computing
 Bei den meisten FPGA Designs werden die FPGAs wie
ASICs verwendet.
 Die Konfiguration des Chips bleibt unverändert, mit der
möglichen Ausnahme eines field upgrades
 Einige Designer nutzen jedoch die inherente Parallelität
von FPGAs, um bestimmte Algorithmen schneller als in
einem konventionellen Prozessor durchzuführen.
 Insbesondere die Möglichkeit, die Schaltung durch
schnelle Rekonfiguration an jede Probleminstanz
anzupassen, ist dabei sehr nützlich.
Erfolge
 Schaltungssimulation
 Fehlersimulation und Testmustergenerierung
 Code Entschlüsselung: DES, RSA, ...
Colossus II von 1945 kann noch immer mit der Rechenleistung
heutiger PCs mithalten (5000 Zeichen/s)
 DNA-Sequenzierung (pattern matching)
Beispiel: DNA pattern matching
 SPLASH, 1990
 32 Chips Xilinx XC3090
ca. 400.000 Gatter
 300-fache Leistung eines Cray-II
 200-fache Leistung einer Connection Machine CM-2 mit
16.000 Prozessoren
Zum nachlesen
 "Building and Using a Highly Programmable Logic Array".
Maya Gokhale et. al., IEEE Computer 24(1):81-89, Januar 1991
 „Searching Genetic Databases on SPLASH-2“ (PDF)
Dzung T. Hozang, Proceedings of FPGAs for Custom Computing
Machines (FCCM), 1993
 Kommerzielle FPGA basierte DNA Analyse wird z.B. von
Timelogic und Compugen vermarktet
Smith-Waterman Algorithmus
 Berechnen des Hammingabstandes einer um i
verschobenen, kurzen Sequenz s in einer langen
Sequenz t
 Abstand d zweier Zeichen:
d(a,b) = 0 wenn a=b
d(a,b) = 1 sonst
 Hammingabstand der Sequenzen
H(i) = d(t(1+i),s(1)) + d(t(2+i),s(2)) +...+ d(t(n+i),s(i))
Systolische Implementierung
 Die lange Zeichenkette t wird durch eine Kette von
Zellen geschoben, die je ein Zeichen von s Speichern.
 In jedem Schritt i kann also alle Zellen j parallel den
Wert von d(t(j+i), s(j)) berechnen.
 Einen solchen Algorithmus bei dem jedes Element nur
über eine konstante Entfernung mit anderen Elementen
kommuniziert nennt man systolisch
Vergleich mit lokal gespeicherten Wert
weiterreichen von t an die Nachbarzelle
 Aber wie wird die Summe berechnet?
Berechnung der Summe
 Zur Berechnung der Hammingdistanz müssen die
Einzelabstände aller Zellen aufsummiert werden
 Ein Baum von Addierern würde die Bedingung für
systolische Algorithmen verletzen und sehr stark
bremsen
Erster Versuch
 Ansatz: Die lokale Differenz wird zum Zwischenergebnis
des Nachbarn addiert und ebenfalls weitergereicht.
Ergibt: H(1) = d(s(1),t(1)) + d(s(2), t(1)) + d(s(3), t(1)) ...
Z-1
Z-1
s0
=
0
+
Z-1
Z-1
s1
=
+
Z-1
Z-1
s2
=
+
Z-1
s3
=
+
Z-1
Zeiter Versuch
 Trick: Wenn die Teilummen mit der halben
Geschwindigkeit wandern ergibt sich wie gewünscht
H(1) = d(s(1), t(1)) + d(s(2), t(2)) + d(s(3), t(3))
Z-1
Z-1
s0
=
0
+
Z-2
Z-1
s1
=
+
Z-2
Z-1
s2
=
+
Z-2
s3
=
+
Z-2
Beispiel
Z-1
Z-1
s0
=
0
Takt 0
1
2
3
4
5
6
7
8
9
10
+
t0
t1
t2
t3
t4
t5
t6
t7
0/0
1/0
2/0
3/0
4/0
5/0
6/0
7/0
s1
=
+
Z-2
0/0
1/0
2/0
3/0
4/0
5/0
6/0
7/0
8/0
Z-1
t0
t1
t2
t3
t4
t5
t6
t7
0/1
0/0+1/1
1/0+2/1
2/0+3/1
3/0+4/1
4/0+5/1
5/0+6/1
6/0+7/1
s2
=
+
Z-2
0/1
0/0+1/1
1/0+2/1
2/0+3/1
3/0+4/1
4/0+5/1
5/0+6/1
6/0+7/1
Z-1
t0
t1
t2
t3
t4
t5
t6
t7
t7
+
Z-2
0/2
0/1+1/2
0/0+1/1+2/2
1/0+2/1+3/2
2/0+3/1+4/2
3/0+4/1+5/2
4/0+5/1+6/2
s3
=
t0
t1
t2
t3
t3
t4
t5
t6
Z-2
0/3
0/2+1/3
0/1+1/2+2/3
0/0+1/1+2/2+3/3
1/0+2/1+3/2+4/3
2/0+3/1+4/2+5/3
Aufgaben für diese Woche
Bau und Simulation einer
Smith-Waterman Zelle
 Vergleich von Aminosäuren
 4 Bits zum Kodieren der Sequenzen t und s
 Hammingdistanz h mit 3 Bits
 Verzögerungselemente sind D-Flip-Flops
 Ladbares Zeichen s(i)
Port Deklaration
clk
load
char_out (3:0)
char_in (3:0)
zeichen (3:0)
h_in (2:0)
h_delay (2:0)
h_out (2:0)
Bitte verwendet genau diese Namen!
Erläuterungen
 char_in ist die Eingabe für die Zeichen der langen
Zeichenkette
 char_out ist char_in um einen Takt verzögert
 h_in ist die Zwischensumme von der Vorgängerzelle
 h_delay ist h_in + d(zeichen, char_in) um einen Takt
verzögert
 h_out ist h_delay um einen Takt verzögert
 wenn bei der steigenden Flanke von clk load=1 ist, wird
in zeichen der Inhalt von char_in gespeichert
Addition mit Sättigung
 Die 3 Bit für die Zwischensumme können nur Zahlen
von 0 bis 7 aufnehmen
 Addition mit Sättigung (Kein Überlauf)
0 +
1 +
2 +
 ...
6 +
7 +
1 = 1
1 = 2
1 = 3
1 = 7
1 = 7
 case h_in
when “000“ =>
h_delay <= “001“
Aufgabe
 Entwerft die Zelle im VHDL Editor
VHDL Wizard verwenden
Schaut euch die VHDL Tips vom letzten mal an
Language Assistant verwenden
Quelltext kommentieren
 Synthetisiert die Zelle
 Simuliert sie mit diesem Simulationsskript
Verhält sich die Zelle wie erwartet?
 Gebt per Email den VHDL Quelltext und einen
Screenshot der Simulation ab

Präsentationsquelle herunterladen