This paper presents another heuristic for local microcode compaction (see [1] for background). The authors’ heuristic is a slight modification of Wood’s weighting heuristic [2], which attempts to compact microoperations with more descendants in the data dependency graph first. Rao and Majumdar add the number of microoperations that conflict with this microoperation to the weight.
This heuristic is another example of a list scheduling algorithm. No data, except for a simple example, is given to show that this approach is worth the added computation time required. An appeal to researchers in compaction: a large number of list scheduling variations can be tried, but please don’t report them until you have run them on some sample microcode.