Hybrid logical to physical address translation for non-volatile storage devices with integrated compute module

0001This application claims the benefit of U.S. Provisional Application 62/483,818, “Hybrid Logical To Physical Address Translation For Non-Volatile Storage Devices With Integrated Compute Module,” filed on Apr. 10, 2017, incorporated herein by reference in its entirety.

BACKGROUND

0002Non-volatile semiconductor memory is used in solid state drives (SSD). As Internet-scale services continue to grow, real time data processing and data analytics by ad-hoc queries on large volumes of data is emerging as a critical application. Additionally, as memory density continues to scale, SSD capacities continue to scale exponentially. Current enterprise systems are ill-equipped to manage these trends as they rely on moving huge volumes of data out of the SSD and into a host system's main memory for processing. These solutions rely on storing data at one location (i.e. a storage device like a SSD) and move data to a different location (typically DRAM of the host) for computation. While this method works for some applications with limited data sizes, applications with large scale data cannot use this method because of the time wasted on transferring data and the prohibitively high cost and power consumption of including large scale (e.g. petabyte) DRAM capacity in such systems.

BRIEF DESCRIPTION OF THE DRAWINGS

0003Like-numbered elements refer to common components in the different figures.

0004<figref idref="DRAWINGS">FIG. 1</figref> is a block diagram of one embodiment of a solid state drive that comprises a Controller, non-volatile memory for storing data and a compute engine near the location of the data that can be used to perform common data manipulation operations.

0005<figref idref="DRAWINGS">FIG. 2</figref> is a block diagram of one embodiment of a solid state drive that comprises a Controller, non-volatile memory for storing data and a compute engine near the location of the data that can be used to perform common data manipulation operations.

0006<figref idref="DRAWINGS">FIG. 3</figref> is a block diagram of one embodiment of a Front End Processor Circuit with a compute engine. The Front End Processor Circuit is part of a Controller.

0007<figref idref="DRAWINGS">FIG. 4</figref> is a block diagram of one embodiment of a Back End Processor Circuit. In some embodiments, the Back End Processor Circuit is part of a Controller.

0008<figref idref="DRAWINGS">FIG. 5</figref> is a block diagram of one embodiment of a memory package.

0009<figref idref="DRAWINGS">FIG. 6</figref> is a block diagram of one embodiment of a memory die.

0010<figref idref="DRAWINGS">FIG. 7</figref> is a block diagram of one embodiment of a solid state drive that comprises a Controller, non-volatile memory for storing data and a compute engine near the location of the data that can be used to perform common data manipulation operations.

0011<figref idref="DRAWINGS">FIG. 8</figref> is a block diagram of one embodiment of a solid state drive that comprises a Controller, non-volatile memory for storing data and a compute engine near the location of the data that can be used to perform common data manipulation operations.

0012<figref idref="DRAWINGS">FIG. 9</figref> is a block diagram of one embodiment of a Front End Processor Circuit without a compute engine. In some embodiments, the Front End Processor Circuit is part of a Controller.

0013<figref idref="DRAWINGS">FIG. 10</figref> is a block diagram of one embodiment of a solid state drive that comprises a Controller, non-volatile memory for storing data and a compute engine near the location of the data that can be used to perform common data manipulation operations.

0014<figref idref="DRAWINGS">FIG. 11</figref> is a block diagram of one embodiment of a Back End Processor Circuit with a compute engine. In some embodiments, the Back End Processor Circuit is part of a Controller.

0015<figref idref="DRAWINGS">FIG. 12</figref> is a block diagram of one embodiment of a solid state drive that comprises a Controller, non-volatile memory for storing data and a compute engine near the location of the data that can be used to perform common data manipulation operations.

0016<figref idref="DRAWINGS">FIG. 13</figref> is a block diagram of one embodiment of a solid state drive that comprises a Controller, non-volatile memory for storing data and a compute engine near the location of the data that can be used to perform common data manipulation operations.

0017<figref idref="DRAWINGS">FIG. 13A</figref> is a block diagram of one embodiment of a solid state drive that comprises a Controller, non-volatile memory for storing data and a compute engine near the location of the data that can be used to perform common data manipulation operations.

0018<figref idref="DRAWINGS">FIG. 14</figref> is a block diagram of one embodiment of a memory package with a compute engine.

0019<figref idref="DRAWINGS">FIG. 15</figref> is a block diagram of one embodiment of a solid state drive that comprises a Controller, non-volatile memory for storing data and a compute engine near the location of the data that can be used to perform common data manipulation operations.

0020<figref idref="DRAWINGS">FIG. 16</figref> is a block diagram of one embodiment of a memory die with a compute engine.

0021<figref idref="DRAWINGS">FIG. 17</figref> is a block diagram of one embodiment of a solid state drive that comprises a Controller, non-volatile memory for storing data and a compute engine near the location of the data that can be used to perform common data manipulation operations.

0022<figref idref="DRAWINGS">FIG. 18</figref> is a block diagram of one embodiment of a memory die with circuitry under the memory array.

0023<figref idref="DRAWINGS">FIG. 19</figref> is a block diagram of one embodiment of a memory die with circuitry under the memory array.

0024<figref idref="DRAWINGS">FIG. 20</figref> depicts a portion of a database.

0025<figref idref="DRAWINGS">FIG. 21</figref> is a block diagram of a block of non-volatile memory.

0026<figref idref="DRAWINGS">FIG. 22</figref> is a block diagram illustrating an implementation of a solid state drive (or other memory system) that comprises a Controller, non-volatile memory for storing data and a compute engine near the location of the data that can be used to perform common data manipulation operations, in accordance with some embodiments. The system of <figref idref="DRAWINGS">FIG. 22</figref> reduces the size in memory of logical address to physical address tables by having separate tables for random and sequential workload to thereby provide more memory resources to the compute engine.

0027<figref idref="DRAWINGS">FIG. 23</figref> is a flow chart describing one embodiment of a process for reducing the size in memory of logical address to physical address tables by having separate tables for random and sequential workload to thereby provide more memory resources to the compute engine inside the memory system (e.g. behind the host interface).

0028<figref idref="DRAWINGS">FIG. 24</figref> is a flow chart describing one embodiment of a process performed by a host.

0029<figref idref="DRAWINGS">FIG. 25</figref> is a flow chart describing one embodiment of a process for operating a memory system using separate logical address to physical address tables for random and sequential workload.

0030<figref idref="DRAWINGS">FIG. 26</figref> depicts fine-grained (page based) mapping that has sixteen different map entries (16 physical pages or 2 blocks in total, s sub-blocks/block, <b>4</b> pages/sub-block).

0031<figref idref="DRAWINGS">FIG. 27</figref> depicts coarse-grained mapping (sub-block based) that has four different map entries.

0032<figref idref="DRAWINGS">FIG. 28</figref> depicts coarse-grained mapping (erase block based) that has two different map entries.

DETAILED DESCRIPTION

0033A solid state drive (“SSD”), or other memory system, is proposed that can accelerate performance of big data applications using a hardware accelerator based approach that involves integrating compute engines inside the SSD (or other memory system) to perform common data manipulation operations such as scan, filter, aggregate, and join (and other operations). Application Programming Interfaces (“APIs”) can be exposed by the memory system (e.g., exposed by the Controller) and used by the host application to perform efficient data processing using the compute engines in the SSD or other memory system.

0034As the compute operations move closer to the data, the available compute-to-data bandwidth increases significantly. For example, compared to conventional systems where compute is located on the host side of the I/O interface (and outside the SSD), integrating the compute engine within a SSD can provide 1.5×-3.75× higher bandwidth, even as NAND architecture and I/O interfaces continue to scale. Similarly, even closer integration with the bits —by moving the compute engine within a memory die—can provide an additional 2.5×-13× increase in bandwidth available to the compute engine.

0035A compute engine is a hardware circuit that can be one or more of the following:

00361. Hardware accelerator for data access and manipulation operations such as filtering, aggregation, compression/decompression, sorting, grouping, and joining tabular or other forms of data;

00372. General purpose CPU core such as ARM/ARC/Intel Atom; and/or

00383. Reconfigurable hardware circuitry such as FPGAs.

0039Unlike other components in an SSD that primarily facilitate reading/writing data from/to the SSD, a compute engine (which is separate from a controller) manipulates the contents of the data. For example, it can search a stream of data looking for a specific key (a set of bytes) or can sort the data in some order as specified by the host. The concept of compute engines includes but is not limited to compression/decompression engines sometimes available in SSDs.

0040Typical memory systems include a controller, non-volatile storage connected to the controller, and local high speed volatile memory (e.g., DRAM) connected to and local to the controller. The controller can use the local high speed volatile memory (also referred to as local memory or working memory) as a read buffer, as a write buffer, as a scratch pad and to store logical address to physical address translation tables (“L2P tables”).

0041In many systems, the non-volatile storage is addressed internally to the memory system using physical addresses associated with the one or more memory die. However, the host system will use logical addresses to address the various memory locations. This enables the host to assign data to consecutive logical addresses, while the memory system is free to store the data as it wishes among the locations of the one or more memory die. To enable this system, the controller typically performs address translation between the logical addresses used by the host and the physical addresses used by the memory die. One example implementation is to maintain tables (i.e. the L2P tables mentioned above) that identify the current translation between logical addresses (such as logical block addresses, known as LBA's) and physical addresses (such as physical block addresses, known as PBA's). An entry in the L2P table may include an identification of a logical address and corresponding physical address.

0042Although logical address to physical address tables (or L2P tables) include the word “tables” they need not literally be tables. Rather, the logical address to physical address tables (or L2P tables) can be any type of data structure.

0043In some examples, the memory space of a memory system is so large that the local memory cannot hold all of the L2P tables. In such a case, the entire set of L2P tables are stored in the non-volatile storage and a subset of the L2P tables are cached (L2P cache) in the local memory. The bigger the L2P cache, the higher performance of the memory system. In some memory systems, the L2P cache may utilize up to 95% of the local memory. Using such a large portion of the local memory is not a problem during normal operation of the memory system (e.g., during programming, erasing and reading). However, when the local compute engine (discussed above) has been engaged to perform data manipulation operations, that local compute engine needs to use a portion of the local memory as working memory to support the data manipulation operations. If 95% of the local memory is reserved for the L2P cache, then there will not be enough free memory for the compute engine and the compute engine's performance will suffer. Therefore, there is a need to reduce the amount of space (capacity) in the local memory that is reserved for the L2P cache when the local memory is needed by a compute engine, without degrading performance of the memory system.

0044To address this need, a non-volatile storage system is proposed that maintains reduced size logical address to physical address tables in volatile working memory by maintaining coarse logical address to physical address tables in the working memory for use with storing sequentially accessed data and storing fine logical address to physical address tables in the working memory for use with storing randomly accessed data. By maintaining reduced size logical address to physical address tables, there will be more room in the working memory for the local compute engine to use during its performance of database operations, thereby, increasing the performance (speed) of the compute engine.

0045One embodiment of the memory system (e.g., SSD) is connectable to (or otherwise in communication with) a host. The memory system comprises non-volatile memory (e.g., one or more memory packages including one or more memory die), a controller in communication with the non-volatile memory, working memory connected to the controller and configured to store coarse logical address to physical address tables for use with storing sequentially accessed data and fine logical address to physical address tables for use with storing randomly accessed data, and a compute engine positioned within the memory system and in communication with the controller. The compute engine is configured to receive compiled code from the host that includes instructions for performing one or more database operations on target data in the non-volatile memory and an indication of whether the target data is sequentially accessed data or randomly accessed data. The compute engine performs the one or more database operations based on the code. The target data is accessed using the coarse logical address to physical address tables if the indication denotes that the target data is sequentially accessed data and the target data is accessed using the fine logical address to physical address tables if the indication denotes that the target data is randomly accessed data.

0046<figref idref="DRAWINGS">FIGS. 1-19</figref> describe various architectures for memory systems that can implement the technology proposed herein. For example, <figref idref="DRAWINGS">FIG. 1</figref> is a block diagram of one embodiment of SSD <b>10</b> that comprises a Controller (SSD Controller) <b>12</b>, non-volatile memory packages <b>14</b> for storing data, DRAM/ReRAM <b>16</b>, and a compute engine <b>22</b> near the location of the data that can be used to perform common data manipulation operations. <figref idref="DRAWINGS">FIG. 1</figref> presents a high-level design where the compute engine <b>22</b> is integrated within the SSD Controller <b>12</b>. The compute engine <b>22</b> can be, for instance, an ASIC that is part of the SSD Controller system on a chip (“SoC”), or can be integrated (deeper) as a hardware circuit within the SSD controller. <figref idref="DRAWINGS">FIG. 1</figref> shows the SSD Controller <b>12</b>, a SoC, including existing SSD Controller components that comprise FTL engines <b>32</b>, ECC engines <b>34</b>, and DDR memory controller <b>36</b> for controlling DRAM/ReRAM <b>16</b>. Included within that SSD Controller <b>12</b> is the new proposed compute engine <b>22</b> that can be used to perform compute operations on data stored in the non-volatile memory of the memory packages. Examples of the compute operations include scanning the data, searching, filtering, sorting, aggregating data, joining data together, as well as other functions on the data. <figref idref="DRAWINGS">FIG. 1</figref> shows the SSD Controller <b>12</b> in communication with DRAM/ReRAM <b>16</b> and in communication with the set of one or more memory packages <b>14</b>. In one embodiment, the SSD Controller <b>12</b> communicates with the memory packages (and/or memory die) using a Toggle Mode interface, which is an asynchronous interface that is able to communicate 32 GB/s. An alternative embodiment could use ONFI interface (Open NAND Flash Interface), which is synchronous and makes use of a clock. DRAM/ReRAM <b>16</b> is one example of a local memory (e.g., high speed volatile working memory).

0047In the designs considered below, a memory package refers to a structure that contains one or more memory dies (e.g., NAND flash memory dies, ReRAM dies, both NAND and ReRAM, or other non-volatile technologies). The term memory package can also refer to managed memory—i.e. a memory package that contains one or more memory dies with an embedded error correction code (“ECC”) engine/controller to correct errors detected during read operations to the memory.

0048The memory packages include one or more memory die. In one embodiment, each memory die will include its own chip enable that can be controlled by SSD Controller <b>12</b>. In other embodiments, multiple memory die may share a chip enable, requiring SSD Controller <b>12</b> to use addressing to select between the memory die that share a chip enable. In one embodiment, the memory die in the memory packages <b>14</b> utilize NAND flash memory. In other embodiments, the memory package can include cross point ReRAM non-volatile memory, which is discussed below.

0049<figref idref="DRAWINGS">FIG. 2</figref> is a block diagram of one embodiment of a solid state drive <b>100</b> that comprises a controller <b>102</b>, non-volatile memory <b>104</b> for storing data, DRAM/ReRAM <b>106</b> and a compute engine <b>114</b> near the location of the data that can be used to perform common data manipulation operations. The embodiment of <figref idref="DRAWINGS">FIG. 2</figref> includes an SSD controller <b>102</b> comprising a Front End Processor Circuit (FEP) <b>110</b> and one or more Back End Processor Circuits (BEP) <b>112</b>. In one embodiment the FEP<b>110</b> circuit is implemented on an ASIC. In one embodiment, each BEP circuit <b>112</b> is implemented on a separate ASIC. The ASICs for each of the BEP circuits <b>112</b> and the FEP circuit <b>110</b> are implemented on the same semiconductor such that the SSD controller <b>102</b> is manufactured as a SoC. FEP <b>110</b> and BEP <b>112</b> both include their own processors. In one embodiment, FEP<b>110</b> and BEP <b>112</b> work as a master slave configuration where the FEP<b>110</b> is the master and each BEP <b>112</b> is a slave. For example, FEP circuit <b>110</b> implements a flash translation layer, including performing memory management (e.g., garbage collection, wear leveling, etc.), logical to physical address translation, communication with the host, management of DRAM (local volatile memory) and management the overall operation of the SSD (or other non-volatile storage system). The BEP circuit <b>112</b> manages memory operations in the memory packages/die at the request of FEP circuit<b>110</b>. For example, the BEP circuit <b>112</b> can carry out the read, erase and programming processes. Additionally, the BEP circuit <b>112</b> can perform buffer management, set specific voltage levels required by the FEP circuit<b>110</b>, perform error correction (ECC), control the Toggle Mode interfaces to the memory packages, etc. In one embodiment, each BEP circuit <b>112</b> is responsible for its own set of memory packages. <figref idref="DRAWINGS">FIG. 2</figref> shows the FEP circuit<b>110</b> in communication with each of the BEP circuits <b>112</b>. In the implementation of <figref idref="DRAWINGS">FIG. 2</figref>, the compute engine <b>114</b> is designed in as a hardware circuit within FEP<b>110</b>. The compute engine can access high speed, high-bandwidth memory using the DDR interface to access the DRAM <b>106</b>. In this implementation, the bandwidth available to the compute engine is limited by the bandwidth that connects the FEP<b>110</b> to the BEP <b>112</b>. DRAM <b>106</b> is one example of a local working memory.

0050<figref idref="DRAWINGS">FIG. 3</figref> is a block diagram of one embodiment of an FEP circuit with the compute engine <b>114</b> designed into the circuit. The FEP circuit of <figref idref="DRAWINGS">FIG. 3</figref> is one example implementation of FEP circuit<b>110</b> of <figref idref="DRAWINGS">FIG. 2</figref>. <figref idref="DRAWINGS">FIG. 3</figref> shows a PCIe interface <b>150</b> to communicate with the host and a host processor <b>152</b> in communication with that PCIe interface. The host processor <b>152</b> can be any type of processes known in the art that is suitable for the implementation. The host processor <b>152</b> is in communication with a network-on-chip (NOC) <b>154</b>. An NOC is a communication subsystem on an integrated circuit, typically between cores in a SoC. NOC's can span synchronous and asynchronous clock domains or use unclocked asynchronous logic. NOC technology applies networking theory and methods to on-chip communications and brings notable improvements over conventional bus and crossbar interconnections. NOC improves the scalability of SoCs and the power efficiency of complex SoCs compared to other designs. The wires and the links of the NOC are shared by many signals. A high level of parallelism is achieved because all links in the NOC can operate simultaneously on different data packets. Therefore, as the complexity of integrated subsystems keep growing, an NOC provides enhanced performance (such as throughput) and scalability in comparison with previous communication architectures (e.g., dedicated point-to-point signal wires, shared buses, or segmented buses with bridges). Connected to and in communication with NOC <b>154</b> is the memory processor <b>156</b>, the compute engine <b>114</b>, SRAM <b>160</b> and a DRAM controller <b>162</b>. The DRAM controller <b>162</b> is used to operate and communicate with the DRAM (e.g., DRAM <b>106</b>). SRAM <b>160</b> is local RAM memory used by the compute engine <b>114</b> or the memory processor <b>156</b>. The memory processor <b>156</b> is used to run the FEP circuit and perform the various memory operations. Also in communication with the NOC are two PCIe Interfaces <b>164</b> and <b>166</b>. In the embodiment of <figref idref="DRAWINGS">FIG. 3</figref>, the SSD controller will include two BEP circuits; therefore there are two PCIe Interfaces <b>164</b>/<b>166</b>. Each PCIe Interface communicates with one of the BEP circuits. In other embodiments, there can be more or less than two BEP circuits; therefore, there can be more than two PCIe Interfaces. In these arrangements, the compute engine <b>114</b> is positioned (from the perspective of the host) behind the interface <b>150</b> to the host (e.g., on the memory system side of the interface to the host) and behind the API exposed by the Controller (e.g., exposed by the FEP circuit).

0051<figref idref="DRAWINGS">FIG. 4</figref> is a block diagram of one embodiment of the BEP circuit. The BEP circuit of <figref idref="DRAWINGS">FIG. 4</figref> is one example implementation of BEP circuit <b>112</b> of <figref idref="DRAWINGS">FIG. 2</figref>. <figref idref="DRAWINGS">FIG. 4</figref> shows a PCIe Interface <b>200</b> for communicating with the FEP circuit(e.g., communicating with one of PCIe Interfaces <b>164</b> and <b>166</b> of <figref idref="DRAWINGS">FIG. 3</figref>). PCIe Interface <b>200</b> is in communication with two NOCs <b>202</b> and <b>204</b>. In one embodiment the two NOCs can be combined to one large NOC. Each NOC (<b>202</b>/<b>204</b>) is connected to SRAM (<b>230</b>/<b>260</b>), a buffer (<b>232</b>/<b>262</b>), processor (<b>220</b>/<b>250</b>), and a data path controller (<b>222</b>/<b>252</b>) via an XOR engine (<b>224</b>/<b>254</b>) and an ECC engine (<b>226</b>/<b>256</b>). The ECC engines <b>226</b>/<b>256</b> are used to perform error correction, as known in the art. The XOR engines <b>224</b>/<b>254</b> are used to XOR the data so that data can be combined and stored in a manner that can be recovered in case there is a programming error. The data path controller is connected to an interface module for communicating via four channels with memory packages. Thus, the top NOC <b>202</b> is associated with an interface <b>228</b> for four channels for communicating with memory packages and the bottom NOC <b>204</b> is associated with an interface <b>258</b> for four additional channels for communicating with memory packages. Each interface <b>228</b>/<b>258</b> includes four Toggle Mode interfaces (TM Interface), four buffers and four schedulers. There is one scheduler, buffer and TM Interface for each of the channels. The processor can be any standard processor known in the art. The data path controllers <b>222</b>/<b>252</b> can be a processor, FPGA, microprocessor or other type of controller. The XOR engines <b>224</b>/<b>254</b> and ECC engines <b>226</b>/<b>256</b> are dedicated hardware circuits, known as hardware accelerators. In other embodiments, the XOR engines <b>224</b>/<b>254</b> and ECC engines <b>226</b>/<b>256</b> can be implemented in software. The scheduler, buffer, and TM Interfaces are hardware circuits.

0052<figref idref="DRAWINGS">FIG. 5</figref> is a block diagram of one embodiment of a memory package. For example, the memory package of <figref idref="DRAWINGS">FIG. 5</figref> is an example implementation of a memory package included in memory packages <b>14</b> of <figref idref="DRAWINGS">FIG. 1</figref> or memory packages <b>104</b> of <figref idref="DRAWINGS">FIG. 2</figref>. <figref idref="DRAWINGS">FIG. 5</figref> shows a plurality of memory die <b>292</b> connected to a memory bus (data lines and chip enable lines) <b>294</b>. The memory bus <b>294</b> connects to a Toggle Mode Interface <b>296</b> for communicating with the TM Interface of an BEP circuit (see e.g. <figref idref="DRAWINGS">FIG. 4</figref>). In some embodiments, the memory package can include a small controller connected to the memory bus and the TM Interface. The memory package can have one or more memory die. In one embodiment, each memory package includes eight or <b>16</b> memory die; however, other numbers of memory die can also be implemented. The technology described herein is not limited to any particular number of memory die.

0053<figref idref="DRAWINGS">FIG. 6</figref> is a functional block diagram of one embodiment of a memory die <b>300</b>. Note that memory is one example implementation of memory die <b>292</b> of <figref idref="DRAWINGS">FIG. 5</figref>. The components depicted in <figref idref="DRAWINGS">FIG. 6</figref> are electrical circuits. Memory die <b>300</b> includes a three dimensional memory structure <b>326</b> of memory cells (such as, for example, a 3D array of memory cells), control circuitry <b>310</b>, and read/write circuits <b>328</b>. In other embodiments, a two dimensional array of memory cells can be used. Memory structure <b>326</b> is addressable by word lines via a row decoder <b>324</b> and by bit lines via a column decoder <b>332</b>. The read/write circuits <b>328</b> include multiple sense blocks <b>350</b> including SB<b>1</b>, SB<b>2</b>, . . . , SBp (sensing circuitry) and allow a page of memory cells to be read or programmed in parallel. Commands and data are transferred between to/from memory die <b>300</b> via lines <b>318</b>. In one embodiment, memory die <b>300</b> includes a set of input and/or output (I/O) pins that connect to lines <b>318</b>.

0054Memory structure <b>326</b> may comprise one or more arrays of memory cells including a 3D array. The memory structure may comprise a monolithic three dimensional memory structure in which multiple memory levels are formed above (and not in) a single substrate, such as a wafer, with no intervening substrates. The memory structure may comprise any type of non-volatile memory that is monolithically formed in one or more physical levels of arrays of memory cells having an active area disposed above a silicon substrate. The memory structure may be in a non-volatile memory device having circuitry associated with the operation of the memory cells, whether the associated circuitry is above or within the substrate.

0055Control circuitry <b>310</b> cooperates with the read/write circuits <b>328</b> to perform memory operations (e.g., erase, program, read, and others) on memory structure <b>326</b>, and includes a state machine <b>312</b>, an on-chip address decoder <b>314</b>, a power control module <b>316</b> and a temperature detection circuit <b>318</b>. The state machine <b>312</b> provides die-level control of memory operations. Temperature detection circuit <b>318</b> (which is on memory die <b>300</b>) is configured to detect temperature at the memory structure <b>326</b>, and can be any suitable temperature detection circuit known in the art. In one embodiment, state machine <b>312</b> is programmable by software. In other embodiments, state machine <b>312</b> does not use software and is completely implemented in hardware (e.g., electrical circuits). In one embodiment, control circuitry <b>310</b> includes registers, ROM fuses and other storage devices for storing default values such as base voltages and other parameters.

0056The on-chip address decoder <b>314</b> provides an address interface between addresses used by a host or controller to the hardware address used by the decoders <b>324</b> and <b>332</b>. Power control module <b>316</b> controls the power and voltages supplied to the word lines and bit lines during memory operations. It can include drivers for word line layers (discussed below) in a 3D configuration, select transistors (e.g., SGS and SGD transistors, described below) and source lines. Power control module <b>316</b> may include charge pumps for creating voltages. The sense blocks include bit line drivers.

0057Multiple memory elements in memory structure <b>326</b> may be configured so that they are connected in series or so that each element is individually accessible. By way of non-limiting example, flash memory devices in a NAND configuration (NAND flash memory) typically contain memory elements connected in series. A NAND string is an example of a set of series-connected memory cells and select gate transistors that can be used to implement memory structure <b>326</b> as a three-dimensional memory structure.

0058A NAND flash memory array may be configured so that the array is composed of multiple NAND strings of which a NAND string is composed of multiple memory cells sharing a single bit line and accessed as a group. Alternatively, memory elements may be configured so that each element is individually accessible, e.g., a NOR memory array. NAND and NOR memory configurations are exemplary, and memory cells may be otherwise configured.

0059The memory cells may be arranged in the single memory device in an ordered array, such as in a plurality of rows and/or columns. However, the memory elements may be arrayed in non-regular or non-orthogonal configurations, or in structures not considered arrays.

0060A three dimensional memory array is arranged so that memory cells occupy multiple planes or multiple memory device levels, thereby forming a structure in three dimensions (i.e., in the x, y and z directions, where the z direction is substantially perpendicular and the x and y directions are substantially parallel to the major surface of the substrate).

0061As a non-limiting example, a three dimensional memory structure may be vertically arranged as a stack of multiple two dimensional memory device levels. As another non-limiting example, a three dimensional memory array may be arranged as multiple vertical columns (e.g., columns extending substantially perpendicular to the major surface of the substrate, i.e., in they direction) with each column having multiple memory cells. The vertical columns may be arranged in a two dimensional configuration, e.g., in an x-y plane, resulting in a three dimensional arrangement of memory cells, with memory cells on multiple vertically stacked memory planes. Other configurations of memory elements in three dimensions can also constitute a three dimensional memory array.

0062By way of non-limiting example, in a three dimensional NAND memory array, the memory elements may be coupled together to form vertical NAND strings with charge-trapping material that traverse across multiple horizontal memory device levels. One example of a three dimensional NAND memory array that can be used to implement memory structure <b>126</b> can be found in U.S. Pat. No. 9,343,156, incorporated herein by reference in its entirety.

0063Other three dimensional configurations can be envisioned wherein some NAND strings contain memory elements in a single memory level while other strings contain memory elements which span through multiple memory levels. Three dimensional memory arrays may also be designed in a NOR configuration and in a ReRAM configuration.

0064A person of ordinary skill in the art will recognize that the technology described herein is not limited to a single specific memory structure, but covers many relevant memory structures within the spirit and scope of the technology as described herein and as understood by one of ordinary skill in the art.

0065Although an example memory system is a three dimensional memory structure that includes vertical NAND strings with charge-trapping material, other (2D and 3D) memory structures can also be used with the technology described herein. For example, floating gate memories (e.g., NAND-type and NOR-type flash memory), ReRAM memories, magnetoresistive memory (e.g., MRAM), and phase change memory (e.g., PCRAM) can also be used.

0066One example of a ReRAM memory includes reversible resistance-switching elements arranged in cross point arrays accessed by X lines and Y lines (e.g., word lines and bit lines). One example of a three dimensional memory array that can be used to implement memory structure <b>126</b> can be found in U.S. Patent Application 2016/0133836, “High Endurance Non-Volatile Storage,” incorporated herein by reference in its entirety.

0067In another embodiment, the memory cells may include conductive bridge memory elements. A conductive bridge memory element may also be referred to as a programmable metallization cell. A conductive bridge memory element may be used as a state change element based on the physical relocation of ions within a solid electrolyte. In some cases, a conductive bridge memory element may include two solid metal electrodes, one relatively inert (e.g., tungsten) and the other electrochemically active (e.g., silver or copper), with a thin film of the solid electrolyte between the two electrodes. As temperature increases, the mobility of the ions also increases causing the programming threshold for the conductive bridge memory cell to decrease. Thus, the conductive bridge memory element may have a wide range of programming thresholds over temperature.

0068Magnetoresistive memory (MRAM) stores data by magnetic storage elements. The elements are formed from two ferromagnetic plates, each of which can hold a magnetization, separated by a thin insulating layer. One of the two plates is a permanent magnet set to a particular polarity; the other plate's magnetization can be changed to match that of an external field to store memory. This configuration is known as a spin valve and is the simplest structure for an MRAM bit. A memory device is built from a grid of such memory cells. In one embodiment for programming, each memory cell lies between a pair of write lines arranged at right angles to each other, parallel to the cell, one above and one below the cell. When current is passed through them, an induced magnetic field is created.

0069Phase change memory (PCRAM) exploits the unique behavior of chalcogenide glass. One embodiment uses a GeTe—Sb2Te3 super lattice to achieve non-thermal phase changes by simply changing the co-ordination state of the Germanium atoms with a laser pulse (or light pulse from another source). Therefore, the doses of programming are laser pulses. The memory cells can be inhibited by blocking the memory cells from receiving the light. Note that the use of “pulse” in this document does not require a square pulse, but includes a (continuous or non-continuous) vibration or burst of sound, current, voltage light, or other wave.

0070<figref idref="DRAWINGS">FIG. 7</figref> is a block diagram of one embodiment of a solid state drive <b>400</b> that comprises a controller <b>402</b>, non-volatile memory packages <b>404</b> for storing data, DRAM/ReRAM <b>406</b>, and a compute engine <b>412</b> near the location for that data that can be used to perform common data manipulation operations. Controller <b>402</b> includes FEP circuit <b>410</b>. In the embodiment of <figref idref="DRAWINGS">FIG. 7</figref>, compute engine <b>412</b> is integrated within FEP circuit <b>410</b> and the one or more BEP circuits <b>422</b> are now incorporated within the memory packages <b>404</b>. In this implementation, the SSD controller contains only one ASIC, for the FEP circuit. That is, the SSD controller <b>402</b> is in communication with the memory packages <b>404</b>, where each memory package includes multiple memory die <b>420</b> and one or more BEP circuits <b>422</b>. One example embodiment of memory die <b>420</b> is depicted in <figref idref="DRAWINGS">FIG. 6</figref>. One example of BEP circuit <b>422</b> is depicted in <figref idref="DRAWINGS">FIG. 4</figref>. One example of FEP circuit<b>410</b> with an integrated compute engine <b>412</b> is depicted in <figref idref="DRAWINGS">FIG. 3</figref>. DRAM/ReRAM <b>406</b> is an example of a local memory (e.g., local high speed working volatile memory).

0071<figref idref="DRAWINGS">FIG. 8</figref> is a block diagram of one embodiment of a solid state drive <b>450</b> that comprises a controller <b>460</b>, non-volatile memory packages <b>454</b> for storing data, DRAM/ReRAM <b>456</b>, and a compute engine <b>464</b> near the location of the data that can be used to perform common data manipulation operations. In the embodiment of <figref idref="DRAWINGS">FIG. 8</figref> the compute engine <b>464</b> is a standalone ASIC (application specific integrated circuit) that is integrated with the SSD controller <b>460</b> as a SoC. In this implementation, controller <b>460</b> includes a FEP circuit<b>460</b> in communication with one or more BEP circuits <b>462</b>. Compute engine <b>464</b> is outside of and connected to FEP circuit<b>462</b>, connected to the BEP circuit and connected to the high speed DRAM memory with separate interfaces. The bandwidth available to the compute engine <b>464</b> is lower than or equal to the bandwidth of the embodiment of <figref idref="DRAWINGS">FIG. 2</figref>. This implementation is preferred when the development of the FEP circuit<b>462</b> and the compute engine <b>464</b> needs to be kept separate. One example of BEP circuit <b>422</b> is depicted in <figref idref="DRAWINGS">FIG. 4</figref>. One example of memory packages <b>454</b> is depicted in <figref idref="DRAWINGS">FIG. 5</figref>. DRAM/ReRAM <b>456</b> is an example of a local memory (e.g., local high speed volatile working memory).

0072<figref idref="DRAWINGS">FIG. 9</figref> is a block diagram of one embodiment of a FEP circuit without a compute engine, that is suitable for the embodiment of <figref idref="DRAWINGS">FIG. 8</figref> (e.g., FEP circuit <b>460</b>). <figref idref="DRAWINGS">FIG. 9</figref> shows all the components of <figref idref="DRAWINGS">FIG. 3</figref>, but without the compute engine. That is, <figref idref="DRAWINGS">FIG. 9</figref> depicts PCIe interface <b>150</b>, host processor <b>152</b>, NOC <b>154</b>, memory processor <b>156</b>, SRAM <b>160</b>, DRAM controller <b>162</b>, and PCIe Interfaces <b>164</b> and <b>166</b>. In the embodiment of <figref idref="DRAWINGS">FIG. 9</figref>, the SSD controller will include two BEP circuits; therefore there are two PCIe Interfaces. Each PCIe Interface communicates with one of the BEP circuits. In other embodiments, there can be more or less than two BEP circuits; therefore, there can be more or less than two PCIe Interfaces.

0073<figref idref="DRAWINGS">FIG. 10</figref> is a block diagram of one embodiment of a solid state drive <b>600</b> that comprises a controller <b>602</b>, non-volatile memory packages <b>604</b> for storing data, DRAM/ReRAM <b>606</b>, and compute engine <b>616</b> near the location of the data that can be used to perform common data manipulation operations. Controller <b>602</b> includes a FEP circuit <b>612</b> connected to one or more BEP circuits <b>614</b>. In this embodiment a compute engine <b>616</b> is integrated with an BEP circuit <b>614</b>. That is, the compute engine <b>616</b> is implemented in the ASIC for the BEP circuit <b>614</b>. The bandwidth available to the compute engine is now determined by the number of toggle mode channels present in each BEP circuit and the bandwidth of the toggle mode channels. The BEP circuit <b>614</b> may also contain an optional interface <b>620</b> to connect to the DRAM/ReRAM chip. A direct interface to the high speed memory provides the compute engine <b>616</b> with fast access to the memory to store temporary working data. In the absence of a direct interface, temporary working data is streamed via the interface that connects the BEP circuits to the FEP circuit. One example of FEP circuit <b>612</b> is depicted in <figref idref="DRAWINGS">FIG. 9</figref>. One example of memory packages <b>604</b> is depicted in <figref idref="DRAWINGS">FIG. 5</figref>. DRAM/ReRAM <b>606</b> is an example of a local memory (e.g., local high speed volatile working memory).

0074<figref idref="DRAWINGS">FIG. 11</figref> is a block diagram of one embodiment of an BEP circuit that includes a compute engine. The embodiment of the BEP circuit of <figref idref="DRAWINGS">FIG. 11</figref> is appropriate for use in the embodiment of <figref idref="DRAWINGS">FIG. 10</figref> (e.g., as an BEP circuit <b>614</b>). The components of <figref idref="DRAWINGS">FIG. 11</figref> are the same as the components of <figref idref="DRAWINGS">FIG. 4</figref>, but further includes a compute engine <b>702</b> connected to the top NOC <b>202</b> and a second compute engine <b>704</b> connected to the bottom NOC <b>204</b>. In another embodiment, one compute engine can connect to both NOCs. In another embodiment, the two NOCs are connected together and the combined NOC will connect to one, two or multiple compute engines. In the embodiment of <figref idref="DRAWINGS">FIG. 11</figref>, there is one compute engine for each set of four channels. In other embodiments, the channels grouped together can include more or less than four channels.

0075<figref idref="DRAWINGS">FIG. 12</figref> is a block diagram of one embodiment of a solid state drive <b>800</b> that comprises a controller <b>802</b>, non-volatile memory packages <b>804</b> for storing data, DRAM/ReRAM <b>806</b> and a compute engine <b>824</b> near the location of the data that can be used to perform common data manipulation operations. Controller <b>802</b> includes FEP circuit <b>820</b> connected to one or more BEP circuits <b>822</b>. In the embodiment of <figref idref="DRAWINGS">FIG. 12</figref>, compute engine <b>824</b> is a standalone ASIC that is connected directly to the toggle mode (TM) channels from the BEP circuits. In such implementations, the compute engine should optionally include an ECC engine in order to decode and correct data read from the flash memory (or other type of nonvolatile memory in the memory packages) before being processed by the compute engine. The compute engine <b>824</b> can also be connected to the high speed, high-bandwidth DRAM memory <b>806</b> through a standard DDR interface to the DRAM/ReRAM chip and to FEP circuit<b>820</b>. One example of FEP circuit<b>820</b> is depicted in <figref idref="DRAWINGS">FIG. 9</figref>. One example of memory packages <b>804</b> is depicted in <figref idref="DRAWINGS">FIG. 5</figref>. One example of BEP circuit <b>822</b> is depicted in <figref idref="DRAWINGS">FIG. 4</figref>. DRAM/ReRAM <b>806</b> is an example of a local memory (e.g., local high speed volatile memory).

0076The embodiments discussed above show various implementations of integrating the compute engine with the controller. In a different set of implementations, the compute engine can be integrated with the memory package, referred to as memory package level integration.

0077<figref idref="DRAWINGS">FIG. 13</figref> is a block diagram of one embodiment of a solid state drive <b>850</b> that includes memory package level integration, comprising a controller <b>852</b>, non-volatile memory packages <b>854</b> for storing data, DRAM/ReRAM <b>856</b> and a compute engine <b>862</b> near the location of the data that can be used to perform common data manipulation operations. Controller <b>852</b> includes FEP circuit <b>858</b> connected to one or more BEP circuits <b>860</b>. The one or more BEP circuits <b>860</b> connect to the non-volatile memory packages <b>854</b>. One example of FEP circuit <b>858</b> is depicted in <figref idref="DRAWINGS">FIG. 9</figref>. One example of BEP circuit <b>860</b> is depicted in <figref idref="DRAWINGS">FIG. 4</figref>. DRAM/ReRAM <b>856</b> is an example of a local memory (e.g., local high speed volatile working memory). In the embodiment depicted in <figref idref="DRAWINGS">FIG. 13</figref>, the compute engine is integrated with each memory package. A memory package. which typically includes multiple memory die (e.g., NAND non-volatile memory or other type of non-volatile memory), is now modified to include the compute engine ASIC (also known as a compute engine core) within the memory package. In one embodiment, the memory package should also include an ECC engine (or at least the decoder portion of the ECC engine) to decode code words read from the memory and to correct the data read from the non-volatile memory die before being processed by the compute engine. Thus, compute engine <b>862</b> includes an ECC engine. In other embodiments, the compute engine can operate on data that has not been subjected to ECC decoding. The memory package can optionally include high-speed memory like DRAM to support the compute engine with access to temporary working data. As the data management operations are within the memory package, the bandwidth available to the compute engine can be much higher than the toggle mode (TM) bandwidth available outside of the memory package.

0078<figref idref="DRAWINGS">FIG. 13A</figref> is a block diagram of one embodiment of a solid state drive <b>880</b> that includes controller <b>882</b>, non-volatile memory packages <b>884</b> for storing data, and DRAM/ReRAM <b>886</b>. Controller <b>882</b> includes FEP circuit <b>888</b> connected to one or more BEP circuits <b>890</b>. The one or more BEP circuits <b>890</b> connect to the non-volatile memory packages <b>884</b>. One example of FEP circuit <b>888</b> is depicted in <figref idref="DRAWINGS">FIG. 9</figref>. One example of BEP circuit <b>890</b> is depicted in <figref idref="DRAWINGS">FIG. 4</figref>. DRAM/ReRAM <b>886</b> is an example of a local memory (e.g., local high speed volatile working memory).

0079The embodiment depicted in <figref idref="DRAWINGS">FIG. 13A</figref> includes multiple (or distributed) compute engines, such that compute engine <b>892</b> is positioned in controller <b>882</b> and a set of compute engines (with built-in ECC engine) <b>894</b> are positioned in non-volatile memory packages <b>884</b>. For example, compute engine <b>892</b> is a standalone ASIC that is connected directly to the toggle mode (TM) channels from the BEP circuits (the interface between the BEP circuits and the memory packages/die). Compute engine <b>892</b> can also be connected to the high speed, high-bandwidth DRAM memory <b>886</b> through a standard DDR interface to the DRAM/ReRAM chip and to FEP circuit <b>888</b>. Compute engine <b>894</b> is integrated with each memory package. In one embodiment, the memory package also includes an ECC engine (or at least the decoder portion of the ECC engine) to decode code words read from the memory and to correct the data read from the non-volatile memory die before being processed by the compute engine. Thus, compute engine <b>894</b> includes an ECC engine. In other embodiments, the compute engine can operate on data that has not been subjected to ECC decoding. The memory package can optionally include high-speed memory like DRAM to support the compute engine with access to temporary working data. As some data manipulation operations are within the memory package, the bandwidth available to the compute engine can be much higher than the toggle mode (TM) bandwidth available outside of the memory package. In some embodiments, the compute engines <b>892</b> and <b>894</b> will split up the work performed on the data. For example, code from the hosts can program the system to perform some operations on compute engine <b>892</b> and other operations on compute engine <b>894</b>. For instance, the compute engine <b>894</b> could perform error correction coding (ECC) function along with simple application level tests, and the compute engine <b>892</b> could be executing a flash translation layer (FTL) optimized for sequential or indexed-sequential workloads, along with more complex filtering, sorting and grouping functions at the application query level.

