ALGORITHMIC STATE MACHINE (ASM) in HLS

Design Technology | Algorithmic State Machines (ASMs) in HLS | What is Algorithmic State Machines

What is Algorithmic State Machine?

An Algorithmic state machine is the directed connected graph containing an initial vertex (Begin), a final vertex (End), and a finite set of the operator and conditional vertices (Fig. 1). The final, operator, and conditional vertices have only one input; the initial vertex has no input. The 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

As the first example, let us consider an Escape mode of a mobile robot, constructed in our GUI ASM Creator (Fig. 2).

Figure 2. A mode Escape of a mobile robot

A Boolean expression can be written in the conditional vertex. An operator with one, two, or more microoperations can be written in the operator vertex. Arithmetic, Boolean, and comparison operators are presented in Tables 1 and 2.

Table 1

Table 2

Two kinds of microoperations

HLS and RTL tool Synthagate uses two kinds of microoperations in ASM:

The first kind is a simple microoperation, containing assignment colon-equal ":=". The second kind of microoperation is a component microoperation (we call it subASM or a generalized operator). Such microoperation does not contain an assign operator colon-equal ":=". In this example, they are colored yellow, but the color is not essential. These operators are subASMs and will be included in the mother's ASM to get the whole behavior of the digital system or one of its modes if we would like to present them separately. SubASM can contain subASMs as well, and there are no constraints on the number of subASMs and the number of levels of such inclusions.

ASM vertices are connected in such a way that:

Inputs and outputs of the vertices are connected by arcs directed from output to input; each output is connected to only one input.
Each input is connected at least to 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. We will call such conditional vertices the waiting vertices since they simulate the waiting process in the system behavior description.

Fig. 3 presents subASMs of ASM Escape.

Figure 3. SubASMs of ASM Escape

The result of the inclusion subASMs from Fig. 3 into the Escape mode is shown in Fig. 4. Synthagate automatically includes all ASMs into the mother's ASM.

Figure 4. Synthagate inserted subASMs into mode Escape

Sometimes we use ASM in which logical conditions and microoperations are replaced by x1, x2, … and y1, y2, … and their operators are replaced by operators Y1, Y2,…. Figure 5 shows this kind of ASM from Figure 4.

Figure 5. The same ASM with replaced operators and logical conditions

ASMs in System C and VHDL

In Synthagate, ASM can be presented:

By a graph, drawn in GUI (ASM Creator) – Fig. 2.
By a text in pseudo-code of System C – see Fig.6 left.
By a text in pseudo-code of VHDL – see Fig.6 right.

The designer doesn't present the design in System C or VHDL. The images in Fig. 6 contain ASM presented as a text. They don't have definitions of ports, signals, or variables. We used operators of System C or VHDL to submit our graph by texts. If you compare these texts with the image in Fig.2, you will understand that they deliver the same behavior.

When we are talking about ASMs in System C or VHDL, these ASMs are only graphs, presented with operators of System C or VHDL. We made this option in the case the designer would prefer to write them in the text file, instead of drawing ASMs. Nevertheless, we highly advise you to draw ASMs in ASM Creator.

Fig6_ASM Escape in System C and VHDL.PNG

Figure 6. ASM Escape in System C and VHDL

The internal representation of ASM in Synthagate

When the designer clicks the build button – the special button in ASM Creator (see ASM Creator Short Manual), Synthagate immediately compiles the schematic into two files (Fig. 7) – escape.gsa (ASM as two connected list) and escape.txt (the text file with the contents of vertices in ASM). These files are the internal representation of ASM, and Synthagate works with them, not with pictures.

ASM Creator numbers vertices, operators, microoperations, and logical conditions and constructs two files – name.gsa and name.txt. Here, a name is the name of the ASM. After that, Synthagate works not with pictures, but with these files (.gsa and .txt). These two files for ASM Escape (Fig. 7) are presented in Fig. 8. To explain the files in Fig. 8, we have numbered vertices (red numbers), microinstructions, and logical conditions in Fig. 7.

Fig 7_ASM escape.asd with numbered verti

Figure 7. ASM escape.asd with numbered vertices

File name.gsa is the two-connected list of ASM graph. Each row of this list corresponds to one vertex. Columns in this list:

The number of vertices.
The content of vertices – Y n for the operator and x m for the logical condition.
The numbers of the vertices following the operator vertex, or output 1 of the conditional vertex.
The numbers of the vertices following output 0 of the conditional vertex.

Vertices Begin and End are described as operator vertices.

From the file escape.txt, we see that it contains five operators Y1 – Y5, seven microoperations y1 –y7, and four logical conditions x1 – x4.

Figure 8. Files escape.gsa and escape.txt

Time in ASM

To describe the time in ASM, look at ASM in Fig. 9. Each operator can contain one, two, three, or more microoperations written in the same operator vertex. These microoperations are implemented simultaneously at the same clock.

Two sequential operators, as Y4 and Y3 in Fig. 9 are implemented at two sequential clocks. Two operators with any number of conditional vertices between them, as Y1 and Y4 in this figure, are implemented at two sequential clocks as well.

Figure 9. Example of ASM

ASM, as a Finite State Machine, is a sequential model. To describe parallel processes, we must draw several ASMs. In Fig. 10 we have shown three fragments of parallel working ASMs. The dots present some sequences of vertices.

The interaction between these processes is implemented by signals (microoperation). In this example, three processes begin to work simultaneously, but at some time, the right one stops and waits for signal y1=1 from the left process. Only then it will continue to work. In the same manner, at some stage, the left process stops and waits for signal y2=1 from the center one. The three processes continue to work, but at some time, the left and the right processes are waiting for signal y3=1 from the center process, etc.