Jisung Park

Roknoddin Azizi

Geraldo F Oliveira

Mohammad Sadrosadati

Rakesh Nadig

David Novo

Juan Gómez-Luna

Myungsuk Kim

Onur Mutlu

Flash-Cosmos: In-Flash Bulk Bitwise Operations Using Inherent Computation Capability of NAND Flash Memory

Bulk bitwise operations, i.e., bitwise operations on large bit vectors, are prevalent in a wide range of important application domains, including databases, graph processing, genome analysis, cryptography, and hyper-dimensional computing. In conventional systems, the performance and energy efficiency of bulk bitwise operations are bottlenecked by data movement between the compute units (e.g., CPUs and GPUs) and the memory hierarchy. In-flash processing (i.e., processing data inside NAND flash chips) has a high potential to accelerate bulk bitwise operations by fundamentally reducing data movement through the entire memory hierarchy, especially when the processed data does not fit into main memory.

We identify two key limitations of the state-of-the-art inflash processing technique for bulk bitwise operations; (i) it falls short of maximally exploiting the bit-level parallelism of bulk bitwise operations that could be enabled by leveraging the unique cell-array architecture and operating principles of NAND flash memory; (ii) it is unreliable because it is not designed to take into account the highly error-prone nature of NAND flash memory.

We propose Flash-Cosmos (Flash Computation with One-Shot Multi-Operand Sensing), a new in-flash processing technique that significantly increases the performance and energy efficiency of bulk bitwise operations while providing high reliability. Flash-Cosmos introduces two key mechanisms that can be easily supported in modern NAND flash chips: (i) Multi-Wordline Sensing (MWS), which enables bulk bitwise operations on a large number of operands (tens of operands) with a single sensing operation, and (ii) Enhanced SLC-mode Programming (ESP), which enables reliable computation inside NAND flash memory. We demonstrate the feasibility of performing bulk bitwise operations with high reliability in Flash-Cosmos by testing 160 real 3D NAND flash chips. Our evaluation shows that Flash-Cosmos improves average performance and energy efficiency by 3.5×/32× and 3.3×/95×, respectively, over the state-of-the-art in-flash/outside-storage processing techniques across three real-world applications.

Introduction

Many data-intensive applications rely on bulk bitwise operations, i.e., bitwise operations on large bit vectors. As such, it is important for modern computing systems to support highperformance and energy-efficient bulk bitwise operations. In databases and web search, prior works (e.g., [START_REF] Chan | Bitmap Index Design and Evaluation[END_REF][START_REF] O'neil | Bitmap Index Design Choices and their Performance Implications[END_REF][START_REF] Li | WideTable: An Accelerator for Analytical Data Processing[END_REF][START_REF] Li | BitWeaving: Fast Scans for Main Memory Data Processing[END_REF][START_REF] Goodwin | BitFunnel: Revisiting Signatures for Search[END_REF][START_REF] Seshadri | RowClone: Fast and Energy-Efficient In-DRAM Bulk Data Copy and Initialization[END_REF][START_REF] Seshadri | Ambit: In-Memory Accelerator for Bulk Bitwise Operations Using Commodity DRAM Technology[END_REF][START_REF] Seshadri | Fast Bulk Bitwise AND and OR in DRAM[END_REF][START_REF] Hajinazar | SIMDRAM: A Framework for Bit-Serial SIMD Processing Using DRAM[END_REF]) propose various techniques that heavily use bulk bitwise operations to accelerate queries. Bulk bitwise operations are also prevalent in various other important application domains, including databases and web search [START_REF] Chan | Bitmap Index Design and Evaluation[END_REF][START_REF] O'neil | Bitmap Index Design Choices and their Performance Implications[END_REF][START_REF] Li | WideTable: An Accelerator for Analytical Data Processing[END_REF][START_REF] Li | BitWeaving: Fast Scans for Main Memory Data Processing[END_REF][START_REF] Goodwin | BitFunnel: Revisiting Signatures for Search[END_REF][START_REF] Seshadri | RowClone: Fast and Energy-Efficient In-DRAM Bulk Data Copy and Initialization[END_REF][START_REF] Seshadri | Ambit: In-Memory Accelerator for Bulk Bitwise Operations Using Commodity DRAM Technology[END_REF][START_REF] Seshadri | Fast Bulk Bitwise AND and OR in DRAM[END_REF][START_REF] Hajinazar | SIMDRAM: A Framework for Bit-Serial SIMD Processing Using DRAM[END_REF][START_REF]FastBit: An Efficient Compressed Bitmap Index Technology[END_REF][START_REF] Wu | Encoded Bitmap Indexing for Data Warehouses[END_REF][START_REF] Guz | Real-Time Analytics as the Killer Application for Processing-In-Memory[END_REF][START_REF] Redis | Redis bitmaps[END_REF], data analytics [START_REF] Seshadri | Ambit: In-Memory Accelerator for Bulk Bitwise Operations Using Commodity DRAM Technology[END_REF][START_REF] Perach | PIMDB: Understanding Bulk-Bitwise Processing In-Memory Through Database Analytics[END_REF][START_REF] Jun | BlueDBM: An Appliance for Big Data Analytics[END_REF][START_REF] Torabzadehkashi | Catalina: In-Storage Processing Acceleration for Scalable Big Data Analytics[END_REF][START_REF] Lee | SmartSSD: FPGA Accelerated Near-Storage Data Analytics on SSD[END_REF], graph processing [START_REF] Hajinazar | SIMDRAM: A Framework for Bit-Serial SIMD Processing Using DRAM[END_REF][START_REF] Beamer | Direction-Optimizing Breadth-First Search[END_REF][START_REF] Besta | SISA: Set-Centric Instruction Set Architecture for Graph Mining on Processingin-Memory Systems[END_REF][START_REF] Li | Pinatubo: A Processing-in-Memory Architecture for Bulk Bitwise Operations in Emerging Non-Volatile Memories[END_REF][START_REF] Gao | ParaBit: Processing Parallel Bitwise Operations in NAND Flash Memory Based SSDs[END_REF], genome analysis [START_REF] Alser | GateKeeper: A New Hardware Architecture for Accelerating Pre-alignment in DNA Short Read Mapping[END_REF][START_REF] Loving | BitPAl: A Bit-Parallel, General Integer-Scoring Sequence Alignment Algorithm[END_REF][START_REF] Xin | Shifted Hamming Distance: A Fast and Accurate SIMD-Friendly Filter to Accelerate Alignment Verification in Read Mapping[END_REF][START_REF] Cali | GenASM: A High-Performance, Low-Power Approximate String Matching Acceleration Framework for Genome Sequence Analysis[END_REF][START_REF] Kim | GRIM-Filter: Fast Seed Location Filtering in DNA Read Mapping Using Processing-in-Memory Technologies[END_REF][START_REF] Lander | Initial Sequencing and Analysis of the Human Genome[END_REF][START_REF] Altschul | Basic Local Alignment Search Tool[END_REF][START_REF] Myers | A Fast Bit-Vector Algorithm for Approximate String Matching Based on Dynamic Programming[END_REF], cryptography [START_REF] Han | Optical Image Encryption Based on XOR Operations[END_REF][START_REF] Tuyls | XOR-based Visual Cryptography Schemes[END_REF][START_REF] Manavski | CUDA Compatible GPU as an Efficient Hardware Accelerator for AES Cryptography[END_REF], set operations [START_REF] Seshadri | Ambit: In-Memory Accelerator for Bulk Bitwise Operations Using Commodity DRAM Technology[END_REF][START_REF] Besta | SISA: Set-Centric Instruction Set Architecture for Graph Mining on Processingin-Memory Systems[END_REF], and hyper-dimensional computing [START_REF] Kanerva | Sparse Distributed Memory and Related Models[END_REF][START_REF] Kanerva | Hyperdimensional Computing: An Introduction to Computing in Distributed Representation with High-Dimensional Random Vectors[END_REF][START_REF] Karunaratne | In-memory Hyperdimensional Computing[END_REF][START_REF] Imani | Exploring Hyperdimensional Associative Memory[END_REF].

In conventional systems, the performance and energy efficiency of bulk bitwise operations are bottlenecked by data movement between the compute units (e.g., CPUs or GPUs) and the memory hierarchy [START_REF] Seshadri | Ambit: In-Memory Accelerator for Bulk Bitwise Operations Using Commodity DRAM Technology[END_REF][START_REF] Seshadri | Fast Bulk Bitwise AND and OR in DRAM[END_REF][START_REF] Li | Pinatubo: A Processing-in-Memory Architecture for Bulk Bitwise Operations in Emerging Non-Volatile Memories[END_REF][START_REF] Gao | ParaBit: Processing Parallel Bitwise Operations in NAND Flash Memory Based SSDs[END_REF][START_REF] Aga | Compute Caches[END_REF][START_REF] Seshadri | In-DRAM Bulk Bitwise Execution Engine[END_REF][START_REF] Li | DRISA: A DRAMbased Reconfigurable In-Situ Accelerator[END_REF]. To perform a bulk bitwise operation, a conventional system must first move every operand to the compute unit and eventually write the results back into the memory hierarchy. Due to the simple nature of bitwise operations, such data movement dominates the execution time and energy consumption in bulk bitwise operations.

Processing data inside NAND flash chips, i.e., in-flash processing (IFP), can fundamentally reduce the data movement that bottlenecks the execution of bulk bitwise operations. IFP is an instance of near-data processing (NDP), a computing paradigm that moves computation closer to where the data resides (e.g., [7-9, 20, 21, 37, 40-54]). When processing large amounts of data that do not fit in main memory, IFP significantly reduces data movement across the entire memory hierarchy by performing computation within the underlying storage media (i.e., NAND flash chips) and transferring only the result (when needed, to main memory and CPUs/GPUs). As we discuss in Section 3, IFP can significantly outperform in-storage processing (ISP) approaches that leverage hardware accelerators inside the NAND flash-based solid-state drive (SSD) (e.g., [49-52, 55, 56]), by reducing data movement to/from NAND flash chips.

To our knowledge, only one recent work, ParaBit [START_REF] Gao | ParaBit: Processing Parallel Bitwise Operations in NAND Flash Memory Based SSDs[END_REF], proposes an in-flash processing technique for bulk bitwise operations. 1 We identify that ParaBit has two major limitations. First, ParaBit falls greatly short of exploiting the full potential of NAND flash memory to significantly improve the perfor- 1 There are many prior works (e.g., [START_REF] Choi | An In-Flash Binary Neural Network Accelerator with SLC NAND Flash Array[END_REF][START_REF] Han | A Novel Convolution Computing Paradigm Based on NOR Flash Array with High Computing Speed and Energy Efficiency[END_REF][START_REF] Shim | GP3D: 3D NAND based In-memory Graph Processing Accelerator[END_REF][START_REF] Merrikh-Bayat | High-Performance Mixed-Signal Neurocomputing With Nanoscale Floating-Gate Memory Cell Arrays[END_REF][START_REF] Tseng | In-Memory-Searching Architecture Based on 3D-NAND Technology with Ultra-High Parallelism[END_REF][START_REF] Wang | Three-Dimensional NAND Flash for Vector-Matrix Multiplication[END_REF][START_REF] Lue | Optimal Design Methods to Transform 3D NAND Flash into a High-Density, High-Bandwidth and Low-Power Nonvolatile Computing in Memory (nvCIM) Accelerator for Deep-Learning Neural Networks (DNN)[END_REF]) that leverage analog current sensing to perform accumulative computation (e.g., multiply-accumulate operation) inside NAND flash chips. However, these proposals 1) use NAND flash memory solely as an accelerator but not as a storage medium, and 2) require significant changes (e.g., adding a precise analog-to-digital converter to each bitline) to commodity NAND flash chips, which increases cost. See Section 9 for more detail. mance and energy efficiency of bulk bitwise operations. To perform bulk bitwise operations for more than two operands (e.g., A • B • C), which frequently happens in many data-intensive applications such as data analytics [START_REF] Seshadri | Ambit: In-Memory Accelerator for Bulk Bitwise Operations Using Commodity DRAM Technology[END_REF][START_REF] Perach | PIMDB: Understanding Bulk-Bitwise Processing In-Memory Through Database Analytics[END_REF][START_REF] Jun | BlueDBM: An Appliance for Big Data Analytics[END_REF][START_REF] Torabzadehkashi | Catalina: In-Storage Processing Acceleration for Scalable Big Data Analytics[END_REF][START_REF] Lee | SmartSSD: FPGA Accelerated Near-Storage Data Analytics on SSD[END_REF], databases [START_REF]FastBit: An Efficient Compressed Bitmap Index Technology[END_REF][START_REF] Wu | Encoded Bitmap Indexing for Data Warehouses[END_REF][START_REF] Guz | Real-Time Analytics as the Killer Application for Processing-In-Memory[END_REF][START_REF] Redis | Redis bitmaps[END_REF] and graph processing [START_REF] Hajinazar | SIMDRAM: A Framework for Bit-Serial SIMD Processing Using DRAM[END_REF][START_REF] Besta | SISA: Set-Centric Instruction Set Architecture for Graph Mining on Processingin-Memory Systems[END_REF][START_REF] Li | Pinatubo: A Processing-in-Memory Architecture for Bulk Bitwise Operations in Emerging Non-Volatile Memories[END_REF][START_REF] Gao | ParaBit: Processing Parallel Bitwise Operations in NAND Flash Memory Based SSDs[END_REF], ParaBit must serially perform multiple two-operand bitwise operations (e.g., (A • B) • C). Doing so requires multiple long-latency sensing operations in series, which become a new performance and energy efficiency bottleneck. In this work, we observe that NAND flash memory has inherent capability to perform bitwise operations on a large number (e.g., tens) of operands at once (i.e., with a single sensing operation) due to its unique cell-array structures that are similar to digital logic circuits for NAND and NOR gates.

Second, ParaBit is applicable only to highly error-tolerant applications because it is not designed to take into account the highly error-prone nature of NAND flash memory. To ensure data reliability, modern NAND flash-based SSDs commonly use (i) error-correcting codes (ECC) and (ii) data randomization [START_REF] Park | Reducing Solid-State Drive Read Latency by Optimizing Read-Retry[END_REF][START_REF] Cai | Reliability Issues in Flashmemory-based Solid-state Drives: Experimental Analysis, Mitigation, Recovery[END_REF][START_REF] Cha | Data Randomization Scheme for Endurance Enhancement and Interference Mitigation of Multilevel Flash Memory Devices[END_REF][START_REF] Cai | Error Characterization, Mitigation, and Recovery in Flash-Memory-Based Solid-State Drives[END_REF]. Unfortunately, ParaBit cannot leverage any of the widely-used ECC and data-randomization techniques, as it performs bitwise operations while sensing the cells that store the data. Performing bitwise AND and OR operations on ECCencoded or randomized data using ParaBit can lead to incorrect results during ECC decoding and/or de-randomization. Although storing a smaller number of bits in a cell would reduce the raw bit error rate (RBER) of NAND flash memory, our characterization using 160 real 3D NAND flash chips shows that even storing a single bit per cell cannot provide sufficientlylow RBER for ParaBit to be adopted across a wide range of applications.

Our goal is to improve both the performance and energy efficiency of in-flash bulk bitwise operations while ensuring high reliability (i.e., zero bit errors) in computation results. To this end, we propose Flash-Cosmos (Flash Computation with One-Shot Multi-Operand Sensing), a novel in-flash processing technique for bulk bitwise operations that achieves our goal by exploiting two key ideas: (i) Multi-Wordline Sensing (MWS), which enables in-flash bulk bitwise operations on multiple (e.g., tens) operands with a single sensing operation, and (ii) Enhanced SLC-mode Programming (ESP), which effectively achieves zero bit errors in the results of in-flash bulk bitwise operations.

MWS leverages the two fundamental cell-array structures of NAND flash memory to perform in-flash bulk bitwise operations on a large number of operands with a single sensing operation: (i) a number of flash cells (e.g., 24-176 cells) are serially connected to form a NAND string (similar to digital NAND logic); (ii) thousands of NAND strings are connected to the same bitline (similar to digital NOR logic). Under these cellarray structures, simultaneously sensing multiple wordlines 2automatically results in (i) bitwise AND of all the sensed wordlines if they are in the same NAND string or (ii) bitwise OR of all the wordlines if they are in different NAND strings.

ESP effectively avoids raw bit errors in stored data via more precise programming-voltage control. A flash cell stores bit data as a function of the level of its threshold-voltage (V TH ). Reading a cell incurs an error if the cell's V TH level moves to another V TH range that corresponds to a different bit value than the stored value, due to various reasons [START_REF] Cai | Error Characterization, Mitigation, and Recovery in Flash-Memory-Based Solid-State Drives[END_REF], such as program interference [START_REF] Cai | Program Interference in MLC NAND Flash Memory: Characterization, Modeling, and Mitigation[END_REF][START_REF] Cai | Vulnerabilities in MLC NAND Flash Memory Programming: Experimental Analysis, Exploits, and Mitigation Techniques[END_REF][START_REF] Park | Improving Performance and Lifetime of NAND Storage Systems Using Relaxed Program Sequence[END_REF], data retention loss [START_REF] Cai | Data Retention in MLC NAND Flash Memory: Characterization, Optimization, and Recovery[END_REF][START_REF] Cai | Flash Correct-and-Refresh: Retention-Aware Error Management for Increased Flash Memory Lifetime[END_REF][START_REF] Cai | Error Analysis and Retention-aware Management for NAND Flash Memory[END_REF][START_REF] Luo | Improving 3D NAND Flash Memory Lifetime by Tolerating Early Retention Loss and Process Variation[END_REF], read disturbance [START_REF] Cai | Read Disturb Errors in MLC NAND Flash Memory: Characterization, Mitigation, and Recovery[END_REF][START_REF] Ha | An Integrated Approach for Managing Read Disturbs in High-density NAND Flash Memory[END_REF], and cell-to-cell interference [START_REF] Cai | Vulnerabilities in MLC NAND Flash Memory Programming: Experimental Analysis, Exploits, and Mitigation Techniques[END_REF]. ESP maximizes the margin between different V TH ranges by carefully leveraging two existing approaches. First, to store data for in-flash processing, it uses the single-level cell (SLC)-mode programming scheme [START_REF] Lee | FlexFS: A Flexible Flash File System for MLC NAND Flash Memory[END_REF][START_REF] Kim | Evanesco: Architectural Support for Efficient Data Sanitization in Modern Flash-based Storage Systems[END_REF]. Doing so guarantees a large V TH margin by forming only two V TH ranges (for encoding '1' and '0') within the fixed V TH window. Second, ESP enhances the SLC-mode programming scheme by using (i) a higher programming voltage to increase the distance between the two V TH ranges and (ii) more programming steps to narrow the high V TH range. While many prior works also leverage precise programming to enhance the reliability of NAND flash memory [START_REF] Jeong | Lifetime Improvement of NAND Flashbased Storage Systems Using Dynamic Program and Erase Scaling[END_REF][START_REF] Shim | Exploiting Process Similarity of 3D Flash Memory for High Performance SSDs[END_REF][START_REF] Kim | SARO: A State-Aware Reliability Optimization Technique for High Density NAND Flash Memory[END_REF][START_REF] Feng | Using Disturbance Compensation and Data Clustering (DC)2 to Improve Reliability and Performance of 3D MLC Flash Memory[END_REF][START_REF] Wang | Using Dynamic Allocation of Write Voltage to Extend Flash Memory Lifetime[END_REF][START_REF] Dong | Using Data Postcompensation and Predistortion to Tolerate Cell-to-Cell Interference in MLC NAND Flash Memory[END_REF], we aim to achieve zero bit errors in computation results and demonstrate that doing so is possible in modern NAND flash memory by combining the two approaches that comprise ESP.

In this paper, we enhance our basic MWS mechanism in two ways to make it more general purpose. First, we support bitwise NAND/NOR/XOR/XNOR by using MWS along with (i) the inverse sensing mechanism [START_REF] Lee | High-Performance 1-Gb-NAND Flash Memory with 0.12-µm Technology[END_REF][START_REF] Lee | A 1.8V 1Gb NAND Flash Memory with 0.12µm STI Process Technology[END_REF] and (ii) internal XOR logic [START_REF] Kim | A 21 nm High Performance 64 Gb MLC NAND Flash Memory with 400 MB/s Asynchronous Toggle DDR Interface[END_REF][START_REF] Kim | A 512-Gb 3-b/Cell 64-Stacked WL 3-D-NAND Flash Memory[END_REF], both of which are already supported in most NAND flash chips. Second, we relax the data location constraints of the basic MWS mechanism (e.g., bitwise OR/NOR operations are possible only for wordlines in different NAND strings) by (i) storing each operand's inverse data and (ii) leveraging De Morgan's laws. For example, if the user stores the inverse of A, B, and C (i.e., A, B, and C) in the same NAND string, Flash-Cosmos can perform bitwise OR of three wordlines by performing bitwise NAND of A, B, and C because (A OR B OR C)=NOT (A AND B AND C).

Flash-Cosmos requires only small changes to the control logic of a NAND flash chip, but no changes to its cell array and sensing circuitry. For efficient post-fabrication tests and optimizations, most modern NAND flash chips are already capable of (i) simultaneously sensing multiple wordlines [START_REF] Crippa | Sensing circuits[END_REF] and (ii) adjusting programming step and voltage at fine granularity [START_REF] Cai | Error Characterization, Mitigation, and Recovery in Flash-Memory-Based Solid-State Drives[END_REF][START_REF] Jeong | Lifetime Improvement of NAND Flashbased Storage Systems Using Dynamic Program and Erase Scaling[END_REF][START_REF] Kim | SARO: A State-Aware Reliability Optimization Technique for High Density NAND Flash Memory[END_REF][START_REF] Luo | Enabling Accurate and Practical Online Flash Channel Modeling for Modern MLC NAND Flash Memory[END_REF]. Hence, integrating Flash-Cosmos into existing NAND flash chips requires changes only to the command latching circuitry and the firmware of the microcontroller in the flash chip (see Section 6).

We evaluate Flash-Cosmos in two ways. First, we validate Flash-Cosmos using 160 real 48-layer 3D NAND flash chips. Our results show that Flash-Cosmos enables commodity NAND flash chips to perform bitwise AND/OR/NAND/NOR of up to 48 operands via a single sensing operation (25 µs). In our validation of computation results across more than 10 11 flash cells, we observe zero bit errors. Second, we compare Flash-Cosmos to two different computing platforms, a stateof-the-art multi-core CPU (which we call outside-storage processing or OSP) [START_REF]Intel Core i711700K Processor -Product Specifications[END_REF] and ParaBit [START_REF] Gao | ParaBit: Processing Parallel Bitwise Operations in NAND Flash Memory Based SSDs[END_REF]. Our evaluation using three real-world workloads shows that Flash-Cosmos improves performance by 32×/3.5× and reduces energy consumption by 95×/3.3× on average compared to OSP/ParaBit. This work makes the following key contributions: • To our knowledge, this work is the first to enable NAND flash memory to perform bulk bitwise operations on multiple (i.e., tens) operands via a single sensing operation. • We introduce Flash-Cosmos, a new in-flash processing technique to significantly improve both performance and energy efficiency of bulk bitwise operations while achieving zero bit errors in computation results. • We demonstrate the feasibility and reliability of Flash-Cosmos using 160 real state-of-the-art 3D NAND flash chips. • We evaluate the effectiveness of Flash-Cosmos using realworld workloads, showing large performance and energy benefits over a state-of-the-art multi-core processor and the state-of-the-art in-flash processing technique.

Background

We provide a brief background on NAND flash memory that is useful to understand the rest of the paper.

Basics of NAND Flash Memory

NAND Flash Organization. Figure 1 shows the organization of 3D NAND flash memory. A number of vertically-stacked flash cells (e.g., 24 to 176 cells) are serially connected, which is called a NAND string. A NAND string is connected to a bitline (BL), and NAND strings at different BLs compose a subblock. The control gates of all cells that are at the same vertical location in a sub-block are connected to the same wordline (WL), which makes all such cells operate concurrently. A NAND flash block consists of several (e.g., 4 or 8) sub-blocks, and thousands of blocks comprise a plane. The blocks in a plane share all the BLs in that plane, which implies that a single BL is shared by thousands of NAND strings. In the rest of the paper, unless specified otherwise, we refer to a subblock as a block for simplicity. A NAND flash chip (or a die) contains multiple (e.g., 2 or 4) planes. Multiple chips in a NAND flash package can operate independently of each other but share the package's command/data buses (i.e., channel) in a time-interleaved manner. Program and Erase Operations. A flash cell stores data using its threshold voltage (V TH ) level that highly depends on the amount of charge in the cell's charge trap. A program operation injects electrons into a cell, which increases the cell's V TH level.

As multiple flash cells are connected to a single WL, NAND flash memory writes data at page (e.g., 16 KiB) granularity such that each cell in a WL stores one bit of the page. To decrease a programmed cell's V TH level, NAND flash memory performs an erase operation that ejects electrons from the cell. The granularity of an erase operation is a block, which causes the erase latency tBERS to be much longer (e.g., 3-5 ms) than the program latency tPROG (e.g., 200-700 µs).

Read Operation. NAND flash memory determines a cell's V TH level (i.e., the cell's bit data) by sensing the conductance of the corresponding NAND string. Figure 2 shows the read mechanism of NAND flash memory, which consists of three steps: (i) precharge, (ii) evaluation, and (iii) discharge [START_REF] Park | Reducing Solid-State Drive Read Latency by Optimizing Read-Retry[END_REF][START_REF] Micheloni | Inside NAND Flash Memories[END_REF].

