Browsing by Subject "GPU"

This thesis examines the implementation of general purpose graphics processing unit (GPGPU) acceleration to a non-equilibrium Green’s function (NEGF) equation solver in the context of a computational photoelectrochemical (PEC) cell model. The goal is to find out whether GPGPU acceleration of the NEGF equation solver is a viable option. The current model does not yet have electron-photon scattering, but from the results it is possible to assess the viability of GPGPU acceleration in the case of a complete PEC cell model. The viability of GPGPU acceleration was studied by comparing the performance difference of two graphics processing unit (GPU) solutions against a multi core central processing unit (CPU) solution. The difference between the two GPU solutions was in the used floating-point precision. The GPU solutions would use LU factorization to solve the NEGF equations, and the CPU solution a banded solver (Gauss tridiagonal) provided by Scipy Python package. The performance comparison was done on multiple different GPU and CPU hardware. The electrical transport properties of the PEC cell were modeled by a self-consistent process in which the NEGF and Poisson equations were solved iteratively. The PEC cell was described as a semiconductor device connected with a metal and electrolyte contacts. The device was assumed to be a simple one dimensional tight-binding atom chain made of GaAs, where the transverse modes in the y–z plane are treated with a logarithmic function. The computational model did lack electron-photon scattering, which would be implemented in the future. From the benchmark results, it can be concluded that the GPGPU acceleration via LU factorization is not a viable option in the current code or in the complete model with electron-photon scattering and the assumed approximations. The parallel multi-core CPU code generally outperformed the GPU codes. The key weakness of the GPU code was the usage of LU factorization. Despite of this, there could be an opportunity for GPGPU acceleration if a more complex lattice structure and more exact scattering terms would be used. Also, a GPU accelerated tridiagonal solver could be a possible solution.

Alignment in genomics is the process of finding the positions where DNA strings fit best with one another, that is, where there are the least differences if they were placed side by side. This process, however, remains very computationally intensive, even with more recent algorithmic advancements in the field. Pseudoalignment is emerging as a new method over full alignment as an inexpensive alternative, both in terms of memory needed as well as in terms of power consumption. The process is to instead check for the existence of substrings within the target DNA, and this has been shown to produce good results for a lot of use cases. New methods for pseudoalignment are still evolving, and the goal of this thesis is to provide an implementation that massively parallelises the current state of the art, Themisto, by using all resources available. The most intensive parts of the pipeline are put on the GPU. Meanwhile, the components which run on the CPU are heavily parallelised. Reading and writing of the files is also done in parallel, so that parallel I/O can also be taken advantage of. Results on the Mahti supercomputer, using an NVIDIA A100, shows a 10 times end-to-end querying speedup over the best run of Themisto, using half the CPU cores as Themisto, on the dataset used in this thesis.

The volume of data generated by high-throughput DNA sequencing has grown to a magnitude that leads to substantial computational challenges in storing and searching the data. To tackle this problem, various computational methodologies have been developed in recent years to space-efficiently index collections of data sets and enable efficient searches. One of the most recent indexing methods, Spectral Burrows-Wheeler Transform (SBWT), presents all distinct k-mers of a DNA sequence using only 4 bits and a small additional space for the rank data structures per k-mer. In addition to being space-efficient, it also enables k-mer membership queries in linear time relative to k, and constant time relative to the number of distinct k-mers in the sequence. The queries rely on rank queries over bit vectors. Experiments run on a single CPU thread have shown that in one second, hundreds of thousands of k-mer membership queries can be performed over SBWT. By parallelizing the queries on a CPU, it is possible to execute millions of queries per second. However, Graphic Processing Units (GPUs) have much more parallelization potential. The main contribution of the thesis is an implementation of the k-mer membership queries over SBWT with GPU computing. Optimizing the queries to be performed on a GPU made it possible to perform over a billion queries per second. Furthermore, the thesis presents a new enhancement for the queries over SBWT called presearching, which doubles the speed of the original SBWT search query. The rank query needed for the membership queries is implemented using space-efficient poppy rank data structures, and its derivative cumulative-poppy data structure which is one of the contributions of the thesis.