Speaker
Description
In high-energy physics experiment trigger systems, track segment seeding is a resource-intensive function. The primary reason lies in the high computational complexity of the segment-finding process— O(n³) in software implementations using nested loops, and O(n) × O(N²) in typical FPGA implementations, where n is the number of hits per detector layer in an event, and N is the number of bins within the coincidence search range. As Moore’s Law approaches its physical limits, simply piling up silicon resources is becoming less viable. Instead, reducing computational complexity—akin to how the FFT replaced the direct DFT in history —deserves serious consideration.
The Tiny Triplet Finder is a track segment recognition scheme that groups three or more hits satisfying a constraint, such as forming a straight line in the non-bend view or a circular arc in the barrel region of a solenoidal magnetic field (passing through the z-axis). It achieves the O(n³) segment-finding function in O(n) time (specifically, in 2n + 1 clock cycles), enabling applications that require real-time or online track finding. Key features of the Tiny Triplet Finder include:
-
Extremely low silicon resource usage:
In FPGA implementations, the logic element usage scales as O(N × log N), significantly reduced from the O(N²) in typical conventional track segment recognition designs. -
True triplet coincidence with a wider search range:
Due to its minimal resource consumption, the Tiny Triplet Finder eliminates the need for a preliminary “pairing” stage. This allows users to implement a relatively wider coincidence search range, unlike typical approaches which must restrict the range to reduce number of fake pairs. The wider search range permits various useful performance such as to find low-pₜ tracks. -
Support for higher-order coincidences:
While the term "triplet" refers to the minimum number of hits required to confidently identify a track, the scheme is not limited to three hits. In practice, it can handle quadruplet, quintuplet, or higher-order coincidences when more detector layers are available, improving fake track rejection in high-luminosity conditions. -
Not restricted by detector geometries:
The Tiny Triplet Finder functions as a general-purpose coincidence search engine adaptable to various detector geometries. -
Suitable for FPGA implementation:
The core of the Tiny Triplet Finder is a wide-range, single-clock-cycle shifter that performs necessary functions and consumes only O(N × log N) resources. This shifter can be implemented using standard FPGA components such as multipliers and block RAMs, reducing the need for logic elements and further conserving silicon area and power.
As a proof of concept, a 3D track segment seeding engine based on the Tiny Triplet Finder has been implemented and tested on a low-cost FPGA device. This engine preselects and groups detector hits (or stubs) for input into a subsequent track-fitting stage (e.g., a Kalman filter). The engine uses a Hough transform space in the r-z view and the Tiny Triplet Finder in the r-φ view to apply full 3D constraints. Organized as a pipeline, it processes each hit in a single clock cycle.
Moreover, the Tiny Triplet Finder serves as a general-purpose coincidence detection algorithm. To demonstrate its versatility, we tested its track-segment finding performance on two distinct detector geometries. In a collider-style barrel-layer geometry, we analyzed fake segment rates under 3D (r-φ + r-z) and 2D (r-φ or r-z only) configurations for high hit multiplicity events (>4000 hits per layer in the barrel region). In a second geometry with strip plane layers that include timing information, we studied both real and fake coincidences—with and without timing (“3D” or “2D”)—at various hit multiplicities. The seeding engine is capable of processing up to 112 hits (real and fake combined) per layer per event in 225 clock cycles.