A parallel algorithm for state assignment of finite state machines

Author

Hasteer, Gagan ; Banerjee, Prithviraj

Author_Institution

Ambit Design Syst., Santa Clara, CA, USA

Volume

47

Issue

2

fYear

1998

fDate

2/1/1998 12:00:00 AM

Firstpage

242

Lastpage

246

Abstract

Optimization of large sequential circuits has become unmanageable in CAD of VLSI due to time and memory requirements. We report a parallel algorithm for the state assignment problem for finite state machines. Our algorithm has three significant contributions: it is an asynchronous parallel algorithm portable across different MIMD machines; time and memory requirements reduce linearly with the number of processors, enabling the parallel implementation to handle large problem sizes; and the quality of the results for multiprocessor runs remains comparable to the serial algorithm on which it is based due to an implicit backtrack correction mechanism built into the parallel implementation

Keywords

circuit optimisation; finite state machines; logic CAD; parallel algorithms; sequential circuits; state assignment; MIMD machines; VLSI; asynchronous parallel algorithm; finite state machines; implicit backtrack correction mechanism; large problem sizes; large sequential circuit optimization; memory requirements; multiprocessor runs; state assignment problem; Automata; Design automation; Encoding; Libraries; Microprocessors; Parallel algorithms; Runtime environment; Sequential circuits; Very large scale integration; Workstations;

fLanguage

English

Journal_Title

Computers, IEEE Transactions on

Publisher

ieee

ISSN

0018-9340

Type

jour

DOI

10.1109/12.663772

Filename

663772