Bellek-içi-işlem sistemi üzerinde dizi-çizge hizalaması

Genome graphs are used to represent the genetic information and variation of a population rather than a single individual. The sequence-to-graph alignment (SGA) problem can be defined as finding the best match between a query sequence and a genome graph. SGA algorithms are expected to suffer from a memory bottleneck due to the irregularity of graph representation, and benchmarks confirm more than 50% memory boundness found in some applications. Therefore, the SGA 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 transfers 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 for much faster and energy-efficient memory access. Our contribution includes SEGAPIM, the design of a pipeline that partitions and distributes a genome graph across DPUs, directs short reads to the relevant DPUs according to their seed locations, and performs alignment solutions within DPUs. Although these distribution and routing components are part of the envisioned full system, the implemented portion of our work focuses on calculating alignment scores for each seed of each read using an adaptation of the graph wavefront alignment algorithm (GWFA) under very limited memory, followed by collecting and finalizing the results on the host CPU. We present comparisons for accuracy and run-time of our implementation to state-of-the-art tools such as vg and GraphAligner, and conclude that the PIM architecture at hand provides a promising speed-up and energy-saving for the SGA problem.