CLASSIC: An O(n(2))-heuristic algorithm for microcode bit optimization based on incompleteness relations

This paper presents a heuristic algorithm called CLASSIC for the minimizati on of the control memory width in microprogrammed processors or the instruc tion memory width of application-specific VLIW (Very Long Instruction Word) processors. CLASSIC results in nearly optimal solutions with the time comp lexity of O(n(2)), where n denotes the number of microoperations. In this p aper, we also propose the so-called incompleteness relations which are expl oited for the minimization of the control memory width. Experiments using v arious examples have shown that CLASSIC always achieves smaller microprogra m widths compared to the earlier techniques based on the maximal compatibil ity class or the minimal AND/OR set. The results show that CLASSIC can redu ce the control memory width by 34.2% on average compared with a heuristic c ompatibility class algorithm.