- author = "Jhe-Yu Liou and Muaaz Awan and Steven Hofmeyr and Stephanie Forrest and Carole-Jean Wu",
- title = "Understanding the Power of Evolutionary Computation for {GPU} Code Optimization",
- howpublished = "arXiv",
- year = "2022",
- month = "25 " # aug,
- keywords = "genetic algorithms, genetic programming, grammatical evolution, GPU, GPGPU, GEVO, epistasis, LLVM Clang, LLVM-IR, nVida nvcc, PTX, Backus Normal Form, BNF, ADEPT, bioinformatics sequence alignment, SIMCoV, COVID viral spread, SBSE, Smith-Waterman algorithm, Software Engineering (cs.SE), Distributed, Parallel, and Cluster Computing (cs.DC), Performance (cs.PF), FOS: Computer and information sciences, FOS: Computer and information sciences",
- copyright = "Creative Commons Attribution 4.0 International",
-
URL = "
https://arxiv.org/abs/2208.12350",
-
DOI = "
doi:10.48550/ARXIV.2208.12350",
-
code_url = "https://github.com/lioujheyu/gevo",
- size = "12 pages",
- abstract = "Achieving high performance for GPU codes requires developers to have significant knowledge in parallel programming and GPU architectures, and in-depth understanding of the application. This combination makes it challenging to find performance optimisations for GPU-based applications, especially in scientific computing. This paper shows that significant speedups can be achieved on two quite different scientific workloads using the tool, GEVO, to improve performance over human-optimized GPU code. GEVO uses evolutionary computation to find code edits that improve the runtime of a multiple sequence alignment kernel and a SARS-CoV-2 simulation by 28.9percent and 29percent respectively. Further, when GEVO begins with an early, unoptimized version of the sequence alignment program, it finds an impressive 30 times speedup -- a performance improvement similar to that of the hand-tuned version. This work presents an in-depth analysis of the discovered optimizations, revealing that the primary sources of improvement vary across applications; that most of the optimizations generalize across GPU architectures; and that several of the most important optimizations involve significant code interdependencies. The results showcase the potential of automated program optimization tools to help reduce the optimization burden for scientific computing developers and enhance performance portability for domain-specific accelerators.",
-
notes = "p19 'demonstrates the excellent potential ... GEVO to
augment [human] developer efforts to optimize GPU
codes'
'code edits' p1 '6.7 million CPU hours .. (NERSC) Cori Supercomputer' nVidia P100, 1080Ti, V100: 3584, 3585, 5120 GPU cores.
p2 'up to 17 [mutations] contribute significantly to the optimization.' Fig 1 (GEVO) population of 256 LLVM IR edits, selection, crossover, mutation, (approx) 300 or 130 generations, 7 or 2 days. => NVPTX => PTX => fitness evaluation. mutation = copy, delete, move, replace, swap, replace the operand. 'strengthening a programmer understanding of system performance improvement opportunities.'
p3 stochastic simulation of 2D model of Lung epithelial cells and human immune system.
p4 'Over 90 percent of the GPU kernel runtime is spent moving T cells and spreading virus and inflammatory signals.'
'Fixing the random seed removes most of the stochasticity, but not all.' race condition (ie dont care...)
Three cases: with 1097, 1707, 1712 LLVM-IR instructions.
Validation not the same as training test (more onerous).
p5 variation between runs. 'some performance optimizations are GPU architecture-dependent.'
Post evolution 'Edit Minimization' removal of edits that speed up by less than 1 percent (reduce 1394 to 12) but twelve interact episatically with each other.
'code is robust against so many mutations while preserving required functionality.'
Fig 8: progressive improvement in performance (elite = 4/256 of population) even though genes interact.
p9 ' The developers were surprised that EC could synthesize code modifications with such large performance improvements' 'EC-driven optimization does not necessarily preserve exact program semantics, which is both a strengthand a limitation.'
p10 'There is no golden rule for finding optimal performance on GPUs.' 'EC can automate this search for counter-intuitive optimizations'",
