Self-cloning state machines on FPGA
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 State
Machine can be used to represent Non-Deterministic Finite State Machines on
a FPGA. NFSMs can be used to for instance match regular expressions and
the Self-Cloning State Machine is a run-time reconguration based approach to
this 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 singular
state and creating a system around it for experimentation.
A system is designed to be used as an example model of a Self-Cloning State
Machine for the Virtex-4 FPGA. This system consists of several finite-state
machines built up by several singular states, a control system, and a result
management module. The FSMs are connected together in order to model a
previously defined NFSM. To model the NFSM a control system is made to
enable 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-hot
coded 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 functional
differences. A comparison between the Self-Cloning State Machine and another
method of implementing a NFSM is made. There is also a brief comparison
of two dierent implementation methods for run-time reconguration with re-
spect to ease of implementation. The two methods are a framework for run-time
reconguration and a Virtual FPGA system.
The modications made to the singular state representation are found to be
appropriate for allowing the singular state to represent any state in any FSM.
A problem was discovered with the size of the conguration register but the
problem can be solved. The control system, data path and result management
system functioned correctly and they were well suited to show the functionality
of a system like this one. Comparing the Self-Cloning State Machine to another
implementation method for NFSMs shows that this implementation demands
much more physical area which is a disadvantage, but the Self-Cloning State
Machine may be more flexible than the other method. The V-FPGA method
of performing run-time reconguration is found to be superior to another type
of framework created specically for the Virtex-4 FPGA.
Place, publisher, year, edition, pages
Institutt for elektronikk og telekommunikasjon , 2013. , 80 p.
IdentifiersURN: urn:nbn:no:ntnu:diva-21833Local ID: ntnudaim:9902OAI: oai:DiVA.org:ntnu-21833DiVA: diva2:644232
Svarstad, Kjetil, Professor