FPGA Praktikum WS2000/2001 2.Woche: FPGA Hintergrund Reconfigurable Computing: pattern matching...

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