Projektowanie akceleratorów algorytmów algebry liniowej przeznaczonych do implementacji w układach FPGA

• Autorzy: Ratuszniak P.

Warianty tytułu

EN

Design of linear algebra hardware accelerators dedicated to implementation in FPGA devices

• Języki publikacji: PL

Abstrakty

PL

W pracy przedstawiono metody projektowania akceleratorów obliczeniowych wybranych algorytmów algebry liniowej, przeznaczonych do implementacji w układach FPGA. Opisano dwie metody projektowe wykorzystujące algorytm ewolucyjny do odwzorowania przestrzennego grafu zależności informacyjnych w architektury równoległe. Pierwsza opisywana metoda projektowa służy do tworzenia architektur równoległych przetwarzających dane w sposób systoliczny, przeznaczonych do implementacji w wielokontekstowych układach reprogramowalnych. Druga metoda wykorzystywana jest do projektowania macierzy procesorowych przeznaczonych do implementacji w klasycznych układach FPGA. Parametry zaprojektowanych akceleratorów dla wybranych algorytmów algebry liniowej porównano z analogicznymi parametrami architektur równoległych, zaprojektowanymi z wykorzystaniem innych znanych metod projektowych.

EN

In this paper, methods for hardware linear algebra accelerators dedicated to implementation in FPGA devices, are presented. The two design methods with the use an evolutionary algorithm for allocation mapping are described. The first method is dedicated to creation a parallel architectures which process data on systolic type, dedicated to implementation into multicontext FPGA devices. The second method is used for design of processor array implemented in classic FPGA devices. Parameters of designed accelerators for exemplary linear algebra algorithms are presented and compared with parameters described parallel architectures obtained with the use of another design methods.

Słowa kluczowe

PL

macierze procesorowe; algebra liniowa; algorytmy ewolucyjne; układy FPGA; elektrotechnika; elektroenergetyka

EN

processor array; linear algebra; evolutionary algorithms; FPGA devices; electrical technology; electrical power engineering

• Wydawca: Wydawnictwo SIGMA-NOT
• Czasopismo: Przegląd Elektrotechniczny
• Rocznik: 2011
• Tom: R. 87, nr 10
• Strony: 155--158
• Opis fizyczny: Bibliogr. 25 poz., il., tabl., wykr.

Twórcy

autor

Ratuszniak P.

• Politechnika Koszalińska, Wydział Elektroniki i Informatyki, Katedra Inżynierii Komputerowej, ul. Śniadeckich 2, 75-453 Koszalin,

Bibliografia

• [1] Maslennikow O., Podstawy teorii zautomatyzowanego projektowania reprogramowalnych równoległych jednostek przetwarzających dla jednoukładowych systemów czasu rzeczywistego, Wyd. Uczelniane Politechniki Koszalińskiej, 2004
• [2] Culler D.E., Singh J.P, Gupta A., Parallel Computer Architectures, Morgan Kaufmann Pub (1999)
• [3] Akhter S., Roberts J., Multi-Core Programming, Intel Press (2006)
• [4] Wyrzykowski R., Klastry komputerów PC i architektury wielordzeniowe. Budowa i wykorzystanie. Wydawnictwo EXIT (2009)
• [5] Kirk D.B, Hwu W.W., Programming Massively Parallel processors, Morgan Kaufmann Pub (2010)
• [6] Kruger J., Westerman R., Linear algebra operators for GPU implementation of numerical algorithms, ACM Transaction on Graphics, Vol. 22, No.3 (2003), 908-916
• [7] Peterson M., FPGA Acceleration for outstanding performance. Challenges and Opportunities, Parallel Processing and Applied Mathematics (2009)
• [8] Dąbrowska A., Jamro E., Janiszewski M., Machaczek K., Russek P., Wiatr K., Wielgosz M., Akceleracja obliczeń HPC z zastosowaniem architektur FPGA, Konferencja I3:Internet – infrastruktury – innowacje (2009)
• [9] Hauck S. ed., Dehon A. ed., Reconfigurable computing. The theory and practice of FPGA-based computing, Morgan Kaufman Publishers (2008)
• [10] Gokhale M.B, Graham P.S., Reconfigurable Computing. Accelerating Computation with Field-Programmable Gate Array., Springer (2005)
• [11] Kestur S., Davis J., Williams O., BLAS Comparision on FPGA,CPU and GPU, IEEE Computer Society Symposium on VLSI (2010)
• [12] Chen Y.K., Kung S.Y., Trend and Challenge on System-on-a- Chip Designs, Journal of Signal Processing Systems 53, Springer, (2008), 217-229
• [13] Williams J., George A.D., Richardson J., Gosrani K., Suresh S., Computational Density of Fixed and Reconfigurable Multi- Core Devices for Application Acceleration, Proc. 4th Reconfigurable Systems Inst., Nat’l Center for Supercomputing Applications (2008)
• [14] Fields C., Design reuse strategy for FPGAs, Xcell jornal (2000), 40-42
• [15] Keating M., Bricaud P., Reuse Methodology Manual For System-on-a-Chip Design. Kluwer Academic Publishers (1999)
• [16] Rizzatti L., How to achieve design productivity increases using architectural synthesis, EDA Vision Magazine (2002)
• [17] Kung S.Y., VLSI array processors. Englewood Clifs, N.J., Prentice-Hall inc. (1988)
• [18] Quinton P., Robert Y., Systolic algorithms and architectures, Prentice Hall, Englewood Cliffs (1991)
• [19] Wyrzykowski R., Kanevsky Ju., Maslennikov O., Mapping recursive algorithms into processor arrays, Proc. Int. Workshop “Parallel numerics’94 (1994), 169-191
• [20] Fimmel D., Merker R., Design of processor Arrays for Reconfigurable Architectures, Kluwer Academic Publishers, The Journal of Supercomputing, nr.19 (2001), 41-56
• [21] Lipowska-Nadolska E., Kwapisz M., Lichy K., Systoliczne przetwarzanie sygnałów cyfrowych, Akademicka Oficyna Wydawnicza EXIT (2007)
• [22] Kazuteru Namba, Hideo Ito, Proposal of Testable Multi- Context FPGA Architecture, IEICE Transactions on Information and Systems, (2006)
• [23] Michalewicz Z., Genetic Algorithms + Data Structures = Evolutionary programs, Springer-Verlag Berlin Heidelber (1996)
• [24] Ratuszniak P., Maslennikow O., New Conception and Algorithm of Allocation Mapping for Processor Arrays Implemented into Multi-context FPGA Devices, Mathematica Balkanica, Vol. 23 (2009)
• [25] Ratuszniak P., Dekompozycja grafów zależności informacyjnych z wykorzystaniem algorytmu ewolucyjnego i programowania z ograniczeniami, Metody wytwarzania i zastosowania systemów czasu rzeczywistego, Praca zbiorowa pod red. L Trybusa i L. Samoleja, WKŁ, Rozdział 3 (2010)