Mathieu Giraud (www), Jean-Stéphane Varré (www), Sequoia bioinformatics team
LIFL / INRIA Lille Nord-Europe
giraud [@] lifl.fr, 03 59 57 79 13
varre [@] lifl.fr, 03 59 57 79 18
Themes: GPGPU, computational biology, bit-parallelism algorithms
Fixed term period: 3 to 6 months (with salary). Start in 2009. Open to any applicant.
Requirements: knowledge in computer architecture, some knowledge in CUDA programming will be appreciated, no knowledge in bioinformatics required.
The GPU technology allows everyone to have some teraflops of cheap computing power. Librairies like CUDA or OpenCL make the programmation of such devices very convenient. However, good speed-ups are achieved only with a good knowledge of the parallel architecture.
The aim of the internship is to study pattern matching algorithms used in computanional biology, taking advantage of both bit-parallelism paradigm and multi-core execution with GPU. Bit-parallelism is a technique that uses logical operators as parallel operators in order to speed up pattern matching algorithms. A 32 bits or 64 bits processor can therefore be viewed as many small processors able to make 32 or 64 operations in parallel. Using this technique within each processor of a graphic card should allow tens of tera-operations per second. Thissshould lead to the design of very efficient algorithms able to look for complex patterns at a genome scale.
The work will begin with a bibliograpgic study of bit-parallelism algorithms with a technological survey about GPU. Depending on the applicant, we will develop an library of open-source operators or we will study more formally how to design specific algorithms dedicated to be implemented onto multi-core processors. In both cases, the student will have to acquire a deep understanding of the architecture.