Wave steered FSMs

TitleWave steered FSMs
Publication TypeConference Paper
Year of Publication2000
AuthorsMacchiarulo, L, Shu, S-M, Marek-Sadowska, M
Conference NameDesign, Automation and Test in Europe Conference and Exhibition 2000. Proceedings
Keywordscellular arrays, finite state machines, FSM decomposition theory, latency penalties, logic CAD, MCNC benchmarks, pipeline processing, pipelining techniques, sequential circuits, sequential machines, standard cell implementation, state variable dependencies, throughput, wave steered FSMs
AbstractIn this paper we address the problem of designing very high throughput finite state machines (FSMs). The presence of loops in sequential circuits prevents a straightforward and generalized application of pipelining techniques, which work so well for combinational circuits, to increase FSM performance. We observe that appropriate extensions of the ldquo;wave steering rdquo; technique are possible to partially overcome the problem. Additionally we use FSM decomposition theory to decouple state variable dependencies. Application of these two techniques to MCNC benchmarks resulted in a factor of 3 average throughput increase as compared to a standard cell implementation, at the expense of factor 3.7 area and less than factor 2 latency penalties