Stage de recherche, été 2007

Architecture systolique programmable génome sur puce

Mathieu Giraud (www), équipe Bioinfo - Sequoia
Philippe Marquet (www), équipe West - Dart
LIFL / INRIA Futurs - bâtiment M3
giraud[AT]lifl[DOT]fr, marquet[AT]lifl[DOT]fr

Thèmes : architecture et bio-informatique

Connaissances préalables : cours d'architecture des ordinateurs

Contexte scientifique

Les recherches de motif sont fréquentes en bio-informatique pour comparer des modèles connus avec des séquences inconnues. Rechercher un motif, c'est trouver dans un long texte (par exemple un génome) toutes les occurences d'un mot (ATTACTCT), éventuellement avec des erreurs de substitution, d'insertion et de délétion. On peut aussi rechercher des automates, des motifs pondérés, des motifs exprimés par des grammaires (V-ATTCCT-V avec |V| = 5). En général, une recherche de motif est définie par un langage donnant tous les mots qui doivent être reconnus à l'intérieur d'un génome [2].

Une architecture systolique est un réseau de cellules similaires ou identiques dans lequel les données circulent de façon synchrone et selon un cheminement fixé [3]. On trouve des modèles d'architectures recherchant un grand nombre de motifs. Dès les années 1980, des réseaux systoliques programmables ont été proposés. Le calcul effectué par chaque cellule, la transmission des données voire la topologie du réseau se reprogramment statiquement ou dynamiquement [1]. Ces études n'ont pas encore été systématiquement appliquées aux recherches de motifs en bio-informatique.

Sujet de stage

Le but du stage est de contribuer à une architecture génome sur puce s'inspirant des architectures systoliques programmables. Vu les possibilités actuelles d'intégration, il est possible de mettre plusieurs milliers à plusieurs centaines de milliers de cellules élémentaires sur un composant. Idéalement, un génome entier tient sur la puce, et le motif est envoyé (systoliquement ou avec une diffusion générale) à chaque cellule : à la latence près, les recherches de motifs sont exécutées quasi instantanément. En pratique, pour explorer des génomes comprenant des milliards de bases, on utilisera une mémoire rapide changeant le contenu des cellules. Concrètement, les objectifs du stage sont :

• une étude bibliographique sur les architectures systoliques programmables,
• la proposition de plusieurs cellules génériques, avec une étude de l'expressivité des motifs reconnus, de la surface utilisée et de la vitesse de traitement (FPGA ou ASIC).
• la programmation par simulation de ces cellules en utilisant SystemC [4], pour obtenir une validation fonctionnelle et temporelle.

Enfin, si ces objectifs sont atteints, on envisagera une utilisation réelle sur l'architecture prototype ReMiX, en collaboration avec l'équipe Symbiose de l'IRISA (Rennes).

Références bibliographiques

1. Kurtis T. Johnson, A.R. Hurson, Behrooz Shirazi, General-Purpose Systolic Array, Computer, 26(11):30--31, 1993
2. Dominique Lavenier, Mathieu Giraud, Reconfigurable Computing, chapter Bioinformatics Applications, Springer, 2005
3. Patrice Quinton, Yves Robert, Algorithmes et architectures systoliques, Masson, 1989