FSM_GA is a GPU-accelerated implementation of a genetic algorithm (GA) for finding well-performing finite-state machines (FSM) for predicting binary sequences.
Click on FSM_GA10.cu to download the source code. A description of the FSM_GA implementation and its usage is available here. Note that the FSM_GA code is protected by this license and that by obtaining the FSM_GA code you agree to the terms and conditions set forth in this license.
The source code can be compiled into an executable called FSM_GA as follows:
nvcc -O3 -arch=sm_35 FSM_GA10.cu -o FSM_GA
To compute a good FSM for the input
The input must be a binary file consisting of 16-bit words. The least significant bit of each word is the bit to be predicted. The remaining 15 bits form an ID, for example, they could be part of the PC value of the instruction that produced the bit.
M. Burtscher and H. Rabeti. "GPU Acceleration of a Genetic Algorithm for the Synthesis of FSM-based Bimodal Predictors." 2013 International Conference on Parallel and Distributed Processing Techniques and Applications. July 2013. [pdf] [pptx]
This work has been supported in part by the National Science Foundation as well as by equipment donations from Nvidia Corporation.