9513

GPU Acceleration of a Genetic Algorithm for the Synthesis of FSM-based Bimodal Predictors

Martin Burtscher, Hassan Rabeti
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}

}

Download Download (PDF)   View View   Source Source   

2042

views

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.
Rating: 2.5/5. From 1 vote.
Please wait...

* * *

* * *

HGPU group © 2010-2024 hgpu.org

All rights belong to the respective authors

Contact us: