Author Topic: State machine design choice  (Read 3309 times)

0 Members and 1 Guest are viewing this topic.

Offline ddr_controllerTopic starter

  • Contributor
  • Posts: 15
  • Country: es
State machine design choice
« on: April 16, 2024, 10:58:21 pm »
I want to design a state machine for one module that have to communicate with another module via a protocol.

Multiple states need might endup needing to communicate, State A, State B, State C. they build the package and the go to the send state. The thing is that once the communication ends they need to return to different states, as they need to process the replied data differently. One possibility is to replicate the communications state Fig 2 or to have a register save the return state, Fig 1 where the communication state will go to the return state depending on what state arrive to it.

I am wondering which is a better design choice, and if they are both awful, then what have people been using? I feel like this is something that is found a lot in design.

Thanks
 

Offline abeyer

  • Frequent Contributor
  • **
  • Posts: 318
  • Country: us
Re: State machine design choice
« Reply #1 on: April 17, 2024, 02:51:09 am »
I'm not sure one is clearly better than the other.

I would argue that A is straying from the strictest definition of a state machine by keeping some parallel state "outside" the machine. This type of ad-hoc management of state is exactly what you'd hope state machines would help to prevent. However, as you see, the way you would deal with this within the formalism can quickly cause an explosion of possible states. Either one can be a valid solution, but there are tradeoffs.

If you're not happy with either, you might consider taking a look at statecharts, which are an extension of the state machine model with features such as hierarchical and composite states which can help formally encode these types of things without breaking out of the system, while keeping the number of states more constrained
 

Offline BrianHG

  • Super Contributor
  • ***
  • Posts: 7835
  • Country: ca
Re: State machine design choice
« Reply #2 on: April 17, 2024, 03:57:21 am »
In verilog, or system verilog, I would construct both of you state diagrams using the 'CASE' command and the choice of state would be the 'case (my_state_location_register)'.

If you so like, making the 'state_location_register' a few extra bits wide allows you to implement an auto program counter allowing for a sequence of events to take place 1 clock cycle after the next if you so like.  You will be making a kind of a hybrid MCU program counter and state-machine, both at the same time.  I used this technique all of the time with code that looks like a complete program running library 'task' calls with goto, gosub & return functions.
 

Offline tggzzz

  • Super Contributor
  • ***
  • Posts: 19843
  • Country: gb
  • Numbers, not adjectives
    • Having fun doing more, with less
Re: State machine design choice
« Reply #3 on: April 17, 2024, 08:47:35 am »
Do not confuse "actions" with "states"; keep the concepts separate and match the implementation to the concept.

Think in terms of what is easiest to debug and modify/extend.

Debugging is easier if you can keep a log of events and/or states. That "trajectory" can be really valuable during integration and while systems are being commissioned; it enables you to point the finger at other parties :) (Or to quickly realise how you can improve things)

Modification is easier if you can determine that changing one line/function will cause the desired change and (equally importantly) won't cause any other changes.

Both of those push towards having having CommunicationStateA plus CommunicationStateB plus CommunicationStateC.

However, nothing is absolute and there is no substitute for good taste.
There are lies, damned lies, statistics - and ADC/DAC specs.
Glider pilot's aphorism: "there is no substitute for span". Retort: "There is a substitute: skill+imagination. But you can buy span".
Having fun doing more, with less
 

Offline dietert1

  • Super Contributor
  • ***
  • Posts: 2187
  • Country: br
    • CADT Homepage
Re: State machine design choice
« Reply #4 on: April 17, 2024, 10:55:49 am »
The pattern i see is three threads/tasks/processes sharing communication resources (another thread/task/process plus certain hardware). The diagrams doesn't show other interaction between threads A, B and C.
The allocation and management of resources is a common problem and other people would probably not use the term state machine for this. A state machine would normally be used to describe and control the progress of work within a thread. States could be "sending, waiting for response, response evaluation, error halt" or so. In your case threads A, B and C have a state "Return".
The management of threads and resources can be implemented using an operating system and its constructs like semaphors. From the system point of view the active thread is state and thread execution is subject to rules. Those rules need to be very flexible and i wouldn't call it a state machine. In a machine with multiple cores there can be concurrent threads, while states of a state machine are meant to be mutually exclusive.

Regards, Dieter
 

Offline tggzzz

  • Super Contributor
  • ***
  • Posts: 19843
  • Country: gb
  • Numbers, not adjectives
    • Having fun doing more, with less
Re: State machine design choice
« Reply #5 on: April 17, 2024, 12:21:20 pm »
It isn't clear whether this FSM is to be implemented in hardware or software or both.

If in software, an RTOS is not necessary for FSMs, and can unnecessarily complicate implementations.

With or without an RTOS, anybody using software FSMs should be aware of the half-sync half-async design pattern. It is finally becoming well known and appreciated, so there are many descriptions available, e.g.https://www.dre.vanderbilt.edu/~schmidt/cs282/PDFs/6-Concurrency-and-Synchronization-part10.pdf
« Last Edit: April 17, 2024, 03:40:44 pm by tggzzz »
There are lies, damned lies, statistics - and ADC/DAC specs.
Glider pilot's aphorism: "there is no substitute for span". Retort: "There is a substitute: skill+imagination. But you can buy span".
Having fun doing more, with less
 

Offline dietert1

  • Super Contributor
  • ***
  • Posts: 2187
  • Country: br
    • CADT Homepage
Re: State machine design choice
« Reply #6 on: April 18, 2024, 07:56:58 am »
The operation system construct to mention here is "queue". Queue entries get tagged with the requesting thread so the system can run the proper thread after a queue entry has been finished.
 

Offline nctnico

  • Super Contributor
  • ***
  • Posts: 27243
  • Country: nl
    • NCT Developments
Re: State machine design choice
« Reply #7 on: April 18, 2024, 11:34:22 am »
When dealing with complex sequential logic in an FPGA, it can help to use a programmable state machine. This can even be in the form of a small processor like Picoblaze / Pacoblaze. The latter can be programmed using a simple assembler. The program for a programmable state machine can be generated using a program or script (Python).

Looking at the problem at hand, using a shared sub-statemachine which does the transmission seems to be the easiest way to go. It looks like there are 3 parallel processes (A, B and C) and 1 send/receive process. So each process creates a packet, waits for the transmission statemachine to become available (make sure this works in a round-robin fashion so in case one of the processes gets stuck, the others still can send/receive), hands over the data to the transmission state machine once it becomes available, waits (or timeout) for the answer to arrive and continue with the rest of the processing.
« Last Edit: April 18, 2024, 11:38:56 am by nctnico »
There are small lies, big lies and then there is what is on the screen of your oscilloscope.
 


Share me

Digg  Facebook  SlashDot  Delicious  Technorati  Twitter  Google  Yahoo
Smf