15.6.6. Finite State Machine
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 ...
|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 VCC.|
|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.|
# this is a comment inputs d0 d1 enable en start begin finish done netlist ...
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
for x 0 < 8 end
The port-names are optional. If specified, they must correspond to the names of ForLoop output ports:
for x 8 >= 0 step -1 : ld v c end
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> ...
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.
for row 0 < 8 : c for col 0 < 8 : c v end end
Triangular Nested Iteration
for row 1 < 8 : c for col 0 < row : c v end end
Strategies for Hiding Dead Cycles
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.
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.
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