Back to Tools

KBS flowHDL®

Background of the Algorithmic State Machine (ASM) Notation

The flowdiagram notation and symbol set is based on several fundamental ideas associated with digital systems architecture: (1) expression of state machine behavior as a set of concurrent Algorithmic State Machines (ASM) charts, (2) representation of specific data path operations through the appending of explicit assignment expressions written in a generic Register Transfer Level (RTL) notation, and (3) the inclusion of a core set of macro-function units that can be used in the description of specific data path operations, in expression form, associating these with specific states in the state machine for purposes of sequencing, scheduling and resource allocation.  For more information on the theory of flow diagrams, refer to the flowHDL® Reference Manual links below.  Some of the better texts that use ASM charts to teach digital design are (1) Lewin & Protheroe, 1992, (2) Fletcher, 1980, (3) Hayes, 1993, (4) Arnold, 1999 and (5) Lee, 2000, among others.

History of the ASM Method

The Algorithmic State Machine (ASM) method for specifying digital designs in an abstract behavioral form was originally documented by Claire in the early 1970’s, based on work done at Hewlett Packard.  Since then, it has become a staple of almost every text on the subject of Digital Logic Design, being covered in some fashion in most texts.  Whereas most books simply give it treatment as a means to specify the control of digital systems using complex finite state machine (FSM) models, some texts actually use it as a primary means for presenting the abstract design methods for digital systems design.

Early texts by Fletcher and Wakerley in the 1980s codified the ASM method into the pedagogy of digital systems analysis and design techniques.  These texts demonstrated how an algorithmic approach to controller design could be used to manage complexity of digital control specifications involving large numbers of state variables or inputs.  These texts were preceded by Hayes’ late 1970s treatment of standardized register-transfer notation (RTN) in computer architecture design, later incorporated into Hayes’ text on digital logic design and into Wakerley’s later text editions in the 1990s.  This incorporation of RTN into ASM notation allowed datapath operations to be specified along with control signals as the result of finite state machine (FSM) execution.

Many of the texts on Digital Logic cover the ASM method in conjunction with other methods for specifying FSMs, namely state tables and state diagrams.  Several authors of newer texts on the subject, such as Lee and Arnold, recognize the value of presenting the design of digital systems solely in terms of the ASM method, incorporating both the FSM and the register transfer notation (RTN) models in a single representation corresponding to the control and datapath structures of a digital system.

Armstrong et al. and Arnold have written texts that recognize the importance of using the ASM method to model algorithms, and present the method as a manual analysis technique to devise digital systems for algorithm implementation.  In particular, Arnold appears to have written to an audience consisting primarily of high-level software language developers, such as C programmers, as he uses the ASM as a means to introduce digital systems development using the Verilog HDL language.  Armstrong et al., on the other hand, are writing to an audience that will engage in digital systems design using the VHDL language.

The Executable ASM Method

In the early 1990s, Kobayashi et al. demonstrated the use of the ASM notation as a means to capture digital systems designs in the automated synthesis of digital circuit descriptions and, working with Ricoh Co., Ltd. Of Japan, developed a set of methods and tools that were subsequently patented.  Several years later, Davis and Kobayashi presented the utility of Executable ASM models in the behavioral design capture that could be used in conjunction with automated logic synthesis of VLSI circuits.  This work involved creating a set of EDA tools that supported the automated capture, compilation and simulation verification of ASM models of digital systems using the Executable ASM method.  The flowHDL® tool set, developed by Knowledge Based Silicon Corp., has been used extensively over the past decade in VLSI Design instruction, first in USC’s Department of Electrical and Computer Engineering and, later, in the Department of Computer Science and Engineering.

Regarding the productivity advantages of using Executable ASM modeling over language-based design methods, Joshi and Kobayashi conducted a set of experiments comparing graphical design methods such as the ASM against language-based design methods (using the Verilog programming language).