Microword length minimization in microprogrammed controller synthesis

摘要

The problem of microword length minimization is crucial to the synthesis of microprogrammed controllers in digital systems. Unfortunately, this problem is NP-hard. Although various enumerative and heuristic methods have been developed, usually they cannot provide fast and efficient solutions to a large size problem. Here, the problem is formulated into a graph partitioning problem. An efficient graph partitioning algorithm was developed that works by recursively extracting large size cliques from the graph. Furthermore, a local search approach is used to reduce the microword length. This yields an efficient algorithm that outperforms any technique to solve the problem. The algorithm has been tested with practical microcodes. Experimental results are compared with other methods.