Parallelization of algorithms is necessary in order increase their speed on modern architectures. Since the clock rate has stalled at around about 3-4 GHz, processors now have multiple cores on the same chip to increase performance further. Intel have launched processors with up to 22 advanced x86-64 cores (Xeon) as well as the Xeon Phi processor (Knights Landing) with up to 72 cores, while Nvidia and others have produced Graphics Processors (GPUs) with thousands of simple cores that can be programmed using CUDA. Furthermore, SIMD technology (Single Instruction Multiple Data) is available in many processors. For example, the Haswell and later 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. Xeon Phi supports 512 bit wide registers using AVX-512. Large clusters of computers, for example the Abel cluster at the University of Oslo, can also be used for large-scale computations with a large number of 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 parallelized 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 or searching involving DNA or protein sequences, sequence profiles / motifs, k-mer counts, genome coordinates, or protein structures are some potential candidates.
The aim of the project is to select and look into an actual algorithm, find out how it can best be parallelised, implement it, and evaluate the results compared to other software.
The project is suitable for anyone interested in bioinformatics and has considerable programming experience, preferably with parallelization in one form or another.
Supervisor: Torbjørn Rognes (BMI/IFI)