Ocena efektywności dopasowania technologicznego dla struktur FPGA

Jednym z kluczowych problemów w rozwoju techniki cyfrowej jest problem ciągłego tworzenia nowych narzędzi syntezy. Niestety dostępne obecnie narzędzia syntezy są dalekie od doskonałości. Uzyskiwane w wyniku syntezy rozwiązania nie zajmują minimalnych zasobów logicznych, jak i nie mają optymalnych właściwości dynamicznych.

Istotą efektywnego odwzorowania technologicznego projektowanych układów cyfrowych w strukturach FPGA jest odpowiednio prowadzona dekompozycja funkcji logicznych, która stanowi podstawy teoretyczne efektywnego podziału układu pomiędzy bloki logiczne LUT, zawarte wewnątrz układu FPGA. Producenci układów FPGA zapewniają możliwość konfiguracji bloków logicznych zawartych wewnątrz struktury [1, 13]. Szczególnie istotna jest, zwykle niewielka, liczba wejść bloków logicznych zawartych w układach FPGA, gdyż ona stanowi główne ograniczenie projektowe. Problem efektywnego dopasowania technologicznego jest więc bezpośrednio związany z wyborem odpowiedniej dekompozycji funkcji i tworzenie odpowiedniej ścieżki dekompozycji.

Celem artykułu jest przedstawienie metodologii poszukiwania odwzorowania technologicznego, pozwalającej na ocenę efektywności dopasowania technologicznego, która wskazuje na sposób doboru odpowiedniej dekompozycji w kolejnych etapach syntezy projektowanego układu. Przedstawiona w artykule metoda oceny efektywności odwzorowania technologicznego do struktury FPGA, jest dopasowana do zasobów struktury programowalnej scharakteryzowanych liczbą wejść bloków logicznych. Opracowana metoda oceny efektywności odwzorowania jest przeznaczona dla układów FPGA typu tablicowego.

Rys. 1. Istota dekompozycji szeregowej z wykorzystaniem BDD a) reprezentacja funkcji za pomocą BDD b) uzyskany podział

Problem dekompozycji funkcji 

Problem dekompozycji funkcji czy też zespołu funkcji jest tematem wielu prac naukowych [9, 12]. Dekompozycja jest modelem matematycznym podziału projektowanego układu na poszczególne bloki logiczne. Najprostszy model dekompozycji funkcji [4] sprowadza się do wyboru odpowiedniego podziału argumentów funkcji na dwa podzbiory: zbiór związany X1 i zbiór wolny X2 [8, 9]. Znane są również inne modele dekompozycji, wśród których jednym z ważniejszych jest dekompozycja wielokrotna.

Kluczowy w procesie dekompozycji jest dobór takiego podziału argumentów, który zapewni minimalizację liczby tzw. funkcji wiążących (skojarzonych z połączeniami pomiędzy blokami związanym i wolnym) przy założonej liczności zbioru związanego card(X1). W przypadku reprezentacji funkcji za pomocą diagramu BDD (ang. Binary Decision Diagram) [7, 11] istota doboru dekompozycji sprowadza się do wyboru odpowiedniego uporządkowania zmiennych w diagramie oraz odpowiednim usytuowaniu tzw. linii cięcia (na rysunku 1a zaznaczona na zielono). Część diagramu znajdująca się nad linią cięcia skojarzona jest ze zbiorem związanym, a poniżej linii cięcia ze zbiorem wolnym [2, 9, 12], co pokazano na rysunku 1a.

Poziom, na którym dokonano cięcia diagramu licząc od korzenia określą liczność zbioru związanego card(X1), natomiast liczba wierzchołków odciętych (czyli wierzchołków znajdujących się w dolnej części diagramu, na które wskazują krawędzie z nad linii cięcia) określa liczbę niezbędnych funkcji wiążących według zależności (1).

ile_g = lg₂ (liczba_węzłów_odciętych)   (1)

Dopasowanie technologiczne dla diagramów jedno oraz wielokorzeniowych

