15.6.6. Finite State Machine

DSP Builder for Intel® FPGAs (Advanced Blockset): Handbook

Download PDF

ID 683337

Date 12/12/2022

Version

Public

A newer version of this document is available. Customers should click here to go to the newest version.

Visible to Intel only — GUID: jkx1613473073764

Ixiasoft

View Details

15.6.6. Finite State Machine

The Finite State Machine block adds state machines to a DSP Builder design. You can describe your Finite State Machine using the FSM specification language, which you enter into a text file. Then you load that text file using the Finite State Machine block and wire up the input and output ports of the Finite State Machine block to the rest of your design. DSP Builder then generates appropriate loop (ForLoop) and lookup-table (LUT) structures to implement the state-machine described in the text file you provide. However, those ForLoop and LUT blocks are not directly visible in the DSP Builder design. DSP Builder translates the ForLoop and LUT blocks to RTL with automatic device mapping and latency balancing with the rest of your DSP Builder design. DSP Builder provides a finite state machine example design, demo_fsm.mdl, which shows how to use the Finite State Machine block to filter out specific numerical values from an input stream.

FSM Specification Language

The FSM specification language supports the following features:

Boolean expressions to form state transition style FSMs
Nested, dependent, loops which allow you to express, for example, rectangular and triangular counters
Automatic dead-cycle hiding at loop completion

The configuration text file specifies the Finite State Machine block to generate.

The file has two sections:

Options that are optional settings to override certain defaults such as the name of the XML file and external port names
Netlist components that define the ForLoop blocks and state transitions, and how they fit together (i.e. nesting or sequencing structure) that defines the behavior of the state machine

The keyword netlist separates these two sections:

option settings ...
netlist...
netlist components ...

Options

Table 270. Options
Option	Description
`inputs` `<port-name>`	Specify one or more boolean input ports that DSP Builder uses in conditional expressions for state transitions.
`enable` `<port-name>`	Add an optional enable with the specified port name. Default is to tie enable to V_CC.
`start` `<port-name>`	Specify a different name for the `go` port. A one-cycle pulse on this port starts the Finite State Machine block.
`finish` `<port-name>`	Add a finish port with the name as specified. The port emits a one-cycle pulse from this port when the Finite State Machine completes. This port allows two or more Finite State Machine blocks to daisy chain, or to nest an Finite State Machine in a ForLoop block.

Figure 112. Options Example

# this is a comment
inputs d0 d1
enable en
start begin
finish done
netlist
    ...

Netlist Components

Figure 113. Netlist Components Example

Instantiates a ForLoop block <name> and inequality operator set to <, <=, >, or >=. The values that you specify for <init>, <step>, and <limit> drive the input ports of the ForLoop block.

for <name> <init> <inequality-op> <limit> step <step>: <port-name> ...
 ... nested components
end

If <step> is 1, you can omit it. For example:

for x 0 < 8
end

The port-names are optional. If specified, they must correspond to the names of ForLoop output ports:

Name	Output Port
bs	Body Start
ld	Loop Done
el	Empty Loop
fl	First Loop
ll	Last Loop
v	Valid
c	Counter

For example:

for x 8 >= 0 step -1 : ld v c
end

You can nest ForLoop blocks:

for x 8 >= 3 step -1
    for y 0 < x
    end
end

The inner ForLoop <limit> is specified to be the counter value of the outer ForLoop

You can select state transitions:

transitions <name> : <port-name> ...
 ... state transitions
end

You specify state transitions by the following inputs:

state <current-state>
if (<condition>) <next-state> <output-value> ...
Each state definition can be followed by one or more if transition statements. The last transition of a state definition can be a catch-all default transition:
default <next-state> <output-value> ...

The output-values are a list of boolean values (0 or 1). There must be the same number of output-values as port-names specified on the transitions line. For example:

transitions Sticky : q r
state Start
if (a) Next 1 0
default Start 1 1
state Next 
if (~a) Start 0 1
end

