Abstract:
Genome sequence analysis plays a pivotal role in enabling many medical and scientific advancements in personalized medicine, outbreak tracing, the understanding of evolution, and forensics. Modern genome sequencing machines can rapidly generate massive amounts of genomics data at low cost. However, the analysis of genome sequencing data is currently bottlenecked by the computational power and memory bandwidth limitations of existing systems, as many of the steps in genome sequence analysis must process a large amount of data. Moreover,  as sequencing technologies advance,  the growth in the rate that sequencing devices generate genomics data is far outpacing the corresponding growth in computational power, placing greater pressure on these bottlenecks.

In this seminar, we provide an overview of our four works, where we characterize the real-system behavior of the genome sequence analysis pipeline and its associated tools, expose the bottlenecks and tradeoffs of the pipeline and tools, and co-design fast and efficient algorithms along with scalable and energy-efficient customized hardware accelerators for the key pipeline bottlenecks to enable faster genome sequence analysis.

First, we comprehensively analyze the tools in the genome assembly pipeline for long reads in multiple dimensions (i.e., accuracy, performance, memory usage, and scalability), uncovering bottlenecks and tradeoffs that different combinations of tools and different underlying systems lead to. We show that we need high-performance, memory-efficient, low-power, and scalable designs for genome sequence analysis in order to exploit the advantages that genome sequencing provides. Second, we propose GenASM, an acceleration framework that builds upon bitvector-based approximate string matching (ASM) to accelerate multiple steps of the genome sequence analysis pipeline. We co-design our highly parallel, scalable, and memory-efficient algorithms with low-power and area-efficient hardware accelerators. We evaluate GenASM for three different use cases of ASM in genome sequence analysis and show that GenASM is significantly faster and more power- and area-efficient than state-of-the-art software and hardware tools for each of these use cases. Third, we implement an FPGA-based prototype for GenASM, where state-of-the-art 3D-stacked memory (HBM2) offers high memory bandwidth and FPGA resources offer high parallelism by instantiating multiple copies of the GenASM accelerators. Fourth, we propose SeGraM, the first hardware acceleration framework for sequence-to-graph mapping and alignment. Instead of representing the reference genome as a single linear DNA sequence, genome graphs provide a better representation of the diversity among populations by encoding variations across individuals in a graph data structure, avoiding a bias towards any one reference. SeGraM enables the efficient mapping of a sequenced genome to a graph-based reference, providing more comprehensive and accurate genome sequence analysis. For SeGraM, we co-design algorithms and accelerators for memory-efficient minimizer-based seeding and bitvector-based, highly-parallel sequence-to-graph alignment. Compared to state-of-the-art software tools for sequence-to-graph mapping and alignment, we show that SeGraM significantly increases the throughput and reduces the power consumption for both short and long reads.

Overall, we demonstrate that genome sequence analysis can be accelerated by co-designing scalable and energy-efficient customized accelerators along with efficient algorithms for the key steps of genome sequence analysis. We hope that this seminar inspires future work in co-designing algorithms and hardware together to create powerful frameworks that accelerate other genomics workloads and emerging applications.

Speaker Bio:
Damla Senol Cali received her Ph.D. degree in Computer Engineering from SAFARI Research Group at Carnegie Mellon University, where she was advised by Prof. Onur Mutlu and Prof. Saugata Ghose. Her research focuses on hardware/software co-design for accelerating bioinformatics applications and computational methods for bioinformatics applications and genomic data analysis. She is also excited about memory systems and processing-in-memory. During her Ph.D., she also interned at Intel Labs in 2018 and 2020. She obtained her M.S. in Computer Engineering from Carnegie Mellon University in 2019, and her B.S. in Computer Engineering from Bilkent University in 2015. Currently, she is working at Bionano Genomics as a “Staff Software Engineer, Hardware Acceleration”.

Personal Website: https://damlasenolcali.github.io
LinkedIn: https://www.linkedin.com/in/damlasenolcali/

Related Papers:

