Automated synthesis of efficient binary decoders for retargetable software toolkits

ABSTRACT

A binary decoder is a common component of software development tools such as instruction set simulators, disassemblers and debuggers. The efficiency of the decoder can have a significant impact on the efficiency of these software tools. Automated synthesis of efficient binary decoders is therefore necessary for retargetable software tool development frameworks targeting the rapidly growing field of application-specific processor design. This paper describes a decoder synthesis algorithm that translates a simple instruction pattern specification into efficient binary decoders in C under given memory constraints. The algorithm constructs a decision tree with carefully chosen decoding primitives and cost models. As demonstrated through two case studies, the synthesized decoders achieve efficiency comparable to hand-coded decoders with ensured correctness. The algorithm has no limitation on the input instruction patterns and it requires only the least amount of knowledge about the instruction encoding. Therefore it can be used with any machine description scheme containing instruction encoding information.

REFERENCES

• 1: Advanced RISC Machines Ltd. Arm Architecture Reference Manual, 1996.
• 2: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 3: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 4: A. Fauth , J. Van Praet , M. Freericks, Describing instruction set processors using nML, Proceedings of the 1995 European conference on Design and Test, p.503, March 06-09, 1995
• 5: Free Software Foundation, Inc. http://www.gnu.org/software/gdb/gdb.html, Dec 2002.
• 6: George Hadjiyiannis , Silvina Hanono , Srinivas Devadas, ISDL: an instruction set description language for retargetability, Proceedings of the 34th annual conference on Design automation, p.299-302, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266108]
• 7: George Hadjiyiannis , Pietro Russo , Srinivas Devadas, A methodology for accurate performance evaluation in architecture exploration, Proceedings of the 36th ACM/IEEE conference on Design automation, p.927-932, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.310100]
• 8: Ashok Halambi , Peter Grun , Vijay Ganesh , Asheesh Khare , Nikil Dutt , Alex Nicolau, EXPRESSION: a language for architecture exploration through compiler/simulator retargetability, Proceedings of the conference on Design, automation and test in Europe, p.100-es, January 1999, Munich, Germany [doi>10.1145/307418.307549]
• 9: D. Huffman. A method for the construction of minimum redundancy codes. Proceedings of the Institute of Radio Engineers, 40:1098--1101, 1952.
• 10: International Business Machines Corporation. PowerPC Microprocessor Family: The Programming Environments for 32-bit Microprocessors, 2000.
• 11: Bernard M. E. Moret, Decision Trees and Diagrams, ACM Computing Surveys (CSUR), v.14 n.4, p.593-623, Dec. 1982 [doi>10.1145/356893.356898]
• 12: Sreerama K. Murthy, Automatic Construction of Decision Trees from Data: A Multi-Disciplinary Survey, Data Mining and Knowledge Discovery, v.2 n.4, p.345-389, December 1998 [doi>10.1023/A:1009744630224]
• 13: Achim Nohl , Gunnar Braun , Oliver Schliebusch , Rainer Leupers , Heinrich Meyr , Andreas Hoffmann, A universal technique for fast and flexible instruction-set architecture simulation, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA [doi>10.1145/513918.513927]
• 14: Stefan Pees , Andreas Hoffmann , Vojin Zivojnovic , Heinrich Meyr, LISA—machine description language for cycle-accurate models of programmable DSP architectures, Proceedings of the 36th ACM/IEEE conference on Design automation, p.933-938, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.310101]
• 15: N. Ramsey and M. F. Fernandez. The New Jersey Machine-Code Toolkit. In USENIX Technical Conference, pages 289--302, 1995.
• 16: R.W.Payne and D.A.Preece. Identification keys and diagnostic tables: a review. Journal of the Royal Statistics Society, Series A, 143(3):253--292, 1980.
• 17: C. E. Shannon. A mathematical theory of communication. Bell System Technical Journal, 27:379--423, 623--656, July, October 1948.
• 18: Henrik Theiling, Generating Decision Trees for Decoding Binaries, ACM SIGPLAN Notices, v.36 n.8, p.112-120, Aug. 2001

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

Additional Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis

General Terms:
Algorithms, Performance

Keywords:
binary decoder, decision tree, decoding tree, instruction set simulator