Soutenance mémoire
Modifications à l’algorithme pour la performance et l’économie de mémoire
Depuis quelques années, on assiste à une stagnation des fréquences des puces dans les ordinateurs . Pour continuer d’augmenter la performance des puces, les fabricants se sont rabattus sur l’intégration de plusieurs processeurs dans une même puce, maintenant appelés « coeurs ». La performance disponible augmente encore à peu près linéairement, sauf que les logiciels doivent évoluer pour exploiter cette nouvelle architecture. Du même coup, le marché du matériel informatique se métamorphose. L’intérêt se déplace de la performance brute la plus élevée vers la meilleure efficacité énergétique, et ce, pour tous les domaines. Pour le commun des mortels, l’explosion de la mobilité informatique en est le plus bel exemple ; les appareils portables sont de plus en plus puissants, pour les mêmes barêmes de dissipation thermique et d’autonomie, alors que la technologie des batteries évolue plus tranquillement. Dans le monde du calcul haute performance, le mouvement est aussi présent ; on opte pour des accélérateurs de toute sorte qui ont une architecture plus adaptée à certains types de problèmes afin de diminuer la consommation électrique. Il s’agit ici de remplacer l’utilisation des processeurs centraux qui ont jusqu’à récemment fourni la majeure partie de la capacité de calcul des appareils. Parmi ces accélérateurs, on retrouve beaucoup de processeurs graphiques (GPU), qui ont acquis ces dernières années des capacités de calcul général. Plus récemment, les circuits logiques programmables (FPGA) ont fait leur entrée, alors qu’ils étaient auparavant limités à des utilisations plus particulières comme par exemple le traitement de signal et le prototypage. En juin 2015, on y retrouvait cependant aucun de ces derniers parmi les 500 super-ordinateurs les plus puissants. 90 de ceux-ci contenaient des accélérateurs autres que des FPGA, soit des processeurs graphiques NVIDIA ou AMD, ou des processeurs hautement parallèles de PEZY Computing et d’Intel.
Revue de littérature:
Assemblage d’ADN:
L’ADN est composé d’une séquence de quatre nucléotides qui se répètent sans cesse. Un chromosome est constitué d’une telle séquence ainsi que de son complément renversé ; ces deux séquences que l’on appelle des brins sont retenus par des liaisons hydrogène. Le complément renversé d’une chaîne de nucléotides consiste en le complément de chacun de ces nucléotides individuellement. Le tout est ensuite renversé, car l’ADN est parcouru toujours dans une direction spécifique pour des raisons biologiques, qui est inversée pour le brin opposé. Cette direction va de 5′ à 3′ , soit lesnoms donnés aux extrémités ; 3′ désigne l’extrémité terminée par groupement hydroxyle OH, alors que 5′ désigne l’extrémité terminée par un phosphate.
afin de comparer à mesure qu’il construit son propre résultat. Évidemment, un assemblage « de novo » est plus complexe puisqu’il consiste en plus qu’une simple question d’alignement. L’assemblage d’ADN a été complété avec différents algorithmes au fil du temps. Le premier d’entre eux est appelé le « greedy ». Il consiste à agrandir les lectures itérativement, simplement en choisissant à chaque fois le plus grand chevauchement [20]. Par la suite, un autre appelé « Overlap, Layout and Consensus » a été inventé. Comme son nom l’indique, il utilise aussi les recouvrements dans les lectures afin d’assembler le génôme [15], mais calcule aussi l’ordre et l’orientation de celles-ci. Cependant, il est moins adapté à l’assemblage de lectures courtes, de par le critère minimal de chevauchement. Une méthode plus récente dont il sera question dans ce mémoire consiste à utiliser un graphe de de Bruijn dans lequel on place des fragments de l’ADN. Un graphe de de Bruijn est un graphe orienté qui permet de représenter les chevauchements de longueur k-1 entre tous les mots de longueur k, appelés k-mers, sur un alphabet donné [8]. Cela résulte en une représentation compacte des lectures, car chaque k-mer présent dans celles-ci n’est stocké qu’une seule fois. Le nombre de fois que chacun a été aperçu est enregistré, ce qu’on appelle la couverture. Par exemple, pour une longueur de k-mer de 3 nucléotides, les lectures représentées à la figure 1.1 résulteront en cinq sommets, tous avec une couverture de 1. Ce graphe de De Bruijn est représenté à la figure 1.2. Il est finalement possible de chercher dans le graphe des chemins qu’on appelle des contigs représentant la séquence génomique orginale ou une partie de celle-ci.
Algorithme d’assemblage Ray:
Les auteurs de Ray ont vu l’opportunité de designer un nouvel assembleur dans le fait qu’aucune méthode n’avait été proposée pour réaliser un assemblage de haute qualité à partir d’un mélange des résultats de séquençage de différentes technologies, sous forme de lectures courtes. C’est ce qu’ils ont accompli, et de par la nature ouverte de Ray, ils espèrent qu’il serve comme base pour d’autres développements .
Construction du graphe
Comme mentionné dans l’introduction, Ray utilise un graphe de de Bruijn pour assembler l’ADN. Tout commence d’abord par la construction du graphe. Chaque lecture est découpée en k-mers, donc une séquence de nucléotides de longueur fixe, décidée par l’utilisateur lors du lancement du programme. Donc dans le graphe, un sommet est créé pour chaque k-mer. La longueur minimale donnant de bons résultats, déterminée par des observations expérimentales [10], est 19. Par défaut, puisque les k-mers doivent être significativement plus petits que les lectures elles-mêmes, Ray utilise une longueur de 21, pour les technologies de séquençage courantes. Il est cependant possible d’imposer une longueur différente, selon les lectures et le type de génôme qu’on souhaite assembler. La longueur des k-mers est imposée impaire, parce que, de par le fait que les nucléotides se rattachent avec leur complément renversé, cela permet de stocker les valeurs d’un brin ou de l’autre de l’ADN dans un seul sommet. Chaque k-mer de longueur k chevauche ses voisins sur k − 1 nucléotides, donc les arrêtes entre les sommets indiquent la continuation de la lecture. L’opération est répétée pour chaque lecture. Lorsqu’un k-mer est rencontré pour une deuxième fois ou plus, sa couverture est incrémentée ; il s’agit du nombre de fois que le dit k-mer a été croisé dans le lot de lectures.
Élimination des couvertures faibles
Ray, pour déterminer si les k-mers rencontrés sont fiables, se fie sur le nombre total de fois qu’ils ont été lus lors du séquençage ; ce nombre est appelé couverture. Dans l’algorithme, une couverture minimale du génôme est requise pour minimiser les erreurs et éliminer les régions répétées. En effet, il considère d’abord que tout k-mer rencontré qu’une seule fois dans le lot de lectures est une erreur.
Annotation des lectures
Lorsque tous les k-mers ont été extraits et que le graphe a été construit, Ray viendra annoter les lectures dans le graphe, car il se réfèrera à elles pour faire l’assemblage. Cette opération consiste à placer sur un seul sommet une référence vers la lecture en question. Il a été déterminé que les lectures sont plus utiles lorsqu’annotées sur un sommet unique, ce qui signifie qu’il ne fait pas partie d’une section du génôme répétée, et qu’il n’est pas erroné. Par exemple, si nous avons la lecture GCAAATAT et que le premier sommet unique est AAA, l’annotation de cette lecture sera faite sur ce dernier. Ceci permet de conserver l’information contenue dans chaque lecture, ce qui est en contraste avec les assembleurs précédents comme Velvet, où les graphes de de Bruijn sont simplifiés et l’information des lectures perdue.
Fusion des chemins
La dernière étape consiste à fusionner les chemins déterminés à l’étape précédente. Cela est nécessaire car ils sont stockés séparément, puis des semences peuvent avoir fait débuter deux extensions qui en réalité sont contiguës. Ray exige un chevauchement minimal entre les chemins de 2000 paires de base, qui pourrait ne pas être respecté si par exemple les deux chemins sont différents. Cela pourrait être expliqué par le fait qu’ils n’ont pas été construits avec les mêmes lectures.
Accélération matérielle:
Modèle de mémoire
Un modèle de mémoire fait partie du standard et est adopté par toutes les implémentations. Dans celui-ci, on retrouve d’abord la mémoire hôte, soit la mémoire principale, accessible par le processeur central, laquelle est utilisée pour l’exécution du programme hôte. Ensuite, du côté de la plateforme d’exécution, il y a la mémoire globale. Celle-ci est accessible à tous moments, de n’importe où. Puis, il y a la mémoire locale. Celle-ci est commune à tous les éléments de travail dans un même groupe de travail. Puis, une mémoire privée à chacune de ces unités est aussi présente. Finalement, il y a aussi une mémoire constante pour les données qualifiées comme tel. Le tout est illustré à la figure 1.8. C’est au manufacturier de l’appareil conforme OpenCL d’implémenter chaque mémoire à sa guise, mais typiquement, en terme de bande passante, la mémoire globale est la plus lente, alors que la mémoire privée est la plus rapide. La latence et la capacité sont inversement proportionelles.
Flux de travail
Le flux de travail OpenCL consiste en trois principales étapes. D’abord, des tampons de grosseur appropriée sont alloués et remplis dans la mémoire globale de l’appareil. Puis, l’exécution du code OpenCL, appelé kernel, a lieu. Finalement, les données résultantes sont récupérées. Dans le cas d’un appareil ayant une mémoire globale distincte de la mémoire hôte, les données doivent être copiées ; c’est l’hôte qui commande un transfert de sa mémoire centrale à celle de l’accélérateur, souvent en utilisant un accès direct à la mémoire (DMA) pour alléger ce lourd travail. Dans le cas d’un accélérateur ayant une mémoire unifiée avec celle de l’hôte, les tampons originaux peuvent être utilisés tels quels. Le délai d’attente après le transfert des données n’a pas lieu. C’est le cas, par exemple, lors de l’exécution OpenCL sur un processeur central, qui peut aussi jouer le rôle d’accélérateur en même temps qu’hôte.
Types de kernels
OpenCL permet deux types de kernels fondamentalement différents. Ils consistent en une tâche, ou une plage d’exécution de dimension N. Le premier type exécute la série d’instructions fournies de manière séquentielle et une seule fois, tandis que le deuxième l’exécute pour chaque élément de la plage d’exécution, pour chaque dimension. Dans ce cas, un groupe de travail peut occuper une plage non unitaire sur une ou plusieurs dimensions.
Accélérations précédentes
Les possibilités d’accélération pour des algorithmes en particulier ont déjà été prouvées à maintes reprises. Dans le domaine de la bioinformatique, l’algorithme de Smith-Waterman a fait l’objet de plusieurs recherches, utilisant notamment les unités de traitement vectoriel des microprocesseurs récents ainsi que les accélérateurs de type GPU et FPGA. Cet algorithme est utilisé pour l’alignement de séquences biologiques, testant des segments de toutes les longueurs possibles. Les résultats obtenus pour une implémentation OpenCL sur FPGA laissent entendre une amélioration de la performance absolue d’un facteur de 9.9 et de l’efficacité énergétique d’un facteur de 26 par rapport à l’implémentation sur microprocesseur.
Types d’accélérateurs compatibles:
Processeurs classiques ou centraux:
Le processeur classique est utilisé en tant qu’hôte dans le système compatible OpenCL. Cependant, il peut en même temps jouer le rôle d’accélérateur. Tel qu’expliqué en 1.3.1, chaque coeur est alors une unité de calcul. La correspondance entre l’architecture logique OpenCL et l’architecture réelle est directe, comme par exemple pour la puce présentée à la figure 2.1, dans laquelle on retrouve huit unités de calcul. Parmi celles-ci, il est possible d’utiliser le traitement vectoriel pour traiter plusieurs éléments en parallèle à l’aide de jeux d’instruction tels AVX-256.
Circuits logiques programmables:
Les circuits logiques programmables sont de nouveaux venus dans la liste des appareils compatibles OpenCL. Autrement, leur programmation requiert un langage de description matérielle (HDL) tel que le VHDL ou le Verilog. Ceux-ci requièrent à l’utilisateur d’avoir une certaine expertise en architecture matérielle pour pouvoir générer des circuits traitant le problème de façon optimale. En OpenCL, c’est le compilateur et l’optimiseur qui s’occupent de générer une architecture adéquate selon les instructions à exécuter, indiquées en C. Le programmeur n’a qu’à respecter un certain nombre de règles, sans quoi le compilateur et l’optimiseur se voient imposer des contraintes. Par exemple, il est dit que le traitement de données en point flottant ainsi que la division et le modulo d’entiers sont très coûteux en terme de logique utilisée dans le FPGA. L’arithmétique sur des pointeurs ainsi que les fonctions atomiques sont également à éviter [1]. Il y a aussi quelques bonnes pratiques à respecter pour optimiser les accès à la mémoire. Pour le reste, le SDK OpenCL promet des performances souvent meilleures qu’une architecture codée en HDL, un temps de développement moindre et aussi un code portable qui pourra être migré à de plus récents FPGA automatiquement .
Conclusion:
Ce mémoire a examiné l’utilisation d’accélérateurs basés sur des FPGA afin d’accomplir des problèmes d’assemblage d’ADN, ainsi que leur comparaison avec les processeurs centraux. Des généralisations ont été tirées quant aux résultats obtenus. Les notions de base d’assemblage d’ADN ainsi que la provenance des données, soit le séquençage, ont été introduites. Les quelques algorithmes d’assemblage développés au fil du temps ont été présentés. Puis, celui qui a été à l’étude dans ce mémoire a été approfondi. Chaque étape a ainsi été décrite en détails. Par la suite, la méthode d’accélération adoptée pour ce projet ainsi que son fonctionnement et ses outils ont été discutés. Les quelques travaux ayant comme sujet l’accélération matérielle des algorithmes d’assemblage ont finalement été présentés pour clore la revue de littérature.
|
Table des matières
Introduction
1 Revue de littérature
1.1 Assemblage d’ADN
1.2 Algorithme d’assemblage Ray
1.3 Accélération matérielle .
2 Types d’accélérateurs compatibles
2.1 Processeurs classiques ou centraux
2.2 Processeurs graphiques
2.3 Circuits logiques programmables
2.4 Consommation énergétique
2.5 Mémoire hétérogène unifiée
2.6 Support OpenCL chez Xilinx
3 Parallélisation
3.1 Parallélisation originale
3.2 Parallélisation OpenCL
3.3 Modifications à l’algorithme pour la performance et l’économie de mémoire
3.4 Partitionnement du problème
4 Résultats
4.1 Montage de test
4.2 Temps d’exécution
4.3 Consommation énergétique
4.4 Effet du taux d’occupation du graphe
4.5 Discussion
Conclusion
Télécharger le rapport complet
