Parallel CPU- and GPU-based connected component algorithms for event building for hybrid pixel detectors
and P. Mánek · 2024
Read Parallel CPU- and GPU-based connected component algorithms for event building for hybrid pixel detectors by and P. Mánek (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-11809.txt.
Introduction
Tomáš Čelko, František Mráz, Benedikt Bergmann, and Petr Mánek present a computing study from 2024 on pixel detectors. New Timepix detectors track particles with fine detail in space and time, but they make so many hits that saving each one is slow and wasteful.
The authors test ways to group hits into clusters on the fly, on both main chips and graphics chips. Their graphics chip method uses a union find design and reached a very high rate of hits per second. It ran far faster than the main chip methods and left those chips free for input and output work.
Catalog record
| CREATOR | and P. Mánek |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 31 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-11809
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Parallel CPU- and GPU-based connected component algorithms for event building for hybrid pixel detectors and P. Mánek Abstract The latest generation of Timepix series hybrid pixel detectors enhance particle tracking with high spatial and temporal resolution. However, their high hit-rate capability poses challenges for data processing, particularly in multidetector configurations or systems like Timepix4. Storing and processing each hit offline is inefficient for such high data throughput. To efficiently group partly unsorted pixel hits into clusters for particle event characterization, we explore parallel approaches for online clustering to enable real-time data reduction. Although using multiple CPU cores improved throughput, scaling linearly with the number of cores, load-balancing issues between processing and I/O led to occasional data loss. We propose a parallel connected component labeling algorithm using a union-find structure with path compression optimized for zero-suppression data encoding. Our GPU implementation achieved a throughput of up to 300 million hits per second, providing a two-order-of-magnitude speedup over compared CPU-based methods while also freeing CPU resources for I/O handling and reducing the data loss. 1 Introduction The Timepix family of pixelated semiconductor detectors [ 1 ] represents a significant advancement in particle detection technology, offering enhanced spatial and temporal resolution. With each new generation of detectors, the performance has progressively improved. A particularly notable development within this family is the Timepix3 detector [ 2 ] , which introduced a data-driven mode that allows precise measurements in high-flux radiation environments. The structure of the data produced by this detector can vary depending on the chosen operating mode. Typically, a pixel hit is registered for each pixel that records a non-zero induced voltage. Each pixel hit consists of the following information. The x and y coordinates indicate the spatial position of the hit pixel. Then, there is the timestamp corresponding to the moment when the voltage exceeds a predefined threshold, referred to as the time of arrival (ToA). Lastly, the time over threshold (ToT) indicates the magnitude of the induced voltage. Notably, data rates can surpass 40 million hits per second in high-flux scenarios, necessitating highly efficient data processing techniques. A significant bottleneck in current data processing workflows arises from the need to organize individual pixel hits into meaningful events based on their temporal and spatial proximity, a process referred to as clustering. A cluster is the detector’s response to ionizing radiation interacting with the sensor. The radiation leaves traces whose shape and energy content indicate – to some extent – particle type, particle energy, or the type of interaction. Informally, a cluster is the trace left by a particle or several coincident particles that participated in an event, e.g., a decay of a radioactive ion. This paper demonstrates how to accelerate clustering through parallel computing on both CPU and GPU architectures. Fast clustering has numerous applications, some of which are outlined below. First, computing cluster features that can be used for on-the-fly data filtering and data compression, reducing the storage space requirements. Second, clustering is a prerequisite for real-time particle identification and classification. Lastly, clustering can improve contrast in imaging applications by correcting for the charge-sharing effect [ 3 ] . Although the presented results were obtained using Timepix3, they are transferable to other detectors functioning in either data-driven or frame-based mode, including the higher-performing Timepix4, where the requirement for processing efficiency is even more pronounced. 2 Preliminaries – clustering Clustering is the process of grouping temporally and spatially coincident hits together. Formalizing this definition can result in multiple application-specific definitions, and we present three variants of such a definition. Given a sequence of hits H=\{h_{1},h_{2},\dots h_{n}\} , we say that subset C=\{h_{i_{1}},h_{i_{2}},\dots h_{i_{m}}\} is a cluster in H if all of the following conditions are satisfied: (i) There is no hit h\in H\setminus C such that C^{\prime}=C\cup\{h\} is a cluster (the maximality condition). (ii) For all h_{a},h_{b}\in C , there exists a sequence P=p_{1},p_{2},\dots p_{l} , P\subseteq C such that p_{1}=h_{a} , p_{l}=h_{b} , and for all i\in\{1,2,\dots l-1\} , hits p_{i} and p_{i+1} are spatially 8-neighboring (the spatial neighborhood condition). (iii) Based on the variant of the definition, one of the following conditions holds (a) For all sequences P as defined in (ii), it also holds |\mathrm{toa}(p_{i})-\mathrm{toa}(p_{i+1})|\leq\Delta t_{\mathrm{max}} for all i\in\{1,2,\dots l-1\} , where \mathrm{toa}(h) represents the time of arrival of hit h ( dynamic local-time-neighborhood variant used in [ 4 ] ) (b) For all h\in C , either \mathrm{toa}(h)=\min\{\mathrm{toa}(h)|h\in C\} or there exists h^{\prime}\in C\setminus\{h\} with \mathrm{toa}(h)-\Delta t_{max}\leq\mathrm{toa}(h^{\prime})\leq\mathrm{toa}(h) ( dynamic global-time-neighborhood variant used in [ 5 , 6 ] ). (c) For all h_{a},h_{b}\in C , |\mathrm{toa}(h_{a})-\mathrm{toa}(h_{b})|\leq\Delta t_{\mathrm{max}} ( static time-neighborhood variant used in [ 7 ] ) For large values of \Delta t_{\text{max}} or in the case of small clusters, these definitions yield identical results. However, as cluster size increases, particularly when \Delta t_{\text{max}} is less than the expected maximum duration of the cluster (time span), the differences between the approaches become more pronounced. In the following, unless otherwise specified, the variant with the dynamic local neighborhood (condition (iii)(a)) will be used for most applications. In the following subsections, we outline the core concepts of the existing state-of-the-art clustering approaches. 2.1 Frame-based clustering For detectors operating in a shutter-based mode, such as Timepix [ 8 ] , the output data can be interpreted as a sequence of image frames (similar to a standard camera). Each frame can be processed individually; we will treat it as a graph G=(V,E) . In this graph, each detected hit in the frame is a node in V . If two hits are adjacent in space and time, they are connected with an edge in E . Clustering in this context can be reduced to finding connected components in the graph G , which can be efficiently solved using graph traversal algorithms (e.g., depth-first-search). However, the use of a shutter introduces a potential loss of information. For example, two spatially overlapping clusters in a single frame could be mistakenly merged into a single cluster, even if there was a considerable time difference between them. Conversely, a cluster occurring near the shutter’s closing time could be incorrectly split into multiple frames. 2.2 Data-driven clustering In the case of a detector with a data-driven output mode (like Timepix3 [ 2 ] ), we can utilize an algorithm that processes data on a pixel-by-pixel basis, avoiding the loss of the information introduced by the shutter in the frame-based mode. Algorithm 1 addresses three possible scenarios for processing a hit based on the set of neighboring clusters to which the hit might belong. If no adjacent cluster exists, a new cluster is created. If the hit can be added to a single cluster, it is incorporated into that cluster. However, if the hit can be part of multiple clusters, those clusters should additionally be merged. The key difference between existing approaches lies in how neighboring clusters are identified for each hit and which data structures they use, e.g., in the implementation of the findNeighborClusters method. One approach is to iterate over the open clusters, conducting a hit membership query for each of them. Here, we need a data structure that allows fast membership queries such as a hash set (with expected constant-time query) or quadtree [ 9