Patent Description:
This application relates generally to a method and system for managing the storage of data in a data storage device.

Non-volatile memory systems, such as flash memory, are used in digital computing systems as a means to store data and have been widely adopted for use in consumer products. Flash memory may be found in different forms, for example in the form of a portable memory card that can be carried between host devices or as a solid state disk (SSD) embedded in a host device. These memory systems typically work with data units called "pages" that can be written, and groups of pages called "blocks" that can be read and erased, by a storage manager often residing in the memory system.

Performance of a non-volatile memory device may be limited by the amount of computational power included in the memory device. A limitation on the amount of computational power in a single device may be the amount of heat generated by the device. Some approaches to improving memory device performance may include raising the clock frequency, using a more powerful processor or combining several processors in a single memory device. Problems with these approaches may include excessive power requirements, heat generation and cost increases. Accordingly, an alternative way of improving the performance of a non-volatile memory device is needed. <CIT> is concerned with task offloading to a peripheral device. <CIT> is concerned with copying protected data from one secured storage device to another via a third party. <CIT> is concerned with multi-tier address mapping in flash memory.

In order to address the problems and challenges noted above, a system and method for implementing parallel processing among more than one memory device, such as between an embedded and a removable memory device, is disclosed.

Further preferred embodiments are defined by the dependent claims.

As shown in <FIG>, in some systems a host may be connected with more than one memory device. For example, in a system where a host <NUM> is a mobile phone, the host <NUM> may include embedded flash memory <NUM> and also be connected to a removable flash memory device <NUM> such as a SD card or other available removable flash storage device form factor. Typically, a host <NUM> is working with one memory device <NUM>, <NUM> while the other one is idle. In order to improve the performance of one of these memory devices, a method and system for utilizing the computation power of the idle memory device for the benefit of the active memory device is described below.

In order to take advantage of an idle memory device's processing power, the active memory device (in this example the embedded flash memory <NUM>) needs to communicate information and instructions to the idle memory device (in this example the removable flash memory device <NUM>). In <FIG>, a physical communication path <NUM> is illustrated where data flows to and from the embedded flash memory <NUM> to the removable flash memory device <NUM> via the host <NUM> as an intermediary/conduit. A logical communication path <NUM> is also disclosed illustrating the data path that is set up between the embedded and removable memory devices <NUM>, <NUM>. Because the memory devices <NUM>, <NUM> are only using the host as a conduit or hub, and because other topologies may include a ring topology or other arrangement that permits direct physical communication between the memory devices (i.e. without a need for the host <NUM> to establish the connection or act as an intermediary) the logical communication path <NUM> may also represent the physical data path in other implementations.

The host system <NUM> is configured to store data into, and retrieve data from, storage devices <NUM>, <NUM>. The host system <NUM> may be any of a number of fixed or portable data handling devices, such as a personal computer, a mobile telephone, a personal digital assistant (PDA), or the like. The host system <NUM> includes the embedded memory <NUM>, which may be a discrete integrated circuit or die, and communicates with the removable storage device <NUM>, such as a solid state disk (SSD) or flash memory card that is removably connected to the host system <NUM> through a mechanical and electrical connector. The host system <NUM> may include a processor <NUM>, a user interface <NUM>, and one or more removable device interfaces <NUM>. An embedded memory interface may also be incorporated in the host along with the embedded memory <NUM>.

Referring to <FIG>, an example storage device <NUM> suitable for use for each of the embedded or removable storage devices <NUM>, <NUM> is illustrated. The configuration of the embedded and removable storage devices may be the same or different, and the arrangement of <FIG> is simply provided as one example of a suitable arrangement that each of these memories <NUM>, <NUM> may take. The storage device <NUM> contains a controller <NUM> and a memory <NUM>. The controller <NUM> includes a processor <NUM> and a controller memory <NUM>. The processor <NUM> may comprise a microprocessor, a microcontroller, an application specific integrated circuit (ASIC), a field programmable gate array, a logical digital circuit, or other now known or later developed logical processing capability. The controller memory <NUM> may include volatile memory such as random access memory (RAM) <NUM> and/or non-volatile memory, processor executable instructions <NUM> for handling memory management, and logical to physical mapping tables <NUM>.

The storage device <NUM> may include functions for memory management. In operation, the processor <NUM> may execute memory management instructions (which may be resident in instruction database <NUM>) for operation of the memory management functions. The memory management functions may control the assignment of the one or more portions of the memory within storage device <NUM>.

The storage device <NUM> contains non-volatile memory <NUM> that includes cells that may be arranged as a short term storage array (referred to herein as cache storage) <NUM> and a long term storage array <NUM>. The cache storage <NUM> and long term storage <NUM> may be made up of the same type of flash memory cell or different types of flash memory cells. For example, the cache storage <NUM> may be configured in a single level cell (SLC) type of flash configuration having a one bit per cell capacity while the long term storage <NUM> may consist of a multi-level cell (MLC) type flash memory configuration having two or more bit per cell capacity to take advantage of the higher write speed of SLC flash and the higher density of MLC flash. Different combinations of flash memory types are also contemplated for the cache storage <NUM> and long term storage <NUM>.

Referring to <FIG>, the flash memory <NUM> in each of the embedded and removable memory devices <NUM>, <NUM> may be arranged in blocks of memory cells. In the example of <FIG>, four planes or sub-arrays <NUM>, <NUM>, <NUM> and <NUM> memory cells are shown that may be on a single integrated memory cell chip, on two chips (two of the planes on each chip) or on four separate chips. The specific arrangement is not important to the discussion below and other numbers of planes may exist in a system. The planes are individually divided into blocks of memory cells shown in <FIG> by rectangles, such as blocks <NUM>, <NUM>, <NUM> and <NUM>, located in respective planes <NUM>, <NUM>, <NUM> and <NUM>. There may be dozens or hundreds of blocks in each plane. Blocks may be logically linked together to form a metablock that may be erased as a single unit. For example, blocks <NUM>, <NUM>, <NUM> and <NUM> may form a first metablock <NUM>. The blocks used to form a metablock need not be restricted to the same relative locations within their respective planes, as is shown in the second metablock <NUM> made up of blocks <NUM>, <NUM>, <NUM> and <NUM>.

The individual blocks are in turn divided for operational purposes into pages of memory cells, as illustrated in <FIG>. The memory cells of each of blocks <NUM>, <NUM>, <NUM> and <NUM>, for example, are each divided into eight pages P0-P7. Alternately, there may be <NUM>, <NUM> or more pages of memory cells within each block. A page is the unit of data programming and reading within a block, containing the minimum amount of data that are programmed or read at one time. A metapage <NUM> is illustrated in <FIG> as formed of one physical page for each of the four blocks <NUM>, <NUM>, <NUM> and <NUM>. The metapage <NUM> includes the page P2 in each of the four blocks but the pages of a metapage need not necessarily have the same relative position within each of the blocks. A metapage is the maximum unit of programming. The blocks disclosed in <FIG> are referred to herein as physical blocks because they relate to groups of physical memory cells as discussed above. As used herein, a logical block is a virtual unit of address space defined to have the same size as a physical block. Each logical block includes a range of logical block addresses (LBAs) that are associated with data received from a host <NUM>. The LBAs are then mapped to one or more physical blocks in the storage device <NUM> where the data is physically stored.

Referring now to <FIG>, a method of utilizing the processing power of a second memory device to enhance that of a first memory in communication with a common host is described. Upon initialization, each of the embedded memory <NUM> and removable memory <NUM> inform the host <NUM> of their abilities to share processing with a sharing protocol common to both. In one implementation, the host <NUM> is configured to recognize the sharing protocol capability information received from each memory <NUM>, <NUM> and to then pass on subsequent information from one memory to the other. This initialization may be triggered as part of a power-up sequence when the embedded and removable memories <NUM>, <NUM> are initialized, or may be triggered by the connection or disconnection of a memory device from the host. The initialization information may include device manufacturer information, device and/or software version, a sharing standard identifier, or other information that allows the memory devices and/or host to recognize the functional capabilities described herein. The host and memory devices may each be configured with a protocol, such as the universal flash storage (UFS) protocol published by JEDEC of Arlington, VA, that has been modified to recognize and act on the sharing capabilities of memory devices.

