A Complexity Agnostic Clustering Engine for Time Projection Chambers and its Implementation in FPGA

This paper presents a complexity-agnostic clustering engine implemented in an FPGA for Time Projection Chambers that guarantees predictable, linear-time processing by organizing hits into clusters within a fixed number of clock cycles, regardless of event complexity.

The Gist

Imagine you are at a massive, chaotic concert. Thousands of people (the "hits") are scattered across the venue, shouting and moving around. Your job is to sort them out: you need to group everyone who is part of the same conversation (a "cluster") together so you can listen to what they are saying later.

In the world of high-energy physics, scientists use giant detectors called Time Projection Chambers (TPCs) to track particles. These detectors generate a massive stream of data points (hits) every time a particle passes through. The problem? The data comes in a jumbled mess. A single particle's path might look like a line of dots, but in the data stream, those dots are mixed up with dots from other particles, arriving in random order.

The Old Way: The Slow Librarian

Traditionally, sorting this data was like having a librarian try to organize a library by checking every single book against every other book to see if they belong on the same shelf.

• The Problem: If you have 100 books, you do 100 checks. If you have 1,000 books, you do 1,000,000 checks. This is called O(n²) complexity. As the crowd gets bigger, the librarian gets overwhelmed and the process slows down to a crawl. In a real-time physics experiment, you can't wait that long; you need to sort the data instantly as it happens.

The New Solution: The "Smart Sorting Machine"

The paper describes a new, super-fast machine built inside a chip called an FPGA (a programmable brain for electronics). This machine doesn't guess or compare everything to everything. Instead, it uses a clever two-step trick to sort the data in O(n) time (linear time), meaning it takes the same amount of effort whether there are 10 hits or 10,000 hits.

Here is how it works, using a simple analogy:

Phase 1: The "Check-In" (Data Filling)

Imagine the chaotic concert crowd rushing into a building.

1. The Map: The machine has a giant, empty grid on the wall (called Hit ID RAM). The grid is organized by Time (when they arrived) and Location (which channel they are in).
2. The Ticket: As each person (hit) walks in, the machine looks at their ticket (header), finds their spot on the grid, and writes down their name (Hit Number) in that specific square.
3. The Result: In a flash, the machine has mapped out exactly where every single person is standing on the grid. It doesn't matter how crowded it is; it just drops a name in a box.

Phase 2: The "Group Walk" (Data Outputting)

Now, the machine needs to get the groups out of the building in order.

1. The Search: The machine looks at the grid. It picks the first person it sees.
2. The Neighbor Check: It asks, "Who is standing right next to you?" (checking the squares immediately to the left, right, above, or below).
3. The Chain Reaction: If it finds a neighbor, it grabs them and asks, "Who is next to you?" It keeps doing this, following the chain of neighbors like a game of "connect the dots."
4. The Output: It pulls out the entire group (the cluster) and sends them out together.
5. Repeat: Once a group is gone, it erases their names from the grid and finds the next person who hasn't left yet, starting a new chain.

Why This is a Big Deal

• Predictable Speed: The old way got slower as the crowd got bigger. This new machine takes exactly the same amount of time to sort a small group as it does a huge group. It's like a conveyor belt that never jams, no matter how many boxes you put on it.
• No "Leftovers": The math is clean. There are no hidden, slow steps that pop up when the data gets complex.
• Real-World Test: The authors built this on a cheap, small computer chip (an FPGA) and ran it at 200 million cycles per second. They tested it with messy, random data, and it successfully reorganized the chaos into neat, tidy groups every time.

The "Double-Check" Trick

The paper mentions one small quirk: sometimes the machine might start grouping a conversation in the middle (e.g., it grabs people 5, 6, and 7, but misses 1, 2, 3, and 4).

• The Fix: If you need the groups to be perfectly ordered from start to finish (like a story from beginning to end), you just run the data through two of these machines in a row. The first one does the heavy lifting of grouping, and the second one just tidies up the order.

In a Nutshell

This paper presents a new, lightning-fast way to organize the chaotic data from particle detectors. Instead of comparing every dot to every other dot (which is slow), it uses a smart "map and chain" method to group related data instantly. This allows scientists to process complex physics events in real-time, ensuring they don't miss any crucial discoveries because the computer was too busy sorting the data.

Technical Summary

1. Problem Statement

In modern high-energy and nuclear physics experiments, Time Projection Chambers (TPCs) generate vast amounts of data where "hits" (electron cloud detections) must be grouped into clusters representing charged particle tracks.

