Minimization and Encoding of High Performance Asynchronous State Machines Based on Genetic Algorithm
Tiago S. Curtinhas, Tássio Côrtes Cavalcante, Duarte L. Oliveira, Lester A. Faria, Osamu Saotome · 2015
Today, the design of complex synchronous digital systems shows serious difficulties relating to the global clock and to Deep-Sub-Micron MOS technology. The asynchronous design is an interesting alternative to solve these difficulties, once they do not present clock skew or distribution problems. However, the lack of tools for automatic synthesis is still a major drawback. Asynchronous Finite State Machines (AFSM) are widely used in the control of asynchronous digital systems. A very popular machine is the burst-mode Huffman machine (BM_HM), which accepts burst-mode specification is implemented as Huffman machines (HM). HM architecture, when compared to HM architecture with fed-back output, has advantages such as a better interaction with fast environments, reducing the cost of timing analysis, and a lower latency time. As disadvantage, the area tends to be bigger. This paper proposes two novel algorithms based on genetic algorithms for the minimization and assignment of states, which are important steps in the synthesis of BM_HMs. These two algorithms were implemented in SAGAAs tool, which was tested in an extensive set of benchmarks, showing a high efficiency when compared to Minimalist tool that is state-of-the-art. It achieved an average reduction of 5.91% in the number of products, 15.50% in the number of literals and 32.61% in the total processing time. Our approach presents a low penalty of 1.56% and 4.41% in the number of states and in number of inserted state variables.