As shown in in <FIG>, assuming each memory <NUM>, <NUM> has the capability to share resources with another memory, the memories exchange tokens <NUM>, <NUM> at initialization with each the other. The token <NUM> generated by the embedded memory <NUM> being transmitted and stored on the removable memory <NUM> and the token <NUM> generated at the removable memory <NUM> being transmitted to and stored on the embedded memory <NUM>. The exchange is shown along the logical path <NUM> rather than the physical path <NUM> for simplicity of illustration. The tokens <NUM>, <NUM> contain information regarding the memory in which they were generated, such as one or more of manufacturer information, version of the sharing protocol or other information indicative of the amount and type of functions it can share with another memory device. Additionally, the tokens contain information on a current state of the memory in which the token was generated. For example, the token may contain back end tables, such as the current logical-to-physical mapping tables, or other tables, for the memory. If other capabilities are supported, such as the ability for one memory to mirror or act as the RAM for the other, then the contents of the RAM memory may also be sent. The capabilities of the memories <NUM>, <NUM> for resource sharing is processor sharing to assist with logical-to-physical mapping such that the embedded memory may use the processing power of the removable memory to calculate where data received at the embedded memory should be physically mapped into the embedded memory.

Referring now to <FIG>, after the exchange of tokens <NUM>, <NUM> and synchronization of tables or other data that was carried in the tokens, data write commands are received from the host <NUM>. Assuming that a UFS protocol is implemented, the host <NUM> may implement a write operation by sending the embedded memory <NUM> a write command, for example in the form of a command descriptor block (CDB) containing the logical block address and size of the data to be written. The host may send a first write command <NUM> followed by a subsequent write command <NUM>, to the embedded memory <NUM>. The embedded memory needs to determine where to physically map the data for each command that the host identified by logical address and size. The calculations necessary for determining how to map the logical addresses to physical locations takes a certain amount of processing time that can lead to delays in actually accepting and writing the data associated with the write commands. Because the write commands may come more quickly than the embedded memory <NUM> can immediately handle, the commands are placed in a queue <NUM> by the embedded memory <NUM>.

Referring now to <FIG>, the embedded memory <NUM> can utilize the removable memory <NUM> to calculate the logical-to-physical mapping of the data to be received in the second command (Write Op N) by passing a second token <NUM> to the removable memory <NUM> with the necessary information on the state of the memory in the embedded memory and the LBA range that is to be written. In one embodiment, the second token <NUM> consists of a collection of all write commands (e.g. CDBs) that have been received by the embedded memory, with the embedded memory associating flags with those write commands that the embedded device would like the removable memory to process. In other embodiments, tokens <NUM> containing individual write commands, along with a flag indicating whether or not the write command is to be processed by the removable memory device, may be sent by the embedded device. Although the embedded device may only want the help of the removable device to process specific write commands, in one embodiment all of the write commands are sent to the removable memory from the embedded memory, with appropriate indication of which ones to act on, so that the removable memory has the complete and up-to-date picture of the state and status of the various tables in the embedded memory.

While the embedded memory <NUM> is handling the first write command and writing the data associated with the first write command, the processor of the removable memory <NUM> may be calculating/mapping the locations for the data the host will be sending with the next command in the queue. As shown in <FIG>, the removable memory <NUM> returns a result token <NUM> to the embedded memory <NUM> containing the mapping information that the embedded memory can use for the requested write command. As shown in <FIG>, the embedded memory can then receive the data <NUM> for the command that the removable memory already calculated the physical locations for. This process may be repeated for each write command in the queue <NUM> so that the embedded memory <NUM> may concentrate on writing the data while the removable memory <NUM> calculates the physical locations for the incoming data. In this manner, the embedded memory may improve its performance and avoid timing out or delaying the data from the host <NUM>.

Other forms of performance enhancement, by exporting/sharing processing or memory functions to the removable memory are contemplated. As mentioned previously, the embedded memory <NUM> may require assistance with expanding its RAM capability, in whole or in part, by utilizing the RAM of the idle removable memory <NUM> during write operations directed by the host to the embedded memory. In this scenario, the RAM functions of the embedded memory may be outsourced to the removable memory via token communications and sharing of RAM status information over the logical path <NUM> between the memories <NUM>, <NUM>. It is contemplated that multiple functions, such as the logical to physical mapping and RAM sharing, may be concurrently or simultaneously utilized by the embedded memory and removable memory in other embodiments.