Damla Senol Cali, Gurpreet S. Kalsi, Zulal Bingol, Can Firtina, Lavanya Subramanian, Jeremie S. Kim, Rachata Ausavarungnirun, Mohammed Alser, Juan Gomez-Luna, Amirali Boroumand, Anant Nori, Allison Scibisz, Sreenivas Subramoney, Can Alkan, Saugata Ghose, and Onur Mutlu, “GenASM: A High-Performance, Low-Power Approximate String Matching Acceleration Framework for Genome Sequence Analysis”
Proceedings of the 53rd International Symposium on Microarchitecture (MICRO), Virtual, October 2020.
[Slides (pptx) (pdf)]
[Short Talk Slides (pptx) (pdf)]
[Lightning Talk Slides (pptx) (pdf)]
[ARM Research Summit Talk Slides (pptx) (pdf)]
[ARM Research Summit Short Talk Slides (pptx) (pdf)]
[Lecture Slides (pptx) (pdf)
[MICRO 2020 Talk Video (18 minutes)]
[MICRO 2020 Short Talk Video (6 minutes)]
[MICRO 2020 Lighting Talk Video (1.5 minutes)]
[ARM Research Summit Talk Video (21 minutes)]
[ARM Research Summit Short Talk Video (15 minutes)]
[ARM Research Summit Short Talk Video and Q&A (31 minutes)]
[Lecture Video (37 minutes)]
[GenASM Source Code]

Damla Senol, Jeremie Kim, Saugata Ghose, Can Alkan, and Onur Mutlu, “Nanopore Sequencing Technology and Tools for Genome Assembly: Computational Analysis of the Current State, Bottlenecks and Future Directions”
Briefings in Bioinformatics (BIB), 2018.
[Open arxiv.org version]
[Slides (pptx) (pdf)]
[Talk Video at AACBB 2019]

On Damla’s homepage:

https://damlasenolcali.github.io/publication/genasm/   

https://damlasenolcali.github.io/publication/nanopore/

Other Talks:

Research Summary Talk, “Accelerating Genome Sequence Analysis via Efficient Hardware/Algorithm Co-Design”: https://youtu.be/1VUOL5SL1MM

SAFARI January 2021 Newsletter, Interview with Damla Senol Cali: https://youtu.be/bXtaxL_YGMs

Abstract:
There is an explosive growth in the size of the input and/or intermediate data used and generated by modern and emerging applications. Unfortunately, modern computing systems are not capable of handling large amounts of data efficiently. Major concepts and components (e.g., the virtual memory system) and predominant execution models (e.g., the processor-centric execution model) used in almost all computing systems are designed without having modern applications’ overwhelming data demand in mind. As a result, accessing, moving, and processing large amounts of data faces important challenges in today’s systems, making data a first-class concern and a prime performance and energy bottleneck in such systems. In this seminar, we study the root cause of inefficiency in modern computing systems when handling modern applications’ data demand, and introduce fundamental solutions to address such inefficiencies, with a focus on two directions.

First, we introduce a new framework that aids the widespread adoption of processing-using-DRAM, a data-centric computation paradigm that improves the overall performance and efficiency of the system when computing large amounts of data by minimizing the cost of data movement and enabling computation where the data resides. To this end, we introduce SIMDRAM, an end-to-end processing-using-DRAM framework that (1) efficiently computes complex operations required by modern data intensive applications, and (2) provides the ability to implement new arbitrary operations as required, all in an in-DRAM massively-parallel Single Instruction Multiple Data (SIMD) substrate that requires minimal changes to the DRAM (Dynamic Random Access Memory) architecture.

Second, we introduce a new, more scalable virtual memory framework that (1) eliminates the inefficiencies of the conventional virtual memory frameworks when handling the high memory demand in modern applications, and (2) is built from the ground up to understand, convey, and exploit data properties, to create opportunities for performance and efficiency improvements. To this end, we introduce the Virtual Block Interface (VBI), a novel virtual memory framework that (1) efficiently handles modern applications’ high data demand, (2) conveys properties of different pieces of program data (e.g., data structures) to the hardware and exploits this knowledge for performance and efficiency optimizations, (3) better extracts performance from the wide variety of new system configurations that are designed to process large amounts of data (e.g., hybrid memory systems), and (4) provides all the key features of the conventional virtual memory frameworks, at low overhead.

Speaker Bio:
Nastaran Hajinazar received her Ph.D. degree in Computer Science from Simon Fraser University, Canada, and is an affiliated researcher in the SAFARI research group at ETH Zürich. Nastaran’s research incorporates several aspects of computing systems and architectures, including data-centric computing architectures and data-aware memory management techniques for optimizing the performance, bandwidth, throughput, memory utilization, and energy efficiency of computing systems when handling the increasingly large amounts of data in modern applications. Her current research also lies in the areas of hardware/software co-design, and memory security.

Link to Thesis:
https://arxiv.org/abs/2109.05881
https://safari.ethz.ch/phd-theses/

Major Papers:

Nastaran Hajinazar, Geraldo F. Oliveira, Sven Gregorio, Joao Dinis Ferreira, Nika Mansouri Ghiasi, Minesh Patel, Mohammed Alser, Saugata Ghose, Juan Gomez-Luna, and Onur Mutlu, “SIMDRAM: An End-to-End Framework for Bit-Serial SIMD Computing in DRAM”, Proceedings of the 26th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), Virtual, March-April 2021.
[2-page Extended Abstract]
[Short Talk Slides (pptx) (pdf)]
[Talk Slides (pptx) (pdf)]
[Short Talk Video (5 mins)]
[Full Talk Video (27 mins)]

