Machines de correspondances en temps réel reconfigurables

Description

Des techniques telles que la cryptographie, la réception GPS ou l’alignement de l’ADN ont en commun la nécessité de rechercher une relation particulier dans une séquence. La vitesse de ces moteurs de correspondances peut être limitée par le nombre de requêtes ou des variations d’une référence. Cela est particulièrement le cas pour une analyse d’ADN pris en charge par des grandes bases de données lors de la recherche de possibles mutations. Les algorithmes de recherche de correspondances dans des chaines de caractères, nécessaires pour les systèmes de détection des instructions du réseau, sont un exemple de base, où la vitesse de traitement, le parallélisme et le débit sont obligatoires. Les algorithmes déterministes et non-déterministes sont généralement nécessaires, en particulier, lorsque la longueur de la cible varie. Les besoins en mémoire, les mutations ou l’évolutivité peuvent également affecter la capacité de traitement parallèle. La taille de l’automate à charge du moteur de correspondances peut croître de façon exponentielle en fonction du nombre de transitions, affectant également la vitesse de traitement. Dans ce contexte, l’objectif de cette thèse est de fournir des algorithmes et des architectures combinées pour fournir des moteurs de correspondances de faible latence, capables, en temps réel, de traiter en parallèle plusieurs requêtes de longueur variable avec des ressources mémoire limitées et une consommation d’énergie réduite. La première contribution sera l’évaluation des algorithmes existants pour traiter plusieurs mots clés simultanément en termes de débit, de besoins en mémoire et de consommation d’énergie lorsqu’ils sont exécutés par des architectures multi-cœurs et GPU. La deuxième contribution sera la proposition d’un algorithme de moteur capable d’augmenter le débit, le traitement parallèle et les exigences de mémoire. La troisième contribution sera la proposition d’une architecture dédiée, un IP (propriété intellectuelle) matériel traitant plusieurs requêtes en parallèle pour être proposé en tant que composant pour les générations futures de plates-formes SoC (System on Chip). La dernière contribution envisagée sera d’automatiser la génération des moteurs sur basé des mots-clés et des requêtes définies.