Dirk Stroobandt is hoofddocent aan de vakgroep Elektronica en Informatiesystemen (Elis) van de faculteit Ingenieurswetenschappen aan de Universiteit Gent. Onder zijn promotorschap werkt Karel Bruneel aan het onderzoek van runtime herconfiguratie. Hij zal op dit onderwerp doctoreren aan de Universiteit Gent.

13 June 2008

Herconfiguratie van FPGA‘s tijdens de werking (runtime) is al enige tijd technisch mogelijk. Toch gebruikt de industrie die mogelijkheid in de praktijk zeer weinig omdat het aanmaken van elke gespecialiseerde implementatie veel te veel tijd in beslag neemt. De Universiteit Gent ontwikkelde een methode om af en toe variërende parameters aan te passen tijdens de werking en hiervoor toch een geoptimaliseerde hardwareoplossing aan te bieden. De aanpak kan zonder veel kwaliteitsverlies vijf grootteordes sneller een nieuw ontwerp aanmaken dan de klassieke technieken.

FPGA‘s bestaan uit enkele duizenden tot meer dan 200 duizend logische elementen in de nieuwste Xilinx Virtex-5-reeks. Elk van deze elementen (lookup tables, LUT‘s) kan iedere mogelijke functie van vier variabelen bevatten – in de Virtex-5 voor het eerst ook van zes variabelen. Uit al deze functies kiezen we voor elke LUT exact één exemplaar door vóór het gebruik van de FPGA de gepaste rij bits in de component in te lezen waardoor we de configuratie (en dus de functie) van de FPGA bepalen.

Diezelfde bitrij legt vast hoe de LUT‘s met elkaar zijn verbonden. Ook de verbindingen zijn immers configureerbaar door aan te geven of een connectie wel (logische 1) of niet (logische 0) wordt gemaakt. Nadat de FPGA een tijdje heeft gewerkt in de huidige configuratie, kunnen we hem gemakkelijk wijzigen door een nieuwe bitrij in te lezen. Dit noemen we herconfigureren. In de gangbare praktijk gebeurt het maar zeer zelden omdat het aanmaken van de herconfiguratiebitrij zeer lang duurt.

Figuur 1: Er zijn typisch twee manieren om een 16-wegs FIR-filter te implementeren op een FPGA: statisch of dynamisch. De Universiteit Gent ontwikkelde een alternatief.

Herconfiguratie van FPGA‘s tijdens de werking (runtime) is al een tijdje technisch mogelijk. Vooral de introductie van partiële herconfiguratie door Xilinx in 2002 heeft de universiteiten heel wat nieuwe onderzoekspaden doen opstarten rond runtime herconfiguratie. Toch heeft de industrie deze mogelijkheid niet omgezet naar concrete toepassingen. Laat ons de reden hiervoor eens van naderbij bekijken aan de hand van een voorbeeld.

We beschouwen een 16-wegs FIR-filter zoals in Figuur 1. Hierbij worden 8 bit ingangssignalen gefilterd door ze per zestien met zestien afzonderlijke coëfficiënten (van 8 bits elk) te vermenigvuldigen en de resultaten op te tellen. Het ingangssignaal verandert voortdurend van waarde, maar de coëfficiënten blijven lange tijd gelijk totdat een gelijkaardige filter met een andere karakteristiek (en dus andere coëfficiënten) nodig is.

Er zijn typisch twee manieren om deze filter te implementeren op een FPGA. Aangezien de coëfficiënten in de tijd kunnen veranderen, beschouwen we ze bij de eerste aanpak ook als ingangen van de filter. We bouwen een generieke implementatie van de filter die alle filteroperaties voor alle coëfficiëntwaarden kan uitrekenen. In ons voorbeeld en voor een eenvoudige FPGA-architectuur neemt dit 2999 LUT‘s in beslag en duurt het 118,4 ns om het kritische pad te doorlopen (langste tijdsvertraging in het systeem).

