Design Technology | Algorithmic State Machines in HLS (ASMs) | ASM Transformations | ASM Minimization

ASM Minimization

In this section, we will discuss minimization of conditional vertices in ASMs used in Synthagate. Fig. 1 presents nonminimal ASM Gnonmin.

Figure 1. Non-minimal ASM Gnonmin

The minimization algorithm consists of three steps. In the first step, the initial ASM is divided into such subgraphs G1, …, GQ, that for obtaining the minimal ASM it is sufficient to minimize the number of conditional vertices in each subgraph independently of one another. In the second step, for each subgraph Gq (q=1, …, Q) we must find a set of equivalent ones that contains the minimized subgraph Gq_min. At the third step, the subgraph Gq_min can be obtained by solving of the covering problem on the set of subgraphs found at the second step.

The minimized ASM Gmin constructed automatically by HLS tool Synthagate is shown in Fig. 2.

Figure 2. Minimized ASM Gmin