Automated synthesis of efficient binary decoders for retargetable software toolkits

Wei Qin, Sharad Malik

Research output: Contribution to journalConference articlepeer-review

19 Scopus citations


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 frame-works 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.

Original languageEnglish (US)
Pages (from-to)764-769
Number of pages6
JournalProceedings - Design Automation Conference
StatePublished - 2003
EventProceedings of the 40th Design Automation Conference - Anaheim, CA, United States
Duration: Jun 2 2003Jun 6 2003

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture
  • Control and Systems Engineering


  • Binary decoder
  • Decision tree
  • Decoding tree
  • Instruction set simulator


Dive into the research topics of 'Automated synthesis of efficient binary decoders for retargetable software toolkits'. Together they form a unique fingerprint.

Cite this