Problem dopasowania technologicznego jest bezpośrednio powiązany z problemem doboru poziomu cięcia diagramu BDD. Oznaczmy przez k liczbę wejść bloku logicznego LUT. W diagramach z jedną linią cięcia (jednokorzeniowych – ROBDD) poziom cięcia określa liczność zbioru związanego card(X1). Najkorzystniej, gdy card(X1) jest równe liczbie wejść bloku LUT (k), co symbolicznie pokazano na rysunku 2. Oczywiście, dopuszczalne jest, aby card(X1) < k, lecz w większości przypadków prowadzi to do nieefektywnego wykorzystania bloku LUT. Niedopuszczalne jest, aby card(X1)> k. 

Rys. 2. Istota dopasowania technologicznego dla dekompozycji realizowanej przy użyciu pojedynczego cięcia diagramu BDD 

Rys. 3. Istota dopasowania technologicznego dla dekompozycji realizowanej przy użyciu kilku linii cięcia (E0 … En- – poszczególne zbiory związane)

Problem dopasowania technologicznego w przypadku dekompozycji realizowanej metodą wielokrotnego cięcia (uzyskiwane są grafy wielokorzeniowe SMTBDD [10]) sprowadza się do wyznaczenia „najlepszej odległości” pomiędzy sąsiednimi liniami cięcia.

Odległości te, muszą być równe (w szczególnych przypadkach mogą być mniejsze) liczbie wejść bloków LUT (rys. 3). Ponieważ dekompozycja wielokrotna realizowana metodą wielokrotnego cięcia prowadzi do uzyskania większej liczby zbiorów związanych, oznaczmy poszczególne zbiory związane symbolem E z odpowiednim indeksem.

Należy zatem odpowiednio dobrać liczbę zmiennych występujących w poszczególnych wycinkach diagramu.

Większość producentów układów FPGA pozwala na dobór liczby wejść bloku LUT (k) w niewielkim zakresie [1, 13]. W celu kompresji opisu w dalszej części pracy będzie używany skrót LUTn/m oznaczający blok logiczny typu LUT zawierający n-wejść i m-wyjść. Zdolność konfiguracji bloku LUT (doboru liczby wejść) musi być uwzględniona na etapie dopasowania technologicznego. W ogólnym przypadku poszukuje się dekompozycji, która zapewni najlepsze dopasowanie do architektury układu. Konieczne staje się więc parametryczne szacowanie efektywności dopasowania w kolejnych krokach dekompozycji.

Ocena efektywności dopasowania technologicznego 

Proces dopasowania projektowanego układu do zasobów struktury programowalnej jest zwykle procesem iteracyjnym. Istotą dobrego dopasowania technologicznego, obserwowanego w i-tym kroku syntezy, jest maksymalne ograniczenie liczby wejść bloku wolnego, przy minimalnym wykorzystaniu zasobów potrzebnych do realizacji bloku związanego. W tej sytuacji efektywność dopasowania technologicznego do bloków LUT jest w głównej mierze zależna od liczby funkcji wiążących, która jest bezpośrednio związana z liczbą bloków LUT potrzebnych do realizacji bloku związanego. Oczywiście celem nadrzędnym procesu dopasowania technologicznego powinna być (w przypadku minimalizacji powierzchni) minimalizacja liczby bloków typu LUT, czy też komórek logicznych o określonej strukturze, potrzebnych do realizacji rozpatrywanej funkcji logicznej. W przypadku optymalizacji właściwości dynamicznych uzyskiwanych rozwiązań, nadrzędnym celem optymalizacyjnym powinna być liczba warstw logicznych uzyskiwanych struktur.

W procesie dopasowania projektowanego układu opisanego za pomocą funkcji logicznych do zasobów użytej struktury programowalnej należy uwzględniać zarówno elementy charakteryzujące zasoby strukturalne (liczba wejść, wyjść bloków typu LUT, struktura komórki logicznej), jak i parametry charakteryzujące i-ty krok podziału (liczba zmiennych tworzących zbiór związany, liczba funkcji wiążących itp.). Należy zatem stworzyć takie wskaźniki szacowania efektywności dopasowania, które pozwolą na uzyskiwanie odpowiednio zoptymalizowanych struktur logicznych. Celem optymalizacyjnym może być powierzchnia (minimalizacja liczby użytych bloków logicznych) lub właściwości dynamiczne (minimalizacji liczby warstw logicznych).

