GPU Acceleration of a Genetic Algorithm for the Synthesis of FSM-based Bimodal Predictors
Department of Computer Science, Texas State University, San Marcos, TX, USA
International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA’13), 2013
@article{burtscher2013gpu,
title={GPU Acceleration of a Genetic Algorithm for the Synthesis of FSM-based Bimodal Predictors},
author={Burtscher, Martin and Rabeti, Hassan},
year={2013}
}
This paper presents a fast GPU implementation of a genetic algorithm for synthesizing bimodal predictor FSMs of a given size. Bimodal predictors, i.e., predictors that make binary yes/no predictions, are ubiquitous in microprocessors. Many of these predictors are based on finite-state machines (FSMs). However, there are countless possible FSMs and even heuristic searches for finding good FSMs can be slow when billions of predictions need to be assessed. We designed such a search heuristic that maps well onto GPU hardware. It is based on a multi-start genetic algorithm. On our six traces, the resulting FSMs are 1% to 29% more accurate than saturating up/down counters. On a Kepler-based GTX 680, the CUDA implementation evaluates 18 to 73 billion predictions per second, which is 14 to 18 times faster than a multicore version running on a hex-core Xeon X5690 with hyper-threading.
June 4, 2013 by hgpu
