Faculté informatique et communications IC, Section d'informatique, Institut des systèmes informatiques et multimédias ISIM (Laboratoire de systèmes périphériques LSP)

Issues in petabyte data indexing, retrieval and analysis

Ponce, Sébastien ; Hersch, Roger-David (Dir.)

Thèse sciences Ecole polytechnique fédérale de Lausanne EPFL : 2006 ; no 3562.

Ajouter à la liste personnelle
    Summary
    We propose several methods for speeding up the processing of particle physics data on clusters of PCs. We present a new way of indexing and retrieving data in a high dimensional space by making use of two levels of catalogues enabling an efficient data preselection. We propose several scheduling policies for parallelizing data intensive particle physics applications on clusters of PCs. We show that making use of intra-job parallelization, caching data on the cluster node disks and reordering incoming jobs improves drastically the performances of a simple batch oriented scheduling policy. In addition, we propose the concept of delayed scheduling and adaptive delayed scheduling, where the deliberate inclusion of a delay improves the disk cache access rate and enables a better utilisation of the cluster. We build theoretical models for the different scheduling policies and propose a detailed comparison between the theoretical models and the results of the cluster simulations. We study the improvements obtained by pipelining data I/O operations and data processing operations, both in respect to tertiary storage I/O and to disk I/O. Pipelining improves the performances by approximately 30%. Using the parallelization framework developed EPFL, we describe a possible implementation of the proposed access policies, within the context of the LHCb experiment at CERN. A first prototype is implemented and the proposed scheduling policies can be easily plugged into it.
    Résumé
    Nous proposons différentes méthodes pour accélérer le traitement des données issues de la physique des particules sur des fermes de PCs. Nous présentons une nouvelle technique d'indexage et d'extraction des données dans un espace comprenant de nombreuses dimensions. Cette technique permet, par l'utilisation de deux niveaux de catalogues, de présélectionner les données efficacement. Nous proposons différents algorithmes d'ordonnancement pour les applications consommant de grandes quantités de données sur des fermes de PCs. Nous montrons que la parallélisation interne des tâches, l'utilisation de caches locaux sur les disques durs des noeuds de la ferme et la modification de l'ordre d'exécution des tâches améliorent considérablement les performances d'un algorithme classique de système de gestion de fermes de processeurs. En outre, nous proposons le concept ordonnancement différé et d'ordonnancement différé adaptatif où l'ajout délibéré d'un délai améliore le taux d'accès au cache local sur disque dur et permet une meilleure utilisation de la ferme. Nous construisons des modèles théoriques pour les différents types d'ordonnancement et nous proposons une comparaison détaillée de la théorie avec les résultats issus de simulations de fermes de processeurs. Nous étudions les améliorations obtenues par un "pipelining" des opérations d'entrées sorties et des opérations de traitement des données, aussi bien dans le cas de l'accès aux données stockées sur bandes magnétiques que dans le cas de l'accès des données stockées sur le disque dur local. Le "pipelining" améliore les performances d'environ 30%. Grâce à l'utilisation des outils de parallélisation développés à l'EPFL, nous décrivons une implémentation des différents algorithmes d'ordonnancement proposés ici dans le contexte de l'expérience LHCb au CERN. Un premier prototype a été réalisé et les différents algorithmes peuvent y être aisément intégrés.