FSMLanguage

From Hybridthreads Wiki

Jump to: navigation, search

Contents

Finite-State Machines

Finite-state machines, or FSMs, are a useful model for describing systems (hardware, software, biological, etc.). FSMs are composed of:

  • A finite-set of states.
  • Transitions between the states.
  • Actions within the states.

Describing finite-state machines (FSMs) in VHDL or Verilog is a straight-forward process, however there is a lot of room for error. The verbosity of most HDLs makes it very easy to "forget" to add a signal/variable in all of the right places, and this can result in the inference of incorrect logic. For instance, some of the most common mistakes include:

  • Forgetting to add signals to sensitivity lists.
    • Results in incorrect simulation results.
  • Forgeting to set default values for FSM signals.
    • Results in generation of latches instead of flip-flops.
    • Causes an increase in hardware size and introduces undesirable timing properties.
  • Forgetting to properly reset FSM signals.
    • Results in strange start-up behavior.
  • Forgetting to add delay cycles when interacting with Block RAMs or other IP components
    • Results in incorrect data, and possibly data races.

FSMLanguage is a domain-specific language for specifying FSMs in a clear and concise manner. The syntax of FSMLanguage is built in such a way that programs are self-documenting, and the FSMLanguage compiler allows one to automatically generate control-flow graphs (CFGs) and VHDL implementations of FSMs with the simple press of a button. The FSMLanguage and it's compiler(s) have been designed to target modern platform FPGAs. The compiler is able to take advantage of soft processors, embedded BRAMs, and dedicated point-to-point FIFOs when generating code for FPGAs. The language allows one to describe a complete HW/SW co-designed system that can be re-partitioned by a compiler without having to undergo re-coding of individual FSMs.

FSMLanguage Abstractions

FSMLanguage has built-in constructs for defining generics, ports, state variables, port connections, reset logic, and state machine logic. The language also includes a memory abstraction that allows the user to easily define and interface with Block RAMs (BRAMS) using a C-style array syntax. Another important feature is the channel abstraction which allows the user to define bi-directional communication channels that are targetted to use a fast-simplex link (FSL) to connect different IP components together.

The language structure allows one to easily describe FSMs in a way that eliminates many of the common errors that occur when describing FSMs in typical HDLs. The FSMLanugage compiler automatically generates correct code for FSM reset, sensitivity lists, memory access schemes, FSM flip-flops, and state transitions. The abstractions for memories and channels allow programmers to use familiar, software-like constructs for describing timing- and synchronization-sensitive operations. Additionally, these abstractions are re-targetable, and can be used in both software or hardware implementations of FSMLanguage programs -- allowing one to easily change the HW/SW partitioning of an application.

Example: Block RAM Access in FSMLanguage

The following code in FSMLanguage performs a read-modify-write to location 'addr' in memory 'bram1'. 

state1 -> state2 where
{
  bram1[addr] <= bram1[addr] + bram2[addr];
}

This same process in VHDL requires the following code, which requires a programmer to explicitly sequence read/write control signals and data staging. 

when state1 =>
  bram1_addr <= addr;
  bram1_ena  <= '1';

  bram2_addr <= addr;
  bram2_ena  <= '1';

  next_state <= state1_intermediate;

when state1_intermediate =>
  -- Idle state
  next_state <= state1_final;

when state1_final =>
  bram1_addr <= addr;
  bram1_ena  <= '1';
  bram1_wea  <= '1';
  bram1_din  <= bram1_dout + bram2_dout;

  next_state <= state2;

Example: Channel (FSL) Access in FSMLanguage

The following code in FSMLanguage sends the value stored in register 'x' over a the 'outbound' channel, followed by a a read on the 'inbound' channel. 

state1 -> state2 where
{
  #outbound <= x;
}
state2 -> state3 where
{
  x' <= #inbound;
}

This same process in VHDL requires the following code, which requires a programmer to explicitly monitor the FSL control lines to make sure that the FIFO is not full before writing the value of 'x' in. 

when state1 =>
  if (outbound_full = '1') then
     next_state <= state1;
  else
     outbound_din   <= x;
     outbound_write <= '1';
     next_state     <= state2;
  end if;
when state2 =>
  if (inbound_exists = '0') then
     next_state <= state2;
  else
    x              <= inbound_dout;
    inbound_read   <= '1'; 
    next_state     <= state3;
  end if;

Development History

FSMLanguage was developed on an Apple MacBook in Haskell, using GHC and Parsec during the dark hours of Winter Break 2007. The initial prototype of the compiler was written in Python, but as the language became larger, the Python code began to become less structured. Once this began to happen I decided to move to Haskell in order to maintain a clean and concise code base. Altogether the compiler (parser, VHDL generation, and C generation) is implemented in about 4,000 lines of code.

