Vol.10, No 1, 2011 pp. 59 - 70
UDC
62-231.2 519.216 004.272.2:004.42 004.438GPU
COMPUTATION OF DYADIC CONVOLUTION ON GPU FOR EFFICIENT MODELING OF DYADIC LTI SYSTEMS
Dušan B. Gajić, Radomir S. Stanković
Department of Computer Science, Faculty of Electronic Engineering,
University of Niš, Aleksandra Medvedeva 14, 18 000 Niš, Serbia
E-mail: dule.gajic@gmail.com , radomir.stankovic@gmail.com
Abstract.
Convolution systems are an important class of systems often used in many practical applications in different areas of science and engineering. In the case of systems with binary encoded input and output signals, finite dyadic groups are usually assumed as the underlying algebraic structure. Modeling and handling of such systems requires frequent computation of the dyadic convolution. This paper discusses a method for efficient computation of the dyadic convolution on Graphics Processing Units (GPUs) with the related algorithm implemented in Open Computing Language (OpenCL). We consider several important issues concerning the efficient mapping of the algorithm to the GPU architecture. Performance of the proposed implementation is compared with the referent C/C++ implementation processed on the Central Processing Unit (CPU). Experimental results confirm that significant speedups are achieved by the application of the proposed GPU calculation method.
Key Words:
Linear translation invariant (LTI) systems, Dyadic convolution, Fast Walsh transform (FWT), GPU parallel programming, OpenCL.
IZRAČUNAVANJE DIJADIČKE KONVOLUCIJE NA GRAFIČKIM PROCESNIM JEDINICAMA ZA EFIKASNO MODELOVANJE DIJADIČKIH LTI SISTEMA
Konvolucioni sistemi predstavljaju važnu klasu sistema koji se često koriste u mnogim praktičnim primenama u različitim oblastima nauke i inženjerstva. U slučaju kada su ulazni i izlazni signali binarno kodirani, obično se kao algebarska struktura na kojoj su definisani odgovarajući sistemi uzimaju konačne dijadičke grupe. Modelovanje i rad sa ovakvim sistemima zahtevaju veoma česta izračunavanja dijadičke konovlucije. U ovom radu predstavljen je metod za efikasno izračunavanje dijadičke konvolucije na grafičkim procesnim jedinicama (Graphics Processing Units - GPUs) pri čemu je odgovarajući algoritam implementiran primenom programskog jezika Open Computing Language (OpenCL). Razmotreno je nekoliko veoma značajnih pitanja koja se tiču efikasnog mapiranja algoritma na arhitekturu grafičkih procesnih jedinica. Performanse predložene implementacije upoređene su sa referentnom C/C++ implementacijom koja se izvršava na centralnoj procesnoj jedinici (Central Processing Unit - CPU). Eksperimentalni rezultati potvrđuju da primena predloženog metoda za izračunavanje dijadičke konvolucije na GPU donosi značajna ubrzanja u odnosu na referentnu CPU implementaciju.
Ključne reči:
Linearni translaciono nezavisni sistemi, Dijadička konvolucija, Brza Walsh-ova transformacija, GPU paralelno programiranje, OpenCL
