Digital Library

Functional analysis and performance evaluation of decoder decision tree generation algorithms

• Lillian Tadros

(2023). ECMS 2023, 37th Proceedings
Edited by: Enrico Vicario, Romeo Bandinelli, Virginia Fani, Michele Mastroianni, European Council for Modelling and Simulation.
DOI: http://doi.org/10.7148/2023
ISSN: 2522-2422 (ONLINE)
ISSN: 2522-2414 (PRINT)
ISSN: 2522-2430 (CD-ROM)
ISBN: 978-3-937436-80-7
ISBN: 978-3-937436-79-1 (CD) Communications of the ECMS Volume 37, Issue 1, June 2023, Florence, Italy June 20th – June 23rd, 2023

https://doi.org/10.7148/2023-0262

Lillian tadros (2023). Functional Analysis and Performance Evaluation of Decoder Decision Tree Generation Algorithms, ECMS 2023, Proceedings Edited by: Enrico Vicario, Romeo Bandinelli, Virginia Fani, Michele Mastroianni, European Council for Modelling and Simulation. doi:10.7148/2023-0262

Instruction decoders are indispensable components
of instruction set simulators and processor toolchains. The
lengthy and elaborate manual implementation of decoders can
be greatly alleviated by decoder generation tools. These need to
handle the rising complexity of modern instruction sets, notably
irregularities such as non-uniform opcodes and logic propositions
on bit fields. In addition, decoder generators need to provide
cost-optimized solutions, as the efficiency of the decoding module
can have a substantial effect on the overall performance. This
paper analyzes five published algorithms for decoder generators
from two perspectives: First, in terms of functionality, we
systematically assess how each tool handles different properties
of modern instruction sets, highlighting properties that are
challenging, unhandled by current algorithms or even result in
functionally erroneous decoders. Second, we challenge seemingly
intuitive definitions of decoder optimality using a sophisticated
model of decision tree cost. We validate this analytical model
against an experimental performance evaluation of generated
decoders for SPARC, MIPS32 and ARMv7 platforms. For our
analysis, we implemented all five algorithms after correcting the
discovered conceptual errors and extending them to handle the
above-mentioned ISAs. Our work reveals that state-of-the-art
decoder generation tools are unable to fully and correctly handle
complex ISAs and adopt an erroneous notion of optimality.