Self-cloning state machines on FPGA

Abstract

The purpose of this thesis is to continue development of a single state rep-resentation for use in a Self-Cloning State Machine. The Self-Cloning StateMachine can be used to represent Non-Deterministic Finite State Machines ona FPGA. NFSMs can be used to for instance match regular expressions andthe Self-Cloning State Machine is a run-time reconguration based approach tothis problem. Previous work has been performed on design tool experiments,choosing a FPGA vendor, and creating a denition of the singular state rep-resentation. This continuation focuses on further development of the singularstate and creating a system around it for experimentation.A system is designed to be used as an example model of a Self-Cloning StateMachine for the Virtex-4 FPGA. This system consists of several finite-statemachines built up by several singular states, a control system, and a resultmanagement module. The FSMs are connected together in order to model apreviously defined NFSM. To model the NFSM a control system is made toenable and disable the different FSMs as the transitions happen in the NFSM.Each of these FSMs have their own data path used for computing a simple op-eration based on a Multiply-Accumulate Circuit. The data path uses one-hotcoded state vectors from the FSM as its internal state machine. A deter-ministic version is also created to be able to compare the area and functionaldifferences. A comparison between the Self-Cloning State Machine and anothermethod of implementing a NFSM is made. There is also a brief comparisonof two dierent implementation methods for run-time reconguration with re-spect to ease of implementation. The two methods are a framework for run-timereconguration and a Virtual FPGA system.The modications made to the singular state representation are found to beappropriate for allowing the singular state to represent any state in any FSM.A problem was discovered with the size of the conguration register but theproblem can be solved. The control system, data path and result managementsystem functioned correctly and they were well suited to show the functionalityof a system like this one. Comparing the Self-Cloning State Machine to anotherimplementation method for NFSMs shows that this implementation demandsmuch more physical area which is a disadvantage, but the Self-Cloning StateMachine may be more flexible than the other method. The V-FPGA methodof performing run-time reconguration is found to be superior to another typeof framework created specically for the Virtex-4 FPGA.