0080<figref idref="DRAWINGS">FIG. 14</figref> is a block diagram of one embodiment of a memory package that includes a compute engine. The embodiment of <b>14</b> can be used to implement one of the memory packages <b>854</b> in <figref idref="DRAWINGS">FIG. 13</figref> or memory packages <b>884</b> of <figref idref="DRAWINGS">FIG. 13A</figref>. The memory package of <figref idref="DRAWINGS">FIG. 14</figref> includes a plurality of memory die <b>904</b> connected to a memory bus <b>906</b> (analogous to the memory bus of <figref idref="DRAWINGS">FIG. 5</figref>). Memory bus <b>906</b> is connected to a TM interface <b>908</b> for communicating with an BEP circuit. Additionally, <figref idref="DRAWINGS">FIG. 14</figref> shows a compute engine <b>910</b> connected to the memory bus and to an ECC engine <b>912</b>. The ECC engine <b>912</b> is also connected to memory bus <b>906</b>. Memory read from a memory die can be subjected to ECC decoding (including fixing errors) and then presented to the compute engine <b>910</b> to perform any of the compute operations discussed herein.

0081<figref idref="DRAWINGS">FIG. 15</figref> is a block diagram of one embodiment of a solid state drive <b>950</b> that comprises a controller <b>952</b>, non-volatile memory packages <b>956</b> for storing data, DRAM/ReRAM <b>954</b>, and a compute engine near the location of that data that can be used to perform common data manipulation operations. Controller <b>952</b> includes FEP circuit <b>960</b> connected to one or more BEP circuits <b>962</b>. The one or more BEP circuits <b>962</b> connect to the non-volatile memory packages <b>956</b>. One example of FEP circuit <b>960</b> is depicted in <figref idref="DRAWINGS">FIG. 9</figref>. One example of BEP circuit <b>962</b> is depicted in <figref idref="DRAWINGS">FIG. 4</figref>. DRAM/ReRAM <b>954</b> is an example of a local memory (e.g., local high speed volatile working memory).

0082The embodiment of <figref idref="DRAWINGS">FIG. 15</figref> implements memory package level integration. For example, each memory package includes multiple memory die and a compute engine <b>970</b> integrated within each memory die <b>972</b>. In one embodiment, the compute engine will include an ECC engine to decode (including correcting) data read from the memory die. The ECC engine can be part of the compute engine or separate from the compute engine but otherwise included in the memory die.

0083For purposes of this document, the concept of the working memory (or local memory or DRAM discussed above) being connected to the controller includes the working memory being inside the controller. A compute engine that is in communication with the controller can be inside or separate from the controller.

0084<figref idref="DRAWINGS">FIG. 16</figref> is a block diagram of one embodiment of a memory die <b>1000</b> that includes a compute engine. For example, the memory die <b>1000</b> is an example implementation of memory die <b>972</b> of <figref idref="DRAWINGS">FIG. 15</figref>. The embodiment of <figref idref="DRAWINGS">FIG. 16</figref> includes the elements of the embodiment of <figref idref="DRAWINGS">FIG. 6</figref>. For example, memory die <b>1000</b> includes a three dimensional memory structure <b>326</b> of memory cells (such as, for example, a 3D array of memory cells), control circuitry <b>310</b>, read/write circuits <b>328</b>, row decoder <b>324</b> and column decoder <b>332</b>. Control circuitry <b>310</b> includes state machine <b>312</b>, on-chip address decoder <b>314</b>, a power control module <b>316</b> and a temperature detection circuit <b>318</b>. Additionally, in the embodiment of <figref idref="DRAWINGS">FIG. 16</figref>, control circuitry <b>310</b> further includes ECC engine <b>1017</b> and compute engine <b>1019</b>. Data read from the memory structure <b>326</b> is decoded using ECC engine <b>1017</b> and provided to compute engine <b>1019</b> for performing various compute operations, as discussed herein.

0085While the embodiments discussed above show the SSD controller to be implemented as a two ASIC solution containing a BEP ASIC and a FEP ASIC, it is also possible that the SSD controller is implemented with more or less than two ASICs. In that case, the design space can be expanded to place the compute engine within any one or more of the ASICs. Additionally, the compute engine can be placed outside of the ASICs. In other embodiments, the SSD controller can include different architectures, other than the FEP/BEP architecture. Even in the other architectures, the SSD controller can still be configured to include a compute engine inside one of the ASICs or circuits or modules. Additionally, a compute engine can be added to SSDs that are not implemented using ASICs, but implemented using other hardware.

0086The embodiment of <figref idref="DRAWINGS">FIG. 15</figref> includes integrating the compute engine within the memory die (such as a NAND memory die or ReRAM memory die). <figref idref="DRAWINGS">FIG. 17</figref> is a block diagram providing additional details for implementing an embodiment of the system of <figref idref="DRAWINGS">FIG. 15</figref>. Specifically, <figref idref="DRAWINGS">FIG. 17</figref> shows a host in communication with a SSD <b>1100</b> (implemented on a printed circuit board) that includes a Big NVM controller <b>1102</b> and a Small NVM controller <b>1114</b>. The Big NVM controller <b>1102</b> is in communication with DRAM <b>1104</b> and memory package <b>1106</b>.

0087In one embodiment, memory package <b>1106</b> includes several memory die <b>1110</b>, optional DRAM (or MRAM/RRAM/PCM/eDRAM) <b>1112</b>, and Small NVM Controller <b>1114</b>. Each of the memory die <b>1110</b> has an on die compute engine (CE). In one embodiment the on die compute engine is implemented using CMOS technology on the top surface of a substrate and under the monolithic three-dimensional memory array. Potentially, eDRAM/STT-MRAM/PCM as well as SRAM can be integrated. The on die compute engine (CE) can perform some of the data manipulation operations.

0088In one embodiment, Small NVM Controller <b>1114</b> includes a compute engine (CE) that can perform some of the data manipulation operations. Small NVM Controller <b>1114</b> can communicate with the internal memory dies and external chips (i.e. Big NVM controller and DRAM in <figref idref="DRAWINGS">FIG. 17</figref>). Optional DRAM <b>1112</b> is used for the Small NVM Controller <b>1114</b> to store working data sets. By off-loading computation from the Big NVM Controller <b>1102</b> to Small NVM controller with a compute engine (CE) <b>1114</b> and the simple CE of the memory die <b>1110</b>, the external DRAM requirement and communication overhead can be reduced.

0089<figref idref="DRAWINGS">FIG. 17</figref> shows that each of Big NVM Controller <b>1102</b>, DRAM <b>1104</b>, memory die <b>1110</b>, DRAM <b>1112</b> and Small NVM Controller <b>1114</b> can be implemented on separate silicon die in three different packages mounted on one printed circuit board. Thus, <figref idref="DRAWINGS">FIG. 17</figref> provides a big and small NVM controller architecture. The Big NVM Controller <b>1102</b> interfaces with the host and DRAM. The Small NVM Controller <b>1114</b>can be inside any of the memory packages. The Small NVM Controller <b>1114</b> includes a computational engine with optional DRAM and manages multiple NVM channels. A mapping table can be stored in the optional DRAM (or MRAM/PRAM).

0090<figref idref="DRAWINGS">FIG. 18</figref> is a block diagram of one embodiment of a memory die <b>1200</b> with circuitry under the memory array. <figref idref="DRAWINGS">FIG. 18</figref> shows a monolithic three-dimensional memory structure <b>1202</b> with multiple layers. Underneath the memory structure <b>1202</b> is circuitry <b>1204</b> that is implemented on the top surface of the substrate <b>1206</b> and under the memory array <b>1202</b>. In one embodiment, the circuitry <b>1204</b> is implemented using CMOS technology. For example, simple computational logic can be integrated in the CMOS logic under the memory array <b>1202</b> potentially with eDRAM/STT-MRAM/PCM as well as SRAM/latches. Simple circuitry logic (i.e., randomizer, ID generator, PUF, or AES) and simple error management logic (i.e., error location map or a simple error avoiding algorithm such as read reference optimizer) as well as ECC can be integrated in the CMOS logic under the memory array <b>1202</b> as examples of the compute engine discussed above. This improves latency and performance by eliminating data transfer overhead from the memory die to the separate controller die. An FPGA could be integrated, supporting multiple configurations with a single system on a chip as an aforementioned compute engine. An FPGA can be integrated, supporting multiple configurations within a system on a chip.

0091Additionally, other functions can be integrated as an aforementioned compute engine. For example, a CPU or parallel computational engine can be integrated as an aforementioned compute engine. An SIMD engine (“GPU”), neural network, DSP engine (e.g., image/audio processing), digital logic operation (multiplication, addition, subtraction, XOR, etc.), data mining (apriori, k-means, pagerank, decision tree) or pattern matching (i.e., Hamming distance calculation), FPGA fabric supporting multiple configurations in the memory die, high speed I/O circuits with memory equalizers, circuits for optical or capacitor/inductive coupling based on interconnections can also be used. In one embodiment, the compute engine needs to be able to work with encrypted data when AES is bypassed for specific applications. In some embodiments, the compute engine may need to work with erroneous data when ECC is bypassed for specific applications

0092<figref idref="DRAWINGS">FIG. 19</figref> is a block diagram of one embodiment of a memory die <b>1300</b> with circuitry <b>1304</b> under the memory array <b>1302</b> for using the non-volatile memory die <b>1300</b> as a non-volatile-FPGA. The memory die <b>1300</b> will include a three-dimensional monolithic memory array <b>1302</b>. Implemented on the top surface of the substrate <b>1306</b>, and under the memory array <b>1302</b>, will be CMOS logic <b>1304</b> that implements a FPGA to be used as a compute engine (per the discussion above). This system will use the memory array <b>1302</b> (NAND or other type of non-volatile memory) as configuration storage for the reconfigurable logic <b>1304</b> of the FPGA. That is, configuration data stored in memory array <b>1302</b> is used to configure the FPGA's. This will make the FPGA non-volatile. This will allow for fast boot up compared to conventional FPGAs, which require a reading of configuration data from a discrete nonvolatile memory device to the volatile FPGA cell array. When the FPGA (hardware accelerator/compute engine) is not needed, the configuration storage (the memory array) can be used as just normal non-volatile storage, saving idle power.