Rozważmy realizację funkcji f:Bn → B w strukturach FPGA typu tablicowego, zawierających konfigurowalne bloki logiczne, w których możliwa jest jedna z dwóch konfiguracji bloków tablicowych, symbolicznie opisana jako LUT5/1 lub LUT4/2. Poszukując najlepszego odwzorowania technologicznego konieczne staje się dopasowanie procesu dekompozycji do zasobów wykorzystywanej struktury. Problem dopasowania sprowadza się więc do wyboru odpowiedniej „ścieżki” dekompozycji, która powinna być prowadzona w taki sposób, aby w poszczególnych krokach wykorzystywać możliwie jak najmniejszą liczbę konfigurowalnych komórek logicznych, przy równoczesnym możliwie maksymalnym ograniczaniu argumentów funkcji, które będą dekomponowane w kolejnych krokach.

Wprowadźmy pojęcie współczynnika efektywności odwzorowania δ, który będzie miarą efektywności dopasowania realizowanej funkcji do wykorzystywanych konfigurowalnych bloków logicznych. Dobór odpowiedniej dekompozycji funkcji będzie uzależniony od wartości tego współczynnika. Czym mniejsza wartość współczynnika δ, tym lepsze odwzorowanie funkcji w i-tym kroku dekompozycji.

Współczynnik efektywności odwzorowania δ można wyznaczyć zgodnie z zależnością (2):

δ = liczba_bloków – (card(X1) – ile_g)    (2)

W zależności (2) występuje parametr liczba_bloków, który zależy od zastosowanej konfiguracji bloku logicznego (może przyjmować wartości połówkowe dla konfiguracji LUT4/2, gdy jest wykorzystany tylko jedno z dwóch wyjść bloku LUT). Dobór konfiguracji bloku logicznego związany jest bezpośrednio z rozpatrywaną dekompozycją funkcji scharakteryzowaną dwoma parametrami (card(X1), ile_g) i powinien być realizowany w taki sposób, aby prowadził do wykorzystania minimalnej liczby konfigurowalnych bloków logicznych.

Przedstawmy wartości współczynnika efektywności odwzorowania δ w postaci tablicy trójkątnej, w której wiersze skojarzone są z liczbą funkcji wiążących (ile_g), a kolumny z licznością zbioru związanego card(X1). W poszczególnych komórkach tablicy (rys. 4) umieszczono wartości współczynnika δ wyznaczone zgodnie z zależnością (2).

Proces poszukiwania odpowiedniej dekompozycji wynika bezpośrednio z wartości zawartych w tablicy trójkątnej przedstawionej na rys. 4 i został pokazany w przykładzie 1. 

Rys. 4. Tablica trójkątna, przeznaczona do szacowania efektywności dopasowania do konfigurowalnych bloków logicznych LUT5/1; LUT4/2

Przykład 1

Rozważmy funkcję logiczną opisaną diagramem o określonym uporządkowaniu zmiennych (jak na rys. 5).

W celu znalezienia dekompozycji zapewniającej możliwie najlepsze dopasowanie technologiczne, w dalszej części przykładu rozważane są trzy linie cięcia na poziomach 3 (rys. 5a), 4 (rys. 5b) oraz 5 (rys. 5c) licząc od korzenia. Zbiory związane mają odpowiednio 3, 4 oraz 5 zmiennych. Z każdym grafem skojarzono tablicę trójkątną, w której symbolem O oznaczono istnienie dekompozycji o danej liczbie ile_g (dla zadanego card(X1)).

Poszukiwanie dekompozycji zapewniającej najbardziej efektywne dopasowanie należy rozpocząć od najmniejszej możliwej wartości δ=-3 odpowiadającej dekompozycji skojarzonej z uporządkowaną parą liczb (card(XBound), ile_g)=(5,1). Taka wartość δ występuje tylko w przypadku pięcioelementowego zbioru związanego (rys. 5c), zatem poszukiwania należy rozpocząć od przypadku card(XBound)=5. Dla diagramu 5c występuje pięć wierzchołków odciętych. Do ich rozróżnienia konieczne są aż 3 funkcje wiążące. Wartość współczynnika δ dla dekompozycji (card(XBound), ile_g)=(5,3) wynosi 1. Przypadek ten jest oznaczany w tablicy trójkątnej (rys. 5c) cyfrą otoczoną kółkiem.