Nastaran Hajinazar, Pratyush Patel, Minesh Patel, Konstantinos Kanellopoulos, Saugata Ghose, Rachata Ausavarungnirun, Geraldo Francisco de Oliveira Jr., Jonathan Appavoo, Vivek Seshadri, and Onur Mutlu,
“The Virtual Block Interface: A Flexible Alternative to the Conventional Virtual Memory Framework”
Proceedings of the 47th International Symposium on Computer Architecture (ISCA), Valencia, Spain, June 2020.
[Slides (pptx) (pdf)]
[Lightning Talk Slides (pptx) (pdf)]
[ARM Research Summit Poster (pptx) (pdf)]
[Talk Video (26 minutes)]
[Lightning Talk Video (3 minutes)]
[Lecture Video (43 minutes)]

Amirali Boroumand, Saugata Ghose, Minesh Patel, Hasan Hassan, Brandon Lucia, Rachata Ausavarungnirun, Kevin Hsieh, Nastaran Hajinazar, Krishna T. Malladi, Hongzhong Zheng, and Onur Mutlu,
“CoNDA: Efficient Cache Coherence Support for Near-Data Accelerators”
Proceedings of the 46th International Symposium on Computer Architecture (ISCA), Phoenix, AZ, USA, June 2019.
[Slides (pptx) (pdf)]
[Lightning Talk Slides (pptx) (pdf)]
[Poster (pptx) (pdf)]
[Lightning Talk Video (4 minutes)] 

Saugata Ghose, Tianshi Li, Nastaran Hajinazar, Damla Senol Cali, and Onur Mutlu,
“Demystifying Workload–DRAM Interactions: An Experimental Study”
Proceedings of the ACM International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS), Phoenix, AZ, USA, June 2019.
[Preliminary arXiv Version]
[Abstract]
[Slides (pptx) (pdf)]
[MemBen Benchmark Suite]
[Source Code for GPGPUSim-Ramulator]
[Source Code for Ramulator modeling Hybrid Memory Cube (HMC)]

Nandita Vijaykumar, Abhilasha Jain, Diptesh Majumdar, Kevin Hsieh, Gennady Pekhimenko, Eiman Ebrahimi, Nastaran Hajinazar, Phillip B. Gibbons and Onur Mutlu,
“A Case for Richer Cross-layer Abstractions: Bridging the Semantic Gap with Expressive Memory”
Proceedings of the 45th International Symposium on Computer Architecture (ISCA), Los Angeles, CA, USA, June 2018.
[Slides (pptx) (pdf)] [Lightning Talk Slides (pptx) (pdf)]