0093In many systems, the complete set of L2P tables are stored in the non-volatile memory (e.g., the Memory Packages), with a subset being cached within local working memory (e.g., see DRAM [or ReRam or SRAM] of <figref idref="DRAWINGS">FIGS. 1, 2, 7, 8, 10, 12, 13, 13A, 15</figref>, and <b>17</b>, or another buffer for the Controller). When there is a cache miss because the needed L2P table (or portion of table) is not within the cache of the local working memory, then the needed L2P table (or portion of table) is retrieved from the non-volatile memory and loaded into the cache of the local working memory. The L2P tables consume a significant amount of space in the local working memory.

0094In certain embodiments, the compute engine discussed above with respect to <figref idref="DRAWINGS">FIGS. 1-19</figref> will also use the local working memory to stored data while performing its computational operations as described above. The use of the local working memory by the compute engine may reduce the space available for the cache storing the L2P tables, thereby, causing a greater “miss” rate for the cache and degrading performance. Limiting the amount of local working memory available to the compute engine will reduce the performance of the compute engine

0095To alleviate the performance issues related to too much demand on the local working memory, it is proposed to reduce the amount of space needed to store L2P tables in the working memory without significantly increasing the “miss” rate by maintaining coarse logical address to physical address tables in the working memory for use with sequentially accessed data and maintaining fine logical address to physical address tables in the working memory for use with randomly accessed data. Certain embodiments disclosed herein take advantage of special access patterns of database applications (or other applications) to use a lower granularity of L2P tables (e.g., erase block level entry L2P tables) for data with known sequential access patterns. Other intermediate levels of granularity such as sub-erase block or word line can also be used with these known sequential access patterns. Page level entries are continued to be used for data with known random access patterns.

0096<figref idref="DRAWINGS">FIG. 20</figref> depicts a portion of an example database and illustrates an example of randomly accessed data and sequentially accessed data. <figref idref="DRAWINGS">FIG. 20</figref> shows two levels of branch nodes and one level of leaf nodes. The branch nodes act as indexes to lower level nodes. The leaf nodes can include many data entries (e.g., in this case names). The first level of branch nodes includes nodes B, F, H and Sam. Node B points to nodes Ba, C and Cr of the second level of branch nodes. Node F points to nodes Fe, Kar and Lu of the second level of branch nodes. Node N points to nodes Na, Pa and Ph of the second level of branch nodes. Node Sam points to nodes Samm, St and V of the second level of branch nodes. Branch node Kar points to leaf nodes Krl, Kathy, Ken and Kim. Branch node Lu points to leaf nodes Luis, Mark, Mary, Mike and Manny. Branch node Na points to leaf nodes Nan, Nancy, Nicky, Nicole and Norm. Branch node Pa points to leaf nodes Pablo, Paul, Paula and Peter. Branch node Ph points to leaf nodes Phil, Pierre, Rachel, Rajiv and Raoul.

0097In the example of <figref idref="DRAWINGS">FIG. 20</figref>, the branch nodes are accesses randomly and, therefore, are determined to be randomly accessed data (for a random workload). The leaf nodes are stored in consecutive addresses (i.e. in alphabetical order) in the non-volatile memory as sequentially accessed data; therefore, they can be written into the non-volatile memory together as such data is serialized using a write buffer between the host and the non-volatile memory for higher performance.

0098Log-structured file systems optimized for the non-volatile memory can support aggregation of multiple random write operations into a single sequential write operation. Then, it typically requires sequential reading of the selected leaf blocks for finding a specific node (e.g., finding a specific last name) when it needs to be searched. HDFS (Hadoop File System) and analytics databases are additional examples that require sequential access to the non-volatile memory. Thus, the SSD (or other device) workload for the database application can be divided into random and sequential workloads.

0099For example, the non-volatile memory can be divided into (at least) two sections. A first section (or portion) of memory (e.g., a first set of memory cells) is configured to store sequentially accessed data (e.g., leaf nodes). A second section (or portion) of memory (e.g., a second set of memory cells) is configured to store randomly accessed data (e.g., meta data, pointers, branch bodes, etc.). The first section/portion is physically separate from the second section/portion. In one example implementation, a first set of memory die for a package or system comprise the first section and a second set of memory die for the package or system comprise the second section. The different sections can also be on the same memory die. L2P tables for data stored in the second section (i.e., store randomly accessed data) will include entries for each page of data and are referred to fine L2P tables (or fine logical address to physical address tables). L2P tables for data stored in the first section (i.e., sequentially accessed data) will include entries at the block level and are referred to a coarse L2P tables (or coarse logical address to physical address tables). In one example of a coarse L2P table, there is one L2P entry per block, where the block is the unit of erase. In one example, each L2P entry includes a logical address used by the host and a physical address in the non-volatile memory. In other embodiments, coarse L2P tables for data stored in the second section (i.e., sequential data) will include entries at the word line level or other sub-block level.

0100Because the L2P tables for data stored in the first section (i.e., sequentially accessed data) will include entries at the block level, there will be many less L2P entries. For example, <figref idref="DRAWINGS">FIG. 21</figref> is a block diagram of an example block of non-volatile memory that includes sixty four word lines (WL<b>0</b>-WL<b>63</b>), with each word line having three pages (Page <b>0</b>, Page <b>1</b> and Page <b>2</b>). Thus, the example block of <figref idref="DRAWINGS">FIG. 21</figref> includes 192 pages. Other blocks can have more or less than sixty four word lines and more or less than three pages per word line. If the example block of <figref idref="DRAWINGS">FIG. 21</figref> is used to store random data than the corresponding L2P table would include <b>192</b> L2P entries. However, if the example block of <figref idref="DRAWINGS">FIG. 21</figref> is used to store sequential data than the corresponding L2P table would include 1 L2P entry, which saves 191 L2P entries' worth of space. As a typical system can have thousands or millions of blocks, the savings for only storing 1 L2P entry per block (that is, the savings for using coarse L2P tables instead of fine L2P tables) is very significant. The reduction in memory space needed by coarse L2P tables opens up room in the local working memory for the local compute engine, without increasing the “miss” rate for the cache of L2P tables in the local working memory. Because the local compute engine will have more local (volatile) working memory (e.g., DRAM) to work with, computational performance will increase.

0101<figref idref="DRAWINGS">FIG. 22</figref> is a block diagram of a block of non-volatile memory system (e.g., a SSD or other device) that reduces the amount of space needed to store L2P tables in the working memory without significantly increasing the “miss” rate by maintaining coarse L2P tables in the working memory for use with sequentially accessed data and maintaining fine L2P tables in the working memory for use with randomly accessed data. The block diagram of <figref idref="DRAWINGS">FIG. 22</figref>, while most similar to <figref idref="DRAWINGS">FIG. 1</figref>, can be used to generalize and applies to any of the embodiments of <figref idref="DRAWINGS">FIGS. 1-2, 7-8, 10, 12, 13, 13A, 15, and 17-19</figref>. That is, the discussion herein about the technology for reducing the amount of space needed to store L2P tables in the working memory by maintaining coarse L2P tables and fine L2P tables applies to and can be implemented by all of the embodiments of <figref idref="DRAWINGS">FIGS. 1-2, 7-8, 10, 12, 13, 13A, 15, and 17-19</figref>.

0102<figref idref="DRAWINGS">FIG. 22</figref> depicts SSD (or other device) <b>1400</b> that includes controller <b>1402</b>, non-volatile memory <b>1404</b> (e.g., Memory Packages) and volatile working memory (e.g., DRAM) <b>1406</b>. Controller <b>1402</b> includes, among other things, a host interface <b>1420</b> and a local compute engine <b>1422</b> (see more complete discussion above of the compute engine). In other embodiments that incorporate the proposed technology for reducing the amount of space needed to store L2P tables in the working memory, as described above, the compute engine can be outside of the controller, including in a memory package (see e.g., the embodiments of <figref idref="DRAWINGS">FIGS. 13, 13A, 15 and 17-19</figref>) and/or in a memory die (see e.g., the embodiments of <figref idref="DRAWINGS">FIGS. 15 and 17-19</figref>).

0103Non-volatile memory <b>1404</b> include an area <b>1430</b> for storing a complete set of L2P tables, section/portion <b>1432</b> configured to store randomly accessed data and a section/portion <b>1434</b> configured to store sequentially accessed data. Section <b>1432</b> is physically separate from the second section <b>1434</b>. In other embodiments, the randomly accessed data and sequentially accessed data can be stored in a common section. In some embodiments, the coarse L2P tables (for sequentially accessed data) are stored in a same area as the fine L2P tables (for randomly accessed data). In other embodiments, the coarse L2P tables (for sequentially accessed data) are stored separately from the fine L2P tables (for randomly accessed data). In one example, the fine L2P tables (for randomly accessed data) are stored in the section <b>1432</b> and the coarse L2P tables (for sequentially accessed data) are stored in the section <b>1434</b>.

0104In one embodiment, volatile working memory <b>1406</b> includes sequential L2P cache <b>1440</b>, random L2P cache <b>1442</b>, working data for compute engine <b>1444</b> and miscellaneous region <b>1446</b>. Sequential L2P cache <b>1440</b> is a cache that stores a subset of the coarse L2P tables. Random L2P cache <b>1442</b> is a cache that stores a subset of the fine L2P tables. Working data for compute engine <b>1444</b> is memory space used by the local compute engine to perform data computations, as discussed above. Miscellaneous region <b>1446</b> is used by controller <b>1402</b> for other purposes. Because the coarse L2P tables stored in Sequential L2P cache <b>1440</b> are much smaller than the fine L2P tables, there is more room in volatile working memory <b>1406</b> for a bigger working data for compute engine <b>1444</b>, which results in higher performance for the local compute engine <b>1422</b>.

0105In one example implementation, compute engine <b>1422</b> is configured to use the coarse logical address to physical address tables of the sequential L2P cache <b>1440</b> to perform address translation between logical and physical addresses for the leaf nodes for one or more database data structures stored in the portion <b>1434</b> of non-volatile memory <b>1404</b> and compute engine <b>1422</b> is configured to use the fine logical address to physical address tables of random L2P cache <b>1442</b> to perform address translation between logical and physical addresses for the branch nodes for one or more database data structures stored in portion <b>1432</b> of non-volatile memory <b>1404</b>.

0106As discussed above, the memory system treats sequentially accessed data different than randomly accessed data. In one embodiment, the memory system (based on the operations being performed with the data) determines whether the data is sequentially accessed data or randomly accessed data. In another embodiment, the host determines whether the data is sequentially accessed data or randomly accessed data. <figref idref="DRAWINGS">FIG. 22</figref> depicts a host <b>1460</b>, in communication with memory system <b>1400</b> (via host interface <b>1420</b> of controller <b>1402</b>), that determines whether the data is sequentially accessed data or randomly accessed data. Host <b>1460</b> includes a Just-In-Time Compiler <b>1462</b> and a memory interface <b>1464</b>. Host <b>1460</b> determines whether target data being accessed by a set of one or more database operations is randomly accessed data or sequentially accessed data. Just-In-Time Compiler <b>1462</b> compiles code to perform the set of one or more database operations on a local compute engine <b>1422</b> located inside memory system <b>1400</b> and embeds in the compiled code an indication of whether the target data is randomly accessed data or sequentially accessed data. Memory interface <b>1464</b> is used to communicate with host interface <b>1420</b> of memory system <b>1400</b>, including transmitting the compiled code with the embedded indication to controller <b>1402</b> and/or compute engine <b>1422</b> (via host interface <b>1420</b>). The target data can be accessed by the compute engine performing the address translation or the compute engine requesting (or working with) the controller to perform the address translation. Thus, the compute engine can perform memory reads (or writes) or the compute engine can work with the controller to perform a memory read (or write).

0107<figref idref="DRAWINGS">FIG. 23</figref> is a flow chart describing one embodiment of a process for reducing the size in memory of L2P tables by having separate tables for random and sequential workload to thereby provide more memory resources to a local compute engine. In one embodiment, the process of <figref idref="DRAWINGS">FIG. 23</figref> is performed by memory system <b>1400</b> of <figref idref="DRAWINGS">FIG. 22</figref> (representing any of the embodiments of <figref idref="DRAWINGS">FIGS. 1-2, 7-8, 10, 12, 13, 15, and 17-19</figref>). In step <b>1502</b>, the controller (or other entity) maintains reduced size L2P tables in volatile working memory by storing fine L2P tables in the working memory for use with randomly accessed data and coarse L2P tables in the working memory for use with sequentially accessed data. In step <b>1504</b>, the controller performs memory operations using the reduced size L2P tables. For example, memory operations (e.g., program, erase, read) for sequentially accessed data are performed using coarse L2P tables and memory operations for randomly accessed data are performed using fine L2P tables. In step <b>1506</b>, the compute engine (inside the controller or outside the controller, or same die as controller or different die than controller) uses the volatile working memory, including extra space due to reduced size L2P tables, to store working data while performing one or more database operations. Steps <b>1502</b>-<b>1506</b> can be performed sequentially or concurrently.

0108<figref idref="DRAWINGS">FIG. 24</figref> is a flow chart describing one embodiment of a process performed by a host when operating a memory system (e.g., such as the memory systems of <figref idref="DRAWINGS">FIGS. 1-2, 7-8, 10, 12, 13, 15, 17-19 and 22</figref>) performing the process of <figref idref="DRAWINGS">FIG. 23</figref>. In step <b>1602</b>, the host determines whether target data being accessed by a set of one or more database operations is randomly accessed data or sequentially accessed data. In step <b>1604</b>, the host (e.g., Just-In-Time Compiler <b>1462</b>) compiles code to perform the set of one or more database operations on a compute engine located inside a memory system. The code is compiled for the specific compute engine chosen to perform the task. In step<b>1606</b>, the host (e.g., Just-In-Time Compiler <b>1462</b>) embeds in the compiled code an indication of whether the target data is randomly accessed data or sequentially accessed data. In step <b>1608</b>, the host (via memory interface <b>1464</b>) transmits the compiled code with the embedded indication to the compute engine (e.g. via host interface <b>1420</b> of controller <b>1402</b> or any of the other controller architectures described above).

0109<figref idref="DRAWINGS">FIG. 25</figref> is a flow chart describing one embodiment of a process for operating a memory using separate logical address to physical address tables for random and sequential workload. In one embodiment, the process of <figref idref="DRAWINGS">FIG. 25</figref> is performed by the memory system (any of the embodiments of <figref idref="DRAWINGS">FIGS. 1-2, 7-8, 10, 12, 13, 15, 17-19 and 22</figref>) in response to step <b>1608</b> of <figref idref="DRAWINGS">FIG. 24</figref>. In one embodiment, the system of <figref idref="DRAWINGS">FIG. 22</figref> (representing any of the embodiments of <figref idref="DRAWINGS">FIGS. 1-2, 7-8, 10, 12, 13, 15, and 17-19</figref>) will perform the process of <figref idref="DRAWINGS">FIG. 25</figref> on the database of <figref idref="DRAWINGS">FIG. 20</figref>.

0110In step <b>1702</b> the memory system receives the compiled code (see step <b>1608</b>) from the host. For example, the compiled code is received at host interface <b>1420</b> and forwarded to another portion of the controller and/or to the compute engine. The compiled code includes instructions for performing one or more database operations on target data in the non-volatile memory. The compiled code includes one or more logical addresses for the target data that need to be translated to physical addresses in the non-volatile memory. The compiled code also includes an indication of whether the target data is sequentially accessed data or randomly accessed data. The indication discussed herein can be a flag or variable that has one value for sequentially accesses data and another value for randomly accessed data. Alternatively, the indication can be the logical address used by the host, where a first set of logical addresses are reserved for and indicate sequential data and a second set of logical addresses are reserved for and indicate random data.

0111In step <b>1704</b>, the memory system determines whether the target data is sequentially accesses data or randomly accessed data based on reading the indication from the compiled code. This can be performed by the compute engine and/or the controller.

0112In another embodiment, the memory system classifies the target data as random or sequential and stores randomly accessed data separately from sequentially accessed data. Therefore, based on the data received or addressed the memory system determines whether the job is for random or sequential data. In another embodiment, the memory system can determine whether the job is for randomly accessed data or sequentially accessed data based on the instructions from the host. For example, if the host is requesting sequential reads then the system assumes the job is for sequentially accessed data and if the host is requesting random reads then the system assumes the job is for randomly accessed data. In another embodiment, the memory system can determine whether the job is for randomly accessed data or sequentially accessed data by utilizing a data structure related to the database. In some embodiments, the instructions from the host are instructions for the local compute engine to perform computations on a set of data. If those instructions are accessing data previously classified as sequentially accessed data then the system assumes the job is for sequentially accessed data and if those are accessing data previously classified as randomly accessed data then the system assumes the job is for randomly accessed data. Alternatively, if those instructions require a scan operation then the system assumes the job is for sequentially accessed data and if those instructions require a seek operation then the systems assumes the job is for randomly accessed data. Similarly, if the instructions cause a sequential writing of data then the operation then the system assumes the job is for sequentially accessed data and if the instructions cause a single write then the operation then the system assumes the job is for randomly accessed data.

0113Looking back at step <b>1704</b>, if the controller and/or compute engine determines that the job is for randomly accessed data, then in step <b>1708</b> the controller and/or compute engine attempts to access the L2P entry for the address received in step <b>1702</b> in the appropriate L2P table in the volatile working memory (e.g., DRAM). Since the job is for randomly accessed data, the system attempts to access the L2P entry for a page address in a fine L2P table for random data in the cache of fine L2P tables, such as random L2P cache <b>1442</b>. Although all L2P tables are stored in the non-volatile memory, only a subset of L2P tables are stored in the relevant cache. Therefore, when the system attempts to access the L2P entry in the random L2P cache it is possible that the L2P entry is in the cache (“hit”) or is not in the cache (“miss”). If the L2P entry for the page address received in step <b>1702</b> is not in the cache so that there is a cache miss (step <b>1710</b>), then in step <b>1712</b> the system fetches the L2P table that includes the page address received in step <b>1702</b> from non-volatile memory (e.g., from area <b>1430</b> of non-volatile memory <b>1404</b>). In step <b>1714</b>, the fetched L2P table is stored in the cache (e.g., in random L2P cache <b>1742</b>). In step <b>1716</b>, the L2P entry for the page address received in step <b>1702</b> that is in the fetched L2P table is used by the controller and/or compute engine to translate the page address received in step <b>1702</b> from a logical address to a physical page address in the non-volatile memory. In step <b>1718</b>, one or more operations are performed on the random data associated with the physical page address from step <b>1716</b> in response to the instructions received from the host in step <b>1702</b>. Step <b>1718</b> includes the compute engine performing the one or more database operations based on the compiled code, including performing one or more memory operations on randomly accessed target data where the target data is accessed using the fine logical address to physical address tables (see step <b>1716</b>) since the indication denotes that the target data is randomly accessed data. Examples of database operations include scanning the data, searching, filtering, sorting, aggregating data, joining data together, as well as other functions on the data. When performing step <b>1718</b>, the compute engine will use the local working memory as a scratch pad or for other use.

0114Note that if in step <b>1710</b> it is determined that there was a cache hit because the relevant L2P entry was resident in the random L2P cache, then the process proceeds to step <b>1716</b> to translate the page address received in step <b>1702</b> from the logical address to the physical page address in the non-volatile memory, as described above.

0115If, in step <b>1704</b>, the controller and/or compute engine determines that the job is for sequentially accessed data, then in step <b>1728</b> the system attempts to access the L2P entry for a block address (or sub-block or word line or other) in a coarse L2P table for sequential data in the cache of coarse L2P tables, such as sequential L2P cache <b>3140</b>. If the L2P entry for the page address received in step <b>1702</b> is not in the cache so that there is a cache miss (step <b>1730</b>), then in step <b>1732</b> the system fetches the L2P table that includes the block address (or sub-block or word line or other) from non-volatile memory (e.g., from area <b>1430</b> of non-volatile memory <b>1404</b>). In step <b>1734</b>, the fetched L2P table is stored in the cache (e.g., in sequential L2P cache <b>1440</b>). In step <b>1736</b>, the L2P entry for the block address received in step <b>1702</b> that is in the fetched L2P table is used to translate the block address received in step <b>1702</b> from a logical block address to a physical block address in the non-volatile memory. If the address receive in step <b>1702</b> is not a block level address, then it is converted into a block address. Note that steps <b>1716</b> and <b>1726</b> comprise performing address translation for a logical address in the compiled code using coarse L2P tables or fine L2P tables based on the embedded indication.

0116In step <b>1738</b>, the compute engine performs the one or more database operations based on the compiled code, including performing one or more memory operations on sequentially accessed target data where the target data was accessed using the coarse logical address to physical address tables (see step <b>1736</b>) since the indication denotes that the target data is sequentially accessed data. When performing step <b>1736</b>, the compute engine will use the local working memory as a scratch pad or for other use.

0117Note that if in step <b>1730</b> it is determined that there was a cache hit because the relevant L2P entry was resident in the sequential L2P cache, then the process proceeds to step <b>1736</b> to translate the page address received in step <b>1702</b> from the logical address to the physical block address (or sub-block or word line or other) in the non-volatile memory, as described above.