In the precharge step ( P in the left part of Figure 2 step ( E in Figure 2). During precharge, the NAND flash chip charges the BL, making V SO =1. Before the evaluation step, the chip initializes the latching circuit by activating only transistor M 1 , resulting in V OUT =0 and thus V OUT =1. The evaluation step disables M PRE and M 1 while enabling M 2 . In Figure 3(a), the evaluation step makes V SO =0 as the charge in C SO quickly flows through the NAND string (because V TH ≤V REF ), which leads to V OUT =1 ( E in Figure 2). The bit value of the flash cell is immediately stored in the latching circuit because of the low charge retention of C SO [START_REF] Micheloni | Inside NAND Flash Memories[END_REF]. In Figure 3(b), the evaluation step leads to V SO =1 and V OUT =0 as the flash cell operates as an open switch when V TH >V REF .

Inverse Read. Modern NAND flash chips commonly support the inverse-read mode [START_REF] Lee | High-Performance 1-Gb-NAND Flash Memory with 0.12-µm Technology[END_REF] to read the inverse of the stored data. 3 Supporting inverse reads requires no hardware changes to the latching circuit shown in Figure 4. We denote the voltage states at the three nodes (SO/OUT/OUT) during an inverse read operation using I SO , I OUT and I OUT . The chip performs an inverse read by simply changing the activation sequence of M 1 and M 2 . Unlike a read operation, the inverse read activates M 2 to initialize the latching circuit before the evaluation step. This leads to I OUT =0 and thus I OUT =1. During the evaluation step, M 1 is activated while M PRE and M 2 are disabled. This causes the values stored in the latching circuit after the evaluation step to be the inverse of the values stored in a normal read.

Reliability of NAND Flash Memory

Modern NAND flash memory is highly error-prone due to various error sources [START_REF] Cai | Error Characterization, Mitigation, and Recovery in Flash-Memory-Based Solid-State Drives[END_REF] such as program interference [START_REF] Cai | Program Interference in MLC NAND Flash Memory: Characterization, Modeling, and Mitigation[END_REF][START_REF] Cai | Vulnerabilities in MLC NAND Flash Memory Programming: Experimental Analysis, Exploits, and Mitigation Techniques[END_REF][START_REF] Park | Improving Performance and Lifetime of NAND Storage Systems Using Relaxed Program Sequence[END_REF], data retention loss [START_REF] Cai | Data Retention in MLC NAND Flash Memory: Characterization, Optimization, and Recovery[END_REF][START_REF] Cai | Flash Correct-and-Refresh: Retention-Aware Error Management for Increased Flash Memory Lifetime[END_REF][START_REF] Cai | Error Analysis and Retention-aware Management for NAND Flash Memory[END_REF][START_REF] Luo | Improving 3D NAND Flash Memory Lifetime by Tolerating Early Retention Loss and Process Variation[END_REF], read disturbance [START_REF] Cai | Read Disturb Errors in MLC NAND Flash Memory: Characterization, Mitigation, and Recovery[END_REF][START_REF] Ha | An Integrated Approach for Managing Read Disturbs in High-density NAND Flash Memory[END_REF], and cellto-cell interference [START_REF] Cai | Vulnerabilities in MLC NAND Flash Memory Programming: Experimental Analysis, Exploits, and Mitigation Techniques[END_REF]. Figure 5 shows the V TH distribution 3 Supporting inverse reads is essential to the copyback operation [START_REF] Lee | High-Performance 1-Gb-NAND Flash Memory with 0.12-µm Technology[END_REF] that moves a page's data to another page in the same plane without off-chip data transfer and thus can improve SSD garbage-collection performance [START_REF] Hong | Improving SSD Performance Using Adaptive Restricted-Copyback Operations[END_REF][START_REF] Wu | FastGC: Accelerate Garbage Collection via an Efficient Copyback-Based Data Migration in SSDs[END_REF]. of a WL, when the WL is programmed in (a) single-level cell (SLC) mode and (b) multi-level cell (MLC) mode to store one and two bits per cell, respectively. Reading or programming a WL affects the V TH distribution of other WLs in the same block by increasing the V TH level of other cells (i.e., interference and disturbance as shown in Figure 5(a)). A flash cell also leaks its charge over time, which decreases its V TH level (i.e., retention loss as shown in Figure 5(a)). If a cell's V TH level moves beyond V REF (i.e., to a V TH range corresponding to a different value), sensing the cell results in a different value from the original stored data, introducing a bit error. Two major factors significantly increase the raw (i.e., precorrection) bit-error rate (RBER) of NAND flash memory. First, a flash cell becomes more error-prone as it experiences more program and erase (P/E) cycles [START_REF] Cai | Error Patterns in MLC NAND Flash Memory: Measurement, Characterization, and Analysis[END_REF], due to the high voltage used in program and erase operations which damages the cell to more easily leak its charge. Second, storing more bits per cell increases RBER because it reduces the margin between adjacent V TH ranges in order to pack more V TH states within the same voltage window, as shown in Figure 5(b). Error-Correcting Codes (ECC). To ensure the integrity of stored data, modern SSDs commonly employ ECC. ECC can detect and correct bit errors by storing redundant information. To cope with the high RBER of modern NAND flash memory, it is necessary to use sophisticated ECC (e.g., low-density parity-check (LDPC) codes [START_REF] Cai | Error Characterization, Mitigation, and Recovery in Flash-Memory-Based Solid-State Drives[END_REF][START_REF] Zhao | LDPC-in-SSD: Making Advanced Error Correction Codes Work Effectively in Solid State Drives[END_REF][START_REF] Micron | Product Flyer: Micron 3D NAND Flash Memory[END_REF][START_REF] Dong | On the Use of Soft-Decision Error-Correction Codes in NAND Flash Memory[END_REF][START_REF] Zuolo | LDPC Soft Decoding with Reduced Power and Latency in 1X-2X NAND Flash-Based Solid State Drives[END_REF][START_REF] Tanakamaru | Error-Prediction LDPC and Error-Recovery Schemes for Highly Reliable Solid-State Drives (SSDs)[END_REF][START_REF] Hu | LDPC Codes for Flash Channel[END_REF]), which increases the performance and the area overheads of an ECC engine. Data Randomization. It is common practice to randomize the values of stored data in modern SSDs to reduce the probability of worst-case data patterns that would exacerbate program disturbance [START_REF] Cha | Data Randomization Scheme for Endurance Enhancement and Interference Mitigation of Multilevel Flash Memory Devices[END_REF][START_REF] Kim | A 21 nm High Performance 64 Gb MLC NAND Flash Memory with 400 MB/s Asynchronous Toggle DDR Interface[END_REF][START_REF] Cernea | Highly Compact Non-Volatile Memory and Method Thereof[END_REF]. For example, when a NAND string has many consecutive erased cells, programming the next cell of the same NAND string significantly increases the V TH level of the consecutive cells, which could introduce bit errors. Data randomization reduces the probability of such cases to a small value by randomly distributing V TH states across a NAND string regardless of the original data values to store. 4 The stored data is de-randomized during a read operation to correctly read the originally stored values before they were randomized.

Motivation

We describe the benefits of in-flash processing and the main limitations of the state-of-the-art in-flash processing technique for bulk bitwise operations (i.e., bitwise operations on large bit vectors) [START_REF] Gao | ParaBit: Processing Parallel Bitwise Operations in NAND Flash Memory Based SSDs[END_REF].

In-Flash Bulk Bitwise Operations

Many prior studies [7-9, 20, 37, 38, 48] investigate near-data processing (NDP) solutions for bulk bitwise operations due to two main reasons. First, bulk bitwise operations are used in a wide variety of important applications, including databases and web search [START_REF] Chan | Bitmap Index Design and Evaluation[END_REF][START_REF] O'neil | Bitmap Index Design Choices and their Performance Implications[END_REF][START_REF] Li | WideTable: An Accelerator for Analytical Data Processing[END_REF][START_REF] Li | BitWeaving: Fast Scans for Main Memory Data Processing[END_REF][START_REF] Goodwin | BitFunnel: Revisiting Signatures for Search[END_REF][START_REF] Seshadri | RowClone: Fast and Energy-Efficient In-DRAM Bulk Data Copy and Initialization[END_REF][START_REF] Seshadri | Ambit: In-Memory Accelerator for Bulk Bitwise Operations Using Commodity DRAM Technology[END_REF][START_REF] Seshadri | Fast Bulk Bitwise AND and OR in DRAM[END_REF][START_REF] Hajinazar | SIMDRAM: A Framework for Bit-Serial SIMD Processing Using DRAM[END_REF][START_REF]FastBit: An Efficient Compressed Bitmap Index Technology[END_REF][START_REF] Wu | Encoded Bitmap Indexing for Data Warehouses[END_REF][START_REF] Guz | Real-Time Analytics as the Killer Application for Processing-In-Memory[END_REF][START_REF] Redis | Redis bitmaps[END_REF], data analytics [START_REF] Seshadri | Ambit: In-Memory Accelerator for Bulk Bitwise Operations Using Commodity DRAM Technology[END_REF][START_REF] Perach | PIMDB: Understanding Bulk-Bitwise Processing In-Memory Through Database Analytics[END_REF][START_REF] Jun | BlueDBM: An Appliance for Big Data Analytics[END_REF][START_REF] Torabzadehkashi | Catalina: In-Storage Processing Acceleration for Scalable Big Data Analytics[END_REF][START_REF] Lee | SmartSSD: FPGA Accelerated Near-Storage Data Analytics on SSD[END_REF], graph processing [START_REF] Hajinazar | SIMDRAM: A Framework for Bit-Serial SIMD Processing Using DRAM[END_REF][START_REF] Beamer | Direction-Optimizing Breadth-First Search[END_REF][START_REF] Besta | SISA: Set-Centric Instruction Set Architecture for Graph Mining on Processingin-Memory Systems[END_REF][START_REF] Li | Pinatubo: A Processing-in-Memory Architecture for Bulk Bitwise Operations in Emerging Non-Volatile Memories[END_REF][START_REF] Gao | ParaBit: Processing Parallel Bitwise Operations in NAND Flash Memory Based SSDs[END_REF], genome analysis [START_REF] Alser | GateKeeper: A New Hardware Architecture for Accelerating Pre-alignment in DNA Short Read Mapping[END_REF][START_REF] Loving | BitPAl: A Bit-Parallel, General Integer-Scoring Sequence Alignment Algorithm[END_REF][START_REF] Xin | Shifted Hamming Distance: A Fast and Accurate SIMD-Friendly Filter to Accelerate Alignment Verification in Read Mapping[END_REF][START_REF] Cali | GenASM: A High-Performance, Low-Power Approximate String Matching Acceleration Framework for Genome Sequence Analysis[END_REF][START_REF] Kim | GRIM-Filter: Fast Seed Location Filtering in DNA Read Mapping Using Processing-in-Memory Technologies[END_REF][START_REF] Lander | Initial Sequencing and Analysis of the Human Genome[END_REF][START_REF] Altschul | Basic Local Alignment Search Tool[END_REF][START_REF] Myers | A Fast Bit-Vector Algorithm for Approximate String Matching Based on Dynamic Programming[END_REF], cryptography [START_REF] Han | Optical Image Encryption Based on XOR Operations[END_REF][START_REF] Tuyls | XOR-based Visual Cryptography Schemes[END_REF][START_REF] Manavski | CUDA Compatible GPU as an Efficient Hardware Accelerator for AES Cryptography[END_REF], set operations [START_REF] Seshadri | Ambit: In-Memory Accelerator for Bulk Bitwise Operations Using Commodity DRAM Technology[END_REF][START_REF] Besta | SISA: Set-Centric Instruction Set Architecture for Graph Mining on Processingin-Memory Systems[END_REF], and hyper-dimensional computing [START_REF] Kanerva | Sparse Distributed Memory and Related Models[END_REF][START_REF] Kanerva | Hyperdimensional Computing: An Introduction to Computing in Distributed Representation with High-Dimensional Random Vectors[END_REF][START_REF] Karunaratne | In-memory Hyperdimensional Computing[END_REF][START_REF] Imani | Exploring Hyperdimensional Associative Memory[END_REF]. Second, bulk bitwise operations can significantly benefit from NDP. Due to the simple nature of bitwise operations, the performance and energy efficiency of bulk bitwise operations are bottlenecked by data movement between the computation units and the memory hierarchy in conventional systems [7-9, 21, 37, 38]. NDP can effectively mitigate such data movement at low cost by supporting simple bulk bitwise operations at very high levels of concurrency near or inside memory devices (e.g., in all memory banks or subarrays [START_REF] Seshadri | Ambit: In-Memory Accelerator for Bulk Bitwise Operations Using Commodity DRAM Technology[END_REF][START_REF] Hajinazar | SIMDRAM: A Framework for Bit-Serial SIMD Processing Using DRAM[END_REF][START_REF] Kim | A Case for Exploiting Subarray-Level Parallelism (SALP) in DRAM[END_REF]).

Among many existing NDP solutions, only one recent work, ParaBit [START_REF] Gao | ParaBit: Processing Parallel Bitwise Operations in NAND Flash Memory Based SSDs[END_REF], proposes an in-flash processing technique for bulk bitwise operations inside a NAND flash chip. ParaBit leverages the latching circuits that are commonly employed in modern NAND flash chips [START_REF] Micheloni | Inside NAND Flash Memories[END_REF][START_REF] Leong | Random Cache Read Using a Double Memory[END_REF][START_REF] Macronix | Technical Note: Improving NAND Throughput with Two-Plane and Cache Operations[END_REF][START_REF] Micron | NAND Flash Memory Data Sheet: MT29F16G08ABABA, MT29F32G-08AFABA[END_REF][START_REF] Samsung | 32Gb A-die NAND Flash Datasheet[END_REF][START_REF] Toshiba | NAND Memory Toggle DDR1.0 Technical Data Sheet[END_REF] (see Section 2.1). Existing NAND flash chips support a command called cache read [START_REF] Leong | Random Cache Read Using a Double Memory[END_REF][START_REF] Macronix | Technical Note: Improving NAND Throughput with Two-Plane and Cache Operations[END_REF][START_REF] Micron | NAND Flash Memory Data Sheet: MT29F16G08ABABA, MT29F32G-08AFABA[END_REF][START_REF] Samsung | 32Gb A-die NAND Flash Datasheet[END_REF][START_REF] Toshiba | NAND Memory Toggle DDR1.0 Technical Data Sheet[END_REF] whose purpose is to improve the performance of a read operation by enabling the transfer of data from the NAND flash chip to the flash controller in parallel with the sensing of a subsequent read operation. To enable cache read, existing chips include a cache latch in addition to the sensing latch ( 4 in Figure 2). We describe the operation and implementation of this cache latch since it is important for and used in Parabit.

Figure 6(a) illustrates the common latching circuit of a modern NAND flash chip equipped with a cache latch (right part) in addition to the sensing latch (left part) described in Figure 3. A NAND flash chip initializes the cache latch in the precharge step by activating M 4 , which pulls down node OUT L and thus makes OUT L =1. Until enabling M 3 , the sensing latch (i.e., the value at node OUT S ) cannot affect the data stored in the cache latch. This feature enables the chip to read new data (into the sensing latch) while transferring the previously-read data in the cache latch to the flash controller.

Figures 6(b) and 6(c) describe how ParaBit performs inflash bitwise AND and OR operations, respectively, by intelligently controlling the latching circuit shown in Figure 6(a). 5Bitwise AND in ParaBit. To perform a bitwise AND operation, ParaBit serially reads operands sharing the same bitline (lines 3 and 4 in Figure 6(b)) while neither enabling M 3 nor reinitializing the sensing latch. Doing so allows ParaBit to keep the result of the bitwise AND of the serially read operands in the sensing latch (node OUT S ). If the read cell stores '0' (i.e., if the value at SO is '1'), enabling only M 2 causes OUT S =0 regardless of the current value at node OUT S . When the cell stores '1' (i.e., when SO=0), sensing the cell does not change the value at node OUT S . In other words, sensing new data N leads to OUT S =1 only if both the new data N and the current value at node OUT S are '1', which is equivalent to OUT S =(N AND OUT S ). After serially reading all the operands sharing the same bitline (which results in bitwise AND of all the operands at node OUT S ), ParaBit enables M 3 to move the result from the sensing latch to the cache latch (line 5). Bitwise OR in ParaBit. To perform a bitwise OR operation, ParaBit also serially reads the operands sharing the same bitline (lines 2 to 5 in Figure 6(c)) as in bitwise AND, but it reinitializes the sensing latch (line 3) before sensing each read and activates M 3 (line 5, i.e., moves the result from the sensing latch to the cache latch) after sensing each operand. Doing so keeps the result of the bitwise OR of the read operands sharing the same bitline in the cache latch (node OUT L ). If newly read data N in the sensing latch (i.e., OUT S =N) is '1', enabling M 3 results in OUT L =1 regardless of the current value of node OUT L . When N=OUT S ='0', activating M 3 does not change the value at node OUT L . Hence, latching new data N to the cache latch causes OUT L =0 only if both the new data N and the current value of OUT L are '0', which is equivalent to OUT L =(N OR OUT L ). Benefits of In-Flash Processing. Figure 7 shows an example where ParaBit-like in-flash processing (IFP) can provide benefits over conventional outside-storage processing (OSP) and in-storage processing (ISP) that process data using compute units in the host CPU/GPU and inside the SSD, respectively. Figure 7(a) depicts the target SSD considered in this example. The SSD has eight channels, each of which is shared by four 2-plane dies (i.e., 64 planes in total) with 16-KiB pages. We assume a page-read latency (tR) of 60 µs, a channel bandwidth of 1.2 GB/s between a channel and the SSD controller [START_REF] Kang | A 512Gb 3-Bit/Cell 3D 6th-Generation V-NAND Flash Memory with 82MB/s Write Throughput and 1.2Gb/s Interface[END_REF], and an external I/O bandwidth of 8 GB/s (4-lane PCIe Gen4) between the host and the SSD. one of OSP, ISP, and IFP, respectively, to perform bulk bitwise OR operations on three 1-MiB bit vectors A, B, and C (i.e., A OR B OR C). We assume that each bit-vector is distributed across all the 64 planes in the SSD as shown in Figure 7(a). Figure 7(b) shows the execution timeline of bulk bitwise operations for one of the eight channels in OSP. To achieve the highest possible performance using OSP, the host must perform concurrent multi-plane reads across the NAND flash dies for each operand. The operands themselves are read sequentially (tR for operands A, B and C in Figure 7(b)). Once an operand is read to the sensing latch, it can be transferred to the SSD controller (tDMA) and subsequently to the host (tEXT) while a read is simultaneously being performed on the next operand. Given the flash channel and external I/O bandwidth, each die requires tDMA=27 µs and tEXT=4 µs to transfer 32-KiB data (2 planes×16-KiB page) to the SSD controller and to the host, respectively. While tEXT per die is lower than tR and tDMA, the data movement between the host and the SSD (called External I/O in Figure 7(b)) bottlenecks performance, as the SSD serially transfers all the bit vectors from the eight channels through the external I/O interface for computation in the host CPU.

Figure 7(c) shows the execution timeline of a channel in the ISP approach. ISP can use per-channel accelerators (e.g., [START_REF] Torabzadehkashi | Catalina: In-Storage Processing Acceleration for Scalable Big Data Analytics[END_REF][START_REF] Mailthody | Deepstore: In-Storage Acceleration for Intelligent Queries[END_REF][START_REF] Mansouri Ghiasi | GenStore: A High-Performance In-Storage Processing System for Genome Sequence Analysis[END_REF][START_REF] Kang | Enabling Cost-effective Data Processing with Smart SSD[END_REF][START_REF] Kim | Behemoth: A Flashcentric Training Accelerator for Extreme-scale {DNNs}[END_REF]) to reduce external data movement by performing computation in the SSD controller and transferring only the computation result to the host system. However, the SSDinternal data movement between the SSD controller and NAND flash dies (called Internal I/O in Figure 7(c)) becomes the new performance and energy bottleneck in ISP. This is because the internal data movement must be serialized through the channel shared by the NAND flash dies, while the dies connected to the channel can concurrently perform page reads.

Figure 7(d) shows the execution timeline of a channel for the state-of-the-art IFP approach, ParaBit. ParaBit can effectively reduce both internal and external data movement by performing the computation as the operands are read within the NAND flash chips and transferring only the computation result to the SSD controller and the host, thereby significantly improving performance and energy efficiency. In state-of-the-art IFP, internal data movement between the SSD controller and the NAND flash dies is not a bottleneck, but sensing the data becomes a bottleneck, as Figure 7(d) shows.

Limitations of State-of-the-Art

We identify two key limitations of ParaBit, the state-of-the-art IFP technique for bulk bitwise operations. Unexploited Potential of IFP Capabilities. Despite ParaBit's benefits over other processing approaches, we identify that Para-Bit still misses a large potential of exploiting IFP to significantly improve the performance and energy efficiency of bulk bitwise operations. As explained in Section 3.1, ParaBit serially reads every operand from a bitline (tR in Figure 7(d)). Each read of an operand requires a costly (i.e., slow) sensing operation in Para-Bit. Such serial reading of every operand poses a big bottleneck when operations need to be performed across more than two operands. We identify that NAND flash memory has inherent capability to perform bulk bitwise operations on a large number of operands (i.e., tens) at once (i.e., using only a single sensing operation) due to (i) its unique cell-array structure and (ii) flash cells' operation principles. First, as explained in Section 2.1, in NAND flash memory, several tens or more than a hundred of flash cells are serially connected (as in digital NAND gates), and thousands of NAND strings are connected to a single BL (as in digital NOR gates). Second, a flash cell is similar to a normal MOS transistor, a basic component for digital logic gates, in its structure and operation principles. These observations lead us to develop a new IFP technique (described in Section 4) that does not have the sensing bottleneck that the state-of-the-art has: our new technique performs bulk bitwise operations on multiple operands with only a single sensing operation. Limited Applicability. ParaBit's applicability is limited to highly error-tolerant applications because it is not designed to take into account the highly error-prone nature of NAND flash memory. As explained in Section 2.2, due to the errorprone nature of NAND flash memory, using ECC and data randomization is essential to guaranteeing the reliability of stored data. However, ParaBit cannot leverage any of the widelyused ECC and randomization techniques, as it performs bulk bitwise operations while reading the operands. Bitwise AND or OR operations on ECC-encoded or randomized data lead can easily lead to incorrect results during ECC decoding or de-randomization. While storing fewer bits per cell can reduce RBER compared to advanced MLC techniques (e.g., triple-level cell (TLC) or quad-level cell (QLC) techniques), ParaBit can be used only when the application can tolerate the NAND flash chips' RBER (pre-correction error rate), which is still very large as reported in prior works [START_REF] Cai | Error Characterization, Mitigation, and Recovery in Flash-Memory-Based Solid-State Drives[END_REF][START_REF] Cai | Vulnerabilities in MLC NAND Flash Memory Programming: Experimental Analysis, Exploits, and Mitigation Techniques[END_REF][START_REF] Cai | Data Retention in MLC NAND Flash Memory: Characterization, Optimization, and Recovery[END_REF][START_REF] Cai | Error Analysis and Retention-aware Management for NAND Flash Memory[END_REF].

To better understand the impact of NAND flash reliability on the applicability of IFP, we perform real-device characterization using 160 TLC NAND flash chips (see Section 5.1 for more detail on our methodology). Figure 8 shows the average RBER across 3,686,400 WLs randomly selected from 160 NAND flash chips we analyze. We measure each WL's RBER (without applying ECC) when (i) programming it in (a) SLC mode and (b) MLC mode and (ii) enabling (left) and disabling (right) data randomization under different P/E-cycle counts (PEC) and retention ages.

We make three key observations. First, even when using SLC-mode programming with data randomization (left plot in Figure 8(a)), the average RBER is significantly (i.e., around 12 orders of magnitude) higher than the uncorrectable bit-error rate (UBER) requirement of an SSD (e.g., <10 -15 to 10 -16 [START_REF] Cai | Error Characterization, Mitigation, and Recovery in Flash-Memory-Based Solid-State Drives[END_REF][START_REF] Cai | Vulnerabilities in MLC NAND Flash Memory Programming: Experimental Analysis, Exploits, and Mitigation Techniques[END_REF][START_REF] Cai | Data Retention in MLC NAND Flash Memory: Characterization, Optimization, and Recovery[END_REF][START_REF] Cai | Error Analysis and Retention-aware Management for NAND Flash Memory[END_REF][START_REF] Gray | Empirical Measurements of Disk Failure Rates and Error Rates[END_REF][START_REF] Cox | JEDEC SSD Endurance Workloads[END_REF]). Second, disabling data randomization (right plots in Figures 8(a) and 8(b)) significantly increases the RBER of stored data by 1.91× and 4.92× in SLC mode and MLC mode, respectively. Third, as expected, using MLCmode programming (plots in Figure 8(b)) significantly degrades the reliability of stored data, leading to up to 4× the RBER of SLC-mode programming. Based on our observations, we conclude that the state-of-the-art IFP technique is hard to adopt for applications that cannot tolerate a bit error rate range of 8.6×10 -4 to 1.6×10 -2 (the RBER range across the two plots in Figure 8(b)), which is very large.

Our goal in this work is to develop a new in-flash processing technique that (i) maximizes performance and energy efficiency by fully exploiting the inherent computation capability of NAND flash memory to enable many-operand computation with a single sensing operation and (ii) provides high data reliability (i.e., zero bit errors in computation results) so that it is applicable to a wide range of error-intolerant applications.

Flash-Cosmos: Key Mechanisms

We present the two key ideas of Flash-Cosmos (Flash Computation with One-Shot Multi-Operand Sensing) that overcome the limitations of the state-of-the-art.

Multi-Wordline Sensing (MWS)

Key Idea. MWS is based on our key observation that simultaneously reading multiple WLs in NAND flash memory re-sults in bitwise AND or OR of the WLs. Figure 9 shows how MWS enables a NAND flash chip to perform bulk bitwise (a) AND and (b) OR operations on two operands with a single sensing operation. While Figure 9 shows bulk bitwise operations on only two operands, Flash-Cosmos can support multi-operand bulk bitwise operations (on tens of operands). For bitwise AND, the NAND flash chip simultaneously applies V REF to multiple target WLs that contain the source operands of the bulk bitwise operation (WL x and WL z in Figure 9(a)) within a block, which we call intra-block MWS. 6 If the chip applies V PASS to all non-target WLs (e.g., WL y and WL w ) as in a regular read, a BL can be sensed as discharged only when all the target cells in the corresponding NAND string are erased (i.e., V TH <V REF ). In other words, the sensing circuitry would read a BL as '1' only if all the target cells store '1' (BL 1 in Figure 9(a)) and it would read a BL as '0' if any of the target cells stores '0' (BL 2 , BL 3 , BL 4 in Figure 9(a)), which is equivalent to the bitwise AND operation. The intra-block MWS operation can easily be generalized to more than two operands by applying V REF to more than two wordlines, leading to the computation of the bitwise AND of all such wordlines with a single sensing operation. For bitwise OR, we introduce inter-block MWS, where the chip simultaneously applies V REF to multiple WLs (WL i and WL k in Figure 9(b)) of different blocks while applying V PASS to all non-target WLs in those blocks. Doing so causes a BL to be discharged if at least one of the target cells in the corresponding NAND string is erased. In other words, the sensing circuitry would read a BL as '0' only if all the target cells in the BL store '0' (BL 4 in Figure 9(b)) and it would read a BL as '1' if any of the target cells stores '1'(BL 1 , BL 2 , BL 3 in Figure 9(b)), which is equivalent to the bitwise OR operation. The inter-block MWS operation can easily be generalized to more than two operands by applying V REF to more than two wordlines, each in a different block, leading to the computation of the bitwise OR of all such wordlines across different blocks with a single sensing operation.

As mentioned above, both types of MWS are capable of single-sensing bulk bitwise operations even for more than two operands. This property enables MWS to be more powerful than prior NDP proposals that leverage multi-wordline (or multirow) activation for in-memory computation in two aspects. First, although prior works also propose to activate multiple wordlines to perform bulk bitwise operations inside various memory devices [START_REF] Seshadri | Ambit: In-Memory Accelerator for Bulk Bitwise Operations Using Commodity DRAM Technology[END_REF][START_REF] Seshadri | Fast Bulk Bitwise AND and OR in DRAM[END_REF][START_REF] Li | Pinatubo: A Processing-in-Memory Architecture for Bulk Bitwise Operations in Emerging Non-Volatile Memories[END_REF][START_REF] Aga | Compute Caches[END_REF][START_REF] Choi | An In-Flash Binary Neural Network Accelerator with SLC NAND Flash Array[END_REF], the number of source operands that can be computed on at the same time is limited (usually to only two), thereby requiring sequential sensing of more operands like ParaBit. 7 Second, there exist several proposals that leverage multi-wordline activation to perform accumulative computation (e.g., multiply-accumulate operations) inside NAND flash memory [START_REF] Choi | An In-Flash Binary Neural Network Accelerator with SLC NAND Flash Array[END_REF][START_REF] Han | A Novel Convolution Computing Paradigm Based on NOR Flash Array with High Computing Speed and Energy Efficiency[END_REF][START_REF] Shim | GP3D: 3D NAND based In-memory Graph Processing Accelerator[END_REF][START_REF] Merrikh-Bayat | High-Performance Mixed-Signal Neurocomputing With Nanoscale Floating-Gate Memory Cell Arrays[END_REF][START_REF] Tseng | In-Memory-Searching Architecture Based on 3D-NAND Technology with Ultra-High Parallelism[END_REF][START_REF] Wang | Three-Dimensional NAND Flash for Vector-Matrix Multiplication[END_REF][START_REF] Lue | Optimal Design Methods to Transform 3D NAND Flash into a High-Density, High-Bandwidth and Low-Power Nonvolatile Computing in Memory (nvCIM) Accelerator for Deep-Learning Neural Networks (DNN)[END_REF], but they rely on analog current sensing, which requires significant changes to regular flash chips (for instance, in a system with multiple memristor-based crossbar arrays, the addition of a precise analog-to-digital converter (ADC) to each array is costly (e.g., each ADC accounts for 58% of the chip power and 31% of the chip area even when each ADC is shared across 128 output columns [START_REF] Shafiee | ISAAC: A Convolutional Neural Network Accelerator with In-Situ Analog Arithmetic in Crossbars[END_REF])).

Intra-and inter-block MWS can be combined to perform complex bitwise AND and OR operations. 8 Suppose that blocks Blk l and Blk n in Figure 9(b) have N pages (WLs), each of which stores bit vectors A i and B i (1≤i≤N), respectively. If we simultaneously apply V REF to all the WLs in the two blocks, the chip would read a BL j as '1', only when at least one of Blk l and Blk n has a NAND string in which every cell stores '1', which is equivalent to:

(A 1, j • ... • A N, j ) + (B 1, j • ... • B N, j ) (1)
Feasibility & Overhead. Applying MWS to commodity NAND flash chips is highly feasible at low cost. In fact, existing chips already use/support both inter-and intra-block MWS for other purposes. For example, after erasing a block, a NAND flash chip needs to check if all the cells in the block are completely erased (called erase verify) by simultaneously applying V REF to all the cells [START_REF] Micheloni | Inside NAND Flash Memories[END_REF], i.e., the chip performs intra-block MWS for all WLs in the block. Also, manufacturers commonly design a chip to support the activation of multiple WLs (i.e., intra-block MWS) and multiple blocks (i.e., inter-block MWS), to perform multi-page reads/writes and multi-block erases that are critical for rapid testing of the chip [START_REF] Micheloni | Inside NAND Flash Memories[END_REF].

The MWS scheme has two potential drawbacks. First, an inter-block MWS would consume more power compared to a regular page read since it needs to activate more blocks, which requires charging of all the WLs in multiple blocks. Note that an intra-block MWS operation's power consumption is lower compared to a regular read because it applies V REF to additional target WLs, to which a regular read would apply V PASS (which is several times larger than V REF ). Second, the latency for a reliable MWS operation may be longer than the default read latency tR since the target data of an MWS operation is programmed without randomization using the ESP scheme (explained in Section 4.2). Without randomization, a NAND string can have low resistance (e.g., when all the cells are in the erased state) compared to with randomization (where around 50% of the cells are always erased), which may increase the precharge latency and the evaluation latency (see Figure 2) for reliable operation. We evaluate the potential drawbacks in Section 5.

Enhanced SLC-Mode Programming (ESP)

Key Idea. ESP enhances existing SLC-mode programming by maximizing the margin between the two V TH states. Figure 10 shows how ESP improves reliability compared to regular SLCmode programming. NAND flash memory commonly uses the incremental step pulse programming (ISPP) scheme [START_REF] Jeong | Lifetime Improvement of NAND Flashbased Storage Systems Using Dynamic Program and Erase Scaling[END_REF][START_REF] Suh | A 3.3 V 32 Mb NAND Flash Memory with Incremental Step Pulse Programming Scheme[END_REF] to precisely control the threshold voltage (V TH ) of a NAND flash cell and to narrow the width of V TH state distributions. As depicted in Figure 10(a), the ISPP scheme gradually increases the program voltage from V PGM1 with a certain step voltage (∆V ISPP ), until the V TH level of every cell in the WL reaches its target voltage V TGT . At the end of each ISPP step, the chip checks if each cell's V TH level has reached its V TGT (i.e., Verify in Figure 10(a)), and excludes such cells from the next ISPP step. The key idea of ESP is to perform additional ISPP steps (after performing regular SLC-mode programming), using (i) an increased V TGT value (for each cell), which further moves the programmed V TH state to a higher voltage level, and (ii) a decreased ∆V ISPP value, which narrows the width of the programmed V TH state distribution. Doing so significantly increases the margins from the new read-reference voltage (V REF ') to both the erased and the programmed V TH states, as shown in Figure 10(b), which makes the cells less vulnerable to many error sources present in NAND flash memory [START_REF] Cai | Error Characterization, Mitigation, and Recovery in Flash-Memory-Based Solid-State Drives[END_REF]. Feasibility & Overhead. Applying ESP to commodity NAND flash chips is highly feasible at low cost due to two reasons. First, modern MLC NAND flash memory commonly supports SLC-mode programming for several reasons, e.g., storing reliability-sensitive data [START_REF] Kim | Evanesco: Architectural Support for Efficient Data Sanitization in Modern Flash-based Storage Systems[END_REF], managing an SLC write buffer [START_REF] Lee | FlexFS: A Flexible Flash File System for MLC NAND Flash Memory[END_REF] or using unreliable cells for data storage in case they cannot be used in MLC mode [START_REF] Jimenez | Phoenix: Reviving MLC Blocks as SLC to Extend NAND Flash Devices Lifetime[END_REF]. Second, commodity NAND flash chips can tune ISPP parameters [START_REF] Jeong | Lifetime Improvement of NAND Flashbased Storage Systems Using Dynamic Program and Erase Scaling[END_REF][START_REF] Shim | Exploiting Process Similarity of 3D Flash Memory for High Performance SSDs[END_REF][START_REF] Kim | SARO: A State-Aware Reliability Optimization Technique for High Density NAND Flash Memory[END_REF][START_REF] Feng | Using Disturbance Compensation and Data Clustering (DC)2 to Improve Reliability and Performance of 3D MLC Flash Memory[END_REF][START_REF] Wang | Using Dynamic Allocation of Write Voltage to Extend Flash Memory Lifetime[END_REF][START_REF] Dong | Using Data Postcompensation and Predistortion to Tolerate Cell-to-Cell Interference in MLC NAND Flash Memory[END_REF] using the SET FEATURE command [START_REF] Park | Reducing Solid-State Drive Read Latency by Optimizing Read-Retry[END_REF][START_REF]Open NAND Flash Interface Specification Revision 4.2[END_REF], which is essential to post-fabrication optimization of NAND flash chips. The SET FEATURE command is also used to dynamically adapt to changes in P/E cycles [START_REF] Cai | Reliability Issues in Flashmemory-based Solid-state Drives: Experimental Analysis, Mitigation, Recovery[END_REF][START_REF] Cai | Error Characterization, Mitigation, and Recovery in Flash-Memory-Based Solid-State Drives[END_REF] and reliability characteristics of NAND flash cells [START_REF] Cai | Reliability Issues in Flashmemory-based Solid-state Drives: Experimental Analysis, Mitigation, Recovery[END_REF][START_REF] Cai | Error Characterization, Mitigation, and Recovery in Flash-Memory-Based Solid-State Drives[END_REF].

