Parallel Infrastructure for Recognition of Non-Local Patterns from Particle Detectors

本项目研究高能物理（HEP）的模式识别算法。特别是，它着眼于从hep实验数据的模式识别，这需要全局信息，并使其具有很好的并行性。由于独立的数据（单独的高能碰撞的结果），HEP软件中一直存在一种微不足道的并行形式，但在单个事件中的模式识别方面做得很少。对于下一代实验来说，这是一个特别紧迫的问题，因为下一代实验的数据采集速度高达每25纳秒20兆字节，而快速的模式识别对于决定哪些事件应该保留下来供以后研究至关重要。由于单个事件会在许多不同的检测器中留下痕迹，因此这里的模式识别是非局部的、非顺序的模式匹配问题。其他物理学家试图在单次遍历数据时找到快速的启发式匹配。相比之下，本项目将对数据进行更仔细的分析，通过使用信号处理技术（例如卡尔曼滤波）对数据进行预处理，以更好地解决在时间和空间上接近的多个事件。该项目将使用更好的算法形式来利用计算机科学算法和数据结构，并将实现并行算法来识别非局部模式。预期的数据集将带来特殊的挑战，这些数据集具有pb级的大小。这些应用程序的新算法必须仔细考虑RAM和磁盘访问的不同访问时间。这个项目是跨学科的，对计算机科学和高能物理都有潜在的影响。

This project studies pattern recognition algorithms for High Energy Physics(HEP). In particular, it looks at pattern recognition for data from HEPexperiments which requires global information and lends itself well toparallelism. While a trivial form of parallelism has always been presentin HEP software due to the independent data (results of separate highenergy collisions), there has been little done for pattern recognitionwithin single events. This is a particularly pressing problem for the nextgeneration of experiments where data is taken in at rates of up to 20Mbytes each 25 nanoseconds and rapid pattern recognition is essential todecide which events should be kept for later study. Since a single eventwill leave traces in many different detectors, pattern recognition here isa non-local, non-sequential pattern matching problem.Other physicists have tried to find a quick heuristic match during a singlepass through the data. In contrast, this project will do a more carefulanalysis of the data to better resolve multiple events that are close intime and space by using signal processing techniques (e.g. Kalmanfiltering) to pre-process the data. The project will use a betteralgorithmic formalism to take advantage of computer science algorithms anddata structures, and will implement parallel algorithms to recognizenon-local patterns. Special challenges will be presented by theanticipated datasets, which have petabyte sizes. New algorithms for theseapplications will have to take careful account of the different accesstimes for RAM and disk access. This project is interdisciplinary innature, with potential impact on both computer science and high energyphysics.