Bilkent University
Department of Computer Engineering
M.S.THESIS PRESENTATION
Sequence-to-Graph Alignment on a Processing-In-Memory System
Ömer Yavuz Öztürk
Master Student
(Supervisor: Assoc.Prof.Can Alkan)
Computer Engineering Department
Bilkent University
Abstract: Genome graphs are used to represent the genetic information and variation of a population rather than a single individual. Sequence-to- graph (S2G) alignment problem can be defined as finding the best match between a query sequence and a genome graph. S2G algorithms are expected to suffer from memory bottleneck due to the irregularity of graph representation, and benchmarks confirm over 50% memory-boundness found in some applications. Therefore, S2G alignment problem can benefit from processing-in-memory (PIM) technologies. PIM is an upcoming non-von Neumann architecture that allows computing near the main memory without the need to utilize the memory bus for data transfer to the CPU and back. One of the currently available PIM technologies developed by UPMEM is an architecture consisting of thousands of DPUs (DRAM Processing Units) that allow much faster and energy-efficient memory access. Our contribution includes implementing a lossless partition of the genome graph across DPUs, efficiently directing queries to relevant DPUs according to their seed locations, calculating the alignment score for each seed of each query, and then gathering and finalizing the results in the host CPU. We present comparisons for accuracy and run-time of our implementation to state- of-the-art tools, and conclude that PIM architecture at hand provides a promising speed-up for the S2G alignment problem.
DATE: September 16, Tuesday @ 11:00 Place: EA 409