ESP has two drawbacks. First, it increases the program latency by performing additional ISPP steps. Second, because it uses SLC-mode programming, it requires double the WLs to store the same amount of data compared to MLC-mode pro-gramming. We provide a detailed analysis of the performance and capacity overheads of ESP in Section 8.3.

Real Device Characterization

This section presents our characterization of 160 real 3D NAND flash chips to validate the feasibility, performance, and reliability of the two key mechanisms of Flash-Cosmos.

Characterization Methodology

Infrastructure. We use an FPGA-based testing platform that contains a custom NAND flash controller and a temperature controller. The flash controller supports all the commands implemented in our NAND flash chips, including not only basic read/program/erase commands but also various test-mode commands necessary to dynamically change operating parameters (e.g., the ISPP step voltage and other timing parameters) and simultaneously activate multiple WLs. The temperature controller maintains a NAND flash chip within ±1 • C of the target temperature. This feature allows us to (i) test all the chips under the same operating temperature (85 • C) and (ii) accelerate retention loss based on Arrhenius's Law [START_REF] Arrhenius | Über die Dissociationswärme und den Einfluss der Temperatur auf den Dissociationsgrad der Elektrolyte[END_REF], which is essential to real device characterization under long retention ages (e.g., 1 year) while maintaining reasonable testing time. We characterize 160 48-layer 3D TLC NAND flash chips, where a NAND string consists of 48 flash cells and the page size is 16 KiB. Under regular SLC-mode programming, the chips have a read latency tR=22.5 µs and a program latency tPROG=200 µs. Methodology. To minimize the potential inaccuracies in our characterization results, we carefully design our experiments following the JEDEC standards [START_REF] Jedec | JESD47: Stress-Test-Driven Qualification of Integrated Circuits[END_REF][START_REF] Jedec | JESD22-A117[END_REF] that specify the test methodology recommended for evaluating the reliability of commercial-grade NAND flash products. To ensure highconfidence reliability tests, JEDEC recommends testing more than 39 flash chips from three different wafers. Our 160 flash chips are fabricated from five different wafers, and we select 120 blocks (not sub-blocks) from each of the 160 chips at random locations. We test every page in each selected block (a total of 3,686,400 WLs) to obtain statistically significant results.