If you omit default, the Finite State Machine assumes an implicit catch-all default transition where the next-state is the same as the current-state and all output-values are 0.

You can specify a finish port for a state transition style Finite State Machine that produces a pulse for one cycle when the Finite State Machine, after it is activated on receipt of the token (or go signal), returns back to its initial state on completion. This corresponds to passing on the token to the next Finite State Machine component in the sequence.

transitions Wait : q r
finish waitDone
 ... state transitions
end

You can freely mix transitions...end Finite State Machine blocks with for..end Finite State Machine blocks to form a Finite State Machine sequence. Also you can nest these Finite State Machine sequences inside a for...end Finite State Machine that may be a member of another Finite State Machine sequence. The transitions Finite State Machine does not support you nesting a Finite State Machine sequence inside it.

Nested ForLoops

Figure 114. Nested ForLoops

for row 0 < 8 : c

    for col 0 < 8 : c v


    end

end

Triangular Nested Iteration

Figure 115. Triangular nested iteration

for row 1 < 8 : c

    for col 0 < row : c v


    end

end

Strategies for Hiding Dead Cycles

Figure 116. dead cycle end early

for row 0 < 8 : c

    deadcycle endearly

    for col 0 < 8 : c v

    end

end

The deadcycle endearly strategy is a simple transformation of the netlist that reduces the number of iterations of the innermost loop by one. The example is functionally equivalent to:

for row 0 < 8 : c

    for col 0 < 7 : c v

    end

end

This strategy only makes sense if the innermost ForLoop body is empty or has zero latency, so that each iteration takes one cycle to compensate for the one cycle spent in the outer loop iteration. The control signals also reflect the shortened iteration space such that the last-loop and loop-done signals go high one cycle earlier. You need to compensate for this in your design.

Figure 117. dead cycle shiftrange

for x 0 < 4

    deadcycle shiftrange


    for y 8 >= 1 step -1

        deadcycle shiftrange


        for z 0 < y : v c

        end

    end

end

The deadcycle shiftrange strategy overlaps each iteration of the outer ForLoop with the first iteration of the inner ForLoop. However, in triangular nested iteration, the inner ForLoop needs to access the outer ForLoop block's counter value before it completes its own iteration cycle. To resolve this dependency, the outer ForLoop iterates over the range from (init+step) to (limit+step), i.e. its range is shifted forward by one iteration step. This transformation is only applicable if the outer ForLoop block's parameters are all constants. The following construction does not work:

for x 0 < 4

    for y 8 >= x step -1
        deadcycle shiftrange

        for z 1 < 5

The y-ForLoop block's limit depends on the x-ForLoop block's counter. It is not trivial to shift the range of the y-ForLoop without affecting other ForLoop blocks.

Figure 118. dead cycle oneahead

for x 0 < 4

    for y 8 >= x step -1

        deadcycle oneahead

        for z 0 <= y : v c


        end

    end

end

The deadcycle_oneahead strategy is similar to the shiftrange strategy but the FSM does not require the outer ForLoop block's parameters to be constants. In the example, the y-ForLoop block's limit is the x-ForLoop block's counter. The netlist transformation uses more elaborate control logic that pre-advances the outer ForLoop by one iteration before initialising the inner ForLoop. This approach doesn't work for deeper nesting structures such as:

for x 0 < 4

    deadcycle oneahead

    for y 8 >= 1 step -1

        deadcycle oneahead

        for z 0 < y : v c

Although the FSM hides the dead-cycle in the x-ForLoop, the FSM inserts an extra cycle to pre-advance the y-ForLoop when applying its dead-cycle hiding strategy.

You can mix and match the different dead-cycle hiding strategies

Select Your Language

Using Intel.com Search

Quick Links

Recent Searches

Advanced Search

Only search in

DSP Builder for Intel® FPGAs (Advanced Blockset): Handbook

15.6.6. Finite State Machine

FSM Specification Language

Options

Netlist Components

Nested ForLoops

Triangular Nested Iteration

Strategies for Hiding Dead Cycles