If fast is not fast enough: Real-time Graph Building for Microsecond Machine Learning Inference

A team of researchers from the Karlsruhe Institute of Technology (KIT) have developed a novel method for building graphs on Field-Programmable Gate Arrays (FPGAs) for machine learning applications in particle physics experiments in real time, submitted today as a preprint. The new method enables the semi-automatic generation of hardware-accelerated graph building architectures for locally constrained graphs based on formally described detector definitions. Graphs are mathematical structures that represent the relationships between objects or entities. Graph Neural Networks (GNNs) are a type of machine learning model that can learn from graph data and perform various tasks. One of these possible tasks is track finding, which is the process of reconstructing the trajectories of particles produced in collisions at particle colliders.

However, building graphs in real time for particle tracking is challenging, especially in very high background environments where several thousand detector hits are present. The conventional approach of using k-nearest neighbour algorithms to build graphs is computationally expensive and does not exploit the geometric constraints of the detector.
The researchers from KIT have proposed a new approach that uses FPGAs to build graphs in real time. FPGAs are devices that can be programmed to perform specific functions after manufacturing. They offer very high performance, parallel processing, and custom logic design capabilities.
The researchers have developed a design methodology that enables the semi-automatic generation of FPGA-based graph building architectures for locally constrained graphs. These graphs only include edges between nodes that satisfy certain geometric criteria based on the detector layout. The researchers have also defined a similarity measure to compare their approach with the k-nearest neighbour approach.

To demonstrate the feasibility of their method for particle physics applications, the researchers have implemented a case study for real-time graph building architecture for the Belle II central drift chamber using FPGAs. The Belle II experiment is one of the largest particle physics experiments in the world, located at the SuperKEKB accelerator in Japan. The experiment aims to study rare decays of B mesons and other particles to search for new physics beyond the Standard Model.
The researchers have shown that their FPGA-based graph building architecture is fully able to work within the hardware and software requirements of the Belle II trigger. The trigger is a system that selects interesting events from the huge amount of data produced by the collisions in real time. The researchers have also shown that their architecture achieves constant time complexity at the expense of linear space complexity, which means that it can handle any number of detector hits without slowing down, but requires more hardware utilization as the number of hits increases.

By enabling hardware-accelerated pre-processing of graphs, the researchers have paved the way for deploying novel GNNs in first level triggers of particle physics experiments. This could lead to improved performance and efficiency in particle tracking and other machine learning tasks.

This project is an interdisciplinary research project at KIT bringing together electrical engineering (Institute for Information Processing Technology, ITIV) and experimental particle physics (Institute of Experimental Particle Physics, ETP).

Contact: Prof. Dr. Torben Ferber