Parallelisation of algorithms is necessary in order increase their speed on modern microprocessors. Since the clock rate has stalled at around about 3-4 GHz, many processors now have multiple cores on the same chip to increase performance further. Intel have launched processors with 12 advanced x86-64 cores (Xeon) as well as the Xeon Phi processor with 61 cores, while Nvidia and others have produced Graphics Processors (GPUs) with hundreds or thousands of simple cores that can be programmed e.g. using CUDA. Furthermore, SIMD technology (Single Instruction Multiple Data) is available in many processors. For example, the recently introduced "Haswell" processors have up to 256 bit wide registers that can be operated using the AVX and AVX2 instruction set extensions allowing operations to be performed on 32 individual bytes simultaneously. Large clusters of computers, for example the Abel cluster at the University of Oslo, can also be used for large-scale computations with nodes communicating with MPI. To exploit the parallel computing technology properly so that programs runs as fast as possible it is always necessary that algorithms are parallelised efficiently and that programs are adapted to the hardware by taking important things like communication overhead and memory/cache sizes and speeds into account.
In bioinformatics, there are many algorithms that are time consuming and where it will be useful with efficient parallelization. Different varieties of algorithms for comparisons of DNA or protein sequences, sequence profiles / motifs, or protein structures are potential candidates. Different types of searches in databases, as well as construction of phylogenetic trees are also relevant.
The aim of the project is to select and look into an actual algorithm, find out how it can best be parallelized, implement it, and evaluate the results.
The project is suitable for anyone interested in bioinformatics and has some programming experience, preferably with parallelization in one form or another.
Supervisor: Torbjørn Rognes (BMI/IFI)