Narzędzia help

Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
first previous
cannonical link button

http://yadda.icm.edu.pl:80/baztech/element/bwmeta1.element.baztech-article-BWA2-0009-0090

Czasopismo

Kwartalnik Elektroniki i Telekomunikacji

Tytuł artykułu

Optymalizacja drzewa dodającego implementowanego w układach FPGA z wykorzystaniem programowania genetycznego i "Simulated Annealing"

Autorzy Wiatr, K.  Jamro, E. 
Treść / Zawartość
Warianty tytułu
Języki publikacji PL
Abstrakty
PL Operacja dodawania jest podstawową operacją w realizacji wielu algorytmów przetwarzania danych (np. podczas obliczania operacji konwolucji - filtracji typu FIR o stałych współczynnikach). W układach FPGA (ang. Field Programmable Gate Arrays) operacja dodawania powinna być implementowana z wykorzystaniem układu dodającego z przeniesieniem skrośnym RCA (ang. Ripple Carry Adder), w porównaniu z układami ASIC, dla których optymalną architekturą jest układ dodający z przechowaniem przeniesienia CSA (ang. Carry Save Adder). W konsekwencji dla układów FPGA powinno się użyć innych metod optymalizacji drzewa dodającego niż dla układów ASIC. W artykule tym zostały przedstawione dwa takie algorytmy: programowanie genetyczne GP (ang. Genetic Programming) i Simulated Annealing SA (symulowane wyżarzanie). Algorytmy te zostały porównane z uprzednio użytymi metodami przeszukiwania wyczerpującego ES (ang. Exhaustive Search) oraz algorytmu zachłannego GrA (ang. Greedy Algorithm). W rezultacie wyniki otrzymane przez SA są lepsze niż dla GP oraz SA daje około 10÷20% oszczędności w porównaniu z GrA. Dlatego optymalnym rozwiązaniem jest użycie algorytmu ES dla liczby wejść do bloku dodającego N<8 oraz SA dla N>8. W przypadku gdy decydującym czynnikiem jest czas znalezienia optymalnego drzewa zalecany jest algorytm GrA.
EN Addition is a very basic operation employed in numerous processes, e.g. constant coefficient FIR filters. In Field Programmable Gate Arrays (FPGAs), an addition should be carried out in the standard way employing ripple-carry adders, rather than carry-save adders as it is usually the case for ASICs. Consequently different adders optimisation techniques should be used in order to reduce area occupied by the adder tree. In this paper implementation of two different optimisation techniques: Genetic Programming (GP) and Simulated Annealing SA) are described. The implementation results of these techniques are compared to the previously published results for the Exhaustive Search (ES) and Greedy Algorithm (GrA). As a result, the SA usually outperforms the GP, and the SA gives about 10÷20% area reduction in comparison to the GrA. In conclusion, for the number of inputs to an adder tree N<8, the ES is the recommended algorithm as the number of possible combinations is usually acceptable, otherwise the SA should be employed. In the case when the time of finding the optimal adder tree is a critical factor, the GrA is recommended.
Słowa kluczowe
PL procesory specjalizowane   architektury systemów procesorowych   programowalne układy logiczne   arytmetyka rozproszona   systemy czasu rzeczywistego  
EN specialised processors   multiprocessors systems architecture   programmable logic device   distributed arithmetic   real-time systems  
Wydawca Wydawnictwo Naukowe PWN SA
Czasopismo Kwartalnik Elektroniki i Telekomunikacji
Rocznik 2002
Tom Vol. 48, z. 3/4
Strony 591--606
Opis fizyczny Bibliogr. 15 poz.
Twórcy
autor Wiatr, K.
autor Jamro, E.
  • Katedra Elektroniki, Akademia Górniczo-Hutnicza w Krakowie, Al. Mickiewicza 30, 30-059 Kraków
Bibliografia
Kolekcja BazTech
Identyfikator YADDA bwmeta1.element.baztech-article-BWA2-0009-0090
Identyfikatory