To evaluate Flash-Cosmos' reliability under the worst-case operating conditions, we measure each WL's RBER under a 1-year retention age at 30 • C [START_REF] Cox | JEDEC SSD Endurance Workloads[END_REF] and 10K P/E cycles. 9 We increase a block's P/E-cycle count by repeating the cycle of programming every page in the block (in TLC mode) and erasing the entire block. Unless specified otherwise, we program each page using the checkered data pattern, the worst-case data pattern for NAND flash reliability where any two adjacent cells (both horizontally and vertically) are programmed either to the highest V TH state (e.g., the P7 state in TLC mode) or to the lowest V TH state (i.e., the Erased state). 9 In our RBER measurements, we exclude faulty cells that introduce permanent (non-transient) errors due to defects in fabrication since (i) faulty cells can be profiled and excluded for the purpose of Flash-Cosmos, and (ii) manufacturers can significantly reduce the faulty-cell fraction by specially designing chips for Flash-Cosmos at the cost of yield and/or technology node size.

Characterization Results

ESP Latency & Reliability. We first study the trade-off between the reliability and program latency of the ESP scheme. Figure 11 shows the average RBER per 1-KiB data when we program the WLs while increasing the ESP latency tESP for more precise ISPP control. We plot the RBER of the worst, median, and best block out of all the tested blocks and normalize the increased tESP values to the default program latency tPROG for regular SLC-mode programming.

We make two key observations from Figure 11. First, it is possible to avoid raw bit errors without data randomization by enhancing SLC-mode programming, at the cost of an increase in program latency. 10 When we increase tESP by more than 90% compared to tPROG, we observe zero bit errors in our tested pages that contain more than 4.83×1011 bits in total, which means that the statistical RBER of ESP is lower than 2.07×10 -12 . 11 Second, the ESP scheme's reliability improvement significantly increases with tESP. For the median block, increasing tESP by 60% achieves an order of magnitude RBER reduction. We conclude that the ESP scheme is essential for achieving effectively zero bit errors in the computation results of in-flash processing and thus ESP can increase applicability of in-flash processing to a much wider range of applications. MWS Latency & Reliability. We measure tMWS, the minimum latency for an MWS operation to achieve zero bit errors in all the tested blocks. First, we perform intra-block MWS operations while changing the number of read WLs from 1 to 48 (the number of WLs in a NAND string). Second, we perform inter-block MWS operations on all WLs in the target blocks while changing the number of activated (target) blocks from 1 to 32. In both experiments, we first increase a target block's P/E cycle count using a checkered data pattern. Next, we check the correctness of intra-block MWS under high disturbance and noise, induced by programming the block using a different data pattern. This new data pattern maximizes the resistance of NAND strings in the block by programming the block to meet two conditions; (i) the number of cells that store bit value '1' (i.e., '1' cells) must be less than two; (ii) if a NAND string has a '1' cell, the cell must be in one of the MWS operations' target wordlines. As explained in Section 4.1, bypassing data randomization can affect the read latency (both tR and tMWS) for reliable operation by decreasing a NAND string's resistance compared to the typical read of randomized data. We validate the correctness of MWS by comparing the result of MWS operations that we obtain from the real chips to the correct results of the bitwise operations on the stored data.

Figures 12 and13 show the tMWS value (as a multiple of tR) for intra-and inter-block MWS operations, respectively. We make three key observations from the results. First, bypassing data randomization does not increase a regular read operation's latency. As shown in Figure 12, using the default read latency introduces no error when we read only a single WL in a block. Second, intra-block MWS does not significantly increase the read latency. Even when we simultaneously read all the 48 WLs in a block, tMWS is only 3.3% higher than tR. When we perform intra-block MWS on eight (or fewer) WLs, tMWS is less than 1% higher than tR. Third, although inter-block MWS (shown in Figure 13) affects tMWS more significantly compared to intra-block MWS, it can still provide significant benefits over individual reads of the same WLs. As shown in Figure 13, when simultaneously reading WLs in 32 different blocks, tMWS is 36.3% higher than tR. This is because activating multiple blocks significantly increases the number of WLs to precharge at the same time. The increased WL-precharge time is mostly hidden by the BL-precharge time until we activate eight blocks, but it becomes larger than the BL-precharge time as the number of activated blocks further increases, which causes the latency of a reliable MWS operation to be longer than the latency of a regular page read. However, the increased latency of MWS on 32 WLs (1.363×tR) is much lower than the latency to individually (serially) read 32 WLs (32×tR).

Based on our observations, we draw three major conclusions. First, we demonstrate that real commodity NAND flash chips can reliably support both intra-block and inter-block MWS operations, so computer architects can build a system that leverages Flash-Cosmos, as long as they have access to the command interfaces used for our characterization. Second, both types of MWS significantly accelerate in-flash bulk bitwise operations in commodity NAND flash chips at low cost. Third, it is possible to support both types of MWS with a small latency increase over the default read latency. If we limit the maximum number of simultaneously-activated blocks for inter-block MWS to 4, we can support any MWS operation with a fixed latency (tMWS) only 3.3% higher than tR. Maximum Power Consumption of Inter-Block MWS. As explained in Section 4.1, inter-block MWS consumes more power compared to a regular page read due to the higher number of activated WLs at the same time. Understanding the impact of MWS on power consumption is important because a NAND flash-based SSD has a limited power budget (e.g., 75W for PCIe Gen4 SSDs [START_REF] Pcisig | PCIe Specification[END_REF]). Figure 14 shows the average power consumption of a NAND flash chip when we perform inter-block MWS as a function of the number of simultaneously-activated blocks. To measure the worst-case power consumption, we read only one WL per each block (i.e., we apply V REF to only one WL per block while applying V PASS (>V REF ) to all non-target WLs). We normalized all values in Figure 14 to the average power consumption of a regular page-read operation.

We make three observations. First, the power consumption of a NAND flash chip considerably increases with the number of activated blocks for inter-block MWS. Increasing the number of activated blocks from one to two increases the average power consumption by about 34%. Second, despite the non-trivial increase in power consumption, it is possible to support inter-block MWS within the SSD's power budget. Until we activate four blocks, the power consumption of inter-block MWS remains lower than that of an erase operation. Third, inter-block MWS is more energy efficient compared to serial reads of the same WLs. For example, performing an inter-block MWS operation on four different blocks would cause about 80% power increase compared a regular read, but due to its negligible latency increase (3.3%), it significantly reduces the energy consumption by 53% compared to individual reads of the four WLs. We conclude that, with a proper limit on the number of inter-block MWS, Flash-Cosmos would not require an increase in the power budget of commodity SSDs.

Design of Flash-Cosmos

We present our design of Flash-Cosmos to support efficient in-flash bulk bitwise operations.

Enhanced Computation Capability

We enhance the basic capability of Flash-Cosmos (beyond the bitwise AND and bitwise OR operations introduced in Section 3.1) in two ways. Supporting Other Bitwise Operations. We design Flash-Cosmos to also support bitwise NOT/NAND/NOR/XOR/XNOR operations by leveraging two existing features that are widely supported in real NAND flash memory chips. First, as explained in Section 2.1, modern NAND flash memory commonly supports inverse reads [START_REF] Lee | High-Performance 1-Gb-NAND Flash Memory with 0.12-µm Technology[END_REF], which enables Flash-Cosmos to perform not only bitwise NOT operations but also bitwise NAND and NOR operations. Flash-Cosmos performs NOT of a WL by simply reading the WL in inverse-read mode. If we perform intra-block (inter-block) MWS while controlling the sensing latch circuit in inverse-read mode, the sensed data would be the inverse value of the bitwise AND (OR) of all the WLs simultaneously read, i.e., bitwise NAND (NOR) by definition.

Second, many modern NAND flash chips (including the 160 chips used in our real-device characterization, Section 5) support a bitwise XOR operation between the data in different latches (i.e., two/three additional latches available in a NAND flash chip for MLC/TLC program operation) [START_REF] Kim | A 21 nm High Performance 64 Gb MLC NAND Flash Memory with 400 MB/s Asynchronous Toggle DDR Interface[END_REF][START_REF] Kim | A 512-Gb 3-b/Cell 64-Stacked WL 3-D-NAND Flash Memory[END_REF]. This feature is essential for supporting on-chip randomization [START_REF] Kim | A 21 nm High Performance 64 Gb MLC NAND Flash Memory with 400 MB/s Asynchronous Toggle DDR Interface[END_REF] and improving testability (e.g., it significantly reduces a NAND flash chip's test time by enabling comparison of programmed data to a golden value without reading the data out of the chip [START_REF] Lu | Fault Leveling Techniques for Yield and Reliability Enhancement of NAND Flash Memories[END_REF][START_REF] Cao | An Efficient Built-in Error Detection Methodology with Fast Page-oriented Data Comparison in 3D NAND Flash Memories[END_REF]). By using this feature along with inverse reads, Flash-Cosmos can also support bitwise XNOR operations since

A XNOR B ≡ A XOR B ≡ A XOR B ( 2
)
To be specific, Flash-Cosmos uses the existing XOR logic while performing an inverse read for either of the two operands.

Improving the Performance of the Bitwise OR Operation.

The performance of bitwise OR using inter-block MWS is limited compared to that achieved by bitwise AND using intra-block MWS. As demonstrated in Section 5.2, commodity NAND flash chips can perform bitwise AND of all the WLs in a block via a single intra-block MWS operation. However, the maximum number of operands in inter-block MWS is limited due to high power consumption.

We can remove this restriction on the maximum number of activated blocks by performing bitwise OR using 1) intra-block MWS along with 2) inverse reads and 3) taking advantage of De Morgan's laws. If we store operands in a block with their inverse data (instead of the original data), we can perform bitwise OR of the operands with a single intra-block MWS operation by leveraging the inverse read mode and De Morgan's laws:

