Szűrő architektúrák FPGA realizációjának vizsgálata Kutatási beszámoló a Pro Progressio alapítvány számára Szántó Péter, 2013.
Bevezetés Az FPGA-ban megvalósítandó jelfeldolgozási feladatok közül a legfontosabb a véges impulzusválaszú (FIR) szűrők implementációja. Az erőforrásigény, feldolgozási teljesítmény és fogyasztás szempontjából is fontos, hogy adott feladathoz és FPGA architektúrához a megfelelő hardver struktúrát válasszuk. A kutatómunka ennek tükrében tekinti át a különböző megvalósítási lehetőségeket, s segíti a megfelelő struktúra kiválasztását.
Konvolúció Az egy dimenziós FIR szűrés a szűrő impulzusválaszának és a bemeneti mintasorozat utolsó N elemének konvolúcióját jelenti:
Realizáció szempontjából igen lényeges paraméterek: a bemeneti minták mintavételi frekvenciája a szűrő fokszáma (N) a bemeneti minták (xk) felbontása a szűrő együtthatókészletének (ck) felbontása A fenti képletből láthatóan az elvégezendő alapművelet a MAC (multiply-and-accumulate) művelet, vizsgáljuk meg ennek megvalósítási lehetőségeit.
Elosztott aritmetika Bár a mai korszerű FPGA-k esetében – melyekben nagyszámú dedikált szorzó áramkör található - jelentősége nem túl nagy, a teljesség kedvéért megemlítendő az elosztott aritmetika (DA – distributed arithmetic) alkalmazása, melynek esetén a szorzás művelet végrehajtása alapvetően bitsorosan történik, így fizikailag csak egy egy bites szorzó valamint egy akkumulátor realizációját igényli. Bontsuk fel az i-edik bemeneti mintát (feltételezve, hogy B bites, egynél kisebb abszolút értékű kettes komplemens számok):
Majd helyettesítsük be ezt a konvolúció képletébe:
Mivel az xkb értékek binárisak, így a kifejezésnek 2N különböző értéke lehet (mindegyik a C együtthatókészlet elemeinek lineáris kombinációja). Ennek megfelelően a teljes konvolúciót megvalósító hardver struktúra az alábbi: <<1
accu
y[n]
ROM
x[n] (soros)
SHR
SHR
SHR
SHR
N-1 B bites shift regiszter
A megvalósítás előnye, hogy nem igényel dedikált szorzó áramkört, hátránya, hogy a szükséges ROM méret a szűrő fokszámának növekedésével exponenciálisan nő. A számítási teljesítmény ugyanakkor nem függ a szűrő fokszámától, csak a bemeneti minták felbontásától. A bemeneti adat particionálásával és a struktúra többszörözésével a teljesítmény növelhető.
Dedikált aritmetikai elemek A jelentősebb gyártók FPGA-i (Altera, Xilinx) igen régóta tartalmaznak a jelfeldolgozási műveletek végrehajtásához dedikált szorzó, illetve jelfeldolgozó egységeket. A régebbi, illetve olcsóbb termékekben (pl. Xilinx Spartan-3, Altera Cyclone IV) tipikusan 18x18 bites előjeles szorzó áramköröket találunk, míg az újabb családok esetén komplett MAC egységek kaptak helyet a szilíciumon. Az alábbi táblázat néhány FPGA család esetére összegzi a legfontosabb paramétereket. Spartan-3 Spartan-6 Xilinx Virtex-6 Cyclone IV
Altera
Cyclone V
Startix V
18x18 bites előjeles szorzó 18x18 bites előjeles szorzó 18 bites elő-összeadó 48 bites akkumulátor 25x18 bites előjeles szorzó 48 bites akkumulátor logikai műveletek 18x18 bites előjeles szorzó használható két 9x9 bites szorzóként 18x18 bites szorzó, 18 bites elő-összeadó, 44 bites akkumulátor 27x27 bites szorzó, 26 bites elő-összeadó, 64 bites akkumulátor kisméretű belső együttható tár (8x18 vagy 8x27 bit) megegyezik a Cyclone V-tel
Amennyiben a fenti táblázatban szereplő felbontás megfelelő az adott alkalmazáshoz, úgy egy MAC művelet egyetlen DSP blokk felhasználásával megvalósítható, a működési frekvencia pedig tipikusan 300-500 MHz körül alakul. Amennyiben az alkalmazás a fentieknél finomabb felbontást igényel, úgy a blokkok kaszkádosításával ez megoldható. Az alábbi blokkvázlat a
Spartan-6 négy darab DSP48A1 blokkjával megvalósított 35x35 bites szorzó kialakítását mutatja. a[34:17]
Z-3
X b[34:17]
Z-3
a[34:17]
Z-2
Z-2
{0, a[16:0}]
Z-1
Z-1
p[69:34]
>>17 Z-1
+
Z-1
Z-1
p[33:17]
Z-3
p[16:0]
DSP48A1
X b[34:17]
+
DSP48A1
X {0, b[16:0}]
Z-1
Z-1
+
Z-1
Z-1
DSP48A1
>>17
{0, a[16:0}]
X
Z-1
+
Z-1
{0, b[16:0}] DSP48A1
Szűrő struktúrák A szűrő működési frekvenciája (fclk), a bemeneti mintavételi frekvencia (fs) és a szűrő fokszáma alapján (N) a kialakított struktúrát három nagy csoportba sorolhatjuk: szekvenciális, párhuzamos és részben párhuzamos.
Szekvenciális FIR struktúra Amennyiben teljesül, hogy , akkor a szekvenciális struktúra megfelelő számítási kapacitással rendelkezik. Ebben az esetben egyetlen MAC egység felel a kimeneti minta kiszámításáért, a számítás – azaz egyetlen kimeneti minta előállítása – pedig N órajelet vesz igénybe.
Coeff ROM
Z-1
X
Z-1
+
y
MAC Sample RAM
x
Mivel egy órajelben csak egy-egy együtthatóra és bemeneti mintára van szükség, az FPGAkban található beágyazott memória blokkok kedvező lehetőséget kínálnak mind az együttható ROM, mind pedig a minta késleltetővonal kialakítására (utóbbit cirkuláris bufferként használva). Tipikusan ezen belső memóriák dual-port kialakításúak, így az együttható készlet dinamikus változtatása is egyszerűen megoldható. Amennyiben a szűrő fokszáma kicsi (és így az általában 1-2 kB-os memóriák kihasználtsága alacsony), az Altera Stratix, illetve a Xilinx FPGA-k esetében alternatívát jelent az ún. elosztott memória használata, amely az FPGA általános erőforrását (LUT) konfigurálja memóriaként. Xilinx FPGA-k esetében a LUT-okból létrehozott, dinamikusan címezhető shift regiszterek is kedvező alternatívát kínálnak a kisméretű tárolóelemek kialakítására.
Teljesen párhuzamos struktúra Amennyiben a mintavételi frekvencia megegyezik a működési frekvenciával (tipikusan ez a helyzet például videó feldolgozásnál), úgy csak a párhuzamos struktúra jelent megoldást. Ebben az esetben a szükséges MAC egységek száma megegyezik a szűrő fokszámával. A konvolúció képletének direkt leképezéséből származtatott ún. „direct-form” architektúrát az alábbi ábra mutatja. Z-1
x
C0
Z-1
X
C1
Z-1
Z-1
X
C2
Z-1
Z-1
X
C3
Z-1
Z-1
X
Z-1
+
+
Z-1
Z-1
C4
X
Z-1
Z-1
+ Z-1
Z-1
+ Z-1
y
A rész-szorzatok összegzése ebben az esetben összeadó-fával történik. A fentiekben bemutatott DSP blokkok felépítéséhez ez a struktúra kevésbé illeszkedik: ugyan az első szintű összeadásokra felhasználható a DSP blokkokban található összeadó/akkumulátor, a további szintek megvalósítása viszont általános logikával történik (miközben a DSP blokkok felében kihasználatlan az összeadó). Ezen architektúra választását éppen ezért legfeljebb az indokolja, hogy késleltetése viszonylag kicsi. Ezzel ellentétben az ún. „systolic FIR” struktúra – köszönhetően az elosztott összeadó fának – teljes egészében kihasználja a DSP blokkok adottságait, s ez tekinthető az ideális választásnak. Z-1
C2
-1
x
Z-1
+
Z-1
+
Z-1
y
-1
Z
Z
X
Z-1
Z-1
C1
C0
X
Z-1
Z-1
X
Z-1
Z-1
+
Z-1
Z-1
Fenti struktúra tökéletesen illeszkedik mind az Altera, mind pedig a Xilinx FPGA-kban található DSP blokkokhoz, ezen blokkok mellett semmiféle kiegészítő logika használatát nem igényli. A DSP blokkok közötti dedikált kaszkádosító huzalozás pedig a jelterjedési időket is minimalizálja, így igen magas működési frekvencia érhető el.
Részben párhuzamos struktúra Részlegesen párhuzamosított struktúra használata szükséges amennyiben a szekvenciális megoldás teljesítménye nem elegendő, ugyanakkor a teljesítmény igény nem indokolja a teljesen párhuzamos struktúra kialakítását, azaz amikor . Ebben az esetben több MAC blokk kerül felhasználásra, s az egyes blokkok a rész-szorzatok egy-egy részhalmazát számítják. Tételezzük fel az alábbi paramétereket: fclk=400 MHz működési frekvencia fs=6 MHz mintavételi frekvencia 128-ad fokú szűrő Mivel , így olyan struktúrára van szükség, amely órajelenként képes két MAC művelet kiszámítására. Az alábbi ábrán látható DSP blokkok közül az alsó kettő végez ténylegesen rész-szorzat számítást, a harmadik blokk akkumulátorként funkcionál. Az együtthatókat és mintákat tároló bufferek szét vannak osztva a két MAC egység között, mindkét egység 64-64 művelet végrehajtásáért felelős.
0 Z-1
X
Z-1
+
0
Coeff Buffer 1.
Z-1
Sample Buffer 1.
Z-1
+
Z-1
Z-1
+
Z-1
Coeff Buffer 0.
Z-1
X Sample Buffer 0.
x
X
Z-1
Z-1
A mintatár (Sample Buffer) kialakítása történhet dual-port memóriával vagy – Xilinx FPGA-k esetében – dinamikusan címezhető shift regiszterekkel. Előbbi esetben minden számítási ciklus végén az utolsóként feldolgozott minta átkerül az első mintatárból a másodikba, megvalósítva egy fizikailag ketté bontott cirkuláris buffert.
Decimáló- és interpoláló szűrők A decimálás művelete aluláteresztő szűrésből és mintaeldobásból áll: k-ad fokú decimálás esetén a bemeneti jelből kiszűrésre kerülnek a kimeneti mintavételi frekvencia felénél nagyobb frekvenciájú komponensek, majd minden k minta közül (k-1)-t eldobunk. A számítási igény k-ad részére csökkenthető, ha az eldobott mintákat ki sem számítjuk. Ekkor azt is kijelenthetjük, hogy a szűrés számítási igénye független a decimálás fokszámától. A decimálás során használt szűrőkről ugyanis elmondható, hogy a decimálási faktor duplázásakor az ehhez szükséges szűrő fokszáma is a kétszeresére nő. Összességében tehát egyetlen kimeneti minta előállításához kétszeres számú MAC műveletre van szükség, egy kimeneti minta számítására viszont kétszer annyi órajel áll rendelkezésre. Tekintsünk egy N=12 pontos szűrőt, valamint másodfokú decimálást. Ez esetben az érvényes kimenetet generáló konvolúciók (c az együtthatókat, x a bemeneti mintákat jelöli): c0 x0 x2 x4
c1 x1 x3 x5
c2 x2 x4 x6
c3 x3 x5 x7
c4 x4 x6 x8
c5 x5 x7 x9
c6 x6 x8 x10
c7 x7 x9 x11
c8 x8 x10 x12
c9 x9 x11 x13
c10 x10 x12 x14
c11 x11 x13 x15
Decimálás esetén a legnagyobb számítási teljesítményű struktúra (órajelenként egy új bemeneti minta feldolgozása) egy-egy MAC egysége sem csak egy együtthatóval képzett részszorzatot számít, hanem a decimálás fokának megfelelő számút, tehát jelen esetben kettőt. Fenti táblázatban az azonosan színezett együtthatókat ugyanaz a MAC egység használja fel – az első számítási fázis első órajelében az első MAC egység az részszorzatot, a második órajelben pedig a részszorzatot számítja. Ebben a MAC egységben a további kimeneti értékek számítása során sem x0 sem pedig x1 nem kerül felhasználásra, így ezek továbbadhatók a következő MAC egységnek, tehát a kiadódó struktúra „előremutató”
adatfolyam jellegű. A MAC egységek számára a bemeneti mintákat a decimálási faktortól függő hosszúságú késleltetővonalak (shiftregiszterek) szolgáltatják. 0
X
Z-1
Z-1
+
y
0
További MAC egységek
Coeff ROM
Z-1
X Z-3
Z-1
+
Z-1
Z-1
Coeff ROM
Z-1
X Z-3 Coeff ROM
Z-1
+
Z-1
Z-1 Z-1
X Z-1
Z-1
+
Z-1
Z-1
Nem ilyen kedvező a helyzet abban az esetben, ha a MAC egységenként feldolgozott együtthatók száma nem egyezik meg a decimálás fokával – például ha a fenti esetben egy MAC egység 4 együtthatóval képzett részeredményeket számít. Többé-kevésbé megtartva a fenti struktúrát a MAC egység – együttható összerendelés az alábbiak szerint módosítható: c0 x0 x2 x4
c1 x1 x3 x5
c2 x2 x4 x6
c3 x3 x5 x7
c4 x4 x6 x8
c5 x5 x7 x9
c6 x6 x8 x10
c7 x7 x9 x11
c8 x8 x10 x12
c9 x9 x11 x13
c10 x10 x12 x14
c11 x11 x13 x15
Tehát az első kimeneti érték számításakor a három MAC egység ugyanazokat a részszorzatokat számítja, mint az előző esetben a 6 MAC egység közül az első három. Az ezt követő két órejelben ugyanez a három MAC egység számítja ki azokat a részszorzatokat, ami az előző esetben a második három MAC egység feladata volt. Ahhoz, hogy a megfelelő bemenetek rendelkezésre álljanak, a bemeneti shiftregiszter-lánc második felét is a három MAC egység bemenetére kell kötni, tehát minden MAC egység két shiftregiszterből képes bemenetet venni. Interpoláció esetén is lehetőség van a műveletvégzés racionalizálására. Mivel I-ed fokú interpoláció esetén minden bemeneti minta közé (I-1) darab 0 értékű mintát illesztünk, így az ezekkel képzett részszorzat 0, tehát a számítás elhagyható. Az alábbi táblázat másodfokú interpoláció esetét mutatja, az azonosan színezett részszorzatok számítása történik 1-1 MAC egységben. Tehát például a második kimenet előállításához az első MAC egység a részszorzatot számítja, míg a harmadik kimenet előállításához a értéket, és így tovább. Általánosan tehát I-ed fokú interpoláció esetén minden MAC I darab együtthatóval végzett számításokért felelős, s I egymást követő órajelben ezeket ugyanazzal a bemeneti mintával szorozza össze.
c0 x0 0 x1
c1 0 x1 0
c2 x1 0 x2
c3 0 x2 0
c4 x2 0 x3
c5 0 x3 0
c6 x3 0 x4
c7 0 x4 0
c8 x4 0 x5
c9 0 x5 0
c10 x5 0 x6
c11 0 x6 0
Új bemeneti minta beolvasása ezért minden I-edik órajelben történik, ezt leszámítva a struktúra megfelel a teljesen párhuzamos MAC alapú FIR struktúrának.
Összegzés A fentiekből láthatóan a korszerű FPGA-k felépítése architektúrálisan igen kedvező a MAC művelet alapú jelfeldolgozási feladatok megvalósításához. A nagyobb eszközökben, melyek akár 500-1000 DSP blokkot tartalmaznak, extrém sebességű és/vagy fokszámű szűrők is megvalósíthatók, míg a kisebb eszközök igen kedvező ár/teljesítmény és ár/fogyasztás mutatókkal rendelkeznek.
