HARD: A hypercube embedding algorithm for state assignment of finite state machines

To minimize the area of the combinational circuit, required to realize a finite state machine (FSM), an efficient assignment of states of the FSM to a set of binary codes is required. As to find an optimal state assignment is NP-hard, therefore heuristic approaches have been taken. One approach generates an adjacency graph from the FSM model and then tries to embed the adjacency graph onto a hypercube with an objective to minimize the cost of mapping. However, hypercube embedding itself is an NP-complete problem. In this paper we present a solution to the hypercube embedding problem by designing a new technique, designated as HARD, that is a hybrid combination of non-linear programming method and a local search. We have transformed our problem from discrete space to continuous space and have applied logarithmic barrier function method, that in turn uses gradient projection approach to minimize the objective function. Each iteration of the gradient projection method produces a valid solution. Local search is performed around solution to improve its quality by using a Kernighan-Lin style algorithm. Two distributed algorithms for the HARD, have also been designed and implemented on network of workstations under message passing interface, to speed up the search. We have carried out a large number of experiments to determine the efficiency of the HARD in terms of solution quality over many other techniques, and have obtained very promising results.