<FIG> illustrates a flow chart of the general steps that may be used in the resource sharing and parallel processing memories of <FIG>, such as the logical-to-physical mapping example provided in <FIG>. Upon initialization and recognition of the memories by the host, information on the processing and resource sharing capabilities or protocols are provided to the host or directly to the other memory (at <NUM>). Each of the memories, embedded or removable, are thus informed of the availability or lack thereof of resource and processing sharing abilities of the other memories. Each memory transmits a token to the other compatible memory identifying its current state (at <NUM>). When additional processing or other resource is desired by a memory, it sends a token to one or more other memories with information necessary for the receiving memory to carry out the request (at <NUM>). The requesting memory then receives the requested result and applies that result to its activities in handling the host requirements (e.g. the write command or other host command for which assistance was requested) (at steps <NUM>, <NUM>).

In order to prepare the embedded and removable memories for sharing the various functions, the status for each device may be exchanged at initialization for all the possible functions that could be shared, regardless of whether the devices end up sharing those particular functions. Thus the one or more tokens generated by each memory <NUM>, <NUM> may include significantly more information than is utilized for the particular session. Additionally, it is contemplated that, even for memory devices and hosts that are compatible with some form of processor or other resource sharing as described herein, that there may be different versions of the sharing protocol contained in each device, such that the system of host and connected memories will default to the lowest common version of the sharing protocol if different versions are present. For example, if a version <NUM> and <NUM> exist, where <NUM> is an earlier and less capable version than version <NUM>, version <NUM> may be utilized by a device with version <NUM> capability if one of the other devices is only capable of version <NUM> functionality for the sharing protocol and functions described herein.

In other embodiments, the memory devices that share processing or other features may be two removable memory devices in communication with a common host rather than an embedded and a removable memory. The second, or idle, memory need not even be a non-volatile memory at all in other embodiments. The idle device may instead be any of a number of peripheral devices that include the ability to process commands and possess other types of memory, such as RAM, that may be shared. In one alternative embodiment, the second memory may be the host itself, where the embedded memory requests assistance in processing or memory sharing from the host processor.

Referring to <FIG>, an embodiment of a method of memory devices engaging in RAM sharing is illustrated. The memory device needing to use RAM of another memory device is referred to in <FIG> as the source memory and the memory device providing RAM services to the source memory is referred to as the destination memory. After the memory devices (embedded and peripheral to the host or both peripheral) have identified their sharing capabilities to the host or other memory device via an exchange of tokens, such as described with respect to <FIG> (at <NUM> and <NUM>), a memory device may request RAM sharing assistance from the other memory device. Although the data that the source memory wishes to have stored in RAM at the destination memory need not be protected, the embodiment of <FIG> shows one encryption process that may be utilized to protect access to and the integrity of the shared data from the source memory.

The controller or processor of the source memory may generate an encryption key internally (at <NUM>) using any of a number of secret keys or certificates and any of a number of encryption techniques. Suitable encryption algorithms include, but are not limited to, CMAC (cipher-based MAC or message authentication code) or hash-based encryption algorithms. Using the generated encryption key, the processor of the source memory may encrypt and/or sign the data that the source memory wishes to store in the RAM of the destination memory (at <NUM>). At this stage, the source memory may transmit a token to the destination memory, either via the host, or over a direct connection as noted below, containing the encrypted data and a RAM sharing operation code to alert the destination memory of what it is being asked to do (at <NUM>). When the source memory wants to retrieve some or all of the data is has asked the destination memory to store in RAM, a subsequent token with an operation code the destination memory will recognize as an instruction to send back the encrypted data is sent from the source to the destination memory (at <NUM>). The destination memory will retrieve the encrypted data from its RAM and send it back to the source memory in another token (at <NUM>). Finally, the source memory may decrypt and authenticate the data from the received token (at <NUM>). In instances where the digital signature fails (cannot be verified), the source memory will not accept the data and may transmit a signal to the host indicating that the data is corrupted.

Although described in the context of a RAM sharing feature, this or other techniques for encrypting and/or signing of data or other information may be used in other parallel computing or resource sharing operations engaged in by the memory devices. In other embodiments, the parallel processing or resource sharing may take place between more than two memory devices, such that a first memory device could ask for and receive processing or resource sharing services from more than one other memory device concurrently.

