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. In this paper, we first formulate the problem into a graph partitioning problem. An efficient graph partitioning algorithm was developed that works by recursively extracting large size cliques from the graph. Furthermore, we employ a local search approach to reduce the microword length. This has resulted in an efficient algorithm that outperforms any existing technique available to solve the problem. We have tested our algorithm with practical microcodes. We compare our experimental results with other existing methods