David A. Bader
IEEE Fellow
AAAS Fellow
College of Computing
Georgia Tech
Atlanta, GA 30332



A Parallel State Assignment Algorithm for Finite State Machines

This paper summarizes the design and implementation of a parallel algorithm for state assignment of large Finite State Machines (FSMs). High performance CAD tools are necessary to overcome the computational complexity involved in the optimization of large sequential circuits. FSMs constitute an important class of logic circuits, and state assignment is one of the key steps in combinational logic optimization. The SMP-based parallel algorithm --- based on the sequential program JEDI targeting multilevel logic implementation --- scales nearly linearly with the number of processors for FSMs of varying problem sizes chosen from standard benchmark suites while attaining quality of results comparable to the best sequential algorithms.

Publication History

Versions of this paper appeared as:
  1. D.A. Bader and K. Madduri, ``A Parallel State Assignment Algorithm for Finite State Machines,'' The 11th International Conference on High Performance Computing (HiPC 2004), L. Bougé and V.K. Prasanna, (eds.), Springer-Verlag LNCS 3296, 297-308, Bangalore, India, December 2004.

Download this report in Adobe PDF


Last updated: November 5, 2004


Computational Biology

Parallel Computing