Subject: Re: FSM Enhancement Goals and Thoughts
From: Clifford E. Cummings (cliffc@sunburst-design.com)
Date: Thu Dec 13 2001 - 12:25:54 PST
I must admit, this type of state machine does not do much for me.
This is a highly contrived FSM design with no residual value that I could
use in a later presentations or professional training. Exerting effort on
this design will be wasted effort since I don't think we should even
include this in the SystemVerilog LRM. It screams "academic example follows!"
This is similar to the Black-Jack FSM, Traffic Light Controller FSM, Soda
Pop Change Machine FSM and Elevator Control FSM designs that are found in
too many "professional" books. It also reminds me of the VIUF Denver
Airport Luggage Sorter contest that was held a few years ago. When I heard
there was going to be a design contest for VIUF, I was excited to
participate. When heard what the contest was, I decided to pass.
I would prefer something like a pair of PCI bus FSMs that have actual
value. If anyone can come up with a real design issue related to FSM
design, please volunteer the concept. It will give you a chance to have
some industry experts attack a real design problem that you could probably
use on your project. If nothing else comes up, we will have to do with this
example.
Hoping someone has a more interesting, real-hardware design problem - Cliff
At 10:54 AM 12/13/01 -0800, Alec Stanculescu wrote:
>Cliff,
>
>I came up with the following example of state machines, which we can
>use, to bounce ideas around:
>
>In FutureTown driver-less taxis are dispatched by a robot when
>customers place orders by phone, describing in ascii (computer
>processable) the origin and destination addresses.
>
>The dispatcher must:
>===================
>- accept orders
>- ask for the list of free taxis, upon receipt of an order, and
> wait for list_timeout or for the list to arrive.
>- send and emergency signal to system_maintenance and stay
> out_of_order, if list_timeout arrives.
>- select the best taxi for the job and send the job description to the
> selected taxi, and wait for acknowledgement or for taxi_timeout,
> when the list of free taxis arrives.
>- send a taxi_maintenance signal, upon receipt of
> taxi_timeout, and ask again for the list of free taxis.
>- upon receipt of the acknowledgement the order is considered under
> processing until a signal is sent by the taxi that it is free again
> or until a cancel_ack signal is received. In case cancel_ack is
> received the dispatcher must ask for the list of free taxis again in
> order to select the best one for the job.
>
>We shall not worry about how to select the best taxi, nor with how the
>taxi manages to follow directions. Let us focus on the state machine.
>
>Hints
>-----
>Inputs: Order, Free_taxi_list_available, list_timeout, taxi_timeout,
> ack, cancel_ack
>Outputs: system_maintenance, taxi_maintenance, job_description,
>States: wait_for_order, wait_for_list, send_job, out_of_order...
>
>To consider: the dispatcher must accept multiple overlapping orders.
>
>Therefore, it must be capable of spawning of a new fsm for each order
>received, to be able to monitor its completion (and in case of
>cancel_ack to start again to select the best taxi), while accepting
>new orders.
>
>Or, alternatively, the dispatcher must keep info about the status of
>each taxi and in each state check if a cancel_ack has been received
>from taxis that accepted jobs.
>
>The two alternatives allow us to understand the advantages of the
>hierarchical state machine over the flat state machine.
>
>The robot of the taxi must:
>==========================
>- wait for job_description from dispatcher, while sending a taxi_free
> signal to dispatcher.
>- respond to a job_description with an acknowledgement and proceed to
> process the job.
>- send a cancel_ack upon receipt of accident
>- consider that the order was processed, upon receipt of customer_done
> and wait for a new job_description.
>
>Inputs: job_description, accident, customer_done
>Outputs: taxi_free, ack, cancel_ack.
>States: Wait_for_job, Processing, Out_of_Order
>
>Describe the Dispatcher/Taxis system as a "Dispatcher state machine"
>that communicates with multiple instances of the "Taxi state machine".
>
>Note: Assume different clocks for each taxi and the dispatcher.
>
>Suppose now that we want to improve
>the dispatcher so that when it receives a taxi_free and it determines
>that the newly available taxi may satisfy better an order in progress,
>it may give the job description to the newly available taxi and
>interrupt the job previously given to the other taxi.
>
>To achieve the improvement we will split the "processing" state of taxi
>into two states: going_to_customer, and going_to_destination and we
>will add a new signal from dispatcher to each taxi (cancel_job) as
>well as one signal from each taxi to dispatcher (cancel_job_ack).
>
>This will show the need for transferring a FSM into another state from
>another FSM (i.e. the dispatcher will transfer the taxi from the state
>going_to_customer to the state wait_for_job. This may imply a protocol
>which may be hidden at a higher level of abstraction.
>
>We can also extend this example if necessary. The problem will become
>more complicated when FutureTown decides to share its taxi pool with
>NextTown... Issues of fairness, etc.
>
>Alec Stanculescu
//*****************************************************************//
// Cliff Cummings Phone: 503-641-8446 //
// Sunburst Design, Inc. FAX: 503-641-8486 //
// 14314 SW Allen Blvd. E-mail: cliffc@sunburst-design.com //
// PMB 501 Web: www.sunburst-design.com //
// Beaverton, OR 97005 //
// //
// Expert Verilog, Synthesis and Verification Training //
//*****************************************************************//
This archive was generated by hypermail 2b28 : Thu Dec 13 2001 - 12:26:00 PST