On Approximation Algorithms For Microcode Bit Minimizationt
Lists
Only you see this
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...