- author = "Jhe-Yu Liou and Xiaodong Wang and Stephanie Forrest and Carole-Jean Wu",
- title = "{GEVO: GPU} Code Optimization Using Evolutionary Computation",
- journal = "ACM Transactions on Architecture and Code Optimization",
- year = "2020",
- volume = "17",
- number = "4",
- pages = "Article 33",
- month = dec,
- keywords = "genetic algorithms, genetic programming, Genetic improvement, DEAP, GPGPU, SIMT, CUDA, LLVM intermediate representation, LLVM IR, PTX, GPU code optimization, approximate computing, NSGA-II, MOGA, MOGI, multi-objective evolutionary computation, Non-dominated sorting, Heuristic function construction, Support Vector Machine (SVM), ThunderSVM, Stochastic Gradient Descent, momentumSGD, Caffe2, ResNet, Rodinia, MNIST, income prediction a9a",
- ISSN = "1544-3566",
- publisher = "Association for Computing Machinery",
-
DOI = "
doi:10.1145/3418055",
-
code_url = "
https://github.com/lioujheyu/cuda_evolve",
- size = "28 pages",
- abstract = "GPUs are a key enabler of the revolution in machine learning and high-performance computing, functioning as de facto co-processors to accelerate large-scale computation. As the programming stack and tool support have matured, GPUs have also become accessible to programmers, who may lack detailed knowledge of the underlying architecture and fail to fully leverage the GPU's computation power. GEVO (Gpu optimization using EVOlutionary computation) is a tool for automatically discovering optimization opportunities and tuning the performance of GPU kernels in the LLVM representation. GEVO uses population-based search to find edits to GPU code compiled to LLVM-IR and improves performance on desired criteria while retaining required functionality. We demonstrate that GEVO improves the execution time of general-purpose GPU programs and machine learning (ML) models on NVIDIA Tesla P100. For the Rodinia benchmarks, GEVO improves GPU kernel runtime performance by an average of 49.48percent and by as much as 412percent over the fully compiler-optimized baseline. If kernel output accuracy is relaxed to tolerate up to 1percent error, GEVO can find kernel variants that outperform the baseline by an average of 51.08percent. For the ML workloads, GEVO achieves kernel performance improvement for SVM on the MNIST handwriting recognition (3.24) and the a9a income prediction (2.93 fold) datasets with no loss of model accuracy. GEVO achieves 1.79 fold kernel performance improvement on image classification using ResNet18/CIFAR-10, with less than 1percent model accuracy reduction.",
-
notes = "strongly typed Mutate-Copy LLVM-IR. list of mutations.
'crossover using the patch representation'. 'both
representations' ???
'fitness function as multi-objective (GEVO-mO) = min(time,error)'. 'held-out test cases'. 25% elitism, 75% tournament selection (population=256, generation 12..80+). LLVM-IR type based repair, does it use semantics too? 'GEVO uses dominator analysis to eliminate values ...' 'GEVO implements one-point messy crossover,which combines shuffle [17] and variable-length [54] crossover operations' (produces two children). 'our mutations are relatively expensive' 'The acceptance rate (ie child is ok) of crossover is as high as 80%, because each individual mutation has already been validated. DEAP \cite{DeRainville:2012:GECCOcomp}.
Intel Xeon E5-2640 CPU with 40 cores, 256 GB plus NVIDIA Tesla P100 GPU with 16 GB GPU memory, Ubuntu 16.04 with NVIDIA CUDA 10.1. 'nvprof introduced no overhead to kernel execution time
'each input set contains from tens of thousands to millions of input values'
'ML kernel variants are rejected if the training error exceeds the error achieved from the original kernel by the 1% threshold.'
B+Tree kernel improved five fold
Remove CUDA syncthread() 'As part of a wide deployment, additional post hoc methods, such as test-case generation or program analysis, could be employed to double-check that specific optimizations are indeed safe under the relevant use cases.' 'Removing Redundant Store.' Replaces with a temporary register.
'GEVO removes dead code'. 'Removing Redundant Load.' 'Loop Perforation.' 'Memoization.'
GEVO-mO compensatory evolution 'highlights the strength of a population-based search' 'the best kernel variant would not be found if a tighter error bound had been enforced from the beginning.'
'incomplete LU factorization'. 'sequential minimal optimization', 'perhaps by avoiding over fitting'.
'injecting inline-assembly in LLVM-IR' found to be unnecessary here.
'some programs for which GEVO was unable to find improvement' 'defeat some power side channel attacks.'
Arizona State University, Tempe, USA",