0118In the discussion of step <b>1732</b> above, it was assumed that the non-volatile memory stored a full set of fine L2P tables and a full set of coarse L2P tables. In another embodiment, the non-volatile memory stores a full set of fine L2P tables and no (or a subset of) coarse L2P tables. In this latter embodiment, when the system needs to fetch a coarse L2P table in step <b>3332</b> it will instead fetch one or more corresponding fine L2P tables and use the fetched one or more corresponding fine L2P tables to generate the needed coarse L2P table on demand (i.e. on the fly). Thus, in one example implementation, the controller is configured to create the coarse logical address to physical address tables for the working memory on demand from the fine logical address to physical address mapping tables in the non-volatile memory.

0119While the discussion above has focused on a database example, in certain embodiments the principle can be generalized to different host workloads and applications. One embodiment reorganizes the embedded DRAM L2P tables to efficiently support both small block (e.g., 4 KB) writes (e.g., random data operations) and large block writes (100 KB or more) (e.g., sequential data operations). For workloads with a relatively large amount of data requiring large block writes (e.g., sequential data writes), this significantly reduces the amount of DRAM required to hold the L2P cache. One embodiment assumes a workload with these properties: small block (4 KB or so) reads and writes to a relatively small portion of the overall logical address space; and large block (100 KB or more) writes to the remainder of the logical address space, with both large and small random reads. Applications with these properties allow for much more DRAM-efficient mappings for the large block writes: a single mapping entry can represent a much larger region of storage. If the large block writes are performed contiguously to physical storage, the same mapping entry allows small block reads using simple offsets into the large contiguously written block. Examples of applications that exhibit this behavior include: HDFS (Hadoop File System); Databases using Log-Structured Merge (LSM) trees (including, e.g., Cassandra, LevelDB, and RocksDB); Log-structured file systems, such as ZFS and its derivatives; storage software implementations that perform write serialization for optimized RAID and improved flash performance; and scan-heavy analytics applications.

0120<figref idref="DRAWINGS">FIGS. 26-28</figref> depicts L2P tables that can support sequentially accessed data and randomly accessed data, Such tables that supports both small and large block writes can be organized in a variety of ways. These include partitioning for sequentially and randomly written data. <figref idref="DRAWINGS">FIGS. 26-28</figref> provide more description with examples.

0121<figref idref="DRAWINGS">FIG. 26</figref> depicts an embodiment of fine-grained (page based) mapping in a persistent memory that has sixteen different map entries (16 physical pages or 2 blocks in total, s sub-blocks/block, 4 pages/sub-block). The fine-grained (page based) L2P tables of <figref idref="DRAWINGS">FIG. 26</figref> are for randomly accessed data. <figref idref="DRAWINGS">FIG. 26</figref> shows blocks divided into two sub-blocks. Each sub-block has a set pages. Each page represents data stored in memory cells connected to a common word line, Two types of mapping are depicted: direct mapping and hash mapping. With direct mapping, logical page addresses are mapped to physical page addresses in sequence. With hash mapping, a hash table is used to map a logical page address to any of the physical page addresses, in any order.

0122<figref idref="DRAWINGS">FIG. 27</figref> depicts an embodiment of coarse-grained mapping (sub-block based) that has four different map entries. The logical block address can be mapped to physical block address for sequentially accessed data. <figref idref="DRAWINGS">FIG. 27</figref> also teaches to use offsets for the logical block addresses and the physical block addresses to access individual pages so that sequentially accessed data can be accessed randomly. Therefore, the controller and/or the compute engine can be configured to perform a random read of data written as sequentially accessed data using a logical block address and an offset. Two types of mapping are depicted: direct mapping and hash mapping. With direct mapping, logical block addresses are mapped to physical block addresses in sequence. With hash mapping, a hash table is used to map a logical block address to any of the physical block addresses, in any order.

0123<figref idref="DRAWINGS">FIG. 28</figref> depicts another embodiment of coarse-grained mapping (erase block based) that has two different map entries. The logical block address can be mapped to physical block address for sequentially accessed data. <figref idref="DRAWINGS">FIG. 28</figref> also teaches to use sub-block offsets and page offsets for the logical page addresses and the physical page addresses to access individual pages so that sequentially accessed data can be accessed randomly. Two types of mapping are depicted: direct mapping and hash mapping.

0124In one embodiment, fine grained L2P tables (e.g., page address based) are stored in a persistent memory (i.e. NAND flash, ReRAM, PCM, etc.). Logical page addresses can be directly mapped to physical page address, or it can be mapped to certain page addresses through a hash function. In one embodiment, when the table is brought to local working memory (e.g., the L2P cache) for the sequentially written data, the fine grained table is reduced into the coarse grained table which is either of sub-block based or erase block based (or other granularity coarser than page level, as discussed above). For this sequentially written data, logical page addresses can be randomly read through sub-block offset and page offset values in the logical page address with the coarse grained table that stores sub-block or erase block address translation table. As illustrated in <figref idref="DRAWINGS">FIGS. 26-28</figref>, for the case that has 16 physical pages with 2 sub-blocks/block and 4 pages/sub-block, compared to the fine-grained mapping based on page that has 16 different table (also known as a map) entries, coarse-grained mapping based on sub-block or erase block significantly reduce the number of table entries (e.g. 4 for sub-block mapping, 2 for erase-block mapping).

0125An extent table contains an ordered set of entries mapping variable sized, contiguous regions of logical addresses to physical locations in storage. This would allow the mappings for an arbitrary mix of various sized writes to be kept in a single table. Extent tables of this type can be implemented as a pool of fixed-size records managed as a tree (binary, red-black, B+, etc.) or skip list. Such an organization makes it easy to “page” records between DRAM (the local working memory) and suitable for storage if the entire table cannot fit in DRAM. Other ways to support multiple data sizes in an L2P table should be apparent to someone skilled in the art.

0126One embodiment includes an apparatus, comprising a memory system. The memory system includes non-volatile memory, a controller in communication with the non-volatile memory, working memory connected to the controller and configured to store a coarse logical address to physical address table for use with storing sequentially accessed data related to database operations and a fine logical address to physical address table for use with storing randomly accessed data related to database operations, and a compute engine positioned within the memory system and in communication with the controller. The compute engine is configured to: receive code from a host, the code including instructions for performing one or more database operations on target data in the non-volatile memory and an indication of whether the target data is sequentially accessed data or randomly accessed data, perform the one or more database operations based on the code, and the target data being accessed using the coarse logical address to physical address table in response to the indication denoting that the target data is sequentially accessed data, perform the one or more database operations based on the code, and the target data being accessed using the fine logical address to physical address table in response to the indication denoting that the target data is randomly accessed data.

0127In one example implementation, the code received from the host is compiled code that includes the indication of whether the target data is sequentially accessed data or randomly accessed data, the controller includes a host interface, the compute engine is behind the host interface, the host interface receives the compiled code from the host and forwards the compiled code to the compute engine, and the compute engine is configured to use the controller to perform address translation between logical and physical addresses for the target data based on the coarse logical address to physical address tables and the fine logical address to physical address tables in the working memory.

0128In one example implementation, the non-volatile memory includes a memory package that is separate from and connected to the controller and the memory package includes one or more non-volatile memory dies and the compute engine. Additionally, the compute engine is positioned on a first memory die of the one of the non-volatile memory dies; the code received from the host is compiled code that is received by the compute engine on the first memory die; and the compute engine executes the compiled code to access the target data on the first memory die based on the coarse logical address to physical address tables in the working memory for sequentially accessed and the fine logical address to physical address tables in the working memory for data randomly accessed data.

0129One embodiment includes a method, comprising: maintaining, in a memory system, reduced size logical to physical (L2P) tables in volatile working memory by maintaining coarse L2P tables in the working memory for use with sequentially accessed data and maintaining fine L2P tables in the working memory for use with randomly accessed data; receiving, by the memory system from a host, compiled code instructing a compute engine within the memory system to perform a set of one or more database operations on target data in the memory system, wherein the compiled code is embedded with an indication of whether the target data is randomly accessed data or sequentially accessed data; using, by the compute engine inside the memory system, the compiled code to perform the set of one or more database operations on the target data using the working memory, including using space in the working memory made available due to reduced size L2P tables, to store working data for the set of one or more database operations; and performing address translation for a logical address in the compiled code using coarse L2P tables or fine L2P tables based on the embedded indication.

0130One embodiment includes a memory system, comprising: non-volatile memory including a first set of memory cells configured to store branch nodes of a database as randomly accessed data and a second set of memory cells configured to store leaf nodes of the database as sequentially accessed data; working memory; and a controller in communication with the non-volatile memory and the working memory. The controller includes a host interface. The controller is configured to: store a first logical address to physical address table in the working memory for use with storing randomly accessed data in the first set of memory cells and a second logical address to physical address table in the working memory for use with storing sequentially accessed data in the second set of memory cells, the first logical address to physical address table providing address translation at a lower level of granularity than the second logical address to physical address table; receive a request from a host via the host interface, the request including an indication of whether target data of the database to be accessed by the request is sequentially accessed data or randomly accessed data; access the target data from the first set of memory cells using the first logical address to physical address table in response to the request including an indication that the target data is randomly accessed data, and access the target data from the second set of memory cells using the second logical address to physical address table in response to the request including an indication that the target data is sequentially accessed data; and a compute engine that is behind the host interface and is in communication with the controller and the working memory, the compute engine being configured to perform data manipulation operations on sequentially accessed data stored in the second set of memory cells.

0131For purposes of this document, reference in the specification to “an embodiment,” “one embodiment,” “some embodiments,” or “another embodiment” may be used to describe different embodiments or the same embodiment.

0132For purposes of this document, a connection may be a direct connection or an indirect connection (e.g., via one or more others parts). In some cases, when an element is referred to as being connected or coupled to another element, the element may be directly connected to the other element or indirectly connected to the other element via intervening elements. When an element is referred to as being directly connected to another element, then there are no intervening elements between the element and the other element. Two devices are “in communication” if they are directly or indirectly connected so that they can communicate electronic signals between them.

0133For purposes of this document, the term “based on” may be read as “based at least in part on.”

0134For purposes of this document, without additional context, use of numerical terms such as a “first” object, a “second” object, and a “third” object may not imply an ordering of objects, but may instead be used for identification purposes to identify different objects.

0135For purposes of this document, the term “set” of objects may refer to a “set” of one or more of the objects.

0136The foregoing detailed description has been presented for purposes of illustration and description. It is not intended to be exhaustive or to limit to the precise form disclosed. Many modifications and variations are possible in light of the above teaching. The described embodiments were chosen in order to best explain the principles of the proposed technology and its practical application, to thereby enable others skilled in the art to best utilize it in various embodiments and with various modifications as are suited to the particular use contemplated. It is intended that the scope be defined by the claims appended hereto.