769 research outputs found
On-line reconstruction algorithms for the CBM and ALICE experiments
No full textDiese Dissertation präsentiert verschiedenen Algorithmen, die für die Echtzeit-Ereignisrekonstruktion im CBM-Experiment der GSI (in Darmstadt) und im ALICE-Experiment am CERN (in Genf) entwickelt wurden. Obwohl diese Experimente unterschiedlich sind - CBM ist ein Fixed-Target Experiment mit Forward-Geometrie, während ALICE eine typische Collider-Geometrie hat - gibt es bei der Rekonstruktion gemeinsame Aspekte.
Diese Arbeit beschreibt:
— allgemeine Änderungen an der Kalman-Filter-Methode, die bestehende Fit-Algorithmen (auch Anpassungsalgorithmen genannt) beschleunigen, vereinfachen sowie deren numerische Stabilität verbessern.
— Fit-Algorithmen, die für die CBM und ALICE Experimente entwickelt wurden, inklusive einer neuen Methode für die Spurextrapolation in nicht-homogenen Magnetfeldern.
— die entwickelten Algorithmen für die Bestimmung der primären und sekundären Vertices in beiden Experimenten. Insbesondere wird eine Methode zur Rekonstruktion der zerfallenen Teilchen vorgestellt.
— parallelisierte Methoden für die Echtzeit-Spursuche im CBM Experiment.
— parallelisierte Methoden zur Echtzeit-Spursuche im High Level Trigger des ALICE-Experiments.
— die Realisierung der Spurrekonsturtion auf moderner Hardware, insbesondere Vektorprozessoren und GPUs.
Alle vorgestellten Methoden sind vom oder mit direkter Beteiligung des Autors entwickelt worden.This thesis presents various algorithms which have been developed for on-line event reconstruction in the CBM experiment at GSI, Darmstadt and the ALICE experiment at CERN, Geneve. Despite the fact that the experiments are different — CBM is a fixed target experiment with forward geometry, while ALICE has a typical collider geometry — they share common aspects when reconstruction is concerned.
The thesis describes:
— general modifications to the Kalman filter method, which allows one to accelerate, to improve, and to simplify existing fit algorithms;
— developed algorithms for track fit in CBM and ALICE experiment, including a new method for track extrapolation in non-homogeneous magnetic field.
— developed algorithms for primary and secondary vertex fit in the both experiments. In particular, a new method of reconstruction of decayed particles is presented.
— developed parallel algorithm for the on-line tracking in the CBM experiment.
— developed parallel algorithm for the on-line tracking in High Level Trigger of the ALICE experiment.
— the realisation of the track finders on modern hardware, such as SIMD CPU registers and GPU accelerators.
All the presented methods have been developed by or with the direct participation of the author
An erasure-resilient and compute-efficient coding scheme for storage applications
No full textDriven by rapid technological advancements, the amount of data that is created, captured, communicated, and stored worldwide has grown exponentially over the past decades. Along with this development it has become critical for many disciplines of science and business to being able to gather and analyze large amounts of data. The sheer volume of the data often exceeds the capabilities of classical storage systems, with the result that current large-scale storage systems are highly distributed and are comprised of a high number of individual storage components. As with any other electronic device, the reliability of storage hardware is governed by certain probability distributions, which in turn are influenced by the physical processes utilized to store the information. The traditional way to deal with the inherent unreliability of combined storage systems is to replicate the data several times. Another popular approach to achieve failure tolerance is to calculate the block-wise parity in one or more dimensions. With better understanding of the different failure modes of storage components, it has become evident that sophisticated high-level error detection and correction techniques are indispensable for the ever-growing distributed systems. The utilization of powerful cyclic error-correcting codes, however, comes with a high computational penalty, since the required operations over finite fields do not map very well onto current commodity processors. This thesis introduces a versatile coding scheme with fully adjustable fault-tolerance that is tailored specifically to modern processor architectures. To reduce stress on the memory subsystem the conventional table-based algorithm for multiplication over finite fields has been replaced with a polynomial version. This arithmetically intense algorithm is better suited to the wide SIMD units of the currently available general purpose processors, but also displays significant benefits when used with modern many-core accelerator devices (for instance the popular general purpose graphics processing units). A CPU implementation using SSE and a GPU version using CUDA are presented. The performance of the multiplication depends on the distribution of the polynomial coefficients in the finite field elements. This property has been used to create suitable matrices that generate a linear systematic erasure-correcting code which shows a significantly increased multiplication performance for the relevant matrix elements. Several approaches to obtain the optimized generator matrices are elaborated and their implications are discussed. A Monte-Carlo-based construction method allows it to influence the specific shape of the generator matrices and thus to adapt them to special storage and archiving workloads. Extensive benchmarks on CPU and GPU demonstrate the superior performance and the future application scenarios of this novel erasure-resilient coding scheme
Anan — a debugger for compute clusters
No full textDas Projekt anan ist ein Werkzeug zur Fehlersuche in verteilten Hochleistungsrechnern. Die Neuheit des Beitrags besteht darin, dass die bekannten Methoden, die bereits erfolgreich zum Debuggen von Soft- und Hardware eingesetzt werden, auf Hochleistungs-Rechnen übertragen worden sind. Im Rahmen der vorliegenden Arbeit wurde ein Werkzeug namens anan implementiert, das bei der Fehlersuche hilft. Außerdem kann es als dynamischeres Monitoring eingesetzt werden. Beide Einsatzzwecke sind
getestet worden.
Das Werkzeug besteht aus zwei Teilen:
1. aus einem Teil namens anan, der interaktiv vom Nutzer bedient wird
2. und aus einem Teil namens anand, der automatisiert die verlangten Messwerte erhebt und nötigenfalls Befehle ausführt.
Der Teil anan führt Sensoren aus — kleine mustergesteuerte Algorithmen —, deren Ergebnisse per anan zusammengeführt werden. In erster Näherung lässt anan sich als Monitoring beschreiben, welches (1) schnell umkonfiguriert werden (2) komplexere Werte messen kann, die über Korrelationen einfacher Zeitreihen hinausgehen
Cellular automaton based track finder in the STAR experiment (BNL, USA)
No full textThe relevant field of interest in High Energy Physics experiments is shifting to searching and studying extremely rare particles and phenomena. The search for rare probes requires an increase in the number of available statistics by increasing the particle interaction rate. The structure of the events also becomes more complicated, the multiplicity of particles in each event increases, and a pileup appears. Due to technical limitations, such data flow becomes impossible to store fully on available storage devices. The solution to the problem is the correct triggering of events and real-time data processing.
In this work, the issue of accelerating and improving the algorithms for reconstruction of the charged particles' trajectories based on the Cellular Automaton in the STAR experiment is considered to implement them for track reconstruction in real-time within the High-Level Trigger. This is an important step in the preparation of the CBM experiment as part of the FAIR Phase-0 program. The study of online data processing methods in real conditions at similar interaction energies allows us to study this process and determine the possible weaknesses of the approach.
Two versions of the Cellular Automaton based track reconstruction are discussed, which are used, depending on the detecting systems' features. HFT~CA Track Finder, similar to the tracking algorithm of the CBM experiment, has been accelerated by several hundred times, using both algorithm optimization and data-level parallelism. TPC~CA Track Finder has been upgraded to improve the reconstruction quality while maintaining high calculation speed. The algorithm was tuned to work with the new iTPC geometry and provided an additional module for very low momentum track reconstruction.
The improved track reconstruction algorithm for the TPC detector in the STAR experiment was included in the HLT reconstruction chain and successfully tested in the express production for the online real data analysis. This made it possible to obtain important physical results during the experiment runtime without the full offline data processing. The tracker is also being prepared for integration into a standard offline data processing chain, after which it will become the basic track search algorithm in the STAR experiment.Das Interessensgebiet der Hochenergiephysik-Experimente verschiebt sich hin zur Suche und Untersuchung extrem seltener Teilchen und Phänomene. Zur Erhöhung der Anzahl verfügbarer Statistiken über seltene Ereignisse erfordert es einen Anstieg der Kollisionsrate von Teilchen. Die Struktur der Ereignisse wird komplizierter, die Teilchenvielfalt in jedem Event nimmt zu und es kommt zur Überlagerung von Ereignissen. Aufgrund technischer Einschränkungen kann ein solcher Datenfluss nicht vollständig auf verfügbaren Speichergeräten zur späteren Analyse gesichert werden. Die Lösung des Problems liegt in der korrekten Selektion von Ereignissen und der Datenverarbeitung in Echtzeit.
In dieser Arbeit wird der Aspekt der Beschleunigung und Verbesserung der Algorithmen zur Rekonstruktion der Flugbahnen geladener Teilchen basierend auf einem zellulären Automaten in dem STAR-Experiment betrachtet, um die Algorithmen für die Spurrekonstruktion in Echtzeit innerhalb des High-Level-Triggers zu implementieren. Dies ist ein wichtiger Schritt in der Vorbereitung des CBM-Experiments im Rahmen des Phase-0-Programms der FAIR. Die Untersuchung von Online-Datenverarbeitungsmethoden unter realen Bedingungen bei ähnlichen Kollisionsenergien ermöglicht es uns, diesen Prozess zu untersuchen und die möglichen Schwächen des jeweiligen Ansatzes zu bestimmen.
Es werden zwei Varianten der auf einem zellulären Automaten basierenden Spurrekonstruktion analysiert, die je nach den Merkmalen der Erkennungssysteme verwendet werden. Der HFT~CA Track Finder, ähnlich dem Tracking-Algorithmus des CBM-Experiments, wurde um das mehrere Hundertfache beschleunigt, indem sowohl Algorithmusoptimierungen durchgeführt als auch Datenparallelität ausgenutzt wurden. Der TPC~CA Track Finder wurde aktualisiert, um die Rekonstruktionsqualität zu verbessern und gleichzeitig eine hohe Berechnungsgeschwindigkeit beizubehalten. Dieser Algorithmus wurde auf die Arbeit mit der neuen iTPC-Geometrie abgestimmt und stellt ein zusätzliches Modul für die Streckenrekonstruktion von Teilchen mit sehr geringem Momentum bereit.
Der verbesserte Spurrekonstruktionsalgorithmus für den TPC-Detektor im STAR-Experiment wurde in die HLT-Rekonstruktionskette aufgenommen und erfolgreich in der „STAR-Express-Production“ für die Online-Echtdatenanalyse getestet. Dadurch war es möglich, wichtige physikalische Ergebnisse während der Versuchslaufzeit, ohne die vollständige Offline-Datenverarbeitung, zu erhalten. Der Tracker wird auch für die Integration in eine Standard-Offline-Datenverarbeitungskette vorbereitet, wonach er zum grundlegenden Spur-Suchalgorithmus im STAR-Experiment wird
Fast Failure Erasure Encoding Using Just in Time Compilation for CPUs, GPUs, and FPGAs
No full textFailure tolerant data encoding and storage is of paramount importance for data centers, supercomputers, data transfers, and many aspects of information technology. Reed-Solomon failure erasure codes and their variants are the basis for many applications in this field. Efficient implementation of these codes is challenging because they require computations in Galois fields, which are not supported by processors natively. Improved variants such as the Cauchy-Reed-Solomon code enable a better mapping of the required calculations to computer instructions. However, this works best when the source code of the application is tuned for fixed encoding parameters which deteriorates the flexibility. We present an approach to overcoming these limitations by just in time compiling optimized code for arbitrary encoding settings. Our open source library is optimized for x86 processors using SSE and AVX extensions and we present prototypes for GPUs and FPGAs as well. For a significant range of encoding parameters, our implementation encodes at the maximum bandwidth the processor can read the data from memory. In more complicated settings with additional redundancy data to compensate the failure of multiple data stores, the algorithm becomes compute limited. The optimized JIT code leverages the full potential of modern processors reaching an instruction throughput of more than three SIMD-instructions per compute cycle, and encodes up to 19 gigabytes of data per second on a Skylake system
- …