W następnej kolejności rozpatrywane są przypadki, w których δ<1 dla card(XBound)<5. Dla zbiorów związanych, w których liczba elementów jest mniejsza od 5 minimalna wartość δ osiągana jest dla zbioru związanego czteroelementowego, w którym (card(XBound), ile_g) = (4, 1). Wynosi ona δ=-2.5. Dla linii cięcia jak na diagramie 4b występują 3 wierzchołki odcięte, zatem do ich rozróżnienia konieczne są 2 funkcje wiążące. Dla (card(XBound), ile_g) = (4, 2) wartość δ=-1 i jest mniejsza od współczynnika δ uzyskiwanego w poprzednim kroku analizy. W odpowiedniej komórce tablicy trójkątnej wartość współczynnika δ została otoczona kółkiem.

Dla zbioru związanego trójelementowego istnieje tylko jeden przypadek, dla którego δ<-1. Występuje on dla dekompozycji (card(XBound), ile_g) = (3, 1). Z rysunku 4a widać, że dla dekompozycji, dla której card(X1)=3, konieczne są dwie funkcje wiążące, co sprawia, że uzyskiwane rozwiązanie nie prowadzi do lepszego, niż znalezione w poprzednim kroku, rozwiązania, gdyż wartość δ wynosi 0. Dla porządku odpowiedni symbol wyróżniono kółkiem w tablicy trójkątnej na rysunku 5a.

Nie ma sensu rozważać przypadku, w którym card(XBound) = 2, gdyż jedyna wartość δ możliwa do osiągnięcia wynosi -0,5 i jest większa od wartości już uzyskanej dla card(XBound)=4.

W tej sytuacji, dla analizowanego przypadku najlepsze dopasowanie zapewnia dekompozycja, w której zbiór związany jest 4 elementowy, dla której (card(XBound), ile_g) = (4, 2).

Zaprezentowaną metodę wyznaczania współczynnika δ dla bloków LUT5/1 i LUT4/2 można stosować też dla innych konfiguracji bloków. W takim przypadku, należy określić tablicę trójkątną podobną do tej z rysunku 4. Zaprezentowana metoda może być wykorzystana zarówno do klasycznych metod dekompozycji, jak i do metody wielokrotnego cięcia z wykorzystaniem diagramu SMTBDD. Może być ona również uogólniona na zespół funkcji.

Rys. 5. Możliwe cięcia diagramu wraz z odpowiednimi tablicami trójkątnymi

Wyniki eksperymentów 

W celu określenia przydatności nowej metody szacowania efektywności dopasowania technologicznego w procesie dekompozycji wykonano szereg eksperymentów. Poddano dekompozycji układy testowe [3], a wyniki zestawiono w tabeli 1. Porównano wyniki dla wybranych narzędzi programowych takich jak Decomp [8], ALTO [6] oraz Bdd [5] (w którym do reprezentacji funkcji wykorzystuje się diagramy BDD) oraz program Dek_tm, w którym zawarto techniki szacowania efektywności w oparciu o reprezentacje BDD funkcji. Układy kombinacyjne poddane dekompozycji odzwierciedlają zarówno pojedyncze funkcje jak i zespoły funkcji.

W przypadku dekomponowania zespołów funkcji często dążono do współdzielenia zasobów logicznych w celu zminimalizowania zajętości zasobów logicznych. Do szacowania efektywności dopasowania dla zasobów niewspółdzielonych wykorzystano wartość współczynnika δ. Dla zasobów współdzielonych odwzorowanie poszukiwano na zasadzie minimalizacji liczby wykorzystywanych bloków LUT.

Tab. 1. Wyniki eksperymentów:

