On Approximation Algorithms For Microcode Bit Minimizationt

S. S. Ravi, Dechang Gu

Abstract

The bit (or width) minimization problem for microprograms is known to be NP-complete. Motivated by its practical importance, we address the question of obtaining near-optimal solutions. Two main results are presented. First, we establish a tight bound on the quality of solutions produced by algorithms which minimize the number of compatibility classes. Second, we show that the bit minimization problem has a polynomial time relative approximation algorithm only if the vertex coloring problem for graphs with n nodes can be approximated to within a factor of O(logn) in polynomial time.
BibTeX
@inproceedings{ravi1988approximation,
  author = {S. S. Ravi and Dechang Gu},
  title = {{On Approximation Algorithms For Microcode Bit Minimizationt}},
  booktitle = {International Symposium on Microarchitecture},
  year = {1988},
  doi = {10.5555/62504.62538},
}

Loading related content...

Figure