Proposição de uma arquitetura para árvores de decisão orientada a notificações - ADON

Abstract

The increasing complexity of machine learning models requires evolving computing systems towards more efficient processing capabilities in terms of resource utilisation, energy consumption, and performance. This need has motivated research and the development of specialised hardware solutions to support those models. Due to their acceleration potential, a set of literature research focuses on implementing decision tree algorithms, namely ensemble methods, such as Random Forest and Gradient Boosting, on reconfigurable logic devices (FPGAs). However, the limited size of these platforms restricts the number of decision trees that can be allocated, compromising the algorithm’s efficiency and hardware performance. In addition, the structural and temporal redundancies inherent in these algorithm’s evaluations lead to inefficiencies in execution time and FPGA hardware synthesis size. These inefficiencies occur mainly due to decision tree structures composed essentially of ‘ifthen’ logical evaluations that require repeated assessment at various tree nodes. However, these algorithms would be especially suitable for benefiting from the concepts and properties of the Notification Oriented Paradigm (NOP), which avoids such redundancies and, moreover, allows fine-grained parallelism in FPGA. This thesis proposes the Notification-Oriented Decision Tree Architecture (NODTA), a novel architecture that integrates NOP principles for decision tree composition and execution, particularly emphasising Random Forest and Gradient Boosting. NODTA implements a unique notification chaining mechanism by adapting and extending NOP concepts. Its digital hardware implementation, NODTA-DH, presents enhanced inference acceleration and hardware efficiency. Experiments comparing the NODTADH performance against current state-of-the-art hardware implementation of decision trees, specifically using the open-source hls4ml library, present significant improvements. In this scenario, NODTA-DH’s logical model eliminates the redundancies in decision tree algorithms and achieves up to 70.5% reduction in LUT usage and 94.8% in FF requirements. Moreover, the inference phase showed a 13.02 times performance improvement through reduced processing time and enhanced classification rates. These results establish NODTA-DH as a viable solution for hardware implementation of decision tree-based algorithms, offering better performance and resource utilisation.