A Fast State Assignment Procedure for Large FSMs

This paper addresses the problem of state assignment for large FSM (Finite State Machines). This is an important problem in high performance digital system design where added functionality often comes at the expense of a larger (and slower) FSM to control the system. We present a new scheme to solve the graph embedding problem which is the main step in state assignment process. This new approach places the graph in a two-dimensional array (grid) while minimizing the total edge length, and then maps this two-dimensional array into an n-dimensional hypercube with dilation at most 2. Experimental results are presented and compared against those of NOVA. These results show the effectiveness of our proposed approach.