(A 1 + ... + A N ) ≡ (A 1 • ... • A N ) (3)
Note that (i) Flash-Cosmos can return the original data of such operands via inverse reads (∵A≡NOT A), and (ii) inter-block MWS is still useful for combined bitwise AND/OR operations as explained in Section 4.1 (Equation 1).

Increasing Maximum Number of Operands for IFP. Flash-Cosmos alone cannot completely avoid off-chip data transfer for bitwise AND/OR/NAND/NOR operations if the number of operands exceeds the number of WLs in a block. This is because intrablock MWS involves a single sensing operation to read all WLs within a block, thereby limiting the maximum number of operands to the number of WLs in a block. Inter-block MWS has a stronger constraint on the maximum number of operands due to the limited power budget as explained in Section 5.2.

Fortunately, Flash-Cosmos can accumulate the results of multiple intra-block MWS operations by leveraging ParaBit, which has fewer constraints on the maximum number of operands. For example, suppose that (i) a block has N WLs, and (ii) Flash-Cosmos needs to perform bitwise AND of all WLs of M different blocks (i.e., the number of total operands is M N). We can accumulate the results in two steps. First, Flash-Cosmos performs bitwise AND on each block for N operands at a time. Second, Flash-Cosmos performs bitwise AND on the results from the M blocks.

Flash-Cosmos Command Set

Although we demonstrate that our NAND flash chips already support all necessary features to perform the ESP and MWS operations in their test-mode command set, efficient design of Flash-Cosmos commands is important due to two reasons. First, NAND flash vendors consider their test-mode command set design to be proprietary and do not reveal any details in publicly-accessible documentation. Second, efficient command set design can significantly reduce the necessary changes to the NAND flash chip's control logic and communication overheads with a flash controller.

Figure 15 shows three new NAND flash commands that we design for Flash-Cosmos: (a) MWS, (b) ESP, and (c) XOR. We design the MWS command to be used for all three necessary features in Flash-Cosmos except for bitwise XOR: (i) intra-and inter-block MWS, (ii) inverse read, and (iii) accumulation of the results of all reads as described in Section 6.1. To this end, we extend the regular read command that contains the operation code and target page address in three aspects. First, we add the ISCM command slot before the address slot to allow a flash controller to turn on/off four features by setting the dedicated flags: (i) inverse-read mode, (ii) sensing-latch (S-latch) initialization, (iii) cache-latch (C-latch) initialization, and (iv) data transfer from S-latch to C-latch. Second, we enable the flash controller to efficiently specify the WLs to activate for MWS operations by sending the page bitmap (PBM) instead of the page index in the address slot. Third, we design an MWS command to have up to four address slots for inter-block MWS by sending the additional block address and PBM after a CONT (continue) slot. 12 The ESP command has the same command interface as the regular program command, and the XOR command performs bitwise XOR between two (sensing and cache) latches and stores the result in the C-latch. Figure 16 shows how a flash controller can use Flash-Cosmos to perform bulk bitwise operations using an example that makes two assumptions: (i) a Flash-Cosmos-enabled chip stores four sets of four bit vectors, A i , B i , C i , and D i , in four blocks Blk i (1≤i≤4), each of which has four pages; (ii) bit vectors C i and D i are programmed using their inverse data with the knowledge that they would be used for bitwise OR (Section 6.1). Suppose that the user would like to perform the following bitwise operations:

{A 1 + (B 1 • B 2 • B 3 • B 4 )} • (C 1 + C 3 ) • (D 2 + D 4 ) (4)
As shown in Figure 16, the user can perform bitwise operations using two intra-block MWS commands, 1 one for

(C 1 + C 3 ) • (D 2 + D 4
) while enabling the inverse-read mode and initialization of both latches and 2 the other for

A 1 + (B 1 • B 2 • B 3 • B 4 )
while disabling the inverse-read mode and initialization of both latches. By disabling the initialization of both latches while performing the second MWS command, the results of the two MWS commands, 1 and 2 , are accumulated in both the S-latch and the C-latch (Section 6.1). Note that the order of the two MWS commands is important, as an inverse read requires S-latch initialization, which prevents the accumulation of the results.

System Support

We briefly discuss the end-to-end system support that we envision to efficiently enable Flash-Cosmos.

Requirements. There are two key requirements for a system to take full advantage of Flash-Cosmos-enabled NAND flash chips. First, the target data of bitwise operations needs to be properly stored using ESP. To maximize the performance benefits of Flash-Cosmos, it is important to store as many operands of the target bitwise operation as possible in the same block, which minimizes the number of MWS operations required. For example, bitwise OR on 48 pages (i.e., operands) would require 12 inter-block MWS operations if each operand is stored in different blocks, assuming that the maximum number of pages for inter-block MWS is limited to 4 in order to avoid maximum power consumption related issues. However, when the operands are stored in the same block with their inverse data, it is possible to perform the same bitwise OR operation with a single intra-block MWS operation using inverse-mode read (Section 6.1). Second, the host system needs to interact with the underlying SSD in order to efficiently store the data to maximize the benefits of Flash-Cosmos. Application Changes. In our design, the application program needs to decide how to store data in three aspects. First, the application determines the data that will be used for bulk bitwise operations so that it can inform the SSD to selectively use ESP for only such data (to minimize the storage overhead due to SLC mode). Second, depending on the computation that can benefit the most from Flash-Cosmos, the application decides whether or not to store the inverse of the original data. For example, if the application performs bitwise OR more frequently than bitwise AND for certain data, it could be more beneficial to store the inverse data to leverage intra-block MWS for bitwise OR as well. Third, the application decides which operands to be stored in the same block to minimize the number of MWS operations required for the same bitwise operation. System Software Changes. In our design, the application program interacts with the SSD using the Flash-Cosmos library that includes two methods: (i) fc _ write, which writes the operand data for bitwise operations, and (ii) fc _ read, which reads the results of bitwise operations. Using fc _ write, the application informs the SSD of the context of the operation, such as the programming mode and the location (e.g., logical block address), to ensure that the data is properly stored for in-flash computation. To perform an in-flash bitwise operation, the application uses fc _ read to specify to the SSD the locations of the target operands, the size of the operands, and the types of bitwise operations required. SSD Changes. In our design, the SSD firmware requires two key changes. First, it generates Flash-Cosmos commands to properly handle fc _ write and fc _ read from the host system. Second, the SSD firmware maintains additional metadata necessary for Flash-Cosmos, such as each page's programming mode and the location where the page should be stored.

In this work, our focus is on investigating the feasibility and benefits of Flash-Cosmos using modern NAND flash memory chips. While the end-to-end support for Flash-Cosmos requires several changes within layers of the system stack, we believe that existing approaches can be applied to meet the key requirements (e.g., efficient storage layout designs [START_REF] Seshadri | Ambit: In-Memory Accelerator for Bulk Bitwise Operations Using Commodity DRAM Technology[END_REF][START_REF] Seshadri | Fast Bulk Bitwise AND and OR in DRAM[END_REF][START_REF] Hajinazar | SIMDRAM: A Framework for Bit-Serial SIMD Processing Using DRAM[END_REF][START_REF] Aga | Compute Caches[END_REF], host-SSD communication [START_REF] Hajinazar | SIMDRAM: A Framework for Bit-Serial SIMD Processing Using DRAM[END_REF][START_REF] Mailthody | Deepstore: In-Storage Acceleration for Intelligent Queries[END_REF][START_REF] Kim | Evanesco: Architectural Support for Efficient Data Sanitization in Modern Flash-based Storage Systems[END_REF], and metadata management inside the SSD [START_REF] Mailthody | Deepstore: In-Storage Acceleration for Intelligent Queries[END_REF][START_REF] Kim | Evanesco: Architectural Support for Efficient Data Sanitization in Modern Flash-based Storage Systems[END_REF]). We leave more efficient end-to-end system designs and software stack for Flash-Cosmos to future work.

Methodology

Evaluated Systems. To evaluate the effectiveness of Flash-Cosmos, we analyze four computing platforms: (i) an outsidestorage processing system (OSP),(ii) an in-storage processing system (ISP), (iii) ParaBit (PB) [START_REF] Gao | ParaBit: Processing Parallel Bitwise Operations in NAND Flash Memory Based SSDs[END_REF], and (iv) Flash-Cosmos (FC). OSP performs bulk bitwise operations using the host CPU concurrently with reading the operands from the SSD to main memory in batches. ISP leverages an in-storage hardware accelerator that consists of simple bitwise logic and 256-KiB SRAM buffer in order to perform bulk bitwise operations inside the SSD and sends only the final results to the host. PB and FC perform bulk bitwise operations inside the NAND flash chips via the in-flash processing mechanisms described in Section 3.1 and Section 6, respectively, and send only the final results to the host. Unless otherwise specified, we set all the evaluated systems to program (and thus read) the inputs and outputs of bitwise operations in SLC mode for fair performance comparison. Performance Modeling. We use two state-of-the-art simulators to analyze the performance of the evaluated systems. We model DRAM timing with the DDR4 interface [123] in Ramulator [START_REF] Kim | Ramulator: A Fast and Extensible DRAM Simulator[END_REF]125], a widely-used cycle-accurate DRAM simulator. We model SSD performance using MQSim [START_REF] Tavakkol | MQSim: A Framework for Enabling Realistic Studies of Modern Multi-Queue SSD Devices[END_REF]127], a stateof-the-art SSD simulator. We extend MQSim to faithfully model the performance of ISP, ParaBit, and Flash-Cosmos with the timing parameters we obtain from our real-device characterization (Section 5). We model the end-to-end throughput of the evaluated systems based on the throughput of each of two computation stages, SSD read (including in-storage processing in ISP, PB, and FC) and host computation (which we measure on a real host system). Table 1 summarizes the configurations of the SSD and host system used for our evaluation. Energy Modeling. We measure the energy consumption for host computation using Intel RAPL [START_REF] Hähnel | Measuring Energy Consumption for Short Code Paths Using RAPL[END_REF] To model DRAM energy consumption, We use DRAM power values based on the DDR4 model [START_REF] Inc | 4Gb: x4, x8, x16 DDR4 SDRAM Data Sheet[END_REF][START_REF] Ghose | Demystifying Complex Workload-DRAM Interactions: An Experimental Study[END_REF]. To model SSD energy consumption, we use the SSD power values of Samsung 980 Pro SSDs [START_REF] Samsung | Samsung SSD 980 PRO[END_REF] and the NAND flash power values that we measure in our realdevice characterization (Section 5). Workloads. We evaluate three real-world applications that heavily rely on bulk bitwise operations. For fair comparison with ParaBit, we evaluate two of the three applications studied in [START_REF] Gao | ParaBit: Processing Parallel Bitwise Operations in NAND Flash Memory Based SSDs[END_REF], bitmap indices and image segmentation, 13 as well as a graph-processing workload called k-clique star listing [START_REF] Besta | SISA: Set-Centric Instruction Set Architecture for Graph Mining on Processingin-Memory Systems[END_REF][START_REF] Danisch | Listing k-Cliques in Sparse Real-world Graphs[END_REF][START_REF] Jabbour | Pushing the Envelope in Overlapping Communities Detection[END_REF]. For all workloads, we assume that the data set is initially stored in the SSD due to its large size. 1) Bitmap Index (BMI): Bitmap indices [START_REF] Chan | Bitmap Index Design and Evaluation[END_REF] are an alternative to traditional B-tree indices for databases, which can provide high space efficiency and high performance for many queries (e.g., join and scan) compared to B-trees. We assume a database that tracks the log-in activities of u users for a website every day. For the i-th day, the database maintains a vector D i with u elements, each of which is a 1-bit flag to indicate each user's log-in activity on the day (0: not logged-in, 1: logged-in). Our BMI workload runs the following query: "How many users were active every day for the past m months?" Executing the query requires (i) bitwise AND operations on d vectors, where d is the number of days in the past m months, and (ii) a bitcount operation, i.e., an operation that counts the number of '1' (logged-in) bits in a given result vector r. We assume a database that tracks the log-in activities of 800 million users and evaluate the BMI workload while varying m from 1 to 36. For executing the BMI workload, PB and FC perform the bit-count operation using the host CPU concurrently with sending the result vector to main memory in batches.

2) Image Segmentation (IMS): Image segmentation [START_REF] Bruce | Fast and Inexpensive Color Image Segmentation for Interactive Robots[END_REF] is an image processing kernel that aims to break an image into multiple regions depending on a given set of colors. To determine whether a pixel p belongs to a certain color C, our IMS workload uses the YUV color recognition and performs a bitwise AND operation of Y (p,C) • U(p,C) • V (p,C), where Y (p,C), U(p,C), and V (p,C) are binary values that can be obtained 13 We do not evaluate the other application evaluated in ParaBit [START_REF] Gao | ParaBit: Processing Parallel Bitwise Operations in NAND Flash Memory Based SSDs[END_REF], image encryption [START_REF] Han | Optical Image Encryption Based on XOR Operations[END_REF], as it relies only on bitwise XOR operations that commodity NAND flash chips already support (see Section 3), i.e., neither ParaBit nor Flash-Cosmos is necessary to perform in-flash processing for such XOR operations. from pre-processing [START_REF] Bruce | Fast and Inexpensive Color Image Segmentation for Interactive Robots[END_REF]. In our evaluation, IMS segments I images, each of which consists of 800×600 pixels, with four colors. This can be done by performing a bulk bitwise AND operation to three bit vectors where each bit-vector contains I × 800 × 600 × 4 bits. We assume the three bit-vectors are initially stored in the SSD and evaluate the IMS workload while varying I from 10,000 to 200,000.