FSMLanguage has a few new back-end tweaks that allow it to generate code for:

  • SMI (a core that is destined to become the new hthread's HWTI) - http://hthreads.csce.uark.edu/wiki/PLB_HWTI
    • New function "gen_hwt"
  • ReconOS OSIF - http://www.reconos.de/twiki/bin/view/ReconOS/ReconOSFSMLang
    • New SVN branch hosted at UNI Paderborn, collaboration between Jason Agron and Markus Happe
    • Implements all blocking OSIF system calls and uses array-like syntax for local BRAM access
  • Arbitrary Bit-Width Operation Support in C
    • Uses structure types (structs) for all FSM signals and data
      • Necessitates the use of pack/unpack operations as well as function calls for all FSM primitives
    • Implemented in a separate compiler branch (/src_arbitrary)
  • FSMLanguage as a compiler target
    • CheapThreads to FSMLang compilation flow for high-assurance, secure components.
      • Research in conjunction with MU's HASK Lab and NRL.
    • KISS-to-FSMLang compiler
      • Regression testing and generation of VHDL for synthesis tests
    • Prototype of a WHILE-to-FSMLanguage compiler
      • A good teaching resource for courses on programming languages, interpreters, and compilers
  • ArchLang - language for describing the interconnection of FSMLang components
    • Capable of generating MHS/MSS descriptions suitable for use with the Xilinx EDK toolset

FSMLanguage Compiler

If you would like to use the FSMLanguage compiler, please check out the following subversion repository:

FSMLanguage 
https://hthreads.csce.uark.edu/svn/fsmLanguage

The FSMlanguage compiler makes use of:

The FSMLanguage compiler is made up of several components: a Parsec-based parser, elaboration passes, and a set of code generators. Currently there are 4 major code generators: a VHDL back-end, a C (native type) back-end, a C (structured type) back-end, and a DOT back-end for CFG visualization.

Example Usage

First, make sure that GHCi and DOT/DOTTY (GraphViz) is installed, then you can check out the compiler from Subversion using the following command: 

svn co https://hthreads.csce.uark.edu/svn/fsmLanguage fsmLang

Next, go to the location of the compiler sources in the downloaded repository and start up the Haskell interpreter (GHCi), and load the FSMLanguage compiler: 

cd fsmLang/fpga_scripts/generate_fsm/src/
ghci
:load LangParser

The following command translates an FSMLanguage program into VHDL. More specifically, the following takes a description of bubble sort in FSMLanguage and translates it into a VHDL entity called sort_core: 

gen_fsm "sort_core" "../descrip_files/generic_bubblesort.des" "../vhdl_files/sort_core.vhd"

The following command translates an FSMLanguage program into C. Note their are 2 different C compilers, one in the /src directory and one in /src_arbitrary: 

gen_sw "sort_core" "../descrip_files/generic_bubblesort.des" "../c_files/sort_core.c"

The following command can be used to generate the control-flow graph for an FSM: 

gen_cfg "../descrip_files/generic_bubblesort.des" "../dot_files/sort_core.dot"

The DOT file can then be turned into a PDF or SVG using the following commands: 

dot -Tpdf sort_core.dot > sort_core.pdf

Additionally, the subversion repository has some visualization scripts for generating PDFs and SVGs of DOT files: 

cd fsmLang/fpga_scripts/fsm_visualizer/src

To generate a PDF type: 

./showGraph_linux.sh <DOT_FILE>

Or, to generate an SVG file that is hyperlinked back to the FSM description type: 

./gen_svg.sh <DOT_FILE>

To exit GHCi, simply type the following: 

:quit

FSMLanguage Examples

BubbleSort

A simple example is the implementation of a BubbleSort routine. BubbleSort is an iterative "in-place" sort that operates on a single array of data, which maps very easily to an FSM that interacts with a single Block RAM as can be seen in the FSMLanguage example below.

BubbleSort in FSMLanguage

BubbleSort in VHDL (Auto-Generated from FSMLanguage)

BubbleSort in C (Auto-Generated from FSMLanguage Using Native Type C Compiler)

BubbleSort in C (Auto-Generated from FSMLanguage Using Struct Type C Compiler)

  • C Source
  • The struct type compiler uses objects to handle arbitrary bit-width operations in C
  • 416 lines of code

Multiply Accumulate (MACC)

Simple multiply accumulate core that has a fixed number of accumulations controlled by a built-in counter.

MACC in FSMLanguage

MACC in VHDL (Auto-Generated from FSMLanguage)

MACC in C (Auto-Generated from FSMLanguage Using Struct Type C Compiler)

  • C Source
  • The struct type compiler uses objects to handle arbitrary bit-width operations in C
  • 337 lines of code

FSMLang Case Studies

The FSMLang Case Studies page contains results of using FSMLanguage in case studies.

Publications

Presentations

Copyright

FSMLanguage has been developed by Jason Agron with heaping loads of help from Garrin Kimmell.

Retrieved from "http://hthreads.csce.uark.edu/wiki/FSMLanguage"
Personal tools