- author = "Jhe-Yu Liou and Stephanie Forrest and Carole-Jean Wu",
- title = "Genetic Improvement of {GPU} Code",
- booktitle = "GI-2019, ICSE workshops proceedings",
- year = "2019",
- editor = "Justyna Petke and Shin Hwei Tan and William B. Langdon and Westley Weimer",
- pages = "20--27",
- address = "Montreal",
- month = "28 " # may,
- publisher = "IEEE",
- note = "{Best Paper}",
- keywords = "genetic algorithms, genetic programming, genetic improvement, Multi-objective Evolutionary Computation, GPU code optimization, LLVM Intermediate Representation, GPU, LLVM, CUDA, nvidia, GEVO, NSGA-II, ML, MNIST, Epistatis",
- isbn13 = "978-1-7281-2268-7",
-
URL = "
http://gpbib.cs.ucl.ac.uk/gi2019/Liou_2019_GI.pdf",
-
URL = "http://geneticimprovementofsoftware.com/paper_pdfs/liou2019genetic.pdf",
-
URL = "
https://dl.acm.org/citation.cfm?id=3339020.3339025",
-
DOI = "
doi:10.1109/GI.2019.00014",
-
code_url = "https://github.com/Xtra-Computing/thundersvm",
- acmid = "3339025",
- size = "8 pages",
- abstract = "As the programming stack and tool support for GPU have matured, GPUs have become accessible to programmers who often lack domain-specific knowledge of the underlying architecture and fail to fully leverage the GPU's computation power. This paper presents GEVO (Gpu EVOlution), a tool for automatically tuning the performance of GPU kernels in the LLVM representation to meet desired criteria. GEVO uses population-based search to find edits to programs compiled to LLVM-IR that improve performance on desired criteria and retain required functionality. GEVO extends earlier GI work by operating directly on the LLVM-IR without custom representations or other manual interventions. We demonstrate that GEVO improves runtime on NVIDIA Tesla P100 for many programs in the Rodinia benchmark suite and a supervised machine learning code, ThunderSVM. For the Rodinia benchmark, GEVO improves GPU kernel runtime performance by an average of 13.87percent and as much as 43percent over the fully compiler-optimized baseline. If the kernel output accuracy is relaxed to tolerate 1percent error, GEVO can find kernel variants that outperform the baseline version by an average of 15.47percent. For ThunderSVM, GEVO reduces entire model training time by 50percent and 24.8percent, for MNIST handwriting recognition dataset and a9a income prediction, where the accuracy of trained model are improved by 0.17percent and 0.04percent respectively.",
-
notes = "Jhe-Yu (Jerry) Liou
GPGPU code https://github.com/Xtra-Computing/thundersvm
Slides: http://geneticimprovementofsoftware.com/slides/liou2019genetic_slides.pdf
Mutation of LLVM IR intermiedate representation (copy, delete, move, replace, swap instructions/operands) of nVidia CUDA GPU kernel device code often breaks LLVM syntax and so mutation requires repair. Crossover uses mutation's patches to LLVM-IR representation. Crossover randomises patch order so 2 parent patches are split between two offspring, cf uniform crossover, possibly in a new order. GEVO runtime two days.
Benchmarks Rodinia and ThunderSVM.
Epistatis: Observed 3 key mutations, introducing 0.3 error rate individually, but only incurring 0.1 error rate when combined. Sub-optimal individual can be served as the stepping stone for better optimization combination. This implies error tolerance can be used for circumventing and reaching other program spaces.
Examples of optimsation. Eg of LU decomposition where evolution removes redundant store.
Arizona State University
GI-2019 http://geneticimprovementofsoftware.com part of \cite{Petke:2019:ICSEworkshop}",
