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. The # operator is used to signify channel accesses. 

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;

FSMLang Operators

FSMLang has the following set of built-in operators based on those available in VHDL:

  • Boolean Logic:
    • Basic binary boolean operators.
    • "and", "or", "xor", "not"
  • Arithmetic:
    • Addition, subtraction, multiplication, exponentiation, division
    • "+", "-", "*", "**", "/"
  • Bit-Wise Concatenation:
    • "&"
    • e.g. data16' <= x8 & y8;
  • Boolean Comparison Operators:
    • ">", ">=", "=", "/=", "<", "<="
  • Bit-Slicing Operators:
    • Parenthesized ranges
    • e.g. data4' <= data16(0 to 1) & data16(4 to 5);
  • Memory access
    • e.g. mem[x] <= mem[y] + 1;
  • Channel access
    • e.g. #my_chan <= mem[x];
    • e.g. mem[x + 1] <= #my_chan;
  • Function Calls
    • Built-ins (Standard library calls)
      • e.g. x' <= conv_std_logic_vector(99, 32);
    • Custom Functions
      • e.g. x' <= my_own_funtion(a, b, c, 99);

Coding Guidelines

  • Internal memories have 2 ports, External memories only have 1 port.
    • A given internal memory can be accessed a maximum of 2 times per state (uses dual-port BRAMs).
    • A given external memory can be accessed only once per state.
  • Channel accesses have non-deterministic access times (b/c they depend on external full/valid signals).
    • Therefore it is often "better" to put them in their own state without other logic.
      • This is especially important for BRAM accesses, as they may be repeatedly accessed while full/valid signals are not yet asserted.

FSMLang Syntax

The syntax of a valid FSMLang program consists of 2 major parts:

  1. FSM structure:
    1. Interface (input/output ports, compile-time generics, memory/channel interfaces).
    2. Internal state (internal signals).
  2. FSM logic:
    1. Define state machine logic (behavior).
    2. Individual guarded transitions containing assignment statements.
      1. Note: variable assignments must be "nexted", with a tick mark. Assignments to memories and channels do not require tick marks.

Defining FSM Structure

The structure portion must contain definitions for state signal names, generics, ports, output port connections, memories, channels, and internal signals. Each definition uses a simple list-like syntax to make FSMLang both easy to parse and easy to target from higher-level languages. 

-- **** Internal state signal names **** 
CS: <current_state_signal_name>; 
NS: <next_state_signal_name>; 

-- **** Generics (compile-time vars) **** 
GENERICS: 
(<genName>, <type>, <static_value>;)* 

-- **** Input/Output ports **** 
PORTS: 
(<portName>, <in|out>, <type>;)* 

-- **** Permanent connections between output ports and internal logic ****
CONNECTIONS: 
(<outputPortName> <= <rhs>;)* 

-- **** Definitions of memories **** 
MEMS: 
(<memName>, <dataWidth>, <addrWidth> [,EXTERNAL];)* 

-- **** Definitions of FIFO channels **** 
CHANNELS: 
(<channelName>, <dataWidth>;)* 

-- **** Internal FSM signals **** 
SIGS: 
(<sigName>, <type>;)*

Defining FSM Logic

The logic portion must define an initial state definition (start-up and reset), definitions of all state transitions, and native VHDL definitions. Each transition is defined in terms of source and destination states accompanied by an optional guard and state logic. Transition guards are boolean, and must be "instantly" evaluatable (no memory/channel access allowed in guard statements). Assignment statements within a given state occur atomically with an "all-at-once" semantics. Therefore, assignment statement ordering within a given transition does not have an effect on evaluation order, as all statements are evaluated concurrently. 

 
-- **** Internal State Definition **** 
INITIAL: <stateName>; 

-- *** Definition of logic/transitions **** 
TRANS: 
(<curr_st> [|<bool_guard>] -> <next_st>
[where {
  (<lhs> <= <rhs>;)*
}
])* 

-- **** Native VHDL Defs. **** 
VHDL: <un-parsed VHDL code>

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 initial full version of the compiler (parser, VHDL generation, and C generation) was implemented in about 4,000 lines of code. The code base has grown as new prototype features have been added, subtracted, tweaked, and tested. A few of the major FSMLanguage tweaks include:

  • 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.
      • New prototype features such as conditional assignment operators for code complexity reduction.
    • 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

FSMLang has been heavily used within CSDL at the University of Arkansas as both an introductory and advanced HW/SW co-design tool. It has been used to build several of the operating system accelerators in the hthreads project, as a basis for building embedded interpreters, and for creating application-specific accelerators and networking components.

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 following command performs reachability analysis on an FSM: 

reachable "../descrip_files/generic_bubblesort.des"

The following command can be used to generate a VHDL testbench template for an FSM (Note that the extension is left off of the last argument as this function generates both the testbench and the VHDL implementation simultaneously): 

gen_tb "sort_core" "../descrip_files/generic_bubblesort.des" "../vhdl_files/sort_core"

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.

Automatic Architecture Generation

The FSMLang compiler repository contains a prototype architecture compiler suited for building complete systems-on-chip. The compiler was originally meant for creating systems composed of FSMLang components, but it has been adapted for use in the construction of heterogeneous multi-core systems.

The ArchLang prototype has a template system that makes building heterogeneous (PowerPC + MicroBlaze) systems with a simple click of a button (almost). The template system creates a set of MHS/MSS files for use within the Xilinx EDK toolset. The hardware platform generated by the tool can then be further adapted, modified, and extended by hand. The scripts can be found in the FSMLang repository at the following link: 

https://hthreads.csce.uark.edu/svn/fsmLanguage/fpga_scripts/generate_fsm/src/

An example of how to run the system is shown below:

Open up Haskell interpreter 

> ghci

Load Program 

> :load ArchLangHetero.hs

Generate MHS/MSS files 

> gen_new_hetero_sys "<system_name>" <NUM_MBs>

It is important to note that each MicroBlaze (heterogeneous CPU) must be configured to execute the HAL bootloop code that is used in all of the pre-existing hthreads systems. This code can be found here, and should be copied into the EDK project directory and pointed to by each MicroBlaze BRAM-based application.

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