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

• Autorzy: Wiatr K. , Jamro E.
• 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

• 1. K. Wiatr, E. Jamro: Constant Coefficient Multiplication in FPGA Structures. Proceedings of the 26th Euromicro Conference, Maastricht, The Netherlands, Sep. S-7 2000, Vol. I, pp. 252-259.
• 2. T. T. Do, C. Reuter, P. Pirsch: Alternative Approaches Implementing High-Performance FIR Filters on Look-up-table Based FPGAs: A Comparison. SPIE Conference on Configurable Computing and Applications, Boston, Massachusetts, 2-3 Nov. 1998, pp. 248-254.
• 3. K. Wiatr, E. Jamro: Implementacja układów dodających wchodzących w skład konwolwera w układach programowalnych FPGA. Kwartalnik Elektronika i Telekomunikacja PAN, Warszawa 2001, 48, z. 3 -4, ss. 571-589.
• 4. A. R. Omondi: Computer Arithmetic Systems. Algorithms Architecture and Implementations. Prentice Hall, UK, 1994.
• 5. R. A. Hawley et, al.: Design Techniques for Silicon Compiler Implementation of High-Speed FIR Digital Filters. IEEE Journal of Solid-State Circuits, May 1996, vol. 31, no 5, pp. 656-667.
• 6. Xilinx Co. The Programmable Logic Data Book 1999.
• 7. Altera Co. Apex 20K Programmable Logic Device Family, Data Sheet. ver. 2.05, Nov. 1999.
• 8. S. Xing, W. W. H. Yu: FPGA Adders: Performance Evaluation and Optimal Design. IEEE Design & Test of Computers, Jan.-Mar. 1998, pp. 24-29.
• 9. E. H. Aarts, J. Korst: Simulated Annealing and Boltzman Machines. Chichester, UK, Wiley 1989.
• 10. S. Kirkpatrick, C. D. Gelatt, M. P. Vecchi: Optimisation by Simulated Annealing. Science, 220 (4598), May 1983: pp. 671-680.
• 11. J. R. Koza: Genetic Programming: On the Programming of Computers by Means of Natural Selection. Cambridge, MA: The MIT Press, 1992.
• 12. Z. Michalewicz: Genetic Algorithm + Data Structure = Evolutions Programs. Berlin, Spinger-Verlag 1992.
• 13. T. Aytekin, E. E. Korkmaz, H. A. Guvernir: An Application of Genetic Programming to the 4-Op Problem using Map-Trees, in Xin Yao Progress in Evolutionary Computation, Selected Papers on AT'93 nad AI’94 Workshops on Evolutionary Computation. Berlin, Springer, 1995, pp. 28-40.
• 14. M. L. Maudlin: Maintaining Diversity in Genetic Search. AAAI Proc. National Conference on Artificial Inteligence, 1984, pp. 247-250.
• 15. G. McMahon, D. Hadinoto: Comparison of Heuristic Search Algorithms for Single Machine Scheduling Problems, in Xin Yao Progress in Evolutionary Computation, Selected Papers on AI’93 nad AI’94 Workshops on Evolutionary Computation. Berlin, Springer, 1995, pp. 293-304.