Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
DETAILED ACTION
Specification
The title of the invention is not descriptive. A new title is required that is clearly indicative of the invention to which the claims are directed. The following title is suggested: DETERMINING DATA HOTNESS BASED ON PAGE TABLE ENTRY REGION COUNT AND VALID DATA COUNT.
Claim Rejections - 35 USC § 101
35 U.S.C. 101 reads as follows:
Whoever invents or discovers any new and useful process, machine, manufacture, or composition of matter, or any new and useful improvement thereof, may obtain a patent therefor, subject to the conditions and requirements of this title.
Claims 1-20 are rejected under 35 U.S.C. 101 because the claimed invention is directed to an abstract idea without significantly more. The claims are directed to one or more method, memory controller and meme system for determining data hotness based on a page table entry region count and a valid data count.
The claimed invention, when taken as a whole, is directed to the abstract idea of collecting and analyzing data to classify blocks of memory as hot/cold in order to select blocks for garbage collection. Specifically the claims recite: Acquiring counts, calculating ratios and heuristic parameters and using those abstract results to make decisions about which blocks to garbage collect. These are mathematical calculations and resource management rules implemented as block selection policies which fall within the categories of abstract ideas identified as mathematical concepts and certain methods of organizing human activity in the form of resource allocation, which is an abstract idea under prong I step 2a .
The claims do not recite any specific improvements to the functioning of the computer or memory hardware itself. The memory device, memory array, cache, processor, and controller are described in generic terms and operate in their ordinary capacities to store retrieve and erase data. The use of particular ratios and thresholds in the controller’s decision logic for garbage collection are done as high level decision logic expressed as mathematical relationships between conventional parameters and does not integrate the abstract idea into a practical application in the manner of an improvement to computer functionality. As such the claim(s) do not include additional elements that are sufficient to amount to significantly more than the judicial exception because they merely implement the abstract idea using generic computer components (as evidenced by Zhang/Palmer) and these are well-understood, routine, conventional computer functions as recognized by the court decisions listed in MPEP § 2106.05(d). As such, the claims do not amount to significantly more than the abstract idea.
The additional elements beyond the abstract idea in claims 16,17-20 recite a generic processor, memory device, cache, and memory controller that execute the steps of the abstract idea (acquiring counts of valid data, erase program counts, computing ratios, comparing against thresholds and selecting blocks for garbage collection). The generic processor, memory device, cache, and memory controller are recited at a high level of generality and perform nothing more than generic computer functions of sending and receiving information and processing data according to conditional logic. Such generic computer implementation does not impose a meaningful limit on practicing the abstract idea & implementing an abstract idea on a generic computer does not integrate the abstract idea into a practical application.
In conclusion, the claims do not recite a transformation of an article, nor do they add any meaningful limitations beyond generally linking the abstract idea to a technological environment of a generic memory system/device/controller. Thus the abstract idea is not integrated into a practical application and the claims do not include additional elements individually or in combination that amount to significantly more than the abstract idea itself.
Claim Rejections - 35 USC § 103
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
The factual inquiries set forth in Graham v. John Deere Co., 383 U.S. 1, 148 USPQ 459 (1966), that are applied for establishing a background for determining obviousness under 35 U.S.C. 103(a) are summarized as follows:
1. Determining the scope and contents of the prior art.
2. Ascertaining the differences between the prior art and the claims at issue.
3. Resolving the level of ordinary skill in the pertinent art.
4. Considering objective evidence present in the application indicating obviousness or nonobviousness.
Claims 1-2, 9-20 are rejected under 35 U.S.C. 103 as being unpatentable over Zhang (US PGPUB # 20160179386) in view of Palmer (US PGPUB # 20220197790). With respect to independent claims 1, 16, 17 Zhang/Palmer discloses: A method of determining data hotness [Data being stored in a block of flash memory system may be characterized as being frequently modified or infrequently modified (hot/cold) based on a heuristic. When performing garbage collection, if the data from hot blocks is consolidated and data from cold blocks is separately consolidated by writing the data to different free blocks - Zhang abstract], comprising:
acquiring a page table entry region count corresponding to a virtual block [Zhang does not explicitly teach a page table entry region count corresponding to a virtual block, although Zhang teaches a functional equivalent as: For each of the blocks in which valid data is stored: maintaining a garbage collection parameter comprising at least an age parameter and a staleness parameter, where the age parameter is representative of a number of times any block of the usable memory has been erased since a last time the block has been erased, and a staleness parameter may represent a number of stale (invalid) pages of the block – Zhang 0020, 0022] and a valid data count of the virtual block [For each of the blocks in which valid data is stored: maintaining a garbage collection parameter comprising at least an age parameter and a staleness parameter, where the age parameter is representative of a number of times any block of the usable memory has been erased since a last time the block has been erased, and a staleness parameter may represent a number of stale (invalid) pages of the block – Zhang 0022], wherein the virtual block includes at least one memory block in a memory device [virtual block according to this definition appears coextensive in scope with logical blocks of Zhang – Zhang 0010, 0020 ] [logical address space may be divided into any quantity of portions (reads on region), each corresponding to a different subset of a logical-to-physical (L2P) table, and the bitmap (reads page table entry) may include any quantity of corresponding bits (reads on region count). To perform garbage collection on the block, the bitmap may be used to identify one or more subsets of the L2P table to evaluate to determine whether different sets of data within the block are valid or invalid – Palmer abstract, fig 2, 5; virtual blocks disclosed by Palmer in 0032];
determining a data distribution state of data stored in the virtual block based on the page table entry region count and the valid data count [determining valid/invalid data in subset of logical address space - Zhang claim 10, paragraph 0020, 0022 & Palmer 0039]; and
determining data hotness of the data stored in the virtual block based on the data distribution state [determining the hot or cold status of the block being garbage collected using by computing a heuristic value, and when the block is garbage collected, all valid data of the block is designated to be either hot data or cold data based on the heuristic value the block - Zhang claim 10].
Zhang does not explicitly disclose a page table entry region count corresponding to a virtual block, although Zhang teaches a functional equivalent as articulated above. Nevertheless in the same field of endeavor Palmer teaches means for valid data identification for garbage collection (Palmer abstract) wherein a logical address space may be divided into any quantity of portions (reads on region), each corresponding to a different subset of a logical-to-physical (L2P) table, and the bitmap (reads page table entry) may include any quantity of corresponding bits (reads on region count). To perform garbage collection on the block, the bitmap may be used to identify one or more subsets of the L2P table to evaluate to determine whether different sets of data within the block are valid or invalid – Palmer abstract, fig 2, 5; virtual blocks disclosed by Palmer in 0032
It would have been obvious to one of ordinary skill in the art before the effective filing date of the invention to use a page table entry region count corresponding to a virtual block in the invention of Zhang as taught by Palmer because it would be advantageous for increasing an efficiency associated with garbage collection operations performed by the memory system (e.g., by reducing one or more related latencies (Palmer 0012).
With respect to independent claims 16, 17 since the instant claims are substantially similar in scope relative to claim 1, they are rejected according to substantially the same rationale as applied to claim 1, with minor differences considered:
A memory controller, comprising: a cache and a processor communicatively connected with each other, the cache having computer instructions stored therein [Zhang 0059, 0072; Palmer 0018].
With respect to dependent claim 2 Zhang/Palmer discloses wherein the acquiring the page table entry region count corresponding to the virtual block includes: acquiring a page table entry bitmap corresponding to the virtual block, the page table entry bitmap representing a distribution state, in various page table entry regions, of logical addresses of the data stored in the virtual block; and determining the page table entry region count based on the distribution state, in various page table entry regions, of the logical addresses of the data stored in the virtual block [any subset of the logical address space may be evaluated according to its bitmap for valid and invalid data - Zhang claim 10, paragraph 0020, 0022 & Palmer fig 2, paragraph 0039].
With respect to dependent claim 9 Zhang/Palmer discloses wherein the determining the data distribution state of data stored in the virtual block based on the page table entry region count and the valid data count includes determining a second ratio between the page table entry region count and the valid data count, and using the second ratio to represent the data distribution state [bits per logical address region, a count of set bits is a number of regions where block or virtual block has data – Palmer fig 2; valid page counts maintained by staleness parameter and ratios of valid/invalid pages used for garbage collection parameters - Zhang table 2, claim 1-5, using a ratio between the page table entry region count and a valid data count to represent a data distribution state is consistent with teachings of Zhang table 2, claim 1-5 in view of Palmer fig 2].
With respect to dependent claim 10 Zhang/Palmer discloses wherein the larger the second ratio, the more discrete the data distribution state [more bits set for a given valid data count = valid data being spread across more logical address regions - Zhang table 2, claim 1-5 in view of Palmer fig 2].
With respect to dependent claim 11, 18 Zhang/Palmer discloses determining, based on data hotness of data stored in each virtual block and a valid data count of each virtual block, a first target virtual block for garbage collection; and performing first garbage collection on the first target virtual block [Zhang abstract, fig 4-5; Palmer fig 3, 5].
With respect to dependent claim 12, 19 Zhang/Palmer discloses wherein the determining, based on the data hotness of the data stored in each virtual block and the valid data count of each virtual block, the first target virtual block for garbage collection including: acquiring a data storage volume of each virtual block; determining a valid data proportion of each virtual block based on the valid data count and the data storage volume corresponding to each virtual block; determining a collection parameter value corresponding to each virtual block according to the valid data proportion and the data hotness; and determining the first target virtual block for garbage collection from a plurality of virtual blocks based on the collection parameter value [Zhang abstract, fig 4-5 in view of Palmer fig 3, 5].
With respect to dependent claim 13 Zhang/Palmer wherein the larger the collection parameter value, the larger a collection value of the first target virtual block [higher garbage collection parameter = higher garbage collection priority/value - Zhang abstract, fig 4-5].
With respect to dependent claim 14, 20 Zhang/Palmer discloses detecting whether an erase/program count difference between various virtual blocks is greater than a preset threshold [block ages may be compared to one another as they are numerical values that lend themselves to comparison, the claimed preset threshold may be any number, zero to infinity – Zhang abstract, 0022]; when the erase/program count difference is greater than the preset threshold, determining cold data based on data hotness of data stored in a virtual block having a smaller erase/program count in two virtual blocks compared with each other; determining a second target virtual block having a larger erase/program count in the two virtual blocks compared with each other, wherein an erase/program count of the second target virtual block is greater than an erase/program count of the virtual block where the cold data is located; and migrating the cold data into the second target virtual block, and releasing a memory block in the virtual block that stores cold data [For each of the blocks in which valid data is stored: maintaining a garbage collection parameter comprising at least an age parameter and a staleness parameter, where the age parameter is representative of a number of times any block of the usable memory has been erased since a last time the block has been erased, and a staleness parameter may represent a number of stale (invalid) pages of the block…. an aspect of wear leveling where free blocks are selected such that a cumulative erasure count of each block in the entire flash memory is approximately equal. Alternatively the wear leveling may pertain to a specific selected portion of the flash memory - Zhang 0014, 0022 in view of 0024, 0071, 0075, teaching multiple streams of data grouping cold data together].
With respect to dependent claim 15 Zhang/Palmer discloses determining a third target virtual block having a minimum valid data count; and performing second garbage collection on the third target virtual block [greedy garbage collection - Zhang abstract, 0017].
Claims 3-8 are rejected under 35 U.S.C. 103 as being unpatentable over Zhang/Palmer further in view of Kanno (US Patent # 9946643).
With respect to dependent claim 3 Zhang/Palmer does not explicitly disclose all limitations of the instant claim. Nevertheless in the same field of endeavor Kanno teaches controlling non-volatile memory and managing a garbage collection count for each of blocks containing data written by a host, the garbage collection count indicating the number of times the data in said each of the blocks has been copied by a garbage collection operation of the nonvolatile memory wherein an elapsed time interval between updates may be maintained – Kanno col 6 lines 60-67, col 20 lines 20-29. As such, Zhang/Palmer/Kanno teaches wherein the determining the data hotness of the data stored in the virtual block based on the data distribution state includes: acquiring an update time interval [update time interval not explicitly disclosed by Zhang/Palmer, nevertheless in the same field of endeavor Kanno teaches garbage collection in a memory system wherein an elapsed time interval between updates may be maintained – Kanno col 6 lines 60-67, col 20 lines 20-29] of a block mapping relationship [temporal characteristics drive garbage collection operations - Zhang 0060-0063] and a relative erase/program count corresponding to the virtual block [Zhang abstract, fig 9]; determining an erase/program state corresponding to the virtual block based on the update time interval and the relative erase/program count [the age parameter is representative of a number of times any block of the usable memory has been erased since a last time the block has been erased - Zhang 0022; blocks have associated p/e count - Kanno col 4 lines 6-7]; and determining the data hotness of the data stored in the virtual block based on the erase/program state and the data distribution state [Zhang 0082-0083, claim 10]. It would have been obvious to one of ordinary skill in the art before the effective filing date of the invention to track an update time interval in the invention of Zhang/Palmer/Kanno because it would be advantageous for improving the garbage collection operation in terms of reducing wear and write amplification in the memory system (Kanno col 5 line 65 – col 6 line 4, col 12 lines 32-40).
With respect to dependent claim 4 Zhang/Palmer/Kanno discloses wherein the acquiring the update time interval of the block mapping relationship corresponding to the virtual block includes: acquiring latest update time of the block mapping relationship of the virtual block; and determining a time difference between the latest update time and current time, and determining the time difference as the update time interval [an elapsed time interval between updates may be maintained – Kanno col 6 lines 60-67, col 20 lines 20-29].
With respect to dependent claim 5 Zhang/Palmer/Kanno discloses wherein the acquiring the relative erase/program count corresponding to the virtual block includes: acquiring a first erase/program count corresponding to the virtual block and a second erase/program count of another virtual block currently in an unused state; and determining the relative erase/program count based on a difference between the first erase/program count and the second erase/program count.
With respect to dependent claim 6 Zhang/Palmer/Kanno discloses wherein the determining the data hotness of the data stored in the virtual block based on the erase/program state and the data distribution state includes: adjusting the data distribution state according to a preset adjustment coefficient to generate an adjusted data distribution state; and determining the data hotness of the data stored in the virtual block based on the erase/program state and the adjusted data distribution state [adjusted heuristic/parameter may be used to determine data hotness – Zhang 0113, 0115, table 2, claim 1-5].
With respect to dependent claim 7 Zhang/Palmer/Kanno discloses wherein the determining the data hotness of the data stored in the virtual block based on the erase/program state and the adjusted data distribution state includes determining a first ratio between the erase/program state and the adjusted data distribution state, the first ratio to represent the data hotness of the data stored in the virtual block [Zhang table 2, claim 1-5].
With respect to dependent claim 8 Zhang/Palmer/Kanno wherein the larger the first ratio, the colder the data stored in the virtual block [Zhang table 2, claim 1-5].
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure:
Dai US PGPUB # 20170285971 teaches hotness based data storage for facilitating garbage collection. For target data to be stored into a flash drive, hotness of the target is determined, which indicates an expected update frequency of the target data. Then the in-use blocks in the flash drive are searched for a matching block for storing the target data, such that hotness of data being stored in the matching block matches the hotness of the target data. If no matching block is found, a free block is selected for storing the target data. The selection of the free block is based on the hotness of the target data and a degree of wear of the free block.
Bennett US PGPUB # 20100325351 teaches a process of recovering space that is no longer being used for storage of current data, called garbage collection, may interfere with the rapid access to data in other memory locations of the memory system during the erase period. The effects of garbage collection on system performance may be mitigated by performing portions of the process contemporaneously with the user initiated reading and writing operations. The memory circuits and the data may also be configured such that the data is stored in stripes of a RAID array and the scheduling of the erase operations may be arranged so that the erase operations for garbage collection are hidden from the user operations.
When responding to this Office Action, any new claims and/or limitations should be accompanied by a reference as to where the new claims and/or limitations are supported in the original disclosure.
Any inquiry concerning this communication or earlier communication from the examiner should be directed to MARWAN AYASH at (571)270-1179. The examiner may be reached via email at marwan.ayash@uspto.gov – provided that applicant files form PTO/SB/439 to authorize internet communication, found online at http://www.uspto.gov/sites/default/files/documents/sb0439.pdf
The examiner can normally be reached 9a-530p M-R. Examiner interviews are available via telephone, in-person, and video conferencing using a USPTO supplied web-based collaboration tool. To schedule an interview, applicant is encouraged to use the USPTO Automated Interview Request (AIR) at http://www.uspto.gov/interviewpractice.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, Rocio del Mar Perez-Velez can be reached on 571-270-5935. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of an application may be obtained from the Patent Application Information Retrieval (PAIR) system. Status information for published applications may be obtained from either Private PAIR or Public PAIR. Status information for unpublished applications is available through Private PAIR only. For more information about the PAIR system, see http://pair-direct.uspto.gov. Should you have questions on access to the Private PAIR system, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative or access to the automated information system, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/Marwan Ayash/
Examiner, Art Unit 2133
/ROCIO DEL MAR PEREZ-VELEZ/Supervisory Patent Examiner, Art Unit 2133