Long-read sequencing, also known as third-generation sequencing technologies [1], [2], [3] have demonstrated their potential in revolutionizing the field of genomics and beyond, spanning over precision medicine [4], investigation of infectious disease outbreaks [5], global food security [6], and many other applications. It produces longer reads of contiguous DNA base pairs (i.e., >10,000 bps) compared to previous sequencing technologies, which greatly improves the quality of genome assembly and significantly benefits other genetic researches [7]. The state-of-the-art technology can even offer portable, real-time sequencing via a USB-sized sequencer [8]. Nevertheless, managing and analyzing the obtained raw genomic data with an exponentially growing size, also known as Moore's Law in molecular biology [9], imposes new computational challenges to the processing speed and efficiency of existing computing platforms.
In general, large-scale genomic reads can be analyzed by read mapping or de novo assembly based on the characteristic of the underlying data and the availability of reference genomes [10]. Although different approaches have distinct strategies and thus provide different insights, the key step of these methods is to examine the similarity between pairs of sequences via pairwise alignment. In generally, most genome aligners follow a typical seed-chain-align [11] procedure, among which chain phase consumes >70% of the total computation time, which thus is the focus of this work.
The chain algorithm is an one-dimensional dynamic programming model, where each input element is compared to N previous elements to determine the best predecessor. This computation procedure has three notable features: 1) it is a memory-intensive search process; 2) the execution of chain is dominated by simple subtraction and comparison operations; 3) it requires little support for floating-point computation. Therefore, we identify that ReRAM-based associative computing is well suited for the acceleration of chain due to its high density, low power consumption, and the ability to perform parallel in-situ subtraction/comparisons. In this work, we present PARC, a Processing-in-Memory (PIM) architecture that utilizes configurable ReRAM-based content-addressable memory (CAM) to perform in-situ logic operations and conventional memory access. On top of this architecture, We also propose an efficient data mapping method and a pipelined processing scheme. In summary, we make the following contributions:
• To support read, write and computation functionalities, we exploit the symmetry of the crossbar structure, which can naturally enable dual-addressing memory architecture to support both row-wise in-situ computation and column-wise memory accesses for chaining workloads.
• We share the peripheral circuitry including wordline drivers and sense amplifiers across data arrays, thereby minimizing the area overhead.
• We present an efficient data mapping and management scheme for relational data structured (i.e., tuple). Based on the mapping scheme, computations are performed within the ReRAM array in a wordparallel, bit-serial fashion.
• We compare the performance of PARC against both software tool and state-of-the-art hardware solutions.
Results show that our design achieves significant performance improvement and energy reduction.
This paper is organized as follows: Section II introduces the background and the motivation; Section III proposes the PARC architecture; Section IV describes the strategy of mapping chain phase onto the proposed architecture; Section V present the evaluation setup for PARC; Section VI discuss our experimental results. We conclude ths work in Section VII.
This section introduces the background knowledge that facilitates our design. The basics of seed-chain-align pairewise alignment procedure is first described, followed by the basics of ReRAM and its application in in-memory computing. At last, we review related works and highlight our motivation.
Problem statement. Pairwise alignment finds the optimal alignment of two genomic sequences X = x 1 x 2 . . .x m and Y = y 1 y 2 . . .y n , where the x i and y i are chosen from a finite alphabet. Specifically, for protein sequences the alphabet is 20 amino acids; for DNA sequences of interest in this work, the alphabet is 4 nucleotide bases Σ = {A, C, G, T }. The alignment score is defined in the form of a list of "columns" types including (1) match, (2) mismatch, and (3) gap (insertion or deletion).
Figure 2 illustrate one possible alignment for sequences X = ACGAT CGGAT and Y = GCT CGGT AT . In this example, we reward matching bases with score +10, penalize mismatching bases and gaps (denoted by '-') with -4 and -5, respectively. Therefore, the final score of the alignment is +51. Clearly, different alignments between two sequences yield different scores. The goal of pairwise alignment is to identify the alignment between sequence pairs which maxmize the score.
Alignment algorithm. Sequence alignments typicall use the two-phase Smith-Waterman (SW) algorithm [12] which first fills a m×n (m, n respectively represent the length of two sequences) matrix using Dynamic Programming (DP) to find the maximal alignment score, followed by a traceback phase which reconstruct the optimal local alignment by reversing the traceback pointers starting from the cell with highest-score. Although the SW algorithm guarantees an best local alignment between two sequences, its O(mn) time and O(mn) spatial complexity limit its use in genomic analysis, since in practice it is often necessary to process millions of sequences simultaneously. Instead, BLAST [13], [14] is used as a heuristic of the SW algorithm which employs a two-step seed-and-extend approach. However, for long reads with high error rates, BLAST gives a high false positive rate that results in excessive computation in the more expensive extend stage. To address this issue, minimap [11] chains the seeds to potential mapping regions with a longer length before extend. The chain step itself provides a higher accuracy than many aligners, in which case the align (i.e., equivalent to extend) phase becomes optional and is performed only when necessary. Minimap's superior performance in processing latency and mapping accuracy with reduced computational efforts make it the de facto general-purse pairwise alignment tool.
Seed-chain-align. Figure 1(a) illustrats the seedchain-align procedure in minimap. Seed collects k-mer minimizers (i.e., a k-long DNA sequence with minimum value in a w-sized surrounding window) of the targeting sequences and indexes them in a hash table by performing a hash function Φ : Σ k →Z. Then the query minimizers are taken as seeds to find exact matches (also called as anchor) against the hash table of the reference sequence. The collected Anchors are stored in 2-tuples and enter into a chain phase, which performs one-dimensional DP to identifies correlated anchors as chains. Finally an optional align step applies SW algorithm [12] to extend the chains with approximate matches.
As chain step is the focus of this paper, we show the detailed algorithm in Figure 1(b). Essentially, each anchor is compared against N previous anchors to identify its predecessor with the highest score. The grey block highlights the key operations involved in the chain step, which include additions, subtractions and simple scaling. Table I summarizes the notations that are used for explanation of genome pairwise alignment. Due to page limit, we do not give the full explanation of those parameters or the chain algorithm. We refer interested reader to [11], [15].
ReRAM is an emerging type of non-volatile memory that stores information by changing cell resistances. The resistance of a ReRAM cell can be programmed by applying a current or voltage with proper pulse-width or magnitude. ReRAM has been extensively studies as a promising candidate for future main memory [16]. Very recently, many ReRAM-based in-memory accelerator were proposed for hardware acceleration of machine learning applications [17], [18]. However, the current ReRAM based PIM accelerators mainly leverages ReRAM to perform in-situ matrix-vector multiplications. The computational requirement in genomic analysis is different. It barely require complex computation (i.e. dot-product in machine learning). Instead, it is a memory-intensive search process. Thus we identify ReRAM-based associative computing as a perfect fit. The details of the proposed dual-addressing ReRAM CAM (content addressable memory) is elaborated in Section III.
RADAR [19] proposed to accelerate the ungapped extension stage of BLAST [14] using 3D vertical ReRAM. However, BLAST is only suitable for the previous generation of short read alignments. In addition, the 3D vertical implementation of ReRAM is still not a mature technology that can be used in commodity chips. Racelogic [20] and BioSEAL [21] are two accelerators which accelerate dynamic programming in traditional CMOS and ReRAM, respectively. These two works, however, lack the critical features to support backtrace. Darwin [7] is the first accelerator for long reads mapping. It integrates hash table based seeding and SW-based extension. Instead, we are targeting a more efficient and accurate seed-chain-align procedure. The work most similar to this work is proposed in [22], which proposed an FPGA-based chain accelerator, while we realize chain acceleration by leveraging in-situ computation in ReRAM CAMs.
A content-addressable memory broadcasts a search word onto the searchlines (SrLs) against a table of stored data. Each stored word has a matchline (ML) that indicates whether it is a match or mismatch. This matching information normally is fed to an encoder to generates further instructions corresponding to the ML that is in the match state. Since the area of a CAM cell affects both the cost-per-bit and the speed/energy in a megabit array, we propose an area-efficient CAM design shown in Figure 3 utilizing high-density ReRAM cells. In the proposed design, each CAM unit consists of two adjacent complementary cells located in the same row. Specifically, a high resistance cell R H and a low resistance cell R L pair up to represent logic '1' and a R L /R H cell pair represents logic '0'. Search words on SrLs are also encodes by a pair of complementary voltages: V/0 and 0/V represents input signal '1' and '0', respectively. Here V denotes the minimum voltage required for a read operation.
Column-wise search. To search a word, MLs are precharged to V. Each bit of the search word is represented with a pair of complementary voltages on the SrLs. Figure 3 shows an example for search "10" in an array which stores "01" and "11". The voltage on the ML of each ReRAM cell is V . Thus, within each pair, only the cell with a 0 voltage on SrL is activated as highlighted in blue. We denote the read current of a cell in high resistance state (HRS) and low resistance state (LRS) as I H and I L , respectively. In this case, a sensed current I L (I H ) at the end of a row indicates a 1-bit match (mismatch). Normally, the fine-grained bit-wise matching information is not needed. For a n-bit search, the threshold current can simply be set as nI L . Rows with a current lower than nI L indicates a word mismatch.
Row-wise read/write. For regular read/write, we reserve a group of column sense amplifiers (SAs) at the vertical end of each SrL. As denoted in light blue text in Figure 3, MLs and SrLS serves as regular wordlines (WLs) and bitlines (WLs) when performing row-wise memory access.
CAM-based addition. The execution of chain is dominated by simple subtraction, and comparison such as min, max operation as illustrated in the grey block in Figure 1(b). The calculation of min, max can be realized by a read followed by a parallel 1-bit comparison. with negligible overhead. The bottleneck of computation is the calculation of anchor distance r ir j and q iq j . We proposed to implement abstraction on CAM without moving huge anchor dataset (i.e., averagely 8MB in our profiling) between memory hierarchies. We store anchors in CAM in consecutive rows which facilitates in-situ calculation
Fig. 4. CAM-based 1-bit addition.
Authorized licensed use limited to: Duke University. Downloaded on July 30,2020 at 14:28:22 UTC from IEEE Xplore. Restrictions apply. of distance. Detailed mapping scheme is illustrated in Section IV. In general, the two elements in each tuple is located in neighboring arrays. The subtraction can be viewed as addition with 2's complement. We structure multiple-bit addition as series of 1-bit addition. Figure 4 demonstrated the computation flow of CAMbased 1-bit addition. The left part shows 1-bit addition table, where a, b, C i are the two operands and the carry-in bit, c o , s denotes the carry-out bit and sum. The operands are located in each single row with carry bit initialized as '0'. A controller first sequentially searches all the 8 possible input combinations of a, b, and c, and the corresponding values are written into sum s and carry bit c in the following cycle. For instance, as shown in the right part of Figure 4. The carry-bit column is first initialized as '0'. Then the SrLs of bit 'A 0 ', 'B 0 ' and 'C' are activated (denoted in color blue). The first entry in the addition truth table is first searched in the CAM array. In this case we get a match in row 1. So C and S 0 will be written as '0' and '0' accordingly in the next cycle. Following the similar search procedure, we searches every entry in the truth table to perform the addition for every bit to obtain the final results. Note that in each cycle, the carry bit C is updated in-situ to save memory space.
B. PARC Architecture PE organization. Figure 5 illustrates the organization of one PE structure in PARC, which allows each memory row to be searched, read, and write. PARC leverages ReRAM CAM to perform in-memory execution. Each array contains four dual-accessing ReRAM crossbars and a score memory which stores the floating-point scores for each anchor. The four ReRAM CAM arrays share a row decoder, a wordline driver, a match line pre-charger, a search line mask, and a column decoder and driver. A PE also has a small array of 1-bit comparator to support comparison, a registers to record α, and a look-up table based memory for calculating β in chain algorithm, which are respectively denoted as cmp, α-flag, and LUT in Figure 5.
Sharing of peripheral circuitry. The baseline design requires a set of vertical sense amplifiers connected to MLs and a set of horizontal sense amplifiers connected to BLs, as illustrated in Figure 3. These two sets of SAs introduce significant overhead in terms of both area and computational energy. Hence, we adopt the sense amplifier sharing scheme in [23] by rotating the arrays 90 • in turn. As demonstrated in Figure 5, adjacent SAs are used on a search, while the neighboring SAs a litter further are leveraged for conventional memory access. Moreover, wordline drivers are also shared among the crossbar arrays within a PE by global wordline. At a time, only a pair of crossbar array in a PE can be activated and used to perform column-wise search or row-wise access. PARC architecture overview. Figure 6 demonstrated the PARC architecture. At the top level, it consists a scheduler which fetch anchor list from the database and distributes tasks among PEs, an array of PEs which chain the anchors, and a collector that output the results (i.e., chains and scores) to DRAM. Each row of PEs handles the anchors from the same reference sequence, such that multiple PE rows perform calculations in an independent manner.
Anchors are organized as 2-tuples (r, q), where r and q are both 32-bit integer [11]. Conventional main memory is a linear address space starting at zero. Normally, all fields of a tuple are stored consecutively. In PARC, tuples are mapped into two neighboring arrays which shares a wordline driver as highlighted in red in Figure 5. Based on this efficient relational data layout, we explain how the execution of chain is mapped onto PARC.
Computing distance r ir j and q iq j . The 2's complement of current target anchor (r i , q i ) is applied onto the SrLs. In this case, we obtain r jr i and q jq i (j ∈ [i -N, i -1]) in parallel. The addition operation is performed in a bit-serial fashion as explained in Section III which takes 32 logic cycles. Within each cycle, the singbit addition table entries are searched and corresponding results are written into both sum and carry regions, denoted by and in Figure 5.
To compute α = min(r jr i , q jq i , w), we read both r j and q j out in a bit-serial fashion starting from the most-significant-bit (MSB). With each PE, the dedicated comparator array cmp compares 32 pair of 1-bit value in parallel and store the results in αflag . To compute g, we utilize the CAM-based addition again. Results are store back into the same PE denoted as in Figure 5. After g is obtained, we look up in LUT to obtain the value of β.
Similar to [23], PARC is implemented modularly in a DIMM attached to the main memory system. While PARC features non-volatile CAM data arrays, PARC arrays do not include any of the priority index logic, population count logic, the reduction network, or programmable microcontrollers. Instead, PARC tailors the data and control paths to pariwise alignment, which entails minimal logic for chaining. At the same time, the peripheral circuitry of the array and the processing units are all pipelined, which significantly improves the processing throughput and makes the design overhead tolerable.
Long Reads Dataset. We generate 10Kbp long reads using a PacBio reads simulator [24]. Without loss of generality, We set the genome sequencing error rate as 20% and the coverage as 30×.
Baseline. As comparison baselines, we run minimap [11] on the 8-core Intel E5-2630v3 CPU with 128GB main memory at a maximum frequency of 2.4 GHz and on the NVIDIA Geforce GTX 1080 with 8 GB GDDR5 II. We use NVSIM-CAM [25] to model the latency, power and area of ReRAM arrays. We adopted the ReRAM cell model from [26] with a crossbar size of 256 × 256. The comparators, drivers and other peripheral circuitry are synthesized by Cadence Design Compiler with 32nm PTM process technology. The bus and connections are modeled and estimated using Cadence Virtuoso with TSMC 32nm technology. We also evaluated the PARC architecture using four state-of-the-art alignment accelerators shown in Table III.
We built pairwise alignment for long reads on various platforms to study the performance and throughput. Note that although all of the accelerators under-test support long reads alignment, the underlying algorithms they use are not the same. Specifically, we run minimap [15] on CPU, GPU, FPGA [22], and PARC. Compared with general CPU/GPU platforms, FPGA and PARC are customized hardware accelerators for minimap. For Darwin and BioSEAL, we run Dynamic Programming based alignment algorithm as both design are specialized for DP models. We summarize the detailed die size, off-chip memory capacity, power, read alignment throughput, and power efficiency in Table IV.
As visualized in Figure 7 (a), the power consumption increases from general CPU/GPU platform to customized FPGA and ASIC accelerators. For FPGA and Darwin, the increased power is mainly due to the the intrinsic high computation and memory complexity. For instance, Darwin require huge capacity of off-chip memory to store complex intermediate data, and hash tables. While BioSEAL and PARC both utilize CAM arrays which consume more power than conventional RAMs.
We show the throughput (sequence per seconds) in watt) in Figure 7 (c), which clearly demonstrates that PARC provides the best solution to accommodate the intensive computation in long reads alignment in terms of throughput per unit power. Figure 8 also shows the energy and area breakdown in PARC. In general, sense amplifier consumes 58% energy and 51% area. The ReRAM CAM array together with the score memory consume less than 20% energy and area. In our future work, we plan to design more efficient architecture to reduce the overhead of peripheral circuitry.
In conclusion, we propose a ReRAM CAM based acclerator for DNA long read pairwise alignment. We exploit the symmetry of the crossbar structure to enable dual-addressing memory architecture which supports both row-wise in-situ computation and column-wise memory accesses. We also present an efficient data mapping and management scheme. Based on the mapping scheme, computations are performed within the ReRAM arrays in a word-parallel, bit-serial fashion. Compared to software tools on CPU and GPU, PARC provides 215× and 64× throughput improvement, respectively. Compared to the state-of-the-art accelerator, Darwin, PARC shows respective 2.3× and 1.5× improvement in terms of throughput and power efficiency.
978-1-7281-4123-7/20/$31.00 c 2020 IEEE
3B-1Authorized licensed use limited to: Duke University. Downloaded on July 30,2020 at 14:28:22 UTC from IEEE Xplore. Restrictions apply.
Authorized licensed use limited to: Duke University. Downloaded on July 30,2020 at 14:28:22 UTC from IEEE Xplore. Restrictions apply.