• REAL-TIME PATTERN MATCHING
• FTK PROCESSOR
• EMBEDDED SYSTEM
• BIG DATA
• ATLAS EXPERIMENT
• TRIGGER

The Fast TracKer project and in particular the Associative Memory system aims at setting new standards for speed of computation for pattern recognition, enabling technological advancements useful to research and society. This technology is based on a Processing Unit made of the combination of FPGAs and a full custom associative memory AM-chip. In the Associative Memory system, pattern matching is executed with the maximum parallelism, and the results are then refined using FPGAs.
The Processing Unit has been developed for high energy physics, and its purpose is the real time track reconstruction at hadron collider experiments which is a crucial task for the success of such experiments. There, the most interesting processes are very rare and hidden in an extremely large level of background information. Selecting interesting events from the background in real time is therefore essential to fully exploit the physics potential of experiments where only a very limited fraction of the produced data can be recorded. Only 1 over 107 produced data sets, called "events", can be written to disk to perform physics analysis. Therefore, the selection system must be extremely accurate and fast in order to store and post-process potentially interesting events. Tracking devices, and in particular silicon detectors that are becoming the predominant tracking technology, play an essential role in the identification of interesting
events. In fact, they provide very detailed information for charged particles and they can separate most of the different particle trajectories in the overlapping collisions recorded in the same event. However, these detectors contain hundreds of millions of channels, so they make the problem of complete tracking a formidable challenge even for large computing farms. The events contain many soft, not interesting collisions superimposed to the interesting one, the hard scattering. This level of confusion is due to the
collider extremely high collision rate necessary to produce rare particles, as the Higgs boson recently discovered at CERN, at an appreciable rate. These conditions are going to worsen in the future experiments. The Large Hadron Collider (LHC) at CERN will produce 80 overlapped events before 2020 and this number will grow up to hundreds of collisions for the following machine upgrade.
On the other hand, the state-of-the-art electronics are advanced enough to overcome the problem. We provided real-time tracking using a massively-parallel high-performance system. Our solution provides the required performance for a relatively low cost, lower energy consumption, and saving space (by using a more compact system). We implemented an innovative strategy, based on the optimal mapping of a complex algorithm on different technologies. Our target is to get the optimal results by combining the high performance of rigid dedicated hardware with the distinctive flexibility of the FPGA and of general-purpose, but lower-performance, CPUs. The architecture’s key role is played by FPGAs, while the majority of computing power is provided by cooperating full-custom ASICs named Associative Memory. The AM-chip is suitable for massive
parallelism in data correlation searches and it has a key role in the system. One Processing Unit hosts 64 AM-chips, and it is able to perform bitwise comparisons at 120 Pbit/s. The memory access bandwidth and number of comparisons per second has, to the best of our knowledge, no equal in commercial resources. It takes full advantage of the intrinsic parallel nature of the combinatorial problem by comparing at once the
data under analysis to a set of pre-calculated "expectations", or patterns. This approach reduces to linear the exponential complexity of CPU-based algorithms and the problem is solved by the time data are loaded into the system.
Data processing speed is achieved with pipelining, and parallel processing. Track reconstruction is executed with a two steps pipeline architecture. The AM system implements the first stage by recognizing track candidates at low resolution. The second stage, the Track Fitter, is implemented using FPGAs. The Track Fitter receives track candidates and high resolution hits to refine pattern recognition at the associative memory output rate. "Hit" refers to the centroid of the charge left by the ionization process due to the crossing particle. Track fitting is done rapidly by replacing a helical fit with a simplified calculation that is linear in the local hit position in each silicon layer. The calculation is a set of scalar products of the hit coordinates and pre-calculated constants that take into account the detector geometry and alignment. While FTK is under construction at ATLAS experiment, the CMS experiment is developing its R&D for online tracking. The CMS R&D exploits a similar approach for real time track reconstruction at much higher rates in the CMS upgraded experiment that should take data after 2020.
In this thesis is briefly described the Large Hadron Collider and the ATLAS experiment in Chapter 1.
Chapter 2 shows the Fast TracKer project, and a description of the main parts of the system.
Chapter 3 describes the Associative Memory system, and the detailed description of the main elements of the system. The main activities and results of my PhD studies are described in this chapter. I designed the motherboard (AMB) and the daughter-board (LAMB). I performed an interesting study concerning signal integrity in an high serial links density PCB. I presented these results in San Diego 2015 IEEE Nuclear Science Symposium and Medical Imaging Conference, and the results have been published on a journal article on IEEE Transactions on Nuclear Science. I designed the programmable logic and wrote the VHDL code for the FPGAs on those boards. I gave my contribution and advise to design the AM-chip package, and the new generation of AM-chip. At the end of the Chapter 3 there are also the tests, results and validation procedure that I performed before the production and installation phase. The final results and performances
are described in Section 3.6.3.
In Chapter 4 is described the Associative Memory system infrastructure. Since the AM system is a custom processor with high density of power consumption, we designed a dedicated rack layout and designed a custom fan unit in order to maintain the temperatures low. Concerning these issues I designed the PCB with particular care to the power dissipation and the low air flow resistance. I gave also my contribution to the
temperature simulations that we performed on the chips, boards and on the crate. These results have been presented in the 20th IEEE Real Time Conference 2016 and the relative IEEE TNS paper will be published soon.
The AM system has been developed for high energy physics, but it is a flexible and powerful embedded system for potential application in a wide range of fields. These future possible evolutions are described in the Chapter 5. I gave my contributions and feedbacks concerning these future applications which are under developing. The very first results have been published and presented in the 14th Vienna Conference on Instrumentation, and an IEEE TNS paper (to be published) related to the presentation at the 20th IEEE Real Time Conference 2016.

