All example of using pseudofields to eliminate version shuffling in horizontal code compaction

ABSTRACT

This paper first reviews the version shuffling problem for microcode compaction. Next, a somewhat representative compaction problem involving asymmetric ALUs and a port-limited register file is presented. Finally, the paper shows how to model the architecture in a microcode compiler using the concept of pseudofields. While the modeling process is nontrivial, it is seen that this approach solves the version shuffling problem without introducing early-binding inefficiencies in the compiled code.

REFERENCES

• Horowitz and Sahni, 1978: Ellis Horowitz , Sartaj Sahni, Fundamentals of Computer Alori, W. H. Freeman & Co., New York, NY, 1978
• Linn, 1988: Linn, J.L. "Horizontal Microcode Compaction", in Microprogramming and Firmware Engineering Methods, Stanley Habib: editor, Van Nostrand Reinhold, New York, 1988.
• Mueller, Allan, and Varghese, 1984: Mueller, R.A., V.H. Allan, and 3. Varghese "The Complexity of Horizontal Word Encoding in Microprogrammed Machines", IEEE Transactions on Computers 33:10, October, 1984, pp. 938-939.
• Mueller and Varghese, 1988: Mueller, R.A. and J. Varghese "Fundamentals Concepts of Microprogramming", in Microprogramming and Firmware Engineering Methods, Stanley Habib: editor, Van Nostrand Reinhold, New York, 1988.
• Rimey and Hilfinger, 1988: K. Rimey , P. N. Hilfinger, Lazy data routing and greedy scheduling for application-specific signal processors, Proceedings of the 21st annual workshop on Microprogramming and microarchitecture, p.111-115, November 28-December 02, 1988, San Diego, California, United States
• Vegdahl, 1982: Steven Roger Vegdahl, Local code generation and compaction in optimizing microcode compilers, 1982

INDEX TERMS

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

Additional Classification:
  B. Hardware
  B.1 CONTROL STRUCTURES AND MICROPROGRAMMING
      B.1.4 Microprogram Design Aids
          Subjects: Optimization
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION

  E. Data
  E.4 CODING AND INFORMATION THEORY
      Subjects: Data compaction and compression

General Terms:
Algorithms, Design, Performance