Upload
selma-borchelt
View
113
Download
3
Embed Size (px)
Citation preview
FPGA Praktikum WS2000/2001
2.Woche:FPGA HintergrundReconfigurable Computing:
pattern matchingAufgaben
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 Gatter + 3KByte RAM für $ 8 100.000 Gatter + 8KByte RAM für $ 26 200.000 Gatter + 70KByte RAM für $ 420 300.000 Gatter + 36KByte RAM für $ 380 1.600.000 Gatter + 104KByte RAM für $6.000
Nächstes Jahr 10.000.000 Gatter
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
0
50
100
150
200
250
0 50 100
Gatter/1000
Pre
is/$
XC4000 (0,5/5V)
XC4000XL(0,35/3,3V)
XC4000XLA(0,35/3,3V)
Spartan (0,35/5V)
Spartan XL(0,25/3,3V)
Virtex (0,18/2,5V)
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
s0=
Z-1
+ Z-10
s1=
Z-1
+ Z-1
=
Z-1
+ Z-1
s2
+ Z-1
= s3
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
s0=
Z-1
+ Z-20
s1=
Z-1
+ Z-2
=
Z-1
+ Z-2
s2
+ Z-2
= s3
Takt 0 t0 0/01 t1 1/0 t0 0/12 t2 2/0 0/0 t1 0/0+1/1 t0
3 t3 3/0 1/0 t2 1/0+2/1 0/1 t1 t0
4 t4 4/0 2/0 t3 2/0+3/1 0/0+1/1 t2 0/2 t1
5 t5 5/0 3/0 t4 3/0+4/1 1/0+2/1 t3 0/1+1/2 t2 0/36 t6 6/0 4/0 t5 4/0+5/1 2/0+3/1 t4 0/0+1/1+2/2 t3 0/2+1/37 t7 7/0 5/0 t6 5/0+6/1 3/0+4/1 t5 1/0+2/1+3/2 t3 0/1+1/2+2/38 6/0 t7 6/0+7/1 4/0+5/1 t6 2/0+3/1+4/2 t4 0/0+1/1+2/2+3/39 7/0 5/0+6/1 t7 3/0+4/1+5/2 t5 1/0+2/1+3/2+4/310 8/0 6/0+7/1 t7 4/0+5/1+6/2 t6 2/0+3/1+4/2+5/3
Z-1
s0=
Z-1
+ Z-20
s1=
Z-1
+ Z-2
=
Z-1
+ Z-2
s2
+ Z-2
= s3
Beispiel
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_in (3:0)
h_in (2:0)
char_out (3:0)
h_out (2:0)
h_delay (2:0)
Bitte verwendet genau diese Namen!
zeichen (3:0)
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 = 1 1 + 1 = 2 2 + 1 = 3 ... 6 + 1 = 7 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