• Computational Complexity: Traditional software-based clustering uses nested loops, resulting in $O(n^2)$ time complexity, where $n$ is the number of hits. This is too slow for real-time trigger systems.
• Hardware Limitations: Existing FPGA implementations often use "unrolled" hardware blocks to achieve $O(n)$ performance. However, these approaches are complexity-dependent; they fail or exhibit non-deterministic timing (with residual $O(n^2)$ terms) when event complexity (number of hits per event, clusters, or hits per cluster) exceeds specific design limits.
• Requirement: There is a need for a clustering engine that operates with predictable, deterministic time regardless of event complexity, provided the total number of hits remains within a fixed limit.

2. Methodology

The authors propose a Complexity-Agnostic Clustering Engine that utilizes indexing search via Block Random Access Memory (RAM) to eliminate $O(n^2)$ computations. The core logic operates in two distinct phases:

A. Data Structure and Memory Mapping

• Hit ID RAM: The core component is a 2D Block RAM array where the X-axis represents Time Bins and the Y-axis represents Channels.
• Addressing: The RAM address is derived from the {Time, Channel} pair in the hit header.
• Content: Each RAM location stores a Hit Valid flag and a Hit Number (a running count of the input stream).
• Cluster Logic: Clusters form lines in the Time-Channel map. A hit is connected to neighbors if the channel changes by $\pm 1$ and the time bin changes by $\{-1, 0, +1\}$.

B. Two-Phase Operation

The engine processes data in two phases, each taking an equal number of clock cycles, ensuring total operation time is exactly twice the data filling time.

1. Phase 1: Data Filling (Write Phase)

   • Incoming hits (header + ADC data) are stored in a Hit Buffer.
   • The hit header is parsed, and an entry is written to the Hit ID RAM at the address corresponding to {Time, Channel}.
   • A Bit Register tracks which hits have been filled, and a Priority Encoder identifies the highest Hit Number currently in the buffer.

2. Phase 2: Data Outputting (Read/Clustering Phase)

   • Initialization: The system starts with the highest Hit Number (determined by the Priority Encoder).
   • Neighbor Search: The Hit Indexing Unit reads the current hit from the Hit Buffer and checks the Hit ID RAM for neighbors in adjacent channels ($CH \pm 1$) and adjacent time bins ($TM \pm 1, 0$).
   • Traversal:
     • If a neighbor exists, the engine follows that path (prioritizing $CH+1$), marking the current hit as "cleared" in the Bit Register and RAM to prevent re-processing.
     • If no neighbors remain, the engine jumps to the next highest unread Hit Number.
   • Hardware Optimization: To handle the 2D search efficiently within a single clock cycle, the Hit ID RAM is implemented using four physical RAM blocks (representing time bins $TM[9..8] = 00, 01, 10, 11$). This allows simultaneous addressing of current and neighbor bins.
   • Timing: Reading and processing a single hit takes 8 clock cycles.

3. Key Contributions

• Deterministic Latency: The engine guarantees $O(n)$ operation time with no residual $O(n^2)$ term. The total time is strictly $2 \times$ (data filling time), regardless of how hits are distributed or how complex the clusters are.
• Arbitrary Complexity Handling: The system can handle events with arbitrary numbers of clusters and hits per cluster, limited only by the total number of hits fitting in the pre-designed memory buffer.
• Full Data Preservation: Unlike some compression methods, this engine preserves the full data package (header + 15+ ADC values) and reorders it so that all hits belonging to a single cluster are output contiguously.
• Cascading for Ordering: While the single engine outputs clusters contiguously, the entry point within a cluster may be random. The authors propose cascading two engines to achieve strict end-to-end ordering (from one end of the track to the other).

4. Implementation and Results

• Hardware Platform: Implemented on a low-cost Altera Cyclone V (5CGXFC5C6F27C7) FPGA (Terasic C5G module).
• Performance:
  • Operating Frequency: Successfully compiled and tested at 200 MHz (near the device's 275 MHz limit for M10K block RAM).
  • Resource Usage: Consumes a very small amount of FPGA resources (Logic Elements and Block RAMs).
• Testing Scenarios:
  • Standard Event: Tested with ~110 hits and 28 clusters. Results confirmed that hits were correctly reordered, with all hits of a specific cluster appearing consecutively in the output stream.
  • Extreme Complexity: Tested with very long clusters. The engine successfully reorganized the data without timing failures.
  • Cascaded Test: Demonstrated that two cascaded engines successfully reordered clusters from one end to the other.

5. Significance

• Real-Time Trigger Viability: This solution enables TPC trigger systems to perform clustering in real-time with predictable latency, a critical requirement for high-luminosity physics experiments where event rates are high.
• Scalability: Since modern TPC readout systems use FPGAs significantly larger than the Cyclone V used in testing, multiple instances of this engine can be deployed in parallel to handle high-bandwidth data streams (e.g., 50 MHz for gas TPCs or 2 MHz for Liquid Argon TPCs).
• Efficiency: By leveraging Block RAM for indexing rather than complex logic unrolling, the design achieves high performance with low resource consumption, making it suitable for cost-effective and power-efficient detector readout systems.