DETAILED ACTION
Claims 1-24 are pending in this application.
Claims 11-20 are withdrawn.
Claims 1-10 and 21-24 are rejected.
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 .
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.
Claim(s) 1-10 and 21-24 is/are rejected under 35 U.S.C. 103 as being unpatentable over Li et al. (U.S. PGPub No. 2022/0188225) hereinafter Li’225 in view of Woo et al. (U.S. PGPub No. 2008/0120488) in view of Li et al. (U.S. PGPub No. 2014/0082323) hereinafter Li’323
Claim 1
Li (2022/0188225) teaches:
A multimode solid-state drive (SSD), comprising:
a plurality of flash memory chips addressable via physical block addresses (PBAs); and P. 0027 and FIG. 1 flash memory 40 supported by an LBA/PBA mapping system 20; P. 0002 an SSD may include a plurality of flash memory chips
a controller chip that utilizes a set of mapping tables to map logical block addresses (LBAs) to PBAs, FIG. 1 and P. 0027 controller 16 utilizes a LBA/PBA mapping system 20; FIG. 2 and P. 0029 the LBA/PBA map 38 includes a map-page layer with a plurality of mpages [mapping tables] wherein each mapping table […] is partitioned into a set of sub-tables, […] and wherein sub-table sizes are optimized during a garbage collection (GC) process that includes: […] FIG. 3 and P. 0033 each mpage includes multiple map-entries [sub-tables]
[…] storing data associated with each group of consecutive LBAs to an associated group of consecutive PBAs during a GC copy operation; FIG. 9 and P. 0056-57 during mpage garbage collection, map-entries with valid pointers are copied into a newly allocated mpage; P. 0036-37 a single map-entry map represent contiguous LBAs stored contiguously in physical storage space
updating associated sub-tables, wherein only a first PBA of each group of consecutive PBAs is stored in the associated sub-table; and FIG. 3 and P. 0037 n number of contiguous LBAs {Lfirst, Lfirst+1, Lfirst+2, . . . , Lfirst+n−1} are mapped to n compressed blocks {C0, C1, C2, . . . , Cn-1} stored over a contiguous physical storage space. Each map-entry [sub-table] contains the leading LBA Lfirst and the location of compressed block C0 in the physical storage space [analogous to PBA]; P. 0057 and FIG. 9 during garbage collection a new mpage is allocated and the valid map-entries are copied into the new mpage; P. 0047-49 if a new map-page entry Ej (associated with newly written data) is contiguous to an existing valid map-entry Ei [sub-table], the map-entries are merged
updating a metadata block for each associated sub-table to identify un-stored PBAs in the associated sub-table. FIG. 4 and P. 0038-39 a map-entry includes a variable-size trailer [metadata] identifying the size of the remaining n-1 compressed blocks Ci. The size of each Ci and physical location of C0 is enough to access any compressed block Ci [note: the claim does not specify how the un-stored PBAs are identified in the metadata block]; P. 0048-49 new map-page entry Ej is converted to a concatenation pointer (part of trailer see FIG. 4) which is merged with the concatenation pointer of Ei
Li’225 does not explicitly teach sorting identified valid LBAs to identify groups of consecutive LBAs.
Woo (2008/0120488) teaches:
selecting a group of memory blocks and identifying valid LBAs of still-valid data in the memory blocks; sorting the valid LBAs to identify groups of consecutive LBAs; P. 0062 and FIG. 10 the operation unit 400 checks a spare area of consecutive physical pages in operation S901 to determine whether a logical page offset recorded in a spare area increases sequentially
storing data associated with each group of consecutive LBAs to an associated group of consecutive PBAs during a GC copy operation; P. 0065 and FIG. 10 in a copy merge operation in S902, operation unit 400 successively copies the valid logical pages to the log block, then transfers the log block to a new data block in S904
It would have been obvious to a person with ordinary skill in the art at the effective filing date of the application to include the invention of Li’225 with sorting identified valid LBAs to identify groups of consecutive LBAs taught by Woo
The motivation being to generate new free blocks (See Woo P. 0063)
The systems of Li’225 and Woo do not explicitly teach each mapping table being configured for a different LBA block size, and each mapping table partitioned into sub-tables with a fixed number of entries.
Li (2014/0082323) teaches:
a plurality of flash memory chips addressable via physical block addresses (PBAs); and P. 0024 and FIG. 1 memory devices 110-1 to 110-D comprises flash memory cells managed using a logical to physical mapping scheme
a controller chip that utilizes a set of mapping tables to map logical block addresses (LBAs) to PBAs, wherein each mapping table is configured for a different LBA block size and each is partitioned into a set of sub-tables, wherein each sub-table is configured to map a predefined number of LBAs to PBAs, P. 0030 Each mapping unit (MU) 203 comprises a physical address (PA) data structure (e.g., table) comprising a fixed number of entries each mapping a logical page to a physical page; P. 0035 first portion 305 of each MU 303 can comprise mapping data indicating locations of a number of physical data units having a size defined by the variable data unit type; P. 0037 entries of a mapping table can indicate locations on the memory of physical data units having a size other than the base data unit size, which may be a multiple of the base data unit size
It would have been obvious to a person with ordinary skill in the art at the effective filing date of the application to include the invention of Li’225 and Woo with each mapping table being configured for a different LBA block size, and each mapping table partitioned into sub-tables with a fixed number of entries taught by Li’323.
The motivation being improved garbage collection efficiency and reduced write amplification (See Li’323 P. 0016)
The systems of Li’225, Woo and Li’323 are analogous because they are from the “same field of endeavor” and from the same “problem solving area.” Namely, they are both from the field of memory systems.
Therefore it would have been obvious to combine Li’225 and Woo with Li’323 to obtain the invention as recited in claims 1-5.
Claim 2
Li (2022/0188225) teaches:
The multimode SSD of claim 1, wherein updating associated sub-tables includes: initially storing in the associated sub-table all of the PBAs in the group of consecutive PBAs; and P. 0047 P. 0047 a newly generated map-page entry Ej is inserted into an mpage, the mpage already storing an map-page entry Ei with LBAs that are analogous to LBAs in Ej
removing all of the PBAs in the group of consecutive PBAs from the associated sub-table, except for the first PBA. P. 0047-49 if a new map-page entry Ej (associated with newly written data) is contiguous to an existing valid map-entry Ei [sub-table], the map-entries are merged
Claim 3
Li (2022/0188225) teaches:
The multimode SSD of claim 1, wherein updating the metadata block includes entering a data pair {x, y} where x refers to a first un-stored PBA and y refers to a number of un-stored PBAs. FIG. 4 and P. 0038-39 a map-entry includes a variable-size trailer [metadata] identifying the size of the remaining n-1 compressed blocks Ci [i.e. the size of C1 in FIG. 4 refers to the first un-stored PBA]. The size of each Ci and physical location of C0 is enough to access any compressed block Ci [note: the claim does not specify how the un-stored PBAs are identified in the metadata block]; P. 0047-49 new map-page entry Ej is converted to a concatenation pointer including: w, the number of contiguous LBAs covered by the entry
Claim 4
Li (2022/0188225) teaches:
The multimode SSD of claim 1, wherein the controller chip performs a read request from a host according to a process that includes: for each LBA in the read request, locate the associated sub-table and analyze an associated metadata block to determine a corresponding PBA; P. 0040 and FIG. 5 a read request covering m LBAs {L0, L0+1, L0+2, . . . , L0+m−1} is received, and applicable mpages are searched for map-entry pointers and associated map-entries with LBA ranges that overlap with the read request. Each map-entry is used to identify the physical locations {P0, P1, . . . , Pd} of each block associated with the read request
read data from memory for each corresponding PBA; and […] send data to the host. P. 0040 storage devices fetch and decompress data blocks from {P0, P1, . . . , Pd} to serve the read request
Call (2017/0235488) teaches:
perform error correction code (ECC) decoding […] P. 0051 data may be stored with error correction code (ECC) bits
Claim 5
Li (2022/0188225) teaches:
The multimode SSD of claim 1, wherein the controller chip performs a write request from a host according to a process that includes: write data to at least one set of consecutive PBAs; P. 0041 and FIG. 6 a write request covering m LBAs {L0, L0+1, L0+2, . . . , L0+m−1} is received
locate at least one sub-table corresponding to LBAs of the write request; P. 0041 and FIG. 6 applicable mpages are searched for map-entry pointers and associated map-entries to identify map-entries whose LBA ranges overlap with the write request
update the at least one sub-table; and P. 0043-46 and FIG. 6 new map-entries are generated for the write request and inserted into the mpage
update the associated metadata blocks of the at least one sub-table if a PBA removal pattern is changed. P. 0047-49 and FIG. 6 the new map-entry Ej contains LBAs contiguous with an existing valid map-entry Ei, the new map-entry Ej is converted to a concatenation pointer and merged with the concatenation pointer of map-entry of Ei
Claim 6
Li (2022/0188225) teaches:
A method for optimizing sub-table sizes during a garbage collection (GC) process in a multimode solid-state drive (SSD) having a plurality of flash memory chips addressable via physical block addresses (PBA) and P. 0027 and FIG. 1 flash memory 40 supported by an LBA/PBA mapping system 20; P. 0002 an solid-state data storage device may include a plurality of flash memory chips
a controller chip that utilizes a set of mapping tables to map logical block addresses (LBAs) to PBAs FIG. 1 and P. 0027 controller 16 utilizes a LBA/PBA mapping system 20; FIG. 2 and P. 0029 the LBA/PBA map 38 includes a map-page layer with a plurality of mpages [mapping tables] and wherein each mapping table is partitioned into a set of sub-tables, […] FIG. 3 and P. 0033 each mpage includes multiple map-entries [sub-tables] […] comprising:
selecting a group of memory blocks and identifying valid LBAs of still-valid data in the memory blocks; sorting the valid LBAs to identify groups of consecutive LBAs; storing data associated with each group of consecutive LBAs to an associated group of consecutive PBAs during a GC copy operation; FIG. 9 and P. 0056-57 during mpage garbage collection, map-entries with valid pointers are copied into a newly allocated mpage; P. 0036-37 a single map-entry map represent contiguous LBAs stored contiguously in physical storage space
updating associated sub-tables, wherein only a first PBA of each group of consecutive PBAs is stored in the associated sub-table; and FIG. 3 and P. 0037 n number of contiguous LBAs {Lfirst, Lfirst+1, Lfirst+2, . . . , Lfirst+n−1} are mapped to n compressed blocks {C0, C1, C2, . . . , Cn-1} stored over a contiguous physical storage space. Each map-entry [sub-table] contains the leading LBA Lfirst and the location of compressed block C0 in the physical storage space [analogous to PBA]; P. 0057 and FIG. 9 during garbage collection a new mpage is allocated and the valid map-entries are copied into the new mpage; P. 0047-49 if a new map-page entry Ej (associated with newly written data) is contiguous to an existing valid map-entry Ei [sub-table], the map-entries are merged
updating a metadata block for each associated sub-table to identify un-stored PBAs in the associated sub-table. FIG. 4 and P. 0038-39 a map-entry includes a variable-size trailer [metadata] identifying the size of the remaining n-1 compressed blocks Ci. The size of each Ci and physical location of C0 is enough to access any compressed block Ci [note: the claim does not specify how the un-stored PBAs are identified in the metadata block]; P. 0048-49 new map-page entry Ej is converted to a concatenation pointer (part of trailer see FIG. 4) which is merged with the concatenation pointer of Ei
Li’225 does not explicitly teach sorting identified valid LBAs to identify groups of consecutive LBAs.
Woo (2008/0120488) teaches:
selecting a group of memory blocks and identifying valid LBAs of still-valid data in the memory blocks; sorting the valid LBAs to identify groups of consecutive LBAs; P. 0062 and FIG. 10 the operation unit 400 checks a spare area of consecutive physical pages in operation S901 to determine whether a logical page offset recorded in a spare area increases sequentially
storing data associated with each group of consecutive LBAs to an associated group of consecutive PBAs during a GC copy operation; P. 0065 and FIG. 10 in a copy merge operation in S902, operation unit 400 successively copies the valid logical pages to the log block, then transfers the log block to a new data block in S904
It would have been obvious to a person with ordinary skill in the art at the effective filing date of the application to include the invention of Li’225 with sorting identified valid LBAs to identify groups of consecutive LBAs taught by Woo
The motivation being to generate new free blocks (See Woo P. 0063)
The systems of Li’225 and Woo do not explicitly teach each mapping table being configured for a different LBA block size, and each mapping table partitioned into sub-tables with a fixed number of entries.
Li (2014/0082323) teaches:
a controller chip that utilizes a set of mapping tables to map logical block addresses (LBAs) to PBAs and wherein each mapping table is partitioned into a set of sub-tables, and wherein each sub-table is configured to map a predefined number of LBAs to PBAs, the method comprising:
P. 0030 Each mapping unit (MU) 203 comprises a physical address (PA) data structure (e.g., table) comprising a fixed number of entries each mapping a logical page to a physical page; P. 0035 first portion 305 of each MU 303 can comprise mapping data indicating locations of a number of physical data units having a size defined by the variable data unit type; P. 0037 entries of a mapping table can indicate locations on the memory of physical data units having a size other than the base data unit size, which may be a multiple of the base data unit size
It would have been obvious to a person with ordinary skill in the art at the effective filing date of the application to include the invention of Li’225 and Woo with each mapping table being configured for a different LBA block size, and each mapping table partitioned into sub-tables with a fixed number of entries taught by Li’323.
The motivation being improved garbage collection efficiency and reduced write amplification (See Li’323 P. 0016)
The systems of Li’225, Woo and Li’323 are analogous because they are from the “same field of endeavor” and from the same “problem solving area.” Namely, they are both from the field of memory systems.
Therefore it would have been obvious to combine Li’225 and Woo with Li’323 to obtain the invention as recited in claims 6-10.
Claim 7
Li (2022/0188225) teaches:
The method of claim 6, wherein updating associated sub-tables includes: initially storing in the associated sub-table all of the PBAs in the group of consecutive PBAs; and P. 0047 a newly generated map-page entry Ej is inserted into an mpage, the mpage already storing an map-page entry Ei with LBAs that are analogous to LBAs in Ej
removing all of the PBAs in the group of consecutive PBAs from the associated sub-table, except for the first PBA. P. 0047-49 if a new map-page entry Ej (associated with newly written data) is contiguous to an existing valid map-entry Ei [sub-table], the map-entries are merged
Claim 8
Li (2022/0188225) teaches:
The method of claim 6, wherein updating the metadata block includes entering a data pair {x, y} where x refers to a first un-stored PBA and y refers to a number of un-stored PBAs. FIG. 4 and P. 0038-39 a map-entry includes a variable-size trailer [metadata] identifying the size of the remaining n-1 compressed blocks Ci [i.e. the size of C1 in FIG. 4 refers to the first un-stored PBA]. The size of each Ci and physical location of C0 is enough to access any compressed block Ci [note: the claim does not specify how the un-stored PBAs are identified in the metadata block]; P. 0047-49 new map-page entry Ej is converted to a concatenation pointer including: w, the number of contiguous LBAs covered by the entry
Claim 9
Li (2022/0188225) teaches:
The method of claim 6, wherein the controller chip performs a read request from a host according to a process that includes: for each LBA in the read request, locate the associated sub-table and analyze an associated metadata block to determine a corresponding PBA; P. 0040 and FIG. 5 a read request covering m LBAs {L0, L0+1, L0+2, . . . , L0+m−1} is received, and applicable mpages are searched for map-entry pointers and associated map-entries with LBA ranges that overlap with the read request. Each map-entry is used to identify the physical locations {P0, P1, . . . , Pd} of each block associated with the read request
read data from memory for each corresponding PBA; and […] send data to the host. P. 0040 storage devices fetch and decompress data blocks from {P0, P1, . . . , Pd} to serve the read request
The systems of Li and Woo do not explicitly teach error correcting data.
Call (2017/0235488) teaches:
perform error correction code (ECC) decoding […] P. 0051 data may be stored with error correction code (ECC) bits
It would have been obvious to a person with ordinary skill in the art at the effective filing date of the application to include the invention of Li and Woo with each mapping table being configured for a different LBA block size taught by Call
The motivation being ECC bits are a well-known technique for error correction.
The systems of Li, Woo and Call are analogous because they are from the “same field of endeavor” and from the same “problem solving area.” Namely, they are both from the field of memory systems.
Therefore it would have been obvious to combine Li and Woo with Call to obtain the invention as recited in claim 9.
Claim 10
Li (2022/0188225) teaches:
The method of claim 6, wherein the controller chip performs a write request from a host according to a process that includes: write data to at least one set of consecutive PBAs; P. 0041 and FIG. 6 a write request covering m LBAs {L0, L0+1, L0+2, . . . , L0+m−1} is received
locate at least one sub-table corresponding to LBAs of the write request; P. 0041 and FIG. 6 applicable mpages are searched for map-entry pointers and associated map-entries to identify map-entries whose LBA ranges overlap with the write request
update the at least one sub-table; and P. 0043-46 and FIG. 6 new map-entries are generated for the write request and inserted into the mpage
update the associated metadata blocks of the at least one sub-table if a PBA removal pattern is changed. P. 0047-49 and FIG. 6 the new map-entry Ej contains LBAs contiguous with an existing valid map-entry Ei, the new map-entry Ej is converted to a concatenation pointer and merged with the concatenation pointer of map-entry of Ei
Claim 21
Li (2014/0082323) teaches:
The multimode SSD of claim 1, wherein corresponding LBA and PBA block sizes are equal in each LBA/PBA mapping. P. 0033 each of the MUs 303 can store a fixed amount of mapping data used to map between logical and physical addresses. The fixed amount of data can be equal to the page size associated with the memory (e.g., memory 110 shown in FIG. 1) to which data is to be written
Claim 22
Li (2022/0188225) teaches:
The multimode SSD of claim 1, wherein each sub-table is stored in DRAM separately from other sub-tables. P. 0027 mapping system 20 utilizes a tiered LBA/PBA map 38 that is stored in DRAM 38
Claim 23
Li (2014/0082323) teaches:
The method of claim 6, wherein corresponding LBA and PBA block sizes are equal in each LBA/PBA mapping. P. 0033 each of the MUs 303 can store a fixed amount of mapping data used to map between logical and physical addresses. The fixed amount of data can be equal to the page size associated with the memory (e.g., memory 110 shown in FIG. 1) to which data is to be written
Claim 24
Li (2022/0188225) teaches:
The method of claims 6, wherein each sub-table is stored in DRAM separately from other sub-tables. P. 0027 mapping system 20 utilizes a tiered LBA/PBA map 38 that is stored in DRAM 38
Conclusion
Applicant's amendment necessitated the new ground(s) of rejection presented in this Office action. Accordingly, THIS ACTION IS MADE FINAL. See MPEP § 706.07(a). Applicant is reminded of the extension of time policy as set forth in 37 CFR 1.136(a).
A shortened statutory period for reply to this final action is set to expire THREE MONTHS from the mailing date of this action. In the event a first reply is filed within TWO MONTHS of the mailing date of this final action and the advisory action is not mailed until after the end of the THREE-MONTH shortened statutory period, then the shortened statutory period will expire on the date the advisory action is mailed, and any nonprovisional extension fee (37 CFR 1.17(a)) pursuant to 37 CFR 1.136(a) will be calculated from the mailing date of the advisory action. In no event, however, will the statutory period for reply expire later than SIX MONTHS from the mailing date of this final action.
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure.
Zhang (2018/0267896) teaches storing data with contiguous logical addresses in contiguous physical addresses, the metadata mapping the logical address to an aggregation address that identifies a starting physical address and the number of contiguous blocks.
Krafka (2017/0242785) teaches moving a contiguous sequence of valid logical addresses from a first logical stripe to a second logical stripe.
Yoon (2023/0141409) which teaches a preset mapping unit size for updating mapping table entries
Any inquiry concerning this communication or earlier communications from the examiner should be directed to STEPHANIE WU whose telephone number is (571)272-0257. The examiner can normally be reached 1pm to 6pm, and 10pm to 1am Eastern time (10am to 3pm, and 7pm to 10pm Pacific time).
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 at (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 published or unpublished applications may be obtained from Patent Center. Unpublished application information in Patent Center is available to registered users. To file and manage patent submissions in Patent Center, visit: https://patentcenter.uspto.gov. Visit https://www.uspto.gov/patents/apply/patent-center for more information about Patent Center and https://www.uspto.gov/patents/docx for information about filing in DOCX format. For additional questions, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/STEPHANIE WU/ Primary Examiner, Art Unit 2133
Prosecution Insights