We kunnen ook uitgaan van de wetenschap dat de coëfficiënten slechts sporadisch veranderen. Als we er nu voor zouden opteren om voor elke set van coëfficiëntwaarden een andere, meer geoptimaliseerde, FPGA-implementatie te maken, dan kunnen we dezelfde filter gemiddeld met slechts 1005 LUT‘s implementeren en met een kritisch pad van slechts 83,5 ns. In dit geval moeten we wel elke keer dat de coëfficiënten veranderen een nieuwe implementatie voor de FPGA genereren en dat duurt liefst 35 seconden.

Figuur 2: Met de TMap-tool is het mogelijk de FIR-filter af te beelden op een TLUT-structuur zonder dat de coëfficiënten al zijn bepaald.

De eerste mogelijkheid maakt helemaal geen gebruik van runtime herconfiguratie en doet de volledige implementatie van alle mogelijkheden op een generieke manier vooraf (statisch). Dit levert een veel grotere en tragere implementatie op dan de gespecialiseerde implementatie van de tweede oplossing. Die gebruikt wel herconfiguratie, maar de tijd voor het genereren van de nieuwe configuratie is excessief lang en verhindert de praktische haalbaarheid van herconfiguratie tijdens de werking.

Uiteraard bestaat ook de mogelijkheid om alle configuraties op voorhand uit te rekenen en de overeenstemmende bitrij op te slaan in een geheugen. Herconfiguratie vereist dan enkel het uit het geheugen halen van de bitrij en opladen in de FPGA, een actie die een paar milliseconden duurt en runtime herconfiguratie wel mogelijk zou maken. Die werkwijze vereist wel kennis van alle mogelijke filtercoëfficiënten op voorhand. En die is er vaak niet. Bovendien is er veel geheugenruimte nodig voor het opslaan van de bitrijen als er heel veel combinaties van filtercoëfficiënten mogelijk zijn.

Figuur 3: De UGent-onderzoekers gebruiken de klassieke plaatsings- en routeringstools, waarbij ze eerst de TLUT‘s vervangen door gewone LUT‘s door de parameters een fictieve waarde te geven.

Instelfuncties

Aan de Universiteit Gent hebben we een nieuwe techniek ontwikkeld die bestaat uit aangepaste implementatiesoftware maar werkt met de klassieke FPGA‘s. Daarmee is de generatie van nieuwe FPGA-implementaties toch mogelijk tijdens de werking. Het centrale concept in onze techniek is de Tunable LUT (TLUT).

In een klassieke LUT worden vooraf alle uitgangswaarden opgeslagen die horen bij elke mogelijke ingangscombinatie (de zogenaamde waarheidstabel van de booleaanse functie). De ingangen worden dan gebruikt als variabelen die de juiste uitgangswaarde selecteren tijdens de werking. Bij de TLUT maken we handig gebruik van het feit dat er ook vooraf gedefinieerde parameters zijn die veel minder veranderen dan de andere ingangen. We slaan nu niet meer de vaste uitgangswaarden op voor elke ingangscombinatie maar wel uitgangsfuncties (of instelfuncties) die nog afhankelijk zijn van de parameters. Die parameters gebruiken we niet als normale ingangen maar als functieparameters die bij elke herconfiguratie (en enkel dan) de mogelijke uitgangswaarden van de TLUT‘s vastleggen. Elke herconfiguratie bestaat dan niet meer uit een volledige generatie van een FPGA-implementatie maar enkel uit het evalueren van alle instelfuncties en het opslaan in de klassieke LUT van de resulterende uitgangswaarden. Dit is grootteordes sneller (tot 215 duizend keer sneller op dit moment) en leidt wel tot een haalbare herconfiguratie tijdens de werking.