3) K-Clique Star Listing (KCS): K-clique star listing [START_REF] Besta | SISA: Set-Centric Instruction Set Architecture for Graph Mining on Processingin-Memory Systems[END_REF][START_REF] Danisch | Listing k-Cliques in Sparse Real-world Graphs[END_REF][START_REF] Jabbour | Pushing the Envelope in Overlapping Communities Detection[END_REF] aims to find all the k-clique stars in an input graph. For a given graph, a k-clique is a sub-graph with k vertices that are fully connected to each other. A k-clique star is a collection of (i) a k-clique and (ii) all the vertices in the remainder of the graph that are connected to all vertices of the k-clique. Prior work demonstrates that k-clique star listing can be significantly accelerated via processing-in-memory with a set-centric formulation [START_REF] Besta | SISA: Set-Centric Instruction Set Architecture for Graph Mining on Processingin-Memory Systems[END_REF]. In our evaluation, each vertex is represented using a bit-vector that contains adjacency information to all other vertices in the graph. Each k-clique is represented with another bit vector that specifies the set of vertices that belong to the k-clique. With such bit-vector representations, our KCS workload can determine a k-clique star by performing only a bitwise AND operation of the bit-vectors of all the vertices in the corresponding k-clique. To form the final representation of a k-clique star, KCS performs a bitwise OR operation of the calculated intermediate bit vector and the bit-vector that represents the k-clique. Note that Flash-Cosmos can perform both of the bitwise AND and OR operations simultaneously if the k-clique bit vector is stored in a block that is different from than the block that stores the vertex adjacency vectors. We use an input graph with 32 million vertices and 1,024 k-cliques and we sweep the dimensions of the cliques, from 8 to 64.

Applications using bulk bitwise operations with many operands can be particularly sensitive to the RBER of NAND flash memory. For example, a single bit error in any of the operands in the BMI workload results in an active user not being counted. The probability of miscounting active users grows as the number of operands increases and rapidly becomes impractical without a sufficiently low RBER. Assuming a best-case RBER of 8.6 × 10 -4 (based on our analysis) and m=36, the probability of a correct output is 0.42 which is not acceptable. KCS is similarly error-intolerant due to the large number of operands it uses. In contrast, IMS is more error tolerant due to the fewer operands in this workload. Thus, we expect that Flash-Cosmos would be a good fit for all these workloads, especially BMI and KCS, due to its zero bit error rate in computation results.

Evaluation Results

We evaluate the performance and energy efficiency of Flash-Cosmos by comparing its execution time and energy consumption to three baseline computing platforms.

Impact on Performance

Figure 17 shows the speedups of Flash-Cosmos (FC), Para-Bit (PB), and the in-storage processing system (ISP) over the conventional outside-storage processing system (OSP). We make six observations from Figure 17. First, FC significantly outperforms OSP, providing 32× speedup on average across all three workloads and input data sets. In OSP, computation can be completely hidden by reading of the operands due to the simple nature of bitwise operations, but the SSD's external bandwidth bottlenecks performance. This means that, when the operands are stored in the storage system, any other outside-storage processing platform (e.g., GPU or near-memory processor) cannot improve the performance of bulk bitwise operations over OSP (unless one increases SSD's external bandwidth).

Second, FC also significantly outperforms ISP, providing 25× speedup on average. While ISP provides considerable speedup (28%) over OSP by reducing external data movement from the SSD (external bandwidth is 8 GB/s, Table 1), the limited internal SSD bandwidth (9.6 GB/s, Table 1) becomes a new bottleneck. ISP needs to read out all operands from NAND flash chips to the hardware accelerators, which can be largely avoided by in-flash processing.

Third, FC provides large performance improvement over Para-Bit. While PB also significantly outperforms OSP (and ISP) by 9.4× (7.2×), FC outperforms PB by 3.5× on average across all three workloads and input data sets. This highlights the key benefit of performing MWS in real-world applications.

Fourth, the benefits of FC increase with the number of operands used in bulk bitwise operations. The speedups of FC for BMI are higher compared to the other two workloads, since BMI has a larger number of operands (from 30 to 1,095). In contrast, the performance of PB does not improve as the number of operands increases (e.g., for k>16 in KCS). This is because the performance bottleneck of PB shifts to the serial sensing of the operands as discussed in Section 3.2, due to which the latency also linearly increases with the number of operands. As a result, while FC significantly improves performance over OSP/ISP for BMI by 198.4×/150.5×, PB's benefits over OSP/ISP for BMI remain at only 14×/10.7×.

Fifth, the benefits of FC are affected by not only the number of operands but also the operand size. For example, FC does the same operation (AND) over 30 operands for BMI (when m=1) and over 32 operands for KCS (when k=32). Although KCS has more operands than BMI, we observe that FC provides higher improvement over PB for BMI. This is because the total size of the result bit vectors is smaller in BMI (100 MB) than in KCS (4 GB), which results in reduced external I/O time spent for transferring the results from the SSD to the host. As shown in Figure 7(d), external data movement can become the bottleneck even for in-flash processing if the external I/O time within an application (e.g., due to transferring results out of the SSD) is larger than the overall sensing time. Therefore, the benefit of FC over PB is lower if the external I/O time dominates the overall execution time.

Sixth, FC and PB show almost similar performance for IMS across all input sets. Even though FC reduces the average number of sensing operations by 3× compared to PB when executing the IMS workload, moving the large (up to 44GiB) result vector of IMS to the host dominates the total execution time for both mechanisms. This is in contrast to BMI where the vector size is only 100 MB. Note that, in IMS, both FC and PB provide high speedups compared to ISP and OSP (2.5× and 3×, respectively) by reducing the amount of external and internal data transfers, which are the performance bottleneck in IMS.

We conclude that Flash-Cosmos is an effective substrate to accelerate important real-world applications. Flash-Cosmos not only largely outperforms the state-of-the-art IFP technique but also, crucially, provides reliable, error-free execution (which is necessary for correct results in all three real-world workloads we evaluate).

Impact on Energy Consumption

Fig. 18 shows the energy-efficiency of FC, PB, and ISP, in terms of the number of bits that can be computed/transferred per unit of energy, normalized to that of OSP. We make three observations. First, FC greatly increases energy efficiency over the other evaluated systems, providing 95×/13.4×/3.3× higher energyefficiency compared to OSP/ISP/PB, on average across all three workloads and input sets. Flash-Cosmos has the maximum energy savings of 1,839×/222×/35.5× over OSP/ISP/PB for BMI when m=36. Second, the overall trend of FC's energy-efficiency benefits is similar to its performance benefits. The energy benefits of FC increase (decrease) as the number of operands (the operand size) increases. Third, FC reduces energy by not only reducing data movement but also reducing sensing energy, especially for multi-operand operations. As a result, it provides higher improvements in energy efficiency (95× on average over OSP) than in performance (32× on average over OSP). Note that, as shown in Figures 17(b) and 18(b), for IMS, even though FC performs similarly to PB, it provides 2.3% energy savings. We conclude that Flash-Cosmos is an efficient substrate to eliminate the energy overheads of data movement for many commonlyused real-world applications. While the write-performance and capacity overheads are not negligible, we believe that both overheads would not be serious obstacles to the adoption of Flash-Cosmos due to three reasons. First, ESP is essential to ensuring the reliability of in-flash computation. 14 As shown in Section 3.2, regular SLC/MLCmode programming exhibits significantly higher RBER than the UBER requirement, and ESP effectively solves this important reliability problem that is present in in-flash computation. 15 Second, both the write-performance and capacity overheads apply only to the data used for bulk bitwise operations. As such, Flash-Cosmos can minimize these overheads by selectively using ESP only for the data that is involved in in-flash processing (bulk bitwise operations) while programming other data using regular SLC/MLC/TLC-mode programming. Such a functionality is supported by the multiple programming modes in modern NAND flash memory, i.e., any block can be programmed in SLC, MLC, and TLC modes [START_REF] Lee | FlexFS: A Flexible Flash File System for MLC NAND Flash Memory[END_REF][START_REF] Kim | Evanesco: Architectural Support for Efficient Data Sanitization in Modern Flash-based Storage Systems[END_REF][START_REF] Li | Accelerating Garbage Collection for 3D MLC Flash Memory with SLC Blocks[END_REF].

Third, ESP does not degrade SSD write performance, in terms of both bandwidth and latency, compared to MLC-mode programming. This is because the program latency of ESP (400 µs, Section 4.2) is still lower than the latency of MLC-and TLC-mode programming (500 µs and 700 µs, respectively, in our evaluated chips). We evaluate the sequential write bandwidth of ESP, and the results show that ESP provides a write bandwidth of 4.7 GB/s, which is 73.4%/121.4%/166.7% of the regular SLC/MLC/TLC-mode programming write bandwidth (6.4/3.87/2.82 GB/s).

Related Work

To our knowledge, this work is the first to enable in-flash bulk bitwise operations on multiple operands through a single sensing operation, while achieving zero bit errors in the computation 14 In order to be useful for general-purpose computation, ParaBit has to support error-free computation, potentially using ESP. 15 Flash-Cosmos can also work with MLC NAND flash memory while guaranteeing the same level of reliability as ParaBit provides, when the operands are stored in LSB pages. This is because the mechanism of LSB-page reads is the same as SLC-page reads, except for the used read-reference voltage levels (LSB-page read in MLC: V REF2 in in Figure 5 results. We already discussed and comprehensively compared to the state-of-the-art technique [START_REF] Gao | ParaBit: Processing Parallel Bitwise Operations in NAND Flash Memory Based SSDs[END_REF] closely related to Flash-Cosmos (Sections 3, 7 and 8). We briefly describe other NDP proposals at different levels in the memory hierarchy. In-Flash Processing. Several prior works propose in-flash processing techniques to accelerate the multiply-and-accumulate (MAC) operations in different applications such as neural networks (e.g., [START_REF] Choi | An In-Flash Binary Neural Network Accelerator with SLC NAND Flash Array[END_REF][START_REF] Han | A Novel Convolution Computing Paradigm Based on NOR Flash Array with High Computing Speed and Energy Efficiency[END_REF][START_REF] Wang | Three-Dimensional NAND Flash for Vector-Matrix Multiplication[END_REF][START_REF] Lue | Optimal Design Methods to Transform 3D NAND Flash into a High-Density, High-Bandwidth and Low-Power Nonvolatile Computing in Memory (nvCIM) Accelerator for Deep-Learning Neural Networks (DNN)[END_REF][START_REF] Kim | Behemoth: A Flashcentric Training Accelerator for Extreme-scale {DNNs}[END_REF][START_REF] Wang | MemCore: Computing-in-Flash Design for Deep Neural Network Acceleration[END_REF][START_REF] Han | Flash Memory Array for Efficient Implementation of Deep Neural Networks[END_REF][START_REF] Kang | S-FLASH: A NAND Flash-based Deep Neural Network Accelerator Exploiting Bit-Level Sparsity[END_REF][START_REF] Lee | Neuromorphic Computing Using NAND Flash Memory Architecture With Pulse Width Modulation Scheme[END_REF]) and mixed signal sensing (e.g., [START_REF] Merrikh-Bayat | High-Performance Mixed-Signal Neurocomputing With Nanoscale Floating-Gate Memory Cell Arrays[END_REF]). Similar to Flash-Cosmos, these mechanisms have high bit-level parallelism, but they exploit analog current accumulation, which requires significant changes to the NAND flash cell array structures, e.g., deploying precise and costly analog-to-digital converters inside the chip (see Section 4.1). In contrast, our mechanism can be adopted in commodity SSDs with very low cost, as we demonstrated in Section 5. In-Storage Processing. Several prior works propose to leverage the internal processor (e.g., [START_REF] Seshadri | Willow: A User-Programmable SSD[END_REF][START_REF] Gu | Biscuit: A Framework for Near-Data Processing of Big Data Workloads[END_REF][START_REF] Mansouri Ghiasi | GenStore: A High-Performance In-Storage Processing System for Genome Sequence Analysis[END_REF][START_REF] Kang | Enabling Cost-effective Data Processing with Smart SSD[END_REF][START_REF] Wang | Project Almanac: A Time-Traveling Solid-State Drive[END_REF][START_REF] Acharya | Active Disks: Programming Model, Algorithms and Evaluation[END_REF][START_REF] Keeton | A Case for Intelligent Disks (IDISKs)[END_REF][START_REF] Wang | SSD In-Storage Computing for List Intersection[END_REF][START_REF] Koo | Summarizer: Trading Communication with Computing Near Storage[END_REF][START_REF] Tiwari | Active Flash: Towards Energy-Efficient, In-Situ Data Analytics on Extreme-Scale Machines[END_REF][START_REF] Tiwari | Reducing Data Movement Costs Using Energy-Efficient, Active Computation on SSD[END_REF][START_REF] Boboila | Active Flash: Out-of-core Data Analytics on Flash Storage[END_REF][START_REF] Bae | Intelligent SSD: A Turbo for Big Data Mining[END_REF][START_REF] Torabzadehkashi | CompStor: An In-Storage Computation Platform for Scalable Distributed Processing[END_REF][START_REF] Kang | IceClave: A Trusted Execution Environment for In-Storage Computing[END_REF][START_REF] Li | GLIST: Towards In-Storage Graph Learning[END_REF][START_REF] Lim | LSM-Tree Compaction Acceleration Using In-Storage Processing[END_REF][START_REF] Kim | Reducing Tail Latency of DNN-based Recommender Systems using In-Storage Processing[END_REF]) or embed hardware accelerators (e.g., [15-17, 49, 50, 155-165]) within the storage device for computation. Due to their more general-purpose designs, these proposals can perform more diverse and complex operations (e.g., arithmetic operations). However, as discussed in Section 3, in-storage processing needs to first read out the processed data from the flash chips and transmit it to the SSD controller over the SSD-internal I/O link, which is a performance bottleneck. In contrast, Flash-Cosmos can effectively reduce the data movement between NAND flash chips and the SSD controller by performing computation inside the flash chip arrays, leading to more than an order of magnitude higher performance and energy-efficiency than in-storage processing (Section 8). In-Memory and In-Cache Processing. A large body of prior work proposes various NDP techniques at other levels of the memory hierarchy, e.g., in main memory (e.g., [6-9, 14, 20, 38, 39, 54, 166-192]) and in SRAM caches (e.g., [START_REF] Aga | Compute Caches[END_REF][START_REF] Fujiki | Duality Cache for Data Parallel Acceleration[END_REF][START_REF] Eckert | Neural Cache: Bit-Serial In-Cache Acceleration of Deep Neural Networks[END_REF][START_REF] Kang | Deep In-Memory Architectures in SRAM: An Analog Approach to Approximate Computing[END_REF][START_REF] Angstadt | ASPEN: A Scalable In-SRAM Architecture for Pushdown Automata[END_REF][START_REF] Kang | Deep In-Memory Architectures in SRAM: An Analog Approach to Approximate Computing[END_REF][START_REF] Zhang | In-Memory Computation of a Machine-Learning Classifier in a Standard 6T SRAM Array[END_REF][START_REF] Lin | A Reconfigurable In-SRAM Computing Architecture for DCNN Applications[END_REF][START_REF] Al-Hawaj | Towards a Reconfigurable Bit-Serial/Bit-Parallel Vector Accelerator using In-Situ Processing-In-SRAM[END_REF][START_REF] Zhang | Sealer: In-SRAM AES for High-Performance and Low-Overhead Memory Encryption[END_REF]). Even though these works provide significantly lower access latency and high reliability, once the size of the processed data exceeds the cache and main memory capacity, the data needs to move between the storage devices and the rest of the memory hierarchy. Flash-Cosmos can complement these NDP approaches (including in-storage processing) by processing large amounts of data inside flash arrays and communicating only the results of the computation.

Discussion

Extensions to Other Applications. Flash-Cosmos can be used to accelerate not only bitwise operations but also any desired op-eration. This is because Flash-Cosmos supports a set of bitwise operations that are logically complete, like other processingusing-memory (PuM) substrates that use the operational principles of the memory cells for computation, such as Compute Caches [START_REF] Aga | Compute Caches[END_REF] (SRAM-based PuM), Ambit [START_REF] Seshadri | Ambit: In-Memory Accelerator for Bulk Bitwise Operations Using Commodity DRAM Technology[END_REF] (DRAM-based PuM), and Pinatubo [START_REF] Li | Pinatubo: A Processing-in-Memory Architecture for Bulk Bitwise Operations in Emerging Non-Volatile Memories[END_REF] (NVM-based PuM). Follow-up works (e.g., DualityCache [START_REF] Fujiki | Duality Cache for Data Parallel Acceleration[END_REF], SIMDRAM [START_REF] Hajinazar | SIMDRAM: A Framework for Bit-Serial SIMD Processing Using DRAM[END_REF], and IMP [START_REF] Fujiki | In-Memory Data Parallel Processor[END_REF]) propose frameworks that leverage these substrates and techniques to automate the creation of desired complex operations (e.g., addition and multiplication) to accelerate a broad range of workloads, including graph processing, databases, neural networks and genome analysis. We leave the development of such a framework for Flash-Cosmos to future work. Limitations. Flash-Cosmos has two key limitations that also commonly exist in other PuM solutions. First, like ParaBit and other PuM proposals (e.g., [6-9, 20, 37-39, 166-170, 172, 173, 188]), it is not straightforward for Flash-Cosmos to work with mainstream encryption techniques (e.g., AES-256 [START_REF] Samsung | Samsung SSD 980 PRO[END_REF][START_REF] Biryukov | Related-Key Cryptanalysis of the Full AES-192 and AES-256[END_REF]) that are widely used in modern SSDs. This is because widelyused encryption techniques have input-data dependence and/or require complex computation other than bitwise operations (e.g., shifting). One possible solution is to employ homomorphic encryption that preserves the correctness of computation for encrypted data [START_REF] Fontaine | A Survey of Homomorphic Encryption for Nonspecialists[END_REF]. Although homomorphic encryption currently has many challenges with large computation and capacity overheads, we believe that the development of efficient homomorphic encryption would be a promising direction to solve this common problem of the PuM paradigm in dealing with encrypted data.

Second, like ParaBit and other PuM proposals, Flash-Cosmos can accelerate bulk bitwise operations only when the operands are stored in the same chip. The system can potentially leverage an efficient inter-chip data migration technique to gather the target operands into the same block in background, but doing so inevitably incurs data movement that eats away from the benefits of Flash-Cosmos. When the operands are stored in different chips, in-storage processing that uses hardware accelerators near NAND flash chips could be more effective. Fortunately, Flash-Cosmos requires only small changes to commodity NAND flash chips, which makes it easy to be combined with such an in-storage processing solution. We leave the integration of Flash-Cosmos with other NDP solutions to future work.

Conclusion

We propose Flash-Cosmos, a new in-flash processing technique that significantly improves the performance, energy efficiency, and reliability of in-flash bulk bitwise operations. Flash-Cosmos takes full advantage of the massive bit-level parallelism present in modern NAND flash memory by leveraging the cell-array structures and operating principles of NAND flash memory. First, Flash-Cosmos enables the chips to perform bulk bitwise operations on multiple (tens) operands via only one singlesensing operation. Second, Flash-Cosmos enhances the existing SLC-mode programming scheme to achieve zero bit errors in computation results, thereby enabling the use of in-flash processing for general, error-intolerant applications, which was previously not possible. We experimentally demonstrate the feasibility, performance, and reliability of Flash-Cosmos using 160 real 3D NAND flash chips. Our simulation-based real workload evaluations show that Flash-Cosmos significantly outperforms outside-storage processing, in-storage processing and the state-of-the-art in-flash processing technique in terms of both performance and energy efficiency while providing reliable operation. We conclude that Flash-Cosmos is a promising substrate to enable highly-efficient, high-performance, and reliable in-flash computation. We hope and expect that future work builds on Flash-Cosmos in many ways, e.g., by enabling system-level frameworks that take advantage of Flash-Cosmos and by demonstrating benefits over more workloads.

1

  arXiv:2209.05566v1 [cs.AR] 12 Sep 2022

Figure 1 :

 1 Figure 1: NAND flash organization.

  ), a NAND flash chip charges all target BLs and their sense-out (SO) capacitors (C SO ) to the precharge voltage V PRE by enabling the precharge transistor M PRE 1 . At the same time, the chip applies the read-reference voltage V REF to the target WL while applying a much larger pass voltage V PASS to the other WLs in the same block 2 . Doing so makes each target cell's V TH level dictate the corresponding NAND string's conductance; the target cell would operate as either a resistor, if V TH ≤V REF ( a in Figure 2, left part), or an open switch, if V TH >V REF ( b );all non-target cells in the same NAND string would always operate as resistors since V PASS is high enough (>6 V) to turn on any flash cell regardless of its V TH level[START_REF] Cai | Read Disturb Errors in MLC NAND Flash Memory: Characterization, Mitigation, and Recovery[END_REF]. The chip then starts the evaluation of the target cells ( E in the middle part of Figure2) by disconnecting the BLs from V PRE 3 and enabling the latching circuit 4 . If the target cell's V TH level is lower than V REF , the charge in C SO quickly flows through the NAND string ( c ), which is sensed as a '1'. If V TH >V REF , the capacitance of C SO hardly changes ( d ) as the target cell blocks the BL discharge current, which is sensed as a '0'. Finally, the chip discharges the BLs ( D in the right part of Figure2) to return the NAND string to its initial stable state (i.e., the state before precharge can take place) for future operations.

