Microprogram Optimization: A Survey

The application of microprogramming in present day computers is rapidly increasing and microprogramming will undoubtedly play a major role in the next generation of computer systems. Microprogram optimization is one way to increase efficiency and can be crucial in some applications. Optimization, in this context refers to a reduction/minimization of control store and/or execution time of microprograms. The numerous strategies are classified under four broad categories: word dimension reduction, bit dimension reduction, state reduction, and heuristic reduction. The various techniques are presented, analyzed, and compared. Unfortunately, the results of the survey are not too positive. The reason is that much of the work on optimization has been devoted to obtaining the absolute minimum solutions rather than "good engineering reductions." Whether the reduction is being performed with respect to the word dimension, the bit dimension or the number of states existing techniques to obtain the optimum solution use exhaustive enumeration. Thus, the effort involved is prohibitive and there are no guarantees that significant reductions can be obtained. It is thus doubtful that an optimum solution can be justified even when the microcode produced is frequently executed. Heuristic reduction techniques do not guarantee an optimum solution but can provide some reduction with little effort. For the majority of the techniques studied, much further work remains to be done before any practical applications can be foreseen. Some methods however constitute steps in the right directions. Directions for future research are briefly outlined in the conclusions.