W odpowiednich kolumnach tabeli 1 zawarto wyniki odpowiadające poszczególnym metodologiom dekompozycji. Ostatnia kolumna Dek_tm skojarzona jest z uzyskanymi rezultatami dla opisanych w artykule technik. Każda kolumna główna zawiera dwie podkolumny, w których zawarto odpowiednio wartości liczby koniecznych bloków logicznych do realizacji układu (LB) oraz z wartości liczby warstw dla danego układu (LW).

Analizując wyniki można zauważyć, że dobór dekompozycji uzależniony od efektywności dopasowania prowadzi do uzyskiwania struktur o małej zajętości zasobów logicznych zbliżonych do rezultatów uzyskanych z wykorzystaniem programu Decomp.

Reprezentacja funkcji w postaci diagramu BDD, prowadzi jednak do znacznego ograniczenia czasu dekompozycji w porównaniu z programem Decomp. Porównując uzyskane rezultaty pod kątem liczby warstw logicznych można stwierdzić, że nie odbiegają one od wyników uzyskiwanych z wykorzystaniem innych programów, a uzyskiwane są w większości przypadków w znacznie krótszym czasie.

Podsumowanie

Zaprezentowana technika wyboru dekompozycji na podstawie szacowania efektywności dopasowania, może prowadzić do zmniejszenia liczby wykorzystywanych bloków logicznych. Jej zaletą jest uniwersalność, gdyż można ją stosować do różnych modeli dekompozycji i różnych form reprezentacji funkcji. Możliwe jest jej uogólnienie na inne konfiguracje bloków logicznych dopasowując przedstawioną ideę odwzorowania technologicznego do dostępnych na rynku układów programowalnych. Czyni to proponowaną technikę szacowania efektywności odwzorowania bardziej elastyczną od podejść ze sztywno przyjętą liczbą wejść bloków typu LUT.

Literatura:

[1] Altera, Logic Array Blocks and Adaptive Logic Modules in Stratix V Devices, 2012.

[2] Chang S., Marek-Sadowska M., Hwang T.: Technology Mapping for TLU FPGA’s Based on Decomposition of Binary Decision Diagrams, IEEE Transactions on Computer-Aided Design, Vol.15, No.10, 1996, pp. 1226-1235.

[3] Collaborative Benchmarking and Experimental Algorithmics Laboratory, A benchmark set, http://www.cbl.ncsu.edu:16080/benchmarks/LGSynth93/testcases/

[4] Curtis H.A.: The Design of switching Circuits, D. van Nostrand Company Inc., New York 1962.

[5] Dzikowski A.: Dekompozycja zespołu funkcji logicznych z wykorzystaniem Binarnych Diagramów Decyzyjnych – rozprawa doktorska, Politechnika Śląska, 2006.

[6] Huang S.J., Jou J.Y., Shen W.Z.:ALTO: An Iterative Area/Performance Tradeoff Algorithm for LUT-Based FPGA Technology Mapping, IEEE Transactions on Very Large Integration (VLSI) Systems, vol. 8, no. 4, 2000, pp. 392–400.

[7] Ebend R., Fey G., Drechsler R.: Advanced BDD Optimization. Springer, Dordrecht, 2005.

[8] Kania D.: Elementy dekompozycji przeznaczone dla struktur FPGA typu tablicowego, Archiwum Informatyki Teoretycznej i Stosowanej, Tom 16, z. 1, 2004, ss. 45–62.

[9] Kania D.: Układy logiki programowalnej. Podstawy syntezy i sposoby odwzorowania technologicznego, PWN 2012.

[10] Kubica M., Kania D.: Dekompozycja wielokrotna z wykorzystaniem SMTBDD. Elektronika nr 12 2013, ss. 96–99.

[11] Lai M.-T., Pan K.-R. R., Pedram M.: OBDD-Based Function Decomposition: Algorithms and Implementation, IEEE Transactions on Computer-Aided Ddesign of Integrated Circuits and Systems, 1996, Vol. 15, No. 8, pp. 977–990.

[12] Minato S.: Binary Decision Diagrams and Applications for VLSI CAD. Kluwer Academic Publishers, 1996.

[13] Xilinx, 7 Series FPGAs Overview, 2012.