Con il progetto Fast TracKer ed in particolare con il sistema Associative Memory System si vogliono raggiungere prestazioni per l’esecuzione di algoritmi di pattern recognition mai raggiunte prima, rendendo disponibili le sue potenzialità tecnologiche all’ambito della ricerca e della società. Questa tecnologia è costituita da un’unità di processamento, chiamata Processing Unit. La PU è a sua volta composta da numerosi FPGA e da decine di chip full custom di memoria associativa, chiamati AM chip. Nel sistema di Memoria Associativa, l’esecuzione dell’algoritmo di pattern matching è estremante parallelizzato, infatti è eseguito da decine di AM chip che lavorano in parallelo. Il risultato è successivamente elaborato da decine di FPGA. La PU è stata sviluppata per elaborare dati prodotti in esperimenti nel campo della fisica delle alte energie, e il suo scopo è quello di ricostruire in tempo reale tutte le tracce prodotte in esperimenti ai collisori adronici. Questo è un compito cruciale per la riuscita di tali esperimenti. In questo ambito i processi di fisica più interessanti sono molto rari e sono nascosti da un rumore di fondo ordini di grandezza più grande. Selezionare i set di dati (chiamati eventi) interessanti in tempo reale è essenziale, poichè è impossibile salvare tutti i dati prodotti per un’analisi successiva. Solo  1 evento su 107 può essere salvato su disco per analisi successive. Quindi la selezione degli eventi deve essere estremamente accurata e veloce. I sistemi di tracciatura e in particolare quelli in silicio, che stanno diventando sempre più predominanti, giocano un ruolo fondamentale nell’identificazione di eventi interessanti. Infatti forniscono informazioni molto dettagliate e possono discriminare le differenti traiettorie di particelle prodotte in collisioni simultanee all’interno dello stesso evento. D’altro canto, questi sistemi di tracciatura in silicio hanno centinaia di milioni di canali di lettura in uscita, che rendono il problema
della completa tracciatura di un evento una sfida impossibile anche per grandi computer farm. Gli eventi contengono decine di collisioni non interessanti sovrapposte a quella interessante e questo livello di confusione è dovuto all’alta frequenza di collisioni necessaria a produrre particelle rare, come il Bosone di Higgs scoperto al CERN. Queste condizioni saranno sempre più estreme in esterimenti futuri. Il Large Hadron Collider al CERN produrrà 80 collisioni sovrapposte per ogni singolo evento entro il 2020 e
questo numero supererà il centinaio negli anni successivi. D’altro canto anche lo stato dell’arte dell’elettronica è migliorato in termini di prestazioni ed è quindi possibile superare questi problemi. Il nostro progetto è costituito da un sistema di processamento estremamente parallelizzato che esegue ricostruzione di tracce in tempo reale ad elevate prestazioni. La nostra soluzione fornisce le performance
richieste ad un costo più basso, bassa potenza ed elevata compattezza se paragonato ad un possibile equivalente sistema realizzato con CPU. Abbiamo implementato una strategia innovativa basata sulla mappatura ottima di un algoritmo su differenti tecnologie.
L’obiettivo è quello di ottimizzare il sistema, combinando le elevate prestazioni di un ASIC con la flessibilità degli FPGA e delle CPU. Grazie alla sua flessibilità un rolo chiave nell’architettura proposta è giocato dal FPGA, mentre la maggior parte della potenza di calcolo è fornita dal ASIC AM chip. Il chip di Memoria Associativa è adatto a eseguire ricerche di correlazioni tra dati in un’architettura fortemente parallelizzata. La PU ospita 64 AM chip, e 4 FPGA, ed è in grado di confrontare 120 Pbit/s. Considerando
la quantità di confronti al secondo e la banda di input/output del chip, non esiste, al meglio delle nostre conoscenze, un dispositivo in commercio paragonabile al AM chip.
Anche l’architettura del chip è fortemente parallela, atta a confrontare simultaneamente il dato in ingresso con tutta la memoria. Quest’ ultima è costituita da set di dati attesi che sono calcolati e salvati nel chip nella fase di configurazione. Questo dispositivo permette di ridurre la complessità dell’algoritmo da esponenziale (se eseguito da CPU) a lineare.
La ricostruzione delle tracce è eseguita in due stadi successivi, grazie ad un’architettura a pipeline. Il sistema di Memoria Associativa implementa il primo stadio della pipeline identificando le tracce a una risoluzione ridotta. Il secondo stadio è chiamato Track Fitter, ed è implementato completamente con FPGA. Il Track Fitter riceve le tracce a bassa risoluzione trovate dal sistema di Memoria Associativa e combinandole
con gli HIT ad alta risoluzione è in grado di ricostruire i parametri delle tracce a piena risoluzione. HIT si riferisce al baricentro della carica depositata dai processi di ionizzazione dovuti alle particelle che attraversano il rivelatore. La ricostruzione della traccia è eseguita rapidamente utilizzando un’approssimazione lineare nell’intorno del HIT, invece che utilizzare una ricostruzione non lineare che sarebbe più precisa ma più lenta da eseguire. Infatti il calcolo consiste solamente nell’esecuzione di prodotti scalari tra i vettori di coordinate degli HIT e delle matrici di costanti precalcolate che tengono
conto della geometria del rivelatore.
Mentre FTK è in fase di costruzione e installazione presso l’esperimento ATLAS, anche l’esperimento CMS ha approvato un progetto di ricerca e sviluppo per ricostruzione di tracce in tempo reale. Tale progetto sfrutta un approccio simile a FTK per la ricostruzione di tracce a velocità più alte e potrebbe essere installato già dopo il 2020.
In questo elaborato, nel Capitolo 1 è descritto brevemente il Large Hadron Collider e l’esperimento ATLAS.
Nel Capitolo 2 è descritto il progetto Fast TracKer e sono descritte tutte le parti che lo compongono.
Nel Capitolo 3 è esposto il sistema di Memoria Associativa, oltre che una descrizione dettagliata dei principali elementi del sistema. Le principali attività e risultati del mio percorso di dottorato sono riportate in questo capitolo. In particolare, ho progettato la scheda madre chiamata AMB e le mezzanine chiamate LAMB. In questo contesto ho studiato l’interessante problema di signal integrity nel caso di alta densità di linee differenziali ad alta frequenza. Ho presentato questi risultati durante la conferenza "IEEE
Nuclear Science Symposium and Medical Imaging Conference 2015" svoltasi a San Diego, e sono stati pubblicati su un articolo sulla rivista "IEEE Transaction on Nuclear Science". Ho inoltre progettato la logica digitale, configurando gli FPGA con codice VHDL. Ho dato il mio contributo e nella progettazione del package del AM chip, e per il progetto della nuova versione del chip di memoria associativa. Alla fine del Capitolo
3 sono riportati i test, le procedure di validazione, e i risultati delle misure che ho fatto per validare il sistema prima della produzione e installazione. I risultati finali sono riportati nella sezione 3.6.3.
Nel Capitolo 4 è descritta l’infrastruttura costruita per ospitare tutto il sistema di Memoria Associativa. Dal momento che tale sistema è un processore custom con un’alta densità superficiale di potenza dissipata, abbiamo progettato dei rack dedicati e progettato delle unità di raffreddamento in modo da contenere le temperature del sistema. A tal proposito ho progettato i PCB ponendo particolare attenzione alla massimizzazione della dissipazione termica e alla limitazione della resistenza meccanica al flusso d’aria
delle ventole. Ho inoltre contribuito alle simulazioni termiche fatte per lo studio delle caratteristiche del chip, delle schede e dell’intero rack. Questi risultati sono stati presentati alla conferenza "20th IEEE Real Time Conference 2016" e il relativo articolo sarà pubblicato sulla rivista "IEEE Transaction on Nuclear Science".
Il sistema di Memoria Associativa è stato progettato e sviluppato per analizzare i dati prodotti in esperimenti di fisica delle alte energie, ma rimane un sistema con elevate potenzialità anche per applicazioni al di fuori di questo campo. Queste possibili evoluzioni e altre applicazioni sono descritte nel Capitolo 5. Ho dato il mio contributo a sviluppare tali idee e alcune applicazioni sono in fase di studio e sviluppo. I primi risultati di questi studi sono stati presentati alla conferenza "14th Vienna Conference on Instrumentation" e alla conferenza " 20th IEEE Real Time Conference 2016" e il relativo articolo verrá pubblicato sulla rivista "IEEE Transaction on Nuclear Science".