Design Technology | Algorithmic State Machines (ASMs) in HLS | What is Algorithmic State Machines
What is Algorithmic State Machine
An Algorithmic state machine (ASM) is a directed connected graph containing an initial vertex (Begin), a final vertex (End) and a finite set of operator and conditional vertices (Fig. 1). The final, operator and conditional vertices have only one input, the initial vertex has no input. Initial and operator vertices have only one output, a conditional vertex has two outputs marked by "1" and "0". A final vertex has no outputs.
Figure 1. Vertices of Algorithmic state machine
Inputs and outputs of the vertices are connected by arcs directed from an output to an input, each output is connected to only one input;
Each input is connected to at least one output;
Each vertex is located on at least one of the paths from vertex “Begin” to vertex “End”.
One of the outputs of a conditional vertex can be connected to its input. I will call such conditional vertices the “waiting vertices”, since they simulate the waiting process in the system behavior description.
As the first example, let us consider a rather smart Traffic Light Controller (TLC) presented in the flowchart in Fig. 2. First of all, we want to warn you. This ACM is quite complex, but after considering the ACM transformation you will see that it is very easy to build it. Moreover, at this stage it is not important to understand how does it works.
Nevertheless, we will shortly describe its behavior. This controller is at the intersection of a main road and a secondary road. TLC have different day (Bit0=0) and night programs (Bit0=1). Day program has two modes. when prog=1, cars can move along the main road during t_main time. In the second mode (prog=1) car move via the main road until the sensor sec_ full tells to TLS that second road is full.
On the night, the traffic on the main road doesn't stop until a pedestrian appears on the main road (pd_main=1) or the number of cars on the second road reach the number written in the register rg_sec_car.
The traffic on the second road is the same for the day and the night programs. Cars move on the second road during time written in rg_t_sec. The switching between traffic on the main and the second roads takes time written in the register rg_t_int.
Our smart controller can recognize an ambulance on the road. When an ambulance is on the road the signal amb is equal to one (amb = 1), when there is no ambulance on the road this signal is equal to zero (amb = 0). When there is the ambulance on the road, outputs of conditional vertices with logical condition amb marked by ΄1΄, bring us to the intermediate state to let cars to finish their driving: main_yel:=1; sec_yel := 1; t := 0. One more logical condition dmain tells us where the ambulance is – whether it is on the main road or on the second one. If it is on the main road (dmain=0), after time written in intermediate register reg_t_int, the traffic light will be green on the main road, otherwise (dmain=1) the traffic light will be green on the second road.
Figure 2. A traffic light controller
In the flowchart, a logical condition is written in each conditional vertex. It is possible to write the same logical condition in different conditional vertices. A microinstruction (an operator), containing one, two, three or more microoperations, is written in each operator vertex of the flowchart. It is possible to write the same operator in different operator vertices.
If we replace logical conditions by x1, x2, … , xL, microoperations by y1, y2, … , yN and operators by Y1, Y2, … , YT, we will get Algorithmic State Machine (ASM). ASM for the flowchart in Fig. 2 is shown in Fig. 3.
Figure 3. A simple traffic light controller
ASM vertices are connected in such a way that: