We would like to have a program as fast as that of approach 6, as good as in 4 and as useful in VLSI design as approach 7. However, this is impossible. The user then has to implement a method selected among the above for his class of machines and systems's speed and performance requirements, or implement many algorithms and select among them interactively for any particular problem [143].
Let us consider in more detail what are the advantages and disadvantages of the above methods.
The method of De Micheli fails when there are few or no groups of internal states that transit to the same state under some input state. Unfortunately, such type of machines often occur in industrial applications [36]. The new program, developed by De Micheli at IBM gives results about 20constraint assignment problems [61].
The idea of applying Boolean minimization to the non-assigned machine is not new. It was used in the systems of Story, Harrison and Reinhard [170] and of Perkowski and Zasowska at Warsaw Technical University [187, 138], but because of the lack of fast Boolean minimizers, like Espresso-mv, this approach was applicable only to machines smaller than 9 internal states. However, the also method also a secondary assignment, minimizes numbers of gates and can be used for multi-level logic realization. The enumerative approach of the method allows finding an absolutely minimum solution to the problem for various technologies, since the cost function for realization is user-defined. Approximate variant for larger machines was also created. Availability of fast minimizers permits for improvement of methodologies from [121, 122]. The new methods and algorithms will be also presented in the forthcoming papers. The methods give better results than Kiss, but still cannot be applied to machines of more than 20 states.
The disadvantages of the original approach of De Micheli et al [55], are the following:
Attempts to improve Kiss were successful [36, 61]. However, program still cannot be applied for machines with more than 100 states [60]. Also, it does not take into account output states for assignment.
The disadvantages of the approach of Armstrong are the following:
The disadvantages of Moroz approach are the following:
Different papers applying the embedding methods use different approaches to create the assignment graph.
Saucier [157] creates a nonoriented weighted graph, whose edges correspond to transitions between states of FSM.
Moroz [128] creates an oriented graph, whose edges correspond to oriented transitions between states. He writes about embedding, but his work can be treated as approximate solution to quadratic assignment of a particular type, where the graph is oriented, costs the of edges are equal, and the cost function is defined as in the quadratic assignment.
Armstrong [6, 7] formulates a nonoriented graph, whose edges are created according to several principles of adjacency.
The above authors use different constructive algorithms for embedding those graphs on hypercubes. They do not give any, other than heuristic, explanations of adequacy of the proposed assignment (embedding) techniques. Also, program of Saucier is designed for asynchronous machines.
Perkowski uses a combination of factors that take into account adjacency of states, inputs, and outputs, both from the view of primary adjacency (like De Micheli), and also secondary adjacency with use of methods similiar to partition theory and tabular methods.
Although many interesting approaches to state assignment have been recently proposed, the careful comparison of algorithms is necessary on large benchmarks of industrial machines. Many new interesting algorithmic concepts arise from the papers and evaluation results recently available. Large sets of industrial FSMs compiled by us anda other authors allows comparisons of methods. Perhaps in future systems, various algorithms will be used for small (less than 8 states), medium (9-40), and large (40-120) and very large (more than 120) machines to obtain good speed/performance ratios. Detailed analysis of reduction methods is necessary, as well as evaluation of the complexity of optimal and approximate algorithms for related mathematical problems, like hypercube embedding, embedding to faces and quadratic assignment [36, 144]. The possible use of general purpose parallel computers as well as research on special hardware accelerators seem to be also very promising.