On approximation algorithms for microcode bit minimization

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 &Ogr;(logn) in polynomial time.

REFERENCES

• Ag76: Agerwala,T., "Microprogram Optimization: A Survey", IEEE Transactions on Computers, Vol. C-25, No. 10, Ott 1976, pp 962-973.
• An80: Michael Andrews, Principles Firmware Engineering, W. H. Freeman & Co., New York, NY, 1980
• BK79: Baer,J.L. and Koyama,B., "On the Minimization of the Width of the Control Memory of Microprogrammed Processors", IEEE Transactions on Cornput: ers, Vol. C-28, No. 4, Apr 1979, pp 310-316.
• GJ79: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• GM70: Grasselli,A. and Montanari,U., "On the Minimization of Read Only Memory in Microprogrammed Digital Computers", IEEE Transactions on Computers, Vol. C-19, No. 11, Nov 1970, pp 1111-1114.
• RG88: Ravi,S.S. and Gu,D., "On Approximation Algorithms for Microcode Bit Minimization", Tech. Rep. 88-19, Dept. of Computer Science, SUNY at Albany, Aug 1988.
• RGO88: Ravi,S.S., Gu,D. and O'Leary,S.H., "Width Minimization of Microprograms through Simulated Annealing", Tech. Rep. 8820, Dept. of Computer Science, SUNY at Albany, Aug 1988.
• Ro79: Robertson,E.I., "Microcode Bit Optimization Problem is HP-Complete", IEEE Transactions on Computers, Vol. C-28, No. 4, Apr 1979, pp 316-319.
• Sc68: Schwartz,S.J., "An Algorithm for Minimizing Read Only Memories for Machine Control", Conference Record of the Ninth Annual Symposium on Switching and Automata Theory, Ott 1968, pp 28-33.
• vA87: P. J. M. Laarhoven , E. H. L. Aarts, Simulated annealing: theory and applications, Kluwer Academic Publishers, Norwell, MA, 1987
• Wi83: Avi Wigderson, Improving the performance guarantee for approximate graph coloring, Journal of the ACM (JACM), v.30 n.4, p.729-735, Oct. 1983 [doi>10.1145/2157.2158]
• WLL88: D. F. Wong , H. W. Leong , C. L. Liu, Simulated annealing for VLSI design, Kluwer Academic Publishers, Norwell, MA, 1988

INDEX TERMS

Primary Classification:
  B. Hardware
  B.1 CONTROL STRUCTURES AND MICROPROGRAMMING
      B.1.4 Microprogram Design Aids
          Subjects: Optimization

General Terms:
Algorithms, Design, Performance