THESIS
2022
1 online resource (xii, 96 pages) : illustrations (some color)
Abstract
Sequence alignment is an essential component in genome analysis pipelines. However,
it is usually time-consuming due to the high algorithmic complexity and large data volumes.
Furthermore, recent advances in sequencing technologies and biological research
bring new challenges, such as aligning long reads and graph reference genomes. Therefore,
in this thesis, we parallelize three kinds of sequence alignment algorithms and optimize
them on heterogeneous processors.
Specifically, we first propose a long read alignment algorithm on multi-core CPUs,
Intel Xeon Phi Processors (KNL), and Graphics Processing Units (GPU). We redesign
memory layouts of dynamic programming matrices on all three processors to eliminate
data dependency and facilitate vectorization. We also exploit the full feature...[
Read more ]
Sequence alignment is an essential component in genome analysis pipelines. However,
it is usually time-consuming due to the high algorithmic complexity and large data volumes.
Furthermore, recent advances in sequencing technologies and biological research
bring new challenges, such as aligning long reads and graph reference genomes. Therefore,
in this thesis, we parallelize three kinds of sequence alignment algorithms and optimize
them on heterogeneous processors.
Specifically, we first propose a long read alignment algorithm on multi-core CPUs,
Intel Xeon Phi Processors (KNL), and Graphics Processing Units (GPU). We redesign
memory layouts of dynamic programming matrices on all three processors to eliminate
data dependency and facilitate vectorization. We also exploit the full feature set of each
processor to maximize the performance, such as high bandwidth memory of KNL and
concurrent kernel execution of GPU. Second, we propose a parallel sequence-to-graph
alignment algorithm on both the CPU and GPUs. We reduce the computational cost
of aligning frequent structures in genome graphs, design the GCSR (Genome CSR) data
structure for efficient genome graph processing on GPUs, and apply architecture-aware
optimizations to increase memory throughput. Third, we introduce a GPU-accelerated
partial order alignment algorithm. We propose to avoid dynamic memory allocation by
designing the GAL (Genome Adjacency List) graph representation, and increase parallelism
through intra-sequence parallelization.
Post a Comment