Figure 2 :

 2 Figure 2: NAND flash read mechanism.

Figure 3 VOUT : 1 à 1 I OUT : 0 à 0 ISO : 1 à 0 (I OUT : 1 à 0 IOUT : 0 à 1 I SO : 1 à 1 Figure 3 :

 31000113 Figure 3 depicts how NAND flash memory senses a BL's conductance with its latching circuit. Figures 3(a) and 3(b)describe the operation of the latching circuit when the threshold voltage V TH of a flash cell is lower and higher than the read reference voltage V REF , respectively. We show the transition in voltage state at each of the three nodes (SO/OUT/OUT) when going from the precharge step ( P in Figure2) to the evaluation

VOUT : 1 à 1 I OUT : 0 à 0 ISO : 1 à 0 (I OUT : 1 à 0 IOUT : 0 à 1 I SO : 1 à 1 Figure 4 :

 1000114 Figure 4: Latching circuit showing the voltage states at SO, OUT and OUT in the precharge P and evaluation E steps during an inverse read operation (see Figure 2).

Figure 5 :

 5 Figure 5: V TH distribution of a programmed wordline.

Figure 6 :

 6 Figure 6: Bitwise computation techniques employed in the stateof-the-art in-flash processing technique [21].

Figure 7 :

 7 Figure 7: (a) SSD organization, and comparison of execution timelines of a channel in (b) outside-storage processing (OSP), (c) instorage processing (ISP), and (d) in-flash processing (IFP) during bulk bitwise operations.

Figure 8 :

 8 Figure 8: Raw Bit Error Rate (RBER) impact of (a) SLC-mode and (b) MLC-mode programming schemes at different P/E cycles and retention ages, with and without data randomization.

Figure 9 :

 9 Figure 9: Overview of (a) intra-block MWS (leading to bitwise AND) and (b) inter-block MWS (leading to bitwise OR).

Figure 10 :

 10 Figure 10: Overview of Enhanced SLC-mode Programming.

Figure 11 :

 11 Figure 11: RBER vs. tESP.Figure 12: Intra-block MWS latency. Figure 13: Inter-block MWS latency. Figure 14: MWS power.

Figure 12 :

 12 Figure 11: RBER vs. tESP.Figure 12: Intra-block MWS latency. Figure 13: Inter-block MWS latency. Figure 14: MWS power.

Figure 15 :

 15 Figure 15: Three new NAND flash commands for Flash-Cosmos: (a) MWS, (b) ESP, and XOR.

Figure 16 :

 16 Figure 16: Operational example of Flash-Cosmos.While performing the second MWS command, the results of the two MWS commands, 1 and 2 , are accumulated in both the S-latch and the C-latch.

Figure 17 :

 17 Figure 17: Performance comparison of four computing platforms on three real-world workloads. ISP (In-storage processing), PB (ParaBit), FC (Flash-Cosmos). Speedup values are normalized to OSP (Outside-storage processing). Y-axis is in log-scale.

Figure 18 :

 18 Figure 18: Energy-efficiency comparison of four computing platforms on three real-world workloads. Normalized to OSP (Outsidestorage processing). Y-axis represents number of bits computed per unit of energy in log-scale.8.3. Overhead AnalysisAs briefly discussed in Section 4.2, Flash-Cosmos introduces two key overheads due to the use of ESP for reliable in-flash computation. First, ESP requires 2× the page-program latency compared to regular SLC-mode programming. Second, ESP consumes 2× the storage capacity to store the same amount of data compared to MLC-mode programming.While the write-performance and capacity overheads are not negligible, we believe that both overheads would not be serious obstacles to the adoption of Flash-Cosmos due to three reasons. First, ESP is essential to ensuring the reliability of in-flash computation.14 As shown in Section 3.2, regular SLC/MLCmode programming exhibits significantly higher RBER than the UBER requirement, and ESP effectively solves this important reliability problem that is present in in-flash computation.15 Second, both the write-performance and capacity overheads apply only to the data used for bulk bitwise operations. As such, Flash-Cosmos can minimize these overheads by selectively using ESP only for the data that is involved in in-flash processing (bulk bitwise operations) while programming other data using regular SLC/MLC/TLC-mode programming. Such a functionality is supported by the multiple programming modes in modern NAND flash memory, i.e., any block can be programmed in SLC, MLC, and TLC modes[START_REF] Lee | FlexFS: A Flexible Flash File System for MLC NAND Flash Memory[END_REF][START_REF] Kim | Evanesco: Architectural Support for Efficient Data Sanitization in Modern Flash-based Storage Systems[END_REF][START_REF] Li | Accelerating Garbage Collection for 3D MLC Flash Memory with SLC Blocks[END_REF].Third, ESP does not degrade SSD write performance, in terms of both bandwidth and latency, compared to MLC-mode programming. This is because the program latency of ESP (400 µs, Section 4.2) is still lower than the latency of MLC-and TLC-mode programming (500 µs and 700 µs, respectively, in our evaluated chips). We evaluate the sequential write bandwidth of ESP, and the results show that ESP provides a write bandwidth of 4.7 GB/s, which is 73.4%/121.4%/166.7% of the regular SLC/MLC/TLC-mode programming write bandwidth (6.4/3.87/2.82 GB/s).

  (b) vs. SLC-page read: V REF in Figure 5 (a)).

Table 1 :

 1 Evaluated system configurations.

		CPU: Intel Rocket Lake i7 11700K [91];
	Real Host System	x86 [128]; 8 cores; out-of-order; 3.6 GHz;
		Main Memory: 64 GB; DDR4-3600; 4 channels;
		48-WL-layer 3D TLC NAND flash-based SSD; 2 TB;
		Bandwidth: 8-GB/s external I/O bandwidth (4-lane PCIe Gen4);
		1.2-GB/s Channel IO rate;
	Simulated SSD	NAND Config: 8 channels; 8 dies/channel; 2 planes/dies;
		2,048 blocks/plane; 196 (4×48) WLs/block; 16 KiB/page;
		Latencies: tR (SLC mode): 22.5 µs; tMWS: 25 µs (Max. 4 blocks);
		tPROG (SLC/MLC/TLC mode): 200/500/700 µs; tESP: 400 µs;
		Power: HW Accelerator (only in ISP): 93 pJ for 64B operation;

NAND flash memory concurrently reads a large number of (> 10 5 ) cells whose control gates are connected to the same wordline. See Section 2.1 for more background on NAND flash memory operation.

In fact, randomization is the reason why the V TH distribution of NAND flash memory is commonly described by using V TH states with the same shape, as in Figure

ParaBit also introduces several mechanisms to support other bitwise operations (e.g., bitwise XOR) and different approaches that exploit the common bit-encoding scheme for MLC NAND flash memory, but we discuss only AND and OR since the others have key drawbacks, such as costly additional inverter logic at each BL to support bitwise XOR operations.

Intra-block MWS, which applies V REF to two or more WLs, differs from a regular read operation that applies V REF only to a single WL. ParaBit[START_REF] Gao | ParaBit: Processing Parallel Bitwise Operations in NAND Flash Memory Based SSDs[END_REF], the prior state-of-the-art IFP technique, uses regular read operations.

Exceptionally, Pinatubo[START_REF] Li | Pinatubo: A Processing-in-Memory Architecture for Bulk Bitwise Operations in Emerging Non-Volatile Memories[END_REF] can perform the bitwise OR operation on a large number of rows with a single sensing operation. However, Pinatubo cannot support the bitwise AND operation for more than two operands.

Section 6.1 explains how Flash-Cosmos supports other common bitwise operations (e.g., NOT, NAND, NOR, XOR, and XNOR).

We also tried to achieve the same level of RBER by enhancing MLC-mode programming, but the RBER of MLC-mode programming does not decrease below 10 -4 even when we increase the program latency to 5 ms.

The result is not enough to guarantee the JEDEC-specified UBER requirements (see Section 5.1), but we carefully select the evaluated blocks to avoid any potential inaccuracy in our results. Given the limitations in academia, it is challenging to experimentally guarantee the UBER requirements, which requires around 1,000× samples and 1,000× longer testing time than our experiments using our experimental testing infrastructure.

CONT is a command slot to indicate that an address cycle will follow next. CONF is a command slot to indicate the end of the command sequence.

Acknowledgments

We thank the anonymous reviewers of ISCA 2022 and MI-CRO 2022 for feedback. We thank the SAFARI group members for feedback and the stimulating intellectual environment. We specifically thank Nika Mansouri Ghiasi and Minesh Patel who helped shape our arguments and strengthen our evaluation. We acknowledge the generous gifts and support provided by our industrial partners: Google, Huawei, Intel, Microsoft, VMware, the Semiconductor Research Corporation and the ETH Future Computing Laboratory. Jisung Park was in part supported by the National Research Foundation (NRF) of Korea (NRF-2020R1A6A3A03040573). (Co-corresponding Authors: Jisung Park, Myungsuk Kim, and Onur Mutlu)