Result Details

Acceleration of Grammatical Evolution Using Graphics Processing Units

POSPÍCHAL, P.; JAROŠ, J.; SCHWARZ, J. Acceleration of Grammatical Evolution Using Graphics Processing Units. 7th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science. Brno: Vysoké učení technické v Brně, 2011. s. 125-125. ISBN: 978-80-214-4305-1.
Type
abstract
Language
Czech
Authors
Pospíchal Petr, Ing., DCSY (FIT)
Jaroš Jiří, prof. Ing., Ph.D., DCSY (FIT)
Schwarz Josef, doc. Ing., CSc., DCSY (FIT)
Abstract

Několik článků již ukázalo, že symbolická regrese je vhodná pro analýzu dat a predikci ve finančních trzích. Gramatická evoluce a na gramatice založené genetické programování byly úspěšně aplikovány při řešení mnoha problémů včetně symbolické regrese. Nicméně, často je nutno vynaložit značné výpočetní prostředky k výpočtu vhodnosti daného řešení, což může limitovat oblast použití a/nebo provedené experimenty. 

Tento článek se zabývá možností použít klasické grafické karty pro akceleraci gramatické evoluce řešící symbolickou regresi. 
Jsou diskutovány detaily optimalizace kódu na GPU a je analyzován NVCC kompilátor. Navrhujeme efektivní mapování algoritmu na CUDA platformě s respektováním omezení GPU, jako jsou úzké hrdlo PCI-express sběrnice a transakce do hlavní paměti.
Toto je první případ, kdy byla gramatická evoluce akcelerována na GPU. Porovnáváme implementace běžící na CPU Core i7 a GPU GTX 480 spolu s knihovnou implementovanou v javě, GEVA. 
Výsledky ukazují, že náš algoritmus poskytuje stejně kvalitní řešení a je vhodný pro větší počet regresních bodů, kde dosáhl zrychlení až 39x při porovnání se sekvenčním CPU kódem napsaným v C. 
English abstract
Several papers show that symbolic regression is suitable for data analysis and prediction in financial markets. Grammatical Evolution (GE), a grammar-based form of Genetic Programming (GP), has been successfully applied in solving various tasks including symbolic regression. However, the computational effort to calculate the fitness of a solution in GP can often limit the area of possible application and/or the extent of experimentation undertaken. 
This paper deals with utilizing mainstream graphics processing units (GPU) for acceleration of GE solving symbolic regression. GPU optimization details are discussed and the NVCC compiler is analyzed.  We design an effective mapping of the algorithm to the CUDA framework, and in so doing must tackle constraints of the GPU approach, such as the PCI-express bottleneck and main memory transactions. 
This is the first occasion GE has been adapted for running on a GPU. We measure our implementation running on one core of CPU Core i7 and GPU GTX 480 together with a GE library written in JAVA, GEVA.
 Results indicate that our algorithm offers the same convergence, and it is suitable for a larger number of regression points where GPU is able to reach speedup to 39 times faster when compared to GEVA on a  serial CPU code written in C.
Keywords

CUDA, gramatická evoluce, grafické čipy, CPU, GPGPU, zrychlení, symbolická regrese

English keywords

CUDA, grammatical evolution, graphics chips, GPU, GPGPU, speedup, symbolic regression

Published
2011
Pages
125–125
Book
7th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science
Conference
7th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science
ISBN
978-80-214-4305-1
Publisher
Vysoké učení technické v Brně
Place
Brno
BibTeX 
@misc{BUT193911,
  author="Petr {Pospíchal} and Jiří {Jaroš} and Josef {Schwarz}",
  title="Acceleration of Grammatical Evolution Using Graphics Processing Units",
  booktitle="7th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science",
  year="2011",
  pages="125--125",
  publisher="Vysoké učení technické v Brně",
  address="Brno",
  isbn="978-80-214-4305-1",
  note="Abstract"
}
Departments
Department of Computer Systems (DCSY)
Back to top