Adaptive Scheduling Applied to Non-Deterministic Networks of Heterogeneous Tasks for Peak Throughput in Concurrent Gaudi

As much the e-Science revolutionizes the scientific method in its empirical research and scientific theory, as it does pose the ever growing challenge of accelerating data deluge. The high energy physics (HEP) is a prominent representative of the data intensive science and requires scalable high-throughput software to be able to cope with associated computational endeavors. One such striking example is Gaudi – an experiment independent software frame work, used in several frontier HEP experiments. Among them stand ATLAS and LHCb – two of four mainstream experiments at the Large Hadron Collider (LHC) at CERN, the European Laboratory for Particle Physics. The framework is currently undergoing an architectural revolution aiming at massively concurrent and adaptive data processing. In this work I explore new dimensions of performance improvement for the next generation Gaudi. I then propose a complex of generic task scheduling solutions for adaptive and non-intrusive throughput maximization in multithreaded task-based realization of Gaudi. Firstly, I present the reactive graph-based concurrency control system for low latency and scalable task precedence resolution in unpredictable data processing conditions. Secondly, I demonstrate the outstanding potential of the proactive task scheduling approach that employs the technique of induced avalanche concurrency leveling for throughput maximization in conditions of tight task precedence constraints. Finally, I investigate the synergy of latency oblivious task scheduling and controlled oversubscription of central processors. I prove a significant potential of this merger for throughput maximization in general and for adoption of the paradigm of heterogeneous computing in the context of Gaudi in particular. I exemplify all ideas in the LHCb event reconstruction scenario.

Come la e-Science rivoluziona il metodo scientifico nella sua ricerca empirica e teoria scientifica, altrettanto pone una crescente sfida per l'accelerato flusso di dati prodotto. La fisica delle alte energie (HEP, High Energy Physics) è un rappresentante prominente di scienza che usa grandi quantità di dati, e richiede software scalabile e con un alto throughput per essere in grado di sostenere le richieste computazionali associate. Uno spiccato esempio è Gaudi, un framework software indipendente dall'esperimento usato da molti esperimenti di HEP. Tra questi ci sono ATLAS ed LHCb, due dei quattro esperimenti principali presso il Large Hadron Collider (LHC) del CERN, il Laboratorio Europeo per la Fisica delle Particelle. Gaudi è attualmente oggetto di una rivoluzione architetturale mirata al processamento massivamente concorrente e adattivo dei dati. In questo lavoro esploro le nuove dimensioni del miglioramento delle performance per la prossima generazione di Gaudi. Propongo quindi un complesso di soluzioni di scheduling dei task per la massimizzazione adattiva e non intrusiva del throughput nell'implementazione concorrente di Gaudi basata su task multithread. Inizialmente presento un sistema di controllo della concorrenza, reattivo e basato su grafi, per la risoluzione della precedenza dei task, con bassa latenza e scalabile in condizioni non predicibili di processamento dei dati. In seconda istanza, dimostro l'eccezionale potenziale dello scheduling proattivo dei task, che utilizza tecniche di livellamento della concorrenza attraverso l'induzione di valanghe di task, per massimizzare il throughput in condizioni di regole di precedenza stringenti. Infine, investigo la sinergia di uno scheduling dei task che ignora la latenza con una oversubscription controllata dei processori centrali. Dimostro che questa combinazione ha un potenziale significativo per la massimizzazione del throughput in generale e in particolare per l'adozione del paradigma del computing eterogeneo nell'ambito di Gaudi. Tutte le idee sono supportate da esempi basati sulla ricostruzione di eventi di LHCb.