Referring now to <FIG>, one example of a logical structure of a token <NUM> usable by a memory device, whether embedded or peripheral to a host, is shown. The token <NUM> may include a transaction or token ID <NUM> that identifies the particular transaction and/or token and transaction that the token <NUM> represents. An operation code (op code) <NUM> identifies the purpose of the token <NUM>, for example op codes for initialization (e.g. identifying to the other memory or host upon power up the capabilities available from the memory device that generated the token), requesting processor assistance, RAM sharing, and other separate processes or stages within a particular process may be placed in this field of the token <NUM>. The available op codes would include different numbers or other identifiers for all of the processing types available. A set of op codes for RAM sharing may include a code for requesting the RAM sharing feature, a code for later requesting return of data that was previously sent with the RAM sharing request token, and so on. The token <NUM> may also include a field for the data <NUM> that is sent back and forth between memories. The data <NUM> may be contents of RAM being shared, a list of tables or other information relevant to a particular op code provided in the token <NUM>. A token size <NUM> denotes the amount of data that is in the token <NUM> so that the controller of the memory or processor of the host is aware of how much to look for in the token. Finally, cyclic redundancy code (CRC) information <NUM> may be included to help correct, or at least identify, corruption of data being transmitted between source and destination. In one embodiment, there may also be tokens sent or exchanged in acknowledgement of receipt or to confirm completion of a process. In other embodiments no acknowledgement tokens may be used. The token ID <NUM> may serve as a transaction identifier so that the memory devices may be certain which operation or sequence of tokens applies to particular data or other tokens.

The memory device requesting a processing resource from another memory, and the memory from which the processing resource is requested, may each generate tokens <NUM> having this general format.

Also, as noted previously, the connection topology may be a hub-type connection where the different memories need to separately communicate their sharing abilities with the host and the host, as a hub, then mediates communications between the two memory devices. In another implementation, a ring-type topology may be utilized where the memory devices are associated with a common host but are nodes capable of direct physical communication rather than only through the host. In yet other embodiments, a manufacturer of embedded memory may enhance the attractiveness of use of its removable memory devices for hosts having the manufacturer's embedded memory by configuring both the manufacturer's embedded and removable memories with the ability to recognize and utilize the sharing protocols and capabilities described herein. Similarly, the potential advantages of enhanced processing between removable devices having similar sharing capabilities are apparent. In other implementations, it is contemplated that the sharing capability, for example parallel processing, may be further spread over multiple additional currently idle memories attached to a common host where a first of the memories may call upon more than one other idle memory to further share processing requests for the first memory.

An advantage of the disclosed method and system is that compatible memories may communicate at power up, or during some other initialization procedure, to exchange tokens to allow the active memory to utilize a processing resource of the idle memory, for example RAM storage or processing power of the idle memory. In contrast to typical situations where multiple separate memory devices are connected with a host and the processing power of only one active memory device at a time is available, the processing power of multiple memory devices may be used to increase the performance of the active memory device. The use of separate memory devices associated with the same host allows not only for the improvement of performance in terms of speed, but may reduce the concentration of heat that might otherwise be generated if processing were enhanced in a single memory device attached to a host.

Claim 1:
A memory device (<NUM>) configured to be in communication with a host (<NUM>), the memory device (<NUM>) comprising:
a non-volatile memory (<NUM>); and
a processor (<NUM>) in communication with the non-volatile memory (<NUM>), the processor (<NUM>) configured to:
upon an initialization trigger from the host (<NUM>), transmit a token (<NUM>, <NUM>) generated at the memory device (<NUM>) to a separate memory device in communication with the host (<NUM>), the separate memory device comprising a second processor, the token (<NUM>, <NUM>) relating to a state of the memory device (<NUM>) and functions the memory device (<NUM>) has available to share with the separate memory device;
in response to receiving a plurality of host commands directed to writing data to the memory device (<NUM>), transmit a second token (<NUM>) to the separate memory device requesting logical-to-physical mapping processing from the second processor of the separate memory device for determining physical locations in the non-volatile memory (<NUM>) of the memory device (<NUM>) to which data associated with one of the plurality of host commands is to be mapped;
process another of the host commands while waiting for a response from the separate memory device; and
apply a result of the logical-to-physical mapping processing received from the separate memory device to the one host command.