Laten we het voorbeeld van het FIR-filter er nog eens bijpakken. We beschouwen de coëfficiënten van het filter niet als ingangen maar als parameters van de functies die de LUT-uitgangen zullen bepalen. Zoals we in de conventionele FPGA-ontwerpsoftware ons algoritme (het FIR-filter) afbeelden op de FPGA-LUT-structuur, zo beelden we nu het FIR-filter af op een TLUT-structuur waarbij de parameters (coëfficiënten) nog onbepaald zijn. Daarvoor hebben we bestaande afbeeldingssoftware aangepast. Onze oplossing hebben we TMap genoemd (Figuur 2). Plaatsings- en routeringstools beelden de resulterende TLUT-structuur dan af op de fysische FPGA-structuur. Hiervoor gebruiken we het klassieke gereedschap, waarbij we eerst de TLUT‘s vervangen door gewone LUT‘s door de parameters een fictieve waarde te geven (Figuur 3). Tegelijkertijd leiden we wel de instelfuncties af die nog afhankelijk zijn van de parameters. Uit het resultaat van de plaatsing en de routering halen we de moederconfiguratie, waarin is aangegeven welke bits de instelfuncties nog moeten bepalen. Dit alles gebeurt vóór de eerste configuratie (offline) en daarom is het niet erg dat dit meer tijd in beslag neemt.

Het enige dat nog tijdens de werking moet gebeuren om een herconfiguratie van de coëfficiënten uit te voeren, is het herevalueren van de instelfuncties tegen de nieuwe waarden van de parameters en het aanpassen van de bitrij met de juiste bits (Figuur 4). Dit neemt nog zeer weinig tijd in beslag, in het voorbeeld van het FIR-filter gemiddeld 0,166 ms.

DNA-sequentie

In Tabel 1 staan de resultaten weergegeven voor de statische, generieke implementatie (oplossing 1 van het voorbeeld), de dynamische, volledige herimplementatie (oplossing 2) en onze nieuwe aanpak. De mogelijkheid om het FIR-filter te specialiseren, levert ons een veel kleinere en snellere oplossing dan in het statische geval. Hierbij kunnen we in onze aanpak iets minder ver gaan in de optimalisatie dan in het dynamisch geval, waar we een volledige herimplementatie kunnen doen, maar het verschil is relatief beperkt. We gebruiken slechts 23 procent meer LUT‘s en hebben een slechts 4 procent trager circuit dan wanneer we de hele implementatie overdoen voor elke nieuwe set van coëfficiënten. Nochtans is de generatietijd 215 duizend keer sneller en nu wel van die grootteorde om herconfiguratie tijdens de werking mogelijk te maken. Dit maakt onze techniek veel bruikbaarder dan eerder ontwikkelde methoden die klassieke plaatsings- en routeringssoftware trachten te versnellen voor runtime herconfiguratie.

Figuur 4: Het enige dat nog tijdens de werking moet gebeuren om een herconfiguratie van de coëfficiënten uit te voeren, is het herevalueren van de instelfuncties en het aanpassen van de bitrij.

Onze nieuwe techniek is vrij eenvoudig toepasbaar – enkel de afbeeldingssoftware vraagt een aanpassing – en levert winst op voor alle problemen waar traag variërende parameters aanwezig zijn. Zo zijn we overtuigd van het nut van onze techniek in toepassingen zoals encryptiealgoritmes die van een sleutel afhangen, zoals Des, of bio-informatica-algoritmes waar een scorematrix moet worden gekozen afhankelijk van het probleem, zoals DNA-sequentie-uitlijning. We zijn nog op zoek naar praktijkvoorbeelden van dergelijke problemen om onze technieken op uit te testen en aan te tonen dat die voordelen opleveren ten opzichte van de klassieke implementaties.

Op 19 juni verzorgt Dirk Stroobandt tijdens de Bits&Chips Hardware Conference de technische keynote over runtime herconfiguratie van FPGA‘s.

Oppervlakte (LUT‘s) Kritisch pad (ns) Generatietijd (ms)
Statisch 2999 118,4 0
Dynamisch 1005 83,5 35634
Oplossing UGent 1301 86,8 0,166